Programmers write programs as text, i.e. sequences of characters, entered in a programming environment or a text editor. To run our evaluator, we need to start with a representation of this program text as a JavaScript value. In section 2.3.1 we introduced strings to represent text. We would like to evaluate programs such as "const size = 2; 5 * size;" from section 1.1.2. Unfortunately, such program text does not provide enough structure to the evaluator. In this example, the program parts "size = 2" and "5 * size" look similar, but carry very different meanings. Abstract syntax functions such as declaration_value_expression would be difficult and error-prone to implement by examining the program text. In this section, we therefore introduce a function parse that translates program text to a tagged-list representation, reminiscent of the tagged data of section 2.4.2. For example, the application of parse to the program string above produces a data structure that reflects the structure of the program: a sequence consisting of a constant declaration associating the name size with the value 2 and a multiplication. parse("const size = 2; 5 * size;"); list("sequence", list(list("constant_declaration", list("name", "size"), list("literal", 2)), list("binary_operator_combination", "*", list("literal", 5), list("name", "size")))) The syntax functions used by the evaluator access the tagged-list representation produced by parse.

Figure 4.3 Syntax abstraction in the evaluator.

Figure 4.3 depicts the abstraction barrier formed by the syntax predicates and selectors, which interface the evaluator to the tagged-list representation of programs, which in turn is separated from the string representation by parse. Below we describe the parsing of program components and list the corresponding syntax predicates and selectors, as well as constructors if they are needed.

Here is the specification of the syntax of our language:

