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 via the (rnrs mutable-pairs (6)) library. Here is a simple example of a program that generates and prints these objects:
(import (rnrs) (rnrs mutable-pairs (6))) (define zeros (cons 0 '())) (write zeros) (newline) (set-cdr! zeros zeros) (write zeros) (newline) (write (car zeros)) (newline) (write (car (cdr zeros))) (newline) (write (car (cdr (cdr zeros)))) (newline) (write (car (cdr (cdr (cdr zeros))))) (newline)
If you put the above program into a file t.scm, and run the shell command plt-r6rs hw5-test.scm (using the plt-r6rs command of Racket), the output will be the following:
(0) #0=(0 . #0#) 0 0 0 0
The first two lines of output are the values of zeros before and after set-cdr! was invoked. Initially, zeros is a singleton list containing 0. But after set-cdr!, it is a circular data structure that 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 Racket, since it supports input and output of Common LISP-style graphs as described in §12.6.16 of the Racket manual. 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 implementation of expr-returning should restrict itself to side-effect-free Scheme that uses only the features of the (rnrs base (6)) library. This is partly because we want to keep this assignment simple, and partly because the base library contains Scheme's core features and should be a focus of your study.
The expressions that expr-returning returns should restrict themselves to the following tiny subset of Scheme:
These expressions should always return mutable objects. For example, your code should not return the expression '(a b), 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:
(library (expr-returning) (export expr-returning) (import (except (rnrs base (6)) set! vector-set! vector-fill!)) ;; Put your implementation here. ;; It should define expr-returning, along with any other identifiers ;; that it needs internally. It should be free of side effects. )It should be possible to install your library into your personal Racket collection by using the following shell command:
plt-r6rs --install --force expr-returning.scm
We will test your program on the Racket 5.0.2 installation on the SEASnet Linux servers under /usr/local/cs/bin.
If the following program is in the file hw5test.scm:
(import (rnrs)
(rnrs eval (6))
(rnrs mutable-pairs (6))
(expr-returning)
(only (racket base) print-graph))
(define tiny-subset-of-Scheme
(environment '(only (rnrs base (6)) quote cons car cdr list lambda)
'(only (rnrs mutable-pairs (6)) set-car! set-cdr!)))
(define (test obj)
(let ((expr (expr-returning obj)))
(let ((evaluates-to (eval expr tiny-subset-of-Scheme))
(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)
and if your code has been installed with "plt-r6rs --install --force expr-returning.scm" as described above, then the output of "plt-r6rs hw5test.scm" should look something like the following.
Input: 0 Expression: 0 Evaluates to: 0 Input: (a . b) Expression: (cons 'a 'b) Evaluates to: (a . b) Input: (a b) Expression: (cons 'a (cons 'b '())) Evaluates to: (a b) Input: 'a Expression: (cons 'quote (cons 'a '())) Evaluates to: 'a Input: (a #f #\c (27 "x")) Expression: (cons 'a (cons #f (cons #\c (cons (cons 27 (cons "x" '())) '())))) Evaluates to: (a #f #\c (27 "x")) Input: (#0=(a b) 1 (#0# 2)) Expression: ((lambda (e) (set-car! (car (cdr (cdr e))) (car e)) e) (cons (cons 'a (cons 'b '())) (cons 1 (cons (cons #f (cons 2 '())) '())))) Evaluates to: (#0=(a b) 1 (#0# 2)) Input: (#0=(a b) #0# c) Expression: ((lambda (e) (set-car! (cdr e) (car e)) e) (cons (cons 'a (cons 'b '())) (cons #f (cons 'c '())))) Evaluates to: (#0=(a b) #0# c) Input: ((#0=(a b) c) . #0#) Expression: ((lambda (e) (set-cdr! e (car (car e))) e) (cons (cons (cons 'a (cons 'b '())) (cons 'c '())) #f)) Evaluates to: ((#0=(a b) c) . #0#) Input: #0=(0 . #0#) Expression: ((lambda (e) (set-cdr! e e) e) (cons 0 #f)) Evaluates to: #0=(0 . #0#) Input: #0=(#0# . #0#) Expression: ((lambda (e) (set-cdr! e e) (set-car! e e) e) (cons #f #f)) Evaluates to: #0=(#0# . #0#) Input: (#0=(1 #1=(3 #0#)) #1#) Expression: ((lambda (e) (set-car! (cdr e) (car (cdr (car e)))) (set-car! (cdr (car (cdr (car e)))) (car e)) e) (cons (cons 1 (cons (cons 3 (cons #f '())) '())) (cons #f '()))) Evaluates to: (#0=(1 #1=(3 #0#)) #1#)
In the above output, the Expression: line is only one of several possible answers. For example, '0 is an alternative solution to the first test case is, and (list 'a '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.