- Haskell - Haskell.org

type question revisited
by mv 06 Jun '05

06 Jun '05

I answered my own question only to raise another - what I wanted to do is this > foo :: (a -> String) -> [a] -> [String] > foo shw x = > let > shf :: ( forall a . a ) -> String > shf o = shw o > > in map shf x the type of shf is a rank 2 type - but how do you map it ? as the above gives thise error in hugs: Use of shf requires at least 1 argument ____________ Virus checked by G DATA AntiVirusKit Version: AVK 12.0.37 from 06.12.2002 Virus news: www.antiviruslab.com

2 1

FINAL CALL FOR ESSLLI05 registration
by Fairouz Kamareddine 06 Jun '05

06 Jun '05

======================================================================== || FINAL CALL FOR REGISTRATION AND ACCOMMODATION BOOKING || || || || ESSLLI 2005, http://www.macs.hw.ac.uk/esslli05/ || || 17th European Summer School in Logic, Language and Information || || The annual summer school of FoLLI, || || the Association for Logic, Language and Information. || || Heriot-Watt University, Edinburgh, Scotland || || 8-19 August, 2005 || ||--------------------------------------------------------------------|| || THREE WEEKS LEFT FOR REGISTRATION AND ACCOMMODATION BOOKING || || DEADLINE: 7 July 2005 || ||--------------------------------------------------------------------|| || REGISTRATION PROCEDURE ON LINE AT: || || http://www.macs.hw.ac.uk/esslli05/give-page.php?17 || || (Note, this is during the Edinburgh famous international festivals|| || http://www.eventful-edinburgh.com/ || || so accommodation must be reserved promptly to be guaranteed) || ||====================================================================||

1 0

ICLP 2005: Call for Posters
by ICLP 2005 06 Jun '05

06 Jun '05

