• View
• Edit
• History
• Print

PS1

Home Assignments Lecture Blog Resources Project Discussion Group

91.301 Organization of Programming Languages
Prof. F. Martin

Out: Sept 3, 2009
Due: Sept 10, 2009

Overview

The purpose of the exercises below is to familiarize you with the basics of Scheme language and interpreter.

Spending a little time on simple mechanics now will save you a great deal of time over the rest of the course.

Any place that we ask for a piece of code or a written answer to be turned in you should place the code or answer in ps1-ans.ss. Written answers that are not code should be in comments in ps1-ans.ss.

Electronic submissions are preferred to paper, unless the assignment includes a drawing or other material for which it is simpler to make a pen-and-ink drawing. In this case, submit code electronically, and turn in written material in class.

Submit your code using the submit command on mercury. For this assignment:

Assignments are due at the beginning of class.

Reading

• SICP, Preface to the First Edition
• SICP, Chapter 1 Section 1

1. Before Turning on your Computer

Read the text through Section 1.1. Then, predict what the interpreter will print in response to evaluation of each of the following expressions. Assume that the sequence is evaluated in the order in which it is presented here.

(define b 13) 

13 

b 

> 

(define square (lambda (x) (* x x))) 

square 

(square 13) 

(square b) 

(square (square (/ b 1.3))) 

(define multiply-by-itself square) 

(multiply-by-itself b) 

(define a b) 

(= a b) 

(if (= (* b a) (square 13)) 
  (< a b) 
  (- a b)) 

(cond ((>= a 2) b) 
  ((< (square b) (multiply-by-itself a)) (/ 1 0)) 
  (else (abs (- (square a) b)))) 

2. Getting started with the Scheme Interpreter

In the Scheme interpreter, you will use a development environment called DrScheme. The DrScheme main window has two panels. In the upper panel you edit your answer file (or whatever Scheme code you happen to be working on). The DrScheme documentation calls this panel the definitions window.

The lower panel is for interaction with the Scheme interpreter, and is called the interactions window. Please see the documentation for the Scheme programming environment at http://download.plt-scheme.org/doc/html/drscheme/index.html for more.

Use the “Execute” button or the F5 key to load the contents of the definitions window into the Scheme interpreter. Executing will wipe out any previous contents in the interactions window. Use the interactions window for typing small tests, for finding the values of expressions, and for any text I/O (resulting from evaluating read, write, or display expressions).

DrScheme uses key bindings for editing commands similar to those used by the Emacs editor (just different enough to be annoying). You can also perform many editing tasks using the mouse and the menus.

To start Scheme in the lab on a Linux machine, type drscheme at the command line of a terminal window. You can download DrScheme for your own computer (Windows, Mac, or Unix) from the web site linked on the course web page.

Evaluating expressions

After you have learned something about editing in DrScheme, go to the interactions window (the lower panel in the DrScheme window) You can type Scheme expressions, and they should be evaluated and the result printed out.

Type in and evaluate (one by one) the expressions from Section 1 of this assignment to see how well you predicted what the system would print. If the system gives a response that you do not understand, ask for help from a staff member or from the person sitting next to you.

Observe that some of the examples printed above in Section 1 are indented and displayed over several lines for readability. An expression may be typed on a single line or on several lines; the Scheme interpreter ignores redundant spaces and carriage returns. It is to your advantage to format your work so that you (and others) can read it easily. It is also helpful in detecting errors introduced by incorrectly placed parentheses. For example the two expressions

look deceptively similar but have different values. Properly indented, however, the difference is obvious.

	(* 5 
	   (- 2 
	      	(/ 4 2) 
		(/ 8 3))) 

	(* 5 
	   (- 2 
	      (/ 4 2)) 
	   (/ 8 3)) 

When you type Enter at the end of a line, DrScheme will automatically indent the next line as needed.

Creating a file

