A Programming Language for Magic

Or, The Structure and Interpretation of Demonic Incantations, Part II.

As previously mentioned, a great deal of the training for a magician in the animist, demon-magic world consists of developing the mental discipline to compose precise and unambiguous instructions. Natural human languages are terrible at both precision and disambiguation; legalese is a direct result of this fact, and it still fails. In order to summon demons safely, therefore, a specialized formal language will be required- a programming (or "incantation") language.

Many people criticize FORTH and related languages for being hard to follow when data is passed implicitly on the program stack, but that's not an indictment of the concatenative style- it's an indictment of point-free (or, less charitably "pointless") style; i.e., the avoidance of explicit variable names. Concatenative programs can use explicit variables for convenience, and applicative languages can be written in point-free style as well. This is in fact quite common in Haskell and various LISPs, though the syntax of most mainstream languages makes it less convenient.

Despite both being called "languages", programming languages aren't much like human languages. That is, after all, why we need them- because human languages don't do the job. Conversely, programming languages tend to not play nice with humans' natural language abilities. Nobody likes trying to speak a programming language, or even to write fluently in one. When working out ideas on a whiteboard, or describing an algorithm in a paper, real-world programmers and computer scientists frequently avoid real programming languages and fall back on intuitive "pseudo-code" which sacrifices rigor in exchange for more easily communicating the essential ideas to other humans (or themselves 10 minutes later!), with careful translation into correct, computer-interpretable code coming later.

Now, magicians could work in a similar way, and it makes sense that they frequently would: laboriously working out correct spells in a written incantation language ahead of time, and then executing them by summoning a demon with the simple instruction "perform the task described on this paper". One can even go farther and imagine that, given the effort involved in creating such a spell, that they might be compiled into books for frequent re-use, stored in a university library, such that from then on magicians could execute common useful spells by instructing a demon to, e.g., "execute the incantation on page 312 of volume 3 of the Standard Encyclopedia of Spells as stored on shelf 4A of the Unseen University Library".

But, this is not a universal solution. For many simple spells, the description of where to find them may well be longer and more error-prone than simply reciting the spell itself. And, as any sysadmin could tell you, sometimes it's not worth writing a stored program for one-off tasks; you just need to be able to write a quite bash script on the command-line. For magical purposes, therefore, we'll want a programming language that is optimized for speaking, while retaining the precision of any other programming language.

After some discussion on the CONLANG-L mailing list, I think I have a pretty good idea of (one possibility for) what a "magical scripting language" might look like.

The major problem that I see needing to be solved is parenthesization; one can't be expected to properly keep track of indentation levels in speech, and explicit brackets around everything can get really hard to
keep track of even when you can look at what you're doing on a screen (which is why we have special editors that keep track of bracket-matching for us!)

Ideally, the language would not require explicit parenthesization anywhere, and other "syntactic noise" and boilerplate code would be minimized, so that every token of the language carries as much semantic weight as possible, to make them easier to memorize. This leads me to think that a concatenative, combinator-based language (like FORTH, or the non-programming-language conlang Fith) would be the best base, on top of which "idiomatic" flourishes could be added. Concatenative languages are often called "stack based", but they don't have to be implemented with a stack. They are in fact isomorphic to applicative languages like LISPs (i.e., there is a purely mechanical method for transforming any concatenative program into a fully-parenthesized applicative program and vice-versa), and can equally well be thought of as "data flow" languages, specifying how the outputs of one operation connect up with the inputs of another, and this is in fact a topic I have written about on this blog before.

There is a trade-off between being able to keep track of complex data flow without any explicit variable names, which can get very difficult if certain items are used over and over again, and being required to keep track of lots of temporary or bookkeeping variables (like loop indices). A concatenative language that allows you to define variables when you want, but minimizes extra variables whenever they would constitute "syntactic noise" with minimal semantic value, seems to me the best of both worlds. This should make simple incantations relatively easy to compose on-the-fly, and easy to memorize, as they would be mostly flat lists of meaningful words, similar to natural language.

