Sun Jan 23 12:16:28 EST 2011

State space form: draft logic

  (define dict make-hash)   ;; use mutable hashes throughout
  (define (false . _) #f)
  (define (keys d) (dict-map d (lambda (k . _) k)))

  (define (bool x) (if x #t #f))
  (define (dict-op logic-op a b)
    (let ((r (dict)))
      (for (((k v) (in-dict a)))
        (when (logic-op (dict-ref b k false))
          (dict-set! r k v)))
  (define (dict-intersect  a b) (dict-op bool a b))
  (define (dict-difference a b) (dict-op not a b))

;; Sate space model: automatic connect & sort.
(define-syntax (state-space-eqs stx)

  ;; Add identifier to dictionary.  Index on symbol, i.e. identifier
  ;; equality is implemented as symbol equality.  Set identifier as
  ;; value to keep track of lexical context.
  (define (id-add! d id)
    (dict-set! d (syntax->datum id) id))

  (define (id-add-rec! d top-expr)
    (let rec! ((expr top-expr))
      (syntax-case expr ()
        ((op . rands)
         (for ((a (syntax->list #'rands))) (rec! a)))
         (id-add! d #'node)))))
  (let ((state (dict))
        (lhs   (dict))
        (rhs   (dict)))
    (syntax-case stx ()
      ((_ . eqs)
         (for ((eq (syntax->list #'eqs)))
           (syntax-case eq ()
             ((var expr)
                (id-add!     lhs #'var)
                (id-add-rec! rhs #'expr)))))
         (let* ((state (dict-intersect  lhs rhs))
                (in    (dict-difference rhs state))
                (out   (dict-difference lhs state)))
           #`'((in    #,(keys in))
               (out   #,(keys out))
               (state #,(keys state)))))))))

;; test
 (y (+ a b))
 (z (* y y)))

=> ((in (a b)) (out (z)) (state (y)))


The principle is simple:

  * Build 2 dictionaries of LHS + RHS variables (RHS requires tree

  * From these, build 3 dictionaries of state, in, out as:

       state = LHS ^ RHS
       in    = RHS \ state
       out   = LHS \ state

  * Find a way to impedance-match to ordinary Scheme expressions.

       - Explicit I/O spec
       - Keywords
       - Lexical order
       - Order of occurance

The logic operations on the dicts might be reused from a library.