This is in response to a post I read on hacker news: http://news.ycombinator.com/item?id=870434.

I’ll describe what I came up with to have serial code automatically be “parallelized”, how much I’ve implemented, and some concerns about performance.

I worked briefly on a side project for a language that I call Paralang. There are a couple philosophies for this language:

0. code == data like Lisp.
1. everything is an ordered dict, but with revision control
   (or, it's a symbol).
2. functions are also ordered dicts where each key/value pair
   is an assignment to a symbol.
3. symbols are used to refer to objects much like the javascript
   prototype system. (closures)
4. the above properties make it possible to execute sequential
   programs out of order (not to be confused with reordering
   the procedure itself) or in parallel, making it interesting
   for parallel computing studies.

Everything, even the code, is just an ordered dict (or an associative array). Nothing ever gets deleted from the objects, although you can assign values to the same key multiple times. Keys are not unique. All entries preserve order.

  {
   foo = [1 2 3]   // key is foo, value is [1 2 3]
   bar = [x:foo y:foo z:foo] // you can use = and : interchangeably
   baz = bar.x // dot notation fetches the last value with the given key
   return: baz // or you could say return = baz.
  }

During interpretation, the interpreter reads the objects in sequential order and inserts them into the “context” object. The context is of course just another ordered dict object.

Since the code is supposed to be written in serial procedural order, the numeric index of each item in the code object tells the interpreter what “order” of execution for each key/value interpretation task.

  {
   foo = [1 2 3]   // order 1
   bar = [x:foo y:foo z:foo] // order 2
   baz = bar.x // order 3, and the "bar.x" gets unfolded into a function call,
                  which have order "3.0, 3.1 etc"
   return: baz // order 4
  }

Function calls just “happen”, when during interpretation, a “call” key is invoked.

  foo = sum_three(1 2 3)   // parser turns this into...
  foo = [1 2 3 call:sum_three]

During interpretation of sum_three(1 2 3), the interpreter first creates a new object with (None: 1, None: 2, None: 3), then proceeds to interpret the function referenced by “sum_three” into the new (1 2 3) object.

Assignments to “return” is special in that the value being assigned to return gets returned as the final interpreted value of the list that contained the “call” key. So in the above example, “foo” would get assigned the value 6.

Contexts support “self” which refers to the current context being built. “this” refers to the code object.

Function declarations are usually wrapped in ‘{}’ parenthesis, which makes the interpreter copy the object instead of interpreting it.

  [
      foo = {(a b c=4) // special logic handles default params
          a = b+c
          return: a
      }
      return: foo(a:1 b:2 c:3)
  ] // returns 6.

Anyways, all of these objects are version controlled. What I mean is, each context has a “guid” that is composed of the “order” of all the contexts in the call stack, from the interpreter order of “__machine__” to the current context being built. e.g.  “__machine__.0.12.0_key”. These guids represent the global order of execution for the entire program.

The interpreter can execute arbitrary lines of code (out of sequence, or the body of a while loop) as long as the correct guid is assigned to the interpretation. That way, once an object detects a conflict of read/writes where the writing context comes before a prior write from another context, the object can signal the latter context to kill itself and undo its operations.

You can take a look at the current state of Paralang quickly here: http://github.com/jaekwon/Paralang/blob/master/test2.py. I don’t even have conditionals implemented yet, but most of the revision control logic is there. I have some thoughts on how best to implement ifs/switches/try-catches/loops, but I hope to hear from others too.

I realize, that the interpreter might have to do quite a bit of work to roll back speculative interpretation tasks that weren’t going to execute if the code were run in plain serial fashion. I haven’t had the time to think much more about it.