Machine Problem 10: Review

Out: Saturday, 12 April 2008

Due: 5 PM Friday, 18 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 practice on a few problems that would have made good questions for the final exam.

Tasks

The first two 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 two tasks.

For the other tasks, you will not make any changes to any interpreters; you will merely answer questions.

1. [10pts] Extend the interpreter for the SIMPLE language with basic list operations. Your extended variant of SIMPLE should have the following syntax:
   
   

   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)
   	::=	null	null-exp ()
   	::=	Unop(Expression)	unop-exp (op exp1)
   	::=	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)
   Unop	::=	car	op-car ()
   	::=	cdr	op-cdr ()
   	::=	null?	op-null? ()
   Binop	::=	+	op-plus ()
   	::=	-	op-minus ()
   	::=	*	op-times ()
   	::=	<	op-less()
   	::=	=	op-equal ()
   	::=	>	op-greater ()
   	::=	cons	op-cons ()

   
   This task involves changing the set of expressed-values for SIMPLE. To simplify the graders' task, you are required to use the following definition for the expval datatype:

      ;;; an expressed value is either a number, a boolean, a procval,
      ;;;    an empty list, or a pair whose cdr is a list.
      ;;;
      ;;; a list is one of
      ;;;   - an empty list
      ;;;   - a pair whose cdr is a list
   
      (define-datatype expval expval?
        (num-val
          (value number?))
        (bool-val
          (boolean boolean?))
        (proc-val
          (proc proc?))
        (null-val)
        (pair-val
          (ar expval?)
          (dr (letrec ((list? (lambda (e)
                                (and (expval? e)
                                     (cases expval e
                                       (null-val () #t)
                                       (pair-val (a d) (list? d))
                                       (else #f))))))
                list?))))
   

2. [4pts] It is inconvenient to have to build up lists from cons and null alone. Add a list-constructing syntax to the interpreter for your extension of the SIMPLE language from the previous task. This syntax consists of the word list followed by a possibly empty sequence of expressions that are separated by commas and enclosed in parentheses. There is no limit to the number of expressions. Here is an example:

       list(list(),
            list(1,2),
            list(1,2,3,4),
            list(1,2,3,4,5,6))
   

   That example is equivalent to:

       cons(null,
            cons(cons(1,cons(2,null)),
                 cons(cons(1,cons(2,cons(3,cons(4,null)))),
                      cons(cons(1,cons(2,cons(3,cons(4,cons(5,cons(6,null)))))),
                           null))))
   

3. [2pts] Write down a definition in the SIMPLE language, as extended by Tasks 1 and 2, that defines a procedure that
   • takes any list as its argument
   • returns the length of that list as an int.
4. [2pts] Suppose the types of your extended language are generated by

       τ ::= int
         ::= bool
         ::= list[τ]
         ::= ( -> τ )
         ::= ( α -> τ )
       α ::= τ
         ::= τ * α
   

   Answer the following questions:
   • Can the notation generated by that grammar describe the type of null?
   • Can the notation generated by that grammar describe the type of cons?
   • Can the notation generated by that grammar describe the type of the procedure you were asked to define for Task 3?
5. [2pts] If you answered "yes" to all three questions in Task 4, then use the notation generated by the grammar above to write down the types of null, cons, and the definition you wrote for Task 3. If you answered "no" to any of the three questions in Task 4, then describe an extension to the notation that would be able to express the types of null, cons, and the procedure you defined for Task 3.

Infrastructure

You are given three different interpreters for the SIMPLE programming language:

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

You may use any of those three interpreters as your starting point for Tasks 1 and 2. By now, you should know how to copy the code for one of those interpreters into one of your own directories.

Deliverables

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

Back to Machine Problems

Last modified: 13 April 2008