;; OBSOLETE

;; was a nice experiment, but i have a much simpler text book solution
;; now: multipass with phase error detection.

(module relaxation mzscheme

  ;; To solve the relaxation problem, we let cells pass messages to
  ;; each other. There are 2 thing to tell a cell:

  ;;  -> to move
  ;;  -> to update

  ;; That's simple enough, these messages lead to more messages until
  ;; everybody is happy. But there are some complications.

  ;; * To ensure a simple termination proof: only expand in one
  ;;   direction, and limit the expansion. That way it stops before or
  ;;   at the maximal expansion. Say: grow code towards increasing
  ;;   addresses, and replace 1 word by 2 word instructions only.

  ;; * If multiple chunks are cross-linked, assume they wil never
  ;;   overlap.

  ;; * If an expansion of a high address cell leads to the expansion
  ;;   of a low addres cell in the same chunk, the former expansion
  ;;   can be pre-empted.

  

  ;; A cell has..
  (define-struct cell
    (address   
     assemble ;; thunk to recompute the payload
     payload  ;; result of evaluating update = list
     clients  ;; list of cells that depend on this cell's address
     next     ;; cell that will feel our address/size change
     ))

  ;; Tell a cell it has moved, which will make it reassemble itself,
  ;; and tell the next cell in line.

  (define (cell-move c address)
    (let ((payload ((cell-assemble c))))
      (set-cell-payload! c payload)
      (set-cell-address! c address)
      (let ((next (cell-next c)))
        (when next
          (cell-move
           next
           (+ address
              (length payload)))))))

  ;; Tell a cell to update, which will make it recompute its payload
  ;; and tell its dependencies to update and move if the payload size
  ;; changed.
  
  (define (cell-update c)
    (let* ((payload     (cell-payload))
           (new-payload ((cell-assemble)))
           (new-length  (length new-payload)))
      
      (set-cell-payload! c payload)
      (unless
          (and payload
               (= (length payload)
                  (length new-payload)))
        
        (for-each cell-update
                  (cell-clients c))
        
        (cell-move (cell-next c)
                   (+ (cell-address c))))))


  ;; Is this correct? Some tests: an update of cell A can trickle down
  ;; to lead to another update of cell A. Is this a problem? Doesn't
  ;; look like it: a cell might be updated multiple times, but since
  ;; there's no data passed, the update cannot be invalid.
      
  ;; So is this somehow efficient? What we want to avoid is to compute
  ;; updates that will be immediately overwritten, or to compute the
  ;; same update several times.

  ;; It does look to me that oscillations cannot be rulesd out: it
  ;; might be necessary to limit the size change of cells to one
  ;; direction to prevent this. Let's see. If the only event
  ;; 'generator' is for a cell to grow bigger, can this result in
  ;; another one growing smaller?

  ;; Some speedup: each cell could be equipped with a closure that
  ;; recomputes it during the first assembly pass, this way lookup has
  ;; to be done only once. This could eliminated re-computation of
  ;; opcodes independent from the set of possibly changing labels.
  ;; 
  
  
  ;; The problem is: must not notify clients that are in a direct
  ;; causal 'move' path because they might shrink and start an
  ;; oscillation.. This is not so trivial after all..





  ;; Initialization:
  
  ;; Before the relaxation algorithm runs, a symbol table is built
  ;; which associates labels to cells, but the cell addresses
  ;; themselves are not initialized. If the 'assemble' instruction
  ;; needs to lookup a label, but fails, it needs to produce the
  ;; shortest (most optimistic) instruction. Assembly will be
  ;; restarted from the moment the label gets a value.


              
  )