- Haskell - Haskell.org

Infinite, open, statically constrained HLists
by oleg＠pobox.com 01 Nov '06

01 Nov '06

We show a presentation of heterogeneous sequences that admits infinite sequences and permits post-hoc addition of new elements, even to an already infinite sequence. We can also assert static constraints, e.g., the sequence must be made of non-decreasing Peano numerals. Our sequences permit all the common operations such as `head', `tail', `cons', `map', `take' and `fold'. It is a type error to attempt to take `head' of an empty sequence. Any finite sequence is inter-convertible with the HCons-based HList. The full code is available at http://darcs.haskell.org/HList/CHList.hs The presentation is inspired by the problem posed by Greg Buchholz on the following thread: http://www.haskell.org/pipermail/haskell-cafe/2006-October/018948.html http://www.haskell.org/pipermail/haskell-cafe/2006-October/019030.html He observed how easy it is to define _some_ (potentially) infinite heterogeneous data structures. For example, data SeqI a = ConsI a (SeqI (S a)) | NilI defines the type of a sub-sequence of the sequence of natural Peano numerals. We can construct finite seqi1 = ConsI Z (ConsI (S Z) NilI) and even infinite sequences seqi_inf :: n -> SeqI n seqi_inf n = ConsI n (seqi_inf (S n)) but not seqi2 = ConsI Z (ConsI Z NilI) The latter ill-formed sequence is ill-typed. However, it is difficult to generalize these constructions, for example, to the sequences of Fibonacci Peano numerals or to the sequences of non-decreasing Peano numerals. The HList presentation, with familiar "HCons a b" and "HNil" types, makes it straightforward to define sequences with arbitrary constraints on the adjacent elements. The structure of such HList values is reflected in their types, and so we can statically constrain them. Alas, the type of an HList has as many HCons type constructors as there are HCons data constructors. That seems to rule out infinite sequences. There is a trivial way out of this predicament, via a different presentation. A sequence is a partial function from a range of natural numbers. In other words, a sequence is a mapping from a Natural number to {HNothing, HJust a}. We consider the HNothing element with the smallest index to be the end of the sequence. This obvious idea leads to the straightforward implementation: > class Nat n => CHList l n r | l n -> r where > chel :: l -> n -> r > chel = undefined > > -- Default `cut-off' instance > instance (Nat n, TypeCast r HNothing) => CHList l n r where > data HNothing = HNothing > newtype HJust x = HJust x > fromHJust (HJust x) = x -- this is the total function! The class 'CHList l n r' establishes the n-th element of the sequence named 'l' to be 'r'. The empty sequence is defined then by the single declaration: > data LEmpty = LEmpty Here is a bit more elaborate sequence, of two elements. Both are Ints. Homogeneous sequences are just a subset of heterogenous ones. > data L1 = L1 > instance CHList L1 Z (HJust Int) where > chel _ _ = HJust 0 > instance CHList L1 (S Z) (HJust Int) where > chel _ _ = HJust 1 We can convert such sequences to the regular HList; this is quite handy for showing them. For example, > test1 = show $ chl_to_hl L1 yields "HCons 0 (HCons 1 HNil)" Not surprisingly, we can implement all of the common List API, for example, > cl_head l = fromHJust (chel l Z) It will be a type error attempting to apply cl_head to an empty sequence. We can define tail > newtype CLTail l = CLTail l > instance (Nat n, CHList l (S n) r) => CHList (CLTail l) n r where > chel (CLTail l) n = chel l (S n) > > -- ensure the list to take the tail of is non-empty > cl_tail :: CHList l Z (HJust e) => l -> CLTail l > cl_tail l = CLTail l > > test_h3 = cl_head (cl_tail L1) -- 1 and cons > data CLCons a l = CLCons a l > cl_cons = CLCons > > instance CHList (CLCons a l) Z (HJust a) where > chel (CLCons x _ ) _ = HJust x > > instance (Nat n, CHList l n r) => CHList (CLCons a l) (S n) r where > chel (CLCons _ l) (S n) = chel l n after which we can introduce and extend our sequences in the `normal' way: > test_c1 = cl_head (cl_tail (cl_cons ((-2)::Int) (cl_cons ((-1)::Int) L1))) > test_c2 = cl_head (cl_tail (cl_cons () (cl_cons True LEmpty))) > test_c3 = show $ chl_to_hl $ cl_cons () L1 Defining other functions like `take', `map' and `fold' is straightforward and elided. The latter require the generalized `Apply' class defined in the HList library. We can write, for example, > test_m1 = cl_map (succ :: Int->Int) L1 > test_m2 = show $ chl_to_hl test_m1 because regular functions are already instances of the Apply class and so apply-able. It is worth noting a close resemblance between test_m1 above and > test_m1' = map (succ :: Int->Int) l1 > where l1 = [0,1] The difference seems to be in the case of the identifier: `l1' vs `L1'. Indeed, both l1 and L1 _denote_ certain values. The rules of looking up the value given the name are implicit in the case of l1 and explicit (and defined by us) in the case of L1. The type-checking is more explicit in the latter case too -- that's why we are able to assert more constraints, as we shall see soon. It goes without saying that our sequences can as well be infinite: > data LNats = LNats -- lists of successive numerals > instance Nat n => CHList LNats n (HJust n) where > chel _ n = HJust n which defines the infinite list of Peano numerals. That is quite akin to "seqi_inf Z", described in the beginning of this message. Now, however, we can introduce other infinite sequences, e.g., by mapping arbitrary function over LNats. We can also define sequences by recursion, e.g., LFibs. Perhaps more interesting is the fact that our lists are open, even when they are extensible. For example, if we define only > data LCyc = LCyc > instance (Nat n, CHList LCyc n r) => CHList LCyc (S (S n)) r where > chel l (S (S n)) = chel l n then > test_cyc = show $ chl_to_hl $ cl_take five LCyc yields "HNil". If we later add another instance > instance CHList LCyc Z (HJust ()) where chel _ _ = HJust () the same test_cyc will give "HCons () HNil". The addition the third instance > instance CHList LCyc (S Z) (HJust Bool) where chel _ _ = HJust True makes our list infinite. test_cyc now gives "HCons () (HCons True (HCons () (HCons True (HCons () HNil))))" We may still add instances, for example > instance CHList LCyc (S (S Z)) (HJust Bool) where chel _ _ = HJust False causes test_cyc to return "HCons () (HCons True (HCons False (HCons True (HCons False HNil))))" Finally, we show constrained lists. A constraint is a binary predicate; it is apply-ed to two consecutive elements of the sequence, and must return HTrue. For simplicity, we introduce the following non-generic class of constrained lists, whose elements must be non-decreasing numerals: > data CK l = CK l > class (Nat n, Apply (CK l) (n,r) HTrue) => C1 l n r | l n -> r where > chel1 :: l -> n -> r; chel1 = undefined > instance (Nat n, TypeCast r HNothing, Apply (CK l) (n, r) HTrue) => C1 l n r > > instance Apply (CK l) (Z,r) HTrue > instance Apply (CK l) (S n,HNothing) HTrue > instance (C1 l n (HJust ep), Apply PLEQ (ep,e) r) > => Apply (CK l) (S n,HJust e) r The constraint is specified as a class constraint; therefore, all instances of C1 must obey it. All instances of C1 are CHLists, after we say > newtype C1toCL cl = C1toCL cl > instance C1 cl n r => CHList (C1toCL cl) n r where > chel (C1toCL l) n = chel1 l n We introduce > data LC1 = LC1 > instance C1 LC1 Z (HJust Z) > instance C1 LC1 (S Z) (HJust Z) > instance C1 LC1 (S (S Z)) (HJust (S (S (S Z)))) > test_cl1 = show $ chl_to_hl $ C1toCL LC1 but we cannot add the instance instance C1 LC1 (S (S (S Z))) (HJust Z) because it fails the non-decreasing constraint. The constrained list may be infinite: > data LC2 = LC2 > instance C1 LC2 Z (HJust Z) > -- this constraint suggested by the typechecker > instance (Apply PLEQ (r, S (S r)) HTrue, > C1 LC2 n (HJust r)) > => C1 LC2 (S n) (HJust (S (S r))) > > test_cl2 = show $ chl_to_hl $ cl_take five $ C1toCL LC2 We check the constraint by applying the predicate to the current and the previous element of the sequence (if it exists). Even in case of the infinite sequence, the prefix is finite, so our constraint is effectively verifiable.

