Project 4 - Scheme Parser & Interpreter

Introduction

In this project, you will write an interpreter for a tiny subset of the Scheme programming language. As part of the project, you will also write a parser that translates a plain text Scheme program into an abstract syntax tree (AST), and an evaluator that executes the code represented as an AST.

In order to test your project you may want access to a Scheme interpreter. If you log in to linuxlab, you use the command guile to launch the top level of one implementation of Scheme. To run the public tests type "guile public_scheme.scm", the file basic.scm will be loaded and used to execute the public tests.

If you want to find out more about Scheme, you can download the Revised⁶ Report on the Algorithmic Language Scheme. You may also try Teach Yourself Scheme in Fixnum Days.

For purposes of this project, we will only test your interpreter with valid input. Thus your code may do whatever you want on a bad input. We do, however, recommend adding reasonable error handling code to your project for cases of malformed or otherwise incorrect Scheme input, because it will make developing your project easier. As you are testing your program, you may inadvertently create incorrect input data; substantial time may be lost in trying to debug the program, only to find a few mistyped characters in your input data are the source of the problem.

Also, even though you need all of these pieces written to have a "complete" Scheme interpreter, we've structured the project so that you can work on any of the separate phases independently and test them on their own. So if you get stuck on an earlier part of the project, you can still move on to a later part.

Getting Started

Along with files used to make direct submissions to the submit server (submit.jar, .submit, submit.rb), you will find the following project files:

• Your Scheme program - basic.scm
• Your OCaml program - scheme.ml
• Utility code - testUtils.ml
• Public tests
  • public_scheme.scm
  • public_eval1.ml
  • public_eval2.ml
  • public_eval3.ml
  • public_eval4.ml
  • public_parse1.ml
  • public_parse2.ml
  • public_parse3.ml
• Expected outputs for public tests
  • public_scheme.out
  • public_eval1.out
  • public_eval2.out
  • public_eval3.out
  • public_eval4.out
  • public_parse1.out
  • public_parse2.out
  • public_parse3.out
• Driver - for testing scheme.ml interactively
  • main.ml
  • sample.output
• Test Script - goTest.rb
• New Test Cases - myTest.ml

Part 1: Simple Scheme Programming

Implement the following functions in regular Scheme. All of these functions should operate over integers and/or lists of integers. (These should look pretty familiar.) The purpose of this part is just to make sure you understand Scheme before you try to start writing an interpreter for it.

