CMSC 330, Fall 2011
Organization of Programming Languages
Project 4 - Scheme Parser & Interpreter
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 Revised6 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 StartedDownload the following archive file p4.zip and extract its contents.
Along with files used to make direct submissions to the submit server (submit.jar, .submit, submit.rb), you will find the following project files:
Part 1: Simple Scheme ProgrammingPut your solution to this part in the file basic.scm.
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.
The grammar for Scheme S-expressions is particularly simple:
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 listFor example, the Scheme s-expression (foo (bar 3) 4 "baz") represented by the AST List [Id "foo"; (List [Id "bar"; Num 3]); Num 4; String "baz"]. Your AST nodes for strings should not include quotes. For example, parse ["\"a\""] should return String "a", i.e., a String constructed from a string with one character, a.
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 ...where the part labeled ... is for you to fill in. Hence you may extend this type with new constructors (e.g., for closures). However, you must not change the part of value we have given you, because our grading scripts will look for exactly those constructors, with exactly those arguments as given, to test your interpreter.
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:
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 | TRParenFor example, when called as tokenize "(foo (bar 3) 4 \"baz\")", the return value is
[TLParen; TId "foo"; TLParen; TId "bar"; TNum 3; TRParen; TNum 4; TString "baz"; 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 InterpreterTo make it easier to test your system, we've provided you with a driver file main.ml that reads lines of text up to ;; and passes their concatenation through your lexer, parser, and evaluator, and finally outputs the result. We've included a file sample.output containing a transcript of a session with our solution to this project. Note that we will test your project by calling your lexing, parsing, and evaluation functions directly, so be sure to give those functions the types we expect above.
SubmissionAll your code should be in two files, basic.scm & scheme.ml. You can submit your project in two ways:
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.