Once you introduce re-usable variables, however, you have to decide the question of how variables are scoped. Letting all variables have the same meaning everywhere ("global scope") is an extremely bad idea; it makes it very dangerous to try re-using existing spells as components of a new spell, because variable names might be re-used for very different purposes in different sub-spells. If we want to be able to define and re-use sub-spells (i.e., functions, subroutines, procedures, or blocks, in terms of real-world programming languages), there are two major approaches to scoping rules available: dynamic scoping, and static scoping.

Loosely speaking, dynamic scoping means that any variables that are not defined in a function (or block) are the same as variables with the same name that are in-scope at the place where the function was called. This can only be figured out when a function is actually run, hence "dynamic". Static scoping means that any variables not defined in a function (or block) are the same as variables with the same name that are in-scope at the place where the function was defined. This can be figured out by looking at the text of a program without running it, hence "static".

Dynamic scope is generally easier to implement in (some kinds of) interpreters, while static scope is generally easier to implement in compilers, which early on in CS history led to a split between some languages using dynamic scope and some using static scope just because it was easier to implement the language that way. The modern concensus, however, is that dynamic scope is almost always a Bad Idea, because it makes it harder to analyze a program statically and prove that it is correct, whether with an automatic analysis tool or just in terms of being able to look at it and easily understand how the program works, without running it. Nevertheless, dynamic scope does have some legitimate use cases, and some modern languages provide work-arounds to let you enforce dynamic scoping where you really need it.

Scala, for example, simulates dynamic scoping with "implicit arguments", and this really highlights a good argument for dynamic scoping in a spoken programming language. One pain point with most programming languages, which would only be exacerbated in a spoken context, is remembering the proper order for long lists of function arguments. This can be ameliorated by named (rather than positional) arguments, but having to recite the names of every argument every time one calls on a sub-spell seems like a lot of boilerplate that it would be nice to be able to eliminate.

With dynamic scoping, however, you get the benefits of named arguments without having to actually list them either in a function definition (although that might well be a good idea for documentary purposes when spells are written down!) or when calling them. Just use reasonable names in the body of a sub-spell for whatever object that sub-spell is manipulating, and as long as variables with the appropriate names have already been defined when you wish to use a sub-spell, that's all you need. Making sure that those names refer to the correct things each time the sub-spell is called is taken care of automatically.

Examples

So, what might this incantation language actually look/sound like? Let's look first a simple script to do your dishes after a meal:

loop [more-than COUNT-DISHES 0] [let DISH [NEXT-DISH] DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move]

Things that are assumed to built-in to the language are in lower case, while things that are assumed to be magician-defined are in upper case. If every "verb" has fixed arity (so you always know exactly how many arguments it will need- there are no ambitransitives) then you don't need brackets around arguments or special delimiters between statements/expressions. We only need them to delimit "complement clauses"- i.e., blocks of code that are themselves arguments to other operators (in this, case "loop" and "let").

If magicians want to create their own higher-order spells which take other spells as arguments, there's not much to be done about eliminating those brackets. There are transformations in combinator calculus that can be used to remove them, but the results are extremely difficult for a human to follow, and no one would compose them on-the-fly for anything task of significant complexity. We could introduce a macro metaprogramming system that would let magicians define their own clause-delimiter syntax to eliminate cruft or enhance memorability, but then you might have to remember separate syntax for every sub-spell, which could get even worse than having to remember a single set of brackets. This is, in fact, a real problem that the LISP community (among others) deals with- if your language is too powerful, and too expressive, you get fragmentation problems, and end up with extra memory burden trying to keep track of what ridiculous things your co-workers decided to use that power for. It's often easier to enforce consistency.

Still, we can achieve some improvement by adding some "flourishes" to some of the basic, built-in operators in the language, replacing generic brackets with special construct-specific keywords. This is in fact a strategy taken by many real-world programming languages, which use block keywords like "while...wend" or "if...endif" rather than generic brackets for everything. With that alteration made, the spell might look something like this:

