Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Greg Buchholz wrote:
Wow. Color me impressed. A little under a week ago, I stumbled
onto Joy, and thought to myself that it could be translated almost
directly into Haskell (which would imply it was possible to statically
type). Well, it wasn't quite as direct as I had initially thought, but
it looks like you've done it. Are there any papers/books out there
which I could study to learn more about these (and other) tricks of the
type system wizards?
Here's a cleaned up version, I have made the function composition and
stack both
use HLists... a bit neater. Have also added primrec and a 5th factorial.
As for type tricks most of these should be in the HList or OOHaskell
papers. The things to notice are using types as instance labels, that
constraints form horn
clause compile time meta-programs (in a non-backtracking prolog style)
and that multi-parameter classes with functional depandencies simulate
some dependant
types.
Keean.
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-overlapping-instances #-}
{-# OPTIONS -fallow-undecidable-instances #-}
--Joy implemented in Haskell... extensible embedded language...
module Joy where
import MainGhcGeneric1
-- Building non-empty lists
type HOne = HSucc HZero
hOne :: HOne
hOne = undefined
type HTwo = HSucc HOne
hTwo :: HTwo
hTwo = undefined
type HThree = HSucc HTwo
hThree :: HThree
hThree = undefined
end :: HNil
end = hNil
instance HList s = Apply HNil s s where
apply _ s = s
instance (HList s,HList s',HList l,Apply a s s',Apply l s' s'') = Apply (HCons a l) s s'' where
apply (HCons a l) s = apply l (apply a s :: s')
instance HList s = Apply HZero s (HCons HZero s) where
apply _ s = hCons hZero s
instance (HNat a,HList s) = Apply (HSucc a) s (HCons (HSucc a) s) where
apply a s = hCons a s
data Lit a = Lit a
lit :: a - Lit a
lit a = Lit a
unl :: Lit a - a
unl (Lit a) = a
instance Show a = Show (Lit a) where
showsPrec _ (Lit a) = showChar '[' . shows a . showChar ']'
instance HList s = Apply (Lit a) s (HCons a s) where
apply (Lit a) s = hCons a s
class (HBool b,HList s) = HIfte b t f s s' | b t f s - s' where
hIfte :: b - t - f - s - s'
instance (HList s,Apply t s s') = HIfte HTrue t f s s' where
hIfte _ t _ s = apply t s
instance (HList s,Apply f s s') = HIfte HFalse t f s s' where
hIfte _ _ f s = apply f s
data Ifte
ifte :: Ifte
ifte = undefined
instance Show Ifte where
showsPrec _ _ = showString If
instance (Apply b s r,HHead r b',HIfte b' t f s s')
= Apply Ifte (f :*: t :*: b :*: s) s' where
apply _ (HCons f (HCons t (HCons b s))) = hIfte (hHead (apply b s :: r) :: b') t f s
data Nul
nul :: Nul
nul = undefined
instance Show Nul where
showsPrec _ _ = showString Nul
instance HList s = Apply Nul (HCons HZero s) (HCons HTrue s) where
apply _ (HCons _ s) = hCons hTrue s
instance HList s = Apply Nul (HCons (HSucc n) s) (HCons HFalse s) where
apply _ (HCons _ s) = hCons hFalse s
data EQ
eq :: EQ
eq = undefined
instance Show EQ where
showsPrec _ _ = showString Eq
instance (HList s,TypeEq a b t) = Apply EQ (HCons a (HCons b s)) (HCons t s) where
apply _ (HCons a (HCons b s)) = hCons (typeEq a b) s
data Dip
dip :: Dip
dip = undefined
instance Show Dip where
showsPrec _ _ = showString Dip
instance (HList s,HList s',Apply a s s') = Apply Dip (HCons a (HCons b s)) (HCons b s') where
apply _ (HCons a (HCons b s)) = hCons b (apply a s)
data Dup
dup :: Dup
dup = undefined
instance Show Dup where
showsPrec _ _ = showString Dup
instance HList s = Apply Dup (HCons a s) (HCons a (HCons a s)) where
apply _ s@(HCons a _) = hCons a s
data Pop
pop :: Pop
pop = undefined
instance Show Pop where
showsPrec _ _ = showString Pop
instance HList s = Apply Pop (HCons a s) s where
apply _ (HCons _ s) = s
data Swap
swap :: Swap
swap = undefined
instance Show Swap where
showsPrec _ _ = showString Swap
instance HList s = Apply Swap (HCons a (HCons b s)) (HCons b (HCons a s)) where
apply _ (HCons a (HCons b s)) = hCons b (hCons a s)
data Suc
suc :: Suc
suc = undefined
instance Show Suc where
showsPrec _ _ = showString Suc
instance (HNat a,HList s) = Apply Suc (HCons a s) (HCons (HSucc a) s) where
apply _ (HCons _ s) = hCons (undefined::HSucc a) s
data Pre
pre :: Pre
pre = undefined
instance Show Pre where
showsPrec _ _ = showString Pre
instance (HNat a,HList s) = Apply Pre (HCons (HSucc a) s) (HCons a s) where
apply _ (HCons _ s) = hCons (undefined::a) s
data Add
add :: Add
add = undefined
instance Show Add where
showsPrec _ _ = showString Add
instance (HList s,HAdd a b c) = Apply Add (HCons a (HCons b s)) (HCons c s) where
apply _ (HCons _ (HCons _ s)) = hCons (hAdd (undefined::a) (undefined::b)) s
class (HNat a,HNat b) = HAdd a b c | a b - c where
hAdd :: a - b - c
instance HAdd HZero HZero HZero where
hAdd _ _ = hZero
instance HNat b = HAdd HZero (HSucc b) (HSucc b) where
hAdd _ b = b
instance HNat a = HAdd (HSucc a) HZero (HSucc a) where
hAdd a _ = a
instance (HNat (HSucc a),HNat (HSucc b),HNat c,HAdd a b c)
= HAdd
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Keean Schupke wrote: The things to notice are using types as instance labels, that constraints form horn clause compile time meta-programs (in a non-backtracking prolog style) and that multi-parameter classes with functional depandencies simulate some dependant types. I think I understood everything in that sentance up to the word as ;-) Greg ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Greg Buchholz wrote:
Keean Schupke wrote:
I dont see why this is illegal... what do we want? take the top two
items from the stack?
With the code below (direct translation from tuples to HLists) I
still get an occurs check error when trying to define fact5...
Okay the reason is that types in the code end up depending on values. The
type of the stack changes when items are pushed or popped. So the type
of the stack returned from recursive functions depends on the recursion
count...
Haskell is not dependantly typed, so cannot deal with types that depend on
values. This is why your code with tuples, and the HList code (which is
really doing the same thing through a defined API) both fall down on the
recursion.
One solution is to make all elements the same type and use lists... like:
data Elem = ElemInt Int | ElemChar Char...
But this looses any static type checking. The alternative is to lift the
values
to the type level, using something like Peano numbers to represent naturals:
data HZero = HZero
data HSucc x = HSucc x
Now different values have explictly different types, so we can have types
which depend on them...
Attached is an example implementation of times using this technique
and the
HList library (its not debugged... so there might be some mistakes).
Keean.
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-overlapping-instances #-}
{-# OPTIONS -fallow-undecidable-instances #-}
module Joy where
import MainGhcGeneric1
data Lit a = Lit a
instance Apply (Lit a) s (HCons a s) where
apply (Lit a) s = HCons a s
data If = If
instance Apply t s s' = Apply If (HCons f (HCons t (HCons HTrue s))) s' where
apply _ (HCons _ (HCons t (HCons _ s))) = apply t s
instance Apply f s s' = Apply If (HCons f (HCons t (HCons HFalse s))) s' where
apply _ (HCons f (HCons _ (HCons _ s))) = apply f s
data Eq = Eq
instance TypeEq a b t = Apply Eq (HCons a (HCons b s)) (HCons t s) where
apply _ (HCons a (HCons b s)) = HCons (typeEq a b) s
data Dip = Dip
instance Apply a s s' = Apply Dip (HCons a (HCons b s)) (HCons b s') where
apply _ (HCons a (HCons b s)) = HCons b (apply a s)
data Dup = Dup
instance Apply Dup (HCons a s) (HCons a (HCons a s)) where
apply _ s@(HCons a _) = HCons a s
data Pop = Pop
instance Apply Pop (HCons a s) s where
apply _ (HCons _ s) = s
data Swap = Swap
instance Apply Swap (HCons a (HCons b s)) (HCons b (HCons a s)) where
apply _ (HCons a (HCons b s)) = HCons b (HCons a s)
class (HNat a,HNat b) = HAdd a b c | a - b - c where
hadd :: a - b - c
instance HAdd HZero HZero HZero where
hadd _ _ = hZero
instance HAdd HZero (HSucc b) (HSucc b) where
hadd _ b = b
instance HAdd a b c = HAdd (HSucc a) (HSucc b) (HSucc (HSucc c))
hadd _ _ = hadd (undefined::a) (undefined::b)
data Add = Add
instance HAdd a b c = Apply Add (HCons a (HCons b s)) (HCons c s) where
apply _ (HCons _ (HCons _ s)) = HCons (hadd (undefined::a) (undefined::b)) s
data Mult = Mult
instance HMult a b c = Apply Mult (HCons a (HCons b s)) (HCons c s) where
apply _ (HCons _ (HCons _ s)) = HCons (hadd (undefined::a) (undefined::b)) s
data a @ b = a @ b
instance (Apply a s s',Apply b s' s'') = Apply (a @ b) s'' where
apply (O a b) s = apply b (apply a s :: s')
type Square = Dup @ Mult
type Cube = Dup @ Dup @ Mult
data I = I
instance Apply a s s' = Apply I (HCons a s) s' where
apply _ (HCons a s) = apply a s
data Times = Times
instance Apply Times (HCons p (HCons HZero s)) s where
apply _ (HCons _ s) = s
instance Apply p s s' = Apply Times (HCons p (HCons (HSucc n) s) (HCons p (HCons n s')) where
apply _ (HCons p (HCons _ s)) = HCons p (HCons (undefined::n) (apply p s))
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Keean Schupke wrote: Haskell is not dependantly typed, so cannot deal with types that depend on values. Can anyone recommend a nice dependently typed language to play with? Cayenne, Epigram, other? Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Greg Buchholz wrote (on Wed, 09 Mar 2005 at 20:08): Can anyone recommend a nice dependently typed language to play with? Cayenne, Epigram, other? http://www.cs.chalmers.se/~catarina/agda/ See also the sexy IDE alfa: http://www.cs.chalmers.se/~hallgren/Alfa/ Peter Hancock ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Greg Buchholz wrote:
Keean Schupke wrote:
Haskell is not dependantly typed, so cannot deal with types that depend on
values.
Can anyone recommend a nice dependently typed language to play with?
Cayenne, Epigram, other?
I have refactored your code into a type level Haskell program.
This has the nice advantage that it is extensible. You can add a new
primitive to the language as:
data PrimName
primName :: PrimName
primName = undefined
instance Apply PrimName a b where
apply _ a = {- method implementing primName -}
Programs are assembled as types like:
fac4 = lit nul `o` lit suc `o` lit (dup `o` pre)
`o` lit mult `o` linrec
Recursion requires a primitive to aviod infinite types, see
definitions of times, linrec and genrec.
programs are run by applying the contructed type representing the
program to a stack... for example:
putStrLn $ show $ apply (lit hThree `o` fac4) hNil
We could have written this:
putStrLn $ show $ apply fac4 (hCons hThree hNil)
I have attached the debugged code, simply load into ghci, in the same
directory as the HList library (download http://www.cwi.nl/~ralf/HList)
as Joy.hs.
ghci -fallow-overlapping-instances Joy.hs
(you need the flag to get the code to run interactively, however you
dont need the flag just to run 'main' to perform the factorial tests)
Keean.
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-overlapping-instances #-}
{-# OPTIONS -fallow-undecidable-instances #-}
module Joy where
import MainGhcGeneric1
type HOne = HSucc HZero
hOne :: HOne
hOne = undefined
type HTwo = HSucc HOne
hTwo :: HTwo
hTwo = undefined
type HThree = HSucc HTwo
hThree :: HThree
hThree = undefined
data Lit a
lit :: a - Lit a
lit = undefined
unl :: Lit a - a
unl = undefined
instance HList s = Apply (Lit a) s (HCons a s) where
apply a s = hCons (unl a) s
class (HBool b,HList s) = HIfte b t f s s' | b t f s - s' where
hIfte :: b - t - f - s - s'
instance (HList s,Apply t s s') = HIfte HTrue t f s s' where
hIfte _ t _ s = apply t s
instance (HList s,Apply f s s') = HIfte HFalse t f s s' where
hIfte _ _ f s = apply f s
data Ifte
ifte :: Ifte
ifte = undefined
instance (Apply b s r,HHead r b',HIfte b' t f s s')
= Apply Ifte (HCons f (HCons t (HCons b s))) s' where
apply _ (HCons f (HCons t (HCons b s))) = hIfte (hHead (apply b s :: r) :: b') t f s
data Nul
nul :: Nul
nul = undefined
instance HList s = Apply Nul (HCons HZero s) (HCons HTrue s) where
apply _ (HCons _ s) = hCons hTrue s
instance HList s = Apply Nul (HCons (HSucc n) s) (HCons HFalse s) where
apply _ (HCons _ s) = hCons hFalse s
data EQ
eq :: EQ
eq = undefined
instance (HList s,TypeEq a b t) = Apply EQ (HCons a (HCons b s)) (HCons t s) where
apply _ (HCons a (HCons b s)) = hCons (typeEq a b) s
data Dip
dip :: Dip
dip = undefined
instance (HList s,HList s',Apply a s s') = Apply Dip (HCons a (HCons b s)) (HCons b s') where
apply _ (HCons a (HCons b s)) = hCons b (apply a s)
data Dup
dup :: Dup
dup = undefined
instance HList s = Apply Dup (HCons a s) (HCons a (HCons a s)) where
apply _ s@(HCons a _) = hCons a s
data Pop
pop :: Pop
pop = undefined
instance HList s = Apply Pop (HCons a s) s where
apply _ (HCons _ s) = s
data Swap
swap :: Swap
swap = undefined
instance HList s = Apply Swap (HCons a (HCons b s)) (HCons b (HCons a s)) where
apply _ (HCons a (HCons b s)) = hCons b (hCons a s)
data Suc
suc :: Suc
suc = undefined
instance (HNat a,HList s) = Apply Suc (HCons a s) (HCons (HSucc a) s) where
apply _ (HCons _ s) = hCons (undefined::HSucc a) s
data Pre
pre :: Pre
pre = undefined
instance (HNat a,HList s) = Apply Pre (HCons (HSucc a) s) (HCons a s) where
apply _ (HCons _ s) = hCons (undefined::a) s
data Add
add :: Add
add = undefined
instance (HList s,HAdd a b c) = Apply Add (HCons a (HCons b s)) (HCons c s) where
apply _ (HCons _ (HCons _ s)) = hCons (hAdd (undefined::a) (undefined::b)) s
class (HNat a,HNat b) = HAdd a b c | a b - c where
hAdd :: a - b - c
instance HAdd HZero HZero HZero where
hAdd _ _ = hZero
instance HNat b = HAdd HZero (HSucc b) (HSucc b) where
hAdd _ b = b
instance HNat a = HAdd (HSucc a) HZero (HSucc a) where
hAdd a _ = a
instance (HNat (HSucc a),HNat (HSucc b),HNat c,HAdd a b c)
= HAdd (HSucc a) (HSucc b) (HSucc (HSucc c)) where
hAdd _ _ = hSucc $ hSucc $ hAdd (undefined::a) (undefined::b)
data Sub
sub :: Sub
sub = undefined
instance (HList s,HSub a b c) = Apply Sub (HCons b (HCons a s)) (HCons c s) where
apply _ (HCons _ (HCons _ s)) = hCons (hSub (undefined::a) (undefined::b)) s
class (HNat a,HNat b) = HSub a b c | a b - c where
hSub :: a - b - c
instance HSub HZero HZero HZero where
hSub _ _ = hZero
instance HNat a = HSub (HSucc a) HZero (HSucc a) where
hSub a _ = a
instance HNat a = HSub HZero (HSucc a) HZero where
hSub _ _ = hZero
instance (HSub a b c) = HSub (HSucc a) (HSucc b) c where
hSub _ _ = hSub (undefined::a) (undefined::b)
data Mult
mult :: Mult
mult = undefined
instance (HList s,HMult a b c) = Apply Mult (HCons a (HCons
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Keean Schupke wrote: I have refactored your code into a type level Haskell program. This has the nice advantage that it is extensible. Wow. Color me impressed. A little under a week ago, I stumbled onto Joy, and thought to myself that it could be translated almost directly into Haskell (which would imply it was possible to statically type). Well, it wasn't quite as direct as I had initially thought, but it looks like you've done it. Are there any papers/books out there which I could study to learn more about these (and other) tricks of the type system wizards? Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Keean Schupke wrote: Daniel Fischer wrote: And, BTW, that's why Keean et al's HList library doesn't help here either, the type of an HList determines the number of elements and the type of each, so there we face the same problems as with nested tuples. What we need is type Stack = [ArbitraryType] (from the HList paper, I surmise that [Dynamic] would be possible, but that seems to have it's own problems). Well it depends on what you want to do... If the types of elements are determined by the computation then you can use an HList as is, and there is no problem. The problem is that for the recursion combinators we need polymorphic recursion functions. For fact3 we need rec2 :: forall l. (HCons a (HCons a l) - HCons a l), which is illegal in an HList (at least, I haven't found a way to make it acceptable) and in tuples. For the general recursion combinator it's even worse, because rec2 may take n2 elements of certain types from the stack, does something with them and put k2 elements of certain types determined by the types of the consumed elements on the stack, leaving the remainder of the stack unchanged, rec1 takes n1 elements etc. And the numbers n2, n1 . . . and the types depend on the supplied recursion functions. So (reverting to nested pairs notation), we would have to make linrec to accept arguments for rec2 of the types (a,b) - (r,b), (a,(a1,b)) - (r,(r1,(r2,b))), (a,(a1,b)) - (r,b) (a,(a1,(a2,b))) - (r,b) and so on, for arbitrary munch- and return-numbers, where we don't care what b is. These can't be unified however, so I think it's impossible to transfer these combinators faithfully to a strongly typed language. [Dynamic] won't work either, I believe, because Dynamic objects must be monomorphic, as I've just read in the doc. The point is, in Joy all these functions would have type Stack - Stack and we can't make a stack of four elements the same type as a stack of six elements using either nested pairs or HLists (correct me if I'm wrong, you know HList better than I do). However, Joy has only very few datatypes (according to the introduction I looked at), so data Elem = Bool Bool | Char Char | Int Integer | Double Double | String String | Fun (Stack - Stack) | List [Elem] | Set [Int] type Stack = [Elem] type Joy = State Stack (IO ()) looks implementable, probably a lot to write, but not too difficult - maybe, I'll try. The only time there is a problem is if the _type_ of an element to be put in an HList depends on an IO action. In this case you need to existentially quantify the HList. How would I do that? What the user's guide says about existential quantification isn't enough for me. So you can use the HList in both cases, but you have to deal with existential types if the type of the HList is dependant on IO (you dont have to do this if only the value of an element depends on IO). Keean. If you can faithfully implement Greg's code (including fact3-5) using HList, I'd be interested to see it, I think HList suits other purposes far better. Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Am Dienstag, 8. März 2005 17:31 schrieben Sie: Daniel Fischer wrote: The problem is that for the recursion combinators we need polymorphic recursion functions. For fact3 we need rec2 :: forall l. (HCons a (HCons a l) - HCons a l), I dont see why this is illegal... what do we want? take the top two items from the stack? It's illegal, because a type variable may not be instantiated by a forall-type; section 7.4.9 of the user's guide: There is one place you cannot put a forall: you cannot instantiate a type variable with a forall-type. So you cannot make a forall-type the argument of a type constructor. So these types are illegal: x1 :: [forall a. a-a] x2 :: (forall a. a-a, Int) x3 :: Maybe (forall a. a-a). I'd say that also applys to HList, HCons (forall l. (HCons a (HCons a l) - HCons a l)) blah won't work (and my ghci doesn't swallow it). Take the to N elements from the stack: class Take l n h t | l n - h t where take :: l - n - (h,t) instance Take l HZero HNil l where take l _ = (HNil,l) instance Take t n (h',t') = Take (HCons h t) (HSucc n) (HCons h h',t') where take (HCons h t) (_::HSucc n) = (HCons h h',t') where (h',t') = take t (undefined::n) Good, but cumbersome. And I'm not sure what the type signature should be for genrec (HCons rec2 (HCons rec1 (HCons t (HCons b stack | hHead (b stack) = t stack | otherwise = rec2 (HCons (genrec.quote rec2.quote rec1.quote t.quote b) (rec1 stack)) I dare say it would be easier in Haskell-style: genrec rec2 rec1 t b stack. For the general recursion combinator it's even worse, because rec2 may take n2 elements of certain types from the stack, does something with them and put k2 elements of certain types determined by the types of the consumed elements on the stack, leaving the remainder of the stack unchanged, rec1 takes n1 elements etc. And the numbers n2, n1 . . . and the types depend on the supplied recursion functions. So (reverting to nested pairs notation), we would have to make linrec to accept arguments for rec2 of the types (a,b) - (r,b), (a,(a1,b)) - (r,(r1,(r2,b))), (a,(a1,b)) - (r,b) (a,(a1,(a2,b))) - (r,b) and so on, for arbitrary munch- and return-numbers, where we don't care what b is. These can't be unified however, so I think it's impossible to transfer these combinators faithfully to a strongly typed language. [Dynamic] won't work either, I believe, because Dynamic objects must be monomorphic, as I've just read in the doc. The point is, in Joy all these functions would have type Stack - Stack and we can't make a stack of four elements the same type as a stack of six elements using either nested pairs or HLists (correct me if I'm wrong, you know HList better than I do). They are not the same type, but that are the same Kind, or Type-Familly... Aye, but as I understand it, once we push the recursion functions on the stack, they must be monomorphic, which means, the scheme won't work in general. class Stack s instance Stack HNil instance Stack s = Stack (HCons a s) Isn't this exactly the HList class? isItAStack :: Stack s = s - s isItAStack = id However, Joy has only very few datatypes (according to the introduction I looked at), so data Elem = Bool Bool | Char Char | Int Integer | Double Double | String String | Fun (Stack - Stack) | List [Elem] | Set [Int] type Stack = [Elem] type Joy = State Stack (IO ()) looks implementable, probably a lot to write, but not too difficult - maybe, I'll try. The above can be translated to HLists, the difference is that with HLists the types (classes) are extensible. Might well be, only I don't see how (would have to take a log look at HList, probably). Of course, doing it the primitive way means a lot of work every time you add a new datatype :-( But for these types, I did it (with a few modifications) and all works fine. There appears to be no IO in the example Joy code so existentials are unneccessary. No IO around, I only thought I might wish to write an interactive frontend, printing out the top of the stack (might be an error message) after each step. I haven't got round to that yet, and I don't know whether I will, but I think if I do, I'd better use type Joy = IO (State Stack Elem). Keean. Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Keean Schupke wrote:
I dont see why this is illegal... what do we want? take the top two
items from the stack?
With the code below (direct translation from tuples to HLists) I
still get an occurs check error when trying to define fact5...
Compiling Main ( joy3.hs, interpreted )
joy3.hs:23:
Occurs check: cannot construct the infinite type: l = HCons e l
Expected type: HCons
(HCons e (HCons e l) - HCons e l)
(HCons
(HCons e3 l3 - HCons e3 (HCons e3 l3))
(HCons
(HCons e1 l2 - HCons e1 l2)
(HCons (HCons e2 l1 - HCons Bool l1) a)))
- c
Inferred type: HCons
(HCons e (HCons e l) - HCons e (HCons e l))
(HCons
(l4 - l4)
(HCons (l4 - HCons e (HCons e l))
(HCons (l4 - l5) l4)))
- HCons e (HCons e l)
In the second argument of `(!)', namely `linrec'
In the definition of `fact5':
fact5 = quote (nul)) ! (quote (suc))) ! (quote (dup ! pre)))
! (quote (mult)))
! linrec
Failed, modules loaded: MainGhcGeneric1, TypeCastGeneric1, Label3,
TypeEqGeneric1, TypeEqBoolGeneric, GhcExperiments, GhcSyntax,
CommonMain, Datatypes2, Variant, TIC, TIP, HTypeIndexed, GhcRecord,
Record, HZip, HOccurs, HArray, HListPrelude, FakePrelude.
Looks to me like a very similar error to the tuple case.
Greg Buchholz
--Joy combinators in Haskell
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-overlapping-instances #-}
import MainGhcGeneric1
import Data.Typeable
main = do print $ ((lit 10)!(lit 4)!mult) bot -- 4*10
print $ ((lit 3) ! cube ) bot-- 3^3
print $ ((lit 4) ! fact5) bot-- 4!
bot = HNil
square = dup ! mult
cube = dup ! dup ! mult ! mult
nul = (lit 0) ! eq
suc = (lit 1) ! add
pre = (lit 1) ! sub
--In Joy: [null] [succ] [dup pred] [*] linrec
fact5 :: HCons Integer a - HCons Integer a
fact5 = quote(nul) ! quote(suc) ! quote(dup ! pre) ! quote(mult) ! linrec
--}
--primitive combinators
(!) f g = g.f
i(a, b) = (a b)
add (HCons a (HCons b c)) = (HCons (b+a) c)
sub (HCons a (HCons b c)) = (HCons (b-a) c)
mult (HCons a (HCons b c)) = (HCons (b*a) c)
swap (HCons a (HCons b c)) = (HCons b (HCons a c))
pop (HCons a b) = b
dup (HCons a b) = (HCons a (HCons a b))
dip (HCons a (HCons b c)) = (HCons b, (a c))
eq (HCons a (HCons b c)) | a == b= (HCons True c)
| otherwise = (HCons False c)
ifte (HCons f (HCons t (HCons b stack)))
| hHead(b stack) = (t stack)
| otherwise = (f stack)
linrec (HCons rec2 (HCons rec1 (HCons t (HCons p stack
| hHead (p stack) = (t stack)
| otherwise = rec2 (linrec (HCons rec2
(HCons rec1
(HCons t
(HCons p (rec1 stack))
lit val stack = (HCons val stack)
quote = lit
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Daniel Fischer wrote: Am Freitag, 4. M?rz 2005 19:35 schrieb Greg Buchholz: So, can anyone direct me towards more information on exactly what an Occurs check is, or does anyone see an easy fix to my problems? If I remember correctly, an occurs check is checking whether a type variable (call it 't') occurs as an argument to a tuple constructor or function arrow in a type expression to be substituted for t, as above or in t = t - t1. Such occurences would lead to an infinite type, hence are forbidden. Interesting, I'll have to think it over. (Of course being a relative newcomer to Haskell, I have to do a lot of thinking when it comes to most things.) BTW, can anyone recommend a good introductory resource for learning about type theory? I once flipped through Pierce's Types_and_Programming_Languages, but at first glance, it seemed to be a little advanced for my understanding (the foreign-looking equations per word ratio seemed a little too high). I have a fix for the factorial and similar recursive functions, though it's not really easy (and needs extensions): don't define the recursion combinators via Stack, do it like this: linrec2 :: forall a. (forall b. (a,(a,b)) - (a,b)) - (forall b. (a,b) - (a,(a,b))) - (forall b. (a,b) - (a,b)) - (forall b. (a,b) - (Bool,b)) - (forall b. (a,b) - (a,b)) linrec2 rec2 rec1 t p stack | fst $ p stack = t stack | otherwise = rec2 $ linrec2 rec2 rec1 t p (rec1 stack) Nice. Definitely something for me to study. Of course, IFAICT, the main motivation for Joy is to try and define everything in terms of function composition instead of function application. I don't know Joy, but probably there the stack is (roughly) a heterogenous list, which is hard to model in Haskell, Yeah, I don't know Joy either, other than reading a few documents, but I do think its stack is really heterogenous list. The one reason I was thinking this might be doable in Haskell, is the fact that the few combinators I looked at don't recurse down the whole stack. That, of course, would be a complete nightmare in Haskell. Instead they take a stack, munge a few (finite number of) items at the top, and return another stack. I was hoping that the type variable a in (Integer, a) - (Integer, a) would be amorphous enough to match whatever was left over after grabbing a few items off the top of this stack. Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Am Montag, 7. März 2005 17:58 schrieb Greg Buchholz: Daniel Fischer wrote: Am Freitag, 4. März 2005 19:35 schrieb Greg Buchholz: So, can anyone direct me towards more information on exactly what an Occurs check is, or does anyone see an easy fix to my problems? If I remember correctly, an occurs check is checking whether a type variable (call it 't') occurs as an argument to a tuple constructor or function arrow in a type expression to be substituted for t, as above or in t = t - t1. Such occurences would lead to an infinite type, hence are forbidden. Interesting, I'll have to think it over. (Of course being a relative newcomer to Haskell, I have to do a lot of thinking when it comes to most things.) BTW, can anyone recommend a good introductory resource for learning about type theory? I once flipped through Pierce's Types_and_Programming_Languages, but at first glance, it seemed to be a little advanced for my understanding (the foreign-looking equations per word ratio seemed a little too high). I have a fix for the factorial and similar recursive functions, though it's not really easy (and needs extensions): don't define the recursion combinators via Stack, do it like this: linrec2 :: forall a. (forall b. (a,(a,b)) - (a,b)) - (forall b. (a,b) - (a,(a,b))) - (forall b. (a,b) - (a,b)) - (forall b. (a,b) - (Bool,b)) - (forall b. (a,b) - (a,b)) linrec2 rec2 rec1 t p stack | fst $ p stack = t stack | otherwise = rec2 $ linrec2 rec2 rec1 t p (rec1 stack) Nice. Definitely something for me to study. Of course, IFAICT, the main motivation for Joy is to try and define everything in terms of function composition instead of function application. One more, you need not supply a type signature for fact, if you provide the argument: fact0 (n,st) = ifte (dup ! pre ! fact ! mult, (pop ! lit 1, (nul, (n,st That's of course rather unJoyful :-), but it helps the type-checker (I don't know the workings thereof, but it's often the case that functions which don't type-check points-free do if sufficiently many arguments are provided). I don't think that'll help fact3-5, though. I don't know Joy, but probably there the stack is (roughly) a heterogenous list, which is hard to model in Haskell, Yeah, I don't know Joy either, other than reading a few documents, I've taken a look, and I must say, I find Haskell more intuitive. but I do think its stack is really heterogenous list. The one reason I was thinking this might be doable in Haskell, is the fact that the few combinators I looked at don't recurse down the whole stack. That, of I think, it would be possible to define recursion combinators for specific patterns, like this functions takes 4 elements from the stack, this one 3 and so on, but then you would need combinators for all these patterns, which is rather cumbersome. IMO, it's just not the thing to do things in Haskell exactly like in Joy (or in Java, prolog, or - horribile dictu- in C/C++). Even if it's possible, the spirit of the languages is so different that you should do the same thing in different ways. But of course it's interesting to see whether it can be done. course, would be a complete nightmare in Haskell. Instead they take a stack, munge a few (finite number of) items at the top, and return That's nightmarish enough, because Haskell is strongly typed. So, if we look at linrec, for example, we find that rec2 and rec1 must return the same type as they devour, that's why fact5 doesn't work, because mult has type Num a = (a,(a,b)) - (a,b). And, BTW, that's why Keean et al's HList library doesn't help here either, the type of an HList determines the number of elements and the type of each, so there we face the same problems as with nested tuples. What we need is type Stack = [ArbitraryType] (from the HList paper, I surmise that [Dynamic] would be possilble, but that seems to have it's own problems). another stack. I was hoping that the type variable a in (Integer, a) - (Integer, a) would be amorphous enough to match whatever was left over after grabbing a few items off the top of this stack. Well, it's fairly amorphous, but it must be the same type in both type-expressions, and that's why the points-free definition of fact doesn't type-check without the type signature, the 'fact' in the else-branch is used at type (Integer,(Integer,a)) and so on, without the type signature, the type-checker assumes that it must be instantiated at exactly the same type, which it isn't. With the signature, the type-checker knows that 'fact' is polymorphic and that it's perfectly all right to instantiate it at a different type in the recursive call. Well, at least that's what I worked out from my sparse knowledge, if I'm wrong, would somebody please correct me? Thanks, Greg Buchholz HTH, Daniel
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Daniel Fischer wrote: And, BTW, that's why Keean et al's HList library doesn't help here either, the type of an HList determines the number of elements and the type of each, so there we face the same problems as with nested tuples. What we need is type Stack = [ArbitraryType] (from the HList paper, I surmise that [Dynamic] would be possilble, but that seems to have it's own problems). Well it depends on what you want to do... If the types of elements are determined by the computation then you can use an HList as is, and there is no problem. The only time there is a problem is if the _type_ of an element to be put in an HList depends on an IO action. In this case you need to existentially quanify the HList. So you can use the HList in both cases, but you have to deal with existential types if the type of the HList is dependant on IO (you dont have to do this if only the value of an element depends on IO). Keean. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Daniel Fischer wrote: I think, it would be possible to define recursion combinators for specific patterns, like this functions takes 4 elements from the stack, this one 3 and so on, but then you would need combinators for all these patterns, which is rather cumbersome. Hmm. The standard Joy combinators probably can't be typed, so maybe my next step would be to find/create a recursion combinator with a static type. Surely one must exist? If you can have a typed lambda calculus, you must be able to have a typed SK combinator calculus, right? (Now I'm way out of my league.) I'll have to think some more on why you couldn't have a recursion combinator which was more generic than the one that takes 3 items off the stack, or 4 items, rather than n items. Or maybe the whole idea of using a stack is the essential weakness. IMO, it's just not the thing to do things in Haskell exactly like in Joy (or in Java, prolog, or - horribile dictu- in C/C++). Even if it's possible, the spirit of the languages is so different that you should do the same thing in different ways. But of course it's interesting to see whether it can be done. Yeah. I'm only in it for the brain exercise, not to convert the masses over to Joy ;-) ...another stack. I was hoping that the type variable a in (Integer, a) - (Integer, a) would be amorphous enough to match whatever was left over after grabbing a few items off the top of this stack. Well, it's fairly amorphous, but it must be the same type in both type-expressions, and that's why the points-free definition of fact doesn't type-check without the type signature, the 'fact' in the else-branch is used at type (Integer,(Integer,a)) and so on, without the type signature, the type-checker assumes that it must be instantiated at exactly the same type, which it isn't. With the signature, the type-checker knows that 'fact' is polymorphic and that it's perfectly all right to instantiate it at a different type in the recursive call. That pretty much sums up why I thought the whole crazy scheme might work, only in better words. Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
On Mon, Mar 07, 2005 at 08:47:11PM +0100, Daniel Fischer wrote: And, BTW, that's why Keean et al's HList library doesn't help here either, the type of an HList determines the number of elements and the type of each, so there we face the same problems as with nested tuples. What we need is type Stack = [ArbitraryType] (from the HList paper, I surmise that [Dynamic] would be possilble, but that seems to have it's own problems). It would be interesting if you could use the HList framework for 'partially typed lists' in that if your stack is an hlist, an operation like plus would be plus :: forall a. HList a = Int :*: Int :*: a - Int :*: a which says that plus goes from ANY Hlist starting with two ints and returns that hlist with a single Int on it. basically you use a universally quantified type to represent the unknown tail of the list (everything else on the stack). not sure if it works.. just brainstorming It seems very natural if it could be made to work. John -- John Meacham - repetae.netjohn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Daniel Fischer wrote: I don't know Joy, but probably there the stack is (roughly) a heterogenous list, which is hard to model in Haskell, think of data Element = Bool Bool | Char Char | Int Int . . . | IntToBool (Int - Bool) . . . type Stack = [Element] and how to define functions for that, urgh. Not saying it isn't tricky - but thats what the HList library (http://www.cwi.nl/~ralf/HList) implements, a heterogenous list. It works slightly differently using classes, but does abstract the workings enough to be useful, to construct an HList you can do: hlist = a .*. (3:Int) .*. False .*. 'v' .*. HNil And provides head/tail functions and other useful list and set operators. Keean. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Keean wrote: Not saying it isn't tricky - but thats what the HList library (http://www.cwi.nl/~ralf/HList) implements, a heterogenous list. It works slightly differently using classes, but does abstract the workings enough to be useful, to construct an HList you can do: hlist = a .*. (3:Int) .*. False .*. 'v' .*. HNil And provides head/tail functions and other useful list and set operators. Keean. Phew, not bad, but not easy to absorb. Do you know whether the Joy Combinators would work with HList? If I find the time, I'll try to see for myself tomorrow, but I'm not sure that I will. Respectfully, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Am Freitag, 4. März 2005 19:35 schrieb Greg Buchholz:
Recently, while investigating the (non-statically typed) stack-based
functional language Joy
(http://www.latrobe.edu.au/philosophy/phimvt/joy.html), I became interested
in seeing if I could implement Joy's combinators in Haskell. I started
with a stack based implementation using nested tuples as the stack. Things
worked out well until I got to the
recursion combinators. Even then, things didn't seem that bad, since
Haskell was able to infer types for the the linrec and genrec
combinators. Trouble popped up when I tried to apply the recursion
operators to a function (in this case calculating the humble factorial).
In the code below, fact3,4 5 all fail with an Occurs check that
looks something like the following...
joy3.hs:24:
Occurs check: cannot construct the infinite type: t = (a, t)
Expected type: ((a5 - (a, (a, t)), a5) - (a, t),
((a1, t3) - (a1, (a1, t3)),
((a2, t2) - (a2, t2), ((a3, t1) - (Bool,
t1),a4 - c
Inferred type: ((a5 - (a, (a, t)), a5) - (a, (a, t)),
(a5 - a5, (a5 - (a, (a, t)), (a5 - (Bool,
b),a5 - (a, (a, t))
...Normally, I would have given up and declared that Joy wasn't an easily
typed language, but I'm motivated to dig further because if you remove
the type signature from fact below, it also fails with an Occurs
check. So, can anyone direct me towards more information on exactly
what an Occurs check is, or does anyone see an easy fix to my
problems?
If I remember correctly, an occurs check is checking whether a type variable
(call it 't') occurs as an argument to a tuple constructor or function arrow
in a type expression to be substituted for t, as above or in
t = t - t1.
Such occurences would lead to an infinite type, hence are forbidden.
If you really think you need such things,
data Pair a b = P (a, (Pair a b))
works, however that type contains no fully defined values, so is only of
limited usefulness.
I have a fix for the factorial and similar recursive functions, though it's
not really easy (and needs extensions):
don't define the recursion combinators via Stack, do it like this:
linrec2 :: forall a. (forall b. (a,(a,b)) - (a,b)) -
(forall b. (a,b) - (a,(a,b))) -
(forall b. (a,b) - (a,b)) -
(forall b. (a,b) - (Bool,b)) -
(forall b. (a,b) - (a,b))
linrec2 rec2 rec1 t p stack
| fst $ p stack = t stack
| otherwise = rec2 $ linrec2 rec2 rec1 t p (rec1 stack)
and similarly for genrec. Then you can define
fact6 = linrec2 mult (dup ! pre) suc nul.
You cannot use linrec, because rec2 and rec1 must each have identical result
and argument types:
*Joy :t linrec
linrec :: forall t b b.
(t - t, (b - b, (b - t, (b - (Bool, b), b - t
I don't know Joy, but probably there the stack is (roughly) a heterogenous
list, which is hard to model in Haskell, think of
data Element = Bool Bool
| Char Char
| Int Int
. . .
| IntToBool (Int - Bool)
. . .
type Stack = [Element]
and how to define functions for that, urgh.
Thanks,
Greg Buchholz
P.S. The first thing you should note about the code below is the
definition of the reverse composition operator (!), which I used to give
the program a more Joy-like feel. (i.e. (!) f g = g.f)
--Joy combinators in Haskell
main = do print $ ((lit 6) ! fact) bot-- factorial of 6
print $ ((lit 2) ! square ! fact2) bot -- factorial of 4
bot = EOS -- end of stack
square = dup ! mult
cube = dup ! dup ! mult ! mult
--In Joy: factorial == [0 =] [pop 1] [dup 1 - factorial *] ifte
fact :: (Integer, a) - (Integer, a)
fact = (quote ((lit 0) ! eq)) !
(quote (pop ! (lit 1))) !
(quote (dup ! (lit 1) ! sub ! fact ! mult)) !
ifte
--In Joy: [1 1] dip [dup [*] dip succ] times pop
fact2 = (quote ((lit 1) ! (lit 1)))
! dip ! (quote (dup ! (quote mult) ! dip ! suc))
! times ! pop
{- fact3,4 5 don't type check, fails with...
-- Occurs check: cannot construct the infinite type:
--In Joy: [null] [succ] [dup pred] [i *] genrec
fact3 :: (Integer, a) - (Integer, a)
fact3 = (quote nul) ! (quote suc) ! (quote (dup ! pre)) ! (quote (i !
mult)) ! genrec
fact4 :: (Integer, a) - (Integer, a)
fact4 = genrec.quote(mult.i).quote(pre.dup).quote(suc).quote(nul)
--In Joy: [null] [succ] [dup pred] [*] linrec
fact5 :: (Integer, a) - (Integer, a)
fact5 = quote(nul) ! quote(suc) ! quote(dup ! pre) ! quote(mult) ! linrec
--}
nul = (lit 0) ! eq
suc = (lit 1) ! add
pre = (lit 1) ! sub
linrec (rec2, (rec1, (t, (p, stack
| fst (p stack) == True = (t stack)
^^
fst (p stack) suffices.
| otherwise =
[Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Recently, while investigating the (non-statically typed) stack-based
functional language Joy (http://www.latrobe.edu.au/philosophy/phimvt/joy.html),
I became interested in seeing if I could implement Joy's combinators in
Haskell. I started with a stack based implementation using nested
tuples as the stack. Things worked out well until I got to the
recursion combinators. Even then, things didn't seem that bad, since
Haskell was able to infer types for the the linrec and genrec
combinators. Trouble popped up when I tried to apply the recursion
operators to a function (in this case calculating the humble factorial).
In the code below, fact3,4 5 all fail with an Occurs check that
looks something like the following...
joy3.hs:24:
Occurs check: cannot construct the infinite type: t = (a, t)
Expected type: ((a5 - (a, (a, t)), a5) - (a, t),
((a1, t3) - (a1, (a1, t3)),
((a2, t2) - (a2, t2), ((a3, t1) - (Bool, t1),a4
- c
Inferred type: ((a5 - (a, (a, t)), a5) - (a, (a, t)),
(a5 - a5, (a5 - (a, (a, t)), (a5 - (Bool, b),a5
- (a, (a, t))
...Normally, I would have given up and declared that Joy wasn't an easily
typed language, but I'm motivated to dig further because if you remove
the type signature from fact below, it also fails with an Occurs
check. So, can anyone direct me towards more information on exactly
what an Occurs check is, or does anyone see an easy fix to my
problems?
Thanks,
Greg Buchholz
P.S. The first thing you should note about the code below is the
definition of the reverse composition operator (!), which I used to give
the program a more Joy-like feel. (i.e. (!) f g = g.f)
--Joy combinators in Haskell
main = do print $ ((lit 6) ! fact) bot-- factorial of 6
print $ ((lit 2) ! square ! fact2) bot -- factorial of 4
bot = EOS -- end of stack
square = dup ! mult
cube = dup ! dup ! mult ! mult
--In Joy: factorial == [0 =] [pop 1] [dup 1 - factorial *] ifte
fact :: (Integer, a) - (Integer, a)
fact = (quote ((lit 0) ! eq)) !
(quote (pop ! (lit 1))) !
(quote (dup ! (lit 1) ! sub ! fact ! mult)) !
ifte
--In Joy: [1 1] dip [dup [*] dip succ] times pop
fact2 = (quote ((lit 1) ! (lit 1)))
! dip ! (quote (dup ! (quote mult) ! dip ! suc))
! times ! pop
{- fact3,4 5 don't type check, fails with...
-- Occurs check: cannot construct the infinite type:
--In Joy: [null] [succ] [dup pred] [i *] genrec
fact3 :: (Integer, a) - (Integer, a)
fact3 = (quote nul) ! (quote suc) ! (quote (dup ! pre)) ! (quote (i ! mult))
! genrec
fact4 :: (Integer, a) - (Integer, a)
fact4 = genrec.quote(mult.i).quote(pre.dup).quote(suc).quote(nul)
--In Joy: [null] [succ] [dup pred] [*] linrec
fact5 :: (Integer, a) - (Integer, a)
fact5 = quote(nul) ! quote(suc) ! quote(dup ! pre) ! quote(mult) ! linrec
--}
nul = (lit 0) ! eq
suc = (lit 1) ! add
pre = (lit 1) ! sub
linrec (rec2, (rec1, (t, (p, stack
| fst (p stack) == True = (t stack)
| otherwise = rec2 (linrec (rec2, (rec1, (t, (p, (rec1 stack))
genrec (rec2, (rec1, (t, (b, stack
| fst (b stack) == True = (t stack)
| otherwise = (rec2.quote(genrec.quote(rec2).quote(rec1).
quote(t).quote(b))) (rec1 stack)
times (p, (n, stack)) | n0 = times (p, (n-1, (p stack)))
| otherwise = stack
(!) f g = g.f
i(a, b) = (a b)
add (a, (b, c)) = (b+a, c)
sub (a, (b, c)) = (b-a, c)
mult (a, (b, c)) = (b*a, c)
swap (a, (b, c)) = (b, (a, c))
pop (a, b) = b
dup (a, b) = (a, (a, b))
dip (a, (b, c)) = (b, (a c))
eq (a, (b, c)) | a == b= (True, c)
| otherwise = (False,c)
ifte (f, (t, (b, stack))) | fst (b stack) == True = (t stack)
| otherwise = (f stack)
lit val stack = (val, stack) -- push literals on the stack
quote = lit
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
