The implementation notes document the JavaScript file /system/core.js, which implements the “core” of the EVLambda programming language and the EVL to XML converter (one of the two components of the documentation generator, the other one being the XSLT stylesheet). The implementation notes and the JavaScript file have the same organization (the same sections, in the same order) and are meant to be read side by side.
The JavaScript file implements five interpreter-based evaluators:
Only the trampoline and trampoline++ evaluators allow unbounded iterations through tail-recursive calls. The other evaluators are only useful as stepping stones to understand the trampoline and trampoline++ evaluators. The trampoline++ evaluator is an optimized version of the trampoline evaluator.
The JavaScript file can run inside the IDE (actually inside a web worker started from the IDE) or inside a Node.js runtime environment started from the command line.
Here are quick links to the sections:
errornonlocal-exitobjectvoidbooleannumbercharacterstringsymbolkeywordvariablelistempty-listconsvectorfunctionprimitive-functionclosureThe constant isRunningInsideNode is true if the JavaScript file is running inside a Node.js runtime environment and false otherwise.
The variable abortSignalArray contains a shared array used by the IDE to abort the current evaluation without terminating the web worker.
The variable selectedEvaluator contains the name of the selected evaluator.
The constant optimizeMacroCalls controls whether or not the macro expansions should be burned into the code.
This section implements the interface used by the IDE to control the evaluator and the EVL to XML converter.
The evaluator and the EVL to XML converter are running inside a web worker because running them directly inside the main thread would make the GUI unresponsive when they are running.
The main thread and the web worker thread communicate through messages and shared arrays.
The request messages sent by the main thread to the web worker thread are objects containing the following properties:
id (required): A unique integer id used to pair responses with requests.action (required): An integer specifying the requested action.input (optional): Some data.The response messages sent by the web worker thread to the main thread are objects containing the following properties:
id (required): A unique integer id used to pair responses with requests.status (required): An integer specifying the status of the processing of the requested action.output (optional): Some data.When the processing of the requested action fails because of an error, the response message contains the following properties:
id: A unique integer id used to pair responses with requests.status: The value of the constant ERROR.output: An error message.When the processing of the requested action fails because of the abortion of an evaluation, the response message contains the following properties:
id: A unique integer id used to pair responses with requests.status: The value of the constant ABORTED.The following sections describe the messages currently implemented. The response messages ERROR and ABORTED are omitted from the descriptions. The property id is omitted from the descriptions.
INITIALIZEThis message is used to request the initialization of the web worker.
Request message:
action: The value of the constant INITIALIZE.input: An object containing the following properties:
abortSignalBuffer: The shared buffer underlying the shared array.selectedEvaluator: The name of the selected evaluator.evlFiles: The contents of some EVLambda source files to load.Response message when the processing of the requested action succeeds:
status: The value of the constant SUCCESS.output: An array containing either the printable representations of the values of the last form of the last EVLambda source file or the printable representation #v if the EVLambda source files do not contain any forms.EVALUATE_FIRST_FORMThis message is used to request the evaluation of the first top-level form contained inside some input string.
Request message:
action: The value of the constant EVALUATE_FIRST_FORM.input: The input string.Response message when the processing of the requested action fails because the input string does not contain any forms:
status: The value of the constant FOUND_NO_FORM.Response message when the processing of the requested action succeeds:
status: The value of the constant SUCCESS.output: An array containing the printable representations of the values of the first top-level form contained inside the input string.EVALUATE_ALL_FORMSThis message is used to request the evaluation of the top-level forms contained inside some input string.
Request message:
action: The value of the constant EVALUATE_ALL_FORMS.input: The input string.Response message when the processing of the requested action succeeds:
status: The value of the constant SUCCESS.output: An array containing either the printable representations of the values of the last form contained inside the input string or the printable representation #v if the input string does not contain any forms.CONVERT_EVL_TO_XMLThis message is used to request the conversion of some input string from EVL to XML.
Request message:
action: The value of the constant CONVERT_EVL_TO_XML.input: The input string.Response message when the processing of the requested action succeeds:
status: The value of the constant SUCCESS.output: A string containing the result of the conversion.abortSignalArrayThe shared array contained in the variable abortSignalArray is used by the IDE to abort the current evaluation without terminating the web worker. The shared array contains one boolean flag represented by an $8$-bit unsigned integer. The IDE requests the abortion of the current evaluation by setting the flag to true. The trampoline and trampoline++ evaluators implement the abort-evaluation functionality by regularly checking the value of the flag. The other evaluators do not implement the abort-evaluation functionality.
This section defines some custom error types.
For the most part, the tokenizer is implemented as described in the reference manual. The main difference is that the tokens are produced on demand instead of all at once before the parsing begins.
On each invocation, the tokenizer sets the following properties:
whitespace: The run of whitespace preceding the lexeme associated with the next token.lexeme: The lexeme associated with the next token.category: The category of the next token.value: The value of the next token or null if the next token has no value.The reader is a recursive descent parser getting its tokens from the tokenizer.
The read-time conditionalization facility is integrated into the reader.
The central function is the function readObject, which returns one of the following:
DOT.CLOSING_PARENTHESIS.XML_END_TAG.EOI.The function readObject treats XML elements as comments and skips them. However, the objects contained inside XML elements are not completely invisible because a callback can be attached to the tokenizer that will be invoked on each object encountered while skipping XML elements.
Most of the other functions invoke the function readObject and use a switch statement to decide what to do depending on the result of the invocation.
The main function is the function read, which invokes the function readObject and, depending on the result of the invocation, does one of the following:
readObject returns the next object, then the function read returns that object.readObject returns DOT, CLOSING_PARENTHESIS, or XML_END_TAG, then the function read throws an exception.readObject returns EOI, then the function read returns null to signal the invoker that the end of the input has been reached.In order to evaluate the top-level forms contained inside an EVLambda source file, the function read is invoked in a loop. If the function read returns an object, then that object is evaluated and the loop continues. If the function read returns null, then the loop terminates.
When the source file is a plain EVLambda source file, the function read returns each top-level form in turn and all top-level forms get evaluated.
When the source file is a documented EVLambda source file, the first invocation of the function read returns null (because the chapter element is treated as a comment and skipped) and nothing seems to get evaluated. Actually, this is not the case because a callback is attached to the tokenizer that will evaluate each object encountered while skipping the chapter element.
The job of the EVL to XML converter is to produce an output identical to the input except that (1) the characters less-than, greater-than, and ampersand occurring inside the code have been escaped and (2) some tags have been added to better delimit the code from the surrounding documentation and the comments from the surrounding code.
The EVL to XML converter uses the following context-free grammar to model the input:
| $\metavar{input}$ | $\Coloneq$ | beginning-of-input {$\metavar{top-level-whitespace}$ $\metavar{construct}$}* $\metavar{top-level-whitespace}$ end-of-input |
| $\metavar{construct}$ | $\Coloneq$ | $\metavar{xml-construct}$ | $\metavar{evl-construct}$ |
| $\metavar{xml-construct}$ | $\Coloneq$ | xml-start-tag {$\metavar{xml-whitespace}$ $\metavar{construct}$}* $\metavar{xml-whitespace}$ xml-end-tag | xml-empty-element-tag | xml-comment |
| $\metavar{evl-construct}$ | $\Coloneq$ | void | boolean | number | hash-string-construct | string | keyword | variable | quote | quasiquote | unquote | unquote-splicing | hash-plus | hash-minus | dot | {left-parenthesis | hash-left-parenthesis} {$\metavar{evl-whitespace}$ $\metavar{construct}$}* $\metavar{evl-whitespace}$ right-parenthesis |
The main differences between the context-free grammar used by the EVL to XML converter and the context-free grammar used by the parser are the following:
The tags are always added before or after a run of whitespace. The converter considers each of the runs of whitespace contained inside the input and, for each of them, decides what to do depending on the following:
beginning-of-input, an XML token, or an EVL token.end-of-input, an XML token, or an EVL token.The XML tokens are the following tokens: xml-start-tag, xml-end-tag, xml-empty-element-tag, and xml-comment.
The EVL tokens are the end-of-line and end-of-last-line comments (which are treated as a unit) and the following tokens: void, boolean, number, hash-string-construct, string, keyword, variable, quote, quasiquote, unquote, unquote-splicing, hash-plus, hash-minus, dot, left-parenthesis, hash-left-parenthesis, and right-parenthesis.
The end-of-line and end-of-last-line comments are treated as EVL tokens because they are not delimited from the surrounding code by additional tags.
Tags are never added before or after the runs of whitespace occurring in top-level context.
The runs of whitespace occurring in XML context are processed as follows:
$\metavar{xmltok}$$\metavar{ws}$$\metavar{evltok}$ is transformed into$\metavar{xmltok}$$\metavar{ws}$<toplevelcode><blockcode>$\metavar{evltok}$$\metavar{evltok}$$\metavar{ws}$$\metavar{evltok}$, where $\metavar{ws}$ contains at least one blank line, is transformed into$\metavar{evltok}$</blockcode></toplevelcode>$\metavar{ws}$<toplevelcode><blockcode>$\metavar{evltok}$$\metavar{evltok}$$\metavar{ws}$$\metavar{evltok}$, where $\metavar{ws}$ contains no blank lines, is transformed into$\metavar{evltok}$$\metavar{ws}$$\metavar{evltok}$$\metavar{evltok}$$\metavar{ws}$$\metavar{xmltok}$ is transformed into$\metavar{evltok}$</toplevelcode></blockcode>$\metavar{ws}$$\metavar{xmltok}$$\metavar{xmltok}$$\metavar{ws}$$\metavar{xmltok}$ is transformed into$\metavar{xmltok}$$\metavar{ws}$$\metavar{xmltok}$The runs of whitespace occurring in EVL context are processed as follows:
$\metavar{evltok}$$\metavar{ws}$$\metavar{xmltok}$ is transformed into$\metavar{evltok}$</blockcode><indentation style="…"><blockcomment>$\metavar{ws}$$\metavar{xmltok}$$\metavar{xmltok}$$\metavar{ws}$$\metavar{xmltok}$ is transformed into$\metavar{xmltok}$$\metavar{ws}$$\metavar{xmltok}$$\metavar{xmltok}$$\metavar{ws}$$\metavar{evltok}$ is transformed into$\metavar{xmltok}$</blockcomment></indentation><blockcode>$\metavar{ws}$$\metavar{evltok}$$\metavar{evltok}$$\metavar{ws}$$\metavar{evltok}$ is transformed into$\metavar{evltok}$$\metavar{ws}$$\metavar{evltok}$The analysis of a form does not entail the analysis of the direct subforms of the form or, if the form is a lambda abstraction, the analysis of the body of the form. In all evaluators except the trampoline++ evaluator, the direct subforms and the bodies are analyzed if and when they are evaluated. In the trampoline++ evaluator, a top-level form is fully analyzed during the preprocessing phase.
The first part of the analysis is done by the evaluators themselves by checking whether the form is the empty list, a cons, a variable, or something else and, if the form is a cons, by checking whether the car of the cons is a special operator or something else.
The scope-extent combinations are identified using the members of the following enumeration:
LEX_SCOPE: lexical scope and indefinite extent (= lexical environment)DYN_SCOPE: indefinite scope and dynamic extent (= dynamic environment)The namespaces are identified using the members of the following enumeration:
VAL_NS: value namespaceFUN_NS: function namespaceBLK_NS: block namespaceXIT_NS: exit-point namespaceBecause the global environment is unique, any given variable can have, at any given time, at most one global binding in the value namespace and one global binding in the function namespace. An obvious way to implement the global environment is thus to store the global bindings for a variable directly on the JavaScript object representing the variable.
Variables are represented by instances of the class EVLVariable. The property value of the instance representing a variable contains the value of the binding for the variable in the value namespace of the global environment if that binding exists and null otherwise. The property function of the instance representing a variable contains the value of the binding for the variable in the function namespace of the global environment if that binding exists and null otherwise.
The user manual specifies the lexical and dynamic environments as follows:
The reference manual introduces two new namespaces: the block namespace and the exit-point namespace.
In actuality, a lexical or dynamic environment is represented not by the result of the sequence of extensions leading to the environment but by a recording of the sequence of extensions leading to the environment. A single extension is recorded into a data structure called a frame and a sequence of extensions is recorded into a chain of frames.
Let $\env$ be a lexical or dynamic environment and$$[(\ns_1,[\var_{1,1},\ldots,\var_{1,m_1}],[\obj_{1,1},\ldots,\obj_{1,m_1}]),\ldots,(\ns_n,[\var_{n,1},\ldots,\var_{n,m_n}],[\obj_{n,1},\ldots,\obj_{n,m_n}])]$$be the sequence of extensions leading to the environment. The extensions are applied from left to right and the first extension is applied to an empty environment. The $i$-th extension$$(\ns_i,[\var_{i,1},\ldots,\var_{i,m_i}],[\obj_{i,1},\ldots,\obj_{i,m_i}])$$extends the previous environment by binding, in the namespace $\ns_i$, the variable $\var_{i,j}$ to the object $\obj_{i,j}$ (for all $i$ from $1$ to $n$ and all $j$ from $1$ to $m_i$). We will denote by $\binding(i,j)$ the binding between $\var_{i,j}$ and $\obj_{i,j}$ created by the $i$-th extension.
The binding for the variable $\var$ in the namespace $\ns$ of the environment $\env$ can easily be located using the following lookup procedure:
Initialize $i$ to $n$. Loop: If $i=0$, then the variable $\var$ in unbound in the namespace $\ns$ of the environment $\env$. Otherwise, if $\ns_i=\ns$ and there exists $j\in\{1,\ldots,m_i\}$ such that $\var_{i,j}=\var$ (if such $j$ exists, it is necessarily unique because the variables $\var_{i,1},\ldots,\var_{i,m_i}$ are distinct), then $\binding(i,j)$ is the binding for the variable $\var$ in the namespace $\ns$ of the environment $\env$. Otherwise, decrement $i$ by $1$ and loop.
By selecting the greatest $i$ satisfying the conditions, the lookup procedure correctly handles the possibility of shadowing of a binding by another binding.
Lexical and dynamic environments are represented by instances of the classes Frame and NullDefiniteEnv, which are the two concrete subclasses of the abstract class DefiniteEnv.
For the sake of this document, lexical and dynamic environments are called definite because their scope or their extent is definite. The bindings of a lexical environment have lexical, and thus definite, scope. The bindings of a dynamic environment have dynamic, and thus definite, extent. By contrast, the bindings of the global environment have indefinite scope and indefinite extent.
Instances of Frame, which represent single extensions, have four properties:
namespace: VAL_NS, FUN_NS, BLK_NS, or XIT_NSvariables: an array of distinct variablesvalues: an array of objectsnext: an instance of Frame or NullDefiniteEnvThe two arrays variables and values must have the same length $m\ge0$. The array variables contains the variables $\var_1,\ldots,\var_m$ and the array values contains the objects $\obj_1,\ldots,\obj_m$. The property next is used to create chains of instances of Frame. Each chain is terminated by an instance of NullDefiniteEnv, which represents an empty environment.
The parameters are paired with the arguments by the following functions:
| Function | Function call | Rest parameter |
|---|---|---|
pairPrimFunParametersNoApply | plain function call multiple-value-call-form | N/A |
pairPrimFunParametersApply | apply multiple-value-apply-form | N/A |
pairClosureParametersNoApplyNoRest | plain function call multiple-value-call-form | no |
pairClosureParametersNoApplyRest | plain function call multiple-value-call-form | yes |
pairClosureParametersApplyNoRest | apply multiple-value-apply-form | no |
pairClosureParametersApplyRest | apply multiple-value-apply-form | yes |
The function pairClosureParametersApplyRest reuses conses from the last element of the spreadable sequence of objects when possible. To illustrate, let us consider the following function calls:
(apply (_vlambda a (list a)) $x=\code{1}$ $y=\code{2}$ $z=\code{'(3 4)}$)a is paired with (cons $x$ (cons $y$ $z$))$\,=\,$(1 2 3 4) ($2$ new conses and $2$ reused conses)(apply (_vlambda (a . b) (list a b)) $x=\code{1}$ $y=\code{2}$ $z=\code{'(3 4)}$)a is paired with $x$$\,=\,$1b is paired with (cons $y$ $z$)$\,=\,$(2 3 4) ($1$ new cons and $2$ reused conses)(apply (_vlambda (a b . c) (list a b c)) $x=\code{1}$ $y=\code{2}$ $z=\code{'(3 4)}$)a is paired with $x$$\,=\,$1b is paired with $y$$\,=\,$2c is paired with $z$$\,=\,$(3 4) ($0$ new conses and $2$ reused conses)(apply (_vlambda (a b c . d) (list a b c d)) $x=\code{1}$ $y=\code{2}$ $z=\code{'(3 4)}$)a is paired with $x$$\,=\,$1b is paired with $y$$\,=\,$2c is paired with (car $z$)$\,=\,$3d is paired with (cdr $z$)$\,=\,$(4) ($0$ new conses and $1$ reused cons)(apply (_vlambda (a b c d . e) (list a b c d e)) $x=\code{1}$ $y=\code{2}$ $z=\code{'(3 4)}$)a is paired with $x$$\,=\,$1b is paired with $y$$\,=\,$2c is paired with (car $z$)$\,=\,$3d is paired with (car (cdr $z$))$\,=\,$4e is paired with (cdr (cdr $z$))$\,=\,$() ($0$ new conses and $0$ reused conses)(apply (_vlambda (a b c d e . f) (list a b c d e f)) $x=\code{1}$ $y=\code{2}$ $z=\code{'(3 4)}$)The generic evaluator simply dispatches the form to evaluate to the selected evaluator.
Defining a primitive function is a two-step process. First, the function primitiveFunction is used to add to the Map contained in the variable primitiveFunctions an entry mapping the name of the primitive function to a record containing the minimum number of arguments, the maximum number of arguments, and the JavaScript function implementing the primitive function. Then, a binding between the name of the primitive function and an instance of the class EVLPrimitiveFunction is added to the function namespace of the global environment.
The first step occurs where it makes the most sense. For the primitive functions related to a primitive date type, the first step occurs inside the section defining the class representing the primitive data type.
The second step is postponed to the section Primitive Function Definitions (Second Steps) because it cannot happen before the class EVLPrimitiveFunction has been defined.
The actual number of arguments is checked against the minimum and maximum numbers of arguments by the code implementing the invocation of primitive functions.
The types of the arguments are checked by the JavaScript functions implementing the primitive functions.
A bounce is what is sent back to the trampoline. A bounce is either an evaluation request or an outcome.
An evaluation request specifies a form to evaluate and the lexical environment with respect to which the form is to be evaluated. The dynamic environment with respect to which the form is to be evaluated is always the current dynamic environment. An evaluation request is represented by an instance of the class EvalReq.
An outcome is either an abrupt completion or the result of a normal completion.
An abrupt completion is either an abrupt completion of type error or an abrupt completion of type nonlocal-exit.
errorAn abrupt completion of type error is represented by an instance of the class EVLError.
nonlocal-exitAn abrupt completion of type nonlocal-exit is represented by an instance of the class NonlocalExit.
The result of a normal completion is represented by an instance of the class EVLObjects (when the result consists of zero or more than one object) or by an instance of a concrete subclass of the abstract class EVLObject (when the result consists of exactly one object).
A result consisting of zero or more than one object is represented by an instance of the class EVLOjects.
The method primaryValue returns #v if the result consists of zero objects and the first object otherwise.
The method allValues returns an array containing the objects composing the result.
objectThe abstract class EVLObject represents the primitive data type object.
An instance of a concrete subclass of the abstract class EVLObject can represent one of two things: an object or a result consisting of a single object.
The method primaryValue returns the single object.
The method allValues returns an array containing the single object.
The method eql implements the default behavior of the equality predicate eql? (that is, pointer equality). The method is overridden in the classes EVLNumber, EVLCharacter, and EVLString.
The default implementation of the method toString is overridden in some subclasses to return the printable representation of this.
voidAn object of type void is represented by a instance of the class EVLVoid.
booleanAn object of type boolean is represented by a instance of the class EVLBoolean.
numberAn object of type number is represented by a instance of the class EVLNumber.
characterAn object of type character is represented by a instance of the class EVLCharacter.
stringAn object of type string is represented by a instance of the class EVLString.
symbolThe abstract class EVLSymbol represents the primitive data type symbol.
keywordAn object of type keyword is represented by a instance of the class EVLKeyword.
variableAn object of type variable is represented by a instance of the class EVLVariable.
listThe abstract class EVLList represents the primitive data type list.
empty-listAn object of type empty-list is represented by a instance of the class EVLEmptyList.
consAn object of type cons is represented by a instance of the class EVLCons.
vectorAn object of type vector is represented by a instance of the class EVLVector.
functionThe abstract class EVLFunction represents the primitive data type function.
primitive-functionAn object of type primitive-function is represented by a instance of the class EVLPrimitiveFunction.
closureAn object of type closure is represented by a instance of the class EVLClosure.
This section implements the primitive functions values, error, and now.
The second steps of the primitive function definitions all occur in this section.
This section creates and interns the objects of type variable naming the special operators, the boolean operators (which can occur in feature expressions), and the macro mlet (which is handled directly by the trampoline++ evaluator).
This section implements the command-line interface used to control the evaluator and the EVL to XML converter.
The syntax of the command line to control the evaluator is as follows:
node core.js { --directstyle | --cps | --oocps | --sboocps | --trampoline | --trampoliepp }? { -l $\metavar{file}$ | -e $\metavar{form}$ }*The options and arguments have the following meanings:
--directstyle: selects the direct style evaluator--cps: selects the continuation passing style evaluator--oocps: selects the object-oriented CPS evaluator--sboocps: selects the stack-based object-oriented CPS evaluator--trampoline: selects the trampoline evaluator--trampolinepp: selects the trampoline++ evaluator (DEFAULT)-l $\metavar{file}$: loads the EVL file-e $\metavar{form}$: evaluates the formThe syntax of the command line to control the EVL to XML converter is as follows:
node core.js --convert $\metavar{file}$The options and arguments have the following meanings:
--convert $\metavar{file}$: converts the EVL file to XML