## Assignment 1

*Last updated 12 September 2010*

See also: Assignment1FAQ with questions I've been asked and answers I've given.

Due Friday 17 February on paper in class *and* by email to LAS with the clearly labeled subject line **FOCS assignment 1**.

(If you do it on paper, use the handy dandy scanner/copiers to email ...)

This assignment is complete and officially released (as of 9:15pm Sunday 12 Sept).

1. Define the following procedures using only the basic numeric operations + - * / < > <= >= = and list manipulations (cons/car/cdr -- or first/rest if you prefer -- and empty?, which is sometimes spelled null?). You may also use the special forms (including define, lambda, and if) that we discussed in class.

- A procedure that takes one argument, a positive integer, and returns the reciprocal (multiplicative inverse) of that number.
- A procedure that takes one argument, a positive integer, and returns the factorial of that number.
- A procedure that takes one argument, a positive integer, and returns a list of all of the integers between 1 and that number, inclusive.
- Is your procedure (from 1c) tail-recursive/iterative? If so, why? If not, why not?
*EXTRA CREDIT/CHALLENGE*: Can you write this procedure (from 1c) two different ways, one tail-recursively and one not? (Hint: don't worry about the order of the numbers in the list you produce.)

2. Write a scheme procedure that takes a list of numbers and returns a list of the same numbers in ascending order. For example,

(sort (list 3 1 7 5 -2 7 0 6)) ==> (-2 0 1 3 5 6 7 7)

- Is your procedure linear, quadratic, exponential, or something else? Explain your answer.

3. Suppose that we

(define repeatedly (lambda (f n) (lambda (x) (if (= n 0) x ((repeatedly f (- n 1)) (f x))))))

and also

(define 1+ (lambda (x) (+ 1 x)))

What will the results of evaluating the following expressions be?

`((repeatedly 1+ 6) 0)``((repeatedly (repeatedly 1+ 3) 2) 1)``((repeatedly (repeatedly 1+ 2) 3) 1)``((repeatedly 1+ 3) ((repeatedly 1+ 2) 1))``(repeatedly (repeatedly 1+ 2) 3)`- Explain any differences among your answers.
*EXTRA CREDIT/CHALLENGE*Considering the definition of repeatedly, above, write a procedure`repeatedly-until`which takes a procedure`f`of one argument and a procedure`until`of one argument, and repeats`f`until`until`evaluates to true (on the same argument as`f`). Make sure that you return the final value of repeatedly applying`f`to`x`. For example,((repeatedly-until 1+ (lambda (x) (= (remainder x 10) 0) ) ) 346) ==> 350

4. Functional programming languages are quite good for some things, but less good for others. Read about (stacks and) queues in Cormen (pp. 200 - 203). Explain why a queue is a more natural fit for a procedural programming language (i.e., one that uses assignment as a common primitive) than for a purely functional programming language that does not use assignment. You may find it easier to answer this question if you think about implementing a queue in your favorite assignment-based programming language and in scheme. Your answer should be a few well reasoned sentences (no more than a paragraph), possibly with an accompanying illustration if it helps your explanation.

5. Extend our expression evaluator -- see ExpressionEvaluatorDotScm -- with each of the following operations. You may use any of the versions we discussed in class or your own.

Exponentiation. You may use scheme's exponentiation operator,

`expt`, if you wish.- Squaring. Note that scheme does not have a built-in squaring operator.