2 2

The Monad.Reader - Call for Copy
by Wouter Swierstra 31 Oct '06

31 Oct '06

Call for Copy The Monad.Reader - Issue 6 I would like to welcome articles for the next issue of The Monad.Reader. * The Monad.Reader * There are a large number of conferences and journals that accept research papers related to Haskell; unfortunately, the platform for non-academic publications is far less developed. This is where The Monad.Reader fits in. I believe that there are lots of people on these mailing lists that have plenty of ideas that might not be suitable for the the Haskell Workshop, for instance, but are nonetheless worth writing about. Sometimes such ideas end up as posts on a Haskell mailing list; sometimes they get posted on personal blogs; sometimes they disappear altogether. A lot of e-mails to these mailing lists deserve a more lasting place. Rob Dockins's recent proof that Haskell's class system is Turing complete is a case in point. The Monad.Reader would be the perfect place to publish such insights. As The Monad.Reader's editor, Shae Erisson, has been terribly busy lately, I've decided to help out. I would like to propose the following format: * Frequency: Issues should appear quarterly. The previous goal of one issue every month was just too ambitious. * Format: I propose to move from wiki-publishing to LaTeX. Andres Loeh has been kind enough to provide us with a suitable LaTeX class. The final pdf will appear on the Haskell-wiki with links to wiki- pages for follow-up discussions. I realize this is a controversial point. At the moment, though, I would like to try out LaTeX and believe that any progress regarding The Monad.Reader is good. * Reviews: Every article should be reviewed. I'd like to keep The Monad.Reader as accessible to potential authors as possible, while trying to guarantee a certain basic quality. I think that we should strive to accept every serious submission, but subject them to a review process and aspire to the best possible end result. * Content: I'd be happy if we can get approximately two longer length articles in every issue, accompanied by a few shorter columns, reviews, puzzles, or diversions. As far as I'm concerned, just about anything goes as long as it is somehow related to Haskell or functional programming in general. Tutorials on Haskell related tools are more than welcome! * License: The entire magazine should be published under a Creative Commons Attribution 2.5 License. This makes it much easier to publish, distribute, teach, and share the Reader. This license allows anyone to use the work in any way they seem fit as long as credit is given to the original author. I'd be happy to discuss any of these points further on the Haskell- cafe list. * Submission Details * If you've made it this far down, you must be considering submitting something! By all means, get in touch with me if you intend to submit something -- the sooner you let me know what you're up to, the better. Please submit articles for the next issue by e-mail (wss at cs.nott.ac.uk) to me before **January 19th, 2007** . Articles should be written according to the guidelines available from http://www.haskell.org/haskellwiki/TheMonadReader Please submit your article PDF format. After the reviews, I may ask you to make your sources available in order to format the entire magazine uniformly. If you would like to submit an article, but have trouble with LaTeX please let me know and we'll sort something out. Looking forward to your submission, Wouter Swierstra This message has been checked for viruses but the contents of an attachment may still contain software viruses, which could damage your computer system: you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.

