Higher-Order Programming » Lab Sessions

Session 1 (Solutions)

Assistant: Steven Keuchel (steven.keuchel@vub.be)

Identifiers and Bindings

Exercise 1

(* (+ 2 2) 5) ; -> 20 (+ (2 2) 6) ; Error, 2 is not a procedure 5*4 ; Error, 5*4 is seen as a variable, which is not bound at this point (define 5*4 20) ; No output, but now 5*4 is bound (* 5*4 2) ; -> 40 ((+ 2 3)) ; Error, 5 is not a procedure (define $ /) ; No output, but now $ is bound (define / (* 2 3)) ; No output, but now / is re-bound to a new value (/ 6 2) ; Error, 6 is not a procedure / ; -> 6 ($ 6 2) ; -> 3 $ ; -> #<procedure> (+ 6 /) ; -> 12 (define (double x) (+ x x)) ; -> No output, but now double is bound to a procedure known as #<procedure:double> (double (double 5)) ; -> 20 ((double double) double) ; -> Error: (double double) gives an error as its evaluation causes (* double 2), and * doesn't work on procedures. (define five 5) ; -> No output, but now five is bound to 5. (define (six) 6) ; -> No output, but now six is bound to a procedure known as #<procedure:six> which, when applied, returns the value 6. five ; -> 5 (five) ; -> Error: 5 is not a procedure six ; -> #<procedure:six> (six) ; -> 6

Exercise 2

The following output is generated by the program.

[foo] n = 15 [bar] n = 10 [bar] n = 20 300000

Inside the procedure foo, the procedure bar is applied twice. Whenever a procedure is called, a new environment is created where the parameters (given by the parameter list in the procedure), are bound to the argument values given in the application expression (usually, a compound expression = a combination). This means that bar sees an environment where n is not equal to 15.

Conditionals using if and cond

Exercise 3

(define (collatz-step n) (if (even? n) (/ n 2) (+ (* n 3) 1)))

Exercise 4

(define (check-password-length str) (define length (string-length str)) (cond ((< length 8) (display "Password too short!")) ((> length 20) (display "Password too long!")) (else (display ""))))

You can also optimise it by putting the display before/around the cond expression...

(define (check-password-length str) (define length (string-length str)) (display (cond ((< length 8) "Password too short!") ((> length 20) "Password too long!") (else ""))))

In order to understand recursion, you first have to understand recursion

Exercise 5

;; recursive process (define (fac n) (if (= n 0) 1 (* n (fac (- n 1))))) ;; iterative process (define (fac n) (define (iter n result) (if (= n 0) result (iter (- n 1) (* result n)))) (iter n 1))

The first solution entails a recursive process, as after (fac (- n 1)) is evaluated the multiplication still needs to be performed.

The second solution entails an iterative process as the recursive call to iter is in tail-position: thus after the recursive result is evaluated, no other computations need to be performed.

Both solutions are written as recursive programs (programs that make use of themselves), but thanks to tail-call optimisation, only the first describes a recursive process. Recursive processes need a run-time stack to remember pending computations.

Exercise 6

;; Only printing numbers (define (collatz-loop n) (display n) (newline) (if (not (= n 1)) (collatz-loop (collatz-step n)))) ;; Including a counter that returns the length of the sequence until a 1 is encountered... (define (collatz-loop n) (define (loop n i) (display n) (newline) (if (= n 1) i (loop (collatz-step n) (+ i 1)))) ; Using tail-call recursion (loop n 0))

Higher-Order Procedures

Exercise 7

(define (twice proc) (lambda (a) (proc (proc a)))) (((twice (twice twice)) add1) 5) ; -> 21

Exercise 8

(define (f x) (* x x)) (define (g x) (* x 2)) (define (compose f g) (lambda (x) (f (g x)))) (f (g 3)) ; -> 36 ((compose f g) 3) ; -> 36

Bonus Questions

The solutions to the bonus exercises are not published. For feedback, send your solution to the assistent.