This Statement is False

2012-01-04T00:51:00.000-08:00

I added an intro, a summary, and a few more ideas to the Code Google post. It needs a better name that doesn't just mean "search" to people and also doesn't include trademarked words :).

Code Google

2011-12-27T00:02:00.000-08:00

UPDATE: Added structure and a few more ideas...

Intro

Have you ever seen someone include a giant open source library in a project, just to access some small part of its functionality? It's very important to have someone else write, debug, and maintain a large part of your code, but when you do this over and over, it can add quite a lot of bloat to an app for comparatively little gain in functionality.

This is a huge problem, as I see it, but maybe there is a solution?

What about allowing people to integrate only small subsets of modules into their code. I'm calling this idea "code google," for lack of a better term, although it's a LOT more than just search. It involves search, analysis, IDE integration, and social networking, so that library developers can track what parts of their code are actually being used. It's far from trivial to implement, but I think it could be very useful

Before our company started, a friend and I wrote a fair-sized game in LISP (a couple tens of thousands of lines) and later versions used OO languages (both class-based and prototype-based). My friend and I seem both to be coming to the conclusion that what is happening in the Java world is not a good thing. A lot of modern programming seems actually to be just gluing together libraries and frameworks. Many times, frameworks are chosen because of a few of their features and glued onto other frameworks similarly chosen.

Module systems concentrate on versioning in the large -- each framework is versioned as a whole, despite the fact that so many people (apparently) pick a small set of features and use that. Programmers achieve modularity by marking off a segment of code and declaring it to be a module. APIs are defined explicitly by developers, but I, on the other hand, often need to use implicit APIs that the developers didn't consider to be "first class," when they wrote their code.

Code Search

What I think is needed, in addition to explicit module declaration, is a "code Google" that searches the vast sea of code and finds a small subset that does what I need at the time. Curiously enough, this already exists, in part, for Haskell programmers, with Hoogle, that lets you search for functions based on their type signatures. It might be hard to imagine how this could possibly work in Java, because you won't necessarily know the name of the actual type you are looking for, but it becomes more practical as Java gets closer to LISP (or Haskell), because it becomes easier to express generic behavior without knowing as many explicit names. A "code Google" for Java could allow you to inline a method signature without knowing the name of the SAM type that the code needs. This could be done before Java actually has a lambda syntax.

Closures will go a long way toward making Java simpler to use, since so many design patterns are trivial with them -- I made a command-driven framework in Java 1.0.4, before there were even anonymous inner classes and had to make a separate class file for each of several hundred commands. You can look at how much much easier AWT became after the introduction of anonymous inner classes for an example of this detangling; you don't have to subclass Button, anymore, when you make a GUI, you just make an anonymous event handler inner class. In Java 8 (or later?), each of these 1.0.4 files would just be a lambda expression -- same anonymous inner class mechanism as in Java 6, but it's a LOT easier on the eyes.

Code Snippet Retrieval

In addition to search, Code Google should be able to retrieve the dependencies of the code snippet you need and pack it all up for you in a library jar with source included. Hoogle does not do anything like this -- it just gets you to the module version. Again, as Java gets closer to LISP, dependencies won't need to be as tangled up because as closures become easier to use and more prevalent in code, it becomes easier to write code that stands on its own (see the AWT evolution for examples). It's already possible to do this in Java, by using anonymous inner classes, but these are verbose and a lot of people don't like to use them (except when they write event handlers :) ).

Social Networking and IDE integration

Once you have the snippet, all jarred up, there should be a way to track the search query and the version of the module it came from, so you can automatically update your code. When someone downloads a snippet, there should be a social networking tie-in with tools that the developers use so that they can see an annotation in their code to let them know that people are using that particular API, so that the the developer doesn't unintentionally change or remove that implicit API. If the search does fail because the code is no longer in a module, someone can still spawn another open source module to support it. The social networking support should also indicate how many people are using a piece of functionality and allow people to attach comments to the code so the developers and other users can see them.

As an alternative to IDE integration, there should also be command line and web-based tools for your project. Mods to Gitweb and Fossil, maybe?

Summary

Code Search indexes vast amounts of code and lets people search for what they need by specifying type signatures in addition to just unstructured text
Code Snippet Retrieval incorporates a snippet and its dependencies into your project's codebase and includes metadata that describes where the snippet came from (the module, version number, site, etc.)
IDE Integration puts this information at your fingertips so users can be informed when new versions are available and developers can be informed which pieces of their code that people are finding important and how many people are using the code
Social Networking lets people comment and collaborate with the developers to keep them connected to the users of their code

The Eclipse Code Recommenders plugin looks like it's trying to do the search portion, at least.

Podcast interview about Death of the Vele

2011-09-27T10:13:00.000-07:00

I already blabbed this in a bunch of emails to people, but just in case... Scott Dunphy of New Style interviewed me about Death of the Vele, here. This was the first time I've been interviewed for anything; I was surprised I sounded coherent -- I thought it might come out a lot less cohesive than it did when I listened to it.

Quick update on The Philosopher's Stone

2011-08-18T10:17:00.000-07:00

I have changed TPS many times in the past year and a half, but the core idea is still to be a collaborative story telling RPG that feels like a traditional RPG. The latest version of it is called Death of the Vele and the (lame) website is here It has a link to the latest rules.

Wow, taking a look at the old rules, I see that I have streamlined the mechanics a LOT since last year. They are simpler, lighter weight, and more intuitive. There are also tools to promote more integrated and structured stories (spotlights, hitting aspects, etc.). Death of the Vele also adds a back story (which you can remove if you don't like, of course).

I'm hoping to publish Death of the Vele within the next 12 months. In the mean time, the rules are out there for free, so anyone who wants to can use them.

Here is the feature list from the latest copy of the rules:

Collaborative, but feels like a traditional RPG
Your characters are yours
Supports campaign-length stories
Game play stays at the table
Characters don’t always do their best -- sometimes they have an off-day, even if their stats say they’re fine, but this is your decision
The Right of Challenge -- if the other players don’t buy it, you can’t do it
Show, don’t tell -- a lot of communication happens through scenes and events
Answer questions with scenes -- if players want to know, scenes reveal the answer
Characters are naturally “woven together”
Your characters will get the spotlight
Supports visiting gamers

Applied Lambda Calculus

2011-07-08T09:47:00.000-07:00

I made a slide presentation introducing Lambda Calculus and some functional concepts (lazy evaluation, how to represent data, etc.). It also talks about a Lambda Calculator I wrote, which does LC in three ways:

compiles into JavaScript
interprets through substitution (alpha, beta, and eta) and shows the steps
compiles into virtual machine code (and can execute it)

The VM still fails on some complex cases, but when I have that working, I want to make it generate native code, using LLVM.

I open sourced all this, under the ZLIB license.

Oh, I also started on a Lambda Calculus version of space invaders, which is in there, too :)

LC is a really nice language. I wasn't able to find a modern, untyped, lazy language. It seems like functional languages have all gone the way of static typing, but I'm hoping it doesn't have to end that way. Looking at what Anders Møller and co. are doing with TAJS at Aarhus University and BRICS gives me hope that some day, the computer will tell the type information to the programmer and not the other way around like it is, today.

So I wrote my own "Lambda Calculator." Really, it was so I could teach a friend about computers, but I am relatively new to LC and I thought I really ought to write something in it, which is why I chose Space Invaders. So far, I have 55 lines of space invader code written. It doesn't do all that much, but I think it's still informative. In the mean time, I had to make that slide presentation and fix bugs in the calculator.

I had a lot of fun writing space invaders and I think I'm starting to understand the power of having lazy evaluation, currying, etc. built into a language (shame on me for not using Haskell, yet). Check out the slides for more info :)

Calculator/spreadsheet tool for Acme

2010-10-22T04:02:00.001-07:00

I got Plan9 from User Space and started messing with it in the hopes of getting a nice toolbench going with Acme. Since I wrote Ober, I've been interested in this idea. Now, I'll probably rewrite it in Go. I'm wondering if I can just use named pipes to mimic what Acme does with its 9p interface.