1 0

Haskell Weekly News: October 31, 2006
by dons＠cse.unsw.edu.au 30 Oct '06

30 Oct '06

--------------------------------------------------------------------------- Haskell Weekly News http://haskell.org/haskellwiki/HWN Issue 47 - October 31, 2006 --------------------------------------------------------------------------- Welcome to issue 47 of HWN, a weekly newsletter covering developments in the Haskell community. This week we see a number of community documentation and maintenance efforts, and the appearance of indexed data types in GHC Announcements * Associated data types in GHC. Manuel Chakravarty [1]announced the availability of indexed data types, an extension of our earlier proposal for [2]associated data types, in GHC's development version. Detailed information on where to get the right GHC and how to use indexed types is available from [3]the Haskell wiki. 1. http://article.gmane.org/gmane.comp.lang.haskell.general/14447 2. http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html 3. http://haskell.org/haskellwiki/GHC/Indexed_types * Yhc Bytecode library 0.3. Robert Dockins [4]announced the release of the [5]Yhc Bytecode library, version 0.3. 4. http://article.gmane.org/gmane.comp.lang.haskell.general/14434 5. http://www.eecs.tufts.edu/~rdocki01/yhc-bytecode.html * Haskell Program Coverage. Andy Gill [6]checked the latest version of HPC, with GHC support, into the head GHC branch 6. http://www.galois.com/~andy/ray/hpc.html * Haskell Mersenne Twister. Lennart Augustsson [7]made available his Haskell implementation of the Mersenne Twister random number generator. 7. http://www.augustsson.net/Darcs/MT/ * Haskell-specific Google Search Engine. Don Stewart [8]initialised a Haskell-specific search engine, as part of Google's coop engine system, which seems to do a good job of targeting just Haskell sites, in particular, mailing list items 8. http://www.google.com/coop/cse?cx=015832023690232952875%3Acunmubfghzq * A process for submitting library extensions. The libraries hackers [9]have developed [10]a document describing how to best go about contributing new code to the core Haskell libraries. On a similar note, the GHC team has prepared [11]a page on best practice for GHC submissions. 9. http://article.gmane.org/gmane.comp.lang.haskell.libraries/5368 10. http://haskell.org/haskellwiki/Library_submissions 11. http://hackage.haskell.org/trac/ghc/wiki/WorkingConventions * How to create a Haskell project. Don Stewart and Ian Lynagh [12]prepared some guidelines on starting your own Haskell project. 12. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/16164/focus=16164 Haskell' This section covers the [13]Haskell' standardisation process. * [14]Lambda-match vs PMC * [15]Indentation of If-Then-Else * [16]Digit groups 13. http://hackage.haskell.org/trac/haskell-prime 14. http://thread.gmane.org/gmane.comp.lang.haskell.prime/1815/focus=1815 15. http://thread.gmane.org/gmane.comp.lang.haskell.prime/1791/focus=1791 16. http://thread.gmane.org/gmane.comp.lang.haskell.prime/1763/focus=1781 Discussion * Haskell Quiz/Ruby Quiz. Haskell Hackers [17]have started recording Ruby Quiz solutions on the Haskell wiki. Lots of fun puzzles are available, and its a useful resource if you're learning the language. 17. http://haskell.org/haskellwiki/Haskell_Quiz * Infinite, open, statically constrained HLists. Oleg Kiselyov [18]described heterogeneous sequences that admit infinite sequences and permits post-hoc addition of new elements, even to an already infinite sequence. 18. http://article.gmane.org/gmane.comp.lang.haskell.general/14424 * Lexically scoped type variables: new proposal. Ben Rudiak-Gould [19]made a new for scoped type variables. 19. http://article.gmane.org/gmane.comp.lang.haskell.general/14429 * Simple GADT parser for the eval example. Greg Buchholz [20]sought advice on creating evaluators with GADTs 20. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/16178/focus=16178 * Package mounting. Frederik Eaton [21]proposed an alternative [22]design for package mounting extensions to the package system. 21. http://article.gmane.org/gmane.comp.lang.haskell.libraries/5389 22. http://hackage.haskell.org/trac/ghc/wiki/PackageMounting * Function types as instances of Num. Greg Buchholz [23]had an interesting problem using functions as instances of Num 23. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/16129/focus=16129 * Yhc Core file generation. Neil Mitchell [24]suggested that it was time to start taking YHC Core output a bit more seriously, and made some proposals. 24. http://thread.gmane.org/gmane.comp.lang.haskell.yhc/397/focus=397 * Parallelism in GHC 6.6 and seq vs. pseq. Simon Marlow [25]noticed that Control.Parallel exports seq when in fact it should probably export pseq. 25. http://article.gmane.org/gmane.comp.lang.haskell.glasgow.user/11093 Jobs * Lectureships in Software Engineering. Jeremy Gibbons [26]announced that applications are invited for three new University Lectureships in Software Engineering, at the University of Oxford. For further information, including full details of the application procedure and selection criteria, see [27]here. 26. http://article.gmane.org/gmane.comp.lang.haskell.general/14445 27. http://www.softeng.ox.ac.uk/jobs/ Blog noise [28]Haskell news from the blogosphere. * [29]Developing Gnome Apps with Glade * [30]The Fun of Functional Infrastructure * [31]Lightweight Threads * [32]Fold diagrams * [33]Haskell and Scheme: Which One and Why? * [34]Scheme Death Knell? * [35]Software Cipher * [36]Algebraic Topology in Haskell * [37]Syntax extension for Monads in Ocaml * [38]The wxhaskell revival * [39]Query Composition using Functional Programming Techniques in C# 3.0 * [40]Practical Haskell? * [41]FP publisher interview * [42]Haskell mentions at the Dynamic Languages Symposium * [43]Phil Wadler (aka Lambda Man) at OOPSLA * [44]Haskell programming * [45]RushCheck, a lightweight random testing tool for Ruby similar to QuickCheck 28. http://planet.haskell.org/ 29. http://j-van-thiel.speedlinq.nl/EddyAhmed/GladeGtk2Hs.html 30. http://blog.syntaxpolice.org/isaac/index.cgi/technology/onInfrastructure.ht… 31. http://lambda-the-ultimate.org/node/1721#comment-21046 32. http://cale.yi.org/index.php/Fold_Diagrams 33. http://scienceblogs.com/goodmath/2006/10/haskell_and_scheme_which_one_a.php 34. http://theonlywinningmove.blogspot.com/2006/10/scheme-death-knell.html 35. http://mult.ifario.us/articles/2006/10/25/solitaire-cipher-in-haskell 36. http://sigfpe.blogspot.com/2006/08/algebraic-topology-in-haskell.html 37. http://www.cas.mcmaster.ca/~carette/pa_monad/ 38. http://koweycode.blogspot.com/2006/10/wxhaskell-on-darcshaskellorg.html 39. http://blogs.msdn.com/ericwhite/pages/FP-Tutorial.aspx 40. http://lambda-the-ultimate.org/node/1803#comment-21779 41. http://on-ruby.blogspot.com/2006/10/author-interview-joshua-smith-prequel.h… 42. http://mark.santaniello.net/archives/272 43. http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2006-10.html#e2006-10… 44. http://ste.aeschbacher.ch/blog/2006/04/entry1 45. http://rushcheck.rubyforge.org/ Quotes of the Week * Simon Marlow: In fact, you don't need an evil scheduler, an ordinary scheduler will do this. * Conor McBride: My operating hypothesis is that even ordinary schedulers are evil... * Larry Wall: Continuations - if you know what they are - I don't need to explain them. If you don't know what they are - you don't want to know. * Cale: [discussing names for Haskell, after suggesting Sapphire] Diamond: The Hardest Programming Language on Earth * ConorMcBride: So, taking Void to be the colour of the empty bikeshed ... * cjeris: I like how you conveniently gloss over the part where your head explodes. * dons: C++: Creating blub programmers since 1985 * mwc: I can only believe that Java is a conspiracy perpetrated by keyboard manufacturers * Pseudonym: (:[]) looks like a ninja robot pirate monkey * chessguy: We've got satan and beelsebob in here, and talking about unicycling.... this channel is guaranteed to be a bad influence on me now * dons: fold (\water dish -> wash water dish) soapywater dishes * masklinn: Scheme, on the other hand, is dynamically compiled and thus doesn't 'fail early', it fails as late as it can, which produces weird error unless you're into testing. Beginners never are into testing. * Riastradh: Assume that I haven't the faintest idea of what a comonad is, beyond that if a monad goes `voob', then a comonad goes `boov' * Anonymous: It is quite possible that 'the ultimate teaching language' was not actually invented when Steele and Sussman came down from the mountain bearing a spool of 9-track magtape... * sigfpe: How can Haskell not be the programming language that all mathematicians should learn? * Syzygy: > let _'__'_'''_'__'_=2 in _'__'_'''_'__'_ * ihope>: > let _' __ ___ (____:_____) = __ ____ (_' __ ___ _____); _' _ __ [] = __ in _' (+) 0 * Syzygy: one thing that stands out is the relatively low distance between thought expressed in my ordinary day-to-day mathematical discourse, and thought expressed in Haskell code Code Watch * Tue Oct 24 14:29:07 PDT 2006. Andy Gill. Haskell Program Coverage. This large checkin is the new ghc version of Haskell Program Coverage, an expression-level coverage tool for Haskell. You can run the coverage tool with -fhpc at compile time. Main must be compiled with -fhpc. * Tue Oct 24 02:13:57 PDT 2006. Simon Marlow. Split GC.c, and move storage manager into sm/ directory. In preparation for parallel GC, split up the monolithic GC.c file into smaller part About the Haskell Weekly News Each week, new editions are posted to [46]the Haskell mailing list as well as to [47]the Haskell Sequence and [48]Planet Haskell. [49]RSS is also available, and headlines appear on [50]haskell.org. The Haskell Weekly News is also [51]available in Spanish translation. To help create new editions of this newsletter, please see the [52]contributing information. Send stories to dons at cse.unsw.edu.au. The darcs repository is available at darcs get http://www.cse.unsw.edu.au/~dons/code/hwn 46. http://www.haskell.org/mailman/listinfo/haskell 47. http://sequence.complete.org/ 48. http://planet.haskell.org/ 49. http://sequence.complete.org/node/feed 50. http://haskell.org/ 51. http://haskell.org/haskellwiki/HWN/es 52. http://haskell.org/haskellwiki/HWN

