Homework 1

A Language Processing Warm-Up

810:155
Translation of Programming Languages

OUT: Thursday, January 22
DUE: Thursday, January 29

Background

A straight-line programming language allows only one form of control flow, the sequencing of statements. As you might guess, all other things being equal, straight-line languages are simpler to interpret than languages that allow selection, loops, procedure calls, and other control structures. Yet they can be quite useful in simple computational domains.

Here is a grammar for a straight-line programming language defined in my programming languages course last semester. It supports programs with numbers, arithmetic expressions, variable bindings and references, and sequences of expressions:

            <exp> ::= <number>
                    | <variable-ref>
                    | ( <exp> <operator> <exp> )
                    | ( with <var> = <exp> do <exp>+ )
                    | ( <var> <- <exp> )

            <operator> ::= + | - | * | / | % | @

For simplicity, identifiers are strings starting with an alphabetic character, and numbers are integers.

Here are two sample programs in the language:

    (with x = 2 do
          (x <- (2 * x))
          (- x 1))

    (with x = 7 do
          (x <- (2 * x))
          (x <- (2 * x))
          (with y = 3 do
                (y <- (x * y))
                (* x y)))

Their values are 3 and 2352, respectively.

This assignment asks you to implement an interpreter for this language. Its goal is to let you refresh your programming skills before diving head-first into your compiler project. It will also (re-)introduce you to the ideas of:

• abstract syntax,
• structural recursion over inductive tree structures, and
• environments, which map variables to values.

Tasks

Implement a simple interpreter for programs in the little language.

Your interpreter should evaluate a program and print its value.

If you would like to keep things simple, you can define your programs as strings in code, or you may read a program from a file whose name is given as an argument.

For this assignment, you have the option of working in any high-level language except Scheme. If you choose to use a language other than Java, C/C++, or Ada, then you must receive my approval by Saturday night.

Extra Credit: Give your interpreter the ability to return the maximum number of variables in existence at any time.

This behavior can be an extra method or function available to the main function that invokes your interpreter.

Miscellaneous Notes

• You may work on this as individuals or as pairs. While you may certainly discuss the assignment with others, you (or you and partner) must write your own code.


• Please adopt the programming standards of whichever language you are using. In particular, if you are writing your program in Java, please use good object-oriented style.

Deliverables

By 12:30 PM on Thursday, January 29, submit the following:

• (electronically)   a compressed file named homework01.zip or homework01.tar.gz consisting of a folder that contains all of your code files from the assignment
• (hardcopy)   a print-out of whichever source file contains the code of your "main" function, which should invoke your interpreter

Make your electronic submission using the on-line submission system.