Anyway, I wrote a simplified version of the Calc tool I wrote for Ober and I put it, here. The calc tool searches an Acme window for variables and their values and some code at the bottom. Then, it executes the code, sending the variables and values to its stdin. The code is expected to output new values for some of the variables. Calc parses the output and replaces the new values into the window. I'm also including two wrappers that make it easy to write calc scripts in rc or Go, so you can say something like this:

Bob's age=30, he is yearsleft=0 years away from retirement (calc).

#!/usr/bin/env calcgo
yearsleft = 55 - age

If you middle-click "calc" in the text, it will update the window to show yearsleft=25.

The Philosopher's Stone

2010-04-17T10:31:00.000-07:00

I've been searching for the "Philosopher's Stone" of role playing for years -- a role playing system that combines traditional role playing with the collaborative story telling of Universalis. I think the Blood Red Sands system might allow this. By replacing the coins of Universalis with dice, BRS introduces relative differences between traits, an element of risk into contesting for narrative control, and a competitive framework for play. I think this difference can allow it to support traditional role playing better than Universalis.

That's how the document for the new game I'm working on starts. I found Ralph Mazza's Blood Red Sands about 5 weeks ago, when I checked out the Ramshead Publishing site, to see if there was anything new going on. Wow, was there ever! Blood Red Sands is a highly stylized, competitive role playing/story telling game about heroes and their ordeals as they strive to confront the evil, despotic Witch King in a blasted land called Abalahn. My summary of Blood Red Sands is here and the play test rules are here. There are some discussions about BRS on Story-Games.com.

Universalis is really a different type of game (which is why it was named "most innovative indie game" of 2002). It's not really a role playing game; it's a story telling game. Theory From the Closet interviews Mike Holmes (coauthor) and he talks quite a bit about Universalis here. A later podcast interviews Ralph Mazza about Blood Red Sands, Universalis, and other things here.

I started playing Universalis in December, 2005. In December, 2007, I combined Universalis with FATE and PDQ in a campaign we ran for over a year. We started every session with a few Universalis scenes (usually 20-40 minutes of play), then we played a mashup of PDQ and FATE, incorporating the new information from the Universalis scenes, and we ended a lot of the sessions with Universalis, too. It worked really well. During the Universalis sessions, there were a few ground-rules (enforced by Universalis gimmicks), but other than that, the players had free-reign with the story. They could define NPC motivations, stage events that took place "meanwhile", etc. I was tag-team GMing with a friend and we had to deal with all of the curves the players threw at us -- the players introduced some things into the story we really hadn't thought of.

Universalis is also how we did all of our cut-scenes. What made it radically different from the way MOST GMs do their cut-scenes is that the players could take over in mid-scene and change things. You can look at a bunch of the Universalis logs here.

I loved the Universalis integration so much, that I've been searching for "clean" system ever since; one that allows story telling and role playing all the time. I tried F#, which is a great game (you should check it out). It comes close, but it doesn't quite do what I want. Then I saw Blood Red Sands.

In Blood Red Sands, one player plays their "hero" character, going through ordeals on the way to confronting the Witch King, while the other each play a "faction" which may be aligned with the Witch King, opposed, or neutral. BRS is played on two levels at the same time: the story level, where the characters' loyalties are defined by the ordeal and the game level, where the players are all competing, even though their characters may be allies in the story. This can lead to some interesting story twists and it can support behavior like Pippin's in The Lord of the Rings (check this post, for example). BRS is a great game and I consider the underlying system to be the next generation of Universalis. Also, I think it can lend itself well to traditional role playing, in which every player gets to role play their character during a session.

So, my entry in the mix, The Philosopher's Stone. It uses the system from Blood Red Sands, so please by Blood Red Sands when it comes out, but it packages it in a different framework that (hopefully) supports traditional role playing. In The Philosopher's Stone, as in Blood Red Sands, no player is the designated Narrator (i.e. GM) for the whole session -- players trade off acting as the Narrator and they can even "steal" the position of Narrator (just like in Blood Red Sands).

The players cooperate to make the story within a mission/act framework where they define the mission and acts as well as objectives for the group of player characters. A player can counter an objective and steal the victory points for himself. Of course, the other players will try to stop him.

The BRS system underneath TPS contains two key mechanisms to limit the power of the current Narrator: challenges and contests. Any player can challenge the "fiction" that a Narrator composes -- the rationalization that supports a mechanic. This can't directly prevent a Narrator from using a mechanic, but it can force him to reframe the rationalization and may lead him to try a different tack. A contest allows a player to attempt to take over the position as Narrator, preempting what the Narrator was doing. I think these two mechanisms combine well to keep the player who is the Narrator from being "too harsh" on the other players.

One thing that is very different from other role playing games is that in TPS, players control "story components" in addition to their characters, which are NPCs, monsters, beasts, traps, hazards, etc. In fact, there are no NPC or other direct "actors" in the story that are not controlled by one of the players. This means that even in a scene without any player characters, the players are still involved, because at least some of the players will have story components present at the scene. When orcs squabble over who gets to eat a hobbit, it's different players controlling the orcs and one of those players might also have the hobbit in question as their player character (or it could be Neanderthals arguing over a Cro-Magnon captive or aliens planning to torture an earth man).

I don't think that controlling story components in addition to their characters will make it difficult for people to play. I think there will be scenes with only story components present, scenes with only characters present and scenes with both. In scenes with both that involve conflict, players will be attacking other players' characters and story components, so I think there's a clear objective.

So, that's the idea. We'll see if it works.

Xus Rsync/Bittorrent/Git approach

2010-02-08T22:30:00.000-08:00

Approach

I started working on my file sharing approach. Sharing will not involve deltas or packs, just chunks, by Git id. The idea is to share Git commits, with all of their associated tree and blob objects. They'll be shared using a manifest for each commit that exhaustively lists all of the chunks in that commit. A manifest will be a binary XML document (using fastinfoset, same as Xus uses for its protocol), since that's a pretty efficient binary serialization format (using BERencoding for numbers in a lot of places and whatnot) and then using another XML doc to list chunks for the manifest:

A commit manifest contains the serialized commit data, the commit id, and a list of tree object ids/crcs and blob ids with blob chunk ids/crcs
A commit manifest chunk list contains a list of chunks for the commit manifest file, since a commit manifest file could get large

I'll probably use an extra branch to store the chunks that a peer currently has for that branch. When it gets new chunks, it can store them in its chunk-branch for that Git branch (probably named [branch]-chunks). Git will properly reuse shared chunks because that's what Git does.

A word about chunks. Git stores its data compressed, but to get good chunks, we have to uncompress the data first and then break it into chunks. This is so that we can effectively scavenge the Git repository for chunks so that we can avoid downloading the ones we already have, ala rsync.

How rsync works

The brilliant idea of rsync is that you can cheaply compute a "rolling crc" as you "slide a window" down a file, byte-by-byte. An example of this type of crc is the standard shift-xor hash function a lot of people use for strings. For each byte in the string, shift the crc up one bit and xor the byte in. Assuming you are using a 32-bit hash, the hash is only "good" for 32 bytes of a string.

Here's an implementation of the Rsync chunk finder with a very simplistic rolling crc function:

import java.io.FileInputStream
import scala.collection.mutable.ArrayBuffer
import java.security.MessageDigest

object Rsync {
 def use(test: Boolean)(block: => Any) {
  if (test) {
   block
  } else {
   println("Usage: Findit [-hash string] | [-find file crc sha-1]")
   System.exit(1)
  }
 }
 
 def pad(n: BigInt, width: Int) = {
  val s = n.toString(16)

  if (s.length >= width) {
   s
  } else {
   ("%0"+(width - s.length)+"d").format(0)+s
  }
 }
 
 def next(hash: Long, number: Int) = {
  var p = 0
  var n = number

  for (i <- 1 to 8) {
   p ^= n
   n >>= 1
  }
  (hash << 1) | (p & 1)
 }

