Even More Concurrency; Or, What You Can't Find By Searching Google Scholar

(Continuing the series of Schrodinger's Equation of Software, First Class Everything: Loops, Tail-Calls, and Continuations, and Automatic Concurrency)

      Our last version of cps_map_eval gave us concurrent evaluation of arguments, and without even needing any locks or other kinds of synchronization. That's pretty impressive... except that it only works as long as a) every argument returns at least once and b) no argument returns more than once before all have returned at least once.
      Those may not seem like very strict restrictions, except that the whole point of continuations is to break them. Consider this program:

((vau () % (+ (return 2) 2)))

      With the last version of cps_map_eval, it will cause an error, because when the first argument thread has terminated, it will not have filled in its slot- it jumped to a different continuation. The parent thread will try to evaluate (+ None 2) and throw an exception, when what we really wanted was for it to not run at all! A similar problem can be seen in this program:

(+  ((vau () % (par (return 1) (return 2))))
    (do-long-computation))

      In this case, no arguments fail to return. But the first argument activates its continuation twice, and from different threads. If both of those continuation calls execute before (do-long-computation) completes, the first one will fill in the argument slot and disappear as intended, but the second will go ahead and execute the function body with an incomplete argument list, because we have assumed erroneously that a continuation can only be called a second time after the function body has begun executing. This is false as soon as argument expressions can themselves contain multiple threads, and even more false if you allow mutation so that external threads might get hold of the continuation.
      I searched far and wide for existing research on combining continuations and concurrency. But it seems that on this particular topic, nothing exists. Fortress does not have continuations, and no experimental LISP dialect has automatic concurrency! There is a lot of interesting work on what continuations mean in concurrent systems, and different ways to deal with them when you have explicit language constructs for parallelism like spawn or pcall, but none of it is easily applicable to a situation where all of the parallelism is implicit. There are some very interesting ideas out there, like this work on subcontinuations and this on inter-thread communication with ports, which I may come back to in later posts, but for now it looks like I, too, can be on the cutting edge of functional programming research.
      What we want is not for all argument threads to terminate before executing the function body, but for all argument slots to be filled, whether it's by the same threads that were started for that purpose or not. In order to do that, we'll have to introduce a counter for the number of argument positions that's decremented whenever an argument slot is filled; when the counter reaches zero, then we can run the function body. A version of cps_map_eval that does that looks like this:

def cps_map_eval(k,v,*x):
    """
    Evaluates the elements of an argument list,
    creating continuations that will assign values
    to the correct indices in the evaluated list.
    """
    arglen = len(x)
    if arglen == 0: return k([])

    counter = [arglen]
    finished = Event()
    flock = Lock()
    argv = [None]*arglen

    def assign_val(i,val):
        argv[i] = val
        flock.acquire()
        counter[0] -= 1
        flock.release()
        if counter[0] == 0:
            finished.set()

    def reassign(i,val):
        finished.wait()
        new_argv = argv[:]
        new_argv[i] = val
        return k(new_argv)

    def arg_thread(i,ax):
        eval(ax,v,ArgK( lambda val: assign_val(i,val),
                        lambda val: reassign(i,val)))

    threads = [Thread(target=arg_thread,args=(i,ax))
                for i, ax in enumerate(x[:-1])]

    for t in threads: t.start()

    def arg_k(val):
        argv[-1] = val
        flock.acquire()
        counter[0] -= 1
        flock.release()
        if counter[0] == 0:
            finished.set()
        else:
            finished.wait()
        for t in threads: t.join()
        return k(argv)

    return Tail(x[-1],v,
                ArgK(arg_k,lambda val: reassign(-1,val)))

      Again, we're using a 1-element array because Python won't let us mutate variables in closure scopes, but will let us alter the contents of collections. Initial continuations fill in values and decrement the counter; non-initial continuations and the parent thread that will execute the function body wait until all of the slots are filled (every initial continuation has been called). When all of the slots are filled, any waiting threads are unblocked and the function body can be executed for as many times as continuations containing it have been activated. This almost works. Except for one rather important problem. This program will never terminate:

((vau () % (+ (return 1) 1)))

      The argument thread will send 1 to the outer continuation, never giving anything to (+ [] 1), and the parent thread will hang forever waiting for that slot to be filled. So, we can't allow the parent thread to block. To fix this, we don't privilege the parent thread. It becomes just another argument evaluator, whose sole speciality is the ability to call join() to cleanup all the other threads eventually. Instead, every initial continuation checks to see whether it filled in the last argument slot, and if so, it evaluates the function body. This means that the thread that began a computation may not be the same thread that completes it- the continuation can get picked up by a different thread, and the parent may end up swapped out for one of its children. This version of cps_map_eval takes care of that:

def cps_map_eval(k,v,*x):
    """
    Evaluates the elements of an argument list,
    creating continuations that will assign values
    to the correct indices in the evaluated list.
    """
    arglen = len(x)
    if arglen == 0: return k([])

    counter = [arglen]
    finished = Event()
    flock = Lock()
    argv = [None]*arglen

    def assign_val(i,val):
        argv[i] = val
        flock.acquire()
        counter[0] -= 1
        flock.release()
        if counter[0] == 0:
            finished.set()
            return k(argv)

    def reassign(i,val):
        finished.wait()
        new_argv = argv[:]
        new_argv[i] = val
        return k(new_argv)

    def arg_thread(i,ax):
        eval(ax,v,ArgK( lambda val: assign_val(i,val),
                        lambda val: reassign(i,val)))

    threads = [Thread(target=arg_thread,args=(i,ax))
                 for i, ax in enumerate(x[:-1])]

    for t in threads: t.start()

    def arg_k(val):
        r = assign_val(-1,val)
        for t in threads: t.join()
        return r

    return Tail(x[-1],v,
            ArgK(arg_k, lambda val: reassign(-1,val)))

      We're getting closer. All of the previous examples will now behave properly. But this one won't:

((vau () % (+ (return 1)
              ((vau () % (par (return 1)
                              (return 2)))))))

      The first argument slot is never filled. The first thread to return to the second argument slot fills in its value and terminates. And the second thread to return to the second argument slot then waits for the first one to be filled. And it will wait forever, that one blocked thread preventing the program from terminating.
      We could consider having some kind of thread garbage collector that periodically checks to see if all existing threads are blocked and if so terminates the program, or cleans up threads that can never be unblocked because the necessary continuations aren't held by anyone anymore. But what we really want is to simply not block in the first place. The choice of the name Event for the notification objects we've been using from Python's threading library so far is apt: we'd like something like an event loop that can store up computations and then execute them when an event (filling all the argument slots) occurs, or not if that event never occurs.
      We can achieve the same effect without actually building an event loop, though. Everything can still live nicely inside of cps_map_eval, and it looks like this:

def cps_map_eval(k,v,*x):
    """
    Evaluates the elements of an argument list,
    creating continuations that will assign values
    to the correct indices in the evaluated list.
    """
    arglen = len(x)
    if arglen == 0: return k([])

    counter = [arglen]
    flock = Lock()
    argv = [None]*arglen
    blocked = set()

    def assign_val(i,val):
        argv[i] = val
        flock.acquire()
        counter[0] -= 1
        if counter[0] == 0:
            flock.release()
            for t in blocked: t.start()
            r = k(argv)
            for t in blocked: t.join()
            blocked.clear()
            return r
        flock.release()

    def reassign(i,val):
        new_argv = argv[:]
        new_argv[i] = val
        return k(new_argv)

    def reactivate(i,val):
        flock.acquire()
        if counter[0] == 0:
            flock.release()
            return reassign(i,val)
        blocked.add(Thread(target=reassign,args=(i,val)))
        flock.release()

    def arg_thread(i,ax):
        eval(ax,v,ArgK( lambda val: assign_val(i,val),
                        lambda val: reactivate(i,val)))

    threads = [Thread(target=arg_thread,args=(i,ax))
                 for i, ax in enumerate(x[:-1])]

    for t in threads: t.start()

    def arg_k(val):
        r = assign_val(-1,val)
        for t in threads: t.join()
        return r

    return Tail(x[-1],v,
            ArgK(arg_k, lambda val: reactivate(-1,val)))

      If a continuation call cannot immediately continue, it's dumped into a blocked set and the thread terminates. If the argument slots are ever all filled, that set is checked, and everything in it is re-activated. If they aren't, the set just gets garbage collected when the necessary continuations are no longer held by anybody else. Note that thread join()s only occur after a parent thread has finished all possible useful work, and cannot do anything but return a final value to the top-level eval loop; thus, they do not inhibit concurrency. We could even get along without them, and let Python deal with the cleanup, but if we were using raw POSIX pthreads that wouldn't be an option, so we might as well cleanup our garbage. We did end up having to use 1 lock, to ensure atomic access to the counter, but that's pretty darn small; most of the time, it will never be contended. Note that we need to keep the lock around additions to the blocked set, just in case, but we don't need the lock when iterating over it; that's because we only get to that point if the counter has just been set to zero, and if the counter is zero, we know that no other thread will ever access the blocked set again.
      So there it is. Automatic concurrency that plays nice with continuations, without any need to modify the core vau evaluator.

As usual, working code can be found at https://github.com/gliese1337/schrodinger-lisp/.

Automatic Concurrency

(Continuing the series of Schrodinger's Equation of Software and First Class Everything: Loops, Tail-Calls, and Continuations)

      So far, we've had a language with de-jure concurrent evaluation of lambda arguments, but de-facto left-to-right evaluation order. A modification to cps_map_eval can make our language genuinely concurrent.
      First, we'll drastically simplify the continuations of each argument evaluation, so they don't explicitly chain together anymore. Instead, we'll just evaluate them all in a loop. If the loop already finished, and all of the arguments have been previously evaluated, the continuation is the same as before: reassign the current argument and re-call the continuation of the whole argument list; otherwise, the continuation is implicitly the next iteration of the loop.

def cps_map_eval(k,v,*x):
    """
    Evaluates the elements of an argument list,
    creating continuations that will assign values
    to the correct indices in the evaluated list.
    """
    arglen = len(x)
    if arglen == 0: return k([])

    argv = [None]*arglen
    done = False
    
    def arg_thread(i,ax):
        def assign_val(val):
            if done:
                new_argv = argv[:]
                new_argv[i] = val
                return k(new_argv)
            else:
                argv[i] = val
        eval(ax,v,assign_val)

    for i, ax in enumerate(x):
        arg_thread(i,ax)
    
    done = True
    return k(argv)

      This is much simpler than our previous code, so why didn't we use it? Well, evaluating arguments in an explicit loop means that each call to eval is no longer a tail call. That's not a huge deal, because it will only grow the stack with recursive calls to eval for as many times as you type in nested function calls in argument positions in your source code; but we don't need to grow the stack at all, and doing so gains us nothing by itself since this still results in implicit left-to-right sequential evaluation. However, notice that the extra function used to create a closure for the value of the index for each argument evaluation is named arg_thread- with the code in this form, we can arrange to execute each argument evaluation in its own concurrent thread.

def cps_map_eval(k,v,*x):
    """
    Evaluates the elements of an argument list,
    creating continuations that will assign values
    to the correct indices in the evaluated list.
    """
    arglen = len(x)
    if arglen == 0: return k([])

    argv = [None]*arglen
    done = False
    
    def arg_thread(i,ax):
        def assign_val(val):
            if done:
                new_argv = argv[:]
                new_argv[i] = val
                return k(new_argv)
            else:
                argv[i] = val
        eval(ax,v,assign_val)

    threads = [Thread(target=arg_thread,args=(i,ax))
                for i, ax in enumerate(x)]

    for t in threads: t.start()
    for t in threads: t.join()
    
    done = True
    return k(argv)

      This isn't quite true parallelism because of Python's Global Interpreter Lock. But it is true concurrency, and with a better underlying implementation of threads would result in automatic paralellism. The existing thread starts up one new thread for each argument to be evaluated, waits for all of them to terminate, and then returns to the main eval loop. Each new thread makes one call to eval to start up its own evaluation loop. However, this implementation creates one more thread than necessary: the main thread sits idle while all of the arguments are evaluating. This is especially heinous if you only have 1 argument; why start a new thread just to do one sequential evaluation? That can be fixed by changing just a couple of lines so that the last argument in the list is evaluated in the current thread:

    threads = [Thread(target=arg_thread,args=(i,ax))
                for i, ax in enumerate(x[:-1])]

    for t in threads: t.start()
    arg_thread(arglen-1,x[-1]) #make use of the current thread
    for t in threads: t.join()

      But now we've re-introduced a recursive call to eval (inside of arg_thread)! Let's go ahead and CPS that away:

def cps_map_eval(k,v,*x):
    """
    Evaluates the elements of an argument list,
    creating continuations that will assign values
    to the correct indices in the evaluated list.
    """
    arglen = len(x)
    if arglen == 0: return k([])

    argv = [None]*arglen
    done = [False]
    
    def arg_thread(i,ax):
        def assign_val(val):
            if done[0]:
                new_argv = argv[:]
                new_argv[i] = val
                return k(new_argv)
            else:
                argv[i] = val
        eval(ax,v,assign_val)

    threads = [Thread(target=arg_thread,args=(i,ax))
                for i, ax in enumerate(x[:-1])]

    for t in threads: t.start()
    
    def arg_k(val):
        if done[0]:
            new_argv = argv[:]
            new_argv[-1] = val
            return k(new_argv)
        else:
            argv[-1] = val
            for t in threads: t.join()
            done[0] = True
            return k(argv)
    
    return Tail(x[-1],v,arg_k)
    

      This has some ugly code duplication. We can get rid of that and eliminate all of the conditional branches at the same time. The new version of cps_map_eval looks like this:

def cps_map_eval(k,v,*x):
    """
    Evaluates the elements of an argument list,
    creating continuations that will assign values
    to the correct indices in the evaluated list.
    """
    arglen = len(x)
    if arglen == 0: return k([])

    argv = [None]*arglen
    
    def assign_val(i,val):
        argv[i] = val

    def reassign(i,val):
        new_argv = argv[:]
        new_argv[i] = val
        return k(new_argv)

    def arg_thread(i,ax):
        eval(ax,v,ArgK( lambda val: assign_val(i,val),
                        lambda val: reassign(i,val)))

    threads = [Thread(target=arg_thread,args=(i,ax))
                for i, ax in enumerate(x[:-1])]

    for t in threads: t.start()
    
    def arg_k(val):
        argv[-1] = val
        for t in threads: t.join()
        return k(argv)

    return Tail(x[-1],v,
                ArgK(arg_k,lambda val: reassign(-1,val)))
    

      ArgK is a callable wrapper class that takes a function to run the first time it's called and a function to run every other time it's called. This eliminates a lot of nesting and allows reassign to be shared everywhere. The definition of ArgK looks like this:

### self-modifying continuations for argument evaluation

class ArgK():
    def __init__(self,first,rest):
        def k(val):
            self.k = rest
            return first(val)
        self.k = k

    def __call__(self,val):
        return self.k(val)
        

      And it contains no conditional branches.
      Now that we have a mechanism for concurrent evaluation of arguments, we can use that to build a concurrent analog to the sequential "begin" construction. The simplest way to do it is to simply pass concurrent expressions as arguments to "list"; a simple vau expression to do that and resturn the result of the first expression looks like this:

(define par (vau (a) % (car (eval % (cons list a)))))

      It's rather inefficient to create a list if you're going to throw most of it away, though. Just as we could make the built-in sequence function much simpler and more efficient than the sequential version of cps_map_eval, we can make a much better built-in concurrency construction. We'll have it parallel the semantics of "begin" by returning the value of the last listed expression.

def par(k,v,*x):
    """
    Evaluates arguments in parallel, returning the
    last listed value like sequence does.
    Ensures that all parallel threads terminate
    before continuing
    """
    if len(x) == 0: return k(None)
    final = [None]

    def call_k(val):
        return k(final[0])

    def par_thread(ax):
        eval(ax,v,ArgK(lambda val: None,call_k))
    
    threads = [Thread(target=par_thread,args=(ax,))
                for ax in x[:-1]]
    for t in threads: t.start()

    def par_k(val):
        for t in threads: t.join()
        final[0] = val
        return k(val)
    return Tail(x[-1],v,ArgK(par_k,call_k))
    

      The par function starts up a new thread with its own eval loop for every argument except the last, throws away the results of all those other threads, and saves the results of evaluating its last argument. And what if you don't want to throw away the results of all those other threads? Just call "list", and it will evaluate all of it's arguments concurrently! You can test it with this sample program which evaluates a bunch of expressions of varying complexity and prints the results in the order that they are completed:

(define mul (lambda (a b) (* a b)))
(begin
    (print (mul (+ 1 2) 3))
    (print (* 4 5))
    (print (+ 10 12))
    (print 7))
(par
    (print (mul (+ 1 2) 3))
    (print (* 4 5))
    (print (+ 10 12))
    (print 7))
(print
    (list
        (print (mul (+ 1 2) 3))
        (print (* 4 5))
        (print (+ 10 12))
        (print 7)))

As usual, working code can be found at https://github.com/gliese1337/schrodinger-lisp/.

First-Class Everything: Loops, Tail Calls, and Continuations

      From where we left off in "Schrodinger's Equation of Software", we had first-class functions, first-class syntax, and first-class environments. Since we can build anything out of lambdas, and we can build lambdas out of vau and wrap, our language ought to be complete, right? Well, yes, if we actually had a perfect implementation of the mathematical ideal of vau calculus.
      Unfortunately, the limitations of Python's stack mean that we can't use recursive loops. There are two ways to solve this: we can add another built-in function just to handle loops, or we can separate the interpreted stack from the Python stack and make tail calls work.
      The simplest way to make tail calls work is to use trampolining. So, we'll define a special interpreter data structure for a tail call that encapsulates everything we'll need to execute the function call (i.e., all of the arguments to eval), and return that instead of the value of the function call whenever we have a function call in tail position.

class Tail():
    def __init__(self,expr,env):
        self.expr = expr
        self.env = env

    def __iter__(self):
        yield self.expr
        yield self.env

      Then, we modfy eval to check if it got a value or a tail call instruction every time it executes a procedure. If it did get a tail call, it replaces its arguments with the data in the tail call object and loops:

def eval(x, env):
    "Evaluate an expression in an environment."
    while True:
        if isa(x, Symbol):          # variable reference
            return env[x]
        elif isa(x, list):          # (proc exp*)
            proc = eval(x[0], env)
            if hasattr(proc, '__call__'):
                val = proc(env,*x[1:])
                if isa(val, Tail):
                    x, env = val
                else:
                    return val
            else:
                raise ValueError("%s = %s is not a procedure" %
                                  (to_string(x[0]),to_string(proc)))
        else: return x

      Note that eval should *never* return a tail call object; it's not a value in the language, it's just bookkeeping for the interpreter. That works pretty well; if you write proper tail-recursive loops, they'll run just fine. But we can do better. For one thing, there's still a recursive call to eval in eval. For another, not all calls to eval in the builtin functions are tail calls. E.g., here's the definition of "if":

    'if': lambda v,z,t,f: Tail((t if eval(z,v) else f), v)

      The middle call to eval can't be replaced by Tail. The basic binary operators can't be fixed at all, and these sequences of eval -> procedure -> eval can still result in blowing up the stack. Ideally, we want to eliminate any recursive calls to eval, so no matter what happens to the interpreted language stack, Python's stack doesn't grow. We could make sure that *all* function calls are in tail position by transforming our interpreted programs into CPS- but that would add a whole lot complexity to our interpreter to do the transformation. We can get the same effect by noting that the continuation of an interpreted expression is exactly the same as the continuation of the interpreter when it's interpreting that expression; therefore, we just have to CPS the interpreter. And since our eval function is tiny, that's no trouble at all!
      The CPSed eval function looks like this:

def eval(x, env, k=lambda x:x):
    "Evaluate an expression in an environment."
    val = None
    while True:
        if isa(x, Symbol):          # variable reference
            val = k(env[x])
        elif isa(x, list):          # (proc exp*)
            def capture_args():
                cx, cv, ck = x[1:], env, k
                def try_call(proc):
                    if hasattr(proc, '__call__'):
                        return proc(ck,cv,*cx)
                    raise ValueError("%s = %s is not a procedure" %
                                      (to_string(cx[0]),to_string(proc)))
                return try_call
            x, k = x[0], capture_args()
            continue
        else:
            val = k(x)
        if not isa(val, Tail):
            return val
        (x,env,k) = val

      Of course, we also have to re-write all of our builtin functions, which are now called with an extra continuation parameter, in CPS, but we'll get to that later. Now, the k parameter to eval isn't a real continuation, because Python doesn't have them; it's a callback that actually does return a value, but the value it returns is the value of executing the continuation. At the top level, when calling eval from outside, there's no continuation to process values, so the callback is just the identity function. Once again, eval can never return a Tail, nor can it return a continuation- but continuations can return Tails (in fact, they usually will), so we have to make sure that we check that whenever we get a value via a call to k.
      Function application is a little bit special; we build our own continuation in the eval function that will actually do the procedure call, using a Python closure to save the necessary state, then loop to evaluate the procedure itself. We also avoid the overhead of constructing and destructing a Tail object since we already have all the bits that we need right there, and the environment stays the same. Of course, we also have to update the definition of a Tail, since we've increased the number of parameters to eval:

class Tail():
    def __init__(self,expr,env,k):
        self.expr = expr
        self.env = env
        self.k = k

    def __iter__(self):
        yield self.expr
        yield self.env
        yielf self.k

      To help support recursion, we'll update the way that closure __call__s are handled a little bit:

def __call__(self, k, call_env, *args):
    new_env = Env(zip(self.vars, args), self.clos_env)
    new_env[self.sym] = call_env
    if not 'self' in args: new_env['self'] = self #safe recursion
    return Tail(self.body, new_env, k)

      Now, every procedure gets access to a special "extra parameter" called "self" that refers to the currently executing function, unless it's overwritten by an explicit parameter of the same name. This ensures that recursion will still work even if the function is re-assigned to a different name, or if it's anonymous, without having to bother with the Y-combinator. Now we can write a simple infinite loop:

((vau (a) %
    (begin
        (define va (eval % a))
        (print va)
        (self (+ va 1))))
    0)

      And it works! A never-ending stream of increasing numbers printed to the console, and Python doesn't complain about blowing up the stack.
      Back to CPSing the built-in functions. Only a few of them are actually interesting: define, begin, list, and wrap. Define is interesting because it has side-effects: it modifies the environment. Other side-effectful functions (like set! and print) are essentially identical in structure:

def defvar(k,v,var,e):
    def def_k(val):
        v[var] = val
        return k(val)
    return Tail(e,v,def_k)

      It just builds a continuation that performs its side-effects before passing the return value onto the external continuation.
      Begin has to build a chain of continuations that will evaluate successive expressions in an arbitrarily long list until it gets to the end and passes the value of that expression to the external continuation. It looks like this:

def sequence(k,v,*x):
    if len(x) == 0: return k(None)
    return Tail(x[0],v,k if len(x) == 1 else lambda vx: sequence(k,v,*x[1:]))

      The apparent recursive call to sequence does not actually risk exploding the stack, becuase it's not called from here; it's only called as the value of k somewhere in eval. Thus, it only grows the stack by two frames: one for the lambda that throws away intermediate values, and one for the next call to sequence, which will return without actually calling itself. The implementation of "cond" is similar.
      List and wrap initially seem similar to begin. However, they have to actually save intermediate results, and that makes a big difference. List is implemented with this function to map evaluation loops over a list of argument expressions:

def cps_map_eval(k,v,*x):
    vx = []
    arglen = len(x)
    def map_loop(i):
        if i == arglen: return k(vx)
        else:
            def assign_val(vmx):
                vx.append(vmx)
                return map_loop(i+1)
            return Tail(x[i],v,assign_val)
    return map_loop(0)

      It builds a chain of continuations that tack the value of an expression onto the end of the mapped argument list and then evaluates the next one. Wrap uses that same function to evaluate arguments to a wrapped procedure:

def wrap(k,v,p):
    return Tail(p,v,
        lambda vp:
            k(lambda ck,cv,*x:
                cps_map_eval(lambda vx: vp(ck,cv,*vx),cv,*x)))

      Since, after CPSing, every call to eval in the builtin functions is transformed into constructing a Tail object, CPSing our interpreter has also nicely eliminated the dependency between the definition of the global environment and the interpreter itself.
      Now that we have proper tail calls and a continuation chain that's independent of the Python stack, we're just about ready to implement first-class continuations! There is, however, one little problem: if we give interpreted programs access to their continuations, anything that tries to activate a continuation into a function argument list will break cps_map_eval. The continuation will tack new values onto the old argument list, re-evaluating any arguments after the one whose continuation was called, and try to continue to the next procedure with too many arguments!
      To fix this, we need to ensure two things: 1) argument evaluation order is arbitrary and unimportant; 2) calls to continuations that return to a function argument slot fill in the value of that slot, and only that slot. The new version of cps_map_eval that accomplishes those goals looks like this:

def cps_map_eval(k,v,*x):
    """
    Evaluates the elements of an argument list,
    creating continuations that will assign values
    to the correct indices in the evaluated list.
    """
    arglen = len(x)
    if arglen == 0: return k([])
    argv = [None]*arglen
    done = [False]
    def map_loop(i):
        if i == arglen:
            done[0] = True
            return k(argv)
        else:
            def assign_val(vmx):
                if not done[0]:     #on the first time through,
                    argv[i] = vmx   #evaluate the next argument in the list
                    return map_loop(i+1)
                else: #if this is a continuation call,
                    new_argv = argv[:]   #copy the other argument values
                    new_argv[i] = vmx    #and just overwrite this one
                    return k(new_argv)
            return Tail(x[i],v,assign_val)
    return map_loop(0)

      Note that "done" is a single-element list rather than a simple boolean variable due to Python's scoping rules- closures can't mutate variables in higher scopes, but they can mutate the contents of containers. With just a little more work, this could be further modified to ensure that argument evaluation occurs in parallel.
      Now that our continuations are safe, we need to decide how to give the interpreted language access to them. It seems a little disingenuous to make calls to continuations look just like calls to functions, but since we turned all of our syntax into function calls, we don't really have any special syntax that we could use that would look different. So, we'll just go with that. We'll wrap up interpreter callbacks in a special callable Continuation object for the interpreted language:

