« Inches away from the peak | Main | Release 0.36 ( Cardinal ) »
February 23, 2005
At the peak
So the hard work was done: creating a system that executed lists from the inside outwards in a linear way that never uses recursive java methods. How? I use a linear method of evaluation that rewards tail call elimination and lists that refer to themselves.
CX syntax requires the runtime to use an algorithm that isn't commonly used for evaluation. It all starts with the parser, really. My parser produces an AST that doesn't notate function calls and arguments. There is no a(x) in cx, there is only a x , and only if 'a' happens to 'take input' at the time of evaluation, a(x) will happen. This leads to an algorithm I've concluded to , which introduces some new terms to the compiler conversations I take part in. I feel a need to define my algorithm in detail.
The overall sections of CX evaluation are as follows: Syntax is put into the parser, which produces the AST, which is sent to the evaluator and evaluated.
The parser uses a state machine to tokenize the syntax. The state machine also tells the parser when to go 'up stack' and 'down stack'. Up stack is when a '[' or '{' is encountered. The parser pushes a new Quote or List into the parsing stack, and continues to iterate over the text, pushing tokens into this list , using Stack.peek(). When a ']' or '}' is encountered, the state machine reports a 'down stack' which triggers the parser to pop the list from the top of the parsing stack and add it to the top of the stack. Here is a psuedo-code explanation of a 'down stack' operation:
((Collection)parsingStack.peek()).add(parsingStack.pop());
(I stopped writing this because it's better to be put in a manual or something...)
Posted by Rex at February 23, 2005 01:09 PM