- Haskell - Haskell.org

ANN: H98 FFI Addendum 1.0, Release Candidate 4
by Manuel M. T. Chakravarty 28 Apr '02

28 Apr '02

Dear Haskell Community, Release Candidate 4 of the Haskell 98 FFI Addendum is now available from http://www.cse.unsw.edu.au/~chak/haskell/ffi/ Changes since RC1 are summarised below. Please check this version for problems. If there are no problems reported within the coming month, I would propose to make RC4 into the final 1.0 definition. Cheers, Manuel -=- * 5.8: Clarified documentation for `MarshalAlloc.free'. * 5.8: Added `MarshalAlloc.realloc'. * 3: Added the new safety level `threadsafe' with an explanation at the end of 3.3 (this has been prompted by Sigbjorn Finne's addition of OS thread to GHC) * 3: Replaced the nontermional `entity' by `impent' and `expent' to distinguish between import and export entities (as they are defined differently in later sections). * 3.2: Clarified the description of foreign types; in the previous discussion, `IO ()' was strictly speaking not included as a valid return type. * 4.1.5: New section discussing the traps & pitfalls of type promotion with C bindings. * Renamed the functions constructing `ErrorType's, as `userError' collided with a function name in the Prelude. * Various minor fixes

1 0

RE: Lexing character literals in H98
by Simon Peyton-Jones 26 Apr '02

26 Apr '02

| Yet another H98 question, this time regarding the module | Char: Is it a deliberate design decision that readLitChar | handles decimal, octal, and hex escapes, but lexLitChar | handles only decimal ones? It looks more like an oversight to me... Me too. It's a messy part of the language that both readLitChar and lexLitChar exist, with pretty much duplicate code. Still, I'd rather not rewrite it all (easy to introduce more bugs). But it is unfortunate that the two actually parse different escape sequences. Would anyone like to volunteer to write missing code for lexLitChar? Below is the stuff from the Report that describes the spec | Another question is if the uppercase variants '\O...' and | '\X...' should be forbidden explicitly. Current | implementations seem to differ in this aspect. Implementation shouldn't accept \O \X etc. I don't think it's appropriate to forbid it... should we forbid \A (read number base 35) too? Simon The function showLitChar converts a character to a string using only printable characters, using Haskell source-language escape conventions. The function lexLitChar does the reverse, returning the sequence of characters that encode the character. The function readLitChar does the same, but in addition converts the to the character that it encodes. For example: showLitChar '\n' s = "\\n" ++ s lexLitChar "\\nHello" = [("\\n", "Hello")] readLitChar "\\nHello" = [("\n", "Hello")]

1 0

SAVE02 call for papers *** EXTENDED DEADLINE ***
by Sandro.Etalle＠cwi.nl 26 Apr '02

26 Apr '02

FloC 2002 workshop SAVE 2002 Workshop on Specification, Analysis and Validation for Emerging Technologies Copenhagen , Denmark, July 27, 2002 CALL FOR PAPERS EXTENDED DEADLINE: MAY 15, 2002 ^^^^^^^^^^^^ TOPICS * Specification languages and rapid prototyping: * Logic programming and its extensions * First-order, constructive, modal and temporal logic * Constraints * Type theory * Analysis: * Abstract interpretation * Program analysis and transformation * Validation: * Simulation and testing * Deductive methods * Model checking * Theorem proving The preferred issues include, but are not limited to: * Mobility: specification and verification of mobile code. * Security: e.g. specification and verification of security protocols. * Interaction, coordination, negotiation, communication and exchange on the Web. * Open and Parametrized Systems. PUBLICATION The proceedings of the workshop will be published as technical report. We are planning a journal special issue: a selection of the workshop papers will be invited for submitting a full version to it. MOTIVATIONS AND GOALS The huge increase in interconnectivity we have witnessed in the last decade has boosted the development of systems which are often large-scale, distributed, time-critical, and possibly acting in an unreliable or malicious environment. Furthermore, software and hardware components are often mobile, and have to interact with a potentially arbitrary number of other entities. These systems require solid formal techniques for their verification and analysis. In this respect, computational logic plays an increasingly important role, both providing formal methods for proving system's correctness and tools - e.g. using techniques like constraint programming and theorem proving - for verifying their properties. In addition, computational logic is gaining importance as tool for the specification of these systems. For instance, one can think at the specification, in a form of temporal logic, of a communication protocol. Such specification offers the advantage that one can reason about it using formal methods, and at the same time it is often easily executable by rewriting it into a logic-based programming language. The first edition of SAVE 2001 took place as a one-day satellite event of ICLP/CP 2001 in Paphos, Cyprus. The technical program consisted of an invited talk and seven paper presentations covering problems related to security, real time systems, simulation and performance evaluation, and general purpose verification techniques (all papers are available on line in the here). The aim of this new edition is to bring together researchers interested in the use of computational logic as a tool for the specification, analysis and validation of systems, with particular emphasis on (but not restricted to) emerging technologies like World Wide Web and e-commerce, (protocols for) smart cards and mobile telephony, wireless technology, control and real-time systems, open and distributed systems. IMPORTANT DATES * Deadline for submissions: May 15, 2002 * Notification: June 4, 2002 * Final papers due: June 24, 2002 * Workshop date: July 27, 2002 PROGRAM COMMITTEE Alessandro Armando DIST, University of Genova, Italy Radhia Cousot, Ecole Polytecnique, France Thierry Massart, U. Libre de Brussels, Belgium Catuscia Palamidessi, Penn State University, USA Frank Pfenning, Carnegie Mellon University, USA Andreas Podelski Max-Planck-Institut, Germany Sriram Rajamani, Microsoft Research, USA Jean-Francois Raskin, U. Libre Brussels, Belgium INSTRUCTION FOR AUTHORS Please send your submission as a (uuencoded, gzipped, if possible) Postscript or PDF file to: giorgio(a)disi.unige.it The paper must not exceed 15 pages, and must contain a cover page with: title, name and addresses of the authors, abstract and keywords. Please prepare the manuscript using LaTex article style, single column, 12.2cm x 19.3cm text area. The proceedings will be published in electronic format. A printed version will be distributed to all participants of the workshop. WORKSHOP ORGANISERS/PC CHAIRS * Giorgio Delzanno - Dipartimento di Informatica e Scienze * dell'Informazione - Universita' di Genova. e-mail: giorgio(a)disi.unige.it * Sandro Etalle - Department of Computer Science- University of Twente and CWI. e-mail: etalle(a)cwi.nl * Maurizio Gabbrielli - University of Bologna, Italy e-mail: gabbri(a)cs.unibo.it