1 0

Associated data types in GHC
by Manuel M T Chakravarty 30 Oct '06

30 Oct '06

Dear Haskell Folks This is to announce the availability of indexed data types, a modest extension of our earlier proposal for associated data types[1], in GHC's development version. Detailed information on where to get the right GHC and how to use indexed types is available from the Haskell wiki: http://haskell.org/haskellwiki/GHC/Indexed_types This is an experimental feature and any feedback is greatly appreciated. NB: The implementation of associated type *synonyms* is *not* complete yet. We are working on this now. Happy Hacking! Manuel [1] http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html

1 0

University of Oxford: Lectureships in Software Engineering
by Jeremy.Gibbons＠comlab.ox.ac.uk 30 Oct '06

30 Oct '06

UNIVERSITY OF OXFORD Software Engineering Programme Kellogg College THREE UNIVERSITY LECTURERSHIPS IN SOFTWARE ENGINEERING Applications are invited for three new University Lecturerships in Software Engineering. The successful applicants will join the staff of the University's Software Engineering Programme in teaching and researching the application of scientific principles to the development of software systems. The salary will be on a scale up to GBP50,589 per annum. An advanced degree in a related subject, proven teaching ability, and a strong research record - of international standing - are all essential requirements. Applications are particularly welcome from those with expertise in software and systems security, service-oriented architectures, or model-driven development. The appointments will be associated with fellowships at Kellogg College, Oxford and the appointees will be members of the Governing Body of the college. The closing date for applications is 27th November 2006. For further information, including full details of the application procedure and selection criteria, see http://www.softeng.ox.ac.uk/jobs/

