apf-lib


Traversal-based Generic Programming in Scheme

Implementation and Examples



apf-lib is our Scheme implementation of AP-F, the ideas behind DemeterF.

The implementation includes a generic traversal that is extended with sets of functions. A data definition language allows concrete syntax for use with a custom dynamic parser to build structures.

Our generic traversal currently uses structural reflection found in MzScheme, though using another data representation would require only a few functions to be rewritten.

The sources include a couple test files with traversal examples. Also see some smaller examples below.

Source: apf-lib.tgz

Browsable Source: APF Src

Slides from an older talk: apf-slides.pdf



Examples: Just a few for now... More to come.

Here's multi-dimensional map

(require "apf.scm")

;; map-t : (number -> Y) [listof number] -> [listof Y]
(define (map-t n->y lon)
  (traverse lon (union-TP [(number) (n) (n->y n)])))

(map-t add1 '(1 2 3))               ;; ==> '(2 3 4)
(map-t sub1 '(1 2 3))               ;; ==> '(0 1 2)
(map-t add1 '(1 ((2)) (((3 (4)))))) ;; ==> '(2 ((3)) (((4 (5)))))
        

And some tree definitions/functions

(require "apf.scm")

;; Trees
(def-sum  tree [node leaf])
(def-prod leaf ["*"])
(def-prod node ["(" (data number)
                    (left tree)
                    (right tree) ")"])

;; tree->string: tree -> string
;;   Convert a tree into a string...
(define (tree->string t)
  (traverse t (union-id [(number) (n) (number->string n)]
                        [(leaf) (l) ""]
                        [(tree string string string)
                         (t d lt rt) (string-append "[" d lt rt "]")])))

;; tree-incr : tree -> tree
;;   Increment each data element in the given tree
(define (tree-incr t)
  (traverse t (union-TP [(number) (n) (add1 n)])))

(define names '("zero" "one" "two" "three" "four" "five"
                "six" "seven" "eight" "nine" "ten"))

;; tree-strs : tree -> tree
;;   Replace each data element by its English word
(define (tree-strs t) 
  (traverse t (union-TP [(number) (n) (list-ref names n)])))

;; tree-rev : tree -> tree
;;   Reverse all the data elements in the tree
(define (tree-rev t)
  (traverse t (union-TP [(node object tree tree)
                         (n d lt rt) (node d rt lt)])))

;; tree-height : tree -> number
;;   Calculate the height of the given tree
(define  (tree-height t)
  (traverse t (union-id [(leaf) (l) 0]
                        [(node object number number)
                         (n d lt rt) (add1 (max lt rt))])))

;; A tree instance
(define a-tree (parse-string 'tree "(3 (1 (0 * *) (2 * *)) (5 (4 * *) *))"))

;; A few tests...
(tree->string a-tree)             ;; ==> "[3[2[0][2]][5[4]]]"
(tree->string (tree-incr a-tree)) ;; ==> "[4[2[1][3]][6[5]]]"
(tree->string (tree-strs a-tree)) ;; ==> "[three[one[zero][two]][five[four]]]"
(tree->string (tree-rev a-tree))  ;; ==> "[3[5[4]][1[2][0]]]"
(tree-height a-tree)              ;; ==> 3