Do any lab work that you want to submit (or any other work that needs to be preserved) in the definitions window. If modifying an existing file, use the “Open” dialog from the File menu. If starting a new file, just type a few characters and then press the Save button. A dialog should pop up requesting the file name to save into.

To practice these ideas, create a new file, called ps1-ans.ss. In this file, create a definition for a simple procedure, by typing in the following:

Now evaluate this definition by using either F5 or the “Evaluate” button. Go back to the interactions window, and try evaluating (square (+ 3 y)).

You should have hit an error at this point—the symbol y has not been defined. The system will now be offering you a chance to backtrace back the error, by clicking on the stacked stop sign in the interactions window.

The backtrace window shows you how Scheme tried to evaluate (square (+ 3 y)):

Reading from the bottom up, Scheme first tried to evaluate the whole expression, then the sub-expression to which square must be applied, and then the sub-expression to which + must be applied. Then it encountered the error when attemption to evaluate the identifier y.

To fix your invocation of square, press Escape followed by P (for “previous”) to get back the last line that you typed. Then you can edit it to say (e.g.) (square (+ 3 2)). Place the cursor at the end of the line, and press Enter to evaluate the expression.

Make a habit of using ESC-p, rather than going back and editing previous expressions in the interactions window in place. That way, the buffer will contain an intact record of your work (since the last “Execute”).

3. The Scheme Debugger

While you work, you will often need to debug programs. Unfortunately, DrScheme does not have as much debugging capability as some other Scheme and Lisp systems. It does have the ability to show you the sequence of evaluations that were performed befor the bug occurred.

You can find the code for this problem set here.

Save the code to your directory. Once you've saved the file, load the code for this problem set. Evaluate the code. This will load definitions of the following three procedures p1, p2 and p3:

(define p1
  (lambda (x y)
    (+ (p2 x y) (p3 x y))))

(define p2
  (lambda (z w)
    (* z w)))

(define p3
  (lambda (a b)
    (+ (p2 a) (p2 b))))

In the interactions window, evaluate the expression (p1 1 2). This should signal an error.

Don't panic. Beginners have a tendency, when they hit an error, to immediately try to change their code, often without even reading the error message. Then they stare at their code in the editor trying to see what the bug is. Indeed, the example here is simple enough so that you probably can find the bug by just reading the code. Instead, however, let's see how Scheme can be coaxed into producing some helpful information about the error.

First of all, there is the error message itself. It tells you that the error was caused by a procedure being called with one argument, which is the wrong number of arguments for that procedure. Unfortunately, the error message alone doesn't say where in the code the error occurred. In order to find out more, you need to look at the backtrace. Click on the stacked stop-signs icon in the interactions window to bring up a backtrace window.

4. Exploring the system

The following exercises are meant to help you practice editing and debugging, and using on-line documentation.

Exercise 1: More debugging The code you loaded for Problem Set 1 also defined three other procedures, called fold, spindle, and mutilate. One of these procedures contains an error. Evaluate the expression (fold 1 2). What is the error? What simple change to the procedure fold will fix the error?

Exercise 2: Computing factorials Type the following code into your buffer and evaluate it. You'll need this for Exercise 3.

(define fact 
  (lambda (n) 
    (if (= n 0) 
        1 
        (* n (fact (- n 1))))))

Exercise 3: Defining a simple procedure The number of combinations of n things taken k at a time, is given by n!/(k!(n - k)!). Define a procedure (comb n k) that computes the number of combinations, and find the number of combinations of 93 things taken 37 at a time. Include your procedure definition and your answer in ps1-ans.ss.

Exercise 4: Write a procedure that takes one argument and quadruples it. Call this procedure quadruple (you'll use it below).

Exercise 5: Write a procedure that takes two arguments and returns the difference of their quadrupled values. You should use the quadruple procedure that you wrote for Exercise 4.

Exercise 6: Write a procedure that takes two arguments and returns the smallest number. Call it smallest-of-two.

Exercise 7: Write a procedure that takes two arguments and returns the quadrupled value of the smallest number. You should use the procedures that you wrote for Exercises 4 and 6.

Exercise 8: Look through the DrScheme menus to find out how to re-indent in the region selected by the mouse (or to reindent the current line if no region is selected by the mouse). Explain how to do this in a comment in ps1-ans.ss (which whould be in the definitions window).

Also find out how to re-indent an entire buffer and explain how to do this in a comment in ps1-ans.ss.

What is the key shortcut to re-indent the contents of the buffer? (Look for the “Keybindings” entry in one of the menus.) Put the answer into a comment in ps1-ans.ss. (Figuring out the pattern here? You can type answers to questions into comments in the definitions window—this will allow you to evaluate the whole buffer to update your environment or to reload the code when you start working on your problem set again after a break.)

Exercise 9: Starting from the Help menu in DrScheme, open the Help Desk and use it to find the subsection on “Reading Comments” in the “Revised(6) Report on the Algorithmic Language Scheme” (often called the “R6RS”).

Copy that section into your definitions window.

Look up the keybinding in DrScheme that comments out code selected by the mouse.

Use that combination of keys to comment out the text you just inserted.

Use F5 or the execute button to load your definitions into your Scheme session. (If part of the description didn't get commented out, you will either get a bunch of error messages in the interactions window, of you will define the fact procedure, or both.)

Use the index of the R6RS to look up the “zero?” predicate. What other library procedures (dealing with numbers) are defined immediately after the “zero?” predicate?

Exercise 10: In this exercise, we will use Scheme's code stepper to examine the substitution model of Scheme execution.

To enable the stepper, select the language “Intermediate Student with lambda” from the How to Design Programs tab in the Languages menu.

Then, remove the text “#lang scheme” from the beginning of the buffer.

Now, type/copy the following code into your definitions window:

(define mystery 
  (lambda (a b) 
    (cond ((zero? b) 0) 
          ((odd? b) 
           (+ a (mystery (+ a a) 
                         (quotient b 2)))) 
          (else 
           (mystery (+ a a) 
                    (quotient b 2)))))) 
(mystery 7 2) 

Evaluate the buffer, and then click on the button. The Stepper window will appear. The statement being evaluated will be on the left—(mystery 7 2)—and on the right, will be the next step of the expansion. In this case, mystery is being evaluated and will be replaced by its definition (the lambda expression):

The exercise: How many steps does it take to get the value of

(mystery 7 2)

Exercise 11: Now we can try the substitution model as shown in class. You can use the stepper to check your intermediate results.

Put any evaluated expression into curly braces.

Put an expression that has all evaluated, but is not yet applied into square braces. For example:

((lambda (x) (* x x)) 5)                   evaluate the lambda 
({proc (x) (* x x)} 5)                     evaluate 5 
[{proc (x) (* x x)} {5}]                   substitute into the body 
(* {5} {5})                                evaluate * 
[{mult} {5} {5}]                           apply primitive {mult} 
{25} 

Please note: C-style “curly braces” are not part of Scheme syntax! We are just using them for the purposes of this exercise to highlight what expression is to be evaluated! Please don't get confused by this.

Assume we have definitions:

(define abs (lambda (x) 
               (if (> 0 x) 
                   (- 0 x) 
                   x))) 
(define square (lambda (x) (* x x))) 
(define a -2.0)

Your job is to use the substitution model to evaluate the combination

(square (abs a))

Exercise 12 (extra credit; required for honors/grad): Read Michael Swaine's article “It's Time to Get Good at Functional Programming.” Do some research to see if his opinion that functional programming could be quite valuable in multicore development is supported by others' research. Find one or more scholarly articles (search here, logging in with your UML student account: http://libproxy.uml.edu/login?url=http://www.acm.org/dl) to support your findings, and write about a page of discussion, including references.