Mon Mar 30 12:52:39 CEST 2009

Shifting the Stage: Staging with Delimited Control

This looks like an interesting next step:


In my own uneducated view, there seems to be a relation between
staging and delimited control.  The goal of staging is to re-order
evaluation so some evaluations can be performed before final code is
generated.  Intermediate data structures (intermediate compuations)
are eliminated.

Now.. A zipper produces some (coroutine style) execution sequencing.
It mainly turns things inside out directed by the shape of a data
structure: data is passed between processes in a way directed by the
data structure, but if the eventual result is not necessary,
re-constructing the structure can be avoided.  This is essentially
deforestation (elimination of intermediate structure, where
intermediate computation is a form of deconstructed intermediate

Now, that's a very vague notion.  Let's try to make it more precise.
Maybe it's the "left fold with abort" that's been mentioned in Oleg's

Let's just write a zipper based on a left (non-recursive) fold.

This leads to:

(define-struct zipper (element state yield))
(define (collection/traverse->zipper collection init-state [fold traverse/fold])
   (fold (lambda (el state)
           (shift k (make-zipper el state k)))

(define (traverse/fold fn init-state lst)
  (let next ((s init-state) (l lst))
    (if (null? l) s
        (let ((s+ (or (fn (car l) s) s)))
          (next s+ (cdr l))))))

The contents of the struct:
  - element: current focus
  - state: state of the output (data structure)
  - yield: state of the input (continuation)

Now, does it make sense to put the input and output state on the same
ground?  In the zipper both input and output state are contained in
the continuation.  Is it possible to write a zipper which has only an
abstract representation of output state (compile-time only) but never
produces any real data:  all we're interested in is how code is
sequenced in the end.

That's another vague notion..

This probably relates to trouble with having to write code in CPS when
staging is involved.