Itty Bitty Programming Language Interpreter Assignment

In a series of assignments, we will build the Itty Bitty Programming Language (IBPL). The inspiration for these assignments is MUPL by Dan Grossman and his team at UW.

One can build an IBPL Abstract Syntax Tree (AST) with the following expressions:

Expressions

(struct IdentifierExp (name)                                           #:transparent)
(struct IntExp        (value)                                          #:transparent)
(struct AddExp        (left_exp right_exp)                             #:transparent)
(struct IfGreaterExp  (left_exp right_exp then_body_exp else_body_exp) #:transparent)
(struct NilExp        ()                                               #:transparent)
(struct IsNilExp      (exp)                                            #:transparent)
(struct ConsExp       (car_exp cdr_exp)                                #:transparent)
(struct CarOfConsExp  (cons_exp)                                       #:transparent)
(struct CdrOfConsExp  (cons_exp)                                       #:transparent)
(struct LetExp        (binding_name binding_exp body_exp)              #:transparent)
(struct FunctionExp   (name_option parameter_name body_exp)            #:transparent)
(struct CallExp       (function_exp argument_exp)                      #:transparent)

Values

int

• exact-integer?

the empty list

• null
• null?

the mighty cons cell

• cons
• cons?
• car
• cdr

closure

(struct closure (env function) #:transparent)

Utility

entry

Environments in IBPL will be stored as a list of entries. An entry is comprised of a name of type string and a value which is a value.

• string?
• value?

(struct entry (name value) #:transparent)

Code To Implement

file:	src/main/racket/ibpl/interpreter/interpreter.rkt
functions:	value? expand-environment evaluate

value?

(define (value? v)
        (error 'not-yet-implemented))

expand-environment

(define (expand-environment name value env)
        (error 'not-yet-implemented))

evaluate

Note: the syntaxdescription below is adapted from Prof. Grossman's MUPL syntax description.

IBPL programs are written directly in Racket by using the constructors defined by the structs defined in ast.rkt.

This is the definition of IBPL’s syntax:

• If name is a Racket string, then (IdentifierExp name) is a IBPL expression (a variable use).
• If value is a Racket integer, then (IntExp value) is a IBPL expression (a constant).
• If e1 and e2 are IBPL expressions, then (AddExp e1 e2) is a IBPL expression (an addition).
• If s1 and s2 are Racket strings and e is a IBPL expression, then (FunctionExp s1 s2 e) is a IBPL expression (a function). In e, s1 is bound to the function itself (for recursion) and s2 is bound to the (one) argument. Also, (fun #f s2 e) is allowed for anonymous nonrecursive functions.
• If e1, e2, and e3, and e4 are IBPL expressions, then (IfGreaterExp e1 e2 e3 e4) is a IBPL expression. It is a conditional where the result is e3 if e1 is strictly greater than e2 else the result is e4. Only one of e3 and e4 is evaluated.
• If e1 and e2 are IBPL expressions, then (CallExp e1 e2) is a IBPL expression (a function call).
• If s is a Racket string and e1 and e2 are IBPL expressions, then (LetExp s e1 e2) is a IBPL expression (a let expression where the value resulting e1 is bound to s in the evaluation of e2).
• If e1 and e2 are IBPL expressions, then (ConsExp e1 e2) is a IBPL expression (a pair-creator).
• If e1 is a IBPL expression, then (CarOfConsExp e1) is a IBPL expression (getting the first part of a pair).
• If e1 is a IBPL expression, then (CdrOfConsExp e1) is a IBPL expression (getting the second part of a pair).
• (NilExp) is a IBPL expression. Notice (NilExp) is a IBPL expression, but NilExp is not.
• If e1 is a IBPL expression, then (IsNilExp e1) is a IBPL expression (testing for (NilExp)).

You should assume MUPL programs are syntactically correct (e.g., do not worry about wrong things like (IntExp "hi") or (IntExp (IntExp 37)). But do not assume IBPL programs are free of type errors like (AddExp (NilExp) (IntExp 7)) or (CarOfConExp (IntExp 7)).

Write a IBPL interpreter, i.e., a Racket function evalulate that takes an IBPL expression e and either returns the IBPL value that e evaluates to under the empty environment or calls Racket’s error if evaluation encounters a run-time IBPL type error or unbound IBPL variable.

A IBPL expression is evaluated under an environment (for evaluating variables, as usual). In your interpreter, use a Racket list of entries to represent this environment) so that you can use without modification the provided lookup-value-in-environment function. Here is a description of the semantics of IBPL expressions:

• An identifier evaluates to the value associated with it in the environment.
• An addition evaluates its subexpressions and assuming they both produce integers, produces the integer that is their sum. (Note this case is done for you to get you pointed in the right direction.)
• Functions are lexically scoped: A function evaluates to a closure holding the function and the current environment.
• An IfGreaterExp evaluates its first two subexpressions to values v₁ and v₂ respectively. If both values are integers, it evaluates its third subexpression if v₁ is a strictly greater integer than v₂ else it evaluates its fourth subexpression.
• A LetExp expression evaluates its first expression to a value v. Then it evaluates the second expression to a value, in an environment extended to map the name in the LetExp expression to v.
• A call evaluates its first and second subexpressions to values. If the first is not a closure, it is an error. Else, it evaluates the closure’s function’s body in the closure’s environment extended to map the function’s name to the closure (unless the name field is #f) and the function’s argument-name (i.e., the parameter name) to the result of the second subexpression.
• A cons expression evaluates its two subexpressions and produces a (new) pair holding the results.
• A CarOfCons expression evaluates its subexpression. If the result for the subexpression is a pair, then the result for the CarOfConsExp expression is the car field in the pair.
• A CdrOfCons expression evaluates its subexpression. If the result for the subexpression is a pair, then the result for the CdrOfConsExp expression is the cdr field in the pair.
• An IsNilExp expression evaluates its subexpression. If the result is an NilExp expression, then the result for the IsNilExp expression is the value 1, else the result is the value 0.

Hint: The call case is the most complicated. In the sample solution, no case is more than 12 lines and several are 1 line.

(define (evaluate exp env)
  (if (expression? exp)
      (if (list? env)
          (ensure-value? 
                 (error 'not-yet-implemented))
          (raise-argument-error 'env "list?" env))
      (raise-argument-error 'exp "expression?" exp)))

Test

file:	test_interpreter.rkt	Test
source folder:	src/test/racket/ibpl/interpreter

note: ensure that you have removed all printing to receive credit for any assignment.