Homework 5. Generating programs returning recursively mutable structures

Motivation

Many programs at your company Amalgamated Software Engineering (ASE) are written in Scheme. These programs are supposed to be portable to a wide variety of Scheme implementations.

Among other things, ASE's Scheme programs often generate other Scheme programs, and include in their output programs objects that are supposed to be recursively mutable structures. Here are two simple examples of recursively mutable structures:

> (define s1 (string-copy "abc"))
> (define s2 (list s1 3 7 (list 'def)))
> s1
"abc"
> s2
("abc" 3 7 (def))
> (string-set! s1 1 #\z)
> s1
"azc"
> (set-car! (cdr s2) 1.1)
> s2
("azc" 1.1 7 (def))
> (string-set! (car s2) 2 #\y)
> s2
("azy" 1.1 7 (def))
> s1
"azy"

Here, s1 and s2 are recursively mutable, in the sense that every pair, vector or string within these objects are mutable. In the above example, string-set! modifies a string, and set-car! modifies the car field of a pair; but these uses are valid, since s1 and s2 are recursively mutable. In contrast, the literal constants "abc" and '("abc" 3 7 (def)) return structures that cannot be modified by an portable Scheme program, so string-set! and set-car! cannot be used on the resulting values.

ASE's programs often generate Scheme programs that are supposed to contain large mutable structures. It would be convenient if a program generator could output a program snippet like this:

'(a large mutable structure
  #(with some subvectors)
  (and sublists)
  "and strings"
  and numbers like 3.0 and so forth.)

This does not work, however, since the expression 'x returns a structure that might be immutable. A generator of portable Scheme programs can output a program snippet that looks like this instead:

(list 'a 'large 'mutable 'structure
 (vector 'with 'some 'subvectors)
 (list 'and 'sublists)
 (string-copy "and strings")
 'and 'numbers 'like 3.0 'and 'so 'forth.)

This generates a mutable structure, since the builtin procedures list, vector and string-copy always return mutable objects. However, it is a bit of a pain to do this sort of thing by hand, so your boss assigns you the job of automating it.

While working on this job, you notice that there are multiple ways to generate a correct answer. For example, here is a different expression that returns an equivalent recursively mutable structure:

(cons 'a
 (cons 'large
  (cons 'mutable
   (cons 'structure
    (cons (vector 'with 'some 'subvectors)
     (cons (cons 'and (cons 'sublists '()))
      (cons (string-copy '"and strings")
       (cons 'and
	(cons 'numbers
	 (cons 'like
	  (cons '3.0
	   (cons 'and
	    (cons 'so
	     (cons 'forth.
	      '()))))))))))))))

This expression is longer, partly because it uses cons instead of list, and partly because it quotes subexpressions like 3.0 and "and strings" that do not need to be quoted. You ask your boss about this, and he suggests two rules. First, omit the ' in 'X (i.e., prefer X to (quote X)) whenever possible. Second, prefer list to cons and to '() whenever possible, so that your program should never generate '() and should generate (cons A D) only when D does not evaluate to a list.

Three other questions come up.

What about cyclic structures, e.g., the structure returned by (let ((zeros (cons 0 '()))) (set-cdr! zeros zeros) zeros)?
What about structures with shared substructure, e.g., the structure returned by (let ((p (cons 0 1))) (cons p p))?
What about boxes and hash tables? These MzScheme extensions are not portable to all R5RS implementations, but your company's code uses them in a few places, so you want to handle them too.

Your boss says that for your first prototype you don't need to worry about these three cases: you can assume that your input expressions contain neither cycles nor shared substructure nor boxes nor hash tables. However, he wants you to think about these cases and design a solution that will handle them, even if your current prototype does not handle them.

Assignment

Write and test a Scheme function (expr-returning-mutable obj) that returns a Scheme expression that, when evaluated, will return a recursively mutable copy of obj, that is, an object that has the same data structure as obj, but where every pair, vector, and string is mutable.

Furthermore, design extensions for expr-returning-mutable to support cycles, shared substructure, boxes, and hash tables, and write test cases for these extensions.

Your implementation of expr-returning-mutable can assume that its argument contains only booleans, characters, numbers, pairs, strings, symbols, and vectors. In particular, you need not worry about arguments containing ports or procedures. Your implementation may also assume that its argument has neither cycles nor shared substructure.

Your implementation of expr-returning-mutable should be written in portable R5RS Scheme. When it uses recursion, it should prefer tail-recursion.

Also, your implementation should be free of side effects. For example, it should not invoke any builtin procedures whose names contain ! and it should not do any I/O. Also, it should not invoke any conversion procedure (a procedure with -> in its name).

The expressions that expr-returning returns should restrict themselves to the following tiny subset of Scheme:

Numerical constants, string constants, character constants, and boolean constants.
(quote S) where S is a symbol.
(string-copy S) where S is a string constant.
Calls to list and vector.
Calls to cons, but only when absolutely necessary. That is, if there is an equivalent expression that does not use cons, it should be generated instead.

These expressions always return mutable objects. For example, the expression (quote (a b)) is not allowed, as it yields an object that might be immutable.

To avoid garbage-collection overhead, the expressions should avoid generating objects that are not used in the final result. For example, if the final result contains only one pair, the expressions should not call cons more than once, or call list in such a way that it generates more than one pair.

For partial credit, you may omit support for vectors.

Your implementation should work on the SEASnet installation of PLT MzScheme 360. To run this program, you can prepend /usr/local/cs/bin to your PATH, e.g., by appending the following lines to your $HOME/.profile file if you use bash or ksh:

export PATH=/usr/local/cs/bin:$PATH

or the following line to your $HOME/.login file if you use tcsh or csh:

set path=(/usr/local/cs/bin $path)

The command mzscheme -v should output the following text:

Welcome to MzScheme version 360, Copyright (c) 2004-2006 PLT Scheme Inc.

Submit

Submit four files:

hw5.ss: should contain your definition of expr-returning-mutable, along with any auxiliary definitions.
hw5.txt: should discuss how to modify your implementation so that it supports cycles, shared substructure, boxes, and hash tables. Discuss any changes required to the tiny subset of Scheme used by expressions that expr-returning return, and explain why these changes are necessary. Similarly, discuss and justify any changes needed to either the expr-returning API or the internal functions used in your implementation. If you prefer, you can simply implement support for these extensions in hw5.ss; if so, in hw5.txt you need merely document the use of your extended support.
hw5test.ss: should define and run at least three good tests for expr-returning-mutable. Your tests can assume that recursively-mutable? and test are defined as shown in the examples below.
hw5test-e.ss: should be like hw5test.ss except it should define and run at least four tests for your extended version of expr-returning-mutable, one test for each extension (boxes, hash tables, cycles, shared substructure).

Examples

Here is a test program that you can load. For ease of testing it uses some MzScheme extensions to R5RS Scheme; the first occurrence of each extension is decorated with a hyperlink to the MzScheme manual.

(define (recursively-mutable? x)
  (cond
   ((string? x)
    (not (immutable? x)))
   ((pair? x)
    (and (not (immutable? x))
	 (recursively-mutable? (car x))
	 (recursively-mutable? (cdr x))))
   ((vector? x)
    (and (not (immutable? x))
	 (let rmi? ((i (vector-length x)))
	   (or (zero? i)
	       (let ((i0 (- i 1)))
		 (and (recursively-mutable? (vector-ref x i0))
		      (rmi? i0)))))))
   (else
    #t)))

(define (test obj)
  (let ((expr (expr-returning-mutable obj)))
    (let ((evaluates-to (eval expr (scheme-report-environment 5))))
      (display "Input: ") (write obj) (newline)
      (display "Expression: ") (write expr) (newline)
      (display "Evaluates to: ") (write evaluates-to) (newline)
      (or (recursively-mutable? evaluates-to)
	  (display " not recursively mutable!"))
      (or (equal? obj evaluates-to)
	  (display " not equal?!"))
      (newline))))

(test 0)
(test #t)
(test #\X)
(test 1/3)
(test 'a)
(test '(1 . 2))
(test '(1 2 3))
(test '(1 2 . 3))
(test '(1 2 . ()))
(test '(1 a "b"))
(test '#(1 a "b"))
(test "abc")
(test ''x)
(test '''"")
(test (list "abc" 3 7 (list 'def)))
(test '(3 4 #() #(5 6 (7 8) 9)))
(test '#(() #()))
(test (cons-immutable 0 1))
(test (list-immutable 1 2 'a (cons-immutable '() '())))
(test (vector-immutable 3 4 "x"))

then the output should look something like the following.

Input: 0
Expression: 0
Evaluates to: 0

Input: #t
Expression: #t
Evaluates to: #t

Input: #\X
Expression: #\X
Evaluates to: #\X

Input: 1/3
Expression: 1/3
Evaluates to: 1/3

Input: a
Expression: (quote a)
Evaluates to: a

Input: (1 . 2)
Expression: (cons 1 2)
Evaluates to: (1 . 2)

Input: (1 2 3)
Expression: (list 1 2 3)
Evaluates to: (1 2 3)

Input: (1 2 . 3)
Expression: (cons 1 (cons 2 3))
Evaluates to: (1 2 . 3)

Input: (1 2)
Expression: (list 1 2)
Evaluates to: (1 2)

Input: (1 a "b")
Expression: (list 1 (quote a) (string-copy "b"))
Evaluates to: (1 a "b")

Input: #3(1 a "b")
Expression: (vector 1 (quote a) (string-copy "b"))
Evaluates to: #3(1 a "b")

Input: "abc"
Expression: (string-copy "abc")
Evaluates to: "abc"

Input: (quote x)
Expression: (list (quote quote) (quote x))
Evaluates to: (quote x)

Input: (quote (quote ""))
Expression: (list (quote quote) (list (quote quote) (string-copy "")))
Evaluates to: (quote (quote ""))

Input: ("abc" 3 7 (def))
Expression: (list (string-copy "abc") 3 7 (list (quote def)))
Evaluates to: ("abc" 3 7 (def))

Input: (3 4 #0() #4(5 6 (7 8) 9))
Expression: (list 3 4 (vector) (vector 5 6 (list 7 8) 9))
Evaluates to: (3 4 #0() #4(5 6 (7 8) 9))

Input: #2(() #0())
Expression: (vector (list) (vector))
Evaluates to: #2(() #0())

Input: (0 . 1)
Expression: (cons 0 1)
Evaluates to: (0 . 1)

Input: (1 2 a (()))
Expression: (list 1 2 (quote a) (list (list)))
Evaluates to: (1 2 a (()))

Input: #3(3 4 "x")
Expression: (vector 3 4 (string-copy "x"))
Evaluates to: #3(3 4 "x")