« Return to index

HOP WPO 1 (Solutions)

Assistant: Bjarno Oeyen (bjarno.oeyen@vub.be)

General remarks

These are some general remarks that I have that can help everyone becoming a better Scheme programmer.

Section 1: Getting used to prefix notation

Exercise 1: Conversion to prefix notation




		

In order to call a procedure, you need to put it as the first element in a combination (i.e., expressions wrapped in parentheses). The remaining elements in the list are the arguments sent to apply that function.

The value for z is a fractional number which is visualised as 3/8, however you cannot write it using this notation inside your program.

Exercise 2: Predict the result of the following expressions

Expression Result Comment
(* (+ 2 2) 5) 20
(+ (2 2) 6) Error: application: not a procedure (2 2) will try to apply 2, which is not a procedure.
5*4 Error: 5*4: undefined 5*4 is a variable, which has not been defined.
(define 5*4 20) No output
(5*4 + 2) Error: application: not a procedure 5*4 is still a variable, but it has been defined. However, its value is 20, thus cannot be applied as a procedure.
(* 5*4 2) 40
((+ 2 3)) Error: application: not a procedure (+ 2 3) produces 5. Thus (5) is evaluated. However, 5 is not a procedure. Thus an error.
(/ 6 2) 3
/ #<procedure:/> / is a variable that is bound to the #<procedure:/> procedure.
(define $ /) No output
(define / (* 2 3)) No output
(/ 6 2) Error: application: not a procedure / has been redefined to be equal to 6, and 6 is not a procedure and can thus not be applied.
/ 6
($ 6 2) 3 $ is now equal to #<procedure:/>, thus it can be applied.
$ #<procedure:/>
(+ 6 /) 12 / is still a variable bound to 6.
(define (double x) (+ x x)) No output Creates a new procedure called double and binds that variable to that procedure.
(double (double 5)) 20 Calls double twice on 5.
(define five 5) No output
(define (six) 6) No output
five 5
(five) Error: application: not a procedure
six #<procedure:six>
(six) 6

Hint! If the result you obtained in DrRacket is different. Make sure that you followed the instructions in section 0! You need to allow the redefinition of global variables.

Section 2: Building procedures

Exercise 3: Temperature conversion

Celsius to Fahrenheit:




		

Fahrenheit to Celsius:




		

Exercise 4: Areas and perimeters




		

Section 3: Recursion and Iteration

Exercise 5: Factorial!

Non-tail call recursive implementation:




		

Tail call recursive implementation:

Pass around an accumulator, so no work needs to be executed after doing the recursive call. Therefore, the Scheme interpreter does not need to grow the stack.




		

Renaming the function to fac-iter and write a function fac that supplies the default accumulator value is a nice approach. However, we polluted the global scope. Therefore, a nicer implementation is shown below.




		

You can create the fac-iter procedure inside fac such that it is not defined elsewhere. When evaluating (fac 5) will create fac-iter inside the evaluation of (fac 5).

Exercise 6: Collatz conjecture

Base implementation




		

Use ' for creating symbols (and other literal notations). A more detailed explanation will be given later.

Display total number of iterations




		

Section 4: Anonymous Procedures

Exercise 7: Lambda notation




		

You can arbitrarily nest lambdas.

Exercise 8: Higher-order Procedure (Exercise 1.41 from SICP)




		



		

Explanation:

Evaluating (double inc) will result in the creation of a new anonymous procedure object given by lambda. When this anonymous procedure is evaluated, the value for f can be found in the lexical scope (i.e., the scope created when (double inc) was evaluated. The value for x will be bound via the formal parameter (e.g., ((double inc) 2) will bound x to 2). Therefore, the body of the anonymous procedure will run in an environment where f is set to #<procedure:inc>, and x is bound to 2.

Exercise 9: Function composition




		

Analogous to the previous exercise, except that the top-most definition has two formal parameters that the anonymous procedure has access to.