 def sha(msg: String) = {
  val digest = MessageDigest.getInstance("SHA1")
  val i = BigInt(digest.digest(msg.getBytes))

  digest.reset
  i
 }
 
 def find(file: String, crcIn: Long, shaIn: BigInt, len: Int): Int = {
  val input = new FileInputStream(file)
  var crc = 0L
  val buf = ArrayBuffer[Char]()
  var offset = -1
  var mask = (1 << len) - 1

  while (true) {
   val c = input.read()

   if (c == -1) {
    input.close
    return -1
   } else {
    offset += 1
    crc = next(crc, c)
    buf.append(c.asInstanceOf[Char])
    if (buf.length > len) buf.remove(0)
    if ((crc & mask) == crcIn && sha(buf.mkString) == shaIn) {
     input.close
     return offset
    }
   }
  }
  return -1
 }
 
 def main(args: Array[String]) {
  use(args.length > 0) {
   args(0) match {
   case "-hash" => use(args.length == 2)(println("args: -find file "+pad(BigInt(args(1).foldLeft(0L)(next(_, _))), 16)+" "+pad(sha(args(1)), 40)+" "+args(1).length))
   case "-find" => use(args.length == 5)(println("offset: "+find(args(1), BigInt(args(2), 16).longValue, BigInt(args(3), 16), args(4).toInt)))
   }
  }
 }
}

This is more or less what Xus will use. As you can see, you can efficiently update the crc a byte at a time, so it's quick to locate a chunk. When you have several chunks, just use a set of CRCs. As you scan the file, check each crc to see if it's in the set.

So after Xus gets a manifest it has to download all of the chunks it doesn't have. Here's how it will work:

Check the Git repository for the file id. If it's in there, no need to download
Check the Git repository for a previous version of that file (we can eventually include extra information in the manifest if the creator's Git detected a rename). If there is a previous version, scavenge the previous version for chunks using the rsync algorithm
If there are any outstanding chunks we need to download, request them from the DHT

Requesting from the DHT

When a peer needs to download a chunk, we use the topic as a DHT, backed by the master peer's storage:

Use a DHT message to send a chunk request to the peer with ID nearest the chunk's ID
If the peer does not have the chunk, it requests it from a topic master using a mini topic master DHT to distribute the load
Once the peer has the chunk, it connects to the requesting peer and transfers the chunk to it

Connecting to a Peer

Some peers may not be able to accept connections. This interferes with chunk sending requests. Xus has two ways to deal with this problem:

The preferred way is the connection service: if one peer can receive connections but the other cannot, the peer which can receive connections can delegate a message to the other peer to connect back to it
If neither peer can receive connections, they can delegate all of their messages through the topic master

So, there you have a fairly detailed idea of how I'm implementing the Xus file sharing service.

Story telling in role playing games

2010-01-26T01:36:00.000-08:00

I play a lot of indie RPGs, like Spirit of the Century and Swashbucklers of the Seven Skies, but for the past couple months, we've been retrying D&D 4e (and I'll be using "DM" below a lot of times in the generic sense). I tried it for 5 months in 2008, running a Keep on the Shadowfell adventure. I have to say that I think that was a mistake for Wizards. It's a dungeon. A lot of the monsters aren't intelligent (rats, oozes, skeletons, zombies). Etc. It ran like a 5 month long miniatures game. Maybe it was me, I don't know.

Nevertheless, we're giving 4e another go (this time, I even get to be a player!) D&D 4e has some great ideas and it has great resources for DMs. Since 2005, I've used techniques described in the "Group Storytelling" in the DMG2. You can find a lot of helpful hints for DMs out there on the net and I haven't read nearly all of them, but maybe I use some novel techniques. Some of these techniques were new to the veteran DMs and RPG designers I've spoken with. I created/independently discovered/borrowed/stole several techniques specifically to prevent wasting the work I do as a DM/story writer.

A friend of mine ran an adventure for us a while back and after we failed a search check in one room, I noticed him file away a sheet on which he had written a LOT of text. I asked him later if we were supposed to see that only if we succeeded in that roll, thus wasting all of that work. He said "yes." I thought it was a shame that he did all of that work and we never got to see it.

Usually, I have a campaign story arc, with subarcs for sections of the story. For each subarc (i.e. adventure), I do something kind of like what the DMG2 describes in the "Branching" section. Rather than make a tree with possibly dead scenes, I write a LINEAR story line which is really just a list of scenes, usually using an outline format in a google spreadsheet (this is great for collaborative DMing, by the way). This list represents the order in which I THINK the players are going to experience the scenes. I almost never have any "dead" scenes in my stories -- I work too hard coming up with ideas and fleshing them out to allow them to be skipped :).

Players almost never make the decisions I'm expecting them to make, so the actual order of scenes usually ends up different from the way I wrote it, with from-the-hip scenes inserted in the list as well, along with alterations to the original scenes (I usually change the spreadsheet as I run the adventure). To prevent the players from skipping over scenes and information that I've worked so hard to produce, I use a few techniques that they didn't mention in the branching section.

First, a few observations to keep in mind:

The players don't have a lot of information until the DM reveals it; they don't know what's behind every door or around every corner
The DM can ask a player to make a roll without telling them why; "make a perception roll"

If the players skip over a scene, there are a few techniques I use to "reclaim" the scene so I can present it to them later on:

if it is an appointment that they missed, make it a "chance meeting" later
if it was with a particular person who is out of the story now, reassign it to another person or use a messenger to convey the information
make a new scene on-the-fly that accomplishes the same goals

Sometimes the story requires a prerequisite before an event can happen, like searching, detecting an ambush, etc. Prerequisites can be a way to put a certain character in the spotlight, like requiring a certain ritual, a certain skill, a bloodline, a race, etc. Lock-and-key scenarios that require successful rolling can be a bit dicey (sorry :D). You don't want the players to blow a roll and fail to see the cool document with the burnt edges that you antiqued by heating up paper soaked with lemon juice! The "Avoiding Dead Branches" section in the DMG2 presents two alternatives for "fake" branches; i.e. situations that look like a branch, but where there is no actual chance of failure. The alternatives are setting the DC of the check to 1 and "dropping the pretense" by just telling the players they succeeded (i.e. no roll). Here are some techniques I use to make sure that the players get the information or have the experience that I put so much work into, but still "keep the pretense"...

Ball and cups

Ever see that magic trick, where the magician shuffles around 3 cups and you can't tell which cup has the ball under it? The first two cups you look at never have the ball; it's always in the third cup. That's because the magician has the ball in his hand.

When the players are searching for something which could be anywhere, sometimes I assign it to "the third place they check". So after they look in two empty rooms, the third room will have what they're looking for, regardless of what the map looks like.

Suppose the players are looking for clues. Prepare several clues for them to find and have them gain the clues on successful search rolls in a specific order, regardless of where they are when they actually do the searching. So they can search 5 rooms in a house, find two clues and then search the alley to find the third clue. If they succeed in each of the first 3 rooms in the house, they get the clues then. If they blow all of the rolls in the house and the alley, they can discover the clues in some other location entirely.

Well, aren't you clever!

Suppose you want to have the characters spot an ambush in a jungle way before it happens so they can ambush the ambushers. The D&D game mechanics represent keen senses as a high perception skill value. Call for a perception roll from the group and if they blow it, give them a "soft ball" random encounter. Wash-rinse-repeat until they get a successful roll. When they do succeed, run the "real" encounter where they get to surprise the ambushers as they are preparing the ambush. Instead of just declaring that the characters have surprised the ambushers, they surprise them "because" they succeeded on a perception roll.

Reality is how you perceive it

OK, this one is from Donjon. Sometimes, the players search for traps and none of the chests/doors/cabinets in the whole building actually have traps. If they ask to check for traps, sometimes you'll want to put a trap there anyway. If they blow the roll, it can explode, if they make it, they can disarm it. When the characters use their skills, the player is actually requesting some spot light time for their character. Give it to them.

Use rsync with Xus file sharing?

2010-01-21T00:23:00.000-08:00