1 0

Re: package mounting
by Frederik Eaton 30 Oct '06

30 Oct '06

On Sun, Oct 29, 2006 at 10:03:32PM -0400, Samuel Bronson wrote: > On 10/25/06, Frederik Eaton <frederik(a)a5.repetae.net> wrote: > > >http://hackage.haskell.org/trac/ghc/wiki/PackageMounting > > It looks nice, but don't you think the -package-base flag ought to > take both the package name *and* the mountpoint? My intention was that -package-base specifies a base for the package specified in the preceding -package flag, but I'll clarify it in the document. In other words, it is an optional argument and the syntax is ghc ... -package PACKAGE -package-base BASE ... (giving package PACKAGE mount point BASE) > Otherwise, this looks like what I've wanted all along, if only I knew it ;-). Excellent, thanks. Frederik -- http://ofb.net/~frederik/

3 3

[Announce] Yhc Bytecode library 0.3
by Robert Dockins 29 Oct '06

29 Oct '06

[Please direct disccusion to the yhc list] Fellow Haskellers, I am pleased to announce the release of the Yhc Bytecode library, version 0.3. The major differences from version 0.2 are: * Updated to work with the current Yhc development branch as of 2006-10-13 * API modified to fully handle the string table so that it is no longer exposed to the user * Added support for the 'Ext' and 'Prim' object types * Slightly improved some error messages Source and Haddock documentation downloads are avaliable from: http://www.eecs.tufts.edu/~rdocki01/yhc-bytecode.html Direct access to the darcs repository from: http://www.eecs.tufts.edu/~rdocki01/yhc-bytecode/ Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG

