- Haskell-Cafe - Haskell.org

Why is this program leaking memory ?
by Ahn Ki-yung 28 May '03

28 May '03

I'm playing with the lazy abstract machine of 1997 Sestoft's paper. I implemented this with haskell using ghc 5.04.3. I lambda lifted the original input expression to prevent memory leak of "Lazy Abstarc Machine", and it works fine. I tested with the leaky program example of the Sestoft 97 paper. [kyagrd@OBIWAN transform]$ cat test.txt let ff = \n.let i=\x.x in ff i in ff ff I printed the 4 tuples (Heap, Exp, Env, Stack) each step. It goes on and on like this. [kyagrd@OBIWAN transform]$ ./main.exe < test.txt let "ff"=\"n".let "i"=\"x"."x" in "ff" "i" in "ff" "ff" let 1=\2.let 3=\4.4 in 1 3 in 1 1 let -1=\2.-1 -3 -3=\4.4 in -1 -1 let -1=\2.-1 -3 -3=\4.4 in -1 -1 let 0=\0.1 2 0=\0.0 in 0 0 ([],let 0=\0.1 2 0=\0.0 in 0 0,[],[]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],0 0,[2,1],[]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],0,[2,1],[2]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],\0.1 2,[2,1],[2]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1 2,[2,2,1],[]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1,[2,2,1],[1]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],\0.1 2,[2,1],[1]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1 2,[1,2,1],[]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1,[1,2,1],[1]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],\0.1 2,[2,1],[1]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1 2,[1,2,1],[]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1,[1,2,1],[1]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],\0.1 2,[2,1],[1]) ([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1 2,[1,2,1],[]) ... But Strangely the Haskell heap memory leaks if I omit printing every step but only print the result. [kyagrd@OBIWAN transform]$ ./main.exe < test.txt let "ff"=\"n".let "i"=\"x"."x" in "ff" "i" in "ff" "ff" let 1=\2.let 3=\4.4 in 1 3 in 1 1 let -1=\2.-1 -3 -3=\4.4 in -1 -1 let -1=\2.-1 -3 -3=\4.4 in -1 -1 let 0=\0.1 2 0=\0.0 in 0 0 c:\MyDoc\iFolder\kyagrd\LAZY\transform\main.exe: fatal error: RTS exhausted max heap size (268435456 bytes) I attach my source code except for the parser and lexer stuff. I switched between two main' and main fucntion. Why, in the Main module, "printNreduce" do not leak but while "printeval" leaks ? Can't understand this behavior. module Main where import Syntax import Parser import Lazyeval import MonadST printeval q = if q'==q then print q' else printeval q' where q' = reduce q printNreduce q = if q'==q then print q' else (print q >> printNreduce q') where q' = reduce q -- print every step does not leak main = do s <- getContents let e = parser s e' <- printNpreprocess e printNreduce ([],e',[],[]) -- print only result leak !! main' = do s <- getContents let e = parser s e' <- printNpreprocess e printeval ([],e',[],[]) printNpreprocess e = print e >> print e1 >> print e2 >> print e3 >> print e' >> return e' where ((ns,[]),e1) = evalST ([1..],[]) (uniqueify e) e2 = lambdalift negate e1 (ns3,e3) = evalST ns (normalize e2) e' = bruijnize e3 {- Syntax.hs preprocessing of lazy language for evaluation Ahn Ki-yung -} module Syntax where import MonadST import List data Lambda id = Var id | App (Lambda id) (Lambda id) | Lam id (Lambda id) | Let [(id,Lambda id)] (Lambda id) -- deriving (Eq, Ord) deriving (Eq, Ord, Read) instance Show a => Show (Lambda a) where show (Var s) = show s show (Lam s e) = '\\':show s ++ '.':show e show (App e e') = showParenExpr e ++ ' ' : showParenExpr e' where showParenExpr e@(Var s) = show e showParenExpr e = '(':show e++")" show (Let h e) = "let" ++ concat [' ':show s++'=':show e|(s,e)<-h] ++ " in " ++ show e instance Functor Lambda where fmap f (Var x) = Var (f x) fmap f (App e e') = App (fmap f e) (fmap f e') fmap f (Lam x e) = Lam (f x) (fmap f e) fmap f (Let ds e) = Let [(f x,fmap f e)|(x,e)<-ds] (fmap f e) transform (getId,putId,popId) = trans where newId x = putId x >> getId x trans (Var x) = do { x'<-getId x; return (Var x') } trans (App e e1) = do { e'<-trans e; e1'<-trans e1; return (App e' e1') } trans (Lam x e) = do { x'<-newId x; e'<-trans e; popId x; return (Lam x' e') } trans (Let ds e) = do let (xs,es) = unzip ds xs'<-mapM newId xs es'<-mapM trans es let ds' = zip xs' es' e'<-trans e mapM popId xs return (Let ds' e') uniqueify :: (Eq a, Eq b) => Lambda a -> StateTrans ([b],[(a,b)]) (Lambda b) uniqueify = transform (getId,putId,popId) where getId x = do (_,l) <- readST let Just (_,n) = find ((x==).fst) l return n putId x = do (n:ns,l) <- readST writeST (ns,(x,n):l) popId x = do (ns,l) <- readST writeST (ns,deleteBy (\p-> \q->fst p==fst q) (x,head ns) l) normalize :: Lambda a -> StateTrans [a] (Lambda a) normalize = normExpr where newvar = do (x:xs) <- readST writeST xs return x normExpr (Var x) = return (Var x) normExpr (Lam x e) = do e' <- normExpr e return (Lam x e') normExpr (App e (Var x)) = do e' <- normExpr e return (App e' (Var x)) normExpr (App e1 e2) = do x <- newvar e1' <- normExpr e1 e2' <- normExpr e2 return (Let [(x,e2')] (App e1' (Var x))) normExpr (Let ds e) = do let (vs,es) = unzip ds es' <- mapM normExpr es let ds' = zip vs es' e' <- normExpr e return (Let ds' e') (f,g)@@(x,y) = (f x, g y) -- assumes uniquified normalized e lambdalift topv e = Let ds (subsfree [] topv d' e') where d' = delcombs [] d ds = [ (topv x, foldr Lam (subsfree fv topv d' e) fv) | (x,fv,e)<-d' ] (d,fv,e') = llift e delcombs combs d = if combs/=combs' then delcombs combs' [(x,fv\\combs',e) | (x,fv,e)<-d] else d where combs' = [x | (x,[],_)<-d] -- assumes uniquified and no lets -- done llift subsfree bv topv d e = subs e where var' = Var . topv subs (Var x) = case find (\(y,_,_)->x==y && not (elem x bv)) d of Just (_,fv,_) -> foldl App (var' x) (map var' fv) _ -> Var x subs (App e e') = App (subs e) (subs e') subs (Lam x e) = Lam x (subs e) -- assumes uniquified llift (Var x) = ([], [x], Var x) llift (App e e') = (d1++d2, union fv1 fv2, App e1 e2) where (d1,fv1,e1) = llift e (d2,fv2,e2) = llift e' llift (Lam x e) = (d, fv\\[x], Lam x e') where (d, fv, e') = llift e llift (Let ds e) = (dd++d', fv, e') where (d, fv, e') = llift e xds = map ((id,llift)@@) ds dd = [ (x, fv\\[x], e) | (x,(d,fv,e))<-xds ] d' = foldr (++) d [d | (_,(d,_,_))<-xds] bruijnize e = bruijn [] e elemIndex' x xs = (\(Just i)->i) $ elemIndex x xs bruijn xs (Var x) = Var (elemIndex' x xs) bruijn xs (Lam x e) = Lam 0 (bruijn (x:xs) e) bruijn xs (App e e') = App (bruijn xs e) (bruijn xs e') bruijn xs (Let ds e) = Let [(0,bruijn xs' e) | e<-es] (bruijn xs' e) where (vs,es) = unzip ds xs' = vs ++ xs module Lazyeval where import Syntax import List data StackElem = Update Int | Point Int deriving Eq instance Show StackElem where show (Update i) = '#':show i show (Point i) = show i getHeap p = (\(Just x)->snd x) . find ((p==).fst) setHeap t@(p,e) = insertBy (mapF2 fst $ flip compare) t . deleteBy (mapF2 fst (==)) t where mapF2 g f2 x y = f2 (g x) (g y) reduce (h,App e (Var i),env,s) = (h,e,env,Point(env!!i):s) reduce (h,Lam _ e,env,Point p:s) = (h,e,p:env,s) reduce (h,Var i,env,s) = (h,e',env',s') where s' = case e' of Lam _ _ ->s; _->Update p:s (e',env') = getHeap p h p = env!!i reduce (h,Lam x e,env,Update p:s) = (setHeap (p,(Lam x e,env)) h,Lam x e,env,s) reduce (h,Let ds e,env,s) = (h',e,env',s) where es = snd (unzip ds) h' = newhs ++ h env' = newps ++ env newhs = zip newps [(e,env')|e<-es] newps = take n [m+n,m+n-1..] m = if null h then 0 else (head . fst . unzip) h n = length es reduce q = q fix f x = if x'==x then x else fix f x' where x' = f x eval = fix reduce module MonadST (readST, writeST, applyST, evalST, valueST, stateST, StateTrans) where data StateTrans s a = ST { st :: s -> (s,a) } instance Monad (StateTrans a) where return x = ST (\s -> (s, x)) m >>= f = ST (\s -> let (s',x) = st m s in st (f x) s') readST = ST (\s -> (s, s)) writeST s' = ST (\s -> (s', ())) applyST f = ST (\s -> (f s, ())) evalST s m = st m s valueST s = snd . evalST s stateST s = fst . evalST s

1 0

RE: Question about Haskell lexer and parser.
by Simon Marlow 28 May '03

28 May '03

> Question is really about layout rules. > If the first lexeme of a module is not a "module" keyword, we insert > {n}, where n is the indentation of first lexeme. Then we apply > function L to the list of lexemes and stack of layouts: > > L ({n}:lexemes) [] > > One of first case definitions of L covers this situation: > L ({n}:ts) [] > | n>0 = {:L ts [n] -- n>0 means that layout isn't explicit. > It's obvious that after our first {n} comes usual lexeme, like Var. > This situaiton is covered in the following L rule: > > L (t:ts) (m:ms) > | m /= 0 = }:L (t:ts) ms -- Haskell Report says that we here > -- should recognize parsing errors > -- but how we can do that in lexer? This rule only applies if there is a parse error on the next token (t). The report explains what this means in "Note 5". It does mean that layout processing can't be done entirely in the lexer, the parser has to be involved too. This is what makes parsing layout in Haskell hard. Take a look at some of the existing Haskell parsers to see how it can be done: there are two in GHC's source tree (one in GHC itself, another in libraries/haskell-src). Hugs's parser is written in C but uses similar techniques. nhc98's parser uses parsing combinators IIRC. Cheers, Simon

2 1

Re: Haskell Employers
by David Barton 27 May '03

27 May '03

Ashley Yakeley writes: > So are there companies that pay people to write in Haskell, or indeed in > any functional language? I do know of Galois Connections in Oregon; are > there others? > > As a Haskell developer looking for a job, this would certainly be useful > information... I can't say we are using Haskell (well, we have for a small thing or two, but not enough to justify hiring someone for it). However, I think that the use of higher level languages in general are increasing. We'll be looking for someone soon to develop, not only in C++ or Java, but also in a new systems design language called Rosetta (http://www.sldl.org) I predict that the use of such languages will increase in the next few years --- slowly at first, then faster --- particularly in the systems and hardware design arenas, even more than in software. Dave Barton EDAptive Computing

1 0

Happy
by Pablo Dejuan 27 May '03

27 May '03

Hi. I've just started using haskell and I've some problems with the generated file of happy, the example.hs. When I try to load it, It complains that isAlpha, isDigit and isSpace are variables not in scope. This means I should import a particular module to do so? TIA

2 1

failure notice
by MAILER-DAEMON＠foshan.net 27 May '03

27 May '03

Hi. This is the qmail-send program at foshan.net. I'm afraid I wasn't able to deliver your message to the following addresses. This is a permanent error; I've given up. Sorry it didn't work out. <hauj(a)foshan.net>: Sorry, no mailbox here by that name. vpopmail (#5.1.1) --- Below this line is a copy of the message. Return-Path: <haskell-cafe(a)haskell.org> Received: (ctmail 25865 invoked from network); 27 May 2003 09:57:10 -0000 Received: from unknown (HELO hauj) (218.13.218.251) by 0 with SMTP; 27 May 2003 09:57:10 -0000 From: "haskell-cafe" <haskell-cafe(a)haskell.org> Subject: =?GB2312?B?VE+jumhhdWpAZm9zaGFuLm5ldLvh1LHK1SE=?= 17:52:54:7 To: hauj(a)foshan.net Content-Type: text/html;charset="GB2312" Sender: haskell-cafe <haskell-cafe(a)haskell.org> Reply-To: wangxiao1999(a)163.com Date: Tue, 27 May 2003 17:52:54 +0800 X-Priority: 4 X-Mailer: Microsoft Outlook Express 5.50.4133.2400 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META http-equiv=Content-Type content="text/html; charset=gb2312"> <META content="MSHTML 6.00.2462.0" name=GENERATOR></HEAD> <BODY>     ÄúºÃ£¡     CCTV-2£º·ÇµäŽÙœø¡¢ÉýÎÂÐÅÏ¢»¯£¬µç×ÓÉÌÎñÐÎÊÆŽóºÃ£¬ÄúžÐÊÜÏ²ÔÃÁËÂð£¿     ÔÚÖøÃûÉÌÃ³ÍøÕŸÖÐÇáËÉÑ°ÕÒÂò·œÓëÂô·œµÄÁªÏµ·œÊœ£š¹«ËŸ¡¢µç»°¡¢Ž«Õæ¡¢ÁªÏµÈË¡¢ÓÊŒþ¡¢µØÖ·µÈ£©£¬²¢ÓëÎŽÀŽ¿Í»§È¡µÃÁªÏµ£¬ÊÇ×îÓÐÐ§¡¢×î¿ìœÝ¡¢×îµÍ³É±ŸµÄÓªÏú·œ·š¡£     ÉÌÖÇµç×ÓÉÌÎñÈíŒþŸÍÄÜ°ïÄúÊµÏÖÍêÃÀ£¡Íš¹ý»¥ÁªÍøÀŽ»ñÈ¡ÒµÎñ¶©µ¥µÄµç×ÓÉÌÎñÓÅÐãÈíŒþ£¬ÄÜÊ¹ÄúÔ¶Àë·ÇµäÀ§ÈÅ£¬Íš¹ý»¥ÁªÍøÀŽÊµÏÖÓ¯Àû£¡     Ö»ÐèŒž·ÖÖÓ£¬ÉÌÖÇµç×ÓÉÌÎñÈíŒþ¿Éœ«ÄúµÄ²úÆ·»òÏîÄ¿ÐÅÏ¢ÔÚ1554ŒÒ¹©ÇóÐÅÏ¢ÆœÌš·¢²Œ¡¢2147ŒÒÍøÕŸÖÐËÑË÷ÄúÎŽÀŽµÄ¿Í»§¡£ÒÔ×îµÍµÄ³É±Ÿ¡¢ÓÃ×î¹ãµÄ×ÊÔŽ¡¢ŽŽ×îºÃµÄÐ§Òæ.ÈíŒþ×¢²áºÅ£ºÉîÛÚDGY-2002-0321     »¶ÓÏÂÔØÈíŒþÊÔÓÃ£¬Ãâ·ÑË÷È¡ÓÃ»§ÃûÓëÃÜÂë.³ÏÕ÷ºÏ×÷»ï°é¡£     ÇëÓÊŒþ»òÔÚÏßQQ:39398668 3203821 33669329  ÍõÐ¡œã Â¬ÏÈÉú</BODY></HTML> ÉÌÖÇµç×ÓÉÌÎñÈíŒþÉÌÎñ×ÉÑ¯

1 0

I am just starting out
by Andy Schmidt 27 May '03

27 May '03

Hi, my name is Andy Schmidt and I stumbled across this website as I started my quest for the best programming language. I am only in college and I am trying to learn as many languages as I can. I hope haskell will be the one I stick with. -Andy _________________________________________________________________ Help STOP SPAM with the new MSN 8 and get 2 months FREE* http://join.msn.com/?page=features/junkmail

11 16

Re:For All Educational Personnel
by epcinquire＠epcparts.com 26 May '03

26 May '03

For all Educational Personnel Re: 50% Off Electronic Parts Company is offering a limited supply of top of the line brand new Laptop and Desktop computers to all Educational personnel at 50% off MSRP. All Computers are brand-new packed in their original boxes and come with a full manufacturer's warranty plus ePC's 100% satisfaction guarantee. These computers are fully equipped with the latest 2003 technology to make these the best performing computers money can buy. ePC is offering these computers with the latest Intel technology at a remarkable price to those who call: 1.888.399.3744 by Wednesday May 28th, 2003 by 6 p.m. All desktops come with minimum:(Upgrades are available) * 1.3 Intel Processor * 128 MB SDRAM * 52x CD-ROM Drive * 20 GB UDMA Hard drive * Intel 3D Graphics * Sound Blaster 64v Sound * Floppy disk Drive * Keyboard, Speakers, Mouse * Motorola 56.6 V90 Fax Modem * Windows XP * Internet ready * Award winning tech support and customer service Retail..........$798.00 Your Cost............. $399.00 All laptops come with minimum:(Upgrades are available) * 1.0 GigaPro CPU, 512KB L2 cache * 128 MB SDRAM * CD-ROM * 10 GB UDMA Hard drive * Sound Card and Video Card * 14.1 XGA TFT Liquid Screen * Soft touch keyboard * 56.6 V90 Fax Modem * Windows XP * Internet ready * Bundled PC essentials software package * Award winning tech support and customer service Retail..........$1394.00 Your Cost............. $697.00 How to qualify 1. All computers will be available on a first-come first-served basis. 2. You must call 1.888.399.3744 by 6 P.M. Wednesday May 28th. and we will hold the computers you request on will call. 3. You are not obligated in any way 100% Satisfaction Guarantee. To take advantage of this offer please call 1.888.399.3744 To order online visit http://www.epcparts.com use promo code ENS4592

1 0

re: re: 你好
by 高明 26 May '03

26 May '03

1 0

Italian-crafted Rolex - only $65 - $140!! Free SHIPPING ! !
by james＠hello.com 26 May '03

26 May '03

1 0

monomorphism restriction
by John Meacham 24 May '03

24 May '03

Just a random thought, What would be the effect of lifting the monomorphism restriction under the condition that assignments which would normally be subject to the restriction must be memoized on the class constraint parameter by the implementation? it seems that this would solve the problems which inspired the monomorphism restriction since the value can be shared among all instantiations when the type is the same. I am posting this to haskell-cafe because it might just be half-baked. John -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john(a)foo.net ---------------------------------------------------------------------------

1 0