Project 2: Scheme InterpreterCSC 4101, Fall 2014Due: 13 November 2014For this project, you will implement a simple Scheme interpreter in C++ or Java. Your interpreter shouldbe able to handle the same subset of the language as the parser for project 1, as well as some predefinedfunctions.In particular, your interpreter should implement• symbols, 32 bit integers, booleans, strings, lists, and closures;• the test symbol? for identifying an identifier;• the test number? for identifying integers and the binary arithmetic operations b+, b-, b*, b/, b=,b<;• the list operations car, cdr, cons, set-car!, set-cdr!, null?, pair?, eq?;• the test procedure? for identifying a closure;• the I/O functions read, write, display, newline;• the functions eval, apply, and interaction-environment.Build this interpreter on top of the code you wrote for project 1. Use the parse trees from project 1 asthe internal data structure for lists. The arithmetic and list operations would then be simply implemented bythe appropriate C++ (or Java) operations on parse trees.The following built-in Scheme functions call parts of your interpreter:• read calls the parser and returns a parse tree,• write calls the pretty-printer,• eval calls your C++ or Java eval() function,• apply calls your C++ or Java apply() function,• interaction-environment returns a pointer to your interpreter’s global environment.All other built-in Scheme functions, such as and, or, not, >, >=, <=, list, cadr, caddr, etc.,equal?, map, assq, reverse, etc., can then be implemented as Scheme definitions using only theprimitive operations implemented above. Since we have a general mechanism for defining functions with avariable number of arguments, the n-ary versions of the binary arithmetic operators can also be implementedin Scheme. We’ll do that in project 3.1EnvironmentsFor keeping track of the values of variables during evaluation, we need a data structure for storing thesevalues. That’s the environment. Scheme is a language with nested scopes. Given the function definition:(define (z x) (+ x y))(define y 42)(define x 17)When evaluating the body of the function call (z y), we need to look for the values of +, x, and y. For eachvariable, we first look in the local function scope, then in the outer file scope, then in the scope containingthe built-in function definitions. We will find x in the function scope, y in file scope, and + in built-inscope (+ is nothing special, it’s a regular variable which has a function as its value). The environment datastructure needs to be designed to allow this search.The environment consists of individual frames, tables that contain the values for a single scope. We haveone scope for built-in functions, the top-level (file) scope, and one scope for each function call and for eachevaluation of a let-expression. Every frame is linked to the frame representing the syntactically enclosingscope. When looking up the value of a variable, we traverse these links to frames for enclosing scopes untilwe find the variable or until we reach the outermost scope.If a variable name refers to a function, its value is represented as a closure. Unlike function pointers in C,which only point to the code, a closure consists of two pointers: a pointer to the code (a lambda expression)and a pointer to the environment in which the lambda expression was created.As data structure for environments, you could either use a list of association lists or a list of hash tables.The implementation of environments is described below in the form of association lists in Scheme. This isalso the implementation used in the Scheme interpreter written in Scheme. I suggest, though, that you useclasses to define the environment data structure.An association list is a lists of pairs with the first element (the car) of each pair being the key and thesecond element (the cadr) being the value. The Scheme function assq can be used to look up an entry inan association list. The function assq takes a key as first argument, an association list as second argument,and looks up the key in the association list with the comparison operation eq?. E.g., the call(assq ’y ’((x 17)(y 42)(z (closure(lambda (x) (+ x y))nil))))will result in the list (y 42).Each scope in the program will be represented by such an association list. A complete environment isa list of association lists, from the innermost scope to the outermost scope. E.g., evaluating the Schemedefinitions(define (z x) (+ x y))(define y 42)(define x 17)will result in the environment2(((x 17)(y 42)(z (closure (lambda (x) (+ x y)) ...))))where ... is the environment in which z is defined, i.e., a pointer to the entire environment. Since thisresults in a circular data structure, we need to use the assignment function set-car! for building it.The circular data structure can be constructed in Scheme using set-car! as follows:; Define the empty environment: a list containing an empty scope(define env (list ’())); Add a binding for z to the innermost scope(set-car! env (cons(list ’z (list ’closure’(lambda (x) (+ x y))env))(car env))); Add a binding for y to the innermost scope(set-car! env (cons(list ’y 42)(car env))); Add a binding for x to the innermost scope(set-car! env (cons(list ’x 17)(car env)))These set-car! operations are performed when evaluating the define special forms above.The value associated with a variable can be updated using set-cdr!. For example, the redefinition(define x 15) or the assignment (set! x 15) would have the effect(set-cdr! (assq ’x (car env)) (list 15))When calling a function, we create a new (empty) association list for representing the function scopeand cons it in front of the environment in which the function was defined (which is taken out of the closurefor the function). Then we add variable definitions for the parameters to the new association list.Given the function call (z y), the body of the function z will be evaluated in the environment(((x 42))((x 17))(y 42)(z (closure (lambda (x) (+ x y)) ...)))where the first association list, ((x 42)), contains the binding for the parameter x of function z to thevalue passed as argument.A frame (association list) is added to the environment when entering a function body or when entering alet body. For each define that is encountered inside a function body or inside a let body, one bindingis added to the front of the first frame in the environment.The Scheme interpreter written in Scheme is