Metalinguistic Abstraction I

Note

This is the Metacircular Evaluator, different from the CSE Machine, (kinda corresponds to substitution model)

Steps

1. Parsing
   1. Lexical analysis: Split the input program (string) into tokens (using regex)
   2. Parsing: Check that the tokens form allowable components, produce a syntax tree

Implementation

Syntax tree

The syntax tree is made out of tagged lists. A tagged list is a list where the first element is the tag (describes what the list is), and the remaining elements are the branches of the tree. The remaining elements themselves should be tagged lists.

parse("2 + 3;"); // will result in:
list("binary_operator_combination", "+",
	list("literal", 2),
	list("literal", 3));

Using the syntax tree

This is part of the CSE Machine code (simplified), it handles expressions:

// note: comp stands for component
// syntax predicates
function is_literal(comp) {
	return is_tagged_list(comp, "literal");
}
function is_tagged_list(comp, the_tag) {
	return is_pair(comp) && head(comp) === the_tag;
}
 
// selectors
function literal_value(comp) {
	return head(tail(comp));
}
 
// evaluate
function evaluate(expr, env) {
	return is_literal(expr)
		? literal_value(expr)
		: is_operator_combination(expr)
		? apply(op_comb_operator_symbol(expr), // operator
			list_of_values( // evaluate the operand expessions
				list(op_comb_first_operand(expr),
					op_comb_second_operand(expr))))
		: is_name(expr)
		? lookup_symbol_value(symbol_of_name(comp), env)
		// ...
		: error(expr, "Unknown expression:");
}
 
function list_of_values(exprs) {
	return map(evaluate, exprs);
}
 
function apply(operator, operands) {
	const first_op = head(operands);
	const second_op = head(tail(operands));
	return operator === "+"
		? first_op + second_op
		: operator === "-"
		? first_op - second_op
		// ...
		: error();
}
 
// to use:
const syntax_tree = parse("1 + 2 * 3");
evaluate(syntax_tree);

Syntax tree nodes contents

Literal

• value

Operator Combinations

• operator
• operand 1 expression
• operand 2 expression

Conditional

• predicate expression
• expression if true
• expression if false

Sequence

• It is a list of expressions

Block

• The sequence that is its body

Declaration

• Symbol (name)
• Expression that the symbol should be assigned to

Compound Function

• Parameters
• Body block
• Env

Frames and environments

function make_frame(names, values) {
	// names and values are lists
	// value of the ith name is stored at the ith position in values
	return pair(names, values);
}
 
function extend_environment(ns, vs, e) {
	return pair(make_frame(ns, vs), e); 
	// can be seen that an environment is a list
}
const the_empty_environment = null;
const the_global_environment = the_empty_environment;
 
// functions that can be used to implement symbol(name) lookup
function first_frame(env) {
	return head(env);
}
function enclosing_environment(env) {
	return tail(env);
}
function is_empty_environment(env) {
	return is_null(env); 
	// ^ since environments cannot be empty,
	// this will be the outermost enclosing environment
}
function lookup_symbol_value(name, env) {
	// recursively search for the symbol ...
}

Evaluating Blocks

{ const x = y + 7; x * 2; } // example block
function eval_block(component, env) {
	const body = block_body(component); 
	// ^ selector, will result in a sequence
	const locals = scan_ount_declarations(body);
	// ^ look through the sequence for name declarations
	const unassigneds = list_of_unassigned(locals);
	// ^ create the values list for the names
	// all items have the value "*unassigned*"
	return evaluate(body,
		extend_environment(locals, unassigneds, env));	
}

Evaluating Declarations

function eval_declaration(comp, env) {
	assign_symbol_value(
		declaration_symbol(comp),
		evaluate(declaration_value_expression(comp), env),
		env);
	// ^ this looks through the current frame for the symbol(name)
	// then, it evalues the value expression and assigns it
	return undefined;
}

Functions

function function_decl_to_constant_decl(comp) {
	// ...
} // this takes a "function aaa(x) {...}" and converts it to
// "const aaa = (x) => {...}"
 
function evaluate(comp, env) {
	return // ...
		: is_lambda_expression(comp)
		? make_function(//...)
		: is_function_declaration(comp)
		? evaluate(function_decl_to_constant_decl(comp), env)
		: is_application(comp)
		? apply(evaluate(function_expression(comp), env),
			list_of_values(arg_expressions(comp), env))
		// ...
		: error();
}
 
function apply(fun, args) {
	return is_primitive_function(fun)
		? apply_primitive_function(fun, args)
		: is_compount_function(fun)
		? evaluate(function_body(fun),
			extend_environment(function_parameters(fun), 
				args, 
				function_environment(fun)))
		: error();
}

Declaring functions are handled by the evaluate function like this:

1. Function declarations are converted to constant declarations, where the value is a lambda expression
2. Lambda expressions are converted to function (objects)