1 0

How to find out who is leaking memory?
by szefirov＠ot.ru 29 Oct '06

29 Oct '06

My program is leaking memory. It is fairly complex and long running on the test that leaks. On that particular test it exits abnormally telling me that heap is overflown. Is there a way to find out what part is leaking memory without refactoring?

1 0

Animal guessing game - critique my code
by JTXX 28 Oct '06

28 Oct '06

Hello everybody. I'm trying to learn Haskell, and so I implemented the classic animal guessing game. However, I feel that there is probably a more elegant implementation than the one shown below, so any suggestions for improvement would be great. Cheers, Caleb \begin{code} data GuessTree = Answer String | GuessTreeQuestion {guessTreeQuestion :: String, guessTreeNo, guessTreeYes ::GuessTree} askQuestion :: String -> IO Bool askQuestion str = do putStrLn str response <- getLine return $ isYes response where isYes ('y':xs) = True isYes _ = False runTree :: GuessTree -> IO GuessTree runTree (Answer name) = do response <- askQuestion $ "Is it a " ++ name ++ "?" if response then do putStrLn "Ha!" return $ Answer name else do putStrLn "What is it?" animal <- getLine putStrLn $ "Enter a question to help distinguish between a " ++ name ++ " and a " ++ animal question <- getLine a <- askQuestion $ "Is the answer yes for " ++ animal ++ "?" (if a then id else flip) (\n y -> return $ GuessTreeQuestion {guessTreeQuestion = question, guessTreeNo = n, guessTreeYes = y}) (Answer animal) (Answer name) runTree GuessTreeQuestion {guessTreeQuestion = ques, guessTreeYes = yesTree, guessTreeNo = noTree} = do response <- askQuestion $ ques if response then do a <- runTree noTree return $ GuessTreeQuestion {guessTreeQuestion = ques, guessTreeNo = a, guessTreeYes = yesTree} else do a <- runTree yesTree return $ GuessTreeQuestion {guessTreeQuestion = ques, guessTreeNo = noTree, guessTreeYes = a} run :: GuessTree -> IO GuessTree run tree = do putStrLn "Think of an animal and press enter." getLine a <- runTree tree r <- askQuestion "Play again?" if r then run a else return a main = run $ Answer "bear" \end{code} Send instant messages to your online friends http://uk.messenger.yahoo.com

