Back to main page of Programming Language Technology.

Summary

The objective of this lab is to write an interpreter for a small, untyped functional programming language. This language is a tiny subset of Haskell. The interpreter should walk through programs and print out the value of the main function.

Before the lab can be submitted, the interpreter has to pass some tests, which are given on the course web page via links later in this document.

The recommended implementation is via a BNF grammar processed by the BNF Converter (BNFC) tool. No type checker is needed.

The approximate size of the grammar is 15 rules, and the interpreter code should be about 100 lines, depending on the programming language used for the implementation. You can use this grammar if you want.

All BNFC supported languages can be used, but guidance is guaranteed only for Haskell and Java.

Language specification

The language is the same as in the PLT book, Chapter 7.

Syntax

The main category is Program. A program is a sequence of definitions, which are terminated by semicolons. A definition is a function name followed by a (possibly empty) list of variable names followed by the equality sign = followed by an expression:

    f x1 ... xn = exp ;

Both f and the variables x1 ... xn are lexical identifiers. Thus f is the function to be defined, and x1 ... xn are its arguments. These variables are considered bound in exp. Notice that the all such definitions can be converted to definitions of just f with a lambda abstraction over its arguments.

The last definition has a special form. Its name is main, it has no variables, and its body is a call to the (undefined) unary function print. For example:

    main = print (2 + 2) ;

The purpose of this special form is to make our language a subset of Haskell. You can run well-formed programs in Haskell to check the expected result.

Expressions are of the following forms

Applications and operations are left-associative. Conditionals and abstractions are prefix operators and thus necessarily right-associative.

The available operations are +, -, <.

Here is an example of a program in the language:

    -- Multiplication with premature optimization.
  
    mult x y =
      if (y < 1) then 0 else
      if (y < 2) then x else
      (x + (mult x (y-1))) ;
  
    mult_with_less_parentheses x y =
      if y < 1 then 0 else
      if y < 2 then x else
      x + mult_with_less_parentheses x (y-1) ;
  
    -- The factorial function.
  
    fact = \x -> if (x < 3) then x else mult x (fact (x-1)) ;
  
    -- Compute factorial of 6.
  
    main = print (fact 6) ;

Lines starting with -- are comments.

Scoping

The function defined in a definition is in scope in the entire program, including the expression part of that definition (which results in recursive and mutually recursive functions). Exception: the main function is not in scope, thus, cannot be called from another function.

The variables bound on the left-hand-side of a definition are in scope in the expression part of the definition.

The variable x in an abstraction \x -> exp is bound in the body of the abstraction, i.e. exp.

Bindings made inside a scope overshadow those made outside.

Semantics

There is just one type of basic values: integers. The operations +, -, < have their usual integer semantics. The comparison < has value 1 if it is true, 0 if false.

The conditional if c then a else b is evaluated "lazily" so that if c has value 0, b is evaluated, otherwise a is evaluated.

The output of a program is the value of the expression passed to print in the main definition, and it must be an integer.

Besides integer expressions, a program usually contains expressions that denote functions, which orginate from definitions and abstractions. Functions can be applied to arguments, be passed as arguments to other functions and also be the result of a function call.

The interpretation of a program may exit with an error, in one of these cases:

• The main function is missing.
• An identifier is not bound. It should then report the unbound identifier by name.
• Something which is not a function is applied to an argument.
• An arithmetic operation is attempted on non-integers are also errors, e.g.

      f x = x + x ;
      main = print (f + f) ;
  

All these errors occur at run time, because there is no type checker.

Evaluation is parametrized so that it can be performed in both call-by-value and call-by-name.

Lab format

Solution templates

For Haskell and Java there are stubs that can be extended to the full solution. Just download one of the following tar archives, unpack, write the code, test, pack the archive again, and submit to fire.

• Haskell package
• Java package

These packages contain the grammar, stubs for the interpreter, and suitable makefiles. If you start from these stubs, you will likely match the requirements for the solution format as detailed in the following:

Input and output

Calling the interpreter should work by the command

    lab4 [-n|-v] <File>

The flag -n forces call-by-name evaluation, the flag -v forces call-by-value. The default, i.e. when no flag is present, is call-by-value.

The output at success must be just the output defined by the interpreter.

The output at failure is an INTERPRETER ERROR. The error message should also give some useful explanation, which we leave to your imagination.

Example of success

Source file:

    -- File: good.hs
  
    mult x y = if y < 1 then 0 else x + mult x (y-1) ;
    fact     = \x -> if x < 3 then x else mult x (fact (x-1)) ;
    main     = print (fact 6) ;

Running the interpreter:

    ./lab4 good.hs
    720

Example of failure

Source file

    -- File: bad.hs
  
    mult x y = if y < 1 then 0 else x + mult x (y-1) ;
    fact     = \x -> if x < 3 then x else mul x (fact (x-1)) ;
    main     = print (fact 6) ;

Running the interpreter

    ./lab4 bad.hs
    INTERPRETER ERROR: unknown identifier mul

Example of call-by-name vs. call-by-value

Source file:

    -- File: infinite.hs
  
    grow  x   = 1 + grow x ;
    first x y = x ;
    main      = print (first 5 (grow 4)) ;

Running the interpreter:

    ./lab4 infinite.hs
    <infinite loop>
  
    ./lab4 -n infinite.hs
    5

Compiling the interpreter

Use a Makefile similar to lab2. The interpreter should be compilable via calling

    make

Test programs

If you have any problems getting the test program to run, or if you think that there is an error in the test suite, contact the teachers of the course via the mailing list.

Run the programs in the test suite before submitting the lab. Include a log on the test run, showing the call of lab4 for every program in the testsuite.

Success criteria

The interpreter must give acceptable results for the test suite and meet the specification in this document in all respects.

All "good" programs must work with at least one of the evaluation strategies; need not work on both (because of loop or long time); see comments in test programs to see which one is expected to work.

The solution must be written in an easily readable and maintainable way. In particular, tailoring it for the programs in the test suite is not maintainable!

Submission

• Do not submit your solution before it passes the test suite, lest it be returned automatically.
• Please include exactly all the files that are required for building your solution, including a Makefile. To verify this you can follow the following 7 steps (on Windows, the tools used here (bash, mktemp, tar, make) are provided by both Cygwin and MSYS).
  1. Create an empty folder

       $ TMPDIR=`mktemp -d`
     

  2. Copy your solution to the created folder

       $ cp lab4.tar.gz $TMPDIR/
     

  3. Change to the created folder

       $ cd $TMPDIR
     

  4. Unpack your solution

       $ tar --strip-components=1 -xzf lab4.tar.gz
     

  5. Build your solution

       $ make
     

  6. Make sure step 5 succeeds without errors.
  7. Make sure your solution has been built

       $ ./lab4
     

• Do not submit any generated files.
• Submit your lab using Fire.