SICP Ch5 eceval compiler in Racket: set-cdr! into quoted list (not a dup)

Question

This is not a duplicate of set-car!, set-cdr! unbound in racket? or of Implement SICP evaluator using Racket or of How to install sicp package module in racket?, but rather a follow-up question because the solutions proposed therein do not work for me. First, the need: Section 5.5.5 of SICP, the compiler plus explicit-control evaluator (code here in "ch5-eceval-compiler.scm"), are entirely dependent on set-car! and set-cdr! into explicit quoted lists. I would like to copy and modify this code without a complete, bottom-up rewrite in immutable form. I'd also accept a reference to a scheme implementation that can run the code out-of-the-box or with some minimal, straightforward adaptation, i.e., a scheme that has set-car! and set-cdr! or some work-around. Neither guile nor racket give me an easy time running this code.

EDIT: mit scheme will load the eceval compiler. I'm leaving the question up for those who might want to get it going in racket (I would rather, for example).

Here is a deeper explanation, including the things I explored and tried out, and how I diagnosed the quoted list as the deepest problem. When I hand-converted the quoted list into an mquoted nest of mlists, the code broke in much worse ways and the rabbit hole got much deeper. I had to revert after a couple of hours of delicate brain surgery that failed.

Here is an MVE of the kind of structure that section 5.5.5 relies on. This is small, but structurally like the real thing:

(define foo '(a b))
(set-cdr! foo '(c))

The real thing starts like this:

(define eceval
  (make-machine
   '(exp env val proc argl continue unev
     compapp            ;*for compiled to call interpreted
     )
   eceval-operations ;;   ----------------------------------------------
  '(  ;; <<<<<<<<======== BIG QUOTED LIST CAUSING TROUBLE / NOT MCONSES!
;;SECTION 5.4.4, as modified in 5.5.7 ;; -------------------------------
;;*for compiled to call interpreted (from exercise 5.47)
  (assign compapp (label compound-apply))
;;*next instruction supports entry from compiler (from section 5.5.7)
  (branch (label external-entry))
read-eval-print-loop
  (perform (op initialize-stack))
  (perform
   (op prompt-for-input) (const ";;; EC-Eval input:"))
...

and goes on for quite a while. The evaluator is the "machine-code" in the quoted list, and various generated code does set-car! and set-cdr! into registers and environment frames and other things. The code fails on load.

There seems to be no easy way to convert the evaluator into immutable form without a full rewrite, and I'm trying to avoid that. Of course, set-car! and set-cdr! are not available in #lang racket, and I don't think they're in guile, either (at least guile refused to load "ch5-eceval-compiler.scm," throwing a mutability error, on which I did not dig deeper).

One solution proposed in set-car!, set-cdr! unbound in racket? is to rewrite the code using mcons, mcar, mlist, etc. according to (require compatibility/mlist) (require rnrs/mutable-pairs-6). Those compatibility packages have no replacement for quote, so I tried writing my own mquote. I spent a couple of hours on such a refactoring, but the exercise was not converging, just going deeper and deeper down the rabbit hole and ending up with even deeper problems. It seems that to pursue even a refactoring I must understand more semantics about "ch5-eceval-compiler.scm," and if I must, I might as well rewrite it in immutable form.

Easier solutions proposed in set-car!, set-cdr! unbound in racket? are to use #lang sicp or #lang r5rs. There follows three experiments that referenced other answers on stack overflow:

#lang r5rs
(define foo '(a b))
(set-cdr! foo '(c))
foo

Error: struct:exn:fail:contract:variable

set-cdr!: undefined;
 cannot reference an identifier before its definition
  in module: "/usr/share/racket/pkgs/r5rs-lib/r5rs/main.rkt"
             -----------------------------------------------

which points to a place where set-cdr! is clearly defined:

...
(module main scheme/base
  (require scheme/mpair
           racket/undefined
           (for-syntax scheme/base syntax/kerncase
                       "private/r5rs-trans.rkt")
           (only-in mzscheme transcript-on transcript-off))

  (provide (for-syntax syntax-rules ...
                       (rename-out [syntax-rules-only #%top]
                                   [syntax-rules-only #%app]
                                   [syntax-rules-only #%datum]))
           (rename-out
            [mcons cons]
            [mcar car]
            [mcdr cdr]
            [set-mcar! set-car!] ;; --------------------------
            [set-mcdr! set-cdr!] ;; <<<<<<<<======== LOOK HERE
            [mpair? pair?]       ;; --------------------------
            [mmap map]
            [mfor-each for-each])
           = < > <= >= max min + - * /
           abs gcd lcm exp log sin cos tan not eq?
           call-with-current-continuation make-string
           symbol->string string->symbol make-rectangular
           exact->inexact inexact->exact number->string string->number
...

Here is a similar failure with #lang sicp

#lang sicp
(define foo '(a b))
(set-cdr! foo '(c))
foo

Error: struct:exn:fail:contract:variable

set-cdr!: undefined;
 cannot reference an identifier before its definition
  in module: "/home/rebcabin/.racket/7.2/pkgs/sicp/sicp/main.rkt"
             ----------------------------------------------------

pointing to code that only indirectly defines set-cdr!, but clearly in the appropriate package:

....
#lang racket

(require racket/provide         ;; --------------------------------------------
         (prefix-in r5rs: r5rs) ;; <<<<<<<<======== PULL IN SET-CDR! ETC. HERE?
         (rename-in racket [random racket:random])) ;; ------------------------

(provide (filtered-out (λ (name) (regexp-replace #px"^r5rs:" name ""))
                       (except-out (all-from-out r5rs) r5rs:#%module-begin))
         (rename-out [module-begin #%module-begin]))

(define-syntax (define+provide stx)
  (syntax-case stx ()
    [(_ (id . args) . body) #'(begin
                                (provide id)
                                (define (id . args) . body))]
    [(_ id expr) #'(begin
                     (provide id)
                     (define id expr))]))
...

I dig deeper into Implement SICP evaluator using Racket and find

(require (only-in (combine-in rnrs/base-6
                              rnrs/mutable-pairs-6)
                  set-car!
                  set-cdr!))
(define foo '(a b))
(set-cdr! foo '(c))
foo

yielding

Error: struct:exn:fail:contract

set-mcdr!: contract violation
  expected: mpair?
  given: '(a b)
  argument position: 1st
  other arguments...:
   '(c)

This error implies that the problem really is the quoted list. I don't have an easy way to make the big quoted list in eceval into an mlist or chain of mcons. I tried it and it's very verbose and error prone, plus I think the code that loads eceval scans and patches that list, so it uses other list operations. I had to revert after going south in a bad way.

Perhaps I missed some way to automate the transformation, a macro, but that's a deeper rabbit hole (my scheme macro-fu is too old).

So I'm stuck. Nothing easy or recommended works. I'd like to either (1) know a scheme implementation that will run this code (2) some way I can implement set-car! and set-cdr! in racket (3) some other kind of work around (4) or maybe I just made a stupid mistake that one of you kind people will easily fix.

Answer 1

I tried (by either running racket directly or running it via DrRacket)

#lang sicp

(define foo '(a b))
(set-cdr! foo '(c))
foo

and it outputs (a c).

This also works:

#lang r5rs

(define foo '(a b))
(set-cdr! foo '(c))
(display foo)

---

To answer your question regarding the implementation of SICP (which I am currently maintaining), you are correct that (prefix-in r5rs: r5rs) will import set-cdr!.

---

Update: I just installed Geiser and now experienced the same problem that you did when I C-c C-b. However, C-c C-a works as expected.

Personally, I would use racket-mode instead of Geiser.

Answer 2

Mit-scheme will load the eceval compiler from the code drop mentioned in the question. On Ubuntu, mit-scheme loads with sudo apt-install mit-scheme. The geiser package of emacs finds mit via run-mit. The problem is solved.