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)

Environment Support

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)

Runtime Type Error Support

raise-ib-type-error

When you encounter a runtime type error in evaluate, you should raise an exception which is more descriptive than, for example, what the + function might report. We have provided the function raise-ib-type-error which accepts a message and a value as well as an optional list of whatever other details you would like to provide.

(define (raise-ib-type-error message value . details)
  ; implementation can be found in ast.rkt

example use in evaluate

For example, if in handling an AddExp, you had defined local variables for right-exp and right-value and detected that right-value was not an exact-integer, then you could raise an exception something like the following:

(raise-ib-type-error "AddExp-right_exp not an exact-integer" right-value right-exp)

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))

Here we build a utility function to be used in evaluate. If name is a string?, value is a value?, and env is a list? we will cons an entry with the name and value onto the environment. If any of these conditions are not met, you should raise-argument-error with the appropriate information.

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 left_exp and right_exp are IBPL expressions, then (AddExp left_exp right_exp) is a IBPL expression (an addition).
• If name_option and parameter_name are Racket strings and body_exp is a IBPL expression, then (FunctionExp name_option parameter_name body_exp) is a IBPL expression (a function). In body_exp, name_option is bound to the function itself (for recursion) and parameter_name is bound to the (one) argument. Also, (FunctionExp #f parameter_name body_exp) is allowed for anonymous nonrecursive functions.
• If left_exp, right_exp, then_body_exp, and else_body_exp are IBPL expressions, then (IfGreaterExp left_exp right_exp then_body_exp else_body_exp) is a IBPL expression. It is a conditional where the result is then_body_exp if left_exp is strictly greater than right_exp else the result is else_body_exp. Only one of then_body_exp and else_body_exp is evaluated.
• If function_exp and argument_exp are IBPL expressions, then (CallExp function_exp argument_exp) is a IBPL expression (a function call).
• If binding_name is a Racket string and binding_exp and body_exp are IBPL expressions, then (LetExp binding_name binding_exp body_exp) is a IBPL expression (a let expression where the value resulting binding_exp is bound to binding_name in the evaluation of body_exp).
• If car_exp and cdr_exp are IBPL expressions, then (ConsExp car_exp cdr_exp) is a IBPL expression (a pair-creator).
• If cons_exp is a IBPL expression, then (CarOfConsExp cons_exp) is a IBPL expression (getting the first part of a pair).
• If cons_exp is a IBPL expression, then (CdrOfConsExp cons_exp) 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 exp is a IBPL expression, then (IsNilExp e1) is a IBPL expression (testing for (NilExp)).

You should assume IBPL 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 (CarOfConsExp (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 a null?, 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.