class Continuation():
    def __init__(self,k):
        self.k = k

    def __call__(self, call_k, call_env, *args):
        if len(args) != 1:
            raise Exception("Continuations take exactly 1 argument.")
        return self.k(args[0])

      We could just use a Python closure for that, but making it a class of it's own results in nicer debugging output. When called, it throws out the current environment and continuation, and activates the saved callback instead. This version of Continuation acts like a vau expression- it doesn't evaluate its argument! We could use wrap on a continuation value, but it's probably better if explicit arguments to continuations behave the same way as implicit return values, so here's an alternate version that evaluates the continuation's argument:

class Continuation():
    def __init__(self,k):
       self.k = k

    def __call__(self, call_k, call_env, *args):
        if len(args) != 1:
            raise Exception("Continuations take exactly 1 argument.")
        return Tail(args[0],call_env,self.k)

      This even looks more like what it actually does: returns to another iteration of the eval loop, but replacing the current continuation with the saved continuation.
      We still need to provide a way for programs to get references to continuations. Rather than adding an extra built-in form like call/cc to bind continuations to the environment, we'll just make another minor edit to how closures are __call__ed:

def __call__(self, k, call_env, *args):
    new_env = Env(zip(self.vars, args), self.clos_env)
    new_env[self.sym] = call_env
    if not 'self' in args: new_env['self'] = self #safe recursion
    if not 'return' in args: new_env['return'] = Continuation(k)
    return Tail(self.body, new_env, k)

      Every function gets a reference to the current continuation at its call site as an extra over-writable argument, just like "self", which it can return or pass on to other function calls.
      Here are a couple of simple programs to verify that it really works:

