Assignment 4

Principles of Programming Languages (201-1289101)

Objects -- Mutation

Due June 4 1997


Questions

  1. Function profiler
  2. Print-cycles
  3. Constraints as Expression

Question 1: Function Profiler (Book 3.2 p.224)

When testing a program, it is useful to be able to count the number of times a given procedure is called during an evaluation. Write a procedure make-monitored that takes as input a procedure f, that itself takes one input. The result returned by 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 to mf is the special symbol reset-count!, then mf resets the counter to 0.

For any other input, mf returns the result of calling f on that input and increments the counter.

Example

> (define s (make-monitored sqrt))

> (s 100)
10

> (s 'how-many-calls?)
1

Note

If you use make-monitored on a recursive function, the way to count recursive calls as well as top-level calls to the function is as follows:
(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))

(define mf (make-monitored fact))
(mf 5)
(mf 'how-many-calls?) --> 1

;; This is the difference: it changes the definition of the recursive
;; function itself -- this way the recursive calls call the monitored 
;; version as well.
(set! fact (make-monitored fact))
(fact 5)
(fact 'how-many-calls?) --> 6

Optional

Extend make-monitored so that it can work with functions taking any number of arguments.

Question 2: Print cycles

The procedures set-car! and set-cdr! permit the construction of circular data structures. Our Scheme interpreter, however, is not prepared to print circular data structures and will go into an infinite loop trying to print one.
> (define x (list 1 2))
#
> (set-cdr! x x)
#
> x
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1...)
In general, the way the interpreter prints list values does not indicate if sublists are shared or not.
> (define y (list 1 2))
#
> (define x (cons y y))
#
> x
((1 2) 1 2)
Nothing in the way x is printed indicates that it contains two pointers to the same sublist (1 2). Write a function print-cons that does not loop on cycles and correctly indicates sublist sharing. The function outputs cons structures using the following Common Lisp syntax (the following definition is taken from "Common Lisp the Language", Guy Steele Jr):
#n=object: labels the first occurrence of an object that is reused later in
           the cons structure. n is an unsigned decimal number.

#n#:       refers to some object labelled by #n=; that is, #n# is a pointer
           to the same identical (eq?) object labelled by #n=.
A reference #n# may occur only after a label #n=; forward references are not permitted. In addition, the reference may not appear as the labelled object itself, that is, one may not write #n=#n#.

Examples

> (define x (list 1 2))
#
> (set-cdr! x x)
#
> (print-cons x)
#1=(1 . #1#)

> (define y (list 1 2))
#
> (define z (cons y y))
#
> (print-cons z)
(#1=(1 2) . #1#)

> (define u (cons (list 1 2) (list 1 2)))
#
> (print-cons u)
((1 2) 1 2)

Notes

You need to traverse the cons-structure twice. In the first traveral, in a depth-first manner, keep track of all cons cells used in a table. Be sure you avoid circles. In the second traversal, print the cons structure, using the #n= notation only if a cons cell is reused. Be sure to use the (x . y) notation as needed, as shown in example z above. In the first traversal, you need to define a data-structure keeping track of each cons cell and of how many times it appears in the total cons structure. Define this data-structure using the message-passing style.

Question 3: Constraints as Expression (Book 3.37 p.296)

The celsius-fahrentheir-converter procedure is not nice when compared with a more expression-oriented style of definition, such as:
(define (celsius-fahrentheit-converter x)
  (c+ (c* (c/ (cv 9) (cv 5))
          x)
      (cv 32)))

(define C (make-connector))
(define F (celsius-fahrentheit-converter C))
Here, c+, c*, c/ and cv are the "constraint" versions of the arithmetic operations. For example, c+ takes two connectors as arguments and returns a connector that is related to these by an adder constraint:
(define (c+ x y)
  (let ((z (make-connector)))
    (adder x y z)
    z))
Define analogous procedures c-, c*, c/ and cv (constant value) that enable us to define compound constraints as in the converter example above.
The end.