« 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.

• Don’t write your code on a single line, use newlines and indentation. CTRL + I (⌘ + I on Mac) will auto-indent.
• By convention, procedure and variable names are in lowercase, use - to seperate words. E.g., celsius-to-fahrenheit instead of C2F (or something similar).
• If you save your files use the .scm filename suffix. Also, you can configure DrRacket to open multiple files using tabs instead of seperate windows. Go to Edit > Preferences (DrRacket > Preferences on a Mac), open the General tab and check the checkbox next to Open files in separate tabs.
• Make use of comments in your code (;). Multi-line comments (#| ... |#) can be used to comment out code.
• In the REPL of DrRacket use CTRL + ALT + Up/Down (Control + ⌘ + Up/Down on Mac) for re-executing a previous expression.

§ 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:

§ 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.