Pure functional TypeRep [Was: Existentials...]
This message shows how to map _types_ to integers at compile time -- and then extend this facility to run-time so it can be used with existentially-quantified types. It is statically guaranteed that different types receive different integer labels. Unlike TyCons of Dynamics, our mapping does NOT rely on unsafePerformIO. We use the typechecker itself to compare types. It seems our typemap can also be used for _safe_ casts, in particular, for casting away the existential blemish. This message was inspired by Amr Sabry's problem on existentials. Unlike Hal Daume's solution posted here earlier, we do not use Dynamics nor GMap -- therefore, we completely avoid unsafePerformIO and unsafeCoerce. Our solution is purely functional and assuredly type-safe (to the extent the typechecker can be trusted). Extensions used: -fglasgow-exts -fallow-undecidable-instances -fallow-overlapping-instances First, the compile-time mapping from types to integers. Polytypic list:
data Nil t r = Nil data Cons t r = Cons t r
class PList ntype vtype cdrtype where cdr:: ntype vtype cdrtype -> cdrtype empty:: ntype vtype cdrtype -> Bool value:: ntype vtype cdrtype -> vtype
instance PList Nil vtype cdrtype where empty = const True
instance (PList n v r) => PList Cons v' (n v r) where empty = const False value (Cons v r) = v cdr (Cons v r) = r
and the finite map from types to integers
class TypeSeq t s where type_index:: t -> s -> Int
instance (PList Cons t r) => TypeSeq t (Cons t r) where type_index _ _ = 0
instance (PList Cons t' r', TypeSeq t r') => TypeSeq t (Cons t' r') where type_index v s = 1 + (type_index v $ cdr s)
Let us build some finite map
init_typeseq = Cons (undefined::Char) $ Cons (undefined::Int) $ Cons (undefined::Bool) $ Cons (undefined::String) $ Cons (undefined::Maybe Char) $ Nil
A typeseq maps a type to an integer -- which is the type's position in the polytypic list. We are satisfied with the first occurrence of the type in the list. It is plain that a typeseq maps different types to different integers. Let us see how it works: -- *Main> type_index True init_typeseq -- 2 -- *Main> type_index 'a' init_typeseq -- 0 -- *Main> type_index "a" init_typeseq -- 3 -- *Main> type_index (1::Int) init_typeseq -- 1 -- *Main> type_index (Just 'a') init_typeseq -- 4 -- *Main> type_index (Just True) init_typeseq -- <interactive>:1: -- No instance for (TypeSeq (Maybe Bool) (Nil t r)) -- arising from use of `type_index' at <interactive>:1 -- In the definition of `it': type_index (Just True) init_typeseq We call this mapping compile-time because the translation from a type to the corresponding encoding (1+1+...1) is done at compile time, when the appropriate instance of the TypeSeq class is chosen. A sufficiently smart compiler can just as well fold the constant expression (1+1...+1) down to a single integer. Also, errors in the translation are reported at compile-time. However, to apply the mapping to existential types, we need to extend the former to run-time.
class TypeRep t where tr_index:: t -> Int
-- All of the following are almost the same. -- The Template Haskell can really help us here instance TypeRep Char where tr_index x = type_index x init_typeseq
instance TypeRep Int where tr_index x = type_index x init_typeseq
instance TypeRep Bool where tr_index x = type_index x init_typeseq
instance TypeRep String where tr_index x = type_index x init_typeseq
instance TypeRep (Maybe Char) where tr_index x = type_index x init_typeseq
Now, Amr Sabry's Problem
data F a b = forall c. (TypeRep c) => PushF (a -> c) (F c b) | Bottom (a -> b)
f1 :: Char -> Bool f1 'a' = True f1 _ = False
f2 :: Bool -> String f2 True = "true" f2 False = "false"
f3 :: String -> Int f3 = length
fs = PushF f1 (PushF f2 (PushF f3 (Bottom id)))
First, we make fs an instance of class Show. It is jolly convenient.
data HF = forall a b. (TypeRep a,TypeRep b) => HF (F a b) show_fn_type (g::(a->b)) = "(" ++ (show (tr_index (undefined::a))) ++ "->"++(show (tr_index (undefined::b))) ++ ")"
instance (TypeRep a, TypeRep b) => Show (F a b) where show = show . hsf_to_lst . HF where hsf_to_lst (HF (Bottom g)) = [show_fn_type g] hsf_to_lst (HF (PushF g next)) = (show_fn_type g):(hsf_to_lst$HF next)
Now, Amr Sabry's question: ] Is it possible to write a function ] f :: F a b -> T c -> F c b ] where (T c) is some type for values of type 'c' or values representing ] the type 'c' or whatever is appropriate. Thus if given the ] representation of Bool, the function should return: ] PushF f2 (PushF f3 (Bottom id)) ] and if given the representation of String the function should return ] PushF f3 (Bottom id) ] and so on. First, we prepend to the given F a b structure the identity composition. We see the meaning of it below.
f fs v = f' (PushF id fs) v
f':: (TypeRep c) => (F a b) -> c -> F a b f' here@(PushF g next) (v::tv) = if tr_index v == tr_index (g undefined) then here else case next of PushF g1 next' -> f' (PushF (g1.g) next') v Bottom g1 -> f' (Bottom (g1.g)) v
The function f' takes a data structure F a b and a value of type c and returns another data structure F a b, but of a different structure PushF g next here 'next' has the type F c b -- which is the answer to Amr Sambry's question. The function g::a->c is a composition of all previously occurring functions. This is a neat "side-effect" of the function f': we partially compose the given F a b structure up to the given type. Let us see how it works: *Main> fs ["(0->2)","(2->3)","(3->1)","(1->1)"] *Main> f fs 'a' ["(0->0)","(0->2)","(2->3)","(3->1)","(1->1)"] *Main> f fs True ["(0->2)","(2->3)","(3->1)","(1->1)"] *Main> f fs "a" ["(0->3)","(3->1)","(1->1)"] *Main> f fs (1::Int) ["(0->1)","(1->1)"] Because f is capable of producing any partial composition, it can do the full composition just as easily:
flatten:: (TypeRep a, TypeRep b) => F a b -> (a -> b) flatten fs :: (a->b) = case f fs (undefined::b) of PushF g (Bottom g1) -> g1.g
And it indeed works: *Main> flatten fs 'a' 4 -- the length of the word true *Main> flatten fs 'b' 5 -- the length of the word false Again, I can't seem to write any Haskell code that doesn't explicitly use undefined.
This message describes functions safeCast and sAFECoerce implemented in Haskell98 with common, pure extensions. The functions can be used to 'escape' from or to existential quantification and to make existentially-quantified datatypes far easier to deal with. Unlike Dynamic, the present approach is pure, avoids unsafeCoerce and unsafePerformIO, and permits arbitrary multiple user-defined typeheaps (finite maps from types to integers and values). An earlier message [1] introduced finite type maps for purely-functional conversion of monomorphic types to unique integers. The solution specifically did not rely on Dynamic and therefore is free from unsafePerformIO. This message shows that the type maps can be used for a safe cast, in particular, for laundering existential types. The code in this message does NOT use unsafePerformIO or unsafeCoerce. To implement safe casts, we define a function sAFECoerce -- which works just like its impure counterpart. However the former is pure and safe. sAFECoerce is a library function expressed in Haskell with common extension. The safety of sAFECoerce is guaranteed by the typechecker itself. This whole message is self-contained, and can be loaded as it is in GHCi, given the flags -fglasgow-exts -fallow-undecidable-instances -fallow-overlapping-instances This message was inspired by Amr Sabry's problem on existentials. In fact, it answers an unstated question in Amr Sabry's original message. It has been observed on this list that existentially-quantified datatypes are not easy to deal with [2]. For example, suppose we have a value of a type
data EV = forall a. (TypeRep a TI)=> EV a
(please disregard the second argument of TypeRep for a moment). The constructor EV wraps a value. Suppose we can guess that the wrapped value is actually a boolean. Even if our guess is correct, we *cannot* pass that value to any function of booleans: *> *Main> case (EV False) of (EV x) -> not x *> *> <interactive>:1: *> Inferred type is less polymorphic than expected *> Quantified type variable `a' is unified with `Bool' *> When checking an existential match that binds *> x :: a *> and whose type is EV -> Bool *> In a case alternative: (EV x) -> not x A quantified type variable cannot be unified with any regular type -- or with another quantified type variable. Values of existentially quantified types cannot be passed to monomorphic functions, or to constrained polymorphic functions (unless all their constrains have been mentioned in the declaration of the existential). That limitation guarantees safety -- on the other hand, it significantly limits the convenience of existential datatypes [2]. To overcome the limitation, it _seemed_ that we had to sacrifice purity. If we are positive that a particular existentially quantified value has a specific type (e.g., Bool), we can use unsafeCoerce to cast the value into the type Bool [3]. This approach is one of the foundations of the Dynamic library. The other foundation is an ability to represent a type as a unique run-time value, provided by the methods of the class like TypeRep. Given an existentially quantified value and a value of the desired type, Dynamic compares type representations of the two values. If they are the same, we can confidently use unsafeCoerce to cast the former into the type of the latter. This works, yet leaves the feeling of dissatisfaction. For one thing, we had to resort to an impure feature. More importantly, we placed our trust in something like TypeRep and its members, that they give an accurate and unique representation of types. But what if they lie to us, due to a subtle bug in their implementation? What if they give the same representation for two different types? unsafeCoerce will do its dirty work nevertheless. Using the result would lead to grave consequences, however. This message describes sAFECoerce and the corresponding safe cast. Both functions convert the values of one type into the target type. One or both of these types may be existentially quantified. When the source and the target types are the same, both functions act as the identity function. The safe cast checks that the type representations of the source and the target types are the same. If they are, it invokes sAFECoerce. Otherwise, we monadically fail. The function sAFECoerce does the conversion without any type checking. It always returns the value of the target type. If the source type was the same as the target type, the return value has the same "bit pattern" as the argument. If the types differ, the return value is just some default value of the right type. The user can specify the default value as he wishes. Therefore, we can now write *> *Main> case (EV False) of (EV x) -> not $ sAFECoerce x *> True We can also try *> *Main> case (EV 'a') of (EV x) -> not $ sAFECoerce x *> *** Exception: Prelude.undefined The default value was 'undefined'. The function safeCast is actually trivial
safeCast::(Monad m, TypeRep b TI, TypeRep a TI) => a -> m b safeCast a :: m b = if tr_index a (undefined::TI) == tr_index (undefined::b) (undefined::TI) then return $ sAFECoerce a else fail "miscast"
*> *Main> case (EV False) of (EV x) -> (safeCast x)::Maybe Bool *> Just False *> *Main> case (EV False) of (EV x) -> (safeCast x)::Maybe Int *> Nothing The above examples cast the value of an existentially quantified type into a regular type. As we shall see at the end, we can just as well cast _into_ an existentially quantified type. Some of the code in this message is similar to the code posted here earlier. However, there are many small and subtle changes. It seemed more convenient to include all the code, to make this message self-contained. We start with the polymorphic list as a base data structure, as before:
data Nil t r = Nil data Cons t r = Cons t r
class PList ntype vtype cdrtype where cdr:: ntype vtype cdrtype -> cdrtype empty:: ntype vtype cdrtype -> Bool value:: ntype vtype cdrtype -> vtype
instance PList Nil vtype cdrtype where empty = const True
instance (PList n v r) => PList Cons v' (n v r) where empty = const False value (Cons v r) = v cdr (Cons v r) = r
We use the polymorphic list to define a finite type map. The map in this message has two additional operations: fetch and alter.
class TypeSeq t s where type_index:: t -> s -> Int fetch:: t -> s -> t alter:: t -> s -> s
instance (PList Cons t r) => TypeSeq t (Cons t r) where type_index _ _ = 0 fetch _ (Cons v _) = v alter newv (Cons v r) = Cons newv r
instance (PList Cons t' r', TypeSeq t r') => TypeSeq t (Cons t' r') where type_index v s = 1 + (type_index v $ cdr s) fetch v s = fetch v $ cdr s alter newv (Cons v' r') = Cons v' $ alter newv r'
TypeSeq is an associative map between types, values, and integers. The operation type_index takes a value and a typemap and returns the index of the type of the value in the map. The operation alter takes a value and a typemap and returns a new typemap which stores the given value. The value can be retrieved either by its index -- or by its type. Here we need only the latter: the operation fetch. We can build the initial typemap
init_typeseq = Cons (undefined::Char) $ Cons (undefined::Int) $ Cons (undefined::Bool) $ Cons (undefined::String) $ Cons (undefined::Maybe Char) $ Nil
We also need the type of init_typeseq, to be used in a type-expression context. Alas, there does not seem to be an easy way to take a type of a variable in a that context. In the expression context, we can write init_typeseq::u and then use the type variable 'u' as needed. In the type-expression context (in the context of data and instance declarations), this trick does not work. I couldn't find a better solution than loading the above definition into GHCi, entering ":t init_typeseq" and cutting and pasting GHCi's answer back into the code:
type TI = Cons Char (Cons Int (Cons Bool (Cons String (Cons (Maybe Char) (Nil Bool Bool)))))
We can test the typemap as follows *> *Main> type_index True init_typeseq *> 2 *> *Main> fetch (undefined::Bool) $ alter True init_typeseq *> True
testmap = let tp1 = alter True init_typeseq tp2 = alter 'a' tp1 tp3 = alter False tp2 -- updating the previously-stored value in (fetch (undefined::Bool) tp3, fetch 'x' tp3)
*> *Main> testmap *> (False,'a') As before, to deal with existentials, we need to extend the above compile-time type-mapping to run-time
class (TypeSeq t u) => TypeRep t u where tr_index:: t -> u -> Int tr_index = type_index inj:: t -> u -> u inj = alter prj:: t -> u -> t prj = fetch
instance TypeRep Bool TI instance TypeRep Char TI instance TypeRep String TI instance TypeRep Int TI
We can use any TypeSeq -- init_typeseq or any other TypeSeq. We can define a number of suitable TypeSeq values in various modules and import the most suitable one. The function sAFECoerce is trivial:
sAFECoerce a = sAFECoerce' a (init_typeseq::TI)
sAFECoerce' (a::a) tenv ::b = prj (undefined::b) $ inj a tenv
It stores its argument into the type environment, and then retrieves it given the target type as the index. If the source and the target types are the same, the retrieved value is identical to the argument of sAFECoerce'. Otherwise, sAFECoerce' returns whatever value has been stored in the typenv under the target type (the default value). We have remarked earlier that this message was intended to solve an unstated question in Amr Sabry's original message. The unstated question is the need to cast into an existentially quantified datatype. Here's the description of the problem and the stated question:
data F a b = forall c. (TypeRep c TI) => PushF (a -> c) (F c b) | Bottom (a -> b)
f1 :: Char -> Bool f1 'a' = True f1 _ = False
f2 :: Bool -> String f2 True = "true" f2 False = "false"
f3 :: String -> Int f3 = length
fs = PushF f1 (PushF f2 (PushF f3 (Bottom id)))
] Is it possible to write a function ] f :: F a b -> T c -> F c b ] where (T c) is some type for values of type 'c' or values representing ] the type 'c' or whatever is appropriate. Thus if given the ] representation of Bool, the function should return: ] PushF f2 (PushF f3 (Bottom id)) ] and if given the representation of String the function should return ] PushF f3 (Bottom id) ] and so on. The solution given earlier is:
data HF = forall a b. (TypeRep a TI,TypeRep b TI) => HF (F a b) show_fn_type:: (TypeRep a TI, TypeRep b TI) => (a->b) -> String show_fn_type (g::a->b) = "(" ++ (show (tr_index (undefined::a) (undefined::TI) )) ++ "->"++(show (tr_index (undefined::b) (undefined::TI))) ++ ")"
instance (TypeRep a TI, TypeRep b TI) => Show (F a b) where show = show . hsf_to_lst . HF where hsf_to_lst (HF (Bottom g)) = [show_fn_type g] hsf_to_lst (HF (PushF g next)) = (show_fn_type g):(hsf_to_lst$HF next)
f':: (TypeRep c TI) => (F a b) -> c -> F a b f' here@(PushF g next::(F a b)) v = if tr_index v (undefined::TI) == tr_index (g undefined) (undefined::TI) then here else case next of PushF g1 next' -> f' (PushF (g1.g) next') v Bottom g1 -> f' (Bottom (g1.g)) v
f fs v = f' (PushF id fs) v
flatten:: (TypeRep a TI, TypeRep b TI) => F a b -> (a -> b) flatten fs :: (a->b) = case f fs (undefined::b) of PushF g (Bottom g1) -> g1.g
In short, the function f' takes a data structure F a b and a value of type c and returns another data structure F a b, but of a different structure PushF g next here 'next' has the type F c b -- which is the answer to Amr Sabry's question. The function g::a->c is a composition of all previously occurring functions. This is a neat "side-effect" of the function f': we partially compose the given F a b structure up to the given type. Technically, the function f' answers Amr Sabry's question. Alas, the answer, until now, was useless. The answer, the second field in the structure returned by f', is existentially quantified. We can do preciously little with it -- until now. Now we can write
t1 v = case f fs v of PushF _ (next::F c b) -> flatten next $ sAFECoerce v
Here we cast into an existential type. *> *Main> t1 'a' *> 4 *> *Main> t1 False *> 5 *> *Main> t1 "xyz" *> 3 [1] Previous message Pure functional TypeRep [Was: Existentials...] http://www.haskell.org/pipermail/haskell/2003-July/012330.html [2] escape from existential quantification http://www.haskell.org/pipermail/haskell/2003-February/011288.html [3] Re: escape from existential quantification http://www.haskell.org/pipermail/haskell/2003-February/011293.html
Throughout this message you imply, if not outright state, that Dynamics requires unsafeCoerce/unsafePerformIO. This is simply not the case. GHC implements Dynamics with unsafeCoerce, or did last time I checked, but it can easily be implemented using only existentials. (I presume that this decision was made either for efficiency, simplicity, and/or simply that another (readily useable) technique was not known when the library was made.) Anyways, as I have often mentioned, "A Lightweight Implementation of Generics and Dynamics" has an unsafePerformIO/Coerce free implementation of Dynamics as well as Generics as the title suggests.
This is a "Related Work" section of the previous message. We compare three main methods of achieving safe casts. It seems that the method proposed in the earlier message is quite different -- especially in terms of extensibility. In this message, we compare the extensibility of four techniques. Stephanie Weirich ICFP'00 paper points out another solution, which relies on mutable IORefs. Since that technique can only be used with IO monad, we do not consider it here. Some of the methods below require type classes and algebraic datatype declarations. Some require only an algebraic datatype, or only a typeclass. In either case, we run into an extensibility problem: to add support for a new datatype, we must either add an instance declaration, or a new alternative to the datatype declaration. These are non-trivial, non-modular extensions. For example, when we add a new alternative to a datatype declaration, we must physically update the corresponding file. We must then re-compile all dependent modules. Surprisingly, the solution in the earlier message is free from these drawbacks. We can extend the type heap in a modular fashion. We do not need to alter type or data declarations. It seems our type heaps are sort of reified lists of instances. There appear to be a duality between typeclasses and our type heaps. Only our type heaps are first-class. The idea behind all type-safe casts is simple: to cast a value of a type 'a' into a target type 'b', we inject the value into some universe and then project it to the target type 'b'. To illustrate the differences in implementations of that idea, we will be using James Cheney and Ralf Hinze's example: a generic comparison function. To avoid unnecessary complications, we limit ourselves to built-in and scalar types. Extensions to products, exponential, recursive and polymorphic types are possible, but too messy. We also will not consider existential types, so we avoid introducing type classes if they are not needed in the static case. This whole message is self-contained, and can be loaded as it is in GHCi, given the flags -fglasgow-exts -fallow-undecidable-instances -fallow-overlapping-instances Approach 1: Tcl approach The universal type is a string. The values to cast must belong to the class Show and the class Read. The injection and projection functions are trivial:
sh_inj x = show x sh_prj x = read x
Generic equality and the cast functions are trivial as well:
sh_gequal x y = sh_inj x == sh_inj y
sh_cast x = sh_prj $ sh_inj x
Here's the test:
sh_test1 = [sh_gequal 1 2, sh_gequal True True, sh_gequal 'a' 'b']
To add support for a new datatype, we have to place that datatype in the class Show and the class Read. That is, we have to add the corresponding instance declarations _and_ we have to implement methods 'show' and 'read'. Functions sh_gequal and sh_cast do not have to be modified. The Tcl approach is also the most generous with respect to type equivalence: for example, Int and Integer are considered equivalent, and sh_cast may cast between them. Incidentally, when GHC can derive Binary, this approach becomes far more appealing. Approach 2: The universe is the tagged union
data TU = TChar Char | TBool Bool | TInt Int
class TURepr t where tu_inj:: t -> TU tu_prj:: TU -> t
instance TURepr Char where tu_inj = TChar tu_prj (TChar x) = x
instance TURepr Bool where tu_inj = TBool tu_prj (TBool x) = x
instance TURepr Int where tu_inj = TInt tu_prj (TInt x) = x
tu_gequal x y = cmp (tu_inj x) (tu_inj y) where cmp (TChar x) (TChar y) = x == y cmp (TBool x) (TBool y) = x == y cmp (TInt x) (TInt y) = x == y
tu_cast x = tu_prj $ tu_inj x
tu_test1 = [tu_gequal (1::Int) (2::Int), tu_gequal True True, tu_gequal 'a' 'b']
To add support for a new datatype, we have to add a new alternative to the declaration of the datatype TU and we have to add a new instance for the class TURepr (with the implementation of the tu_inj and tu_proj methods). We also have to add another clause to the tu_gequal function. Clearly this is the least extensible approach. Approach 3: by Cheney and Ralf Hinze's The universe is a set of inject/project pairs
data IPP a = IPPInt (a->Int) (Int->a) | IPPChar (a->Char) (Char->a) | IPPBool (a->Bool) (Bool->a)
ipp_gequal (IPPInt prj inj) x y = prj x == prj y ipp_gequal (IPPChar prj inj) x y = prj x == prj y ipp_gequal (IPPBool prj inj) x y = prj x == prj y
ipp_cast (IPPInt xprj xinj) x (IPPInt yprj yinj) = yinj $ xprj x -- more should follow...
ipp_test1 = [ipp_gequal (IPPInt id id) (1::Int) (2::Int), ipp_gequal (IPPBool id id) True True, ipp_gequal (IPPChar id id) 'a' 'b']
To add a new primitive datatype, we should modify the declaration of the datatype IPP and add a new alternative. We also need to add clauses to ipp_gequal and ipp_cast. Incidentally, (IPPInt id id) specifies that the type Int is equivalent only to Int (that is, for type Int equality is the same as identity). However, we can be more generous: for example, we can cast between any enumerable type and Int: *> *Main> ipp_cast (IPPInt fromEnum toEnum) () (IPPInt id id) *> 0 *> *Main> ipp_cast (IPPInt fromEnum toEnum) True (IPPInt id id) *> 1 Approach 4: the approach of an earlier message. We can have as many universes as we wish. For historical reasons, injection is called 'alter' and projection 'fetch'.
data Nil t r = Nil data Cons t r = Cons t r
class PList ntype vtype cdrtype where cdr:: ntype vtype cdrtype -> cdrtype empty:: ntype vtype cdrtype -> Bool value:: ntype vtype cdrtype -> vtype
instance PList Nil vtype cdrtype where empty = const True
instance (PList n v r) => PList Cons v' (n v r) where empty = const False value (Cons v r) = v cdr (Cons v r) = r
class TypeSeq t s where type_index:: t -> s -> Int fetch:: t -> s -> t alter:: t -> s -> s
instance (PList Cons t r) => TypeSeq t (Cons t r) where type_index _ _ = 0 fetch _ (Cons v _) = v alter newv (Cons v r) = Cons newv r
instance (PList Cons t' r', TypeSeq t r') => TypeSeq t (Cons t' r') where type_index v s = 1 + (type_index v $ cdr s) fetch v s = fetch v $ cdr s alter newv (Cons v' r') = Cons v' $ alter newv r'
The initial type heap (the initial universe).
th_init = Cons 'a' $ Cons True $ Cons (1::Int) $ Nil
th_gequal tenv x y | type_index (undefined::Char) tenv == type_index x tenv = let t1 = alter x tenv t2 = alter y tenv in fetch (undefined::Char) t1 == fetch (undefined::Char) t2 th_gequal tenv x y | type_index (undefined::Int) tenv == type_index x tenv = let t1 = alter x tenv t2 = alter y tenv in fetch (undefined::Int) t1 == fetch (undefined::Int) t2 th_gequal tenv x y | type_index (undefined::Bool) tenv == type_index x tenv = let t1 = alter x tenv t2 = alter y tenv in fetch (undefined::Bool) t1 == fetch (undefined::Bool) t2
th_cast tenv x :: y = fetch (undefined::y) $ alter x tenv
th_test1 = [th_gequal th_init (1::Int) (2::Int), th_gequal th_init True True, th_gequal th_init 'a' 'b']
Let us see what is involved in adding a new datatype. Let us add Float: First, we introduce an extended universe:
th_heap2 = Cons (1.0::Float) $ th_init
Then we extend the function th_gequal. We do _not_ need to modify the code of the latter:
th_gequal2 tenv x y | type_index (undefined::Float) tenv == type_index x tenv = let t1 = alter x tenv t2 = alter y tenv in fetch (undefined::Float) t1 == fetch (undefined::Float) t2 -- delegate the rest to the old th_gequal th_gequal2 tenv x y = th_gequal tenv x y
-- th_cast doesn't need to change
th_test2 = [th_gequal2 th_heap2 (1.0::Float) (2.0::Float), th_gequal2 th_heap2 (3.14::Float) (3.14::Float), th_gequal2 th_heap2 (1::Int) (2::Int), th_gequal2 th_heap2 True True, th_gequal th_heap2 'a' 'b'] -- old th_gequal used here!
*> *Main> th_test2 *> [False,True,False,True,False] We should emphasize the modularity of the latter approach. No _declarations_ need to be changed. In the present, static case, there are no type class instances to add. Furthermore, no code needs to be altered either. The function th_gequal can still be used with the extended heap.
oleg@pobox.com wrote:
This is a "Related Work" section of the previous message.
... again cunning stuff omitted ...
I buy most of this but IMHO you should make very clear that there is not just a single safeCoerce, but the TI/init_typeseq argument has to be constructed and supplied by the programmer in a way that (s)he decides what array of types can be handled. So if you wanted to use your approach to scrap boilerplate [1], say deal with many datatypes, this becomes quite a burden. Think of actually building initial type sequences. Think of how combinators need to be parameterised to take type sequences. (That's what I called a CWA yesterday.) On the other hand, you mention this duality between type classes vs. type heaps. Yes, I would say that type classes and type case are somewhat dual. You provide a type case. What I like about your type case vs. the approach taken in [1] is that your type case will be very precise. That is, you don't say one can just try anything what is Typeable but you rather restrict questions to the types in the supplied initial type sequence. This is certainly beneficial for applications other than scraping boilerplate. Ralf [1} "Scrap your boilerplate: a practical design pattern for generic programming" by Ralf Lämmel and Simon Peyton-Jones, appeared in Proceedings of TLDI 2003, ACM Press http://www.cs.vu.nl/boilerplate/#paper -- Ralf Laemmel VU & CWI, Amsterdam, The Netherlands http://www.cs.vu.nl/~ralf/ http://www.cwi.nl/~ralf/
This message illustrates how safe casting with multiple universes can be extended to new user-defined, polymorphic datatypes. We show a _portable_ mapping of polymorphic types to integers. Different instances of a polymorphic type map to different integers. Phantom types can be either disregarded or accounted for -- as the user wishes. Furthermore, if two different applications running on two different machines agree on the same type heap, then they agree on the type encoding. An application can use multiple typeheaps at the same time. It is easy therefore to dedicate one particular typeheap for portable encoding of types across several computers. Incidentally, our encoding of types may take into account _values_ of some of the components of a polymorphic type. For example, given a value of a type 'Foo Int a', the encoding may use the _value_ of the first component and the _type_ of the second component. When we do the cast, we can check not only for the desired type but also for the desired values. We can thus approach dependent types. This message hopefully replies to Ralf Laemmel's comment: ] You should make very clear that there is ] not just a single safeCoerce, but the TI/init_typeseq argument has to ] be constructed and supplied by the programmer in a way that (s)he ] decides what array of types can be handled. So if you wanted to use ] your approach to scrap boilerplate [1], say deal with many datatypes, ] this becomes quite a burden. Think of actually building initial type ] sequences. Think of how combinators need to be parameterised to take ] type sequences. with which I agree. Below I try to make it very implicit what depends on TI/init_typeseq and what doesn't, and how much work is involved in adding new datatypes and extending type heaps. I don't know if the proposed approach is better than the others in many circumstances. It's certainly different. Ralf Laemmel also wrote: ] Software-engineering-wise your approach suffers from an important ] weakness: a closed world assumption. The programmer has to maintain ] your "TI" and pass it on in all kinds of contexts for the array of ] types to be handled. I thought it is a feature. I thought a programmer can import some type heap, partially apply the needed function to it, and re-export the latter. The example below demonstrates what is involved when a new datatype is added. It seems not that much. ] I didn't need undecidable not even overlapping instances. I don't actually need overlapping-instances extensions. An earlier message on the subject of MRefs used similar type heaps without any need for -fallow-overlapping-instances. However I had to use numeral types such as Succ (Succ ... Zero) rather than Int for type indices. The current approach looks more elegant. Besides, you seem to in favor of giving overlapping instances more acceptance, support and legitimacy. ] Is it obvious to see that fetching stuff from the type sequences would ] be indeed efficient for long PLists? The sequence of 'cdr' operations needed for fetching stuff is known statically. A compiler might therefore do something intelligent. This whole message is self-contained, and can be loaded as it is in GHCi, given the flags -fglasgow-exts -fallow-undecidable-instances -fallow-overlapping-instances We start with the boilerplate, which has changed a little (for example, the class PLists now has a member function pllen).
data Nil t r = Nil data Cons t r = Cons t r
class PList ntype vtype cdrtype where cdr:: ntype vtype cdrtype -> cdrtype empty:: ntype vtype cdrtype -> Bool value:: ntype vtype cdrtype -> vtype pllen:: ntype vtype cdrtype -> Int
instance PList Nil vtype cdrtype where empty = const True pllen = const 0
instance (PList n v r) => PList Cons v' (n v r) where empty = const False value (Cons v r) = v cdr (Cons v r) = r pllen (Cons v r) = 1 + pllen r
class TypeSeq t s where type_index:: t -> s -> Int fetch:: t -> s -> t alter:: t -> s -> s
instance (PList Cons t r) => TypeSeq t (Cons t r) where type_index _ _ = 0 fetch _ (Cons v _) = v alter newv (Cons v r) = Cons newv r
instance (PList Cons t' r', TypeSeq t r') => TypeSeq t (Cons t' r') where type_index v s = 1 + (type_index v $ cdr s) fetch v s = fetch v $ cdr s alter newv (Cons v' r') = Cons v' $ alter newv r'
The initial typesequence:
init_typeseq = Cons (undefined::Char) $ Cons (undefined::Int) $ Cons (undefined::Bool) $ Cons (undefined::String) $ (Nil::Nil () ())
and its type. See the previous message for more discussion of the latter.
type TI = (Cons Char (Cons Int (Cons Bool (Cons String (Nil () ())))))
Because we will be dealing with existential types, we need to extend the compile-time indexing into run-time:
class (TypeSeq t u) => TypeRep t u where tr_index:: t -> u -> Int tr_index = type_index inj:: t -> u -> u inj = alter prj:: t -> u -> t prj = fetch
instance TypeRep Bool TI instance TypeRep Char TI instance TypeRep String TI instance TypeRep Int TI
The following declarations of the datatype DTR and functions ti and tinj do _not_ depend on a particular type environment. These functions are fully generic with respect to TypeSeq and do not depend on init_typeseq. The purpose of these declarations should be become clear in a moment.
data DTR s = forall t. (TypeRep t s) => DTR t s
ti decon v = foldl1 (\acc x -> base*acc + x) $ map (\(DTR v s) -> 1+ type_index v s) ta where base = case head ta of (DTR _ tenv) -> pllen tenv ta = decon v
tinj decon v = map (\(DTR v s) -> alter v s) $ decon v
We come now to the extension part. Suppose the user declares the following polymorphic datatype (along the lines suggested by Wang Meng):
data UT a b = C | D a | E a b deriving Show
If we wish to index it, we need to extend our typeheap with a _monomorphic_ instance of the datatype:
typeseq1 = Cons (undefined::UT () ()) $ init_typeseq
type IT2 = Cons (UT () ()) TI
We chose "UT () ()" as a representative monomorphic instance. We also need to extend TypeRep. It is actually quite easy. First we assert that everything indexable against init_typeseq can be indexed against typeseq1:
instance (TypeRep a TI,TypeSeq a IT2) => TypeRep a IT2
The compiler will check in due course if this assertion holds. We can now index (UT () ()):
instance TypeRep (UT () ()) IT2
We should note that these instance declarations are trivial: they rely on the default implementation of the relevant methods. Now, the user has to provide two functions: ut_decon and ut_con. The former is to deconstruct a value of UT x y into an array of DTRs -- an array of polymorphic values that constitute the given UT value. We chose the following deconstructor:
ut_decon C = [DTR (undefined::UT () ()) typeseq1, DTR (1::Int) typeseq1] ut_decon (D x) = [DTR (undefined::UT () ()) typeseq1, DTR (2::Int) typeseq1, DTR x typeseq1] ut_decon (E x y) = [DTR (undefined::UT () ()) typeseq1, DTR (3::Int) typeseq1, DTR x typeseq1, DTR y typeseq1]
Note that a value "C" has the type "UT x y" where x and y can be any particular type or any type. The above encoding disregards the phantom x and y when encoding C. If we wished, we could have taken the phantom types into account. To encode a type UT x y, we need to pass a value of that type to "ti ut_decon". We get an integer, which is, in base B, a_0 a_1 a_2 ... with each "digit" encoding the type of one component of UT. The base B is the size of the type environment. Examples: *> *Main> ti ut_decon (C::UT Bool Bool) *> 8 *> *Main> ti ut_decon (C::UT Bool Char) *> 8 -- as we saw, phantom types are disregarded. *> *Main> ti ut_decon (D 'a' ::UT Char Bool) *> 42 *> *Main> ti ut_decon (D 1 ::UT Int Bool) *> 43 *> *Main> ti ut_decon (E 'a' 'b') *> 212 *> *Main> ti ut_decon (E 'a' 'c') *> 212 *> *Main> ti ut_decon (E 'a' True) *> 214 *> *Main> ti ut_decon (E True 'a') *> 222 The other function is the constructor (aka projector)
ut_con (thd:tflag:targs) :: UT x y = case fetch (undefined::Int) tflag of 1 -> C 2 -> D $ fetch (undefined::x) (head targs) 3 -> E (fetch undefined t1) (fetch undefined t2) where [t1,t2] = targs
The injector is a composition ut_con with (tinj ut_decon). The projector and the injector together give us the safe cast: *> *Main> (ut_con $ tinj ut_decon (C::UT Bool Bool))::(UT Bool Bool) *> C *> *Main> (ut_con $ tinj ut_decon (C::UT Bool Bool))::(UT Int Int) *> C -- C can be cast into (UT Bool Bool) and (UT Int Int) *> *Main> (ut_con $ tinj ut_decon (E True 'a'))::(UT Bool Char) *> E True 'a' *> *Main> (ut_con $ tinj ut_decon (E True 'a'))::(UT Bool Bool) *> E True *** Exception: Prelude.undefined -- cast error!
oleg@pobox.com wrote:
... loads of cunning stuff omitted
Software-engineering-wise your approach suffers from an important weakness: a closed world assumption. The programmer has to maintain your "TI" and pass it on in all kinds of contexts for the array of types to be handled. I also had a type-safe and efficient cast in [1] with a CWA. (I guess it works fine for extensials.) My CWA was even more serious however. I use a class for casting whose declaration even depends on the array of types to be handled. On the positive side, I didn't need undecidable not even overlapping instances. Also, the programmer is not concerned with passing on any type seq like your "TI". I really admire your use of polymorphic lists (which are in fact kind of products) to get the problem of type sequences to the value level. Cool! Do you see any way to effectively remove this CWA? (Only then it could serve as a replacement of the current cast function.) If yes, would you expect that your approach is more efficient then the one taken in Data.Typeable? (We recently split up Data.Dynamics into Data.Dynamics and a more primitive module Data.Typeable which contains cast; see CVS) Is it obvious to see that fetching stuff from the type sequences would be indeed efficient for long PLists? Well, I guess the hard problem is the CWA anyway. Ralf [1] The Sketch of a Polymorphic Symphony http://homepages.cwi.nl/~ralf/polymorphic-symphony/ See the Larghetto movement It is trivial; it makes Stephanie Weirich's type-safe cast fit for nominal type analysis. -- Ralf Laemmel VU & CWI, Amsterdam, The Netherlands http://www.cs.vu.nl/~ralf/ http://www.cwi.nl/~ralf/
I admire the elegancy of your code which makes the changes to add new data types minimum. There is one question I want to ask: Does this technique extend to polymophic types? Let's say we have the following type:
data D a = C | D a
Is it possible to index the type D a? Or there is some fundmental limitations which make it not achievable by Haskell type classes? -W-M- @ @ | \_/ On Thu, 31 Jul 2003 oleg@pobox.com wrote:
This message describes functions safeCast and sAFECoerce implemented in Haskell98 with common, pure extensions. The functions can be used to 'escape' from or to existential quantification and to make existentially-quantified datatypes far easier to deal with. Unlike Dynamic, the present approach is pure, avoids unsafeCoerce and unsafePerformIO, and permits arbitrary multiple user-defined typeheaps (finite maps from types to integers and values).
An earlier message [1] introduced finite type maps for purely-functional conversion of monomorphic types to unique integers. The solution specifically did not rely on Dynamic and therefore is free from unsafePerformIO. This message shows that the type maps can be used for a safe cast, in particular, for laundering existential types. The code in this message does NOT use unsafePerformIO or unsafeCoerce. To implement safe casts, we define a function sAFECoerce -- which works just like its impure counterpart. However the former is pure and safe. sAFECoerce is a library function expressed in Haskell with common extension. The safety of sAFECoerce is guaranteed by the typechecker itself.
This whole message is self-contained, and can be loaded as it is in GHCi, given the flags -fglasgow-exts -fallow-undecidable-instances -fallow-overlapping-instances
This message was inspired by Amr Sabry's problem on existentials. In fact, it answers an unstated question in Amr Sabry's original message.
It has been observed on this list that existentially-quantified datatypes are not easy to deal with [2]. For example, suppose we have a value of a type
data EV = forall a. (TypeRep a TI)=> EV a
(please disregard the second argument of TypeRep for a moment).
The constructor EV wraps a value. Suppose we can guess that the wrapped value is actually a boolean. Even if our guess is correct, we *cannot* pass that value to any function of booleans:
*> *Main> case (EV False) of (EV x) -> not x *> *> <interactive>:1: *> Inferred type is less polymorphic than expected *> Quantified type variable `a' is unified with `Bool' *> When checking an existential match that binds *> x :: a *> and whose type is EV -> Bool *> In a case alternative: (EV x) -> not x
A quantified type variable cannot be unified with any regular type -- or with another quantified type variable. Values of existentially quantified types cannot be passed to monomorphic functions, or to constrained polymorphic functions (unless all their constrains have been mentioned in the declaration of the existential). That limitation guarantees safety -- on the other hand, it significantly limits the convenience of existential datatypes [2].
To overcome the limitation, it _seemed_ that we had to sacrifice purity. If we are positive that a particular existentially quantified value has a specific type (e.g., Bool), we can use unsafeCoerce to cast the value into the type Bool [3]. This approach is one of the foundations of the Dynamic library. The other foundation is an ability to represent a type as a unique run-time value, provided by the methods of the class like TypeRep. Given an existentially quantified value and a value of the desired type, Dynamic compares type representations of the two values. If they are the same, we can confidently use unsafeCoerce to cast the former into the type of the latter.
This works, yet leaves the feeling of dissatisfaction. For one thing, we had to resort to an impure feature. More importantly, we placed our trust in something like TypeRep and its members, that they give an accurate and unique representation of types. But what if they lie to us, due to a subtle bug in their implementation? What if they give the same representation for two different types? unsafeCoerce will do its dirty work nevertheless. Using the result would lead to grave consequences, however.
This message describes sAFECoerce and the corresponding safe cast. Both functions convert the values of one type into the target type. One or both of these types may be existentially quantified. When the source and the target types are the same, both functions act as the identity function. The safe cast checks that the type representations of the source and the target types are the same. If they are, it invokes sAFECoerce. Otherwise, we monadically fail. The function sAFECoerce does the conversion without any type checking. It always returns the value of the target type. If the source type was the same as the target type, the return value has the same "bit pattern" as the argument. If the types differ, the return value is just some default value of the right type. The user can specify the default value as he wishes.
Therefore, we can now write
*> *Main> case (EV False) of (EV x) -> not $ sAFECoerce x *> True
We can also try
*> *Main> case (EV 'a') of (EV x) -> not $ sAFECoerce x *> *** Exception: Prelude.undefined
The default value was 'undefined'.
The function safeCast is actually trivial
safeCast::(Monad m, TypeRep b TI, TypeRep a TI) => a -> m b safeCast a :: m b = if tr_index a (undefined::TI) == tr_index (undefined::b) (undefined::TI) then return $ sAFECoerce a else fail "miscast"
*> *Main> case (EV False) of (EV x) -> (safeCast x)::Maybe Bool *> Just False *> *Main> case (EV False) of (EV x) -> (safeCast x)::Maybe Int *> Nothing
The above examples cast the value of an existentially quantified type into a regular type. As we shall see at the end, we can just as well cast _into_ an existentially quantified type.
Some of the code in this message is similar to the code posted here earlier. However, there are many small and subtle changes. It seemed more convenient to include all the code, to make this message self-contained.
We start with the polymorphic list as a base data structure, as before:
data Nil t r = Nil data Cons t r = Cons t r
class PList ntype vtype cdrtype where cdr:: ntype vtype cdrtype -> cdrtype empty:: ntype vtype cdrtype -> Bool value:: ntype vtype cdrtype -> vtype
instance PList Nil vtype cdrtype where empty = const True
instance (PList n v r) => PList Cons v' (n v r) where empty = const False value (Cons v r) = v cdr (Cons v r) = r
We use the polymorphic list to define a finite type map. The map in this message has two additional operations: fetch and alter.
class TypeSeq t s where type_index:: t -> s -> Int fetch:: t -> s -> t alter:: t -> s -> s
instance (PList Cons t r) => TypeSeq t (Cons t r) where type_index _ _ = 0 fetch _ (Cons v _) = v alter newv (Cons v r) = Cons newv r
instance (PList Cons t' r', TypeSeq t r') => TypeSeq t (Cons t' r') where type_index v s = 1 + (type_index v $ cdr s) fetch v s = fetch v $ cdr s alter newv (Cons v' r') = Cons v' $ alter newv r'
TypeSeq is an associative map between types, values, and integers. The operation type_index takes a value and a typemap and returns the index of the type of the value in the map. The operation alter takes a value and a typemap and returns a new typemap which stores the given value. The value can be retrieved either by its index -- or by its type. Here we need only the latter: the operation fetch.
We can build the initial typemap
init_typeseq = Cons (undefined::Char) $ Cons (undefined::Int) $ Cons (undefined::Bool) $ Cons (undefined::String) $ Cons (undefined::Maybe Char) $ Nil
We also need the type of init_typeseq, to be used in a type-expression context. Alas, there does not seem to be an easy way to take a type of a variable in a that context. In the expression context, we can write init_typeseq::u and then use the type variable 'u' as needed. In the type-expression context (in the context of data and instance declarations), this trick does not work. I couldn't find a better solution than loading the above definition into GHCi, entering ":t init_typeseq" and cutting and pasting GHCi's answer back into the code:
type TI = Cons Char (Cons Int (Cons Bool (Cons String (Cons (Maybe Char) (Nil Bool Bool)))))
We can test the typemap as follows
*> *Main> type_index True init_typeseq *> 2 *> *Main> fetch (undefined::Bool) $ alter True init_typeseq *> True
testmap = let tp1 = alter True init_typeseq tp2 = alter 'a' tp1 tp3 = alter False tp2 -- updating the previously-stored value in (fetch (undefined::Bool) tp3, fetch 'x' tp3)
*> *Main> testmap *> (False,'a')
As before, to deal with existentials, we need to extend the above compile-time type-mapping to run-time
class (TypeSeq t u) => TypeRep t u where tr_index:: t -> u -> Int tr_index = type_index inj:: t -> u -> u inj = alter prj:: t -> u -> t prj = fetch
instance TypeRep Bool TI instance TypeRep Char TI instance TypeRep String TI instance TypeRep Int TI
We can use any TypeSeq -- init_typeseq or any other TypeSeq. We can define a number of suitable TypeSeq values in various modules and import the most suitable one.
The function sAFECoerce is trivial:
sAFECoerce a = sAFECoerce' a (init_typeseq::TI)
sAFECoerce' (a::a) tenv ::b = prj (undefined::b) $ inj a tenv
It stores its argument into the type environment, and then retrieves it given the target type as the index. If the source and the target types are the same, the retrieved value is identical to the argument of sAFECoerce'. Otherwise, sAFECoerce' returns whatever value has been stored in the typenv under the target type (the default value).
We have remarked earlier that this message was intended to solve an unstated question in Amr Sabry's original message. The unstated question is the need to cast into an existentially quantified datatype. Here's the description of the problem and the stated question:
data F a b = forall c. (TypeRep c TI) => PushF (a -> c) (F c b) | Bottom (a -> b)
f1 :: Char -> Bool f1 'a' = True f1 _ = False
f2 :: Bool -> String f2 True = "true" f2 False = "false"
f3 :: String -> Int f3 = length
fs = PushF f1 (PushF f2 (PushF f3 (Bottom id)))
] Is it possible to write a function ] f :: F a b -> T c -> F c b ] where (T c) is some type for values of type 'c' or values representing ] the type 'c' or whatever is appropriate. Thus if given the ] representation of Bool, the function should return: ] PushF f2 (PushF f3 (Bottom id)) ] and if given the representation of String the function should return ] PushF f3 (Bottom id) ] and so on.
The solution given earlier is:
data HF = forall a b. (TypeRep a TI,TypeRep b TI) => HF (F a b) show_fn_type:: (TypeRep a TI, TypeRep b TI) => (a->b) -> String show_fn_type (g::a->b) = "(" ++ (show (tr_index (undefined::a) (undefined::TI) )) ++ "->"++(show (tr_index (undefined::b) (undefined::TI))) ++ ")"
instance (TypeRep a TI, TypeRep b TI) => Show (F a b) where show = show . hsf_to_lst . HF where hsf_to_lst (HF (Bottom g)) = [show_fn_type g] hsf_to_lst (HF (PushF g next)) = (show_fn_type g):(hsf_to_lst$HF next)
f':: (TypeRep c TI) => (F a b) -> c -> F a b f' here@(PushF g next::(F a b)) v = if tr_index v (undefined::TI) == tr_index (g undefined) (undefined::TI) then here else case next of PushF g1 next' -> f' (PushF (g1.g) next') v Bottom g1 -> f' (Bottom (g1.g)) v
f fs v = f' (PushF id fs) v
flatten:: (TypeRep a TI, TypeRep b TI) => F a b -> (a -> b) flatten fs :: (a->b) = case f fs (undefined::b) of PushF g (Bottom g1) -> g1.g
In short, the function f' takes a data structure F a b and a value of type c and returns another data structure F a b, but of a different structure PushF g next here 'next' has the type F c b -- which is the answer to Amr Sabry's question. The function g::a->c is a composition of all previously occurring functions. This is a neat "side-effect" of the function f': we partially compose the given F a b structure up to the given type.
Technically, the function f' answers Amr Sabry's question. Alas, the answer, until now, was useless. The answer, the second field in the structure returned by f', is existentially quantified. We can do preciously little with it -- until now.
Now we can write
t1 v = case f fs v of PushF _ (next::F c b) -> flatten next $ sAFECoerce v
Here we cast into an existential type.
*> *Main> t1 'a' *> 4 *> *Main> t1 False *> 5 *> *Main> t1 "xyz" *> 3
[1] Previous message Pure functional TypeRep [Was: Existentials...] http://www.haskell.org/pipermail/haskell/2003-July/012330.html
[2] escape from existential quantification http://www.haskell.org/pipermail/haskell/2003-February/011288.html
[3] Re: escape from existential quantification http://www.haskell.org/pipermail/haskell/2003-February/011293.html _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Does this technique extend to polymophic types? Yes, of course. The type F a b in the earlier message was polymorphic.
Let's say we have the following type:
data D a = C | D a
Is it possible to index the type D a?
I have just lifted the polymorphic Maybe -- which is isomorphic to your type. ti maybe_decon (Just True) ti maybe_decon (Just 'a') give different results. (ti maybe_decon Nothing) can give either the same or different indices for different concrete types of Nothing. It's all up to you. For each new datatype, the user has to provide two functions: one to deconstruct the datatype into a polymorphic array of values of already indexable types, and the other is to re-construct the datatype from the array. As long as the user can do that -- in _any_ way he wishes -- the mapping is established. Incidentally, there is no need to add any new type instances or add new alternatives to datatype declarations. There is no need to extend the type heap either. I could post the code but I need to write explanations and perhaps change a few identifier names to something more meaningful. Alas, it's already almost 2am, and I want to go home...
participants (4)
-
Derek Elkins -
oleg＠pobox.com -
Ralf Laemmel -
Wang Meng