(print ((vau () %
    (begin
        (+ 1 2)
        (return 7)
        19))))

      Prints 7, not 19, because the current continuation that would return 19 is thrown out and replaced.

(define c nil)
(define mul (lambda (a b) (* a b)))
(print
    (mul 
        ((vau () % (begin (set! c return) 2)))
        (+ 2 3)))
(c 3)
(c (+ 1 2))

      Prints 10, 15, 15, restarting the calculation with a different value for the first argument each time c is called.

As before, working code can be found at https://github.com/gliese1337/schrodinger-lisp/.

Schrodinger's Equation of Software

      After reading Michael Nielsen's "Lisp as the Maxwell's equations of software", I thought "that eval function is huge; there has got to be a way to simplify it". Additionally, I've long been annoyed by the fact that many of Lisp's syntactic forms and function calls look exactly the same; this leads to enormous frustration when you try to do something like (map and list-of-bools) and are informed by the compiler that "and" is not a function- it's a macro. If it looks like a function, it should act like a function. Ideally, it should actually be a function; the language should not treat it specially.

      So, I started playing around trying to eliminate as many special forms as possible from the interpreter. Here's my modification of the tiddlylisp eval function, stripped down with as much as possible moved into the global environment, and with a little extra error handling thrown in:

def eval(x, env):
    def eval(x, env):
    "Evaluate an expression in an environment."
    if isa(x, Symbol):  # variable reference
        return env.find(x)[x]
    elif not isa(x, list):  # constant literal
        return x
    elif x[0] == 'quote' or x[0] == 'q': # (quote exp), or (q exp)
        (_, exp) = x
        return exp
    elif x[0] == 'if':  # (if test conseq alt)
        (_, test, conseq, alt) = x
        return eval((conseq if eval(test, env) else alt), env)
    elif x[0] == 'cond':  # (cond (p1 e1) ... (pn en))
        for (p, e) in x[1:]:
            if eval(p, env):
                return eval(e, env)
        raise ValueError("No Branch Evaluates to True")
    elif x[0] == 'set!':  # (set! var exp)
        (_, var, exp) = x
        env.find(var)[var] = eval(exp, env)
    elif x[0] == 'define':  # (define var exp)
        (_, var, exp) = x
        env[var] = eval(exp, env)
    elif x[0] == 'lambda':  # (lambda (var*) exp)
        (_, vars, exp) = x
        return lambda *args: eval(exp, Env(zip(vars, args), env))
    elif x[0] == 'begin':  # (begin exp*)
        for exp in x[1:]:
            val = eval(exp, env)
        return val
    else:    # (proc exp*)
        exps = [eval(exp, env) for exp in x]
        proc = exps.pop(0)
        if hasattr(proc, '__call__'): return proc(*exps)
        else: raise ValueError("%s is not a procedure" % to_string(x[0]))

The global environment looks like this:

global_env = Env({
    '+': operator.add,
    '-': operator.sub,
    '*': operator.mul,
    '/': operator.div,
    '>': operator.gt,
    '<': operator.lt,
    '>=': operator.ge,
    '<=': operator.le,
    '=': operator.eq,
    'eq?': lambda x,y:(not isa(x, list)) and (x == y),
    'cons': lambda x,y:[x]+y,
    'car': lambda x:x[0],
    'cdr': lambda x:x[1:],
    'list': lambda *x:list(x),
    'append':operator.add,
    'len': len,
    'symbol?': lambda x:isa(x,Symbol),
    'list?': lambda x:isa(x,list),
    'atom?': lambda x:not isa(x,list),
    'exit': exit,
    'True': True,
    'False': False
})

      The only things that have to be coded into the eval function are basic syntactic forms that need to be able to control the evaluation of their arguments or directly access the environment. If we implemented macros, most of those could be extracted from eval and implemented as macro definitions in the global environment (in exchange for complicating eval with macro expansion). But, there's another way to simplify eval, without ever needing macros: rather than evaluating all of the arguments to a function, pass the unevaluated expressions along with a reference to the dynamic calling environment and let the function decide which ones it actually needs evaluated. A function that behaves that way is called a vau expression, and using it allows us to eliminate all special syntactic forms from the language; even the definition of a vau expression itself can be implemented as a vau expression!

The interpreter for vau expressions looks like this:

def eval(x, env):
    "Evaluate an expression in an environment."
    if isa(x, Symbol):    # variable reference
        return env[x]
    elif isa(x, list):    # procedure call
        proc = eval(x[0], env)
        if hasattr(proc, '__call__'):
            return proc(env,*x[1:])
        raise ValueError("%s = %s is not a procedure" %
                        (to_string(x[0]),to_string(proc)))
    return x # literal constant

Much simpler! And this is the global environment:

def vau(clos_env, vars, call_env_sym, body):
    def closure(call_env, *args):
        new_env = Env(zip(self.vars, args), self.clos_env)
        new_env[self.sym] = call_env
        return eval(self.body, new_env)
    return closure

def defvar(v,var,e):
    val = eval(e, v)
    v[var] = val
    return val
 
def setvar(v,var,e):
    val = eval(e, v)
    env.find(var)[var] = val
    return val

def cond(v,*x):
    for (p, e) in x:
        if eval(p, v):
            return eval(e, v)
    raise ValueError("No Branch Evaluates to True")

def sequence(v,*x):
    for e in x[:-1]: eval(e, v)
    return eval(x[-1], v)
 
def wrap(v,p):
    p = eval(p,v)
    return lambda v,*x: p(v,*[eval(expr,v) for expr in x])

global_env = Env({
    '+': lambda v,x,y:eval(x,v) + eval(y,v),
    '-': lambda v,x,y:eval(x,v) - eval(y,v),
    '*': lambda v,x,y:eval(x,v) * eval(y,v),
    '/': lambda v,x,y:eval(x,v) / eval(y,v),
    '>': lambda v,x,y:eval(x,v) > eval(y,v),
    '<': lambda v,x,y:eval(x,v) < eval(y,v),
    '>=': lambda v,x,y:eval(x,v) >= eval(y,v),
    '<=': lambda v,x,y:eval(x,v) <= eval(y,v),
    '=': lambda v,x,y:eval(x,v) == eval(y,v),
    'eq?': lambda v,x,y:
    (lambda vx,vy: (not isa(vx, list)) and (vx == vy))(eval(x,v),eval(y,v)),

    'cons': lambda v,x,y:[eval(x,v)]+eval(y,v),
    'car': lambda v,x:eval(x,v)[0],
    'cdr': lambda v,x:eval(x,v)[1:],
    'list': lambda v,*x:[eval(expr, v) for expr in x],
    'append': lambda v,x,y:eval(x,v)+eval(y,v),
    'len':  lambda v,x:len(eval(x,v)),
    'symbol?': lambda v,x:isa(eval(x,v),Symbol),
    'list?': lambda v,x:isa(eval(x,v),list),
    'atom?': lambda v,x:not isa(eval(x,v), list),
    'True':  True,
    'False': False,
    'if':  lambda v,z,t,f: eval((t if eval(z,v) else f), v),
    'cond':  cond,
    'define': defvar,
    'set!':  setvar,
    'vau':  vau,
    'begin': sequence,
    'eval': lambda v,e,x: eval(eval(x,v),eval(e,v)),
    'wrap': wrap
})

      The definition of the environment is now more complex because every function has to handle the evaluation of its own arguments. The vau expression that defines new vau expressions takes a list of names of arguments and a body expression, just like a lambda would, but has an additional parameter for the symbol to which the calling environment should be bound. Now, if you look carefully, you may be wondering "where's quote? where's lambda? don't we need those?" Well, no, we don't; quoting is the default behavior anyway, since vaus don't evaluate arguments, and anything that we can do with lambdas we can do with vaus, always exercising explicit control over evaluation. But in order to save typing, we can write quote and lambda as standard library functions. They look like this:

(define q (vau (e) % e))
(define lambda (vau (args body) %
    (wrap (eval % (list vau args (q $) body)))))

      In order to define lambda, we needed an extra built-in function called "wrap"; wrap just takes a vau expression and returns a new vau expression that automatically evaluates all of its arguments. Lambda uses eval to produce a vau expression that takes the same list of argument names and the same body as the lambda expression did with a throwaway environment binding, and then wraps it to ensure that all of its arguments will be evaluated.

All that wrap does is essentially to map eval over the argument list. We can write map in vau expressions:

(define null? (vau (x) % (= (eval % x) (q ()))))
(define map (vau (f l) % 
    (begin
        (define fv (eval % f))
        (define lv (eval % l))
        (if (null? lv) (q ())
            (cons (fv (car lv)) (map fv (cdr lv)))))))

So, can we write lambda using an explicit map, and no wrap? Well, not very easily. An attempt is something like this:

(define curry (vau (f a) %
    (begin
        (define fv (eval % f))
        (define av (eval % a))
        (vau (b) & (fv av (eval & b))))))

(define lambda (vau (args body) %
    (vau (eval % args) &
        ((eval & (list vau args (q $) body))
            (map (curry eval &) (eval & args)))))

      But the problem with this is that a call to (vau ...) does not evaluate its arguments! So, rather than lambda returning a vau expression that takes the same arguments as the lambda expression, it will end up returning a vau expression that takes arguments named "eval", "%", and "args". If you fix that by evalling the outer vau expression, then you'll have to quote the inner evalled vau expression, which unbinds its eventual evaluation from the environment in which lambda was called. Providing wrap as an additional primitive saves the day.

Wrap also allows us to simplify the definition of our global environment a bit:

global_env = Env({
    '+': wrap(None,operator.add),
    '-': wrap(None,operator.sub),
    '*': wrap(None,operator.mul),
    '/': wrap(None,operator.div),
    '>': wrap(None,operator.gt),
    '<': wrap(None,operator.lt),
    '>=': wrap(None,operator.ge),
    '<=': wrap(None,operator.le),
    '=': wrap(None,operator.eq),
    ...
})

Although this formulation is somewhat less efficient. One could also simply write all of the built-in functions in forms that do not evaluate their arguments, assuming that they will only get primitive values and not expressions passed it, and then define the more general argument-evaluating forms as standard library functions using wrap.

      Vau & wrap actually provide a more fundamental abstraction than lambda does, in the sense that they can be used to build lambdas and some other extra stuff. So, if the Lisp interpreter is like software's Maxwell equations, I see the vau-based interpreter as a bit like software's Schroedinger equation, with the special built-in global environment functions (like the definition of vau itself, or the define function, or the if function) filling the roles of the different fundamental particles that obey it, which can be composed to form all matter. Maybe vau expressions are like complex-valued quantum wave functions, while wraps are like the resulting probability distributions.

      Vau essentially makes syntax and environments into first-class language citizens, while wrap allows us to drop into the more concise world of implicit evaluation when we want to. Making syntax with explicit control of evaluation into a first-class citizen means that we don't need macros anymore; notice that our definition of lambda used its arguments as components in constructing a new syntax tree and then evaluated that, just as macros are used for compile-time syntax transformations. Anything that can be accomplished with compile-time macros can be accomplished at run-time with a vau expression instead. (Of course, implementing compile-time macros may still be desirable for efficiency reasons.)

      Since synactic forms and regular functions are no longer distinct, there's no need for keywords; anything can be used as a variable name, and anything can be shadowed or overwritten. This may seem like a very dangerous thing to allow, as any JavaScript hacker could tell you, but if you're paranoid about other code overwriting important functions in your dynamic environment, you can always write your code in a closure containing a reference to the unmodified global environment, and evaluate everything in that.

      Since we have explicit control over when and how arguments are evaluated, we also no longer have to worry about laziness vs. strictness, or call-by-value vs. call-by-name vs. call-by-reference. Those distinctions only arise when the details of evaluation are abstracted away behind a lambda expression. Want strict evaluation? Write your function to evaluate all its arguments up front. Want lazy evaluation? Just evaluate arguments when you actually need them, and cache the results in a mutable local variable. Want call-by-name? Evaluate arguments when you need them and don't bother with caching.

With first-class environments, we can also build namespaces without built-in language support; referencing a symbol in a namespace is just a special case of evaluating an expression in an environment. This allows for cool things like returning an environment from a deeply nested nested closure, and using it to evaluate a function definition elsewhere, thus permitting flattening out of deeply nested closures without losing access to the static environment where the nested closure was originally defined. It's just like defining a class in, say, C++ with a bunch of private instance variables, and then defining all of the method implementations elsewhere, un-nested, with a little annotation that says that they belong to that environment.

      For more examples of vau expressions, here's the tiddlylisp square root program from Michael's article re-written into vau form:

(define sqrt (vau (x) % (sqrt-iter 1.0 (eval % x))))

(define sqrt-iter 
    (vau (guess x) % 
        (begin
            (define gv (eval % guess))
            (define xv (eval % x))
            (if (good-enough? gv xv) gv
                (sqrt-iter (improve gv xv) xv)))))

(define good-enough? 
    (vau (guess x) % 
        (< (abs (- (eval % x) (square (eval % guess)))) 0.00001)))

(define improve (vau (guess x) %
    (begin
        (:= gv (eval % guess))
        (average gv (/ (eval % x) gv)))))

(define abs (vau (x) % (begin (define xv (eval % x)) (if (< 0 xv) xv (- 0 xv)))))
(define square (vau (x) % (begin (define xv (eval % x)) (* xv xv))))
(define average (vau (x y) % (* 0.5 (+ (eval % x) (eval % y)))))

      Now maybe you're wondering "why did we eval the argument to sqrt? It just gets passed straight on to sqrt-iter, and sqrt-iter evaluates it, so isn't that redundant?"

      Well, if you instead write sqrt as (vau (x) % (sqrt-iter 1.0 x)), it will work so long as you only pass in primitive numbers as arguments. If you try (sqrt (+ 1 2)), though, Python will explode at you. What went wrong?

      (vau (x) % (sqrt-iter 1.0 x)) passes sqrt-iter the symbol x, not it's value; sqrt-iter then evaluates the symbol x, and, since the dynamic environment of sqrt in which x was bound is included in the scope chain of the dynamic environment passed to sqrt-iter, it resolves to the expression passed to sqrt. If that was a number, all is well. But if it was a compound expression, it blows up! Defining sqrt as (vau (x) % (sqrt-iter 1.0 (eval % x))), however, ensures that when sqrt-iter evaluates the symbol x (which is value of sqrt-iter's formal parameter x), it will always get a number back. The square function actually could be simplified, since we know it's only ever called with primitive number arguments, but I've left it with its own call to eval so that it could be used in other situations.

