[plt-scheme] polymorphism of primitive types

On Mon, 17 Oct 2005, Yoav Goldberg wrote:

> I would really like to be able treat my own sequential data (such as
> streams, or trees) as lists, ie, to have "car" "cdr" "map" "list-ref"
> "length" etc work on regular lists as well as on streams (and the other
> relevant data types).

Hi Yoav,

One possible way to write generic code is to use units.  It's not
polymorphism, since there's no run-time type dispatch going on.  Units
behave more like C++ templates, and it's often enough to do this at
compile-time rather than with the full power of polymorphism.

I've started to write a small tutorial on units that might be helpful:

    http://hkn.eecs.berkeley.edu/~dyoo/plt/unit-notes.text


Here's an example that shows how we might use units to write templated
code.  Just as a caveat: I'm somewhat of a PLT Scheme newbie, so this code
is probably rough and non-idiomatic.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(module sequence mzscheme
  (require (lib "unitsig.ss"))
  (provide (all-defined))

  ;; Every "sequence" needs to support the following:
  (define-signature sequence^ (ref len))

  ;; search^ provides a single search function.
  (define-signature search^ (search))

  ;; One possible implementation of a sequence is with lists:
  (define list-sequence@
    (unit/sig sequence^
      (import)
      (define ref list-ref)
      (define len length)))

  ;; Another possible implementation might use vectors:
  (define vector-sequence@
    (unit/sig sequence^
      (import)
      (define ref vector-ref)
      (define len vector-length)))

  ;; And here's our general algorithm for doing searches on any sequence^.
  (define linear-search@
    (unit/sig search^
      (import sequence^)
      (define (search seq key)
        (let ((n (len seq)))
          (let loop ((k 0))
            (if (< k n)
                (if (equal? key (ref seq k))
                    k
                    (loop (add1 k)))
                (error 'search "~a not found" key)))))))

  ;; We define a convenience method to get at the essential "search"
  ;; function, given a sequence at .
  (define (make-linear-search sequence@)
    (let ((extractor@
           (unit/sig () (import search^) search)))
      (invoke-unit/sig
       (compound-unit/sig
         (import)
         (link (SEQ : sequence^ (sequence@))
               (SEARCH : search^ (linear-search@ SEQ))
               (EXTRACT : () (extractor@ SEARCH)))
         (export)))))

  ;; Here are concrete instantiation of linear-search functions for lists
  ;; and vectors:
  (define list-linear-search (make-linear-search list-sequence@))
  (define vector-linear-search (make-linear-search vector-sequence@)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



For example:

;;;;;;
> (require "sequence.ss")
> (list-linear-search '(mal inara jayne book) 'river)
search: river not found
> (list-linear-search '(mal inara jayne book) 'book)
3
> (list-linear-search '(mal inara jayne book) 'inara)
1
> (vector-linear-search '#(mal inara jayne book) 'inara)
1
> (vector-linear-search '#(mal inara jayne book) 'mal)
0
> (vector-linear-search '#(mal inara jayne book) 'kaylee)
search: kaylee not found
;;;;;;

So we're able to define a general algorithm --- linear scan --- and create
concrete instances of that search that work on both vectors and lists and
probably with whatever "sequence-like" thing we'd like linear search to
work on.  This particular example shows how we can use units as
"functors".

The code above is a little syntatically clumsy; I think the new unit
system described in Syntactic Abstraction in Component Interfaces:

    http://www.cs.utah.edu/~sowens/pubs/sigmacros.ps

should make this easier to type.


> __iter__() and next() methods, and you can use it anywhere you would use
> a list. Very handy. What's the best way to achieve the same effect in
> MzScheme? (what's the most efficient way to achieve the polymorphism,
> and what is the minimal set of functions I'll be required to implement
> for each new type?)

A lot of stuff that's hardcoded in Python isn't built into PLT Scheme.
If we really wanted to take a true polymorphic approach, we can pull out
the essential features of Python's sequence protocol:

    http://www.python.org/doc/ref/sequence-methods.html

and develop a similar protocol within PLT Scheme's class system.


Best of wishes!