2 1

Lexically scoped type variables: new proposal
by Ben Rudiak-Gould 26 Oct '06

26 Oct '06

Hi, everyone. Long time no see. I have a specific proposal for scoped type variables, which is totally different from plans A and B, and which I'd like people to pick to pieces for me. (Especially you, Simon.) Type variable scoping in System F is simple: the type bindings are explicit and follow the same rules as the value bindings. Type variable scoping in Haskell is complicated only because the actual binding sites of the underlying System F type variables aren't visible. In particular, GHC's type signatures are never located at type variable binding sites; at best they're nearby. I'm convinced that the only way that type variable scoping will ever make sense is if scoped type variable bindings are written at their actual System F binding sites. That's what this proposal is about. We introduce "anonymous type aliases", with the syntax decl -> ... | 'type' tycon or perhaps more conveniently decl -> ... | 'type' tycon1 ... tyconN These are like ordinary type aliases, except that instead of referring to a type specified by the programmer, they refer to a type to be inferred by the compiler. They can appear in local bindings; for example, let { type N ; x :: [N] ; x = "hello" } in ... results in N being an alias for (i.e. bound to) Char in the body of the let, just as x is bound to "hello". And that's all. Well, that's not all, but I think the system above, as an extension of Haskell 98, has the power of traditional scoped type variables. Note that the problem of distinguishing between local type variables and nonlocal (scoped) type variables goes away in this proposal. The rule is the same as Haskell 98's: lowercase identifiers are local to a type expression, and uppercase identifiers scope like value bindings. Explicit foralls at the top level of a type are never necessary. Also note that in this proposal, the binding site of the type variable is decoupled from the specification of the type; the type signature that fixes N (by forcing unification with a rigid type) can be located anywhere in N's lexical scope. But that's not all! (I wish it were.) The problem with putting the anonymous type aliases in let/where decls is that System F type variables aren't bound there. (They could be, but I don't think they ever are in GHC.) Where they are bound is in lambda expressions, in function bindings (when the function is called), and in pattern matching on existential dcons. The let/where syntax does suffice for those cases, but it's awkward -- you end up having to write something like f x' y = let type N x :: [N] x = x' in ... It should be possible to bind type aliases everywhere that System F type variables can be bound, for which I propose the following syntax: f (type N) (x::[N]) y = ... and analogously \(type N) (x::[N]) y -> ... case e of D (type N) (x::[N]) y -> ... The parentheses around (type N) are mandatory. This syntax is sensible inasmuch as functions really do take type arguments and dcons really do have type fields, and we're simply writing them explicitly in the place where they've always been. This syntax also harmonizes fairly well with the existing type alias syntax, which can kinda sorta be seen as a pattern binding in this picture. The type variables thus introduced have the same scope as pattern variables, except that they also scope over the pattern type signatures in subsequent arguments or dcon fields. And that's all, for old-style scoped type variables. I realize that capitalized type variables might take some getting used to, but I really feel like this approach, or something like it, is much easier to understand and a significantly better candidate for standardization than what we've got now. It's always clear which variables are scoped and which aren't, and the scoping rules are exactly what you'd naively expect them to be. There are no difficult choices to make in the design (except for syntax; beware of Wadler's Law). Things that worry me: * Do constraint (dictionary) parameters threaten this proposal? They aren't explicit either, and so can't be given type signatures for the purpose of fixing a scoped tyvar. Fortunately in this proposal you needn't identify the meaning of a tyvar at its binding spot, and my intuition is that, if the scoped tyvar is useful at all, there will always be somewhere in its scope where its meaning can be disambiguated by a type signature. But I'm not sure. * Something else that's slipped my mind, but I want to post this before going to bed. * What about the GHC 6.6 changes? See below. I don't know how to make this proposal compatible with GHC 6.6 because I don't understand yet how type inference works with GADTs and impredicativity. My best guess is that the correct change is to require that an anonymous type variable only alias a rigid System F type variable [introduced in the same scope], where I'm not sure whether the part in brackets is necessary. This change has the same disadvantages in my proposal as in the existing GHC implementation: you can no longer write things like "type N ; f (x::N) (y::N) = ..." to enforce monomorphic type equality, or "type N ; x :: [N]" to get partial type signatures. I have an idea for how we might get the best of both worlds: anonymous types bound in let/while declarations could be flexible (subject to unification), while anonymous types bound in argument or field lists could refer to rigid type variables actually bound there. I'm not sure how much sense this idea makes because, as I said, I don't grok the reason for the GHC 6.6 changes yet. If people are confused by any aspect of the proposal, give me GHC 6.4 or 6.6 examples and I will either translate them into my proposed syntax, or fail to do so and thereby learn something interesting. And that's really all. Comments solicited. -- Ben

1 0