Homework #4 - CSE130 Programming Languages, Summer I, 2007

Homework #4 - CSE130 Programming Languages

Date Assigned:	Monday, 23 July 2007
Date Due:	Wesdnesday, 1 August 2007 (by 11:59 pm)
Required Solution Files:	`cse130/evaluator/CompoundProcedure.java`, `cse130/evaluator/Evaluator.java`, `cse130/evaluator/PrimitiveProcedure.java`, `cse130/evaluator/Procedure.java`, `cse130/parser/ConsCellDatum.java`, `cse130/parser/DatumParser.java`, `cse130/scanner/MiniLispScanner.java`.

Extend the Scanner to Support Quotes

Extend the MiniLispScanner to support reading the ' character as a new Punctuation token, described by the QUOTE value in the TokenType enum.

Extend the Parser to Support Quotes

Extend the DatumParser to support reading quoted datums. That is, you must automatically translate:

  ' datum

  (quote datum)

Where the result should be constructed with code like the following:

  new ConsCellDatum(new SymbolDatum("quote"),
                    new ConsCellDatum(quotedValue, new EmptyList()));

Write a Scheme-like Meta-Semi-circular Interpreter

Using the code base you already have and Chapter 4 as a guide, write an evaluator for a Scheme-like language in Java. Your Scheme-like language must support these forms:

quote (but you don't need to support quasiquote or unquote)
set!
define
if
lambda
begin
cond
and
or
let
procedure application

Your language must also have the following primitives:

cons
car
cdr
null?
pair?
newline
display
write
+ - variadic form, taking zero or more arguments
- - variadic form, taking one or more arguments
* - variadic form, taking zero or more arguments
/ - variadic form, taking two or more arguments; but use integer division only
< - variadic form, taking zero or more arguments
> - variadic form, taking zero or more arguments
= - variadic form, taking two or more arguments
exit - calls System.exit(0)

To help get you started, some code is already provided for you on ieng6:

$ cd ~/interpreter
$ cp -r ~/../public/interpreter/* .

$ cd ~/interpreter/cse130/evaluator
$ mv CompoundProcedure.java.skel CompoundProcedure.java
$ mv Evaluator.java.skel Evaluator.java
$ mv PrimitiveProcedure.java.skel PrimitiveProcedure.java
$ mv Procedure.java.skel Procedure.java

$ cd ~/interpreter/cse130/parser
$ mv ConsCellDatum.java.skel ConsCellDatum.java
$ mv DatumParser.java.skel DatumParser.java

$ cd ~/interpreter/cse130/scanner
$ mv MiniLispScanner.java.skel MiniLispScanner.java

Notes

Change your MiniLispScanner's main to use toWriteString when applicable. This is when the TokenType is considered self-evaluating:

    String rep = token.toString();
    TokenType type = token.getType();
    if (isSelfEvaluating(type)) {
        Value value = token.getValue();
        rep = value.toWriteString();
    }
    System.out.printf("%s:%d: %s=<%s>%n",
        file, token.getLineNumber(), typename, rep);

(And isSelfEvaluating is a helper method you'll have to write on your own.)

Change your DatumParser to call new method in ConsCellDatum to handle the "pair print" notation, which always uses the dot for pairs. Change the "list print" case to use toWriteString.

Turning It In

Execute the following commands to turn in the required files:

$ prep cs130u
[cs130u] $ cd ~/interpreter
[cs130u] $ bundleHW4

Grading

This portion of the interpreter is worth 80 points:

20 points from autograder-scanner.pl


20 points from autograder-hw3.pl

40 points from autograder-hw4.pl



Running The Autograder

To run the autograder for the interpreter, enter the following commands:

$ prep cs130u
[cs130u] $ cd ~/interpreter
[cs130u] $ autograder-hw4.pl