Appendix: Syntactic Sugar

      Based on the analogy of evaluating in an environment to referencing a namespace, we can add a little syntactic sugar to our parser to get rid of all the "evals". We'll have ENV::EXPR desugar to (eval ENV EXPR) and 'EXPR desugar to (q EXPR) so we can re-write our library functions like this:

(define sqrt (vau (x) % (sqrt-iter 1.0 %::x)))

(define sqrt-iter 
    (vau (guess x) % 
        (begin
            (define gv %::guess)
            (define xv %::x)
            (if (good-enough? gv xv) gv
                (sqrt-iter (improve gv xv) xv)))))

(define good-enough? 
    (vau (guess x) % 
        (< (abs (- %::x (square %::guess))) 0.00001)))
(define improve (vau (guess x) %
    (begin
        (:= gv %::guess)
        (average gv (/ %::x gv)))))

(define abs (vau (x) % (begin (define xv %::x) (if (< 0 xv) xv (- 0 xv)))))
(define square (vau (x) % (begin (define xv %::x) (* xv xv))))
(define average (vau (x y) % (* 0.5 (+ %::x %::y))))

(define q (vau (e) % e))
(define lambda (vau (args body) %
    (wrap %::(list vau args '$ body))))

(define null? (vau (x) % (= %::x '())))
(define map (vau (f l) % 
    (begin
        (define fv %::f)
        (define lv %::l)
        (if (null? lv) '()
            (cons (fv (car lv)) (map fv (cdr lv)))))))

(define curry (vau (f a) %
    (begin
        (define fv %::f)
        (define av %::a)
        (vau (b) & (fv av &::b)))))

We can also write an extra library function to get a handle on the current environment, in case we're not inside a vau expression:

(define get-env (vau () % %))

And that allows us to see that any variable reference

    vau> (define a 2)
    vau> a
    2

is actually equivalent to

    vau> (define std (get-env))
    vau> std::'a
    2

evaluating a symbol in the current namespace.

Code for a working vau interpreter can be found at https://github.com/gliese1337/schrodinger-lisp.

VR, Peanuts, and Willpower

I have a friend who's a recovering video game addict. She* knows this, and has it under control, but she cannot play video games alone because she knows she will come to three days later realizing she's forgotten to go to class. I am the reverse; I enjoy video games, but I will go months before realizing that I haven't played in a while, and maybe I'd enjoy it. In this way, addiction to virtual worlds is different from addiction to drugs. It doesn't affect everyone, only a certain fraction of people who for some reason are psychologically predisposed to it. It's a bit like food allergies. Peanuts, e.g., are not generally considered poisonous, but they are to me, just as video games are not inherently addictive, but they are to my friend. Almost any activity can be addictive to someone; the result is what is usually termed a 'nerd'. The prevalence of video gaming, however, ensures that video game addiction occupies a special place in the public view. While this awareness fuels public worry over the problem of gaming addiction, the very same awareness leads to the extinguishing of that worry. Video game addiction has already started to fade from the public view as it becomes an old problem that we know to expect and know how to deal with. The negative impacts on the lives of gaming addicts are not a result of any inherent feature of games, though the features of a game may make it more or less potentially addicting; they are the results of susceptible people not knowing how to deal with something new, or to recognize when they personally have a problem. And the solution is correspondingly nothing to with video games themselves. It's teaching people to exercise willpower and effectively manage their own lives.

*Yes, female.

What Plagiarism Isn't

For the record, the idea of replacing a symbol with the thing it symbolizes to enforce rational thinking comes to me from Eliezer Yudkowski (http://yudkowsky.net/).

Your Boss Is IT Equipment

The fundamental enabler of large-scale organization is not management; it's communication. Starting on a small scale, any 2, 3,4, or n people can only organize and coordinate their actions if they can communicate with each other. The limit on the scale of organizations is the limit on how effectively people can pass information around. Hierarchical management structures are a solution to the problem of overcoming the natural spatial, temporal, and cognitive limitations on how effectively any individual can connect with a group of others. They represent a social and cognitive technology for facilitating communication, which uses extra people as components to make connections. Because people are very expensive pieces of equipment, hierarchical management is limited in how many connections it can support. This limit can only be overcome when you realize that the real problem is not how to manage more effectively; it's how to enable more effective communication.

This is why information technology is so important. This is why the internet is so socially disruptive. It is an alternate approach to amplifying the ability of an individual to communicate with large groups of others without the need to use other humans as components in the system. At both the smallest scales and the largest, it makes management obsolete. To reduce costs and build large-scale organizations, just replace your managers with switches and routers.

This Post Inspired by Here Comes Everybody.

Where Have all the Flowers Gone?

Computer Science has an embarrassing problem: it attracts a much smaller percentage of females than other science & engineering disciplines. This was not always the case; the world's first computer programmer was a woman, and in the late 70s and 80s women were not uncommon in CS departments. So why did they leave? The answer must explain what makes Computer Science as it is now so different from Mathematics or Electrical Engineering. It's not the subject matter; no, the most significant distinguishing characteristic of Computer Science is that almost no one becomes an Electrical Engineer or a theoretical Mathematician in 6th grade - almost everyone in those fields starts out on an equal footing - but children can program. The barrier to entry for experience with the tools of Computer Science is low, and a 6-year-old can get it. And thus, when I ask women I know why they didn't consider Computer Science in college, I get answers like "I would've been competing with people like you who've been doing it since you were kids," and "I might've if I'd known how fun it could be." Computer Science, more than other fields, suffers from gender discrimination in childhood. Fixing the imbalance will require not just better college recruitment, but changing how we raise our children.

A Technical Religion

Religion and technology are not usually mentioned together. "Religion" as a word has an air of archaism. It is based in the eternal declarations of God to our ancient ancestors, not the newfangled creations of secular men. Yet all knowledge ultimately is inspired by God, including the inspiration for new technology. God works most often through the agency of human servants, and surely He would want His servants to be as capable as possible. The message of true religion does not change, but the media for transmitting it do as God inspires humanity to produce more and better tools to improve the lives of His children. As a side effect, He lets us have Angry Birds.

Amateur Linguist Teaches Elvish to Ethiopian Tribe

OK, yeah, not really...

But you just know that would be the headline somewhere if the mainstream press decided to cover this.

The story starts with Paul Bennet planning to go to Ethiopia; specifically, to a region where the native language is Hamer. Hamer, it turns out, has no writing system.

Being an amateur linguist, Paul decided to do what any of us would do in the same situation: design an orthography for them! Hey, if it worked for St. Cyril....

The neighboring and related language Ge'ez does have a writing system, so the initial plan was to borrow it, with the idea that it would do double-duty in helping Hamer speakers record their own language and give them a leg up on literacy anywhere else in Ethiopia. The work in progress can be seen here.

In discussion on the CONLANG mailing list, however, someone just had to notice that the phoneme inventory of Hamer just happens to fit very neatly in the Tengwar grid. There are existing Tengwar modes for writing English and Latin in the Elvish characters, so why the heck not?

The probability of an Ethiopian tribe actually adopting Tolkein's Elvish characters as the basis of their writing system is rather small, especially since the Ge'ez characters are already officially included in Unicode while Tengwar just have a proposal with codepoints subject to change.

But it would be pretty awesome, wouldn't it?

Mickey Must Die

Let's get one thing straight: it is entirely possible to simultaneously believe that the current state of copyright law is borked beyond repair and that intellectual property is a valid concept which ought to be useful for making money. The law says there's this thing called "Fair Use", an escape from copyright restrictions that lets our culture build upon and expand creative works while still respecting intellectual ownership. But it is so ill-defined and so disrespected by the courts that no one can be confident of actually using it and being safe from attack. Even if your right to Fair Use is upheld in a court, the simple threat of fees from a tactical lawsuit is enough to freeze any attempts to apply it. In this environment of fear, copyright law's primary function is no longer to encourage innovation by ensuring compensation; it is to provide a legal avenue for stifling speech and stomping out creativity. So when I say that I do not respect copyright law, that it should not be followed and needs to be eliminated, that Mickey Must Die, it is not because I think that all information must be inherently free and artists have no claim on their work. It is because my sense of social responsibility is stronger than my greed.

You Can't Buy Everything At The Bazaar- Yet

The first rule of good software is that it scratches the programmer's personal itch. Unfortunately, not everyone with an itch is a programmer. Programming exists as a profession precisely because not everyone with a problem is capable of effectively solving it themselves, and thus someone has to get paid for scratching other people's itches. This will always be the case, because no matter how widely computer literacy is spread throughout society, some people will always be better at it than others; the fact that almost everyone can read and write does not make novelists obsolete, and the same is true for good programmers. This seems to imply that there will always be bad software maintained by people who care only as far as they are paid. However, there is one way out: as the population of programmers expands, the probability that one of them shares whatever problem you may have grows. When the bazaar is big enough, one just has to solve the problem of finding the person who wants to make what you need.

In Which Cliff Stoll Destroys Ignorance

Rarely do those who experience great stories know at the beginning how the stories are going to end, precisely because it is the banishment of high orders of ignorance[1] that makes for a great story. If you already know the end of your story, you're already there, and there is no more story. All character development and all personal growth is a matter of coming to realize the answers to questions that one previously didn't even know existed to be asked. The higher the levels of ignorance overcome, the greater the story is.

At one level, Cliff Stoll's The Cuckoo's Egg[2] is the story of how an astronomer became an expert in computer security, but Cliff could have expected this; he didn't know about security from the start, but he knew he would have to learn. He knew that there were questions to be asked on that topic. On another level, The Cuckoo's Egg is about how a self-styled irresponsible kid discovered responsibility and ethics. This is the greater story, because Cliff not only had to learn the answers, and not only had to learn the questions to ask to get the answers, but had to first learn that there was a topic about which ethical questions could be asked. That realization is the fundamental weltanschauung-altering event, which Cliff Stoll struggled with throughout his pursuit of the German hacker. He knew that his views were changing; he worried about how he would be received by his "radical friends" in the "People's Republic of Berkeley"; and he worried because he knew that not only would they disagree with his new politics, but that they were basically incapable of understanding his new politics, because they did not know how to ask the questions that were the prerequisite for understanding. It is that realization, not the simple acquisition of technical knowledge, that made him a real expert in his new field.

[1] http://dl.acm.org/citation.cfm?id=352194

[2] http://www.amazon.com/Cuckoos-Egg-Tracking-Computer-Espionage/dp/1416507787/

Facebook Knows My Family Tree

Genealogical research is not about generating new information; it is about trying to find information that already exists somewhere, in some inconvenient format, and re-entering it. It is using human brains to look for pointers in written records and joining those records by hand. As more and more records are digitized, or collected originally in digital form, it is utterly insane that human researchers should still be required to engage in this menial work. No one should have to slave away manually searching through old records looking for the pointers that connect one human to another in the family graph. The greatest potential revolution in genealogy lies not in new software to streamline the process of doing research, but in software that eliminates the human bottleneck entirely. The pinnacle of genealogical technology will have arrived when family trees assemble themselves, requiring only that someone ask.

Lobsters Are Bugs

Tonight, a major life milestone was past: I went on my first Real Date.

OK, so I've said that about a lot of other events. And I will probably say it about many more to come. This is because the classification of "date or not date" is not binary, but runs along a continuum of more and less traditional activities. And on Valentine's Eve, I have moved further along this continuum than ever before: I took my fiancée to a Real Fancy Restaurant.

This was only because we got a Gift Card for Red Lobster last Christmas, but for purposes of moving along the continuum, it totally counts.

As a result, I have now had my first experience eating Lobster. I'm not sure what to make of it; it tasted OK, but felt like raw beef. And lobsters are totally giant bugs. I'm not sure how I feel about that. I also had it confirmed by the waiter that there is in fact no dignified way to eat non-de-shelled shrimp.

My fiancée is laughing silently as I write this. I shall go hug her now, and look forward to further adventures moving along the Continuum of Real Dates in time to come.

Circumventing Filters for the Good Guys

Discussions of the ethical implications of technology tend towards the negative; if 'ethics' and 'technology' are mentioned in the same paragraph, it's usually to warn that the technology in question is somehow dangerous. Some more frequent targets of this sort of derision are file-sharing software (like BitTorrent) and anonymizers (like Tor). BYU's own internet filters even block websites about Tor, as it can be used to circumvent them. So it's nice to see an example of both of these technologies being used on a large scale for what most Americans at least would find a very ethically appropriate goal: circumventing Iran's attempts to simplify totalitarian surveillance by eliminating its citizens' use of encryption[1]. Technology itself, after all, is not good or bad- it's all in how the technology in question is being used.

[1] http://arstechnica.com/tech-policy/news/2012/02/tors-latest-project-helps-iran-get-back-online-amidst-internet-censorship-regime.ars

Eastern Europe: A Bastion of Freedom and Democracy?

In case you haven't heard yet, while the US public has worrying about SOPA and PIPA, Europe started dealing with their own version, called ACTA. While some were allegedly taken by surprise by the massive protests against SOPA and PIPA, everyone's pretty much used to American's protesting things. But would you be surprised to hear about anti-ACTA demonstrations in Prague? Or Czech members of parliament refusing to support it "as a matter of principle", and claiming that the media "played a part in the hush-up"[1]? A Slovenian ambassador even made a public apology for having signed the agreement, claiming that she acted carelessly and in ignorance and failed in her civic duty[2]. That is a level of candor that we never expect to hear from a US politician. Admitting ignorance as the Slovenian ambassador did is the first step towards gaining wisdom. But unfortunately, admitting ignorance is socially unnacceptable around here. Everybody knows, tacitly, that no one person can possibly be an expert on everything that they would need to know to decide every issue that faces the government. We'll start to make progress a lot faster when we can get around to no longer being embarrassed by that fact.

[1] http://m.ceskapozice.cz/en/news/politics-policy/czech-euro-mps-oppose-%E2%80%98completely-wide-mark%E2%80%99-acta

[2] http://boingboing.net/2012/02/03/slovenias-ambassador-apologi.html

Javascript Needs Continuations

I am a JavaScript junkie. I love JavaScript. I love building things in JavaScript. And I love the fact that node.js lets me easily use JavaScript on the server as well as the client. But sometimes, JavaScript is just plain missing a really useful feature, and it gets on my nerves. One thing that I do not love about JavaScript, in which opinion I am far from alone, is the proliferation of nested callbacks.

The biggest problem with asynchronous callbacks is that they're infectious. Asynchronicity cannot be isolated and encapsulated.

Consider this code:

var returnHTML = renderAPage(name);
response.end(returnHTML);
...
function renderAPage(name){
 return "Hello "+(name||"World")+"!";
}

Now maybe I want to make it a little more interesting and read a template out of a file or something:

var returnHTML = renderAPage(name);
response.end(returnHTML);
...
function renderAPage(name){
 return fs.readFileSync("hello.html",'utf8').replace("{name}",name||"World");
}

But this is slow, so I clearly want to use asynchronous IO. But if I do, I cannot maintain the same interface! Altering the internal implementation of renderAPage requires leaking changes up through everything that calls it- and this is true no matter how deeply nested that one asynchronous call may be in other auxiliary functions. My new asynchronous code now looks like this:

renderAPage(name,function(err,returnHTML){
 if(err) throw err;
 response.end(returnHTML);
});
...
function renderAPage(name, callback){
 fs.readFile("hello.html",'utf8', function(err, text){
  if(err) callback(err);
  else callback(null, text.replace("{name}",name||"World"));
 });
}

Much more cluttered, and I've essentially had to transform my entire program by hand into continuation passing style just so the event loop can take control away after that asynchronous system call and then give it back later. CPS transformations are supposed to be the job of a compiler, not a programmer. What I would really like to do is this:

var returnHTML = renderAPage(name);
response.end(returnHTML);
...
function renderAPage(name){
 var return_to = arguments.continuation;
 fs.readFile("hello.html",'utf8', function(err, text){
  if(err) throw err;
  return_to(text.replace("{name}",name||"World"));
 });
}

Where return_to is a genuine continuation- called like a function, but passes its argument through to the return value at the place where the continuation was saved. Being able to save continuations makes asynchronicity encapsulatable. And unlike other approaches to fixing JavaScript concurrency, this does not require any additional syntax or keywords; just an extra field on arguments representing the continuation at the place where a function was called.

Eh, but there is one complication- the way asynchronous calls are handled currently, renderAPage will end up returning twice, and the first time it'll return undefined, which is bad. We can just check the return value and terminate if it's not the real value, kind of like checking the return value on POSIX fork, but that fails to eliminate the leaking of implementation details. We could change the semantics of asynchronous calls, so they always suspend execution of that particular stack and never return. But then, what if you really do want to return twice?

I don't think that can be addressed without some additional syntax. Fortunately, it's a very simple bit of additional syntax. The break and continue keywords can already be used with label arguments, and they seem the perfect words to use for continuation control with expressions as arguments:

var returnHTML = renderAPage(name);
var response.end(returnHTML);
...
function renderAPage(name){
 var return_to = arguments.continuation;
 break fs.readFile("hello.html",'utf8', function(err, text){
  if(err) throw err;
  return_to(text.replace("{name}",name||"World"));
 });
}

Here, I'm using the break keyword to signal that this function call will never return- if it tries to return, just terminate execution. Thus, the only way to get information out of it is to have the continuation called. But what if I want parallel execution?

var returnHTML = renderAPage(name);
var headers = renderHeaders();
response.writeHead(200,headers);
response.end(returnHTML);

renderAPage and renderHeaders might both contain asynchronous calls with break, but I have no need to run them sequentially, and I don't want to pause the whole thread while waiting for renderAPage to return via continuation. Well, that's where continue comes in:

var returnHTML, headers;
continue returnHTML = renderAPage(name);
continue headers = renderHeaders();
response.writeHead(200,headers);
response.end(returnHTML);

This usage of continue tells the interpreter not to worry about whatever might be going on inside the following expression- don't worry about side effects, don't worry about execution breaks; spawn a new thread to handle it if you want, but that's an unnecessary implementation choice. You're allowed to keep going and execute some more lines, but just remember that if you ever actually need to read the result of that expression, pause and wait for the return, whether it's an actual return statement or calling a continuation. I'm not sure how one should handle the possibility of multiple returns in this situation; the simple way might be to simply say that continues are only allowed to return once, and subsequent calls to that continuation will throw an error or be ignored.

If the interpreter does feel free to actually spawn a new thread to handle "continues", this potentially gives the programmer great power to define new asynchronous functions without having to use the dreaded nextTick or setTimeout, perhaps something like this:

function myAsyncFunction(){
 var k = arguments.continuation;
 continue break (function(){
  ...
  k(return_value);
 })();
}

The continuation is saved; an anonymous internal function is called and specified not to return, but execution of the containing function is allowed to continue, and will initially return undefined, just like fs.readFile. At some point, however, the internal anonymous function calls the continuation, and it returns again.

These additional behaviors for break and continue do not conflict with any existing syntactically valid constructs, and since they don't require adding any new keywords, they're guaranteed not to break any pre-existing code. That extra syntactic complexity is, however, all just figuring out how to deal with concurrency. This is important because it's the main impetus for my annoyance over JavaScript's lack of continuations, but once you've got continuations they're useful for much more than just that. And while adding real continuations may be a major feat for implementation in the interpreter, the interface for it does not have to be, and again should be perfectly backwards-compatible. Will anyone give me my arguments.continuation?

EDIT: Somehow, my code samples got all messed up when this was first published. They are now all corrected.

Electronic Democracy

In 1979, Norman Spinrad wrote about an electronic democracy[1] that allowed every citizen of a world to be directly involved in their own government. At the time, this was a fantastic futuristic vision, a conceit to make a story work. One of the founding ideas of representative government is the impracticality of actually having everybody directly involved; so, we must allow a class of professionals to take care of governance full-time on our behalf. This works so long as the representatives can be trusted to act in the interests of those they represent. That is incredibly difficult to ensure, but as long as the inconvenience of direct democracy outweighs the combined inconveniences of either keeping politicians honest or dealing with the fact that they're not, we just do the best we can. Since 1776, the US has gotten worse at it (non-monotonically, but with a net downward trend), but there was never much we could ever do about it. That is no longer the case; Spinrad's electronic democracy could really exist in our world. The internet makes it easy for the public to remain informed on what's going on in their nation and its government. And while they can't all keep track of all of it, some millions of people can spend some small amount of their time on any particular aspect of the government's working; there is, collectively a lot more effort available to be used than all of the full-time government employees put together can provide themselves. We have the tools to address the problem of accountability. If we care, we can ensure our representatives do their jobs right.

Inspired by http://www.techdirt.com/articles/20120120/14472117492/mpaa-directly-publicly-threatens-politicians-who-arent-corrupt-enough-to-stay-bought.shtml

[1] http://www.amazon.com/World-Between-Norman-Spinrad/dp/0553258931/

Information Overload

It has been said that, when you have enough data, you don't have to be too clever. Or, in other words, more data usually beats better algorithms. This is empirically true when it comes to programming machines. If you just know some good ways of finding information already stored somewhere, you can often save a lot of trouble on actually calculating it; if you have a sufficiently massive dataset, you don't have to worry about how to do good statistics with a representative sample, because you can just look at the entire population. But many people, myself included, implicitly apply this logic to the operation of their own brains, and, sadly, our brains just don't work like computers. Every day, I am immersed in internet news. While I'm reading it, I always feel like this is a very important thing to do, and how wonderful is it that I can be so well informed in this day and age. But in the long run, very little of it really matters. I never want to get to work on anything until I know everything that the internet knows about that particular topic; but in reality, there is a point, very near the beginning, past which more reading will not improve my performance in any meaningful way. A human needs to be clever, to know how to use the information he has more than to gain all the information there is. One of the greatest challenges for education now may be not getting access to accurate information or figuring out how to study well, but rather filtering out what we actually need to know and successfully ignoring everything else.