while more-than COUNT-DISH 0 loop let DISH be NEXT-DISH in DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move wend

Now there's a lot of distance between the "loop" and the "wend", which could, in a more complicated spell, make it easy to lose track of, even with the specialized keywords. To help with that, we can do some aggressive let-abstraction- assigning blocks to variables, and then using the short variable name in place of the long literal block definition. That gets us a spell like

let WASHING be let DISH be NEXT-DISH in DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move in
while more-than COUNT-DISH 0 loop WASHING wend

In some ways, that's better, but now we have the potentially-confusing sequence of nested "let"s ("let ... be let ... be ... in ... in"), and we can't move the second "let" outside the definition of "WASHING" because it actually needs to be re-evaluated, redefining "DISH", every time "WASHING" is called. This wouldn't be a big problem in a written programming language, but it's seriously annoying in speech. There are a few ways it could be fixed; one solution I like is allowing cataphoric variables (which refer to a later definition) in addition to anaphoric variables (which refer to an earlier definition), so we can switch up which structure to use to avoid repetition, and make a choice about which structure is more conceptually appropriate in different kinds of spells. Cataphoric variables are not terribly common in real-world programming languages, but they do exist, as in Haskell's "where"-clauses. Implementing "where" in out magic language, we can write the spell as

while more-than COUNT-DISH 0 loop WASHING wend
where WASHING is let DISH be NEXT-DISH in DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move done

We might also take advantage of dynamic scoping to write the algorithm in a more functional style, mapping over the collection of dishes, like so:

for DISH in DISHES loop WASHING rof
where WASHING is DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move done

or

let WASHING be DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move in
for DISH in DISHES loop WASHING rof

In either case, the nested "let" to define the DISH variable is eliminated by binding a DISH variable in a for-in construct over a collection of DISHES, and relying on dynamic scope to make that variable available in the body of WASHING. Note that this avoids the need for spoken function parameter definitions, although it would be relatively easy to add syntax for them in cases where they do turn out to be useful.

Now, this looks like a pretty straightforward spell, but note that it only works if we assume that things like "pickup", "NEXT-DISH", "use", and so forth have all been rigorously and safely defined ahead of time! These are all actually pretty complex concepts, and in practice demon magic would probably not be used for relatively low-effort, high-descriptive-complexity tasks like washing dirty dishes. But, for magical scripting to be useful, we would a lot of these kinds of everyday things to be pre-defined. And just as *NIX users tend to have opinions about what things they individually want to have available in their command-line environment, and maintain custom .bash_profile/.bashrc files per login account, I imagine that perhaps working magicians carry around phylacteries containing written copies of personally-preferred spells, and begin each incantation by referring to them to establish the appropriate execution environment.

Uniform Call Syntax in Parles

After a long hiatus, I've come back to do a little more work on Parles. The GitHub repository now has a very simple but functioning compiler and VM that can run very simple programs. Now, I've got some thoughts on the next feature I'd like to add. Uniform Function Call Syntax is a concept implemented in several modern programming languages (like D, or Magpie) which helps make the core language smaller by treating object-oriented method calls, of the form foo.bar(baz), as simple syntactic sugar for function calls of the form bar(foo, baz). If you remove the parentheses, it becomes obvious that this is a fairly simple reordering rule: foo . bar baz gets rewritten as bar foo baz, with bar and foo switching places.

Parles already has two similar bits of token-reordering syntactic sugar (the ; and | operators), so adding a third one should really be no big deal. Since parentheses are already allowed in exactly the positions that you would put them in a method call in a language like C++ or JavaScript, this minor addition would allow Parles to simulate OO method call syntax exactly. We just need to figure out the rules for what exactly gets swapped with what.

