« Return to index


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

Section 1: Environment Diagrams

Exercise 1: A Functional Environment Diagram

Using pen and paper, draw an environment diagram of evaluating (square 5) and (f 5) using the following definitions. You do not need to draw the definition of these 3 procedures.


Exercise 2: A Recursive Environment Diagram

The following is a solution of an earlier exercise.


Draw an environment diagram when evaluating (add-to-end (list 1 2 3) 5).

Exercise 3: A Lexical Environment Diagram

Using pen and paper, draw an environment diagram of evaluating the following program.


What is the displayed in the REPL? Is this the result you expected? What would be the result if Scheme had a dynamic scope (instead of a lexical scope)?

Section 2: Scheme Objects

Exercise 4: The Flip Procedure

  1. Define a procedure flip (with no parameters) that returns 1 the first time it is called, 0 the second time it is called, 1 the third time, 0 the fourth time, and so on.
  2. Define a procedure make-flip that can be used to generate flip procedures. That is, we should be able to define flip as (define flip (make-flip)).
  3. Draw an environment diagram to illustrate the result of evaluating the following sequence of expressions.


Exercise 5: A Turnstile

Create a Scheme object (see bank account example in the theory) that implements the behaviour of a turnstile (e.g., the barriers found at metro stops, the resto…). They count the number of persons that pass a specific point.

They should support the following operations.

The following boilerplate code is given.


Draw the environment diagram of executing the following sequence of expressions.


Exercise 6: Function Profiling

In software-testing applications, it is useful to be able to count the number of times a given procedure is called during the course of a computation. Write a procedure make-monitored that takes as input a procedure f, that takes itself one input. The result returned by applying make-monitored is a third procedure, say mf, that keeps track of the number of times it has been called by maintaining an internal counter. If the input to mf is the special symbol 'how-many-calls?, then mf returns the value of the counter. If the input is the special symbol 'reset-count! then mf resets the counter to zero. For any other input, mf returns the result of applying f on that input and increments the counter. For instance, we could make a monitored version of the sqrt procedure:


What happens when you call a monitored version of a recursive definition of fib.


Did your implementation return 1? Or another number? Adapt your solution. (Hint! You don’t need to change make-monitored. You have to find a way to redefine fib.)

Bonus Exercises

Bonus Exercise 1: Assignments

Recommended after exercise 3.

Predict the outcome of evaluating the following expressions in the Read-Eval-Print-Loop.

  1. (= a 5)
  2. (define a 12)
  3. (define b 10)
  4. (= a 5)
  5. (set! a 5)
  6. (= a 12)
  7. (= b a)
  8. (set! b a)
  9. (= a b)
  10. (define c a)
  11. (set! a 100)
  12. (= a c)

Explain these results. You can draw an environment diagram to help you explain these results.

Bonus Exercise 2: A Turnstile Extension

Recommended after exercise 5.

Extend the implementation for turnstile with the following features.

Bonus Exercise 3: My Own Pairs

Recommended after exercise 6.

A definition for cons, car and cdr is shown below that utilises lambda.


Draw the environment diagram of executing the following program.