CS代写|CSCI 2041: Advanced Programming Principles



0. Introduction.

In this laboratory assignment, you’ll write a print function for the Lisp interpreter that we’re building in the lectures. It will print Lisp thing’s in readable form.

1. Theory.

OCaml provides a library module called Printf (with an upper case P) that defines functions for printing. One way to use it is to ask for a specific function you want. For example, to get the function printf (with a lower case p) you’d say Printf.printf. Another way is to ask for everything that’s in the module. To do that, place the following line at the beginning of your program file.

open Printf ;;

After that, everything visible in the module Printf is available for use in your program.
The function printf from the module Printf takes a format string as its first argument. The format string tells how to print its remaining arguments. Here are some calls to printf that may be useful in this assignment, along with brief descriptions of what they do.

printf "\n"

Stop printing on the current line and begin a new line.

printf "%i" e

Print the integer returned by the expression e.

printf "%s" e

Print the string returned by the expression e, but without surrounding quotation marks.

printf " "

Print a blank (a space).

printf "C0C1 ⋯ Cn−1"

Print a string containing the characters C0C1 ⋯ Cn−1, but without surrounding quotation marks.

Some Lisp thing’s can be printed with only a single call to printf. Other thing’s, like Lisp lists, require something more complex. Recall that a list is written inside a pair of parentheses () with its elements separated by blanks. The following imperative pseudocode algorithm prints a Lisp list L in this way.

print (
if L isnt empty
if print Ls first element
if L = Ls remaining elements
if while L isnt empty
if whprint  
if whprint Ls first element
if whL = Ls remaining elements
print )

For example, the algorithm prints an empty list as a pair of parentheses (), and a list of one element a as (a). It prints a list of two elements a and b as (a b). It prints a list of three elements ab, and c as (a b c), etc.

2. Implementation.

In the lectures, we defined an OCaml type thing to represent Lisp objects. It looks like this.

type thing = 
  Closure of thing ∗ thing ∗ environment | 
  Cons of thing ∗ thing | 
  Nil | 
  Number of int | 
  Primitive of (thing -> environment -> thing) | 
  Symbol of string 
  environment = (string ∗ thing) list ;;

Here Closure represents a user defined function, Cons represents a node in a nonempty list, Nil represents an empty list, Number represents an integer, Primitive represents a predefined function, and Symbol represents a name. The following table shows how each OCaml object described by this type must be printed. (The file tests9.ml has examples.)

OCaml object

How to print it

 Closure (p, b, e)  [Closure]
 Cons (e0, Cons (e1 ⋯, Cons (en−1, Nil) ⋯ ))  (e0 e1  en−1)
 Nil  nil
 Number n  n
 Primitive h  [Primitive]
 Symbol s  s but without quotation marks

You must write OCaml code that defines the following functions. Each function takes a thing as its argument. Your functions must print these thing’s as defined in the table.

printThing thing

Print thing. Begin a new line after thing is printed. Hint: call printingThing as a helper to do almost all the work for this function.

printingThing thing

Print thing, without beginning a new line. Use a matchwith to decide what thing is, and then print it according to the table. Hint: call printingThings as a helper to do almost all the work for printing lists made from Cons’es and Nil’s.

printingThings things

Here things is a list made from Cons’es and Nil. Print things without beginning a new line, as described in the table. Hint: translate the imperative pseudocode algorithm to applicative form.

You may write additional helpers if you need them. However, you must not use loops, mutable objects, or variables in any of your functions. If you do that, then you will receive ZERO POINTS for this assignment!