[plt-scheme] How to make unit functors?

From: Jens Axel Søgaard (jensaxel at soegaard.net)
Date: Sat May 24 19:44:49 EDT 2003

I am interested in making functors between units with different
signatures, but importing modules with the same signatures.
In order to show where I have problems, I have made this
concrete example. It got a little longer than intended, but
on the bright side, it ought to be clear.

Everything below is ready to be pasted into DrScheme.

/Jens Axel Søgaard

; To sum up: How do I define this functor?

;  simple-set->set : simple-set-unit-importing-list ->

; The goal of this example is to implement set using lists.
; The implementation of sets shall be independent of the concrete
; choice of list implementation. Thus we need a signature for lists:

(define-signature list^

; Of course we also need a concrete implementation in our examples.

(define primitive:cons cons)
(define builtin-list@
  (unit/sig list^

    (define empty '())
    (define (member? x l)
      (if (member x l) #t #f))
    (define cons primitive:cons)))

; Now we specify what we mean by a set:

(define-signature set^
  (empty         ;  empty            =  {}
   insert1       ; (insert1 x A)     =  A U {x}
   insert        ; (insert A x1 ...) =  A U {x1, ...}
   member?       ; (member x A)      =  (x in A)

; Given a list implementation it is easy to define a concrete
; implementation.

(define list-set@
  (unit/sig set^
    (import (list : list^))

    (define empty   list:empty)
    (define member? list:member?)
    (define insert1 list:cons)
    (define (insert s . xs)
      (foldl list:cons s xs))))

; To use such a set implementation we need to link the
; set implementation with a concrete list implemenation.
; The result is a concrete set-implementation.

(define (instantiate-list-set set-importing-list@ list@)
    (link (LIST : list^   (list@))
          (SET  : set^    (set-importing-list@ LIST)))
    (export (open SET))))

(define set-using-builtin@ (instantiate-list-set list-set@ builtin-list@))

; To use the set we need to export the names of list-set@ to the
; This could be done directly with namespace-variable-bind/invoke-unit/sig,
; for convenience we define a macro called use-set.

(define-syntax use-set
  (syntax-rules ()
    [(use-queue set-unit)        (namespace-variable-bind/invoke-unit/sig
set^ set-unit)]
    [(use-queue set-unit prefix) (namespace-variable-bind/invoke-unit/sig
set^ set-unit prefix)]))

; Now we can test our implementation.

(use-set set-using-builtin@)

; > (insert empty 1 2 3)
; (3 2 1)
; > (member? 3 (insert empty 1 2 3))
; #t
; > (member? 7 (insert empty 1 2 3))
; #f

; So far everything works as expected.
; Now consider that the definition of insert:

;  (define (insert s . xs)
;       (foldl list:cons s xs))

; We note that the definition does not depend upon
; the chosen representation os sets (as lists).
; If we implement sets in other ways we can use
; this definition again. To share code we define
; a simple set as

; Simple Set
(define-signature simple-set^
  (empty         ;  empty        =  {}
   insert1       ; (insert1 x A) =  A U {x1}
   member?       ; (member? x A) = (x in A)

; and given a functor simpler-set->set we can turn
; an implementation os a simple-set into an implementation
; of a set.

; First let us implement a simple-set.

(define list-simple-set@
  (unit/sig simple-set^
    (import (list : list^))

    (define empty   list:empty)
    (define member? list:member?)
    (define insert1 list:cons)))

; As before we need to instantiate and use it.

(define (instantiate-list-simple-set simple-set-importing-list@ list@)
    (link (LIST   : list^       (list@))
          (SIMPLE : simple-set^ (simple-set-importing-list@ LIST)))
    (export (open SIMPLE))))

(define-syntax use-simple-set
  (syntax-rules ()
    [(use-queue unit)        (namespace-variable-bind/invoke-unit/sig
simple-set^ unit)]
    [(use-queue unit prefix) (namespace-variable-bind/invoke-unit/sig
simple-set^ unit prefix)]))

; Just to make sure, we test it:

(use-simple-set (instantiate-list-simple-set list-simple-set@
; > empty
; ()
; > (insert1 42 empty)

; The goal was to make a functor simple-set->set. With such a functor
; the instantiate-simple-set and use-simple-set are not needed.
; One can simply do this to instantiate a set.

; (use-set (instantiate-list-set (simple-set->set list-simple-set@)

; Here is my attempt to define the functor, but as you probably have
; guessed it doesn't work:

;(define (simple-set->set simple@)
;  (compound-unit/sig
;    (import (list : list^))
;    (link   (LIST   : list^        (list))
;            (SIMPLE : simple-set^  (simple@ list)))
;    (define empty   simple:empty)
;    (define member? simple:member?)
;    (define insert1 simple:insert1)
;    (define (insert s . xs)
;      (foldl simple:insert1 s xs))))

; (use-set (instantiate-list-set (simple-set->set list-simple-set@)
; empty
; (insert empty 1 2 3)

; The problem is how to specify that I want to link the imported list to the
; implementation of simple-set.

Posted on the users mailing list.