[plt-scheme] How to make unit functors?
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 ->
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^
(empty
cons
member?))
; Of course we also need a concrete implementation in our examples.
(define primitive:cons cons)
(define builtin-list@
(unit/sig list^
(import)
(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@)
(compound-unit/sig
(import)
(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
environment.
; This could be done directly with namespace-variable-bind/invoke-unit/sig,
but
; 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@)
(compound-unit/sig
(import)
(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@
builtin-list@))
; > 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@)
builtin-list@))
; 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@)
builtin-list@))
; empty
; (insert empty 1 2 3)
; The problem is how to specify that I want to link the imported list to the
given
; implementation of simple-set.