Sat Jun 21 14:53:40 CEST 2008

Parsing combinators.

A lot of code in Staapl is about converting one datastructure into
another one. Serializing one is simple, but collecting into another
seems more difficult.

Upto now I've been using manual stack manipulation to collect data
structures. Is there a better way to tackle this?

Almost always this is insertion into trees + postprocessing

Let's see..

stack levels
1 -> push            (a b c) -> (x a b c)
2 -> push + push'    ((a b c) (d e f)) -> ((x a b c) (d e f))
                                       -> ((x) (a b c) (d e f))

Let's start with a simple list-of-list parser with the operations:


I tried it with vectors:

;; ----

#lang scheme/base
(require "list.ss")

(define (llp-push-level! v n x)
  (let ((stack (vector-ref v n)))
    (vector-set! v n (cons x stack))))

;; (llp-move! v n x)  push x to stack n
;; (llp-move! v n)    push stack n-1 to stack n
(define (llp-move! v n
             [x (let* ((n- (- n 1))
                       (x- (vector-ref v n-)))
                  (vector-set! v n- '()) ;; move to x
  (llp-push-level! v n x))

(define (llp-push! v x)
  (llp-move! v 0 x))

(define (llp-compact! v n)
  (for ((i (in-range n)))
       (llp-move! v (add1 i))))

(define (make-llp n)
  (make-vector n '()))

(define v (make-llp 3))

;; ----

But it's probably better to just use lists, since the operations
themselves are simple tree operations.

push:    (a b ...) -> ((x . a) b ...)
compact: (a b ...) -> (() (a . b) ...)

this becomes:

;; ----

;; Stack of stacks.
(define (make-sos n)
  (for/list ((i (in-range n))) '()))

;; Convert a collapsed sos to a list of lists, applying an operation
;; to each list level.
(define (sos->lol sos [op reverse])
  (let ((dim-1 (- (length sos) 1)))
    (let down ((l (list-ref sos dim-1))
               (n dim-1))
      (if (zero? n)
          (op l)
          (op (map (lambda (le) (down le (- n 1)))

(define (sos-push sos x)
  (cons (cons x (car sos))
        (cdr sos)))

(define (sos-collapse sos n)
  (if (zero? n)
      (cons '()
             (sos-push (cdr sos)
                       (car sos))
             (- n 1)))))

;; ----