generics-in-scheme.md

Generics in Scheme

In a previous note I demonstrated polymorphism in Scheme using Chez Scheme's compile time values and properties.

The code in that example is pretty raw; you might not want to code each generic in that manner. One approach is to decouple the signature/method table. We can do this by factoring out some code into a 'make-generic' procedure:

(define (make-generic table)
  (lambda (stx)
    (lambda (lookup)
      (syntax-case stx ()
        ((_ param ...)
          (let ((signature (map (lambda (p)
                                  (lookup p (syntax type)))
                                (syntax (param ...)))))
            (let ((proc-name (cdr (assoc signature table))))
              (with-syntax ((proc-syntax (datum->syntax (syntax list) proc-name)))
                (syntax
                 (proc-syntax param ...))))))))))

Now, to define the generic nth from the example, we do:

(define nth-table
  '( ( (vector integer) . vector-ref )
     ( (string integer) . string-ref ) ))

(define-syntax nth (make-generic nth-table))

OK, let's switch gears for a second and talk about functors in Scheme. Here's a fold-left functor for data structures which support operations nth (random access) and size.

(define (make-indexable-fold-left size nth)

  (define (fold-left seq val proc)
    (let ((n (size seq)))
      (let loop ((i 0) (val val))
        (if (>= i n)
            val
            (loop (+ i 1) (proc val (nth seq i)))))))

  fold-left)

For example, to make a vector-fold-left:

(define vector-fold-left (make-indexable-fold-left vector-length vector-ref))

So now, how do we define a generic fold-left? From the functor definition of fold-left, we can see that we'll need generic definitions of nth and size. We defined the generic nth above. Here's size:

(define size-table
  '( ( (vector) . vector-length )
     ( (string) . string-length ) ))

(define-syntax size (make-generic size-table))

Alright, now for our generic fold-left:

(define-syntax fold-left
  (syntax-rules ()
    ((fold-left seq ival proc)
     (let ((n (size seq)))
       (let loop ((i 0) (val ival))
         (define-property i type 'integer)
         (if (>= i n)
             val
             (loop (+ i 1) (proc val (nth seq i)))))))))

Note that while it's based on the functor version, it's a macro. Why's it a macro? So the "types" of the paramaters can "propagate" down into the body of fold-left. This propagation is required so that the generics size and nth can properly dispatch.

Here's an example using the generic fold-left:

> (let ((v0 (vector 10 20 30))
        (s0 "abc"))

    (define-property v0 type 'vector)
    (define-property s0 type 'string)

    (list (fold-left v0 0 +)
          (fold-left s0 #f cons)))
(60 (((#f . #\a) . #\b) . #\c))

The examples here were run in Chez Scheme. Petite Chez Scheme can be downloaded for free.

That just doesn't feel right to me. Bolt something down in a macro if functions can't do the same thing, or for performance reasons.

fold-left-generic can be a function taking nth and size functions and returning fold-left-specialized as a closure. And then fold-left can have a case statement for different types of data types getting dispatched to different fold-left-specialized.

Thoughts?