« Return to index


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

Section 1: Box-and-pointer Diagrams

A cons creates a new pair where the first argument is the first element in the pair, and the second argument is the second element in a pair.


car will get the value stored at the first location, cdr the second location.


If either car or cdr contains another compound data type (e.g., another pair), then they are refered to by reference, not by copy. It is possible to modify the value stored in a pair via set-car! and set-cdr! (for usage, refer to the documentation). The following is a diagram of (cons a 5).

The following structures are all identical, the first one is the canonical form.


'() refers to the empty list. You can check for the empty list using (null? p).

All these structures have the following box-and-pointer diagram.

The procedure list builds a list of values.


Exercise 1: Simple box-and-pointer diagram

Using pen and paper, draw a box-and-pointer diagram of the following structure.


Exercise 2: Advanced box-and-pointer diagrams

Using pen and paper, draw a box-and-pointer diagram of the following structures. Explain the type of each structure (e.g., is it a tree? is it a list?).


Exercise 3: Shared memory in box-and-pointer-diagrams

Using pen and paper, draw a single box-and-pointer diagram of all the variables occuring in this program. What is shown when displaying every variable?


Hint! Refer to the report on R5RS to find out what the semantics of cddr are.

What happens when evaluate (set-cdr! c 'apple) afterwards? What is changed when you display every variable again?

Section 2: Higher-Order Procedures on Lists

In this course, we will make use of higher-order procedures, which are procedures that take a first-class procedure as argument.

Exercise 4: Sum

In this exercise, we will implement multiple versions of a sum procedure, that calculates the sum of all elements in a given list structure.

  1. Implement sum using recursion.
  2. Implement the higher-order procedure accumulate that has three parameters: a procedure, a default value, and a list.
  3. Implement sum by making use of accumulate

For the first part, use the following boilerplate code.


Exercise 5: Filtering

Complete the following definition of filter.


Then, call filter on the list '(4 8 15 16 23 42) such that only odd numbers are kept.

Then, create a predicate that matches odd numbers, unless they are negative. And pass this predict to filter the following list: (1 -1 2 -3 5 -8 13 -21 34 -55 89).

Hint! As a convention in Scheme, all names for predicate procedures should end on ? (e.g., even?, pair?,…)

Section 3: Higher-Order Procedures on Trees

For the exercises in this section, we will use the following trees.


If you feel stuck on one of these exercises, it can help to draw either a box-and-pointer diagram, or a tree diagram of these structures.

Exercise 6: Sum and depth of a tree

First, write a procedure that calculates the sum of all numbers in a tree, and the depth of a tree. If you are stuck, check the implementation of count-leaves given during the theory.

Predict what will happen if you pass the given trees to your procedures, then apply this procedure on all given trees. Did your outcome match your expectations?

Second, write a generic procedure that processes all elements in a tree. Complete the following boilerplate code.


Third, write your procedures of the first part of this exercise using tree-walk and verify whether you get the same result.

Exercise 7: Mapping the values on a tree.

Write a procedure tree-map that maps all the values in a tree according to some mapper function. Can you make use of tree-walk from the previous exercise to implement tree-map? If so, implement this variant.

Bonus Exercises

Bonus Exercise 1: Cycle

Recommended after exercise 3

Write a procedure that takes 3 arguments, and builds a cycle structure. E.g., the result of executing (make-cycle 8 5 3) should look like:

What is the output of when you display a data structure with a cyclic dependency?

Bonus Exercise 2: Generic Function Composition

Recommended after exercise 5

In the previous exercise session you have implemented compose for function composition. In the theory you have seen something that should make it possible to implement compose such that it can be executed on a dynamic number of arguments. Improve your implementation of compose such that it has support for multiple parameters.

Tip! Check section 4.1.4 of the R5RS manual for the different syntactical options for <Formals>.