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 generate objects that rely on shared structure. Here is a simple example of such an object:
> (define zeros (cons 0 '())) > zeros (0) > (set-cdr! zeros zeros) > zeros #0=(0 . #0#) > (car zeros) 0 > (car (cdr zeros)) 0 > (car (cdr (cdr zeros))) 0 > (car (cdr (cdr (cdr zeros)))) 0
Here, zeros consumes only one pair, but represents an infinitely-long list of zeros. ASE's programs often generate such objects, print them, and read them back in.
This technique works fine for MzScheme, since it supports input and output of Common LISP-style graphs as described in §11.2.5.1 of the MzScheme manual, if you use MzScheme's print-graph function as described in §7.9.1.4. However, this behavior is an extension to Scheme, and you would like to port your programs to other Scheme implementations that do not support graphs.
One way to do this would be to write a library for doing graph input and output. But that would be a hassle, since you'd need to rely on the library being present on all the platforms you port to. Your boss suggests a different approach: modify the ASE programs so that, instead of outputting an expression representing a graph, they output a portable expression, that, when executed, will generate the graph. He asks you to investigate the feasibility of this approach. However, he suggests that you limit yourself to a tiny subset of Scheme in your generated expressions, to avoid any further portability problems.
Write a Scheme function (expr-returning obj) that returns a Scheme expression that, when evaluated, will return a copy of obj, that is, an object that has the same data structure as obj.
Your implementation of expr-returning can assume that its argument contains only booleans, characters, numbers, pairs, symbols, and strings. For example, you need not worry about arguments containing vectors or procedures. You need to worry about sharing only for pairs: for example, don't worry about sharing strings.
The expressions that expr-returning returns should restrict themselves to the following tiny subset of Scheme:
These expressions always return mutable objects. For example, the expression (quote (a b)) is not allowed, as it yields an immutable object.
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 turn in an implementation that works only for objects that do not share (e.g., the first five tests shown below). For more partial credit, you may turn in an implementation that works only for objects that do not contain cycles (e.g., the tests below that do not rely on set-car! or set-cdr!.
Submit three files:
If you load the following program:
(define (test obj)
(let ((expr (expr-returning obj)))
(let ((evaluates-to (eval expr (scheme-report-environment 5)))
(pg (print-graph)))
(print-graph #t) (display "Input: ") (write obj) (newline)
(print-graph #f) (display "Expression: ") (write expr) (newline)
(print-graph #t) (display "Evaluates to: ") (write evaluates-to) (newline)
(newline)
(print-graph pg))))
(test 0)
(test '(a . b))
(test '(a b))
(test ''a)
(test '(a #f #\c (27 "x")))
(define ab '(a b))
(test (list ab 1 (list ab 2)))
(define abc (list ab 'c))
(test (cons ab abc))
(test (cons abc ab))
(define zeros (cons 0 '()))
(set-cdr! zeros zeros)
(test zeros)
(define infinite-tree (cons 0 0))
(set-car! infinite-tree infinite-tree)
(set-cdr! infinite-tree infinite-tree)
(test infinite-tree)
(define mutually-recursive (list (list 1 2) (list 3 4)))
(set-car! (cdr (car mutually-recursive))
(car (cdr mutually-recursive)))
(set-car! (cdr (car (cdr mutually-recursive)))
(car mutually-recursive))
(test mutually-recursive)
then the output should look something like the following.
Input: 0 Expression: 0 Evaluates to: 0 Input: (a . b) Expression: (cons (quote a) (quote b)) Evaluates to: (a . b) Input: (a b) Expression: (cons (quote a) (cons (quote b) (quote ()))) Evaluates to: (a b) Input: (quote a) Expression: (cons (quote quote) (cons (quote a) (quote ()))) Evaluates to: (quote a) Input: (a #f #\c (27 "x")) Expression: (cons (quote a) (cons #f (cons #\c (cons (cons 27 (cons "x" (quote ()))) (quote ()))))) Evaluates to: (a #f #\c (27 "x")) Input: (#0=(a b) 1 (#0# 2)) Expression: (let ((e (cons (cons (quote a) (cons (quote b) (quote ()))) (cons 1 (cons (cons #f (cons 2 (quote ()))) (quote ())))))) (set-car! (car (cdr (cdr e))) (car e)) e) Evaluates to: (#0=(a b) 1 (#0# 2)) Input: (#0=(a b) #0# c) Expression: (let ((e (cons (cons (quote a) (cons (quote b) (quote ()))) (cons #f (cons (quote c) (quote ())))))) (set-car! (cdr e) (car e)) e) Evaluates to: (#0=(a b) #0# c) Input: ((#0=(a b) c) . #0#) Expression: (let ((e (cons (cons (cons (quote a) (cons (quote b) (quote ()))) (cons (quote c) (quote ()))) #f))) (set-cdr! e (car (car e))) e) Evaluates to: ((#0=(a b) c) . #0#) Input: #0=(0 . #0#) Expression: (let ((e (cons 0 #f))) (set-cdr! e e) e) Evaluates to: #0=(0 . #0#) Input: #0=(#0# . #0#) Expression: (let ((e (cons #f #f))) (set-cdr! e e) (set-car! e e) e) Evaluates to: #0=(#0# . #0#) Input: (#0=(1 #1=(3 #0#)) #1#) Expression: (let ((e (cons (cons 1 (cons (cons 3 (cons #f (quote ()))) (quote ()))) (cons #f (quote ()))))) (set-car! (cdr e) (car (cdr (car e)))) (set-car! (cdr (car (cdr (car e)))) (car e)) e) Evaluates to: (#0=(1 #1=(3 #0#)) #1#)
In the above output, the Expression: line is only one of several possible answers. For example, (quote 0) is an alternative solution to the first test case is, and (list (quote a) (quote b)) is an alternative solution to the third test case. It doesn't matter which solution your implementation generates, so long as it satisfies the constraints described above.