Delta

Delta extends Gamma by adding collateral and sequential blocks for commands and expressions.

Delta Syntax

Expression blocks are a type of special form. Command blocks are commands:

<SpecialForm> ::= <ExpressionBlock> | etc.
<Command> ::= <CommandBlock> | etc.

The difference between expression and command blocks is the type of body and the delimiters:

<ExpressionBlock> ::= (<Let> [<Declaration>+] <Expression>)
<CommandBlock> ::= {<Let> [<Declaration>+] <Command>}

The let operator indicates a collateral block, the letseq operator indicates a sequential block:

<Let> ::= let | letseq

Note that declaration blocks aren't needed because:

[let [...] [define x init]]

is equivalent to:

[define x (let [...] init)]

A Delta Session

Here's a sample Delta session:

-> [define a 100]
done

The difference between collateral and sequential blocks:

-> (let [[define a 50] [define b (* 2 a)]] (+ a b))
250 // = (+ 50 200)
-> (letseq [[define a 50] [define b (* 2 a)]] (+ a b))
150 // = (+ 50 100)

Declaration blocks aren't necessary:

-> [define b (let [[define x (* 2 a)]] (var (+ x x x)))]
done
-> b
var<600>

Command blocks:

-> {let [[define y (/ a 2)]] {assign b (+ (val b) y y)}}
ok
-> b
var<700>

Nesting blocks:

-> (let [[define x 10]] (let [[define y x]] (+ x y)))
20
-> (let [[define y (let [[define a 10]] (+ a a))]] (+ a y))
120

Delta Semantics

A Delta environment is actually a linked list of environments. The lists are linked through both the callEnv and defEnv fields, although we will only use the defEnv field for now. The global environment, the one created by the default constructor, is always the last environment in the list. It's calling and defining environments are null:

Add a ready flag to the Environment class. Modify the get method so that it searches the defining environment if the flag is set to false or if the search fails:

class Environment extends Frame {
private boolean ready = true;
private Environment defEnv, callEnv;
public Environment(Environment defEnv, Environment callEnv) {
this.defEnv = defEnv;
this.callEnv = callEnv;
}
public Environment(Environment defEnv) {
this(defEnv, defEnv);
}
public Value get(Symbol sym) {
1. if (ready) result = super.get(sym);
2. if (defEnv != null && (!ready || result == null))
result = defEnv.get(sym)
}
// etc.
}

You must add two new classes to the Phrase hierarchy: ExpressionBlock and CommandBlock. Both are very similar. Both have a static isNext method and three fields that must be initialized by the static parse method:

class CommandBlock extends Command {
private String operator; // let or letseq
private List<Declaration> localDecs;
private Command body; // Expression in ExpressionBlock
// etc.
}

The evaluator creates a temporary extension of the environment parameter. Bindings created by the local declarations (called local bindings) are dumped into the extension. The body is recursively evaluated relative to the temporary environment:

Value eval(Environment env) throws AppError {
1. create tempEnv extending env
2. if (operator is "let") tempEnv.ready = false
3. eval local decs in tempEnv
4. tempEnv.ready = true
5. eval body in tempEnv
}

Note that the tempEnv is local to eval. Once eval terminates, there will be no way to access tempEnv. It will become garbage and will eventually be recycled by the garbage collector.

This mechanism can be compared to the call stack mechanism used by other languages. In C, for example, when a block is entered a new frame is pushed onto the call stack. The phrases in the block (which can be declarations, commands, or expressions) are evaluated relative to this new frame. For example, the binding produced by a local declaration will be placed in the top-most frame on the stack. When a symbol is encountered, the top-most stack frame is searched. If the search fails, the next frame on the stack is searched. This continues until the bottom-most frame is searched. This is the frame associated with the call to main. If that search fails, the static memory segment is searched. This is the area where bindings created by global or static declarations are placed. It corresponds to our global environment. When the block exits, the top-most frame is popped off the stack. This corresponds to tempEnv going out of scope and eventually getting recycled.