- Haskell-Cafe - Haskell.org

Re: [Haskell] reading from stdin
by Reinier Lamers 08 Oct '07

08 Oct '07

Axel Simon wrote: >a) is the behaviour I want, but unfortunately for platform d) >b) must be due to ghci and Hugs having different opinions on whether >stdin should be line buffered or unbuffered >c) this is weird >d) this is broken > You can probably unify the behaviors of platforms a, b and c by calling hSetBuffering on stdin to turn off buffering. Reinier

2 1

Typechecker to GADT: the full implementation of a typed DSL
by oleg＠pobox.com 08 Oct '07

08 Oct '07

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 (TString, Str x) typecheck env (EPrim x) = maybe err Right $ lookup x env where err = Left $ "unknown primitive " ++ x typecheck env (EApp e1 e2) = case (typecheck env e1, typecheck env e2) of (Right e1, Right e2) -> typechecka e1 e2 (Left err, Right _) -> Left err (Right _, Left err) -> Left err (Left e1, Left e2) -> Left (e1 ++ " and " ++ e2) -- typecheck the application typechecka (MostlyStatic ((TFun ta tb),e1)) (MostlyStatic (t2,e2)) = typechecka' (eqt ta t2) tb e1 e2 where typechecka' :: Maybe (EQ ta t2) -> Typ tb -> Term (ta->tb) -> Term t2 -> Either String MostlyStatic typechecka' (Just Refl) tb e1 e2 = Right $ MostlyStatic (tb,App e1 e2) typechecka' _ tb e1 e2 = Left $ unwords ["incompatible type of the application:", show (TFun ta tb), "and", show t2] typechecka (MostlyStatic (t1,e1)) _ = Left $ "Trying to apply not-a-function: " ++ show t1 -- tests 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) -- typecheck-and-eval teval :: Exp -> String teval exp = either (terror) (ev) (typecheck env0 exp) where terror err = "Type error: " ++ err ev (MostlyStatic (t,e)) = "type " ++ show t ++ ", value " ++ (tryshow (eqt t TString) (eqt t TDouble) (eval e)) tryshow :: Maybe (EQ t String) -> Maybe (EQ t Double) -> t -> String tryshow (Just Refl) _ t = t tryshow _ (Just Refl) t = show t tryshow _ _ _ = "<fun>"

4 6

SOE/GLFW compilation problems
by Joel Stanley 07 Oct '07

07 Oct '07

Hi folks, I've recently been able to get the SOE/GLFW code up and running from http://haskell.org/soe/software1.htm and things are working well under GHCi under Mac OS X. However, when attempting to compile a simple graphics script using ghc, I'm getting some unexpected link errors: $ ghc -o mygfx mygfx.hs -iSOE/src compilation IS NOT required /usr/bin/ld: Undefined symbols: _SOE_Blue_closure _SOE_Red_closure _SOE_closeWindow_closure _SOE_drawInWindow_closure _SOE_ellipse_closure _SOE_getKey_closure _SOE_openWindow_closure _SOE_polyline_closure _SOE_runGraphics_closure _SOE_withColor_closure collect2: ld returned 1 exit status I'm quite new to Haskell, so I'm not sure if there was something special I had to do in order to get the code for the closures generated by ghc. Any ideas? Thanks in advance. Joel

2 1

Extract source code from literate Haskell (LHS) files
by Peter Verswyvelen 06 Oct '07

06 Oct '07

This is of course very easy to do manually, but does a command line tool exist for extracting source code from literate Haskell files? Thanks, Peter

7 6

GLFW for WinHugs
by Peter Verswyvelen 06 Oct '07

06 Oct '07

The latest version of SOE comes with a wrapper for a nice GLFW library. This library comes with a demo of a 3D bouncing "Amiga" ball so it must be the best library in the world ;-) ;-) Since I'm letting my students play with WinHugs, I would prefer to have a WinHugs compatible version of that library. I tried to convert it, but I got stuck when ffihugs complained about not finding RTS.h, which seems to be a GHC-only include file. Would it be possible to convert this library to WinHugs? I guess similar work has been done for other libraries, so any hints are welcome. Thanks, Peter

2 1

Puzzled
by Peter Verswyvelen 06 Oct '07

06 Oct '07

The following code, when compiled with GHC 6.6.1 --make -O gives a stack overflow when I enter 1000000 as a command line argument: (please don't look at the efficiency of the code, it can of course be improved a lot both in time performance and numeric precision...) import System leibnizPI :: Integer -> Double leibnizPI n = sum (map leibnizTerm [0..n]) where leibnizTerm n = let i = fromIntegral n in 4 * (((-1) ** i) / (2*i+1)) main = do args <- getArgs let n = read (head args) print (leibnizPI n) However, if I replace main = print (leibnizPI 1000000) is does not stack overflow. Now, if I leave the original main, but replace sum in leibnizPI by mysum xs = aux 0 xs where aux s (x:xs) = aux (s+x) xs aux s [] = s then I don't get a stack overflow. However, I do get a stack overflow when I compile it without -O, in all cases. This puzzles me. I don't see any non-tail calls in my code... I guess it has to do with strictness? http://www.haskell.org/haskellwiki/Performance/Strictness Why isn't it possible to annotate strictness on the type signature in Haskell as in Clean? Is this on the TODO list? Many thanks, Peter

5 5

more basic articles on functional programming using haskell
by Vikrant 06 Oct '07

06 Oct '07

part I -> http://www.ias.ac.in/resonance/August2007/p27-48.pdf part II -> http://www.ias.ac.in/resonance/September2007/p40-63.pdf == Vikrant

1 0

Hackathon underway
by Don Stewart 05 Oct '07

05 Oct '07

Just to let everyone know , the Haskell Hackathon is underway (the 2nd this year), in Freiburg, Germany, and library and infrastructure code is being worked on furiously -- Cabal and related tools in particular. You can follow all the action from planet.haskell.org, and from the hackathon site, including photos. http://www.haskell.org/haskellwiki/Hac_2007_II#Photos_.2F_blogs -- Don

1 0

Re: [Haskell-cafe] Curry and uncurry
by PR Stanley 05 Oct '07

05 Oct '07

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:prstanley@ntlworld.com>prstanley(a)ntlworld.com> 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

3 2

Space and time leaks
by Ronald Guida 05 Oct '07

05 Oct '07

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] 500000500000 (0.27 secs, 112403416 bytes) GHCi> sum' [1..10^7] 50000005000000 (2.73 secs, 1161223384 bytes) GHCi> sum' [1..10^8] 5000000050000000 (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. The other type of space leak I know of is when I have a chunk of data in memory that I no longer need, such that the data is still being referenced somewhere. Since, in theory, I might still access the data, the garbage collector can't reclaim the memory. I'm not sure how to construct an example though. Regarding time leaks, I only know of one kind of leak. If I have a calculation that accumulates data over time, and I don't ask for any results until the end, then, due to laziness, that calculation might accumulate a chain of unevaluated thunks. When I get the the end and "demand" the final result, I have to wait for it while the RTS evaluates a long chain of thunks. The chain of unevaluated thunks is a space leak. The time leak occurs because the capture process and the accumulate process are supposed to be interleaved, such that I perform some computations after I capture each piece of data. If I have to wait around at the end, then it means the capture process and the accumulate process happened in sequence. As far as I know, every time leak has a companion space leak; it's not possible to create a time leak without a space leak to go with it. Is this really true? 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? -- Ron

5 4