[Haskell-cafe] Typechecker to GADT: the full implementation of a typed DSL
Pasqualino 'Titto' Assini wrote:
I am trying to write an interpreter for a little functional language but I am
finding very problematic to dynamically create a typed representations of the
language terms.
The problem is to write a function that converts between Exp and Term
t as in:
test :: Term Double
test = typecheck $ EApp (EPrim inc) (EDouble 10.0)
The specification leaves out a few important details. The typechecker can't
be a total function: what happens when typechecking this code?
EApp (EDouble 10.0) (EPrim inc)
The error has to be reported somehow, and it is important to know how.
There are basically two choices. One is to keep the above interface
test :: Term Double
test = typecheck $ EApp (EPrim inc) (EDouble 10.0)
which means using Template Haskell and means letting TH reporting
type errors (with no hope of catching them). The second choice is
`typing dynamic typing'. Which means we can't write a typechecker with
the signature Exp - Term t. Rather, we have to write
typecheck :: Exp - (forall t. Typ t - Term t - w) - Maybe w
or, equivalently, using an existential
data MostlyStatic = forall t. MostlyStatic (Typ t, Term t)
typecheck :: Exp - Maybe MostlyStatic
Although both MostlyStatic and Exp are `untyped', the latter is
`deeply' untyped, whereas the former is only untyped at the
surface. In the case of MostlyStatic, the term is built out of typed
components, and the type is erased only at the end.
These choices aren't contradictory: using TH, we can convert
MostlyStatic to the proper Haskell term. Because the term has already
been typechecked, we are guaranteed the absence of errors during such
a conversion.
For today, perhaps the implementation of the second choice will be
sufficient. This is the complete representation of a typed DSL given
in the untyped AST form. We typecheck a term. We either report a
type error, or evaluate the typed term and then report result, if can be
shown. We also show the inferred type of the result.
Examples. Let's assume the following terms (not all of them well-typed)
te1 = EApp (EPrim inc) (EDouble 10.0)
te2 = EApp (EDouble 10.0) (EPrim inc)
te3 = EApp (EApp (EPrim +)
(EApp (EPrim inc) (EDouble 10.0)))
(EApp (EPrim inc) (EDouble 20.0))
te4 = EApp (EPrim rev) te3
te5 = EApp (EPrim rev) (EApp (EPrim show) te3)
*Eval teval te1
type Double, value 11.0
*Eval teval te2
Type error: Trying to apply not-a-function: Double
*Eval teval te3
type Double, value 32.0
*Eval teval te4
Type error: incompatible type of the application: (String-String) and Double
*Eval teval te5
type String, value 0.23
The complete code follows
{-# OPTIONS -fglasgow-exts #-}
-- Typechecker to GADT
-- Implementing a typed DSL with the typed evaluator and the
-- the typechecker from untyped terms to typed ones
module Eval where
-- Untyped terms (what I get from my parser):
data Exp = EDouble Double |
EString String |
EPrim String |
EApp Exp Exp deriving (Show)
-- Typed terms:
data Term a where
Num :: Double - Term Double
Str :: String - Term String
App :: Term (a-b) - Term a - Term b
Fun :: (a-b) - Term (a-b)
-- Typed evaluator
eval :: Term a - a
eval (Num x) = x
eval (Str x) = x
eval (Fun x ) = x
eval (App e1 e2) = (eval e1) (eval e2)
-- Types and type comparison
data Typ a where
TDouble :: Typ Double
TString :: Typ String
TFun:: Typ a - Typ b - Typ (a-b)
data EQ a b where
Refl :: EQ a a
-- checking that two types are the same. If so, give the witness
eqt :: Typ a - Typ b - Maybe (EQ a b)
eqt TDouble TDouble = Just $ Refl
eqt TString TString = Just $ Refl
eqt (TFun ta1 tb1) (TFun ta2 tb2) = eqt' (eqt ta1 ta2) (eqt tb1 tb2)
where
eqt' :: (Maybe (EQ ta1 ta2)) - Maybe (EQ tb1 tb2) -
Maybe (EQ (ta1 - tb1) (ta2 - tb2))
eqt' (Just Refl) (Just Refl) = Just Refl
eqt' _ _ = Nothing
eqt _ _ = Nothing
instance Show (Typ a) where
show TDouble = Double
show TString = String
show (TFun ta tb) = ( ++ show ta ++ - ++ show tb ++ )
-- Type checking
data MostlyStatic = forall t. MostlyStatic (Typ t, Term t)
-- Typing environment
type Gamma = [(String,MostlyStatic)]
-- Initial environment (the types of primitives)
env0 = [(rev, MostlyStatic (TFun TString TString,
Fun (reverse::String-String))),
-- sorry, no polymorphism!
(show, MostlyStatic (TFun TDouble TString,
Fun (show::Double-String))),
(inc, MostlyStatic (TFun TDouble TDouble,
Fun ((+ (1.0::Double),
(+,MostlyStatic (TFun TDouble (TFun TDouble TDouble),
Fun ((+)::Double-Double-Double)))
]
typecheck :: Gamma - Exp - Either String MostlyStatic
-- literals
typecheck _ (EDouble x) = Right $ MostlyStatic (TDouble, Num x)
typecheck _ (EString x) = Right $ MostlyStatic
[Haskell-cafe] Re: Function composition
Look at the type of (.).(.).(.) Dominic. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: The Exp - Term a problem (again), how to dynamically create (polymorphic) typed terms in Haskell ??
Did you look at Ralf Hinze's paper Fun with Phantom Types? Dominic. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why not assign a type to unsafePerformIO?
Hello Justin, Thursday, October 4, 2007, 1:47:00 AM, you wrote: Which could be stripped off it you wanted: evilDictatator :: a evilDictator = runUnsafe $ launchMissiles just imagine using ByteString library with all these runUnsafe calls flying around :))) or using immutable arrays - in Hugs, they are implemented using unsafeIOToST. and the last point - because almost everything is based on using C calls and they *can* launch missiles, you should have *every* library function imported to be in these Unsafe monad. are you really need it? :D -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Haskell FFI and finalizers
Hello Maxime, Thursday, October 4, 2007, 2:55:41 AM, you wrote: If I write a small C function for doing the finalizer myself, I still wouldn't get passed the FILE * to close, only the struct foo * pointer which is of no use. you can use global assocs list -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Exp - Term a problem (again), how to dynamically create (polymorphic) typed terms in Haskell ??
On 10/4/07, Pasqualino 'Titto' Assini [EMAIL PROTECTED] wrote: It does not seem to be possible to define typecheck on EApp in a generic way and is also not possible to distinguish between the different cases: You want to pattern-match on types and the easiest way to do it is to introduce a witness GADT for types, something like: data Type a where TString :: Type String TFun :: Type a - Type b - Type (a - b) ... It will be useful to write function: termType :: Term a - Type a You'll probably have to decorate Term constructors with Type's in a few places. As for the typecheck function - it has to be able to return any Term type, dynamically. Existentially quantificated data constructors will be handy here. Here's what I use: data Dyn c = forall a. Dyn (c a) withDyn :: Dyn c - (forall a. c a - b) - b withDyn (Dyn e) f = f e Your typecheck function can have type: typecheck :: Exp - Dyn Term or rather typecheck :: Exp - Maybe (Dyn Term) You define it recursively, getting Dyn Term for subexpressions, checking their types, building bigger Dyn Terms, and so on. You'll probably need some other support functions for working with Dyn and Type - at least I did. I think something similar is presented in Hinze's paper, recommended by Dominic. Best regards Tomasz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Function composition
On 10/4/07, Dominic Steinitz [EMAIL PROTECTED] wrote: Look at the type of (.).(.).(.) Indeed, this generalizes to functions of any arity on the RHS: Prelude :t (.) (.) :: (b - c) - (a - b) - a - c Prelude :t (.).(.) (.).(.) :: (b - c) - (a - a1 - b) - a - a1 - c Prelude :t (.).(.).(.) (.).(.).(.) :: (b - c) - (a - a1 - a2 - b) - a - a1 - a2 - c Prelude :t (.).(.).(.).(.) (.).(.).(.).(.) :: (b - c) - (a - a1 - a2 - a3 - b) - a - a1 - a2 - a3 - c Of course, if you want higher-arity functions anywhere *other* than the head of your composition chain, you'll have to resort to tupling and uncurrying. Stuart ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC doesn't work
2007/10/3, Andrew Coppin [EMAIL PROTECTED]: The entry point OpenThread could not be found in KERNEL32.dll. Are you using NT 4? Probably GHC 6.6.1 dropped support for it (or maybe the binary you downloaded was compiled without the support for it), as this error message means more or less your OS is too old to run this. Salvatore ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: bizarre memory usage with data.binary
On 10/4/07, Jules Bean [EMAIL PROTECTED] wrote: ...and indeed it can't be done, except by the naive brute-force method of comparing every subtree, possibly optimised by cryptographically hashing a representation of every subtree, since sharing isn't an observable property. At least one Prolog implementation (I forget which, I'm sorry), had a [de]serialisation library which used a hash-consing approach. Basically, it did its serialization using a post-order traversal and emitted references to previous values when the same value had already been emitted. Not rocket science. Actually, I've heard a Prolog guy - Bart Demoen - talk about doing pretty much this during GC to improve sharing. cheers, T. -- Thomas Conway [EMAIL PROTECTED] Silence is the perfectest herald of joy: I were but little happy, if I could say how much. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: bizarre memory usage with data.binary
Thomas Conway wrote: On 10/4/07, Jules Bean [EMAIL PROTECTED] wrote: ...and indeed it can't be done, except by the naive brute-force method of comparing every subtree, possibly optimised by cryptographically hashing a representation of every subtree, since sharing isn't an observable property. At least one Prolog implementation (I forget which, I'm sorry), had a [de]serialisation library which used a hash-consing approach. Basically, it did its serialization using a post-order traversal and emitted references to previous values when the same value had already been emitted. Not rocket science. Actually, I've heard a Prolog guy - Bart Demoen - talk about doing pretty much this during GC to improve sharing. Not rocket science at all, but relatively expensive. A time/space tradeoff. And these days, with memory and disks feeling cheap, most people want to trade time for space, not the other way around. Not everyone, of course. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell FFI and finalizers
Stefan O'Rear wrote: Calling Haskell code from the garbage collector is essentially impossible to do efficiently and correctly. Don't even try it, your sanity is not worth saving 3 lines of C coding. It is a sad thing indeed if that is correct advice. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell FFI and finalizers
Stefan O'Rear wrote: On Thu, Oct 04, 2007 at 12:55:41AM +0200, Maxime Henrion wrote: When writing the binding for foo_new(), I need to open a file with fopen() to pass it the FILE *. Then I get a struct foo * that I can easily associate the the foo_destroy() finalizer. However, when finalizing the struct foo * object, I want to also close the FILE * handle. If I write a small C function for doing the finalizer myself, I still wouldn't get passed the FILE * to close, only the struct foo * pointer which is of no use. Ah, yes, this does make the situation more interesting. Looks like newForeignPtrEnv is maybe what you want? Yeah, this is what I use now. I wrote a player_finalizer() function in C, that takes a FILE * and a pointer to the struct I'm handling, and which just closes the file. I then added these sources to the mix in my .cabal file (with C-Sources, Extra-Includes, etc), and registered this new finalizer using addForeignPtrFinalizerEnv. This makes me want to ask you, what is so bad about Foreign.Concurrent that it should be avoided at almost any cost? It sure is likely to be much slower than just calling a plain C finalizer, but aren't Haskell threads super-cheap anyways? I'm not doubting your advices at all, but want to make sure I understand all this fully :-). Thanks again, Maxime ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: bizarre memory usage with data.binary
On 2007-10-04, Jules Bean [EMAIL PROTECTED] wrote: Thomas Conway wrote: On 10/4/07, Jules Bean [EMAIL PROTECTED] wrote: ...and indeed it can't be done, except by the naive brute-force method of comparing every subtree, possibly optimised by cryptographically hashing a representation of every subtree, since sharing isn't an observable property. At least one Prolog implementation (I forget which, I'm sorry), had a [de]serialisation library which used a hash-consing approach. Basically, it did its serialization using a post-order traversal and emitted references to previous values when the same value had already been emitted. Not rocket science. Actually, I've heard a Prolog guy - Bart Demoen - talk about doing pretty much this during GC to improve sharing. Not rocket science at all, but relatively expensive. A time/space tradeoff. And these days, with memory and disks feeling cheap, most people want to trade time for space, not the other way around. Caches are still limited sizes, and that can make a huge difference for time. -- Aaron Denney -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Space and time leaks
On 2007-10-04, Ronald Guida [EMAIL PROTECTED] wrote: I need some help with space and time leaks. I know of two types of space leak. The first type of leak occurs when a function uses unnecessary stack or heap space. GHCi sum [1..10^6] *** Exception: stack overflow Apparently, the default definition for sum has a space leak. I can define my own sum in terms of strict foldl ... sum' xs = foldl' (+) 0 xs ... and it doesn't overflow the stack. GHCi sum' [1..10^6] 5050 (0.27 secs, 112403416 bytes) GHCi sum' [1..10^7] 500500 (2.73 secs, 1161223384 bytes) GHCi sum' [1..10^8] 50005000 (27.83 secs, 11645261144 bytes) I think there's still a space leak; I don't understand why GHCi using 10^8, 10^9, 10^10 bytes of memory for these calculations. This isn't a space leak. The memory reported is the total amount of allocation done, not the most used at a given time. A C program that did x = malloc(20); free(x); x = malloc(20); free(x); would be reporting 40. The run-time system is essentially constructing all of these Integers (and functions returning them) at one point or another, and these need to be represented. Compare with last on these structures: Prelude last [1..10^6] 100 (0.06 secs, 40895096 bytes) Prelude last [1..10^7] 1000 (0.50 secs, 402118492 bytes) Prelude last [1..10^8] 1 (4.74 secs, 4016449660 bytes) -- Aaron Denney -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Typechecker to GADT: the full implementation of a typed DSL
Oleg,
thank you so much for taking the time to provide the example code and the
explanation, it really helps.
My mental typechecker seems to diverge on the data EQ a b where Refl :: EQ
a a bit so I am now reading the typing dynamic typing paper, hoping for
further enlightment.
If you don't mind, I would have a question regarding the usage of Template
Haskell to convert the AST to a typed term.
I have found this paper by Louis-Julien Guillemette and Stefan Monnier :
http://www.iro.umontreal.ca/~monnier/tct.pdf
The code that I could extract from the paper (there doesn't seem to be a code
distribution) follows.
I don't see however how this could possibly be used to implement an
interpreter, certainly the AST must be known at compile time, or am I missing
something?
Thanks again,
titto
{-# OPTIONS -fglasgow-exts -fth #-}
module HOASEval where
import Language.Haskell.TH
type VarId = String
data AST = Fvar VarId | Flam VarId AST | Fapp AST AST
lift :: AST - ExpQ
lift (Fvar x) = varE (mkName x)
lift (Flam x b) = [| Lam $(lam1E (varP (mkName x)) (lift b)) |]
lift (Fapp a b) = [| App $(lift a) $(lift b) |]
data Term t where
Num :: Int - Term Int
Prim :: PrimOp - Term Int - Term Int - Term Int
If0 :: Term Int - Term t - Term t - Term t
Lam :: (Term s - Term t) - Term (s - t)
App :: Term (s - t) - Term s - Term t
data PrimOp = Add | Sub | Mult
e0 = Flam x (Fvar x)
eval ast = $(lift ast)
test = eval e0
On Thursday 04 October 2007 07:02:32 [EMAIL PROTECTED] wrote:
Pasqualino 'Titto' Assini wrote:
I am trying to write an interpreter for a little functional language but
I am finding very problematic to dynamically create a typed
representations of the language terms.
The problem is to write a function that converts between Exp and Term
t as in:
test :: Term Double
test = typecheck $ EApp (EPrim inc) (EDouble 10.0)
The specification leaves out a few important details. The typechecker can't
be a total function: what happens when typechecking this code?
EApp (EDouble 10.0) (EPrim inc)
The error has to be reported somehow, and it is important to know how.
There are basically two choices. One is to keep the above interface
test :: Term Double
test = typecheck $ EApp (EPrim inc) (EDouble 10.0)
which means using Template Haskell and means letting TH reporting
type errors (with no hope of catching them). The second choice is
`typing dynamic typing'. Which means we can't write a typechecker with
the signature Exp - Term t. Rather, we have to write
typecheck :: Exp - (forall t. Typ t - Term t - w) - Maybe w
or, equivalently, using an existential
data MostlyStatic = forall t. MostlyStatic (Typ t, Term t)
typecheck :: Exp - Maybe MostlyStatic
Although both MostlyStatic and Exp are `untyped', the latter is
`deeply' untyped, whereas the former is only untyped at the
surface. In the case of MostlyStatic, the term is built out of typed
components, and the type is erased only at the end.
These choices aren't contradictory: using TH, we can convert
MostlyStatic to the proper Haskell term. Because the term has already
been typechecked, we are guaranteed the absence of errors during such
a conversion.
For today, perhaps the implementation of the second choice will be
sufficient. This is the complete representation of a typed DSL given
in the untyped AST form. We typecheck a term. We either report a
type error, or evaluate the typed term and then report result, if can be
shown. We also show the inferred type of the result.
Examples. Let's assume the following terms (not all of them well-typed)
te1 = EApp (EPrim inc) (EDouble 10.0)
te2 = EApp (EDouble 10.0) (EPrim inc)
te3 = EApp (EApp (EPrim +)
(EApp (EPrim inc) (EDouble 10.0)))
(EApp (EPrim inc) (EDouble 20.0))
te4 = EApp (EPrim rev) te3
te5 = EApp (EPrim rev) (EApp (EPrim show) te3)
*Eval teval te1
type Double, value 11.0
*Eval teval te2
Type error: Trying to apply not-a-function: Double
*Eval teval te3
type Double, value 32.0
*Eval teval te4
Type error: incompatible type of the application: (String-String) and
Double *Eval teval te5
type String, value 0.23
The complete code follows
{-# OPTIONS -fglasgow-exts #-}
-- Typechecker to GADT
-- Implementing a typed DSL with the typed evaluator and the
-- the typechecker from untyped terms to typed ones
module Eval where
-- Untyped terms (what I get from my parser):
data Exp = EDouble Double |
EString String |
EPrim String |
EApp Exp Exp deriving (Show)
-- Typed terms:
data Term a where
Num :: Double - Term Double
Str :: String - Term String
App :: Term (a-b) - Term a - Term b
Fun :: (a-b) - Term (a-b)
-- Typed evaluator
eval :: Term a - a
eval (Num x) = x
eval (Str x) = x
eval (Fun x ) = x
eval (App e1 e2) = (eval e1) (eval e2)
--
Re: [Haskell-cafe] The Exp - Term a problem (again), how to dynamically create (polymorphic) typed terms in Haskell ??
Hello Tomasz, thank you very much for your advice. Just a quick question, why using your own Dyn rather than Data.Dynamic? Regards, titto On Thursday 04 October 2007 08:57:11 Tomasz Zielonka wrote: On 10/4/07, Pasqualino 'Titto' Assini [EMAIL PROTECTED] wrote: It does not seem to be possible to define typecheck on EApp in a generic way and is also not possible to distinguish between the different cases: You want to pattern-match on types and the easiest way to do it is to introduce a witness GADT for types, something like: data Type a where TString :: Type String TFun :: Type a - Type b - Type (a - b) ... It will be useful to write function: termType :: Term a - Type a You'll probably have to decorate Term constructors with Type's in a few places. As for the typecheck function - it has to be able to return any Term type, dynamically. Existentially quantificated data constructors will be handy here. Here's what I use: data Dyn c = forall a. Dyn (c a) withDyn :: Dyn c - (forall a. c a - b) - b withDyn (Dyn e) f = f e Your typecheck function can have type: typecheck :: Exp - Dyn Term or rather typecheck :: Exp - Maybe (Dyn Term) You define it recursively, getting Dyn Term for subexpressions, checking their types, building bigger Dyn Terms, and so on. You'll probably need some other support functions for working with Dyn and Type - at least I did. I think something similar is presented in Hinze's paper, recommended by Dominic. Best regards Tomasz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] gtk2hs in Ubuntu Gutsy
I just installed the beta release for Ubuntu Gutsy, and I noticed that gtk2hs (provided by libghc6-gtk-dev) is still at version 0.9.10.5-1ubuntu1. Worse, it's apparently not installable; when I try I get this message: libghc6-gtk-dev: Depends: ghc6 (6.6+) but 6.6.1-2ubuntu2 is to be installed Depends: libghc6-cairo-dev but it is not going to be installed Do any of you guys know why this wouldn't include a newer version? Probably just an oversight, I'm guessing. -- Chad Scherrer Time flies like an arrow; fruit flies like a banana -- Groucho Marx ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] New slogan for haskell.org
It was raised at CUFP today that while Python has: Python is a dynamic object-oriented programming language that can be used for many kinds of software development. It offers strong support for integration with other languages and tools, comes with extensive standard libraries, and can be learned in a few days. Many Python programmers report substantial productivity gains and feel the language encourages the development of higher quality, more maintainable code. With the links from the start about using Python for various purposes, along with reassuring text about licenses and so on. Note its all about how it can help you. The Haskell website has the rather strange motivational text: Haskell is a general purpose, purely functional programming language featuring static typing, higher order functions, polymorphism, type classes, and monadic effects. Haskell compilers are freely available for almost any computer. Which doesn't say why these help you. Any suggestions on a 2 or 3 sentence spiel about what's available? Here's some quick points: General purpose: applications from OS kernels to compilers to web dev to ... Strong integration with other languages: FFI, and FFI binding tools Many developer tools: debugger, profiler, code coverage, QuickCheck Extensive libraries: central library repository, central repo hosting Productivity, robustness, maintainability: purity, type system, etc Parallelism! -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Function composition
Adapting my previous class sample with these ideas, we have: class Multicompose t1 t2 t3 | t1 t2 - t3 where infixr 9 +. (+.)::t1 - t2 - t3 instance Multicompose t1 t2 t3 = Multicompose t1 (a - t2) (a - t3) where (+.) = (.).(+.) instance Multicompose (b - c) (a - b) (a - c) where (+.) = (.) The only advantage is having the compiler calculate the number of compositions. Cheers, Jorge. Stuart Cook escreveu: On 10/4/07, Dominic Steinitz [EMAIL PROTECTED] wrote: Look at the type of (.).(.).(.) Indeed, this generalizes to functions of any arity on the RHS: Prelude :t (.) (.) :: (b - c) - (a - b) - a - c Prelude :t (.).(.) (.).(.) :: (b - c) - (a - a1 - b) - a - a1 - c Prelude :t (.).(.).(.) (.).(.).(.) :: (b - c) - (a - a1 - a2 - b) - a - a1 - a2 - c Prelude :t (.).(.).(.).(.) (.).(.).(.).(.) :: (b - c) - (a - a1 - a2 - a3 - b) - a - a1 - a2 - a3 - c Of course, if you want higher-arity functions anywhere *other* than the head of your composition chain, you'll have to resort to tupling and uncurrying. Stuart ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Jorge M. Pelizzoni ICMC - Universidade de São Paulo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Space and time leaks
Ronald Guida wrote: I need some help with space and time leaks. I know of two types of space leak. The first type of leak occurs when a function uses unnecessary stack or heap space. GHCi sum [1..10^6] *** Exception: stack overflow Apparently, the default definition for sum has a space leak. I can define my own sum in terms of strict foldl ... sum' xs = foldl' (+) 0 xs ... and it doesn't overflow the stack. GHCi sum' [1..10^6] 5050 (0.27 secs, 112403416 bytes) But it fills the heap? My intuition is that foldr (+) 0 [1..10^6] is the fusion of a good producer and consumer so no heap is wasted constructing [1..10^6] but the stack is instead filled with (1+),(2+),...,(99+) unary functions, whereas foldl' (+) 0 [1..10^6] does not fill the stack with anything but does fill the heap with [1..10^6] because foldl' is no longer a good consumer? If so, it seems that the stack is smaller than the heap (or else the size of (1+) is much larger than that the element of an [Int]. Anyone know the truth of any of this? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC doesn't work
Salvatore Insalaco wrote: 2007/10/3, Andrew Coppin [EMAIL PROTECTED]: The entry point OpenThread could not be found in KERNEL32.dll. Are you using NT 4? Affirmative. Windows NT 4.0 Service Pack 6a. Probably GHC 6.6.1 dropped support for it (or maybe the binary you downloaded was compiled without the support for it), as this error message means more or less your OS is too old to run this. Is that what it means? The GHC download page claims it *should* work with NT and even ME. If that's actually not the case, somebody should alter the text... [This is why I was puzzled that it didn't work.] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Space and time leaks
Ronald Guida wrote: Now for the hard questions. 1. How do I go about detecting space and time leaks? 2. Once I find a leak, how do I fix it? 3. Are there any programming techniques I can use to avoid leaks? I'm hard time to believe I'll write something you do not know but I had similar problem and it was not hard to fix (despite some stories that it is very hard in Haskell). If you use ghc then skim over this, otherwise do not mind. Check also GHC User Guide. The options are described, well not very well but better than nothing. add 1) Here are few options I found most useful. compile with: -prof -auto-all run with: +RTS -p -hc -RTS ... to see what functions are creating leaks and which functions take the most time. Check out the app.prof and app.hp (the numbers in app.hp correspond to stack traces in app.prof (the no. column)). run with: +RTS -hr -RTS ... to see what is still keeping references to your data The stack traces corresponding to the numbers in app.hp are in app.prof. The stuff which is keeping the references are typically the routines which are creating closures and pass them around in their results instead of forcing computation and returning the processed data (which are hopefully much smaller than the input data processed). run with: +RTS -s +RTS ... and check your app.stat to see if your time problem is not actually a space problem leading to very poor GC performance. use hp2ps to look at the app.hp files add 2) Add ! to your data types at places from the result data structure to the final/leaf data structures which will keep the processed data. This is provided you do not need laziness on some places. If you do (e.g. so that you do not compute data fields which are not mostly used or when you actually require it for efficient processing (like foldr with function nonstrict in second arg)) then you need to use seq or preferably $! on the code paths which need to be strict and leave the rest of code paths lazy. Idea is that you need strictness somewhere so that your huge input data are compacted to the small output data on the fly instead at the very end when you ask for some result. add 3) There is something on the haskell wiki. Search for stack overflow and something about tail recursion and when it is a red herring. I just looked for the data with google and there is enough of them. Peter. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Is this a known problem?
UltraSPARC II, Solaris 2.10, gcc 4.0.4 (gccfss), Haskell GHC 6.6.1 binary release. Trying to compile a simple file gives me oodles of errors because ghc is generating something that makes gcc generate lots of these: sethi %hi(some register),another register For people unfamiliar with SPARC assembly code, the %hi(...) operation returns the top bits of a *literal* address, it makes absolutely no sense to give it a register. I have tried this version of gccfss with lots of C code and have been unable to make it generate this construction; it's only ghc's .hc files that do it. Running gcc by hand on the .hc file produces 8 warnings ...lib/ghc-6.6.1/include/Regs.h: ###: warning: call-clobbered register used for global register variable -DNO_GLOBAL_REG_DECLS eliminated that. Comparing the .s file produced using 'ghc -S' with the .s file produced by gcc'ing the .hc produced some illumination: .section.text,#slloc,#execinstr,#progbits .align 4 #if GHC .text .align 4 #endif s4AK_ret: save%sp,-96,%sp #if GHC sethi %hi(%l1),%i2 add %i2,%lo(%l1),%i5 ld [%i2+%lo(%l1)],%i2 ld [%i2],%l7 lduh[%l7-2],%l6 ... #else sethi %hi(MainCapability),%i5 add %i5,%lo(MainCapability),%i2 ld [%i2+8],%i5 ld [%i5],%i4 lduh[%i4-2],%i3 ... #endif What with one thing and another, I'm not really sure that it's gcc's fault. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Curry and uncurry
No, still no idea! I tried curry f where f :: (Num a) = (a, a) - a and it didn't like it. For some reason I'm finding this a little chalenging. Thanks, Paul At 17:03 03/10/2007, you wrote: On 10/3/07, PR Stanley mailto:[EMAIL PROTECTED][EMAIL PROTECTED] wrote: I didn't even know about the curry and uncurry functions. I'm not looking for the answer but some guidance would be much appreciated. Thanks, Paul You can look at the types without seeing the implementation, too. Just start up GHCI and type: :t curry or :t uncurry Justin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] gtk2hs in Ubuntu Gutsy
On Thu, Oct 04, 2007 at 09:31:56AM -0700, Chad Scherrer wrote: I just installed the beta release for Ubuntu Gutsy, and I noticed that gtk2hs (provided by libghc6-gtk-dev) is still at version 0.9.10.5-1ubuntu1. Worse, it's apparently not installable; when I try I get this message: libghc6-gtk-dev: Depends: ghc6 (6.6+) but 6.6.1-2ubuntu2 is to be installed Depends: libghc6-cairo-dev but it is not going to be installed Do any of you guys know why this wouldn't include a newer version? Probably just an oversight, I'm guessing. GHC does not have a stable binary interface, so binary libs for 6.6.0 will probably crash if linked by 6.6.1. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] reading from stdin
On Thu, Oct 04, 2007 at 05:46:09PM +0100, Axel Simon wrote:
Hi,
I'm trying to continuously output data to a file handle while reading
single characters from the user to adjust the speed at which things are
output. I'm interested to get this to work in Hugs on Windows.
I successfully used the following function ghci under Mac OS:
{{{
getUserInput :: IO (Maybe Char)
getUserInput = do
hasInput - hReady stdin
if hasInput then liftM Just (hGetChar stdin) else return Nothing
}}}
This function returns a character to me if there's one available.
If anybody could give me a hint how to get this working in Hugs under
Windows, please tell me.
Something in the 'win32' package, or maybe the FFI. MSDN will be very
handy.
P.S.: Sorry to post to [EMAIL PROTECTED], but nothing else seemed to match.
This is a thread for [EMAIL PROTECTED]
Stefan
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] New slogan for haskell.org
Wasn't this the point of the elevator speech thread a few weeks ago? Saying in 30 seconds why haskell is good and what it can do for you? On 10/4/07, Don Stewart [EMAIL PROTECTED] wrote: It was raised at CUFP today that while Python has: Python is a dynamic object-oriented programming language that can be used for many kinds of software development. It offers strong support for integration with other languages and tools, comes with extensive standard libraries, and can be learned in a few days. Many Python programmers report substantial productivity gains and feel the language encourages the development of higher quality, more maintainable code. With the links from the start about using Python for various purposes, along with reassuring text about licenses and so on. Note its all about how it can help you. The Haskell website has the rather strange motivational text: Haskell is a general purpose, purely functional programming language featuring static typing, higher order functions, polymorphism, type classes, and monadic effects. Haskell compilers are freely available for almost any computer. Which doesn't say why these help you. Any suggestions on a 2 or 3 sentence spiel about what's available? Here's some quick points: General purpose: applications from OS kernels to compilers to web dev to ... Strong integration with other languages: FFI, and FFI binding tools Many developer tools: debugger, profiler, code coverage, QuickCheck Extensive libraries: central library repository, central repo hosting Productivity, robustness, maintainability: purity, type system, etc Parallelism! -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Curry and uncurry
Here is one trick I have found useful on occasion: Prelude :t let f = undefined :: (Num a) = (a,a) - a in curry f let f = undefined :: (Num a) = (a,a) - a in curry f :: (Num a) = a - a - a undefined (also called bottom) is an element of every type, so if you just need something with a given type, you can write undefined :: YOUR_TYPE_HERE If you're having typing troubles in a complex expression, stick in annotated (i.e. the suffix :: SOME_TYPE) unknowns as placeholders, then replace them until the type breaks. Use parentheses (undefined :: TYPE) to be sure, since the binding strength of :: is not high. PR Stanley wrote: No, still no idea! I tried curry f where f :: (Num a) = (a, a) - a and it didn't like it. For some reason I'm finding this a little chalenging. Thanks, Paul At 17:03 03/10/2007, you wrote: On 10/3/07, PR Stanley mailto:[EMAIL PROTECTED][EMAIL PROTECTED] wrote: I didn't even know about the curry and uncurry functions. I'm not looking for the answer but some guidance would be much appreciated. Thanks, Paul You can look at the types without seeing the implementation, too. Just start up GHCI and type: :t curry or :t uncurry Justin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Exp - Term a problem (again), how to dynamically create (polymorphic) typed terms in Haskell ??
On Thu, Oct 04, 2007 at 05:05:23PM +0100, Pasqualino 'Titto' Assini wrote: Hello Tomasz, thank you very much for your advice. Just a quick question, why using your own Dyn rather than Data.Dynamic? Well, it's a bit different from Data.Dynamic. You have a guarantee that (Dyn Term) contains (Term t) for some t. Besides, making Term an instance of Typeable wouldn't buy us anything. You would have to define Type GADT anyway. Best regards Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] New slogan for haskell.org
On Thu, Oct 04, 2007 at 10:36:40AM -0700, Don Stewart wrote: The Haskell website has the rather strange motivational text: Haskell is a general purpose, purely functional programming language featuring static typing, higher order functions, polymorphism, type classes, and monadic effects. Haskell compilers are freely available for almost any computer. Because it's not a motivational text. Which doesn't say why these help you. Any suggestions on a 2 or 3 sentence spiel about what's available? Here's some quick points: General purpose: applications from OS kernels to compilers to web dev to ... Strong integration with other languages: FFI, and FFI binding tools Many developer tools: debugger, profiler, code coverage, QuickCheck Extensive libraries: central library repository, central repo hosting Productivity, robustness, maintainability: purity, type system, etc Parallelism! Sounds cool, but what IS haskell? I'm okay with adding motivation, but please leave the description. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] New slogan for haskell.org
Yep, its similar to the elevator pitch, but a little shorter, and mentions why as a programmer this is worth your time. I'm not sure monadic effects is terribly motivating for someone who's heard about Haskell, and just wants to get things done faster, and more reliably -- which is really what Haskell can be about. -- Don wagner.andrew: Wasn't this the point of the elevator speech thread a few weeks ago? Saying in 30 seconds why haskell is good and what it can do for you? On 10/4/07, Don Stewart [EMAIL PROTECTED] wrote: It was raised at CUFP today that while Python has: Python is a dynamic object-oriented programming language that can be used for many kinds of software development. It offers strong support for integration with other languages and tools, comes with extensive standard libraries, and can be learned in a few days. Many Python programmers report substantial productivity gains and feel the language encourages the development of higher quality, more maintainable code. With the links from the start about using Python for various purposes, along with reassuring text about licenses and so on. Note its all about how it can help you. The Haskell website has the rather strange motivational text: Haskell is a general purpose, purely functional programming language featuring static typing, higher order functions, polymorphism, type classes, and monadic effects. Haskell compilers are freely available for almost any computer. Which doesn't say why these help you. Any suggestions on a 2 or 3 sentence spiel about what's available? Here's some quick points: General purpose: applications from OS kernels to compilers to web dev to ... Strong integration with other languages: FFI, and FFI binding tools Many developer tools: debugger, profiler, code coverage, QuickCheck Extensive libraries: central library repository, central repo hosting Productivity, robustness, maintainability: purity, type system, etc Parallelism! -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] New slogan for haskell.org
On 10/4/07, Don Stewart [EMAIL PROTECTED] wrote: It was raised at CUFP today that while Python has: Python is a dynamic object-oriented programming language that can be used for many kinds of software development. It offers strong support for integration with other languages and tools, comes with extensive standard libraries, and can be learned in a few days. Many Python programmers report substantial productivity gains and feel the language encourages the development of higher quality, more maintainable code. With the links from the start about using Python for various purposes, along with reassuring text about licenses and so on. Note its all about how it can help you. The Haskell website has the rather strange motivational text: Haskell is a general purpose, purely functional programming language featuring static typing, higher order functions, polymorphism, type classes, and monadic effects. Haskell compilers are freely available for almost any computer. Which doesn't say why these help you. Any suggestions on a 2 or 3 sentence spiel about what's available? Here's some quick points: General purpose: applications from OS kernels to compilers to web dev to ... Strong integration with other languages: FFI, and FFI binding tools Many developer tools: debugger, profiler, code coverage, QuickCheck Extensive libraries: central library repository, central repo hosting Productivity, robustness, maintainability: purity, type system, etc Parallelism! Can't we embrace the power of 'and'? It's wonderful that Haskell is seeing more practical use, but we shouldn't forget the foundations, either. Maybe we should put your second description first, and *then* have a paragraph saying, and, for those who know what these are, polymorphism, monadic effects, etc.? Only describing Haskell in terms of software engineeering doesn't seem right to me. Cheers, Tim -- Tim Chevalier * catamorphism.org * Often in error, never in doubt I know / no matter what / no matter who / no matter what I do / somebody hates me / and I hate somebody too -- Reel Big Fish ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] New slogan for haskell.org
catamorphism: On 10/4/07, Don Stewart [EMAIL PROTECTED] wrote: It was raised at CUFP today that while Python has: Python is a dynamic object-oriented programming language that can be used for many kinds of software development. It offers strong support for integration with other languages and tools, comes with extensive standard libraries, and can be learned in a few days. Many Python programmers report substantial productivity gains and feel the language encourages the development of higher quality, more maintainable code. With the links from the start about using Python for various purposes, along with reassuring text about licenses and so on. Note its all about how it can help you. The Haskell website has the rather strange motivational text: Haskell is a general purpose, purely functional programming language featuring static typing, higher order functions, polymorphism, type classes, and monadic effects. Haskell compilers are freely available for almost any computer. Which doesn't say why these help you. Any suggestions on a 2 or 3 sentence spiel about what's available? Here's some quick points: General purpose: applications from OS kernels to compilers to web dev to ... Strong integration with other languages: FFI, and FFI binding tools Many developer tools: debugger, profiler, code coverage, QuickCheck Extensive libraries: central library repository, central repo hosting Productivity, robustness, maintainability: purity, type system, etc Parallelism! Can't we embrace the power of 'and'? It's wonderful that Haskell is seeing more practical use, but we shouldn't forget the foundations, either. Maybe we should put your second description first, and *then* have a paragraph saying, and, for those who know what these are, polymorphism, monadic effects, etc.? Only describing Haskell in terms of software engineeering doesn't seem right to me. Yes, I think that's the best step. Combine both why you'd use it, with what unique features enable this. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