The obvious simple solution is to just swap expressions (individual words or blocks). But, what if the expression preceding . produces multiple values? Calling a method on multiple values doesn't make much sense. It would be nice to define the . operator so that it requires the programmer to use it in a way that "makes sense" in terms of OO method calls, rather than as an arbitrary re-ordering operator. To handle that, we'll need to look at type information to guarantee that the output of foo is in fact a single value. It's also important that foo not require any arguments- i.e., that it actually be a value, not a partially-applied function call.

Additionally, we need to ensure that the method name (whatever comes after a .) is in fact a name - a single word - not an arbitrary expression. In other words, we want to make sure that programmers can write things like foo.bar, but not foo."hello world" or foo.(+ 1 2). That's a very simple syntax check that doesn't require any type information. It may also be a good idea to ensure that bar is a function that takes at least one argument (namely, foo).

These typing rules are similar to the restrictions that come with parens, and can be handled in a similar way. So, we'll start out by simply swapping the expressions on either side of a ., but adding implicit type annotations to the AST so that the type checker can ensure that a method call "make sense".

Method Chaining

Swapping single expressions on either side of a . lets us do simple method calls like foo.bar(baz), which gets re-written as bar foo (baz). But what if we want to chain method calls together, writing something like foo.bar(baz).qux(fred)? If . associates to the left, this gets re-written in two steps as bar foo (baz).qux(fred) and then bar foo qux (baz) (fred), which is not what we want! It should be qux bar foo (baz) (fred). We don't want to use just the first expression to the left as the first argument to qux- we want to use the whole preceding method call. There are several possible approaches to fixing this.

First, we could try using type information, just like we would for auto-parenthesization. There is some circularity involved if we use type information to figure out how to re-order things, because we can't actually do type unification until we know the proper order for all expressions, but there is a way around that: only the left argument is potentially ambiguous (since we already said the right argument must always be a single word), so the type checker just needs to keep track of the types of all contiguous subsequences of expressions up to the point where it encounters a .. That takes O(n^2) time for arbitrarily long subsequences, but we can skip sequences that cross block boundaries or ; or | operators. In that case, splitting a long program into two halves with a single block or re-ordering operator also cuts the typechecking time in half. As long as the basic chunks are small enough, this should be reasonable fast, close to O(n) time to typecheck a complete program. With progressive typechecking, every time a . is encountered, the compiler can then select some previous sequence that takes no arguments and returns a single value, and use that sequence as the left argument for the . reordering operator. If the Parles implementation does auto-parenthesization, the necessary type information will have to be calculated anyway, and re-using it for method call left-argument identification adds no additional typechecking overhead. Given that there may be more than one type-compatible left subsequence, though, we still need a rule for how to consistently select exactly one of them. There are two sane options: take the longest type-appropriate sequence, or the shortest.
The longest possible sequence is unlikely to be what you really want in most cases, and it potentially requires programmers to hold a lot more stuff in their heads to understand how any particular program is put together. Using the shortest possible sequence seems like a much better choice; it keeps the scope of reordering smaller and easier to think about, and in most cases will identify just a single expression anyway. Unfortunately, that is also a problem. For example, if baz returns a single value, then foo.bar(baz).qux(fred) will end up being re-written as bar foo qux (baz) (fred), which is not what we wanted! This approach would work fine for chaining method calls with functions that take zero, two, or more arguments, but fails for methods of one argument, which is not an uncommon case.

So, it seems that relying on the typechecker to tell us how to rewrite method calls is not going to work. The second option is to simply ignore the problem, continue to only swap single expressions on either side of a ., and make programmers explicitly mark off whatever they want to function as the left argument in a method call with a block of some sort whenever it is larger than a single word. In that case, we'd just require foo.bar(baz).qux(fred) to be written instead as (foo.bar baz).qux(fred), or {foo.bar baz}.qux(fred). That fails to faithfully simulate how method chaining works in other languages, though, and is thus rather unsatisfying.