I'm wondering if it would be a good thing to use a variant of the rsync algorithm with Xus file transfer. This would help save a lot of bandwidth for large files that only have small changes. One example is Sauerbraten maps, which can be 2M or more (after compression). When you move a tree, only a small part of the map file is changed, but without rsync behavior, pushing an update requires transferring the whole file.

At this point, Plexus breaks files into chunks that are 50K (if I remember correctly) and keys them by SHA-1 hashes. If we include rsync's rolling CRC with the chunk ID, that would be enough (I think) for a peer to determine whether it could reuse a chunk from its current file and avoid downloading a chunk. I'll have to check on rsync to see its default chunk size. We chose 50K based on tuning with Pastry and Xus' behavior will probably be very different.

Xus file sharing

2010-01-18T10:11:00.000-08:00

It's been a long time since my last post; various RL intrusions encroached on Xus. Now I'm starting the file sharing piece. I'm basing it on what I did in Plexus, but starting right away with Git integration instead of putting it off, since that seems to be a better way to actually have Git integration :).

Xus has kind of a weird profile for a p2p system. It's made to handle a mass of small clusters, rather than a giant, monolithic cloud. It's really based on the needs of Plexus, but I suspect other systems out there can benefit from it. In a monolithic p2p storage system like bittorrent or FreePastry's PAST, the cloud can (theoretically) be so large that the data can "live in the cloud". In a game like Plexus (or Sauerbraten), however, the clusters are small and may often drop to 0 users (like when the players for a particular world are asleep), so there needs to be a way to restore cluster state (so a world with no players is still up-to-date when a player joins, even if they weren't around recently).

The most straightforward way I could think of to accomplish this is just to use a Git repository for the Xus file cache and mirror it to a remote Git repository for backup/restore. When a topic space master boots a topic space, it can pull from a remote git repository to restore the state. To avoid a single point of failure, the owners can push to more than one designated repository. The DHT portion of the repository is only useful for peers that are connected, since the DHT expands and contracts, causing chunks to be copied around over time.

Storage:

each resource is tracked with a tag: an outer directory containing chunk-list file and a subdirectory with standard names
creator sends packed delta to topic owner
owner pushes delta to remote Git repository
owner returns signatures for the chunks, etc. to creator
creator stores chunks, etc. in the DHT.
creator gets an event when storage process is complete

Retrieval:

request tag from owner, which responds with ID of chunk-list file
retrieve chunk-list from DHT (which delegates to owner if chunk not in cache)
retrieve chunks from DHT (possibly delegating to owner to fill cache)
requester gets an event when the retrieval process is complete

Several owners is a good thing in this model, since they back the DHT cache.

So, that's the idea. I decided I'm going to include the source to jgit and its dependencies (jsch and jzlib) with this. Requiring on a properly installed command-line Git is just too much work to make developers do (or force their users to do). Requiring developers to download, test, and package a compatible version of JGit wouldn't be nice either. So I have some bloat now. I really don't see the file sharing part as being quite so optional, anyway. From my experience, nontrivial p2p apps tend toward bit torrent the same way most apps tend toward email clients (that's someone's law; maybe I'll get a comment with a citation for it).

Xus Milestone 1 complete

2009-10-11T11:10:00.000-07:00

According to my only somewhat extensive automated tests, Milestone 1 (Basic Xus) is now complete. That includes layers 1 and 2 and the property service (transient and persistent properties). Plexus relies heavily on its property service (currently backed by FreePastry) and I think it will be useful to other programs as well. It's kind of a persistent broadcast; it's really just for relatively small databases, like if you have to track a few hundred things for the topic, like player locations in a game or account credit, for instance. Plexus uses properties for player presence (nickname, which world they're connected to, etc.) and object information (location, orientation, costume, etc.) If you need to store large amounts of data, it might be appropriate to use the file storage service (coming soon and featuring optional Git integration) or maybe to add a database service (and contributing it back to the project would be nifty, too). DHT message routing is useful for this sort of thing, so you don't necessarily have to replicate all the data to all of the peers if you are storing a large amount.

When a peer successfully joins a topic, the topic owner sends it the current property values. Peers broadcast property settings or deletions to the topic and the topic owner keeps track of the properties for when new members join. This creates a very simple (some might even say simplistic) database for each topic. It's just key-value pairs of strings (like in Java's Properties object).

When you set a property, you specify whether the setting should be persistent. If a peer has storage turned on, persistent properties are stored in an XML file so that they are there next time the peer starts up. It usually only important for topic owners to store persistent properties, because other peers always get the latest properties for a topic when they connect to it (and they may have changed since the peer was last connected anyway).

Xus' file storage service and Git

2009-10-07T01:47:00.000-07:00

Xus has a 2-pronged approach for integrating its file storage with Git:

the basic file storage will just use ordinary file storage, with an approach similar to Git's, ensuring that Xus' model is "compatable" with Git's
provide a plugin that uses JGit (http://www.eclipse.org/egit/) for people who want to maintain a local Git repository

Each peer can be optionally Git-enabled, since the peers will only interact with a local Git repository. It doesn't use Git's protocol to exchange data, because we want Xus to be able to swarm downloads, but a Git-enabled peer could use Git-clone to seed its cache. Since the file storage protocol doesn't have to interact with Git, Xus just needs #1 to make sure that a peer can fetch everything it needs over the net. Since Git uses SHA-1 hashes as keys for almost every type of object, this shouldn't bloat the protocol too much. Note that when I say "protocol" here, I'm talking about the file storage service protocol, which rides inside of layer 2 messages, not Xus' layer 1 or layer 2 protocols.

The file storage service will break files into chunks and use the DHT to spread the chunks around. This is how we do it right now in Plexus; the directory and chunk models are ours and Plexus uses PAST (Pastry's DHT file storage service) to store and retrieve the objects (chunks, file chunk lists, and directories). Xus DHT file service will be similar to PAST's but not entirely the same. The chunk/chunk list/directory model will be similar to Plexus' but it also needs branches, commits, and tags, in order to use Git.

The Git model has been a milestone on Plexus since last year because I think it's crucial to power an open, collaborative gaming environment. In a completely open environment where anyone can change anything, version history ensures that people can't destroy data; they can only create new versions without some of the data, and signed commits make spoofing very difficult, allow people to rate authors based on their work, etc.

This also has the side effect of making a p2p version of Git :).

I don't think totally reimplementing PAST is a good idea for small clouds, because I believe data copying would kill the network. If the cloud is small, with peers joining and leaving slowly over time but never getting larger than 5, each time a new peer joins, it gets a copy of all of the data in storage. PAST does have caching and it works very well for large clouds where storage is built up slowly over time, but I don't think it works well for small rings. For this reason, I'm planning on only having the topic space masters replicate automatically (hopefully starting with a Git-cloned cache seed), but having "ordinary" peers "fill in the holes" from the topic space master peers on-demand. This will slow down initial requests, but amortize the impact on the network.

In practice, I think JGit integration will probably be the default, but I still want to provide it as a plugin as a courtesy to projects so they don't have to link in yet another third party library if they don't require it. Also, I want non-Git-enabled peers to be able to work with Git-enabled ones seemlessly. At least this is what seems like a good idea at this time :).

This implements a form of swarming download, similar in spirit to bittorrent, but not similar in the way it actually functions; you can simultaneously download chunks of files from different peers and several peers will have the chunks, but it's organized quite differently.

Also :) I'm thinking that it would be a good idea to give each directory (with all of its versions) a separate "view" in Git; i.e. new directories are branched from HEAD in Git (like when you make static web pages for Github: http://pages.github.com/). This will give each directory an independent set of branches, allowing people to store many different directories in a single Git repository without having to check out a ton of stuff just to get the directory you want, AND it also allows you to reuse the files from other directories because they're all in one Git repository.

Xus: Layers 1 and 2 work now

2009-10-04T01:59:00.000-07:00