1. Write a function double x that returns two times x.
2. Write a function powof2 x that returns true (which is written #t in Scheme) if and only if x is a power of 2. (Hint: Use the functions / and modulo.)
3. Write a function sum l that returns the sum of the integer list l, using recursion. Hint: You can use the function pair? to determine whether a value is a cons cell or not; and in this problem, you can assume if something is not a cons cell, then it's '().
4. Write a function applyToList f l that returns a new list containing all the elements of l, in the same order, but with f applied to them. Your implementation should use recursion. You may not use Scheme's built-in map or for-each functions in writing your map function. Note applyToList directly takes 2 arguments (i.e., it is not using currying).

Scheme Grammar

The grammar for Scheme S-expressions is particularly simple:

• S -> id | n | str | #t | #f | ( L )
• L -> S L | epsilon

• id are Scheme identifiers. Identifiers may contain upper- and lower-case letters, digits, =, *, +, /, < >, !, ?, and -. For example, valid identifiers are Foo, set!, <three, and +=. Identifiers may not begin with a digit.
• n are Integers (made up of digits).
• str are Strings (beginning and ending with quotes). For purposes of this project, only alphanumeric and whitespace characters can appear within a string.
• #t and #f are tokens representing true and false.
• ( and ) are tokens (marking the beginning and end of a list).

For this project, Scheme S-expressions are represented using an AST (abstract syntax tree) defined using the following OCaml data type:

   type ast =
       Id of string
     | Num of int
     | Bool of bool
     | String of string
     | List of ast list

Part 2: Interpreting Scheme S-expressions

Put your solution to this part in the file scheme.ml.

For part 2 of this project, your task is to write a Scheme evaluator that, given an AST, executes the S-expression corresponding to that AST. We will describe the subset of the language you should handle below. You must write a function eval : ast -> value that, given an AST, produces a value representing the result of evaluating that AST. The type value should be of the following form:

type value =
    Val_Num of int
  | Val_Bool of bool
  | Val_String of string
  | Val_Nil
  | Val_Cons of value * value
  ...

As one example, eval (Num 3) should return Val_Num 3, meaning that an AST node containing the integer 3 evaluates to the integer 3. When doing this project, be sure to keep straight the difference between textual entities that the programmer has written down (like the text "3") with the resulting value that your interpreter produces (Val_Num 3).

In class, we will give you a precise definition of the core operational semantics of Scheme, which you should follow in doing your project. Here are the language features your interpreter should support:

• define at the top level. Your evaluation function must maintain a top-level environment containing the values of variables that have been defined. This top-level environment should persist from one evaluation call to another. For example, the following sequence of calls to your eval function should return 3:

    eval (List [Id "define"; Id "x"; Num 3]);
    eval (Id "x")
  

  You should allow define to bind variables to any possible Scheme values, including closures (see below). A define expression itself evaluates to nil. You may assume define is used only at the top level, and not within the body of a function; we will not test your interpreter with any such examples. You also do not need to handle cases where we redefine primitive operators.

  Remember that the Scheme top level environment permits values to be redefined at any time, even with different types. When a defined value is looked up, we return its latest definition. For instance:

    (define x 52)
    (define bar (lambda (y) (+ x y)))
    (bar 2)  <-- outputs 54
    (define x 7)
    (bar 2)  <-- outputs 9
  

  Hint: Since the top-level bindings will persist across calls to eval, you should probably store them in a ref.

• Values Your evaluation function should evaluate integers, booleans, and strings to the corresponding values.

• if You should allow both (if cond tr fl), which evaluates to tr if cond is true and fl otherwise, and (if cond tr), which evaluates to Val_Nil if cond is false.

• lambda You should support creating anonymous functions of one argument. We will not test your code with functions of any other arity. You must support closures.

• identifiers When presented with an identifier, your interpreter needs to look it up. The first place it should look it up is in the "local" environment, consisting of parameters of enclosing lambdas. This is the environment shown in the semantics lecture. When looking up an identifier, if it is not in that environment, then you should look it up in the top-level environment (the one that define updates). If an identifier is in neither environment, then it is unbound, and trying to evaluate it should produce an error.

• Function calls You should support calling user-defined functions of one argument. According to the previous requirement, user-defined functions will be represented as closures. Your implementation must be call-by-value, so that arguments are evaluated before they are passed to a closure. For example, consider the following sequence of calls to eval:

    let t = List
     [Id "define"; Id "next";
      List [Id "lambda"; List [Id "x"]; List [Id "+"; Id "x"; Num 1]]];;
    eval t;;
    eval (List [Id "next"; Num 3]);;
  

  Here we define t to be the abstract syntax tree corresponding to the Scheme code (define next (lambda (x) (+ x 1))). In evaluating t, we first evaluate the lambda to produce a closure. Then we bind next to the closure. The last evaluation line corresponds to the Scheme code (next 3). Thus we look up next in the top-level environment to return the closure. We evaluate 3, which produces Val_Num 3. Then we apply the closure to the argument to produce 4.

• Primitives You should support the following built-in functions; some of these functions can take more than one argument, but you don't have to implement them with currying--you can just make these special cases inside your evaluator. You do not have to treat primitive functions as first-class values; they will only be invoked and applied to arguments (and not passed as arguments or used as return values).
  • +, -, *, and = on integers. The + operator sums its arguments, and should accept one or more arguments. The - may take any number of arguments, and it subtracts its 2nd through last argument from its first argument; given only one argument, it compute unary negation. For example, (- 3) evaluates to Val_Num (-3), while (- 4 3) evaluates to Val_Num 1 and (- 4 3 1) evaluates to Val_Num 0. The * operator multiplies its arguments, and should accept one or more arguments. The = operator compares its two arguments and evaluates to either Val_Bool true or Val_Bool false. You may use the OCaml = operator.
  • nil. For this project, we will vary slightly from Scheme and make nil the built-in keyword for the empty list. Thus nil should evaluate to Val_nil. In actual Scheme, nil is written '().
  • cons, car, and cdr. Here (cons x y) should evaluate to the cons cell Val_Cons(x', y'), where x' and y' are whatever x and y evaluate to, respectively. When applied to a cons cell Val_Cons(x', y'), car returns x' and cdr returns y'.
  • boolean?, number?, string?, and pair?. These return true if their single argument is a boolean, integer, string, or cons cell, respectively, and false otherwise.
  • display. Prints its single argument, which is a string. Do not add a trailing newline after the string. Do not include any quotes around the string when it is printed. Display should return the value nil.

In order to support closures and primitives, you will probably want to extend the type value with two new constructors; alternately, you can add a single new constructor for closures and put the primitive handling code as special cases in your evaluation function.

Part 3: Parsing Scheme

Put your solution to this part in the file scheme.ml.

Your next task is to write a parser for Scheme S-expressions, which in this case will be a function that turns a string into a Scheme abstract syntax tree (AST). There are actually two parts to this: building a lexer to translate a sequence of characters into a sequence of tokens, which are smaller strings that form the terminals for the parser; and writing the actual parser itself, to turn the tokens into an AST.

To make the project a bit simpler, we've supplied you with a function tokenize : string -> token list that acts as a lexer, converting the string input into a list of tokens, represented by the following data type:

type token =
    TId of string
  | TNum of int
  | TString of string
  | TTrue
  | TFalse
  | TLParen
  | TRParen

You must write a function parse : token list -> ast that takes as input a list of tokens (returned from tokenize) and returns an AST. You should use the idea of a recursive descent parser, as we discussed in class. Thus we suggest you write two functions: parse_sexpr, which parses the non-terminal S, and parse_list, which parses the non-terminal L representing a list of S-expressions.

You may assume that all input test cases are syntactically correct. If the input Scheme code is not legal you may perform any action (e.g., exit, throw an exception).

Scheme Interpreter

Submission

• Submit your basic.scm & scheme.ml files directly to the submit server.
  • You can submit multiple files by puting the files in a .zip archive first. On Windows you can select the two files, then right click to select the "Send to->Compressed (zipped) Folder" option to create a .zip archive. Once your files are in a single zip archive, bring up the upload dialog box by clicking on the submit link in the column "web submission". Select your archive file using the "Browse" button, then press the "Submit project!" button.

  • The submit server now allows multiple files (from the same directory) to be selected. Bring up the upload dialog box by clicking on the submit link in the column "web submission". Browse to the directory containing your project files, then click on both basic.scm and scheme.ml. Now press the "Submit project!" button.

  

  

• You may also submit directly by executing a Java program on a computer with Java and network access. Use the submit.jar file from the archive p4.zip, To submit, go to the directory containing your project, then either execute submit.rb or type the following command directly:
  java -jar submit.jar

  You will be asked to enter your class account and password, then all files in the directory (and its subdirectories) will be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

  Successful submission # received for project 4

Academic Integrity

The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.