15-814: `SimplyTyped+Arith` language interpreter.

Frequently Asked Questions

0. What do I need to implement?

You will implement a typechecker and interpreter for the simply-typed lambda calculus extended with booleans and natural numbers (as in Arith), and unit (See Ch.11).

Updated!To facilitate in testing and developing your code, we are providing you with a parser, and pretty printer for a version of the language with variables. We also provide functions that will convert this abstract syntax representation into the deBruijn index form that you will then typecheck and evaluate.

The code is available here (Last updated: 2002-10-14 11:30am). Please let me know if there are any bugs.

You will only really need to look at 3 files: lambda.sig is the signature that your solution should implement, lambda.sml is a skeleton for your implmentation, main.sml contains some functions that nicely tie everything together to facilitate in testing.

In addition a pair of examples are provided (test.pcf and test2.pcf), although you will certainly want more.

1. When I test things, SML prints out # signs, what do those mean, and how do I get rid of them?

The SML/NJ print-loop has several variables that control the depth and length of terms that it prints out. A # is an indication that SML/NJ decided to truncate the output of the term.

You can control the behavior with the following two procedures (conveniently already predefined for you in main.sml):


fun shallow () = (Compiler.Control.Print.printDepth := 5;
  Compiler.Control.Print.printLength := 12 )
fun deep () = (Compiler.Control.Print.printDepth := 200 ;
       Compiler.Control.Print.printLength := 400 )

Entering deep () will instruct the SML/NJ printloop to display more of the results. Entering shallow () will restore the default behaviour

2. I haven't even changed anything (in the code we were given) and it won't compile!

If you get errors when you do CM.make() and mention of pp-lib.cm, you're most likely running an old version of SML/NJ. The pretty printer library that I'm using is only present in versions 110.0.5 and later.

Unfortunately, the version of SML present on facilitized SCS machines is 110.0.3

So there are two solutions: install (the latest stable version) 110.0.7 yourself, or use a package of the pretty printer, below.

3. How do I use the pretty printer package?

Download the pretty printer. Move the tarball to the same directory as the sources.cm file (and the rest) for the assignment. Extract the tarball. You should now have a PP/ subdirectory. Edit the sources.cm file for the assignment, and change the last line from pp-lib.cm to PP/pp-lib.cm.

Everything should compile and run now. You can test it out:

[aleksey@gs155 pcf]$ sml
Standard ML of New Jersey, Version 110.0.3, January 30, 1998 [CM; autoload enabled]
- CM.make ();
[starting dependency analysis]
[scanning sources.cm]
...
...
...
[wrote CM/x86-unix/main.sml.bin]
[introducing new bindings into toplevel environment...]
val it = () : unit
- Main.pretty (Main.parse_str "L x : nat -> nat . x 0");
L x : nat -> nat. x 0
val it = () : unit
-

$Id: pcf-faq.html,v 1.4 2002/10/16 12:17:36 aleksey Exp $

    $Log:	pcf-faq.html,v $
# Revision 1.4  2002/10/16  12:17:36  aleksey
# question 3: backport of pretty printer available
# 
# Revision 1.3  2002/10/16  11:53:34  aleksey
# added question 2: old version of SML without pretty printer
# 
# Revision 1.2  2002/10/14  11:39:20  aleksey
# Updated answer 0: a skeleton implementation is available.
# 
# Revision 1.1  2002/10/10  10:23:06  aleksey
# Initial revision
#

15-814: SimplyTyped+Arith language interpreter.