I have layers 1 and 2 working now, with automated tests (it's on github). Layer 1 is simple packets and layer 2 is p2p messaging. That covers:

strong authentication (challenge/response on connect with RSA keys & signatures)
direct peer-to-peer messages
broadcast messages
unicast messages
dht messages (delegated to the peer with the peer id closest to the dht key)
delegated peer-to-peer messages (one peer sending to another peer through a topic)

Right now, as long as your peer doesn't spoof its public key, it can connect to any topic (authorization is part of layer 3). I think one other thing I should add to layer 1 is a heart beat, so you can quickly detect dropped connections (TCP timeouts are notoriously unreliable).

Layer 3 is the service layer and has these components:

Properties
Topic authorization and management (including peer "accounts")
File sharing
Port configuration testing
Connect-back requests (for when only one peer can accept connections)

A note about topic management: the idea is to use topic space 0 as a "root" topic space for a cluster of spaces, with topic 1 in space 0 handling administrative concerns for the cluster, like id vending for topic spaces and small id vending for peers (so messages don't have to contain a giant peer ids). Topic 0,1 would contain a set of properties about accounts and topics which would also allow banning users from clusters and members-only clusters (allowing private and pay services).

I was thinking back to the very start of my peer-to-peer experiments, so I searched my email archives to see when I started with this. It was April, 2001 when I first started talking p2p architectures over with my friend Fritz. A little while later, I made the p2pmud project on source forge; for project paleontologists, here's a link to the old p2pmud forums.

The project transitioned through several languages and architectures, eventually adopting FreePastry in Plexus so that we didn't have to write and maintain our own peer-to-peer networking layer. So now we have to do that and, ironically, the architecture's pretty close to the one I came up with in 2001, except that it's simpler. In 2001, I had envisioned a set of peers that routed requests to other, natted peers, but now we just have one peer doing the routing for a "topic space" with a bunch of topic spaces clustering to form the entire peer-to-peer grid.

andThen andThen andThen... Scala, where's my car?

2009-09-24T01:05:00.000-07:00

When I saw Dude Where's My Car?, several years ago with my wife (who is Chinese), she started laughing right as they pulled into the parking lot of a Chinese restaurant. I had no idea why, but she said to wait until the end of the scene. In the scene, after they order each item, a voice from the speaker says, "and then?" and continues after they run out of things to order until Ashton Kutcher eventually destroys the speaker in frustration. When the scene was over, I asked her why she started to laugh at the beginning of the scene. She said she had heard people quoting that at work, but she never realized that the Chinese name of the restaurant, which she saw at the beginning of the scene, was "And Then."

Appropriately, Scala defines infinite loops in actors using andThen. Here's how...

In Scala, one way to compose functions is "f andThen g", which is the same as

def newFunc[T](x: T) = g(f(x))

You can think of it as "evaluate f(x) and then evaluate g with that result". It's an easy way to chain functions and it's good for noncommutative operations, where "order matters," like matrix operations (the same type of idea you would use in implementing a safe navigation operator {quickly ducking for cover}). For instance, if you want make a function that takes a matrix, transposes it and inverts it and then returns the determinant, you could write that like this:

def transInv = transpose andThen invert andThen determinant

Those not familiar with functional programming will note the lack of arguments and return type in the definition of transInv. TransInv gets its arg types from transpose and its return type from determinant, so you can still use transInv(myMatrix). The definition of Function1[A, R].andThen is (here, Function1 takes an argument of type A and returns a result of type R):

def andThen[A](g: R => A): T1 => A = { x => g(apply(x)) }

Scala defines infinite loops in actors using andThen:

def loop(body: => Unit): Unit = body andThen loop(body)

So, if want to simulate the scene in Dude, Where's My Car?, using an actor, you can say:

loop {choose}

which translates to:

((_: Unit) => choose) andThen (_ => choose) andThen (_ => choose) andThen...

Xus: A Simple Peer-to-Peer Platform

2009-09-21T00:26:00.000-07:00

A friend of mine wanted to implement peer-to-peer source code repositories with social networking features, like popularity ratings and such and Plexus was already on the way to being able to support something like that, so I decided to break out the back end of Plexus into a separate project, called Xus. We started talking about what such a thing could do.

Then the bottom fell out of Plexus.

Apparently, the FreePastry project is winding down. It was, in my opinion, the most promising of the major peer-to-peer platforms. It was straightforward and relatively small. We chose it over JXTA for our communication in Plexus. We actually started with JXTA, back in 2002, but JXTA was just too over the top with the excessive design patterns, the large surface area, the lack of a usability layer, and things of this nature. Why does Sun seem to delight in requiring so much ritual from developers to do the simplest things with their libraries? So Pastry is way cleaner than JXTA. Like JXTA, Pastry was made to scale to 1000s of nodes in a cloud and had interesting routing schemes and other mechanisms to promote scalability and reliability. We liked it a lot. We did experience a few problems:

An improperly configured NATted peer could royally screw up the cloud, because all of the peers take part in routing and connect directly to each other
We had to roll our own presence using our own heartbeats, because Pastry doesn't inform you when a peer disconnects and you couldn't easily enumerate the peers on a broadcast channel (publishing topic)

This is all moot now, because FreePastry is not going to be actively developed.

So I'm announcing the Xus project. Here's the web page and here's the source, so far. There's a VERY simple, console-based chat to test it. I don't have unit tests yet. I've only been working on this for about a week and I'm not in the TDD habit. Maybe I should be. Anyway, because of the FreePastry news, Xus is a peer-to-peer platform and the other stuff will be services on top of it. Here's a snippet from the doc:

Xus is a peer-to-peer protocol with a reference implementation in Scala. The point of Xus is to provide a peer-to-peer platform that is simple, powerful, practical, and easy to use. People can use it for games, social networks, source code repositories, or whatever.

Simple: able to implemented with a relatively small amount of code so that it's easy to maintain and fix
Layered: there are 3 layers. Layering separates the concerns of the protocol and makes it easier to understand
Self contained: the reference implementation does not rely on third party libraries, reducing cognitive overhead for future developers
Scala: reference implementation is is Scala, which allows for smaller code that is "less noisy" than Java
Straightforward implementation: simple, direct routing
Powerful: strong enough to support common p2p tropes and some new ones
Messaging: multicast, unicast, dht, and delegated and direct p2p messaging
Delegated messaging allows peers behind NATs to receive messages from other peers
File storage, backed with Git
Replicated properties for simple shared data
Practical
Medium scale allows you to know when peers disconnect
Works through NATs
Easy to use
Built-in port testing — peers can request other peers to test their port configurations
API is small with a minimum of required setup
Reference implementation will include a UPnP port configuration tool (ported from the Plexus code base)

Xus is centered around "topic spaces," which are groups of topics. A topic space is a slice of the total peer-to-peer network, consisting of a medium amount of peers and each peer can connect to many topic spaces. Probably 100 or fewer peers in a topic space -- depends on the app. All of the peers in a topic space connect to the active owner, which does all of the message routing for the space. So, if a peer wants to broadcast a message to a topic, it sends a message to the active owner of the topic's space and the owner then sends a message to each peer in the space. Any peer can potentially be an active topic space owner if it can accept connections and it is, in fact, an owner of that topic space (Xus uses strong authentication for this kind of thing) . Peers which can't accept connections can still participate; they just can't be active topic space owners.

I use NIO in the reference implementation, so this routing isn't computationally intensive, but astute readers will notice that this broadcasting arrangement takes up a relatively lot of bandwidth for the active topic space owner, compared to everyone else. Hence the "medium amount of peers". By the way, Xus accomplishes broadcasting in a way that mirrors the most common architecture for first person shooter servers, so it CAN work extremely well (see Sauerbraten). There are issues and constraints, of course.

See, this is just the sort of thing that Pastry was trying to avoid by having all of the peers do routing, but it was also the thing that accounted for some of the major complexity in Pastry and all of the problems we had with it. Thus in Xus, broadcasting is limited to medium-sized groups of peers but this allows Xus to be more reliable and faster -- latency is usually much lower with this architecture. Xus is for when you want to build a peer-to-peer app quickly and defer scalability issues to when you realize that your project has, in fact, become wildly popular. At that point, there is nothing preventing you from making levels 1 and 2 of the Xus stack more scalable. You'll even be able to reuse the Xus protocol, probably adding messages and attributes that are required to support routing.

The protocol is XML-based and I'm using fastinfoset (which is built-in to Java) to take the fat off the wire. This allows you to use your favorite XML tools without worrying about how bloated the communication is. I'm using TCP for connections to simplify things. Maybe I'll look into SCTP, but for now, it's just TCP. The protocol is full duplex but does support request-response in cases where messages could fail, like direct p2p messages, for instance.

I'm not entirely sure whether to have broadcasts return a response with a list of the nodes that failed to accept the broadcast for whatever reason (security or lack of resources, perhaps). This sounds like it would be useful for some applications. Right now, Plexus is what's driving the requirements. If other developers see needs for things like this, they are welcome to jump on board the project and help out.

Can functional programming really offer something substantial to Java?

2009-09-06T11:37:00.000-07:00

This post on Scala-lang talks about research done on how the style of language affects productivity (the time it takes to understand other peoples' code). It is specifically comparing Java with Scala. Here is the paper that the post refers to.

Scala allows functional programming, as in Scheme, as opposed to procedural or object-oriented programming, as in Java, but Scala allows a nice blend of the two, which is a unique approach among programming languages. Yes, there was LOOPS and CLOS, but Scala's approach is quite different and I think it's much a more integrated one. There seem to be more and more posts out there about the importance of functional languages. Personally, I agree with the premise: that functional techniques lead to denser code and that can be (if used properly) easier to understand and maintain. Actually, this is related to one thing that I emphatically agree with the eXtreme Programming camp on: don't use accessors unless absolutely necessary (i.e. use refactoring to insert them when you have need of them).

There is a controversy here, though. Every now and then, over the years, I get extreme push-back on my coding style, because some programmers REALLY hate functional style. They act as if it's offensive -- as if people who use functional techniques are snobs and feel they're too good to use the straightforward, meat-and-potatoes approaches that the gumshoe programmer in the street uses. That's not it at all for me -- I use procedural techniques too. Just not all the time; not as a golden hammer.

It IS possible to use functional techniques in Java (using anonymous inner classes), but they are ugly and verbose. Nevertheless, I use them in places where I feel they're appropriate. Some people have complained bitterly about this in the past. That hasn't had an impact on my code, because of my position and the unique constraints and properties of it but in other circumstances I would be forced to write in what I consider a less effective way.

Maybe this attitude will change with the attention that functional languages are getting. I was a Smalltalk programmer in the 80s and 90s, and I remember the Java hype. A lot of Smalltalkers were saying that it would pass because it was just hype. After all, they said, look how inferior Java is with its primitive types, substandard collection library, and skeletal GUI support, compared to Smalltalk's! And anyway, it was just the new new thing. I figured Java was going to eat Smalltalk's lunch. I made noises so that people at our company got trained in Java and I made a technology that connected Smalltalk to Java so that Smalltalk could essentially use Java as a display medium, which I thought might slow Java's impact on Java (as of last year, there was still at least one Smalltalk project using that technology).

Are functional languages just being hyped now as the latest attempt at a silver bullet or do they REALLY have something to offer? I've always thought they were interesting and powerful and fun to program with. As I mentioned before, the functional paradigm has been around a long, LONG time: Church introduced Lambda Calculus in 1932 and Turing introduced his machine in 1936. They were both VERY different approaches to computing and the Turing Machine approach is currently "in vogue."

That may change. What if functional languages are shown to scale better in several dimensions, such as code comprehension and multithreaded programming? I guess we'll see, but it's starting to smell that way to me. I did a lot of programming in both LISP and Smalltalk, back in the day. When I switched to Java, the lack of lambda in JDK 1.0.X was a real pain. When they introduced inner classes in 1.1, things got better, but so far they really don't have the brevity of Smalltalk's blocks.

Groovy and Scala have nice lambdas and Scala really focuses on functional tools. My money's on a change that integrates functional tools into the JVM. Maybe that'll come quickly as more and more deep pocketed groups adopt Scala. That's how Smalltalk got mainstreamed in the 90s. Even if Scala doesn't get super broad adoption, if high tech, high finance, and infrastructure orgs continue to adopt Scala, there will be a nice little Scala niche for a lot of people I know.

Livecoding: connecting the dots from Lambda Calculus to Gibson's cowboys

2009-09-01T01:39:00.000-07:00

Dot #1: Lambda Calculus...

My wife and I took a vacation recently and I had a chance to learn some more Lambda Calculus; how the Y-combinator works, in particular. At Purdue, we focused on Turing Machines and either we didn't really cover LC or I slept during that part. If you haven't, I HIGHLY recommend learning LC. Lambda Calculus is the most elegant system I, personally, know of (maybe that's not saying much). You functional-types out there will already know this next part, but here's some history and stuff.

It was invented by Alonzo Church, who was Turing's Ph. D. adviser (later they proved that the Lambda Calculus and Universal Turning Machines are equivalent, which was one really impressive feat). The Y-combinator is a way to define recursive functions using only lambda binding. Lambda binding is very simple and it's pretty much what Lambda Calculus is. It more or less just lets you assign values to variables and then use them in an expression, like this (in LISP):

( (lambda (x) (print x)) 50)

(lambda (x) (print x)) is a function definition that says to print whatever x is bound to. Using it like in the above "applies" the function to the argument by first "binding" x to the value 50 and then "evaluating" the expression (print x). Pretty simple concept. The trick is how to define recursive functions using this mechanism, since both the set of variables to be bound and the expression to evaluate are separate. In order to be able to call a function, you either need to pass it in as an argument or have it defined by an "outer" function.

A recursive function can't take itself as its own argument and it's also not defined in an outer scope, so it essentially has to be given a copy of itself as an argument. The Y-combinator is a relatively clean way to do this. I wasn't able to understand it while we were out on our vacation, because I (deliberately) left my computer at home. Once home though, I was able to type things into LISP and play with them to finally be able to grok the combinator (hmm, "grok the combinator" sounds like some sort of euphemism).

Dot #2: Scala...

So, that launched me on a journey to rediscover functional programming, since I hadn't messed with it really since the late 80s, when Roy Riggs and I (TEAM CTHULHU) were working on our MUD. My friend, Serj, reminded me of this functional language for the JVM called Scala and told me that James Strachan wrote in a blog post that if someone had shown him the new Scala book back in 2003, he never would have written Groovy. Groovy has been my favorite scripting language for quite a few years, because it integrates with Java so well (low barrier to adoption for Java coworkers). So, I started messing with Scala. I even made this blog so I could post some musings and info about my Ober project, which I updated from JavaScript to Scala. I recoded a bunch of Groovy stuff for Dataswarm in Scala and that's worked out really well.

Dot #3: Scheme...

I met this guy on a plane to Israel a few months ago. He's in his 50s and he got his masters in education, applying virtual worlds to education. he's not a programmer (yet), but he's been wanting to essentially "do cyberspace" for education since 1996. He got a 17 year old Israeli programmer to work with him and make a bunch of interesting mockups. They tried to commercialize it and whatnot, but never really got anywhere. When I told him about Plexus (which is currently stalled, by the way), he was sort of shocked into action and really got inspired to work on his project again. I asked him that since Plexus was open source anyway, why not build on top of it instead of from scratch?

Eventually, I realized that he really needed a better way to get a feel of what's currently possible, etc. and that would require him to know something of how to program. I looked for a good intro to pure programming, with little between him and the algorithm and that led me to PLT Scheme (http://plt-scheme.org/). There's a GREAT book on programming that basically plows through a few semesters of CS very quickly (How to Design Programs here: http://docs.plt-scheme.org/). The quick intro also does graphics on the command-line, which is pretty slick, letting you define shapes that print out like smileys. This reminded me of "the good old days" in our LISP MUD when we could type in code and change the game as it was running.

Dot #4: testing and log analysis...

I've been doing a lot of log analysis with our technology at work. We're working on making it "bullet proof" now, with the goal of being able to remove the battery from a laptop in a demo, sticking it back in, and starting back up without data loss (after the file system recovers). This requires some heavy journaling and online backup. Test runs can be long and produce giant diagnostic logs (0.5 - 2G). I have to comb through these logs and find errors. Then I have to trim them and transfer them from Kansas to my machine in Israel so I can inspect them more closely. This takes a lot of ad-hoc scripting and the needs change after I fix each bug. This reminds me of what we did with our MUD, because I'm "writing code as I go". One of my hopes with the Ober project is that I can have a nice tool to do this with.

Dot #5: Gibson's cowboys...

I started rereading Neuromancer and it's even MORE impressive than it was the first time I read it. Early in the book, Armitage tells case that he was there when they "invented" Case -- i.e. when they created the software cowboys use for net running. This reminded me of typing code "in-game" with our MUD and I remembered how cool it was to adapt the game as people were playing it. So I was thinking that there ought to be some powerful stuff programmers could do that we might not really be doing yet.

I had told Serj about PLT Scheme. He's early in college and I'm trying to mentor him to be a guru -- I think he has the potential. He started messing with Scheme and reading the book and sent me a link to "fluxus" http://www.pawfal.org/fluxus/ This is a "livecoding" system. People are using this to actually code music and graphics in front of an audience: http://toplap.org/uk/about/ The first vid is fairly poor and what you might fear such a performance would be like (sorry guys who made the vid), but the rest are very interesting, I think. Again, kind of the type of thing that we used to do with our MUD.

Dot #6: livecoding in Scala...

So people are working on creating systems specifically to accomodate changing programs as they run. You could say "that's what a shell is" and you'd be right, to an extent. Shell tools are powerful ways to slice and dice text, but for things like the log analysis I'm doing, I think I need something more like an IDE. Something that gives programmers an environment they can use to modify code and test it in a tight loop, with access to the code, the data, and intermediate results as the program is running, like in the Haskell Hackery performance here http://toplap.org/uk/about/ it's well worth watching. That's more like EMACS or WILY than a shell, I think.

I'm hoping Ober can do something like this for Scala, backed with something like Eclipse, to get syntax highlighting, and whatnot. One idea might be to make Ober an Eclipse plugin instead (or in addition to) a stand-alone environment. It might be interesting to "skin" Eclipse and remove the right-button menus, replacing the behavior with Oberon menus (or 'tags' in Wily -- a single Oberon menu bar above all of the editors might be sufficient, with some commands to open subpanels or something). Perhaps running in the debugger will help or ClassGhost (http://classghost.sourceforge.net/).

One sticky issue is that Java can't redefine arbitrary methods in a running VM -- you can't redefine a method using a different signature as you could in Smalltalk and you can't add or remove fields. A quick check of the new features of JDK7 doesn't show any evidence of change to these limitations. Coding conventions would help with this (kind of like writing "structured COBOL"). As opposed to hotswapping methods, you can just "reload" a class, which defines a NEW class with the SAME name. Production servlet hotswappers are familiar with the perils of this.

Ober's command/namespace registry makes it a system like a shell or Oberon. Indirecting through the registry instead of using hard pointers allows you to reload a class file without worrying about signatures, provided the fundamental command interface didn't change (i.e. the command itself should be the only thing keeping references to its objects). A central storage area where commands could place simple data would allow commands to keep state that was protected from redefinition and they could be initialized with this state.

So here's a simple way to get what I think would be decent support for livecoding with Scala:

run Ober out of the debugger so you can use hotswapping when possible, using Ober to access intermediate results and as a scratchpad for data munging and Eclipse to change code
make the class loading namespace check for hints in the class, like annotations for namespaces and such
provide per-command data storage from the Ober object (a trait can make this even easier to access)
make a Reload command as a fallback for when hotswapping doesn't work
make a log that appends useful Ober commands, such as prefilled Reload commands and access to previous command results and provide easy access to this from the Ober object and a command to show the log
keep commands clean -- don't hold references to other commands' objects; go through the command registery to get them
simplify access to the command registry to make it simple for commands to use it to access each other

Whimsical Jerusalem Pedestrian Crossing Signs

2009-08-28T01:18:00.000-07:00

I noticed these in walking around in Jerusalem and I haven't seen a lot about them on the web yet, so I thought I'd post them. The last one's a fake, obviously put up by a concerned citizen who thought that werewolves weren't getting the representation they deserved. There are several more that I haven't photographed, including at least 2 more fakes: a man dragging a baby, and an angel as well as at least two authentic ones, a man with one hand in a fist and the other with fingers spread and a fat man. I'll post those eventually.

Streamlining Ober

2009-08-20T08:59:00.000-07:00

I made some changes to Ober that make it quicker to use. Now, when you right-click a word, Ober does everything in path-like fashion:

if the word is an Ober built-in, execute it
if the word is a class name, run the main with the args to end of line
if the word is a shell command, run it
if the word is a file, directory, or URL, open it

If you middle click, that sets a hint to tell the command that if it is appropriate, open a new viewer instead of replacing the current one.

Also, I made a runnable jar for it all, so you don't have to build it.

Here's the new doc page

The power of text

2009-07-27T00:44:00.000-07:00

After spending 4 or 5 years working on servers with decent amounts of data going through them, I've had to do a fair bit of forensic work with saved databases, giant log files, etc. AWK, sed, Groovy, EMACS, and their kin have been my friends. You can use them to distill unstructured text into a structured form for summaries, trending, etc.

I am starting to turn Ober into a console for this type of forensic work. I can see how farsighted Niklaus Wirth was when he made Oberon. This doesn't look to me like a temporary phase in computing. If anything, unstructured text is even more prevalent today than it has been in the past. Google has shown people what you can do with it. We'll see where Ober goes from here.

For the future, I'm planning on adding some more Wily-like features to Ober, like preceding commands with |, <, and >. Here's an update on Ober...

Ober is becoming usable now. Here are the items I checked off of the list from the last post:

execute HOME/.oberrc on startup (if it exists)
Scala expressions embedded in {...}
ctrl-click opens a file. Actually, it tells the namespaces to "surf", so surfing depends on the namespaces your viewer is using
fixed redraw bug

I also added some cosmetic commands, like TrackPos, Width, ViewerPos, and Height.

Using the context-sensitive surfing, I made a "data browser" to examine some object databases I use. It was pretty simple, since I could already dump objects and display the guids of the objects they reference, so when you ctrl-click on a guid, it goes to the viewer for that object (or creates it) where it displays the dump of that object. If you type things or mess up the text and you want to redisplay, you just ctrl-click on the viewer name and it refreshes.

Here is the Ober's current source code and here is Ober's current help page.

A tribute to Niklaus Wirth

2009-07-22T05:30:00.000-07:00

If you haven't heard of Niklaus Wirth's Oberon or you haven't seen it, you should check it out. Messing with it reminded me of when I first learned Smalltalk in 1988. There's an air of playfulness and potential to it, just like in Smalltalk-80. The current version of Smalltalk is called Squeak and it's well worth checking out as well.

Oberon is sort of a Pascal take on Smalltalk. Like Smalltalk, it's both a language and an environment. Like Smalltalk, it has built-in programming tools (compiler, editor, etc), and it's interactive; you're programming "in" the language, so the edit-compile-run cycle is VERY tight (like when you're using the scala command and you can evaluate expressions). Oberon's environment was similar to Smalltalk's, but had some major differences and innovations, the most valuable one being (in my opinion) that you can click on a word anywhere in the environment and it will attempt to execute it as a command. There are other innovations too, but that's my favorite.

Harnessing this capability, Rob Pike at AT&T based a text editor/shell on Oberon as part of Plan 9, called Acme. Then, Gary Capell made Wily for Unix. Then, in 2002, I made one based on Wily for Ruby, called Meep. And THEN, I rewrote it in Java and renamed it "Ober," to point back to Oberon (and because ober means "waiter" in German). Somewhere along the line, I don't remember whether it was in Meep or just Ober, I added a "namespace" twist, to allow scoped commands, like Oberon has, but identified in the "tag" of the viewer (the text field at the top of the viewer which contains handy commands).

So. Time for another rewrite. Here's Ober-scala now.

It's two eclipse projects, one Java, and one Scala 2.8 (I'm having trouble with Java and Scala in the same project). To run it, just use the "Scala Ober" launcher that's in the scala project. There's a LOT of room for improvement, of course, but it functions, at least. On Linux. I haven't tested it on Windows. Sorry Windows :(. It's not that I think Windows sucks, it's just that I don't use it and it's pretty inconvenient for me to mess with it on my current setup.

Why did I do this? I wanted a "programmer's workbench" that was a combination program runner, simple editor, and shell. You know, like EMACS, but by Scala and for Scala. And the Oberon environment is very cool. When I read that Martin Odersky studied under Niklaus Wirth, I figured, hey, maybe some Scala people would be interested in this thing too. We'll see.

What can it do? If you righth-click a word, it will try to execute it as a command. At this point, there are 3 types of namespaces:

closure namespaces, which look up named closures
class namespaces, which look up classes
system namespaces, which look up shell commands

So, you can test it by right-clicking on some of the words that are already there when you start it (like New, Newcol, Del, Quit, ...). You can type in the name of a class in your class path and right-click on that (like tc.ober.Test, for instance); it will split the rest of the line by spaces and send the strings to the main method of the class. You can type in a shell command and right-click that; it will execute the word plus the rest of the line as a system command (using Runtime's exec(String) method).

What's left?

execute .oberrc on startup
Scala commands embedded in {...}
file handling (crtl-click on a word and it opens as a file). See Wily for this behavior.
meta commands for your .oberrc (commands to define commands, etc.)
classpath manipulation
fix bugs (like when you delete the last viewer in a track, it doesn't redraw)

Happy hacking!

Safe navigaion in Scala, the aftermath

2009-07-17T16:01:00.001-07:00

Wow, I sure stirred up a hornet's nest with my safe navigation experiment. Some people posted some very useful information and good alternative approaches!

As for comments about "ugliness", being able to read this in 6 months, etc.; I'm not making a policy decision here, just experimenting. The fact that people are so put off by experimentation makes me wonder... Anyway, we'll see if it comes in handy or not. Things like this can easily be "compiled" by the mind as "programming idioms".

But as for unreadable, it's only a cascade of lambdas, after all. Personally, I've been very comfortable with functional style, since I first learned LISP, freshman year in college. It's amazing to me how emotional some programmers get when they see code using functional style. Does this mean "imperative -> good, functional -> bad?"

I guess there's always been a divide between functional and imperative approaches. I'm glad Church and Turing could see that their different approaches were accomplishing the same thing. I really think more universities should teach functional languages in their freshman level courses, before people have a chance to ingrain imperative as the one true way. My university (Purdue) did not; I just happened to learn it from a friend, because I was interested in what LISP was and how to use it. At the time, I was amazed (and a bit envious) to find out that some universities taught LISP or Scheme to freshmen.

I think LISP and Scheme are excellent first languages, because they abstract computation away from the machine; they don't encourage you to simulate a computer in your head when you write code. Simulating a stack machine can be a great barrier to actually understanding recursion and higher order functions. Freshman and sophomore year, I helped quite a few students learn recursion, but I had to "unteach" the technique of "stack simulation" first, so they actually had a chance of understanding something like A-B recursion or composite recursion.

It's interesting, because I just started teaching a guy to program last week, and I chose to start with Scheme (although eventually he probably needs to learn Java). I found good site with some basic tutorials and a free book on programming that actually teaches recursion the way I taught it freshman year, way back in 1984. It looks like I'm not the only one with those ideas about how to teach recursion.

For those interested, here's the PLaneT Scheme Site and here's the book (linked from their site as well).

Safe navigaion in Scala, take 2

2009-07-16T15:30:00.000-07:00

OK, revisiting this topic after a very short time, I have a new implementation, again using that interesting anonymous class technique from James Iry's comment:

implicit def richOption[T](x : T) = new {
 def ??[B](f : T => B):B = if (x != null) f(x) else null.asInstanceOf[B]
}

I changed the operator from "?!" to "??" because that's a lot easier to type and I chose "??" instead of "?" so people wouldn't confuse it with the questi-colon operator from Java and C. It's stand-alone (doesn't depend on Option or anything) and I had to use a cast to get the types to work out properly, but the test case from my last post does work

println(p3??(_.bud)??(_.bud)??(_.bud)??(_.name.drop(1)))

prints null and

println(p3??(_.bud)??(_.bud)??(_.name.drop(1)))

prints ubba.

For those new to Scala, the expressions in parentheses are anonymous functions because they use "_" as identifiers. (_.bud) expands to (x => x.bud), where Scala chooses an x that is unique in the scope of the expression. Of course, you can put whatever you want in the final block there, or the other blocks. You could say this instead

p3??(_.bud)??(_.bud)??(x => println(x.name.drop(1)))

You might want to do this if you only want to print provided that the full path exists for instance, which demonstrates that this construct is more powerful than Groovy's, because each step can be more than just another increment along the path.

This has an advantage over the previous solutions of not requiring the ! operator at the end to extract the value out of the option because the ?? operator returns a raw value instead of an Option. Not having used Scala for more than a week (I haven't even used LISP since the late 80s), I can't speak as an authority on when it's appropriate to use Options, but this seems to me like an alternative to Option for at least some cases.

Safe navigation operators for Scala

2009-07-16T06:11:00.000-07:00

Welcome to my first blog post.

I searched the net for a Scala analog to Groovy's safe navigation, but I didn't find anything, so I made my own. It's like a monad but I haven't thought much about the implications of really making it into a real monad so I haven't monadized it at this point.

Here is some example data to demonstrate how you use these safe navigation operators in Scala:

case class Person(var name: String, var bud: Person = null)

val p1 = new Person("bubba")
val p2 = new Person("fred", p1)
val p3 = new Person("mary", p2)

println(opt(p3)?!(_.bud)?!(_.bud)!(_.name.drop(1)))

This code prints "ubba". It uses ?! like Groovy's ?. operator (?. isn't a legal operator in Scala because of the .), but you need the extra parentheses or it doesn't parse like you would want (I think Scala needs the parentheses to disambiguate the scope for the _). The final ! operator returns the closure value instead of wrapping it with an OptionalRef.

If you go one more step, you'll get () as the return value:

println(opt(p3)?!(_.bud)?!(_.bud)?!(_.bud)!(_.name.drop(1)))

That code prints "()". If you don't like the first opt(Any) and you want to do implicit conversions, you can import OptionalRef.Implicit._

So, it's noisier than Groovy, but a lot less noisy than nested "if" expressions.

Here's the code, modified from James Iry's comment:

def notNull[T](x : T) = if (x == null) None else Some(x)
implicit def richOption[T](x : Option[T]) = new {
  def ?![B](f : T => B) = notNull(f(x get))
  def ![B](f : T => B) = if (x isDefined) f(x get)
}

I like that much better than my old, slightly longer, code :)

object OptionalRef {
 object Implicit {
  implicit def obj2OptionalRef[T <: Object](input: T): OptionalRef[T] = {
    if (input == null) NoRef else Ref(input)
  }
 }
 def opt[T](obj: T) = Ref[T](obj)
 abstract class OptionalRef[+T] {
  def isEmpty: Boolean
  def ?![U](st: (T) => U): OptionalRef[U] = {
   (if (isEmpty) NoRef else st(get)) match {
    case r: OptionalRef[U] => r
    case null => NoRef
    case o: U => Ref(o)
   }
  }
  def !(block: (T) => Any): Any = if (!isEmpty) block(get)
  def get: T
 }
 class Ref[+T](x: T) extends OptionalRef[T] {
  def isEmpty = false
  def get = x
  override def toString = "Ref(" + get + ")"
 }
 object Ref {
  def apply[T](obj: T) = new Ref(obj)
 }
 object NoRef extends OptionalRef[Nothing] {
  def isEmpty = true
  def get = throw new NoSuchElementException("NoRef.value")
  override def toString = "NoRef"
 }
}