Higher-Order Programming » Lab Sessions

Session 1

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

Identifiers and Bindings

In Scheme, symbols are used to represent variables. This means that the symbol string-length is not the string-length procedure itself, but it is the name how it can be found in the initial Scheme environment. The same is true for +. In contrast with many other programming languages (like Java, or Python), + resolves to a + procedure (and unlike those languages, it's not part of the syntax of the language).

---

Exercise 1: Predict, on paper, the outcome of evaluating the following program. Keep track of the values assigned to the created bindings. Check your answer by entering each expression one-by-one in the REPL.

(* (+ 2 2 2 2) 5) (+ (2 2) 6) 5*4 (define 5*4 20) (* 5*4 2) ((+ 2 3)) (define $ /) (define / (* 2 3)) (/ 6 2) / ($ 6 2) $ (+ 6 /) (define (double x) (+ x x)) (double (double 5)) ((double double) double) (define five 5) (define (six) 6) five (five) six (six)

Exercise 2: Predict the output of the following program. Check your answer by evaluating it in the REPL.

(define (foo n) (display "[foo] n = ") (display n) (newline) (define a (bar (- n 5))) (define b (bar (+ n 5))) (* a n b)) (define (bar n) (display "[bar] n = ") (display n) (newline) (* n 10)) (foo 15)

Note in Scheme you have no return statements. The last value produced by evaluating the body of the procedure, is the value returned when the procedure is applied.

Conditionals using if and cond

Scheme has two forms that can be used for conditional computations: if and cond. Abstract examples using these two forms are shown below...

(if <condition> <consequent> <alternative>) ;; Or ... (if <condition> <consequent>)

The classic if in Scheme consists of three sub-expressions: a condition expression, a consequent expression, and an alternative expression. A Scheme evaluator will, upon evaluating an if, first evaluate its condition expression. Depending on its evaluation result it will either evaluate the consequent expression (if the value produced by the condition expression is considered to be true), or the alternative expression (if the value produced by the condition expression is considered to be false).

Note that in Scheme, only false (#f) is considered to be false. Every other value (numbers, strings, and of course the boolean #t) are considered to be true.

In the case where only two sub-expressions are given (the condition expression, and the consequent expression), the evaluator will simply an unspecified value when the result of evaluating the condition expression is #f.

(cond <clause> ...) ;; Where <clause> = (<test> <sequence>) ;; Or ... (cond <clause> ... (else <sequence>)) ;; Where <clause> = (<test> <sequence>)

In situations where there are more than two branches, its better to make use of cond instead of nesting multiple if expressions. When the evaluator encounters a cond expression, it iterates over the different clauses, evaluating their test expression until one evaluates to a value considered to be true. It will then evaluate the sequence of expressions of that clause. The last clause can be an else-clause which is always evaluated if none of the other clauses were evaluated. If the else-clause is missing, the evaluator returns an unspecified value.

---

Exercise 3: The Collatz Conjecture is an unsolved conjecture in mathematics concerning a property of a sequence of numbers. Given the previous number in the sequence, the next number of the sequence can be found by applying the following function:

$$f(n) = \begin{cases} n / 2 \ &\text{if } n \ \text{is even} \\ 3 \times n + 1 & \text{if } n \ \text{is odd}\end{cases}$$

The conjecture states that when the sequence starts with a positive integer $n$, the sequence will, eventually, always reach the number 1.

Implement a procedure that, when given a number, calculates the next number in the sequence

Exercise 4: Almost all websites have a number of requirements for passwords if you wish to register an account. In this exercise, implement a procedure that checks the length of a password. When the password is too short (smaller than 8 characters) it prints “Password too short!”. When the password is too long (larger than 20 characters) it prints “Password too long!”. If the password is between 8 and 20 characters long nothing is printed.

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

Exercise 5: Implement fac which calculates the factorial of a given number.

$$n! = n * (n - 1)! \\ 0! = 1$$

Make use of tail-recursion. Is your solution a recursive or iterative process? Explain your reasoning, and implement it differently. Hint: What is tail-call optimisation?

Exercise 6: Implement a recursive procedure that given a number $n$ prints its Collatz sequence by making use of your solution of exercise 3.

Higher-Order Procedures

Exercise 7: Define a procedure twice that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice. For example, if add1 is a procedure that increments a number by one, then (twice add1) should return a procedure that increments a number by two. What value is returned when the following program is executed? You can assume that the given procedure takes only one argument.

(((twice (twice twice)) add1) 5)

Exercise 8: Define a procedure called compose that composes two procedures such that the first procedure is applied on the result of applying the second procedure of one of the arguments of the procedure (i.e., $f \circ g$). You can assume that both procedure take only one argument.

(define (f x) (* x x)) (define (g x) (* x 2)) (f (g 3)) ; -> 36 (compose f g) ; -> #<procedure> ((compose f g) 3) ; -> 36

Bonus Exercises

The solutions of these exercises will not be published. If you want to verify your solution, send it to the teaching assistant.

Exercise B1: Give the definition of variable f for each of the following cases.

(define f ...)

Expression	Output
f	1
(f)	2
(f 3)	3
((f))	4
(((f)) 3)	5

Make use of lambda whenever possible. Note that there can be different solutions for the same case.

Exercise B2: Modify your solution of exercise 8 such that it can also handle the case where the first procedure has more than one parameter. Check section 4.1.4 of the R5RS specification regarding the syntactical forms of <Formals>, make use of (apply proc lst) to apply a procedure proc on a variable-sized list of arguments lst. Even if we have not yet used lists earlier, you should still be able to perform this exercise.

Exercise B3: Which special forms did you use in the exercises of this lab session?