• The only self-evaluating items are numbers and strings: (define (self-evaluating? exp) (cond ((number? exp) true) ((string? exp) true) ((null? exp) true) (else false)))
• Variables are represented by symbols: (define (variable? exp) (symbol? exp))
• Quotations have the form (quote text-of-quotation) :[1] (define (quoted? exp) (tagged-list? exp 'quote)) (define (text-of-quotation exp) (cadr exp)) Quoted? is defined in terms of the procedure tagged-list?, which identifies lists beginning with a designated symbol: (define (tagged-list? exp tag) (if (pair? exp) (eq? (car exp) tag) false))
• Assignments have the form (set! var value): (define (assignment? exp) (tagged-list? exp 'set!)) (define (assignment-variable exp) (cadr exp)) (define (assignment-value exp) (caddr exp))
• Definitions have the form (define var value) or the form (define (var parameter$_{1}$ $\ldots$ parameter$_{n}$) body) The latter form (standard procedure definition) is syntactic sugar for (define var (lambda (parameter$_{1}$ $\ldots$ parameter$_{n}$) body)) The corresponding syntax procedures are the following: (define (definition? exp) (tagged-list? exp 'define)) (define (definition-variable exp) (if (symbol? (cadr exp)) (cadr exp) (caadr exp))) (define (definition-value exp) (if (symbol? (cadr exp)) (caddr exp) (make-lambda (cdadr exp) (cddr exp))))
• Lambda expressions are lists that begin with the symbol lambda: (define (lambda? exp) (tagged-list? exp 'lambda)) (define (lambda-parameters exp) (cadr exp)) (define (lambda-body exp) (cddr exp)) (define (make-lambda parameters body) (cons 'lambda (cons parameters body))) We also provide a constructor for lambda expressions, which is used by definition-value, above: (define (make-lambda parameters body) (cons 'lambda (cons parameters body)))
• Conditionals begin with if and have a predicate, a consequent, and an (optional) alternative. If the expression has no alternative part, we provide false as the alternative.[2] (define (if? exp) (tagged-list? exp 'if)) (define (if-predicate exp) (cadr exp)) (define (if-consequent exp) (caddr exp)) (define (if-alternative exp) (if (not (null? (cdddr exp))) (cadddr exp) 'false)) (define (make-if predicate consequent alternative) (list 'if predicate consequent alternative)) We also provide a constructor for if expressions, to be used by cond->if to transform cond expressions into if expressions: (define (make-if predicate consequent alternative) (list 'if predicate consequent alternative))
• Begin packages a sequence of expressions into a single expression. We include syntax operations on begin expressions to extract the actual sequence from the begin expression, as well as selectors that return the first expression and the rest of the expressions in the sequence.[3] (define (begin? exp) (tagged-list? exp 'begin)) (define (begin-actions exp) (cdr exp)) (define (last-exp? seq) (null? (cdr seq))) (define (first-exp seq) (car seq)) (define (rest-exps seq) (cdr seq)) We also include a constructor sequence->exp (for use by cond->if) that transforms a sequence into a single expression, using begin if necessary: (define (sequence->exp seq) (cond ((null? seq) seq) ((last-exp? seq) (first-exp seq)) (else (make-begin seq)))) (define (make-begin seq) (cons 'begin seq))
• A procedure application is any compound expression that is not one of the above expression types. The car of the expression is the operator, and the cdr is the list of operands: (define (application? exp) (pair? exp)) (define (operator exp) (car exp)) (define (operands exp) (cdr exp)) (define (no-operands? ops) (null? ops)) (define (first-operand ops) (car ops)) (define (rest-operands ops) (cdr ops))

Literal expression

Literal expressions are parsed into tagged lists with tag "literal" and the actual value. \[ \begin{align*} \ll\ \mathit{literal}\textit{-}\mathit{expression}\ \gg & = \texttt{list("literal", }\mathit{value}\texttt{)} \end{align*} \] where $value$ is the JavaScript value represented by the $literal$-$expression$ string. Here $\ll\ $$literal$-$expression$$\ \gg$ denotes the result of parsing the string $literal$-$expression$. parse("1;"); list("literal", 1) parse("'hello world';"); list("literal", "hello world") parse("null;"); list("literal", null) The syntax predicate for literal expressions is is_literal. function is_literal(component) { return is_tagged_list(component, "literal"); } It is defined in terms of the function is_tagged_list, which identifies lists that begin with a designated string: function is_tagged_list(component, the_tag) { return is_pair(component) && head(component) === the_tag; } The second element of the list that results from parsing a literal expression is its actual JavaScript value. The selector for retrieving the value is literal_value. function literal_value(component) { return head(tail(component)); } literal_value(parse("null;")); null In the rest of this section, we just list the syntax predicates and selectors, and omit their declarations if they just access the obvious list elements.

We provide a constructor for literals, which will come in handy: function make_literal(value) { return list("literal", value); }

Names

The tagged-list representation for names includes the tag "name" as first element and the string representing the name as second element. \[ \begin{align*} \ll\ \mathit{name}\ \gg & = \texttt{list("name", }\mathit{symbol}\texttt{)} \end{align*} \] where $symbol$ is a string that contains the characters that make up the $name$ as written in the program. The syntax predicate for names is is_name. The symbol is accessed using the selector symbol_of_name. We provide a constructor for names, to be used by operator_combination_to_application: function make_name(symbol) { return list("name", symbol); }

Expression statements

We do not need to distinguish between expressions and expression statements. Consequently, parse can ignore the difference between the two kinds of components: \[ \ll\ \mathit{expression}\texttt{;}\ \gg {=} \ll\ \mathit{expression}\ \gg \]

Function applications

Function applications are parsed as follows: \[ \ll\ \mathit{fun}\textit{-}\mathit{expr}\texttt{(}\mathit{arg}\textit{-}\mathit{expr}_1\texttt{, }\ldots\texttt{, } \mathit{arg}\textit{-}\mathit{expr}_n \texttt{)}\ \gg \\ = \\ \texttt{list("application",} \ll\ \mathit{fun}\textit{-}\mathit{expr}\gg\texttt{, list(} \ll\ \mathit{arg}\textit{-}\mathit{expr}_1\;\gg \texttt{, }\ldots\texttt{, } \ll\ \mathit{arg}\textit{-}\mathit{expr}_n\;\gg \texttt{))} \] We declare is_application as the syntax predicate and function_expression and arg_expressions as the selectors. We add a constructor for function applications, to be used by operator_combination_to_application: function make_application(function_expression, argument_expressions) { return list("application", function_expression, argument_expressions); }

Conditionals

Conditional expressions are parsed as follows:

$\ll\ \mathit{predicate}\ \texttt{?}\ \mathit{consequent}\textit{-}\mathit{expression}\ \texttt{:}\ \mathit{alternative}\textit{-}\mathit{expression}\ \gg\ \ = $ list("conditional_expression", $\ll\ $$predicate$$\ \gg$, $\ll\ $$consequent$-$expression$$\ \gg$, $\ll\ $$alternative$-$expression$$\ \gg$)

Similarly, conditional statements are parsed as follows:

$\ll\ \textbf{if}\ \texttt{(} \mathit{predicate} \texttt{)}\ \mathit{consequent}\textit{-}\mathit{block}\ \textbf{else}\ \mathit{alternative}\textit{-}\mathit{block}\ \gg\ \ =$ list("conditional_statement", $\ll\ $$predicate$$\ \gg$, $\ll\ $$consequent$-$block$$\ \gg$, $\ll\ $$alternative$-$block$$\ \gg$)

The syntax predicate is_conditional returns true for both kinds of conditionals, and the selectors conditional_predicate, conditional_consequent, and conditional_alternative can be applied to both kinds.

Lambda expressions

A lambda expression whose body is an expression is parsed as if the body consisted of a block containing a single return statement whose return expression is the body of the lambda expression. \[ \ll\ \texttt{(}\mathit{name}_1\texttt{, }\ldots\texttt{, } \mathit{name}_n \texttt{) =>}\ \mathit{expression}\ \gg \\ = \\ \ll\ \texttt{(}\mathit{name}_1\texttt{, }\ldots\texttt{, } \mathit{name}_n \texttt{) => \{}\ \textbf{return} \ \mathit{expression}\texttt{;}\ \texttt{\}}\ \gg \] A lambda expression whose body is a block is parsed as follows:

$\ll\ \texttt{(}\mathit{name}_1\texttt{, }\ldots\texttt{, } \mathit{name}_n \texttt{) =>}\ \mathit{block}\ \gg\ \ =$ list("lambda_expression", list($\ll\ name_1\;\gg$, $\ldots$, $\ll\ name_n\;\gg$), $\ll\ block\ \gg$)

The syntax predicate is is_lambda_expression and the selector for the body of the lambda expression is lambda_body. The selector for the parameters, called lambda_parameter_symbols, additionally extracts the symbols from the names. function lambda_parameter_symbols(component) { return map(symbol_of_name, head(tail(component))); } The function function_decl_to_constant_decl needs a constructor for lambda expressions: function make_lambda_expression(parameters, body) { return list("lambda_expression", parameters, body); }

Sequences

A sequence statement packages a sequence of statements into a single statement. A sequence of statements is parsed as follows: \[ \ll\ \mathit{statement}_1 \cdots \mathit{statement}_n\;\gg \\ = \\ \texttt{list("sequence", list(} \ll\ \mathit{statement}_1\;\gg \texttt{, } \ldots \texttt{, } \ll\ \mathit{statement}_n\;\gg \texttt{))} \] The syntax predicate is is_sequence and the selector is sequence_statements. We retrieve the first of a list of statements using first_statement and the remaining statements using rest_statements. We test whether the list is empty using the predicate is_empty_sequence and whether it contains only one element using the predicate is_last_statement.[4] function first_statement(stmts) { return head(stmts); } function rest_statements(stmts) { return tail(stmts); } function is_empty_sequence(stmts) { return is_null(stmts); } function is_last_statement(stmts) { return is_null(tail(stmts)); }

Blocks

Blocks are parsed as follows:[5] \[ \begin{align*} \ll\ \texttt{\{}\ \mathit{statements}\ \texttt{\}}\ \gg & = \texttt{list("block",}\ \ll\ \mathit{statements}\ \gg \texttt{)} \end{align*} \] Here $statements$ refers to a sequence of statements, as shown above. The syntax predicate is is_block and the selector is block_body.

Return statements

Return statements are parsed as follows: \[ \begin{align*} \ll\ \textbf{return}\ \mathit{expression} \texttt{;}\ \gg & = \texttt{list("return\_statement",}\ \ll\ \mathit{expression}\ \gg \texttt{)} \end{align*} \] The syntax predicate and selector are, respectively, is_return_statement and return_expression.

Assignments

Assignments are parsed as follows: \[ \begin{align*} \ll\ \mathit{name}\ \ \texttt{=}\ \ \mathit{expression}\ \gg & = \texttt{list("assignment", }\ll\ \mathit{name}\gg \texttt{, }\ll\ \mathit{expression}\ \gg \texttt{)} \end{align*} \] The syntax predicate is is_assignment and the selectors are assignment_symbol and assignment_value_expression. The symbol is wrapped in a tagged list representing the name, and thus assignment_symbol needs to unwrap it. function assignment_symbol(component) { return symbol_of_name(head(tail(component)))); }

Constant, variable, and function declarations

Constant and variable declarations are parsed as follows: \[ \ll\ \textbf{const}\ \mathit{name}\ \ \texttt{=}\ \ \mathit{expression}\texttt{;}\ \gg \\ = \\ \texttt{list("constant\_declaration", } \ll\ \mathit{name}\ \gg \texttt{, }\ll\ \mathit{expression}\ \gg \texttt{)}\\[3mm] \ll\ \textbf{let}\ \mathit{name} \ \ \texttt{=}\ \ \mathit{expression}\texttt{;}\ \gg \\ = \\ \texttt{list("variable\_declaration", } \ll\ \mathit{name}\ \gg \texttt{, }\ll\ \mathit{expression}\ \gg \texttt{)} \] The selectors declaration_symbol and declaration_value_expression apply to both kinds. function declaration_symbol(component) { return symbol_of_name(head(tail(component))); } function declaration_value_expression(component) { return head(tail(tail(component))); } The function function_decl_to_constant_decl needs a constructor for constant declarations: function make_constant_declaration(name, value_expression) { return list("constant_declaration", name, value_expression); }

Function declarations are parsed as follows:

$\ll\ \textbf{function}\ \mathit{name} \texttt{(}\mathit{name}_1\texttt{, }\ldots\texttt{, } \mathit{name}_n \texttt{)} \ \mathit{block}\ \gg\ \ =$ list("function_declaration", $\ll\ $$name$$\ \gg$, list($\ll\ $$name$$_1\;\gg$, $\ldots$, $\ll\ $$name$$_n\;\gg$), $\ll\ $$block$$\ \gg$)

The syntax predicate is_function_declaration recognizes these. The selectors are function_declaration_name, function_declaration_parameters, and function_declaration_body.

The syntax predicate is_declaration returns true for all three kinds of declarations. function is_declaration(component) { return is_tagged_list(component, "constant_declaration") || is_tagged_list(component, "variable_declaration") || is_tagged_list(component, "function_declaration"); }

Derived expressions

Some special forms in our language can be defined in terms of expressions involving other special forms, rather than being implemented directly. One example is cond, which can be implemented as a nest of if expressions. For example, we can reduce the problem of evaluating the expression (cond ((> x 0) x) ((= x 0) (display 'zero) 0) (else (- x))) to the problem of evaluating the following expression involving if and begin expressions: (if (> x 0) x (if (= x 0) (begin (display 'zero) 0) (- x))) Implementing the evaluation of cond in this way simplifies the evaluator because it reduces the number of special forms for which the evaluation process must be explicitly specified.

We include syntax procedures that extract the parts of a condexpression, and a procedure cond->if that transforms cond expressions into if expressions. A case analysis begins with cond and has a list of predicate-action clauses. A clause is an else clause if its predicate is the symbol else.[6] (define (cond? exp) (tagged-list? exp 'cond)) (define (cond-clauses exp) (cdr exp)) (define (cond-else-clause? clause) (eq? (cond-predicate clause) 'else)) (define (cond-predicate clause) (car clause)) (define (cond-actions clause) (cdr clause)) (define (cond->if exp) (expand-clauses (cond-clauses exp))) (define (expand-clauses clauses) (if (null? clauses) 'false ; no else clause (let ((first (car clauses)) (rest (cdr clauses))) (if (cond-else-clause? first) (if (null? rest) (sequence->exp (cond-actions first)) (error "ELSE clause isn't last - - COND->IF" clauses)) (make-if (cond-predicate first) (sequence->exp (cond-actions first)) (expand-clauses rest))))))

Expressions (such as cond) that we choose to implement as syntactic transformations are called derived expressions. Let expressions are also derived expressions (see exercise 4.9).[7]

Derived components

Some syntactic forms in our language can be defined in terms of components involving other syntactic forms, rather than being implemented directly. One example is function declaration, which evaluate transforms into a constant declaration whose value expression is a lambda expression.[8] function function_decl_to_constant_decl(component) { return make_constant_declaration( function_declaration_name(component), make_lambda_expression( function_declaration_parameters(component), function_declaration_body(component))); } Implementing the evaluation of function declarations in this way simplifies the evaluator because it reduces the number of syntactic forms for which the evaluation process must be explicitly specified.

Similarly, we define operator combinations in terms of function applications. Operator combinations are unary or binary and carry their operator symbol as second element in the tagged-list representation: \[ \ll\ \mathit{unary}\textit{-}\mathit{operator}\ \ \mathit{expression}\ \gg \\ = \\ \texttt{list("unary\_operator\_combination", "}\mathit{unary}\textit{-}\mathit{operator}\texttt{"},\ \texttt{list(}\ll\ \mathit{expression}\ \gg \texttt{))} \] where $unary$-$operator$ is ! (for logical negation) or -unary (for numeric negation), and \[ \ll\ \mathit{expression}_1\ \mathit{binary}\textit{-}\mathit{operator}\ \ \mathit{expression}_2\;\gg \\ = \\ \texttt{list("binary\_operator\_combination", "}\mathit{binary}\textit{-}\mathit{operator}\texttt{"},\\ \texttt{list(}\ll\ \mathit{expression}_1\;\gg\texttt{,}\ \ll\ \mathit{expression}_2\;\gg \texttt{))} \] where $binary$-$operator$ is +, -, *, /, %, ===, !==, >, <, >= or <=. The syntax predicates are is_operator_combination, is_unary_operator_combination, and is_binary_operator_combination, and the selectors are operator_symbol, first_operand, and second_operand.

The evaluator uses operator_combination_to_application to transform an operator combination into a function application whose function expression is the name of the operator: function operator_combination_to_application(component) { const operator = operator_symbol(component); return is_unary_operator_combination(component) ? make_application(make_name(operator), list(first_operand(component))) : make_application(make_name(operator), list(first_operand(component), second_operand(component))); }

Components (such as function declarations and operator combinations) that we choose to implement as syntactic transformations are called derived components. Logical composition operations are also derived components (see exercise 4.7).

Exercise 4.3 Louis Reasoner plans to reorder the cond clauses in eval so that the clause for procedure applications appears before the clause for assignments. He argues that this will make the interpreter more efficient: Since programs usually contain more applications than assignments, definitions, and so on, his modified eval will usually check fewer clauses than the original eval before identifying the type of an expression.

1. What is wrong with Louis's plan? (Hint: What will Louis's evaluator do with the expression (define x 3)?)
2. Louis is upset that his plan didn't work. He is willing to go to any lengths to make his evaluator recognize procedure applications before it checks for most other kinds of expressions. Help him by changing the syntax of the evaluated language so that procedure applications start with call. For example, instead of (factorial 3) we will now have to write (call factorial 3) and instead of (+ 1 2) we will have to write (call + 1 2).

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.4 The inverse of parse is called unparse. It takes as argument a tagged list as produced by parse and returns a string that adheres to JavaScript notation.

1. Write a function unparse by following the structure of evaluate (without the environment parameter), but producing a string that represents the given component, rather than evaluating it. Recall from section 3.3.4 that the operator + can be applied to two strings to concatenate them and that the primitive function stringify turns values such as 1.5, true, null and undefined into strings. Take care to respect operator precedences by surrounding the strings that result from unparsing operator combinations with parentheses (always or whenever necessary).
2. Your unparse function will come in handy when solving later exercises in this section. Improve unparse by adding " " (space) and "\n" (newline) characters to the result string, to follow the indentation style used in the JavaScript programs of this book. Adding such whitespace characters to (or removing them from) a program text in order to make the text easier to read is called pretty-printing.

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.5 Rewrite eval so that the dispatch is done in data-directed style. Compare this with the data-directed differentiation procedure of exercise 2.77. (You may use the car of a compound expression as the type of the expression, as is appropriate for the syntax implemented in this section.)

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.6 Rewrite evaluate so that the dispatch is done in data-directed style. Compare this with the data-directed differentiation function of exercise 2.77. (You may use the tag of the tagged-list representation as the type of the components.)

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.9 Let expressions are derived expressions, because (let ((var$_{1}$ exp$_{1}$) $\ldots$ (var$_{n}$ exp$_{n}$)) body) is equivalent to ((lambda (var$_{1}$ $\ldots$ var$_{n}$) body) exp$_{1}$ $\vdots$ exp$_{n}$) Implement a syntactic transformation let->combination that reduces evaluating let expressions to evaluating combinations of the type shown above, and add the appropriate clause to eval to handle let expressions.

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.12 Many languages support a variety of iteration constructs, such as do, for, while, and until. In Scheme, iterative processes can be expressed in terms of ordinary procedure calls, so special iteration constructs provide no essential gain in computational power. On the other hand, such constructs are often convenient. Design some iteration constructs, give examples of their use, and show how to implement them as derived expressions.

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.