Problem Set 1: Beginning Scheme

[jdantonio]

Part 1.1: Simple Scheme

PS.1.1.1: Simple Scheme values

What are the values of the following Scheme expressions?

1. 5
2. (+ 3 4)
3. (- (+ 3 4) (* 2 (+ 4 3)))

PS.1.1.2: Valid Scheme expressions?

Which of the following are valid Scheme expressions? By "valid" we mean that the expression is a syntactically acceptable Scheme expression (which does not violate the syntax rules so does not generate a syntax error), even if evaluation of the expression might result in another error. For example (/ 5 0) is valid but generates a divide by zero error. You should treat the entire line as a single expression and mark only those that are syntactically valid.

1. +
2. 6 + 1
3. (6 + 1)
4. (* 1 2)
5. -1
6. - 1
7. (- 1)
8. (define x)

PS.1.1.3: More complex Scheme values

To what do the following expressions evaluate in MIT Scheme (assume they are evaluated in the sequence shown)? In addition to providing regular Scheme values (such as numbers and strings), you may answer "error", "procedure" or even "unspecified" when appropriate. You may abbreviate "error", "procedure" and "unspecified" by their first letters, "e", "p" and "u" respectively.

1. (define x (+ 2 3))
2. x
3. (+ x 4)
4. x
5. (define x 7)
6. x

PS.1.1.4: So what's a value anyway?

For each statement below, indicate whether it is true or false (check a box for true, leave it blank for false).

1. Names are self-evaluating.
2. Numbers are self-evaluating.
3. Every expression contained in parentheses is a combination.
4. (define 6 2) is a legal Scheme expression.
5. define is a special form.

PS.1.1.5: Correct or erroneous?

Some of the following expressions are correct Scheme expressions and others are not. For each expression, if it is both syntactially correct and evaluates without error, indicate its value. If the value is a procedure, simply indicate "procedure"; if the value is unspecified, then indicate "unspecified". If it is not syntactically valid or results in an error, indicate "error". You may abbreviate "error", "procedure" and "unspecified" by their first letters, "e", "p" and "u" respectively.

1. 2
2. +
3. (+ 2 3)
4. (5 6 7)
5. (+)
6. (3 + 4)
7. 2.5
8. (* 2.5 2)
9. After doing (define a 6), a
10. After doing (define a 6), (*a 2)
11. After doing (define a 6), (* a 2)
12. ((+ 2 3))
13. (+ -3 -5)
14. (+ 6 #f)
15. (+ 6 +)
16. (define 6 2)

PS.1.1.6: Scheme definitions

Assume the following Scheme expressions are evaluated sequentially. Indicate the value of each expression, or "unspecified" if it is unspecified. You may abbreviate "unspecified" as "u".

1. (define b (+ (* 3 4) 1))
2. b
3. (* b 2)
4. b
5. (define x 2)
6. (define y (+ x 1))
7. y
8. (define x 3)
9. y
10. (define x y)
11. x
12. y

Part 1.2: Scheme with procedures

Lec.2.1.1: Lambda evaluations

To what do the following expressions evaluate in MIT Scheme (assume they are evaluated in the sequence shown)? You may answer "error", "procedure" or even "unspecified" when appropriate. You may abbreviate "error", "procedure" and "unspecified" by their first letters, "e", "p" and "u" respectively.

1. (lambda (x) (+ x x))
2. ((lambda (x) (+ x x)) 2)
3. (define double (lambda (x) (+ x x)))
4. (double (double (double 2)))
5. (lambda (x y) x)
6. ((lambda (x y) x) 2 3)
7. ((lambda (x y) x) 2)
8. (define thing (lambda (x y) x))
9. (thing 4 5)
10. (thing thing 3)

Lec.2.2.1: What's in a name?

To what do the following expressions evaluate in MIT Scheme (assume they are evaluated in sequence)? You may answer "error", "procedure" or even "unspecified" when appropriate. You may abbreviate "error", "procedure" and "unspecified" by their first letters, "e", "p" and "u" respectively.

Note that this is meant to be an amusing example of the generality of Scheme, not an example of lucid programming style.

1. (define plus +)
2. (define + 7)
3. +
4. plus
5. (plus + +)
6. (plus 2 3)
7. (+ 2 3)

Lec.2.2.2: Evaluation of subexpressions

When we evaluate the expression (define x (lambda (a b) (* a b 232))), which of its subexpressions get evaluated?

1. x
2. a
3. define
4. (* a b 232)
5. (lambda (a b) (* a b 232))

Lec.2.2.3: More evaluation of subexpressions

Assume we have already evaluated the expression

(define x (lambda (a b) (* a b 232))).

Now, when we evaluate the expression

((lambda (y) (+ y 7)) (+ 3 (x 1 2))),

which of its subexpressions get evaluated?

1. x
2. 1
3. 3
4. (x 1 2)
5. (+ 3 (x 1 2))
6. (lambda (y) (+ y 7))

Lec.2.2.4: Desugaring your lambdas

Write an expression that is equivalent to the following, but that uses lambda explicitly:

(define (fizz x y z) (+ x z))

PS.1.2.1: Double your pleasure

Write a Scheme procedure that, given a value for x, returns double that value.

(define double (lambda (x) write_your_code_here))

PS.1.2.2: Solving simple equations

Write a Scheme procedure that, given a value for x, finds the value of the second order expression 3x^2 + 14x -5.

(define second-order (lambda (x) your_code_here))

PS.1.2.3: Solving quadratic equations

Write a Scheme procedure that, given coefficients a, b, and c of a quadratic equation ax^2 + bx + c, returns the larger of the (real) roots of the equation. You may assume a built-in scheme procedure sqrt that takes a non-negative number and returns its square root. Assume that a is greater than 0 and do not worry about guaranteeing that the roots will be real. The Tutor will test your code only with test cases where the roots are real.

As with all Tutor programming problems, you should define and test your procedure using an interpreter and editor -- in this case Dr. Scheme -- and paste your working code into the answer box. While you are testing your code, you might note that Dr. Scheme's built-in sqrt procedure will accept negative arguments and return imaginary values.

(define quadratic-root
  (lambda (a b c) your_code_here))

PS.1.2.4: Making a choice

Write a Scheme procedure that, given two arguments, returns the square of the first argument if the first argument is smaller than the second argument, and otherwise returns the square root of the second argument. You may assume a built-in Scheme procedure sqrt that takes a non-negative number and returns its square root.

(define weird (lambda (a b) your_code_here))

PS.1.2.5: Are you absolutely sure?

We used the built in Scheme procedure abs in lecture. But we ought to be able to write it ourselves. Write a Scheme procedure that takes a number as argument, and returns the absolute value of that number. Do not use abs within your procedure (this is cheating!!).

(define my-abs (lambda (a) your_code_here))

PS.1.2.6: Pushing it to the max

Another built in Scheme procedure, called max, takes an arbitrary number of arguments, and returns the largest of them. We should be able to write a simple version of this ourselves.

Part 1: Do it for two

Write a Scheme procedure that takes two numbers as arguments, and returns the larger of the two. Do not use max within your procedure (this is cheating!!).

(define bigger2 (lambda (a b) your_code_here))

Part 2: Do it for three

Write a Scheme procedure that takes three numbers as arguments, and returns the larger of the three. Do not use max within your procedure (this is cheating!!), but do use your procedure bigger2.

(define bigger3 (lambda (a b c) your_code_here))

[jdantonio]

Required Exercises

• PS.1.2.2: Solving simple equations
• PS.1.2.3: Solving quadratic equations
• PS.1.2.6: Pushing it to the max