The third option is to still require explicit delimiters for left method arguments, but in a slightly more subtle way: we can simply always collect everything to the left of a . up to the last enclosing block boundary, variable binding, |, or ;, regardless of type information. That means that, if you want to embed foo.bar(baz) in the middle of a larger line, you'll probably have to explicitly mark it off as {foo.bar(baz)} so that the . operator doesn't suck up anything more to the left of foo. But honestly, if you're writing Parles code in an imperative, OO style where method call syntax makes sense, you're not likely to want to embed {foo.bar(baz)} in the middle of a line- you'll stick it on a line by itself terminated by a semicolon and beginning with a variable binding and/or preceded by a block boundary or another line terminated by a semicolon.

After all that consideration, then, that's what Parles will do: . becomes a straightforward re-ordering operator working purely at the surface syntactic level, like ; and |, which swaps everything to the left up the the last enclosing block, variable binding, semicolon, or pipe, with a single following word, and which introduces implicit type annotations similar to those implied by parentheses.

Addendum: the git commit which implements method call syntax can be seen here on GitHub.

Parles: A Language With Less Irritating Superfluous Parenthesization

Well, I haven't blogged in rather a while. But, what with being in a Linguistics MA program, I've been feeling the need to take some me-time and do some Computer Science recently, and I might as well tell the world about it.

Building off my thoughts from Lisp Without Parentheses and Pointful Concatenative Programming, I've started working on a new language called Parles.

Most programming languages seem to me to have a rather inconsistent idea about evaluation order within a line- it usually goes left-to-right, the direction you read in, except when you have to jump backwards to the left to figure out what function to apply to all those argument expressions you just read left-to-right. Most concatenative languages are more straightforward- everything always goes left-to-right; but despite the wonderful consistency, this seems to cause Discomfort and Confusion to people coming from traditional Algol-style languages beyond what comes from just dealing with weird syntax (or the utter lack thereof- even less syntax than LISPs!). I have tried to resolve this issue in the design of Parles.

At its most basic level, Parles is essentially FORTH, read backwards: evaluation proceeds from right to left, with arguments evaluated before function calls (ignoring for a moment that all arguments *are* function calls), and appearing after them in the program text.

There are two ways to alter this basic behavior: semicolons and pipes.
The semicolon is the sequence operator; it is eliminated at parse time and causes everything parsed prior to the semicolon to be post-fixed to whatever comes after, up to the next semicolon or end-of-block. If you end every line with a semicolon, this will cause lines to be evaluated top-to-bottom, just as pretty much everybody ever expects them to be. Thus,

+ 1 2;
* 3 4;

is equivalent to

* 3 4 + 1 2

The trailing semicolon is irrelevant- it causes the entire program to be postfixed to the empty string, which is a no-op.

The pipe (|) operator behaves like a unix shell pipe- take the output from the stuff on the left, and feed it to the stuff on the right. It's essentially identical to the semicolon, except that it binds more tightly (re-ordering occurs up to the next pipe, semicolon, or block boundary) and encodes a type assertion that the output row type of the left side exactly matches the input row type of the right side. E.g., while

1 2 3; +

is totally valid, and results in "3 3" on the stack (with + popping 1 and 2 off the stack and replacing them with 3, and the original three coasting underneath untouched)

1 2 3 | +

is a type error, as the compound expression "1 2 3" has output type "int int int" while + expects only two ints as input. Pipe can be used to simulate infix operators, as long as there is a block boundary or semicolons to properly delimit the expressions whose types are to be matched. E.g.,

1 | + 2

is a valid infix version of

+ 2 1

There are three kinds of blocks, using three kinds of brackets: [], (), and {}.
[] blocks are called quotations and are taken pretty much straight from FORTH: they produce a function value whose type is equal to the type of the body. These are Parles's primary means of abstraction and delayed computation. In addition to all of the things that you would usually use functions for, they are necessary for using control-flow operators. For example, "if" in Parles is a function which takes a boolean and two quotations, and applies one or the other of them depending on the value of the boolean. Its usage looks like this:

if < 2 3
[print "true"]
[print "false"]

This is an excellent example of a circumstance where you do not want to end a line with a semicolon. Inserting semicolons would require re-ordering lines as follows (so that they will be properly un-reordered by the parser):

[print "false"];
[print "true"];
if < 2 3

which is the scary weird order that most FORTHs will make you write it in (modulo each line still being written backwards).

() blocks are argument blocks. They are evaluated immediately, but introduce a type assertion that the contained expression requires no arguments itself- i.e., takes nothing off the stack. Thus, they represent things that you would put parentheses around if you were writing in a traditional LISP. Indeed, you can write Parles to look like Scheme if you feel like putting parentheses everywhere you possibly can and not doing any interesting tricks with floating extra arguments on the stack. I considered extending the type assertion to require that the body terminate having placed exactly one value on the stack to serve as the return value, but plenty of LISPs already allow multi-value return, and it'd be a shame to eliminate that feature from a language to which it belongs so naturally.
Aside from organizing and documenting things for the sake of future readers of the code, the primary purpose of argument blocks is to annotate sections of code that can be executed in parallel due to a lack of input dependencies. A smart compiler would be able to identify such regions automatically, rather than just verify them when pointed out by a human, but that's Hard, so I probably won't implement it for a while, and putting in some clues to make your code easier to read is a good thing anyway.

{} blocks are just regular blocks, and they have no particularly special function except delimiting scope. As mentioned above, block boundaries limit semicolon and pipe re-ordering. In addition, however, all three kinds of blocks allow for an optional argument declaration that binds local variables by popping values off the stack. Thus, binding local variables is likely to be the most common use for regular blocks. That usage looks like this:

{a: str -> print print a a} "waka"

which binds "waka" to the string variable "a" and prints it twice ("wakawaka"). (This is slightly different from the syntax I played with in Pointful Concatenative Programming because I ended up needing the pipe character for something else.) All arguments (at least for now, until the type inference system is more advanced) must have a type declaration, and variables listed in the same order as the expressions which produced the values they bind to. E.g.,

{a: str b: num -> b a} "hi" 1

