CS 11 Ocaml track: lecture 7Where we're atWhere we're goingOverview (1)Overview (2)Environments and values (1)Environments and values (2)Values (1)Values (2)Values (3)Slide 11Lexical scoping (example)Environments (1)Environments (2)Environments (3)Writing the evaluator (1)Writing the evaluator (2)Writing the evaluator (3)Writing the evaluator (4)Writing the evaluator (5)Writing the evaluator (6)Writing the evaluator (7)Writing the evaluator (8)Writing the evaluator (9)Writing the evaluator (10)Writing the evaluator (11)Writing the evaluator (12)Writing the evaluator (13)Writing the evaluator (14)Lab 6CS 11 Ocaml track: lecture 7Today:Writing a computer language, part 2Evaluating the ASTEnvironments and scopingWhere we're atWe've implemented the first part of a language interpretersource code  tokens (lexing)tokens  S-expressions (parsing)S-expressions  abstract syntax trees (ASTs) (also part of parsing)This is the boring (routine) part of writing an interpreterWhere we're goingToday, we'll look at the process of evaluating the ASTs produced by the lexing/parsing processOur programs will go through the parser and will be transformed into a sequence of AST expressionsWe will write an evaluator that can generate a value for any AST expressionOverview (1)Program  [parsing]  sequence of AST expressionsFor each AST expression,evaluate the AST expression to give a valueThat's all there is for a simple interpreter!More complex interpreters/compilers may transform the AST into simpler representations (often called intermediate representations or IRs)compilers may go all the way to machine languageOverview (2)Type signature of evaluator (in eval.mli):val eval : Ast.expr  Env.env  Env.valueThis says: take an AST expression and an "environment" and produce a "value"What are environments?What are values?Environments and values (1)Values are the possible legal values that AST expressions can evaluate toEnvironments are a data structure that stores the mappings (bindings) between identifiers in the language and their valuesEnvironments and values (2)Values and environments are mutually-recursive types:type id = string (* identifiers *)type value = (* values *) | Val_unit | Val_bool of bool | Val_int of int | Val_prim of (value list -> value) | Val_lambda of env * id list * Ast.expr list and env = (* environments *) { parent: env option; bindings: (id, value) Hashtbl.t }Values (1)Values represent the different possible results of a computation:Val_unit -- unit value (#u)Val_bool -- boolean value (#t or #f)Val_int -- integer valueVal_prim -- built-in (primitive) functionVal_lambda -- user-defined functionValues (2)Val_prim of (value list -> value) Represents built-in functions:+, -, *, /, <, >, etc.Built-in functions take a list of values (evaluated arguments) and return a single valueValues (3)Val_lambda (lambda expression) is particularly interesting:Val_lambda of env * id list * Ast.expr listAst.expr list is just a list of Scheme expressions in the body of the lambdausually just one expressionif more than one, evaluate them in orderid list is the list of identifiers making up the formal argument list of the functionenv ...Values (3)Val_lambda (lambda expression) is particularly interesting:env is the environment in which the lambda expression was definedlambda expressions "carry their own environments around with them"This is called lexical scoping and has many usesLexical scoping (example)(define adder (lambda (n) (lambda (i) (+ n i)))(define add3 (adder 3))Here, add3 is bound to the lambda expression (lambda (i) (+ n i))This wouldn't make sense unless there is an environment that maps n to somethingThat environment is the one that was active when (lambda (i) (+ n i)) was definedEnvironments (1)Recall:and env = { parent: env option; bindings: (id, value) Hashtbl.t }Environments bind names (identifiers, id) to values (value)here, we use an Ocaml hash table in the implementationEnvironments may have a "parent environment"here, we use an env option typeEnvironments (2)Environments are used to store bindings between identifiers and values and to look up the value corresponding to a given identifierHow to look up a value in an environment:1) Look it up in the bindings hash table2) If it's found there, return the corresponding value3) If it isn't found there, search the parent environment4) If there is no parent environment, signal an error (raise an exception)Environments (3)Ocaml hash tables are a data structure in the Ocaml standard libraryLook up hash tables in the Ocaml documentationHash tables are not a functional data structurethey are imperativeIn lab 6, the only part of the code that cares about hash tables is inside the file env.mlenv.mli has the interface to the env type, which doesn't mention hash tables at allenv is an abstract data typeWriting the evaluator (1)Type of the evaluator function (from eval.mli):val eval : Ast.expr -> Env.env -> Env.value Ast.expr is the expression to be evaluatedEnv.env is the environment in which the expression is evaluatedThis provides bindings for any free (unbound) variablesEvaluation only makes sense in the context of some environment! We call this the "current environment"Env.value is the result of evaluating the expressionWriting the evaluator (2)Type of AST expressions:type id = string type expr = | Expr_unit | Expr_bool of bool | Expr_int of int | Expr_id of id | Expr_define of id * expr | Expr_if of expr * expr * expr | Expr_lambda of id list * expr list | Expr_apply of expr * expr listWriting the evaluator (3)Literal expressions: | Expr_unit | Expr_bool of bool | Expr_int of intThese are easy to evaluateExpr_unit always evaluates to Val_unitExpr_bool evaluates to corresponding Val_boolExpr_int evaluates to corresponding Val_intThese expressions don't depend on the environmentWriting the evaluator (4)id and define expressions do depend on the environment| Expr_id of id | Expr_define of id * exprTo evaluate an Expr_id expression:look up the identifier (id) in the current environment and return the valueif the identifier isn't found, an exception will be raisedWriting the evaluator (5)id and define expressions do