Final Call for poster submissions 21st. INTERNATIONAL CONFERENCE ON LOGIC PROGRAMMING (ICLP'05) Oct 2-5, 2005 Sitges (Barcelona), Spain http://www.iiia.csic.es/iclp2005/ * Conference scope. Poster contributions are sought in all areas of logic programming including: Theory (semantic foundations, formalisms, non-monotonic reasoning, knowledge representation, inductive logic programming) Language issues (constraints, concurrency, objects, coordination, higher order, types, modes, programming techniques) Implementation (compilation, memory management, virtual machines, parallelism) Environments (program analysis, program transformation, validation and verification, debugging) Applications (deductive databases, software engineering, natural language, web tools, internet agents, artificial intelligence, molecular biology) * The ICLP Posters provide an excellent forum for authors to present their work in an informal and interactive setting. Posters are ideal for presenting speculative, late-breaking results or for giving an introduction to interesting, innovative work. Posters provide authors with a unique opportunity to make their work highly visible during the conference and get feedback from the community on the ongoing work. Poster submissions focusing on the following are specifically encouraged: Tools, applications, current work not yet ready for publication, PhD thesis summaries (submitted recently or to be submitted in the next 6 months), research project overviews. Posters must be submitted electronically through the conference paper submission web pages. A poster should contain an extended abstract of up to two pages. Each accepted poster will have up to 2 pages in the conference proceedings, and a 10 minute slot for presentation during the conference. Posters will also be displayed during the poster session. * Submission deadline (firm): June 20, 2005 Notification: July 05, 2005

1 0

Type Question
by mv 03 Jun '05

03 Jun '05

what is the type of 'shf' in > foo :: (a -> String) -> a -> () > foo shw x = > let > shf o = shw o > > in return () for it certainly is not 'shf :: a -> String', as this explicit signature will not type check ? ____________ Virus checked by G DATA AntiVirusKit Version: AVK 12.0.37 from 06.12.2002 Virus news: www.antiviruslab.com

1 0

ANNOUNCE: The jhc Haskell compiler.
by John Meacham 02 Jun '05

02 Jun '05

See what I've been doing :) This document as html is available at http://repetae.net/john/computer/jhc/jhc.html and the main jhc page with links to the darcs repo is at http://repetae.net/john/computer/jhc/ = Jhc = Jhc is a compiler for Haskell that aims to produce very efficient code as well as explore novel compilation techniques in an attempt to make them practical. One thing jhc does not aim to be is a toy or proof-of-concept compiler. A lot of the techniques have already had proof-of-concept implementations and jhc aims to determine how to bring them to a full-scale Haskell compiler. (or die trying) Although jhc is not ready for general use, I think some of its ideas or code might be useful to other people so I am deciding to release it in this state. == Jhc Bullet Points == * Full support for Haskell 98, The FFI and some extensions. (modulo some bugs being worked on and some libraries that need to be filled out) * Produces 100% portable ISO C. The same C file can compile on machines of different byte order or bit-width without trouble. * No pre-written runtime. other than 20 lines of boilerplate all code is generated from the Grin intermediate code and subject to all code simplifying and dead code elimination transformations. As a result, jhc currently produces the smallest binaries of any Haskell compiler. (main = putStrLn "Hello, World!" compiles to 6,568 bytes vs 177,120 bytes for GHC 6.4) * No garbage collector. A variant of Region Inference is in the works. * Compilation by transformation with 2 general intermediate languages. * First Intermediate language based on Henk, Pure Type Systems and the Lambda cube. This is similar enough to GHCs core that many optimizations may be implemented in the same way. * Second Intermediate language is based on Boquist's graph reduction language. This allows all unknown jumps to be compiled out leaving standard case statements and function calls as the only form of flow control. Combined with jhc's use of region inference, this means jhc can compile to most any standard imperative architecture/language/virtual machine directly without special support for a stack or tail-calls. * Novel type class implementation not based on dictionary passing with many attractive properties. This implementation is possible due to the whole-program analysis phase and the use of the lambda-cube rather than System F as the base for the functional intermediate language. * Intermediate language and back-end suitable for directly compiling any language that can be embedded in the full lambda cube, making things like a compiler for cayenne much more direct. There is no type erasure phase, types are erased for the simple reason that values do not depend on them via the standard dead-code elimination pass. * A very modern design, it using rank-n polymorphism, monad transformers, generic programing, and existential types to make the code very concise and clear and improve code reuseability. (since jhc was written in pieces over 5 years, some at times when I just started using Haskell, the code quality actually varies a lot across the whole project) * All indirect jumps are transformed away, jhc's final code is very similar to hand-written imperitive code, using only branches and static function calls. A simple basic-blocks analysis is enough to transform tail-calls into loops. * Full transparent support for mutually recursive modules. == More in depth == === Type Classes === One of the most novel things about jhc is its implementation of type classes which differs significantly from the standard dictionary passing approach used by other Haskell compilers. Jhc's unique approach is made possible by 2 other design choices, the use of a pure type system with no distinction between types and values and its use of whole-program analysis. The basic idea is that instead of passing a dictionary, a case statement directly scrutinizes the type parameter of a function and calls the appropriate overloaded routine directly. This has a number of interesting properties * The number of extra hidden parameters is the number of free type variables in a functions signature rather than the number of class constraints. So (Ord a, Show a, Num a) => a -> a will only pass a single extra parameter for the type of a rather than 3 dictionaries. * 2 indirections, first one to look up the dictionary, then one to call the function pointed to in the dictionary are replaced by a single case of an algebraic data type and calls to statically known functions. This is exactly the transformation that the GRIN points-to analysis does, but much sooner and with much better optimization potential. Calls to statically known functions are MUCH more efficient. * Standard case coalescing optimizations have a dramatically enhanced effect when dealing with overloaded functions. imagine the code snipped (x*(y + z)/z) :: a . Each of the calls to the polymorphic functions *, +, and / will expand to a case statement on 'a', since all case statements are trivially examining the same value, they are coalesced into a single one. With dictionary passing, we would have to look up the appropriate entry in the Num hidden parameter, the Floating hidden parameter, then look up each of *, +, and / individually. Under jhc's scheme all of that is statically transformed into a single case on a normal algebraic type. This optimization is a HUGE win. Jhc's ability to do this comes from the fact that it is statically evident from that case statement that the type fully determines every polymorphic function on that type, a property that is lost in the dictionary passing approach since as far as the compiler is concerned, arbitrary functions may be being passed in the dictionaries, it does not know that they come in specific correlated sets. * Functional Dependencies actually lead to run-time savings. each functional dependency transforms into a case statement which may be omitted. * Although a whole-world analysis is needed to generate full versions of type class methods, this is actually rarely needed in practice, as it is often the case the compiler is able to statically prove only a certain subset of types are needed at any given point and is able to generate specialized versions on the spot. This is implemented in a manner very similar to GHC's rules. * Advanced compile-time and run-time specializations are possible via pragmas. (see below) === E === E is a pure type system based on Henk and the lambda-cube. An important property of E is that there is no distinction between types and values, this is important for jhc's implementation of type classes. === Grin === Grin is basically a first-order monadic functional language. It is very similar to the Graph Reduction Intermediate Language as defined by Boquist but has a few notable changes. * It is typed. * It has multiple return values as a primitive (unboxed tuples) * My target is higher level C or C-- rather than RISC code, so some transformations are less important as the C compiler can be assumed to take care of them. * The terminology and syntax borrows from Haskell's current implementation of monads and 'do' notation. Most of the transformations mentioned in Boquist's thesis have been implemented, however certain intermediate states in Boquist's scheme are actually invalid in the strongly typed Grin of jhc so need to be combined or modified. A whole lot can be learned from the Grin data type and Grin is fully defined by the following infixr 1 :->, :>>= data Lam = Val :-> Exp deriving(Eq,Ord,Show) data Exp = Exp :>>= !Lam | App Atom [Val] -- ^ this handles applications of functions and built-ins | Prim Primitive [Val] | Case Val [Lam] | Return { expValue :: Val } | Store { expValue :: Val } | Fetch { expAddress :: Val } | Update { expAddress :: Val, expValue :: Val } | Error String Ty -- ^ abort with an error message, non recoverably. | Cast Val Ty -- ^ reinterpret Val as a different type, also used to box\/unbox lifted types deriving(Eq,Show,Ord) data Val = NodeC !Tag [Val] | NodeV !Var [Val] | Tag !Tag | Const Val -- ^ pointer to constant data, only Lit, Tag, and NodeC may be children | Lit !Number Ty | Var !Var Ty | Tup [Val] | ValPrim APrim deriving(Eq,Show,Ord) data Ty = TyTag -- ^ a lone tag | TyPtr Ty -- ^ pointer to a heap location which contains its argument | TyNode -- ^ a whole tagged node | Ty Atom -- ^ a basic type | TyTup [Ty] -- ^ unboxed list of values | TyUnknown -- ^ an unknown possibly undefined type, All of these must be eliminated by code generation deriving(Eq,Ord) === Extensions === Jhc implements several extensions to Haskell 98 ==== Standard Extensions ==== * The FFI is almost fully supported except for calling Haskell code from C. * Hierarchical module names are supported as described in the addendum. The search algorithm is somewhat different than GHC though, Control.Monad.Identity will be searched for as Control/Monad/Identity.hs, Control/Monad.Identity.hs and Control.Monad.Identity.hs, giving you a bit more freedom in laying out your directory structure. * Empty data declarations with no constructors are supported * Liberalized type synonyms are supported (type synonyms may appear anywhere a type may appear) * INLINE, SPECIALIZE pragmas * unsafePerformIO, unsafeInterleaveIO are provided. ==== New Extensions ==== * Magic underscore. Using underscore in an expression expands to bottom with an error message giving the current file and line number. This is useful because it is common practice nowadays to use undefined as a witness for a type. Relatively easy errors to make using this scheme lead to an unhelpful "error: Prelude.undefined" with no indication of where the error actually is. By using the alternate <code>(_ :: Int)</code> rather than <code>(undefined :: Int)</code> you will get an informative run-time error message as well as save some space. The magic underscore is also useful as a placeholder for code you mean to fill in later. * foreign primitive, all primitives are brought into scope with a foreign primitive declaration (barring a few numeric operators) , these can also be used to gain access to C constants, obviating much of the need for a preprocessor such as hsc2hs and allowing portable C code to be generated by jhc. * ERROR_ANNOTATE pragma. This is a generalization of GHCs assert magic. A function which is given an ERROR_ANNOTATE pragma will be replaced with an alternate version that takes the functions use site as an argument. This allows error messages to be in terms of where said function was used. The alternate function is named <code>[function]_err_ann__</code> and must be in the same module as the original function. Jhc does no checking to ensure both functions have the same effect, it is up to the user to ensure that. An example is <pre> head :: [a] -> a head (x:xs) = x head [] = error "head - empty list" {-# ERROR_ANNOTATE head #-} head_err_ann__ :: String -> [a] -> a head_err_ann__ pos (x:xs) = x head_err_ann__ pos [] = error $ pos ++ ": head - empty list" -- Now, a call to head on an empty list will produce an error message like -- "Main.hs:23: head - empty list" </pre> * SUPERSPECIALIZE pragma. This pragma has the same affect as the SPECIALIZE pragma, but in addition to doing compile-time specialization, SUPERSPECIALIZE performs run-time specialization. A superspecialized function will perform a single check against the type it is called with and depending on the single test, call a specialized version of the function. This can be a huge win when working with overloaded numeric types, imagine a matrix-multiply routine, if the type cannot be determined at compile-time then we would normally be forced to fall back to generic version which may have hundreds of additions and multiplications, each of which must test what type its argument are. If we SUPERSPECIALIZE the multiply routine instead, a single run-time test will be performed and the much much more efficient specialized routine will be used, even if it could not be proven at compile time. * MULTISPECIALIZE pragma. This is equivalent to calling SPECIALIZE against every possible type. It's main cost is compile time and memory usage. It should be used only sparingly as it can lead to quadratic rule explosion in the total number of types in the transitive closure of all imported modules in the worst case. * MULTISUPERSPECIALIZE pragma. This is equivalent to calling SUPERSPECIALIZE against every possible type. If not careful, this can result in massive code bloat but might be a big win in certain cases. == The story of jhc == When I first started to learn Haskell in 1999, I decided I needed a project. Haskell was my first (modern) functional language and I was seduced by its robust strong type system and efficiency gains. After writing a toy ray-tracer (my usual first project in a new language) it was clear I needed to try something somewhat more challenging and jhc was born. My reasoning was simple, by writing a Haskell compiler in Haskell I will double my language learning speed since I will not only have to learn how to program in it by forcing myself to complete a non-trivial project, but also its subtle semantics and dark corners since I actually needed to implement it correctly. Writing a compiler is also doubly efficient to begin with, since if you self-compile improvements not only give you a better optimizer, but also speed up your self-compiled compiler. All in all I figure I was making very good use of my time. For some reason, when I explain my reasoning to other people they look at me like I am crazy, but I can detect no flaw in my logic. In any case, I worked on jhc on and off for a while, the project got boosts a few times, such as when hatchet was released and I used it to replace my front end. Recently, with my purchase of a faster machine actually beefy enough to run jhc and the realization I was getting good optimizations from my implementation of type classes combined with the small binary size of produced files I decided to make a push for jhc to become a usable compiler. == All is not well in jhc-land == There are still substantial issues which need to be overcome before jhc can be used for general Haskell programing * It doesn't scale. Basically since jhc compiles the entire standard library along with your code, even moderately complex programs can be beyond its grasp * It takes ridiculous amounts of memory and CPU. A gigabyte of RAM usage is not unheard of. * There are still some major bugs * It leaks memory. The Region inference algorithm is still in the tweaking stage and programs are known to leak memory. for short running programs, this does not seem to be an issue, but anything expected to perform a lot of reductions will probably run out of heap. * it is not done * Arrays are very slow at the moment. * only about 70% of nofib compiles at the moment. * That said, I am releasing it because people might find the ideas interesting or be able to learn from or borrow of the code. * Horrible error messages. A few programmer errors (and some non-errors) cause the compiler to quit with an 'error' or pattern match failure. == References == * Boquist Thesis * Henk paper * Pure Type Systems type checking paper * CPR analysis. * Strictness analysis w/ HORN clauses * Typing Haskell in Haskell * Hatchet -- John Meacham - ⑆repetae.net⑆john⑈

5 5

CfP: 3rd APPSEM II Workshop on Applied Semantics
by Hans-Wolfgang Loidl 01 Jun '05

01 Jun '05

[ --- standard apologies for multiple postings apply -- HWL --- ] 2nd CALL FOR PAPERS 3rd APPSEM II Workshop (APPSEM05) Frauenchiemsee, Germany, 12-15 September 2005 http://lionel.tcs.ifi.lmu.de/APPSEM05/ The final workshop of the APPSEM II initiative will take place on the island of Frauenchiemsee, an island in Lake Chiemsee near Munich, from September 12 to 15, 2005. It will follow immediately onto the APPSEM II Summer School at the same location. Background and Objectives APPSEM II (Applied Semantics II) is a 36-month FP5 IST thematic network project that started in January 2003. The network consists of 20 sites (with a number of subsites) and is coordinated by Martin Hofmann (LMU München). The APPSEM'05 workshop will be held on the island Frauenchiemsee, in the lake of Chiemsee, approximately 100 km south east of Munich. This is the 3rd general annual meeting of the network. Previous meetings took place in Nottingham (APPSEM'03) and in Tallinn (APPSEM'04). All members of the network are invited to attend, but participation of non-members from both academia and industry with interests in application-oriented programming language semantics is actively encouraged, too. The purpose of the workshop is to present new results and plan future work in each of the following nine themes of the network: - Program structuring: object-oriented programming, modules, - Proof assistants, functional programming, and dependent types, - Program analysis, generation, and configuration, - Specification and verification methods, - Types and type inference in programming, - Games, sequentiality, and abstract machines, - Semantic methods for distributed computing, - Resource models and web data, - Continuous phenomena in Computer Science. For each theme there will be a session of contributed talks. In addition, there will be several invited talks, an industrial panel session, a brainstorming session and a business meeting. Following on from the workshop, an informal proceedings will be published on the web. Full refereeing will be done on revised versions of the papers after the workshop with a selection of papers being published in a formal proceedings. Submission Two kinds of contributions are solicited: - short presentations of circa 15 minutes each - full presentations of circa 30 minutes each Submission for short presentations Authors should submit a short abstract of maximal 2 pages. Short presentations offer the opportunity to advertise any work relevant for APPSEM II, either completed or in progress. These submissions will be judged by the programme committee according to interest and relevance to APPSEM II; the PC will try to accommodate in the workshop programme all short presentations that meet these criteria. Submission for full presentations Submission of full presentations is in 2 phases: phase 1 focusses on relevance of the topic to the APPSEM remit; phase 2 involves full refereeing. Phase 1: Authors should submit an extended abstract of maximal 10 pages, excluding appendices. The PC encourages high quality extended abstracts that can be considered for formal publication within few months. The submissions will be ranked by the PC according to quality and relevance to APPSEM II themes. Successful submissions will get a 30 minute slot for presentation at the workshop, and will be considered for phase 2. Other submissions will be automatically considered for 15 minute presentation slots. Authors of submissions to phase 1 automatically express a commitment to submit to phase 2 if accepted. Phase 2: Authors should submit a full paper (max 20 pages excluding appendices) that will be refereed according to usual scientific standards after the workshop. Selected papers will be published in the proceedings for the workshop. We expect to have 10-12 contributions published in the final proceedings. The exact format of these final proceedings is yet to be decided. Important dates - Submission for short presentations (max 2 pages): 8 July 2005 - Submission for full presentations (max 10 pages): 8 July 2005 - Notification of acceptance (phase 1): 12 August 2005 - Workshop: 12-15 September 2005 Programme committee The programme committee consists of one or two scientists per theme and a chairman. - Gilles Barthe - Gavin Bierman - Thierry Coquand - Pierre-Louis Curien - Peter Dybier - Philippa Gardner - Chris Hankin - Fritz Henglein - Martin Hofmann (Chair) - Neil Jones - Achim Jung - Peter O'Hearn - Eugenio Moggi - Andrew Pitts - Francois Pottier - Didier Remy - Uday Reddy - Glynn Winskel Venue The picturesque small island Frauenchiemsee is home of a Benedictine monastery, which nowadays also hosts seminars. Founded in 722 by Duke Tassilo III of Bavaria, its most famous abbess was Irmengard (died 866; beatified 1928), great-granddaughter of Charlemagne. Other historically recorded abbesses are Sabina Preindorfer (died 1609) und Magdalena Haidenbucher (died 1650). Until the 11th century the monastery was directly subordinated to the Holy Empire, later on it was subordinated to the Archbishop of Salzburg. Organisers The workshop is organized by Martin Hofmann, Hans-Wolfgang Loidl, Sigrid Roden, Konstantin Kutzkow (Institute for Informatics, Ludwig-Maximilians Universitaet München).

1 0

HaskellForge
by Gour 01 Jun '05

01 Jun '05

Dear Haskellers, I'd like to suggest one idea which is going on in my mind for quite some time... Recently the project where I am offering some help (gtk2hs) had to move part of its web site from SourceForge to haskell.org since SF site has some limits which we were not able to overcome. So, why not form HaskellForge and thereby form powerful Haskell alliance, ie. common site which can host many/most present Haskell projects offering appropriate web & other (eg. darcs) services? If we take a look on new HCAR, we can see that many Haskell projects are scattered all around, so it would be nice to have them on one place. Ruby (which is not so long around, at least in the Western part) has RubyForge site which at the moment hosts 653 projects with 2159 registered users. Then there is also, Ruby Application Archive (RAA) with 1190 projects. Haskell community is a very friendly one and has lot of brain-power on disposal. Why not add some (more) organizational skills to make it even more friendlier place? Any comment? Sincerely, Gour -- Registered Linux User | #278493 GPG Public Key | 8C44EDCD

12 20

Should inet_ntoa Be Pure?
by Dominic Steinitz 01 Jun '05

01 Jun '05

> Axel Simon wrote: > > > > > Does anyone know why these are in the IO monad? Aren't they > > pure functions > > > > converting between dotted-decimal strings and a 32-bit network byte ordered > > > > binary value? > > > > I guess the answer is no for both: The first one can fail > > That doesn't mean that it should be in the IO monad; using Maybe > would suffice. Agreed. Perhaps I wasn't clear enough in my original question. There appears to be no intrinsic reason why they should be in the IO monad. > > > > Hence ntoa needs to be an IO action so that the value is read > > immediately before the next ntoa call is executed. > > That shouldn't be an issue so long as the buffer contents are > converted to a Haskell String before the function is called again > within the same thread. > > However, I wouldn't rely upon all implementations of inet_ntoa() being > thread-safe. > > What you could do is to apply unsafePerformIO to > > [snip] > > Or you could just re-implement the functions in Haskell. > > Apart from the re-entrancy issues with inet_ntoa(), many > implementations of inet_addr() have misfeatures, e.g. allowing octets > to be expressed in octal or hex, or allowing numbers outside of the > 0-255 range (in which case, the top bits overflow into the next > octet). Perhaps better would be: inet_addr' :: (Octet,Octet,Octet,Octet) -> HostAddress inet_ntoa' :: HostAddress -> (Octet,Octet,Octet,Octet) I see Peter Simons has already written something: http://cryp.to/hsdns/docs/Network.IP.Address.html#v%3Aha2tpl Dominic.

8 16

Discrete event simulation
by Bruno Martínez Aguerre 01 Jun '05

01 Jun '05

Hi. I'm wondering if there is work done about discrete event simulation in functional languages, and more specifically, Haskell DSLs. Any pointers? Regards, Bruno Martínez Conectese mas rapido y ahorre hasta un 50% Tel. 0909.2030 => $0,15 IVA incluido el minuto ______________________________________________________ http://www.internet.com.uy - En Uruguay somos internet Conectese mas rapido y ahorre hasta un 50% Tel. 0909.2030 => $0,15 IVA incluido el minuto ______________________________________________________ http://www.internet.com.uy - En Uruguay somos internet

4 4

June Issue of The Monad.Reader now online - http://www.haskell.org/tmrwiki/IssueThree
by Shae Matijs Erisson 01 Jun '05

01 Jun '05

http://www.haskell.org/tmrwiki/IssueThree This month's issue has a definite introductory theme. It includes republished book reviews, notes on learning, a look at the differences between functional and object oriented programming, and distributed computation. As always, The Monad.Reader invites submissions on Haskell and related topics. Send a summary or abstract for your article to shae(a)ScannedInAvian.com As the summer approaches, it's getting harder to find authors. The Monad.Reader is fueled entirely by articles and time contributed by the community. Please contribute! -- It seems I've been living two lives. One life is a self-employed web developer In the other life, I'm shapr, functional programmer. | www.ScannedInAvian.com One of these lives has futures (and subcontinuations!)| --Shae Matijs Erisson

1 0