will bind "hi" to "a" and "1" to "b" (and swap their positions on the stack when it's done).

Quotations are a little bit special. Their argument binding behavior is just like what one would expect from anonymous functions in any other language: arguments are taken from the stack at the point of application, not at the point of creation (technically, this is true for all blocks, but for the others those are the same time). Quotations also form closures over their free variables that are bound in higher scopes.

So far, all functions (except built-in ones like "if") are anonymous. There is an "apply" operator for executing quotations stored on the top of the stack, but it is also possible to give quotations names by binding them to variables (as in pretty much every other language with first-class functions). In order to ensure equality between built-in and programmer-defined functions, using a variable that holds a quotation does not place that quotation value back on the stack, like accessing another value would; rather, it results in the application of the stored quotation. This means you can bind quotations to variable names and then use them just like the built-in words, without needing to use "apply". If you don't want them to be executed, just re-quote.

There is also one additional way to bind variables: using a lambda binding. This consists of the unicode lowercase letter lambda (λ) or a backslash (\) followed immediately by a name and type assertion. This is translated at parse time into a block binding a single variable whose scope extends left until the next explicit block boundary (or EOF). The intent is that you put these things at the beginning of a line terminated by a semicolon, kind of like a regular variable declaration in an Algol-style language, but you can put them anywhere you like. So, one might decide to declare a new function like this:

\sayhi [print "!" print print "hi "];
sayhi "Bob"

or

\sayhi [name: str -> print "!" print name print "hi "];
sayhi "Bob"

which will both print out "hi Bob!"

All variables are (for now) immutable, but can be shadowed as much as you like. That includes all of the built-in functions; so far, the only keywords or reserved symbols are: the various brackets, the argument arrow "->", the colon for introducing type assertions, the backslash and lambda characters, and the semicolon and pipe characters. Everything else is free game for redefinition by shadowing. Use this power wisely.

As of now, you sadly can't actually run any Parles programs; there's an outline of a virtual machine for it, but no code-generator. The parser and type-checker (a critical component of the compiler, as you can't figure out what hooks up with what unless you can figure out the in- and out-arity of every word) are working though, so you can at least parse and type-check Parles programs with the Python scripts in the Github repo.

Lisp Without Parentheses

Lisp is sometimes jokingly said to stand for "Lots of Irritating Superfluous Parentheses". Despite the joke, it turns out most of the parentheses in an average Lisp program are, in fact, superfluous. Let's examine the program for finding square roots by Newton's Method from SICP:

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (improve guess x)
   (average guess (/ x guess)))
   
(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

This isn't as bad as some Lisp programs, but even so, three closing-parens in a row starts to get hard to keep track of without editor support. Admittedly, most programmers have editor support (if your text editor can't match parens for you in 2013, you need to get a new text editor); but if we don't need them we might as well get rid of them. Parentheses do 3 things in this program: they tell indicate where function/macro applications start and where the argument lists for those applications end, and they delimit lists. If we know the signature of each function or macro, then we don't need parentheses for that second purpose- telling us where argument lists end. We can restrict them to simply marking applications (as opposed to functions that are being used as values), and delimiting lists (in this case, the only lists we need to worry about are the argument lists in function definitions). That gives us a transformed program that looks like this:

(define) '(sqrt-iter guess x)
  (if) (good-enough?) guess x
      guess
      (sqrt-iter) (improve) guess x
                 x

(define) '(improve guess x)
   (average) guess (/) x guess
   
(define) '(average x y)
  (/) (+) x y 2

(define) '(good-enough? guess x)
  (<) (abs) (-) square guess x 0.001

(define) '(sqrt x)
  (sqrt-iter) 1.0 x

For clarity, I've explicitly quoted the lists to distinguish an application from a list of a single element. This is starting to look a lot like Polish Notation with all of the operators parenthesized. You might think "Polish Notation arithmetic doesn't need parentheses because arithmetic operators use distinct symbols from operands"; true, but that turns out not to matter. If we think of values as functions that take no arguments and return themselves, and variables as functions that take no arguments and apply their values, then we can assume that everything is always applied by default, and then we don't need those parentheses (or anything else) to mark applications, giving us this:

define '(sqrt-iter guess x)
  if good-enough? guess x
      guess
      sqrt-iter improve guess x
                x

define '(improve guess x)
   average guess / x guess
   
define '(average x y)
  / + x y 2

define '(good-enough? guess x)
  < abs - square guess x 0.001

define '(sqrt x)
  sqrt-iter 1.0 x

This should look suspiciously like FORTH. If it doesn't, try capitalizing everything and reading it backwards (in Reverse Polish Notation, like old HP calculators use). I have a sneaking suspicion that FORTH variants have remained fairly niche languages largely because they put their arguments and function names backwards from everybody else (well, except for Assembly languages, but nobody really wants to program in assembly either). (Incidentally, this is very similar to how actual Lisps are compiled into concatenative languages like VM bytecode.)

As long as you have just enough static typing to keep track the arity of each function, all of the original parenthesization can be reconstructed automatically (which means that we can still implement things like lazy evaluation or automatic parallelization under the hood).

Now, we did lose something by eliminating parentheses are explicit delimiters of argument lists: you can't handle variadic functions anymore (well, unless you do crazy Haskell stuff). But, for the most part, you don't really need variadic functions. Lisps tend to map rest arguments to lists anyway, so just pass list. If you want, say, variadic add, just write a function to fold a list over binary add. Something like...

define '(\+ l) fold + 0 l

...er, oops. Type error. That code will be automatically parenthesized as follows:

(define (\+ l) (fold (+ 0 l)))

+ needs two numbers, not a number and a list, and fold doesn't take a number as it's first argument (plus, it needs a couple more). What we need is some way to turn off the application of + and get its value instead. We only need this for passing first-class function values as arguments, and that happens far less often than function applications do in most programs, so we can bring back parentheses for that (the exact opposite of their original purpose) and still have a net gain in program concision (and reduced nesting):

define '(\+ l) fold (+) 0 l

We're using parentheses here rather than some other symbol (like, say, a prefixed # or something) to indicate non-application, because we can actually put more stuff in there- a whole list of stuff, in fact. Maybe something like

define '(list-double-plus l) map (+ 1 * 2) l

What's really going on here is not that parentheses are suppressing application- rather, parentheses delimit lists (just like they do when quoted), but now, instead of representing function applications, unquoted lists represent functions that return functions composed of the contents of the list. (+) isn't a binary operator that hasn't been applied, rather it's a new function that returns a function composed solely of that binary operator. It gets applied as normal (to zero arguments), but its return value is what fold needed as its first argument. (+ 1 * 2) returns a function that's the composition of +, 1, *, and 2, with automatic currying. With these semantics, we don't actually need a separate "lambda" construct in the language anymore, since lists produce anonymous functions- as long as you're willing to program in point-free style, anyway.
If we just imagine the whole program as wrapped in one big set of top-level, outside parentheses, we can see that all programs are still lists- just less deeply nested ones. The language is still homoiconic, so it's still pretty easy to do metaprogramming, and it still makes sense to call this a dialect of Lisp.

Addendum on String Formatting:

The canonical example of a variadic function is a string formatter (which is what that Haskell variadic craziness was developed for, too). Since it's horribly stupid to get format strings out of variables, though,  and you should always have them as literals in the program text, we can solve that problem by building string formatting/interpolation into the language as have the language implementation turn literal strings into functions that take a fixed number of arguments (for the interpolation slots) and return string values.

Pointful Concatenative Programming

Well, I managed to spend the last year or so working on parallelism and vau expressions without actually writing any blog posts about it. Next week I'm giving a conference presentation, and maybe after that I'll come back here and review the last year's work. But for now, I am on to something a little different.

Reading Why Concatenative Programming Matters has inspired me to experiment with concatenative languages. Concatenative languages are often called "stack-based" languages, because they are incredibly easy to implement with stacks, but that article enlightened me to the fact that stacks are not actually necessary- other evaluation options are possible. In fact, type analysis can be used to identify substrings of concatenative programs that take no inputs which correspond to expressions in argument positions in functional languages and can all be executed in parallel. (In retrospect, this should have been obvious since functional languages compile to concatenative ones- this is just the reverse mapping.)

One of the reasons concatenative programming is cool because it's point-free; i.e., you never have to specify variable names, which makes things nice and concise. Unfortunately, that can backfire and end up making things horribly unreadable, which is why concatenative languages tend to suck at expressing basic math. Sometimes, you just want to use a variable to put the same value in multiple places; even in RPN syntax, "y x * y -", using variables to put values in the right place on the virtual stack, is way easier to read and understand than "DUP ROT * SWAP -", using stack effect operators. Not having variables also means that concatenative languages tend to lack the ability to do variable capture, which means no closures.

I have thus been pondering a concatenative language that adds variable-binding lambda expressions. Something like this:

{ a b | b a }

would take two values off the top of the virtual stack and bind them to variables "a" and "b" within the scope of the expression. Variables are just words that take no arguments are return their bound values. The effect of this expression would then be to swap the top two elements on the virtual stack. Lots of otherwise basic, built-in words can be created with these kinds of expressions. E.g., DUP looks like this:

{ x | x x }

These sorts of lambda expressions would be interpreted like words and applied immediately, causing them to function rather like let-bindings in functional languages. Combining lambdas with quotation, however, allows us to create closures:

{ x | [{ y | x y + }] }

This expression binds one argument and returns a closure that takes another argument and adds it to the closed-over value.

Well, that's all for now. Maybe, if I'm lucky, I'll have time this summer to start implementing this thing.

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.