Thursday, February 05, 2004
So how might I implement the stack-based evaluation? Well...
So assume for now that we'll stick with the existing hierarchy:
Let's follow along as the different types of S-Expressions get evaluated.
Inside the REPL we have something like this:
Example:
-> 123
this is parsed into a Number.
-> +
this is parsed into a Symbol.
-> '+
this is parsed into a SList: (quote +)
that is, an SList which contains the Symbol 'quote', followed by the symbol '+'.
-> (+ 2 3)
Representation and implementation
So assume for now that we'll stick with the existing hierarchy:
SExpression
Symbol
Number
SList
Function
to represent scheme s-expressions in memory. Assume also that we have a way of building these up from a string representation.
Let's follow along as the different types of S-Expressions get evaluated.
Inside the REPL we have something like this:
SExpression expression = parser.getNextExpression();
SExpression result = virtualMachine.getReturnValue(expression);
System.out.println(result.toString);
getReturnValue() is
expressionStack.push(expression);
evaluate();
return returnValueStack.pop();
evaluate() is
while(expressionStack.isNotEmpty())
expressionStack.pop().evaluate(this);
So that handles the general stuff, in specific:
Example:
-> 123
this is parsed into a Number.
Number.evaluate(VirtualMachine)
virtualMachine.returnValueStack.push(this);
Example:-> +
this is parsed into a Symbol.
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)
Example:-> '+
this is parsed into a SList: (quote +)
that is, an SList which contains the Symbol 'quote', followed by the 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);
Example:-> (+ 2 3)
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);
0 Comments:
