The original version of the tests.scm file provided for this assignment had an incorrect result for the multiple-shadowing-in-rhs test. The correct result of that test is 3, not 15. The test has been corrected in the current version of the tests.scm file. Please use the corrected file.

Machine Problem 9: Continuations

Out: Saturday, 5 April 2008

Due: 5 PM Friday, 11 April 2008

Submission: Individual

This assignment is to be done individually, not in pairs.

Purpose

The main goal of this assignment is to give you some experience with continuation-passing interpreters.

Tasks

The first three tasks involve adding features to the SIMPLE programming language by modifying an interpreter. You should submit a single interpreter that contains all of the modifications you made for the first three tasks.

For the last two tasks, you will not make any changes to any interpreters; you will merely answer questions. Your answers may include a small amount of code, but not a complete program.

1. [4pts] Extend the SIMPLE language by adding let expressions that bind one variable. (Hint: For Task 2, you will modify let expressions to bind any number of variables, so you can complete Task 1 just by completing Task 2. Nonetheless we recommend an incremental software development process in which you complete Task 1 before Task 2.)
2. [5pts] Extend the SIMPLE language by adding let expressions that bind any number of variables.
3. [10pts] Extend the language you implemented for Task 2 by adding return expressions. The full syntax of the language you will implement is
   

   Syntax for the SIMPLE language with let and return

   Program	::=	Definition … Expression	a-program (defns exp1)
   Definition	::=	define Identifier = proc ( Identifier … ) Expression	proc-definition (id bvars body)
   Expression	::=	Number	const-exp (num)
   	::=	Identifier	var-exp (var)
   	::=	Binop(Expression , Expression)	binop-exp (op exp1 exp2)
   	::=	if Expression then Expression else Expression	if-exp (exp1 exp2 exp3)
   	::=	(Expression Expression … )	call-exp (rator rands)
   	::=	let Identifier = Expression       … in Expression	let-exp (ids exps body)
   	::=	return Expression	return-exp (exp1)
   Binop	::=	+	op-plus ()
   	::=	-	op-minus ()
   	::=	*	op-times ()
   	::=	<	op-less()
   	::=	=	op-equal ()
   	::=	>	op-greater ()

   
   The semantics of

           return exp
   

   with continuation cont is the semantics of exp with the continuation that was most recently used to evaluate the procedure body within which the return expression appears; hence   return exp   ignores its normal continuation cont. If a return expression is executed outside the body of any procedure, then an error must be signalled and the program's execution terminated.
4. [3pts] Assume some fixed Gödel numbering for SIMPLE programs. Assume also that

           define executeSimple = proc (n) …
   

   is the definition of a SIMPLE procedure that
   • decides whether its argument n is the Gödel number of a well-typed SIMPLE program of type int;
   • if its argument is the Gödel number of a well-typed SIMPLE program of type int, and that SIMPLE program returns r as its result, then executeSimple also returns r;
   • if its argument is the Gödel number of a well-typed SIMPLE program of type int, and that SIMPLE program does not terminate, then executeSimple also does not terminate;
   • if its argument is not the Gödel number of a well-typed SIMPLE program of type int, then executeSimple does not terminate.
   Using the SIMPLE programming language extended with choose expressions, consider whether it is possible to define a boolean-valued procedure that
   • accepts two arguments p and q, both of type int;
   • returns true if there exists an integer n such that p ≤ n < q and (executeSimple n) returns an integer;
   • returns false if no such integer exists.
   If it is possible to define such a procedure, then write down a definition of that procedure. If it is impossible, then explain why it is impossible.
5. [3pts] Using the SIMPLE programming language extended with choose expressions, consider whether it is possible to define a boolean-valued procedure that
   • accepts two arguments p and q, both of type int;
   • returns true if there exists an integer n such that p ≤ n < q and (executeSimple n) returns an integer;
   • does not return if no such integer exists.
   If it is possible to define such a procedure, then write down a definition of that procedure. If it is impossible, then explain why it is impossible.

Infrastructure

You are given three different interpreters for the SIMPLE programming language, and you are also given an interpreter for the SIMPLE language extended with try/catch and throw:

• simple-lang
• simple-cps1
• simple-cps2
• simple-throw

You may use any of those four interpreters as your starting point for Tasks 1, 2, and 3. (Hint: If you use the interpreter that implements try/catch and throw, you will need to remove those two features.) By now, you should know how to copy the code for one of those interpreters into one of your own directories.

You are also given a set of tests for Tasks 1, 2, and 3.

Deliverables

1. An interpreter for the SIMPLE programming language extended with Tasks 1, 2, and 3.
2. A tests.scm file that includes the tests you wrote for Tasks 1, 2, and 3. Those tests should be run when the top.scm file is required.
3. A text file mp9.txt that contains your answers for Tasks 4 and 5.
4. A Development Diary

Back to Machine Problems

Last modified: 7 April 2008