Advanced Functional Programming Problem 2

John Hughes, Magnus Carlsson & Lennart Augustsson

The Problem

Your new problem is to implement a debugger for a simple functional language. After loading a program, your debugger should enable the user to

• evaluate expressions
• single-step evaluation
• continue execution for a limited number of steps
• trace function calls and returns, with the ability to turn tracing on and off for each function independently (this part is useful, but optional)
• set and remove break-points on function names
• inspect variable values at a break-point
• break on run-time errors (such as head of nil)
• reverse execution

Your debugger will need to print arbitrary values, and perhaps parts of programs at break-points. All such output should be pretty-printed.

Method

You should write an interpreter for the simple language, using a monad to keep track of the information that must be collected, and to support suspending the computation at a break-point. Your interpreter will probably contain a function such as

eval :: Program -> Env -> Expr -> M Value

type Env = [(Ident, Value)]

You will need to use continuations in your monad, to capture the interpreter state when computation is suspended.

The Simple Language

I suggest you write your debugger for a first-order, untyped, call-by-value language.

• first-order means that every function has a name --- good for naming break-points, for example.
• untyped means you don't have to write a type-checker.
• call-by-value means that the right order of evaluation is easy to determine --- important for example when you produce a trace. A debugger for a lazy language is considerably more difficult.

program ::= defn*
defn ::= lhs = expr ;
lhs ::= ident ident+
expr ::= if expr then expr else expr
      |  expr op expr
      |  ident expr+
      |  list
      |  (expr)
      |  number
      |  string
      |  ident
list ::= [] 
      |  [expr {, expr}*]
op ::= + | - | * | / | = | <= | :

The parser uses a parsing library.

The Interface

At a minimum, your interface should enable the user to load a program and interactively carry out the operations described above. Of course, it would be nice to provide a graphical interface, with toggles to turn tracing and break-pointing on and off, and the ability to edit the program during debugging (check out editorF if you want to do this). But a graphical interface is not required.

Information Sources

• The essence of functional programming, in your `collected papers', describes the use of monads in interpreters, and discusses the monad of continuations.
• Pretty-printing: an exercise in functional programming, in your collected papers, describes a library that will make the pretty-printers you need easy to write. There is a version of the library here.
• Programming with Continuations, D. Friedman, C. Haynes and E. Kohlbecker. This paper is not available online, but you can find it in the library. It's in Program Transformation and Programming Environments, (P. Pepper, ed. ), Springer-Verlag Lecture Notes in Computer Science (1984), pp 263--274. It describes programming with continuations in Scheme. The example discussed is available here, programmed in Haskell.
• A Debugger for Standard ML. Andrew Tolmach and Andrew W. Appel. Journal of Functional Programming, vol. 5, number 2, pp. 155-200, April 1995. This paper describes a rather more complete debugger for ML with reverse execution, implemented using continuations.

Learning Goals

The purpose of this problem is to:

• learn to use continuations
• design a more complex monad
• use a monad in an interpreter
• see the pretty-printing library

Deadline

This project is intended to take around three weeks. Solutions should be ready by Monday 29 November.

Collaboration