1 0

free variables in lambda terms ?
by Konst Sushenko 26 Apr '02

26 Apr '02

hi, would someone please help me with the question below? i tried asking on comp.lang.functional list but noone responded... "konsu" <konsu(a)hotmail.com> wrote in message news:<ATOx8.42722%24t65.9246(a)nwrddc02.gnilink.net>... > hello, > > as an exercise, i am trying to implement a pure lambda calculus interpreter. > i am using normal order reduction with textual substitution of terms. > > a program that my interpreter accepts is a list of name/term declarations: > > <name 1> = <lambda term 1> > ... > <name N> = < lambda term N> > > each declaration defines a global name and binds a term to it, and the > interpreter starts evaluation with the term named 'main'. > > > i implemented all the functions necessary to evaluate a closed lambda term, > and now i got to the point where i need to handle free variables in a term. > my assumption is that free variables denote terms declared as above. > > my question is when should i expand free variables? i also would appreciate > any references to literature, etc. where this is discussed. > > so far i believe the way to do it is to reduce a term to its normal form > without handling free variables, and then, if it has free variables, look up > their definitions in the environment and replace them with their bodies, > evaluate the resulting term to its normal form again, and keep repeating > this process until no free variables are found. > > is this the right way to do it? or should i check for free variables when i > compute the WHNF, etc.? any advice from the experts? > > thanks > konst > >

2 1

RE: Syntax of functional dependencies
by Simon Marlow 26 Apr '02

26 Apr '02

