Recursive data structures are broken

[pdarragh]

Related to #10.

The ziggy bits->value functions recurse without pause. Consider the case for vectors in Hoax:

https://github.com/cmsc430/www/blob/d6fbb58e6062b6723a159a168b48cff128d542cc/ziggy/src/types.rkt#L44-L50

I think bits->value could be reworked to include a map from addresses to reconstituted values so we can reconstruct cyclical heap-allocated data structures.

Depending on how complex the final implementation is, it might give us an opportunity to talk about cyclical data structures explicitly in the course.

[dvanhorn]

This came up again recently, so I thought I'd sketch how you might implement this. The idea is bits->value has to maintain a map from addresses to values. If there's a miss, you partially initialize the value, update the map, recur, then set the results.

Here is a sketch:

#lang racket
(require racket/undefined)

;; type Values =
;; | ...
;; | (box-ptr Nat)
;; | (vect-ptr Nat)

(struct box-ptr (a))
(struct vect-ptr (a))

(define mem
  (make-vector 10000 #f))

(define (mem-ref a)
  (vector-ref mem a))

(define (mem-ref-list a n)
  (match n
    [0 '()]
    [i (cons (mem-ref a)
             (mem-ref-list (add1 a) (sub1 n)))]))

(define (bits->value b)
  (define t (make-hash))
  (define (recur b)
    (match b
      [(box-ptr a)
       (hash-ref t a
                 (λ ()
                   (let ((v (box undefined)))
                     (hash-set! t a v)
                     (set-box! v (recur (mem-ref a)))
                     v)))]
      [(vect-ptr a)
       (hash-ref t a
                 (λ ()
                   (let ((v (make-vector (mem-ref a) undefined)))
                     (hash-set! t a v)
                     (for ([v* (in-list (map recur (mem-ref-list (add1 a) (mem-ref a))))]
                           [i (in-naturals)])
                       (vector-set! v i v*))
                     v)))]
      [_ b]))
  (recur b))

;; Create #0='#(1 2 #0#)
(vector-set! mem 0 3)
(vector-set! mem 1 1)
(vector-set! mem 2 2)
(vector-set! mem 3 (vect-ptr 0))

(bits->value (vect-ptr 0))

This will solve the issue of cyclic data in tests and running examples in Racket, but you'd need to do something similar to implement the graph printing in the RTS, which is fine, but also will be a pain because C. Perhaps as a first step we do the above and let the RTS loop while printing cyclic data.