grammar book

Intentional Programming

• Why trees? (I mean, what is it about a tree structure that captures so much about what we're doing when writing a program).
• Can this "abstract program" representation we're thinking about actually be separated from the syntax in the way we imagine? I guess I mean to ask about the nature of the abstract representation... what sort of structure could it have?

  IP just says that the IP Source Tree is composed of a tree of Intentions, with the children of each intention being a more concrete intention. Parent intentions contain all the information needed to understand/debug/image/compile its child intentions.

• What's become of IP? It seems to be inspired by the same notions that Greg has been talking about (esp. the "operate on the source tree" and extensibility aspects).

Revisit

Last time we encountered a problem with matching nodes on an AST with XPath. What we were trying to do is match certain patterns of nodes in the AST so that we could expand them as macro uses. Problem was, the grammar we were representing in our AST wasn't rich enough to match against. We want to be able to match against types, like 'type name', 'variable', 'statement', 'block', 'expression', and so on... but our grammar had only punctionuation: 'identifier', 'brace', 'parenthesis', 'bracket', 'semicolon', 'comma', etc. The grammar was essentially just punctuation, with a minimal amount of structure representing the 'matching punctuation' rules.

The thing is this. We know what sort of constructs can appear in a java program. But we don't know what sort of things can appear in the macro version. So we don't know how much, or what sort, of structure we to put in the AST. Do we represent:

as

or

or any of the other countless ways of structuring that sort of thing.

It seems to me that part of the problem is that we want to match elements based on what type it represents. For instance, in the second example above, we have a <block> inside a <statement> element as a way to represent the fact that a 'block' is a kind of 'statement'. We need this sort of type hierarchy information because we want to match against it -- we want to make rules that match both 'statement' and 'block' nodes. {ref WSDL}

Having type hierarchy matching would only partially help things. We still need to know what type hierarchies to use.. Do we do like the second example above, or

We can do stuff like the above -- naming the parts of the AST based on the grammar production it comes from -- for syntax constructs we know, but what about non-standard constructs that appear when we're writing macros. For instance,

How do we represent the stuff in the parentheses? How do we represent the parentheses themselves? Do we represent it as an <expression> holding several <ident>s and a <comma>? Or a <paren> with an <ident>, <comma> and a <declaration>?

Hrmm.. maybe we can generalize the basic semantic grammar to include "extension points" for macros. Well, by extension points I mean, bits of the grammar are so general that the can include regular sun java or new constructs. Consider declarations. We can have declarations of the following sorts:

We could generalize all of this with the following productions:

where <mod>, <type>, and <name> are all identifiers.

This idea of generalizing the grammar seems basically like what we were doing before by only representing punctionation. This is just more of a compromise which allows some of the annotating and typing we need, while still allowing new constructs.

But again, how general to go? As the grammar becomes more abstract (closer to just punctuation) it becomes more expressive but harder to match against in an XSL. Maybe 'harder' isn't the right word. What I mean is that making the grammar more abstract means that the macro expansion in the XSL seems to become less expressive. (Right? Because if, say, I only have 'ident' to match against, I can't tell whether it's a 'type' or a 'variable'... ).

I'm finding it hard to decide how abstract to make the Abstract Syntax Tree. That is, what do we actually need in terms of expressivity?

JSE parses the source using a basic punctuation grammar and then does all of it's matching in the code. From what I can see (though, I find the code very difficult to understand) they in-effect have a grammar which allows one to match against expressions, statements, blocks, type names, or generally identifiers, and punctuation (much like the first example AST representation).

Something seems off about all all of this. We're trying out macro expansions using XSL because we're thinking along the lines of representing source code as as XML. So far that has meant representing the AST of the source in XML. But now we've ended up putting little more than representing a punctuation. What have we really gained?

Maybe I'm going about this the wrong way. I've been thinking that the XML should represent the source code in such a general way that we don't need to know what parts are macro and what parts aren't.

What if we represent everything in the AST as it is. That is, we use an AST that represents macros and general syntax explicitly. For instance,

which represents:

So it's clear from the XML that the 'if' stuff belongs to sun java syntax, and the 'tryall' stuff belongs to the pipitone java syntax extension.

How did I render the above XML into that java code? Because I have a source renderer for sun:if and pipitone:tryall syntactic components in my head. I could have just as easily rendered it in pure sun java as:

I could have also rendered it as XML. It's pretty clear to me that this sort of thing would now be a synch to do with XSL.

So what I'm saying is that now the job of determing which bits of the code represent which bits of syntax is up to the plain text source code parser (as it should be, right?) rather than the macro template expander. Maybe bits of syntax could be imported like any other type:

And then if there was any ambiguity in parsing the source code, it could be dealt with like normal ambiguity in type usage. For instance, if I'm using a org.w3c.Document and a org.apache.lucene.document.Document in the same class I'm forced to use the fully qualified type name everywhere... So I could do this with syntax as well. Imagine that I wanted my 'tryall' macro to use the keyword 'catch' instead of 'catchall', but that might conflict with Sun's Java syntax. So:

might be a way to disambiguate this.

Under this scheme source code as XML is represented so that it is much more strongly connected to the syntax it represents. It can be validated against a schema much more specifically, etcetera etcetera. Hrm..

XAST

So the task at hand is to use XSL operations on the AST of a java program to expand macros in that program. In order to do this we need an XML representation of an AST. Last time I mentioned using JSE's parse tree. Here's what I came up with last night.

Consider the following program, with the macro 'unless',

A reasonable macro expansion would be,

To get things started, I first created an XMLReader which serializes JSE's AST. Its output for the above program looks like so,

As you can imagine, the above XML leaves out much of what the AST contained. That is, I didn't bother outputting source coordinates, and some semantic information (for instance, nodes on the AST knew whether they represented the end of a clause or not). For now, I decided to just spit out enough to allow me to reconstituted the original java program.

Also notice that the tree is pretty well unstructured. Only the most fundamental bits of the syntax rules (braces, parenthesis and brackets must match) are reflected in the structure. Maybe this is the most we can hope for, since we don't know anything else about the semantics of program until we start matching macros?

Transforming

So, by default I structured the XSL so it visits every node in order, from top to bottom, depth first, and outputs the nodes as it finds them. The template for the 'unless' macro matches at the point of reaching the unless identifier, by using the following XPath,

This says, "match the identifier 'unless' which is followed immediately by a pair of parenthesis". The output of the template is like this,

If I was to write this template in JSE notation it would look like this,

Actually, my template is a little more general, since it doesn't care whether the 'unless' expression is actually an expression, but only that it is followed by parentheses. This points to something larger. Using the current representation of the source code, I can't easily do much better. That is, I can't easily express, in XPath, the fact that inside the parentheses I should find an expression. Why? because expressions aren't marked as expressions in the AST, instead they're represented as unstructured goo. This came up again when I tried to write a template for a more complicated macro...

Traversing properly

This captures the "top down, depth-first, and output each node" behaviour. But notice that it does it in a peculiar way. Each time we match an element we explicitly call apply-templates to match its next sibling. This is in opposition to calling apply-templates on all of its children.

We do this is because there is an interplay between a macro transformation and the default traversal of the XSL. We don't know ahead of time whether a child of an element needs to be expanded until we've inspected the child's previous siblings. That is, when doing a macro transformation we need to add bits into the result tree and we need to control how and where different bits of the source tree are further expanded.

For instance, without the 'unless' macro, the default behaviour is to visit the 'unless' identifier, then visit the following 'Paren', then the 'Braces', and so on. But this isn't what we want to have happen when we transform the 'unless' macro. What we want is to output an 'if' and 'not' operator, then visit the inside of the 'Paren', and then visit the following 'Braces'.

So this is what the 'unless' template turned out looking like,

Blah.

Questions and thoughts

Q: Matching on type information.. Hard to do. It's hard, because we don't have any type information in our tree, as I mentioned above. How would we write a template for the JSE macro template,

The best we could with an XPath seems to be something like,

Yuck. This doesn't work entirely because *[4] matches any single element, so it could be a set of Parens, Braces, Braces, Comma, Semicolon, Identifier, ... Yuck, again. And how do we match the following statement?

Q: Macro uses expanding to macro uses... Imagine the following macro (expressed as a JSE template),

Well, whatever, the basic idea is that the 'unless' macro transformer produces the use of a 'using' macro. How do we deal with that? In XSL-speak, the bit of the tree holding the 'unless' expansion is the result tree, and a template is not allowed to operate on the result tree. To operate on the result tree (conceptually) we could run the stylesheet again over its own output. But what if a macro use expanded to a macro use which expanded to a macro use...?

Structured change detection

Jejune Ejen

yep, Ejen does the whole pipeline of XSLT thing pretty well, and they do have a component for generating SAX events from an ANTLR parse tree, which all seems like a good idea.. but the real headscratching i'm doing seems to be over what sort of representation of the parse tree makes sense to operate on. i won't go into detail right now, but the gist of it is that since we are trying to operate on a parse tree of a program that can contain new constructs (to be expanded as macros) we need to have a principled way to represent those new constructs without knowing anything about the macro syntax itself.

JSE parses and matches successfully , so i'll have to look more into how they do it, and maybe use their AST (of course, their matching strategy might be more complex than what can be done nicely with XSL). hrm...

out there *

[Ejen] allows the use of almost any kind of text file as input, without the need of developing lengthy and complex Java extensions. The use of the Antlr compiler compiler, when corresponding grammars ("Chomsky grammars") are provided, allows the transformation of those files into XML tree representations. Resulting XML trees may then be used in the generation process, as well as other native XML files.

Ejen is not therefore by itself a code generator. It is rather a system based on Java/XML/XSLT technologies that makes the actual creation of code generators easier and faster.

Coolness. It's always fun (though, I have to admit, slightly disappointing) to find a big chunk of the work started.

* the only reason I've taken to putting titles on my posts (something I find pretty silly) is that the hacked rss stream (look left) takes the first line as the title.

the story so far...

this hasn't been the week to blog, has it? I'm going to try to run down everything i've been up to over the past week, very quickly. i've been looking in to JSE, the Java Syntactic Extender. It's trying to do what define-syntax does for Scheme. I played with the JSE, b uilt a few silly macros, and looked into its implementation a bit. I downloaded ANTLR and created a small program to dump its parse tree to XML. Built a silly plugin to eclipse to dump it's internal AST to xml (just handled method calls so far. having no experience writing a plugin i was impressed that i could do it in the hour before i left for work one morning. eclipse + 1). Been reading more about syntax-rules implementations in scheme , as well as interpreter implementations (i'll post the links tonight) -- in particular I've been looking at how SISC (a java implementation of R5RS scheme) is put together.

Been thinking about being able to manipulate java more like how one can manipulate scheme. that is, where the program and all of the bits that make it up could be treated as first class objects. Hopefully I'll take the time tonight to post some examples.

Oh, and what's up with moon?

macros

Oh by the way, I implemented macro's pretty much exactly as Petrofsky had explained. The macro rewriting bit was fairly straightforward. I put in support for the most basic syntax-rules construct. Basically, it looks like this,

pattern variables must be just symbols that act as the parameters for the macro. template is an S-expression that is expanded by the macro transformer. The empty list right after syntax-rules is for literals, but I didn't bother implementing it.

Also notice that I didn't have the macro keyword appear in the macro itself. I could have, but I don't quite see the point of doing so. I ignored the whole pattern matching aspect of macros and just focusing on the transcription side.

So, when a macro is used its template is expanded and pushed onto the expression stack to get evaluated. Expansion is done by first creating map from pattern variables to the macro arguments. Then the expansion S-expression is built by recursively walking the template S-expression. If a number is encountered then it is put directly into the expansion (since numbers are immutable). A new list is created if a list is encountered and its contents are the expanded contents of the template's list. Finally, if a symbol is encountered which is mapped to an argument then the argument is put into the expansion, otherwise a new symbol with the same name is created and put into the expansion.

Actually, this isn't the whole story. The new symbol that is created is labelled in such a way that it can be distinguished as coming from that particular template transcription. This is the basis for the hygenic resolution of variable bindings. I introduced the class Label to capture the concept of a unique identifing mark on a symbol which makes it unique to that transcription AND provides enough information to look up the symbol in the environment of the macro transcription.

A new Label object is created each time a macro template is expanded, and it is applied to each generated symbol by the transformer. When the transformer emits a new symbol (it only does this, remember, when the template symbol is not a pattern variable) it labels the new symbol with all of the labels already applied to the template symbol plus the label for the current template expansion. To handle this, I modified Symbol objects to contain a list of Labels. Applying a Label to a Symbol means adding it to the end of this list.

The list of Labels then describes the history of macro expansions a symbol has undergone, in the order in which they happened. A Label itself contains two things, a unique integer across all instances, and an Environment. The unique integer per Label allows us to describe a Symbol as the symbol's name and the list of Label integers (just like Petrofsky's notation (ex. cons#1#2). In fact, this is exactly the sort of string I used to get the hash code for a Symbol so that symbols with different template expansion histories are treated as distinct symbols (the meaning of 'hygenic').

The only other change to the interpreter I made was to how a Symbol resolves its binding. Previously a Symbol.evaluate() would check with the VM's current environment for a binding. If one couldn't be found then it the symbol would be unbound. But the lexical scoping introduced by hygenic macros meant that symbol lookup should happen for each of the template transcription environments, from the most recent back. Furthermore, the symbol at the time of each macro template transcription, if it was in the environment at the time, wouldn't have label of that transcription. The upshot is that evaluating a Symbol involves first looking in the current environment, and then looking in each Label's environment, from the list of that Symbol's Labels, each time stripping off a label from the symbol.

tokens, snow, and ink

anyhow, the cs labs are a crappy (but surprisingly packed) place to be on a sunny afternoon, so this'll be short. (1) syntactic closures are fun, but when trying to work with i realized it's really hard to decided what bits of an expression need to be closed without looking at the semantics of the expression, and even then parameters can still be incorrectly captured. (2) renaming (explicitly: in such a way that the user could never do, or implicitly: like the serial code notation) seems like the most promising way to go about. well, i tried it out on several examples using odd hacks to introduce the new lexical scoping rules. works on paper. started implementing it last night (i'm not trying to do the whole define-syntax thing, just to handle a single pattern and an template).

syntactic closures

so, are syntactic closures everything i'd need to do something like the hygenic macro thang? to be honest, my head is slightly spinning with all of this. i probably need to sit down and work through some examples using this method again. when i tried it before (last week sometime) I arranged things so that the expression returned by each macro transformer was a syntactic closure. this worked for one macro tranformation, but failed when i had nested macros (i.e. a macro composed of another macro). this happened because expressions in the inner macro were captured by its closure, even though they should have refered to something in the outer macro. that is, this happens when a macro's parameter was 'replicated' (well, this is what Petrofsky calls it) by the inner macro and then put in an expression which assigned it a different value:

anyhow, Bawden and Rees refer to hygenic macros as the "other complete solution", and give a nice short description of it (aside: so i take it guess it's proper to refer to /syntactic closures/ as a solution to the problem of writing well-behaved macros, not as a solution to writing /hygenic macros/).

blurp.

quasiquotation

scaling Mount Oregano

literal expressions and external representation

part 4.1.2 of the spec discusses the quote operator. It says," (quote <datum>) evalutates to <datum>. <Datum> may be any external representation of a Scheme object." Hrm, so what's an external representation? It's a "sequence of characters", like "28" or "(8 13)". These sequences of characters "may be written in a program to obtain the corresponding object", as in the use of quote above.

so the question from before was something like, if you evaluate a quoted expression do you get back a something other than the expression itself -- a 'literal expression' type thing? according to the above, the answer is /yes/, what you get back is the external representation of the thing.

oddness. so, when does an external representation become an internal one? interpreter I - IV converted external representations to internal ones at the time of parsing.. (that's just what parsing was for). Evaluating a quoted expression, in those interpreters, has the effect of returning the expression itself, not the sequence of characters that make up the expression.

Ah, so maybe the spec is being murky again (that is, maybe my mind is being murky again as i read the spec) because look here, in the bit about external representations it says this, "Note that the sequence of characters "(+ 2 6)" is /not/ an external representation of the integer 8, even though it /is/ an expression evaluating to the integer 9 ..." Ah ha, so they /are/ calling the sequence of characters an expression, which means that if they say a quoted expression returns an external representation then they mean that it's exactly the same as returning the expression itself?

But wait, the above quotation from the spec continues, "... rather, it is an external representation of a three-element list, ..." Blurp.

so, my question remains,

macros

1. If a macro transformer inserts a binding for an identifier (variable or keyword), the identifier will in effect be renamed throughout the scope to avoid conflicts with other identifiers...
2. If a macro transformer inserts a free reference to an identifier, the reference refers to the binding that was visible where the transformer was specified, regardless of any local bindings that may surround the use of the macro

He paused for a moment's reflection.

"Tricky," he said finally.

the one-stack interpreter

But he does have a chapter at the end of his book, chapter 10, where he talks about modifying the lisp interpreter to use a single stack, compiler stylz. that is, like interpreter IV, expressions to be evaluated are pushed on to a stack. unlike interpreter IV, variable references are handled by using offsets within the stack. So if x is the 2nd formal parameter of some function, then references to it are resolved by looking at the (BLAH + 1)th thing on the stack. 'nuff said.

quasiquotation

According to the spec, "Quasiquote forms may be nested. Substitutions are made only for unquoted components appearing at the same nesting level as the outermost backquote. The nesting level increases by one inside each successive quasiquotation, and decreases by one inside each unquotation."

the backquote/comma notation is exactly equivalent to (quasiquotation <S-Expression>) and (unquote <S-Expression>). it appears that the 'unquote' symbol is only used as a delimiter, not as a variable bound to a function. For instance, (quasiquotation (unquote unquote)) in guile leads to an unbound symbol 'unquote' error.

macros

interpreter progress

okay, well, things went well with the stack based implementation. as greg notes, it made things *this* much easier.

quoted expressions

i met with miles yesterday's yesterday and we talked over how we each put our interpreters together. two things came up,

for instance, does 'dog evalute to the regular symbol dog or to a special type of literal symbol dog? what did miles mean by literal? well, i think he meant that there was a difference between variables and |literal symbols| in that if a variable was evaluated it returns whatever it's bound to whereas if a literal symbol is evaluated it returns itself. so the evaluation of the evaluation of 'dog should return the literal symbol dog according to miles? i dunno.. sounds confusing. maybe it'll make more sense when i get into macros and quasiquotation.

next up

next up is getting macros working. i read over the appropriate bits in R5RSand it seems clear enough. a macro definition is like a closure, but its evaluation results in an expression to be evaluated, and that expression comes from transforming the macro template. i was more than a little confused by greg's description of templates yesterday because he was introducing quasiquotation at the same time -- which makes sense since i imagine that dealing with quasiquotation inside a marco template brings out all the questions of how macro templates are transformed. well, more on this later when i step through the spec in more detail.

i'll also read up on macros in C. something i've only barely messed with to use wxWindows. greg was pointing out some weirdness that happens with C macros... something about how the macro parameters and local variables with the same name can cause unexpected, but very unintuitive, things to happen.

Representation and implementation

        SExpression
            Symbol
            Number
            SList
            Function

        SExpression expression = parser.getNextExpression();
        SExpression result = virtualMachine.getReturnValue(expression);
        System.out.println(result.toString);

            expressionStack.push(expression); 
            evaluate();
            return returnValueStack.pop();

        while(expressionStack.isNotEmpty())
            expressionStack.pop().evaluate(this); 

        Number.evaluate(VirtualMachine)
           virtualMachine.returnValueStack.push(this); 

        Symbol.evaluate(VirtualMachine)
            SExpression value = virtualMachine.lookup(this);
            if value == null
                throw EvaluationException("Unbound variable: ${name}");
            virtualMachine.returnValueStack.push(value);

        virtualMachine.lookup(Symbol)
            for each environment in environmentStack from top to bottom
                SExpression value = environment.lookup(symbol);
                if value is not null,
                    return it
            if we haven't found anything return null.

        environment.lookup(Symbol)
            return bindings.get(symbol)

        SList.evaluate(VirtualMachine)
            SExpression first = this.first();
            SExpression rest  = this.rest();  // guaranteed to be a list
            if first is null,
                throw new EvaluationException("missing or extra expression");
            virtualMachine.expressionStack.push(new ApplyFunction());
            virtualMachine.expressionStack.push(first);
            virtualMachine.returnValueStack.push(rest);

        ApplyFunction.evaluate(VirtualMachine)
            SExpression function  = virtualMachine.returnValueStack.pop();
            SExpression arguments = virtualMachine.returnValueStack.pop();
            if function is not an Function then
                throw new EvaluationException("wrong type to apply");
            if arguments is not a SList then
                throw new RuntimeException("stack outta wack.");
            ((Function)function).setup(virtualMachine, (SList)arguments)

        QuoteFunction.setup(VirtualMachine, SList arguments)
            if arguments.size() != 1 then
                throw new EvaluationException("missing or extra expression");
            virtualMachine.expressionStack.push(this);
            virtualMachine.returnValueStack.push(arguments.index(0));
            
        QuoteFunction.evaluate(VirtualMachine)
            SExpression result = virtualMachine.returnValueStack.pop();
            if result is null then
                throw new RuntimeException("stack outta wack");
            virtualMachine.returnValueStack.push(result);

       AdditionFunction.setup(VirtualMachine, SList arguments);
            if arguments.size() is not 2 then 
                throw new EvaluationException("wrong number of arguments to
                ${name}: ${arguments}")
            virtualMachine.expressionStack.push(this); 
            virtualMachine.expressionStack.push(arguments.index(1)); 
            virtualMachine.expressionStack.push(arguments.index(0)); 

        AdditionFunction.evaluate(VirtualMachine)
            SExpression operand1 = virtualMachine.returnValueStack.pop(); 
            SExpression operand2 = virtualMachine.returnValueStack.pop(); 
            if operand1 or operand2 are not Numbers then
                throw new EvaluationException("wrong argument type for
                ${name}");
            // i'm leaving out the type casting in the next step
            Number result = new Number(operand1.value() + operand2.value());
            virtualMachine.returnValueStack.push(result);

Expression Evaluation

        EXP STACK: [ 1 ]  ; push the expression to evaluate on the stack
        RTN STACK: [ ]

        EXP STACK:  [ ] 
        RTN STACK:  [ 1 ]

        EXP STACK:  [ (+ 2 3) ]  ; push expression to evaluate 
        RTN STACK:  [ ]

        EXP STACK:  [ + ]  ; the 'car' of the list
                    [ << apply-function >> ] ; a function application
        RTN STACK:  [ (2 3) ] 

        EXP STACK:  [ << apply-function >> ] 
        RTN STACK:  [ << addition-function >> ] 
                    [ (2 3) ]
       

        EXP STACK:  [ 3 ]  ; push argument 2
                    [ 2 ]  ; push argument 1
                    [ << addition-function>> ] ; push myself.
        RTN STACK:  [ ]

        EXP STACK:  [ << addition-function>> ] 
        RTN STACK:  [ 2 ]
                    [ 3 ] 

        EXP STACK: []
        RTN STACK: [ 5 ]

        EXP STACK:  [ (if T 'true 'false) ] 
        RTN STACK:  [ ] 

        EXP STACK:  [ if ] 
                    [ << apply-function >> ] 
        RTN STACK:  [ (T 'true 'false) ] 

        EXP STACK:  [ << apply-function >> ] 
        RTN STACK:  [ << if-function >> ] 
                    [ (T 'true 'false)  ]

        EXP STACK:  [ T ] 
                    [ << if-function >> ]
        RTN STACK:  [ 'true  ] 
                    [ 'false ] 

        EXP STACK:  [ << if-function >> ]
        RTN STACK:  [ T ]
                    [ 'true  ] 
                    [ 'false ] 
       
        EXP STACK:  [ 'true ]
        RTN STACL:  [ ] 

        ...

        EXP STACK:  [ ]
        RTN STACK:  [ true ]

A1.1: The function could push a sentinel on the RTN stack, so that the function just consumes expressions from the return stack until it reaches the sentinel.
A1.2: The function could push the number of things to read as the first thing on the RTN stack.
A1.3: The function instance could hold state as to the number of expressions it should read.

A1.3 means having to create a new instance of the function each time it's evaluated (so as to keep states distinct). Boo.
A1.1 means having to create a new SExpression that's just has the job of being a sentinel. Boo.
A1.2 No internal state, no new SExpressions, just good, clean fun. Way to go!

Closures

    
        EXP STACK:  [ ((lambda (x) (+ 2 x)) 1) ] 
        RTN STACK:  [ ]
        ENV STACK:  [ p1: { } ] 
        
        ...

        EXP STACK:  [ << (lambda (x) (+ 2 x)), p1: {} >>  ] 
        RTN STACK:  [ 1 ]
        ENV STACK:  [ p1: {} ] 

• replaces the environment stack with its own. Since it's the same, there's no difference.
• creates a new environment frame on the stack to hold the bindings to its formal parameters (p2).
• puts a function on stack to return the environment stack to what it was.
• puts it's body on the stack to be executed.

        EXP STACK:  [ (+ 2 x) ] 
                    [ << replace-env-stack p1 >> ] 
        RTN STACK:  [ ]
        ENV STACK:  [ p2: { x = 1 } ] 
                    [ p1: {} ] 

   
                EXP STACK:  [ (+ 2 x) ] 
                            [ << replace-env-stack >> ] 
                RTN STACK:  [ p1 ]
                ENV STACK:  [ p2: { x = 1 } ] 
                            [ p1: {} ] 

        ...

        EXP STACK:  [ << replace-env-stack p1 >> ] 
        RTN STACK:  [ 3 ]
        ENV STACK:  [ p2: { x = 1 } ] 
                    [ p1: {} ] 

        EXP STACK:  [ ] 
        RTN STACK:  [ 3 ]
        ENV STACK:  [ p1: {} ] 

        EXP STACK:  [ (set add (lambda (x) (lambda (y) (+ x y)))) ] 
        RTN STACK:  [ 3 ]
        ENV STACK:  [ p1: {} ] 
    
        ... 

        EXP STACK:  [ (lambda (x) (lambda (y) (+ x y))) ] 
                    [ << set-function >> ] 
        RTN STACK:  [ add ]
        ENV STACK:  [ p1: {} ] 

        ... 

        EXP STACK:  [ << set-function >> ] 
        RTN STACK:  [ << (lambda (x) (lambda (y) (+ x y))), p1 >> ]
                    [ add ]
        ENV STACK:  [ p1: {} ] 
       
        EXP STACK:  [ ] 
        RTN STACK:  [ ] 
        ENV STACK:  [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ] 

        EXP STACK:  [ (set add6 (add 6)) ] 
        RTN STACK:  [ ] 
        ENV STACK:  [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ] 
        
        ... 

        EXP STACK:  [ (add 6) ] 
                    [ << set-function >> ] 
        RTN STACK:  [ add6 ] 
        ENV STACK:  [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ] 

        ... 

        EXP STACK:  [ << apply-function >>  ] 
                    [ << set-function >> ] 
        RTN STACK:  [ << (lambda (x) (lambda (y) (+ x y))), p1 >> ]
                    [ 6 ]  
                    [ add6 ] 
        ENV STACK:  [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ] 
    
        ... 

        EXP STACK:  [ (lambda (y) (+ x y))  ] 
                    [ << replace-env-stack p1 >> ] 
                    [ << set-function >> ] 
        RTN STACK:  [ add6 ] 
        ENV STACK:  [ p2: { x = 6 } ] 
                    [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ] 

        ... 


        EXP STACK:  [ << replace-env-stack p1 >> ] 
                    [ << set-function >> ] 
        RTN STACK:  [ << (lambda (y) (+ x y)), p2 >> ] 
                    [ add6 ] 
        ENV STACK:  [ p2: { x = 6 } ] 
                    [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ] 


        EXP STACK:  [ << set-function >> ] 
        RTN STACK:  [ << (lambda (y) (+ x y)), p2 : { x = 6 } >> ] 
                    [ add6 ] 
        ENV STACK:  [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ] 

        EXP STACK:  [ ] 
        RTN STACK:  [ ] 
        ENV STACK:  [ p1: {  add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
                            add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >>    } ] 

        EXP STACK:  [ (add6 1) ] 
        RTN STACK:  [ ] 
        ENV STACK:  [ p1: {  add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
                            add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >>    } ] 
        
        ... 

        EXP STACK:  [ << apply-function >> ] 
        RTN STACK:  [ << (lambda (y) (+ x y)), p2: { x = 6 } >> ]
                    [ 1 ] 
        ENV STACK:  [ p1: {  add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
                            add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >>    } ] 
    
        EXP STACK:  [ (+ x y) ] 
                    [ << replace-env-stack p1 >> ] 
        RTN STACK:  [ ]
        ENV STACK:  [ p3: { y = 1 } ]
                    [ p2: { x = 6 } ] 
                    [ p1: {  add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
                            add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >>    } ] 

        ...

        EXP STACK:  [ << replace-env-stack p1 >> ] 
        RTN STACK:  [ 7 ]
        ENV STACK:  [ p3: { y = 1 } ]
                    [ p2: { x = 6 } ] 
                    [ p1: {  add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
                            add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >>    } ] 


        EXP STACK:  [ ] 
        RTN STACK:  [ 7 ]
        ENV STACK:  [ p1: {  add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
                            add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >>    } ] 

Continuations

Let's get some terminology going. Let the 'state' of the interpreter at any given moment consist of the EXP, RTN, and ENV stacks.

A continuation is a 1-ary function which *replaces* the current state of the interpreter with its own, and pushes its argument on the RTN stack.

Example:
Assume we have the current state:

        EXP STACK:  [ ] 
        RTN STACK:  [ ]
        ENV STACK:  [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ] 

Now evaluate (call/cc f)

        EXP STACK:  [ (call/cc f) ] 
        RTN STACK:  [ ]
        ENV STACK:  [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ] 

        EXP STACK:  [ call/cc ] 
                    [ << apply-function >> ]
        RTN STACK:  [ (f) ]
        ENV STACK:  [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ] 

        EXP STACK:  [ << apply-function >> ]
        RTN STACK:  [ << call/cc >> ]  
                    [ (f) ]
        ENV STACK:  [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ] 

            EXP STACK:  [ ]  
            RTN STACK:  [ ]  
            ENV STACK:  [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ] 

        EXP STACK:  [ f ]
                    [ << apply-function >> ] 
        RTN STACK:  [ << continuation-function, s1 >> ]
        ENV STACK:  [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ] 

        ... 

        EXP STACK:  [ << apply-function >> ] 
        RTN STACK:  [ << (lambda (cc) (cc 1)), p1 >>  ]
                    [ << continuation-function, s1 >> ]
        ENV STACK:  [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ] 

        EXP STACK:  [ (cc 1) ]
        RTN STACK:  [ << replace-env-stack, p1 >>  ]
        ENV STACK:  [ p2: { cc = << continuation-function, s1 >> ]  
                    [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ] 

        ... 

        EXP STACK:  [ <> ]
        RTN STACK:  [ << continuation-function, s1 >> ]
                    [ (1) ] 
                    [ << replace-env-stack, p1 >>  ]
        ENV STACK:  [ p2: { cc = << continuation-function, s1 >> ]  
                    [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ] 

        EXP STACK:  [ ]  
        RTN STACK:  [ 1 ]  
        ENV STACK:  [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ] 

-> (define add (lambda (z) (lambda (z) (+ z 6))))
-> (define add6 (add 1))
-> (add6 3)
9

In scheme everything is a so-called S-Expression. (symbolic expression). There are three or four types of S-Expressions: numbers, symbols, lists and closures (read: functions). a number is , well, you get it. a symbol is anything that isn't a parenthesis or a number, and a list is defined recursively as

( S-Expression * )

Each of these things can be evaluated. A number evaluates to itself, a symbol evaluates to whatever S-Expression it's bound to in the current, or any enclosing, scope (more on that later). A list can also be evaluated. It's like a function call. The first expression in the list is evaluated, and it must return a function. So to evaluate (+ 2 3) we first evaluate the '+' symbol to get the 2-ary function implementing addition. The rest of the list is passed into the function, and the function is evaluated.

So 123 evalutes to the number 123, (+ 2 3) evaluates to 5, + evaluates to the function implementing addition, and evaluating () is an error (since there is no function to execute.

The single quote, ', is actually a short form. It works like this, ' is short for (quote ). The 'quote' function is 1-ary function which just returns its argument. So 'a is short for (quote a) which evaluates to the symbol "a". '123 is (quote 123) which evalutes to the number 123, '() evaluates to (), ''() evaluates to (quote ()), etc..

Now, the function

(define add (lambda (z) (lambda (z) (+ z 6))))

So you know what a 'define' does.. it evaluates its second argument and binds that to the symbol that is its first argument. In this case we evaluate

(lambda (z) (....))

and bind it to 'add'. well.. (lambda (z) (...)) evaluates to a closure, which for the moment we can think of as a function. It's a 1-ary function with parameter 'z' and body (lambda (z) (+ z 6)). Forget the fact that the body is another lambda expression, we'll deal with that in a moment, it could just as well be something like (print z) or (+ z 1).

So now if i were to type 'add' at the prompt i should get whatever's bound to the symbol 'add' which is the 1-ary function I described above. But your question is, what does the function bound to 'add' actually do. Well, if I type (add 1) I invoke the function add with the argument '1'. What does that give us? Well, when we invoke a function we return the evaluation of the function's body, where we evaluate the body in a new scope in which we bind each parameter of the function to the evaluation of its respective argument. In our case, we are going to evaluate (lambda (z) (+ z 6)) in the scope where 'z' is bound to 1.

so what does (lambda (z) (+ z 6)), when 'z' is '1', return? first, forget about 'z' being bound to '1', and you'll see that the lambda expression evaluates to a 1-ary function with the body (+ z 6).. in other words, it's a function which adds 6 to its single argument. got it? the fact that 'z' is bound to '1' in the scope actually plays no role in the behaviour of this particular function because this function overrides the scope's "z" with the parameter with the same name. It's kind of like this in Java:

class add {
    int z = 1;

    int add6 (int z)
    {
        return z + 6;
    }       
}

If you created an instance of 'add' and called add6(3) you'd get 9.

(I'm still not even sure what the difference between a list and a function application is...

well, hopefully this makes a little more sense now. a list is what i defined above, a function application is the evaluation of a list, where the first element evaluates to a function. So (+ 2 3) is a list, but when we try to evaluate it we first eval + to get the addition function and so on.. we could also write an equivalent list ((lambda (x y) (+ x y)) 2 3). You see, this is the same thing as (+ 2 3). When we evaluate it we evaluate the first element (lambda (x y) (+ x y)) to get a 2-ary function that adds its arguments and then we apply it to the two arguments 2 and 3.

for instance, is (7 3) a valid expression in scheme? Or do you have to say ('7 '3) for it to make sense? Or '(7 3)??)

Well, this should make sense now. (7 3) is a list. If you tried to evaluate it you'd first try to evaluate 7 and get the number 7, which isn't a function so you'd get an error.

('7 '3) is also a list, which when evaluated would give you an error because '7 evaluates to 7 -- not a function. '(7 3) is a list too, namely the list (quote (7 3)) which evalutes to the list (7 3).

Also, what does Miles mean by <<(lambda (x) e), {p}>>? Is he just referring to an ordered pair that corresponds to one of your internal data structures? If so, then maybe I don't need to understand that.

Okay, so this is what I was glossing over when I said closures where just functions. A lambda expression (lambda (...) (...)) evaluates to a closure, which is the function implementing the lambda expression AS WELL as the current scope p (sometimes refered to as the environment). The idea is that when a closure is evaluated you evaluate it in the scope p.

So, let's say you do this:

-> (define a 2)                ; bind 2 to the symbol a

Then the current environment is {a <- 2}.

-> (define plus-two (lambda (x) (+ 2 a))

so 'plus-two' is bound to a closure which contains the lambda function and the current environment. You can see this play out if I was to do this:

-> (plus-two 2)
4
-> (define a 4)
-> (plus-two 2)
6

get it? So above when we defined add6 we actually created the closure:

    << (lambda (z) (+ z 6)), {z <- 1} >>

But applying the lambda expression to some number we first bind the argument to the parameter 'z' which overrides the things in the closure's environment.. like the example I gave with the method parameter overriding the class member.

So check this:

-> (define add (lambda (z) (lambda (x) (+ z x))))
-> (define add7 (add 7))
-> (add7 1)
8

There I changed the parameter for the inner lambda expression so that it uses a different name, which doesn't override the closure's environment binding.

I'll just fill you in on what I've tried. I rewrote the Lexer to use different classes as tokens. I've stuck with five token types so far,

        LeftParen 
        RightParen 

        Number 
        Quote - just the ' symbol 
        Symbol - anything that's not a paren, number or quote. 

I've done this because I decided to, taking Greg's lead, treat all builtin functions and user-defined functions in the same way. So their names all get packed into a Symbol token.

The parser accepts these tokens and builds up SExpressions with them. An SExpression is an abstract class with three concrete children:

        Number 
        Symbol 
        SList (since 'List' had too many name conflicts) 

Number tokens are turned into Numbers, Symbol tokens into Symbols. SLists are built from the rest. So, a Quote is actually turned into an SList with the first element as the symbol "quote".

Evaluation of all of this is handled by a VirtualMachine. The VirtualMachine has the job of keeping track of variable bindings, scoping and execution of SExpressions and functions (more on functions in a minute). Every SExpression has an evaluate(VirtualMachine) method, and this is what the VM calls to execute an expression.

When a Number is executed it returns itself. When a Symbol is executed it calls VirtualMachine.lookup() which returns an SExpression bound to that symbol, if it exists. If an SExpression is returned then the Symbol returns it, otherwise it throws an exception about trying to evaluate an unbound variable.

When an SList is executed things are a little different. It does a VM.lookup() on the head of the list (which must be a symbol). Here's where I tell you that there are actually four children of SExpression. Function is the fourth. The SList checks that what it got back was a function, and takes this function and calls VM.evaluation(function, this.rest()). where rest() returns a new SList containing everything but the first element in the list.

Now, here's where I tell you about there being two types of Functions, Builtin and UserDefined. Since a Builtin function has unnamed parameters, whereas a user defined function has named ones, I decided to treat them as seperate cases. A builtin function is evaluated by calling function.evaluate(VirtualMachine, SExpression[]) where SExpression[] comes from the SList.rest() SList, and is treated as the arguments to the function.

Calling a UserDefined function involves the VM creating a new Scope and binding each of the UserDefined function's parameters with the arguments, executing the function, and then popping the stack of Scopes afterwards.

So, the upshot of all of this to evaluate *any* SList you have to have a Function bound to the first Symbol in the list. So the first thing the REPL does is bind the Builtin functions to their symbols. I've created a few: Addition, Car, Cdr, Define, Eval, Quote, and Set.

Addition works by just summing the evaluations of each of its arguments (must be at least 2). Quote returns its arguement. Eval returns the evaluation of its first argument. Set calls vm.bind(firstargument, secondargument). Define creates new UserDefined function and binds it to it's first arguemnt (which must be a Symbol). And so on..

It all seems to be working pretty well. And it'll make creating lambda functions a snap (just like Define except you don't bind the function to anything, and just return it).

Some things I'm not totally comfortable with are the fact that each function gets a name (as a Symbol). This might make sense for builtin functions (which have a set name) but for userdefined function it seems dumb because the function *itself* shouldn't know about it's own binding name. Especially because you can assign a function to a new variable.

For instance,

-> (define y () '(happy)) 
          y 
-> y 
          FUNCTION: y = '(happy) 
-> (set x y) 
          FUNCTION: y = '(happy) 
-> x 
          FUNCTION: y = '(happy) 

So, the define function returns the symbol that was just defined. When a UserDefined function prints itself it prints "FUNCTION: <name> = <body>", so that's why you see that when I entered "y" (since y returned the function it was bound too).

The set function returns the function that was just defined (I don't know why, it probably should return the symbol or something).

When I typed "x" I got back the function, but the function's name wasn't updated when I bound it to x. So this whole UserDefinedFunction naming bit is a little screwy.

The other thing that's a little wonky is that the parser only consumes enough tokens to create a single SExpression each time parse() is called. So if you type more than one SExpression on a line, you only get the first one evaluated. But if you enter a blank line after that, then you get the second one evaluated (because the tokenizer tokenizes the entire line). Hence,

-> 'a 'b 
          a 
-> 
          b 

So I'll start wearing my text like any other cloth. And you do your best to flash your eyes sideways quickly.

In the winter
or Autumn,
I generate a hum