> I errorneously specified categories as > > class (Eq object, Eq morphism) => > Category id object morphism | id ->, id -> morphism > where o :: id -> morphism -> morphism -> Maybe morphism > dom, cod :: id -> morphism -> object > > it should have been > > class (Eq object, Eq morphism) => > Category id object morphism | id -> object, id -> morphism > ... ^^^^^^ > > - but ghci 5.02.2 does not complain. Why? The syntax of a functional dependency is (from GHC's parser): fd : varids0 '->' varids0 varids0 : {- empty -} | varids0 tyvar so the list of tyvars on either side of the '->' can be empty. Functional dependency experts can correct me if I'm wrong, but I imagine though that 'a ->' is not a very useful functional dependency (isn't it the same as giving no functional dependency at all?), and '-> a' means that there can only ever be one instantiation for 'a' in the whole program. Cheers, Simon

1 0

Re: free variables in lambda terms ?
by John Hughes 26 Apr '02

26 Apr '02

"konsu" <konsu(a)hotmail.com> wrote in message news:<ATOx8.42722%24t65.9246(a)nwrddc02.gnilink.net>... > hello, > > as an exercise, i am trying to implement a pure lambda calculus interpreter. > i am using normal order reduction with textual substitution of terms. > > a program that my interpreter accepts is a list of name/term declarations: > > <name 1> = <lambda term 1> > ... > <name N> = < lambda term N> > > each declaration defines a global name and binds a term to it, and the > interpreter starts evaluation with the term named 'main'. > > > i implemented all the functions necessary to evaluate a closed lambda term, > and now i got to the point where i need to handle free variables in a term. > my assumption is that free variables denote terms declared as above. > > my question is when should i expand free variables? i also would appreciate > any references to literature, etc. where this is discussed. > > so far i believe the way to do it is to reduce a term to its normal form > without handling free variables, and then, if it has free variables, look up > their definitions in the environment and replace them with their bodies, > evaluate the resulting term to its normal form again, and keep repeating > this process until no free variables are found. > This is certainly one reasonable possibility. Alternatively, you could replace a free variable by its value as soon as you encounter it in a reduction context (i.e. at the point where your reducer would make the next reduction step). Since you're aiming for normal forms rather than weak head normal forms, you presumably will substitute for free variables under lambdas. I assume you're being careful not to capture variable names during substitution -- beware of cases like f = g g = 1 main = (\g.f) 2 where substituting for f in main must rename the local variable g to avoid a name clash with the global g. Given the Church-Rosser property, it doesn't really matter when you substitute for free variables -- you should get the same result in any case. The only thing to be careful of is that you don't substitute "too eagerly", and thus fall into an infinite loop. Global definitions are presumably the only way to achieve recursion in your system (apart from using Y); substituting too eagerly in recursive definitions will of course lead to loops. Just consider fac = \n. if (== n 0) 1 (* n (fac (- n 1))) where if you substitute for fac before applying the lambda-expression, you clearly fall into a loop. John Hughes

1 0

Re: some algorithms are hard to code in O(n) in Haskell
by Ch. A. Herrmann 25 Apr '02

25 Apr '02

Hi, first of, you should consider whether you really need O(n). Since you want to use Haskell, your aim is probably more on elegance than on performance. Maybe, an Theta(n * log n) program in Haskell would be easier to verify. Surely, you can program in imperative style in Haskell achieving optimal complexity, using arrays with destructive updates (check the Glasgow extensions). For some O(n) graph algorithms (like connected components), there is an elegant optimal solution by John Launchbury: "Graph algorithms with a functional flavour", Springer Lecture Notes in Computer Science 925, pp. 308--331, 1995. Good luck -- Christoph Herrmann

1 0

Syntax of functional dependencies
by Till Mossakowski 25 Apr '02

25 Apr '02

I errorneously specified categories as class (Eq object, Eq morphism) => Category id object morphism | id ->, id -> morphism where o :: id -> morphism -> morphism -> Maybe morphism dom, cod :: id -> morphism -> object it should have been class (Eq object, Eq morphism) => Category id object morphism | id -> object, id -> morphism ... ^^^^^^ - but ghci 5.02.2 does not complain. Why? Till Mossakowski -- Till Mossakowski Phone +49-421-218-4683 Dept. of Computer Science Fax +49-421-218-3054 University of Bremen till(a)tzi.de P.O.Box 330440, D-28334 Bremen http://www.tzi.de/~till

1 0

Announcement: WASH/CGI 1.0
by Peter Thiemann 25 Apr '02

25 Apr '02

WASH/CGI Web Authoring System for Haskell WASH/CGI is an embedded DSL for server-side Web scripting based on the purely functional programming language Haskell. Its implementation is based on the portable common gateway interface (CGI) supported by virtually all Web servers. WASH/CGI offers a unique and fully-typed approach to Web scripting. It offers the following features * a monadic interface to generating HTML output * type-safe compositional approach to specifying form elements * callback-style programming interface for forms * automatic error detection * complete interactive script in one program * type-safe interfaces to state with different scopes: interaction, persistent client-side (cookie-style), persistent server-side * integration with CSS yields compositional style descriptions * on-the-fly generated graphics * high-level interface to email generation Download WASH-CGI-1.0 from http://www.informatik.uni-freiburg.de/~thiemann/WASH/

1 0

RE: "do" notation and ">>"
by Simon Marlow 24 Apr '02

24 Apr '02

> > I don't believe that it will break many programs. How many programs > > produce large *input independent* output, that is not already > > literally in the source, in a caf with a long life-time? > > That sounds like a description of all the animation programs in Paul > Hudak's School of Expression book and there's plenty more examples > like that. > > [I haven't tested whether these programs do leak space with the > modified compiler - my point is that there is a large class of > programs with exactly the characteristics you describe.] > > -- > Alastair Reid > > ps I think your CAF restriction is a bit of a red herring - Koen's > modification to make his example leak in GHC (which GCs CAFs) shows > that the leak happens as long as the relevant thunk isn't collected. This whole discussion is a red herring. The Haskell report doesn't say anything about sharing - it doesn't even mandate laziness (look in the index - you won't find the term "lazy" :-). Different compilers will behave differently, GHC in particular will probably share <expr2> in Koen's example f = do <expr1> <expr2> regardless of whether the translation uses >> or >>=, because GHC implements full laziness (when -O is turned on). So you might reasonably argue that Haskell should provide more control over such things, and I might well agree. But there's no point in discussing whether using >>= or >> in the translation of do-notation is better: they're both equivalent as far as the current language specification is concerned. Cheers, Simon

2 1