January 2003 - Haskell

WFLP'03 - First Call for Papers
by German Vidal 27 Jan '03

27 Jan '03

====================================================================== PRELIMINARY CALL FOR PAPERS WFLP 2003 12th Int'l Workshop on Functional and (Constraint) Logic Programming June 12-13, 2003, Valencia (Spain) http://www.dsic.upv.es/~rdp03/wflp/ ====================================================================== WFLP is the International Workshop on Functional and (Constraint) Logic Programming. WFLP'03, the twelfth in the series, will be held in Valencia, Spain, June 12-13, 2003, at the Federated Conference on Rewriting, Deduction and Programming (RDP'03) http://www.dsic.upv.es/~rdp03/ The WFLP workshops aim at bringing together researchers interested in functional programming, (constraint) logic programming, as well as their integration. It promotes the cross-fertilizing exchange of ideas and experiences among researches and students from the different communities interested in the foundations, applications, and combina- tions of high-level, declarative programming languages and related areas.The technical program of the workshop will include invited talks, presentations of refereed papers and demo presentations. Previous editions of the workshop have been held in Grado (Italy), Kiel (Germany), Benicassim (Spain), Grenoble (France), Bad Honnef (Germany), Schwarzenberg (Germany), Marburg (Germany), Rattenberg (Germany), and Karlsruhe (Germany). ---------------------------------------------------------------------- TOPICS OF INTEREST WFLP'03 solicits papers in all areas of functional and (constraint) logic programming, including (but not limited to): * Language Design: modules and type systems, multi-paradigm languages, concurrency and distribution, objects * Foundations: formal semantics, rewriting and narrowing, nonmonotonic reasoning, dynamics, type theory * Implementation: abstract machines, parallelism, compile-time and run-time optimizations, interfacing with external languages * Transformation and Analysis: abstract interpretation, specialization, partial evaluation, program transformation, meta-programming * Software Engineering: design patterns, specification, verification and validation, debugging, test generation * Applications: declarative programming in education and industry, domain-specific languages, visual/graphical user interfaces,embedded systems, WWW applications, knowledge representation and machine learning, deductive databases, advanced programming environments and tools The main focus is on new and original research results but submissions describing innovative products, prototypes under development or interesting experiments (e.g., benchmarks) are also encouraged. ---------------------------------------------------------------------- IMPORTANT DATES Submission of papers: Sunday, March 23, 2003 Notification of acceptance: Friday, April 25, 2003 Camera-ready papers: Sunday, May 11, 2003 Workshop: June 12 - 13, 2003 ---------------------------------------------------------------------- SUBMISSION Authors are invited to submit an extended abstract (no longer than 12 pages including figures and references) or a system description (no longer than 4 pages) in Postscript or PDF format (Springer LNCS style) via email to gvidal(a)dsic.upv.es before March 23, 2003. Submissions should include the title, authors' names, affiliations, addresses, and e-mail. ---------------------------------------------------------------------- PUBLICATION Accepted papers will be included in the preliminary proceedings that will be available at the workshop. A selection of the accepted papers will be considered for publication in the Electronic Notes in Theoretical Computer Science (Elsevier) after the workshop. ---------------------------------------------------------------------- BEST NEWCOMER AWARD An award will be given to the best paper exclusively written by one or several young researchers who have not yet obtained their PhD degrees. Papers written in this category should be clearly marked "Student papers" in the submission. ---------------------------------------------------------------------- PROGRAM COMMITTEE Maria Alpuente (Technical University of Valencia, Spain) Sergio Antoy (Portland State University, USA) Annalisa Bossi (Universita Ca' Foscari di Venezia, Italy) Olaf Chitil (University of York, UK) Rachid Echahed (Institut IMAG, France) Sandro Etalle (University of Twente, The Netherlands) Moreno Falaschi (Universita di Udine, Italy) Michael Hanus (CAU Kiel, Germany) Herbert Kuchen (University of Muenster, Germany) Michael Leuschel (University of Southampton, UK) Juan Jose Moreno-Navarro (Universidad Politecnica de Madrid, Spain) Ernesto Pimentel (University of Malaga, Spain) Mario Rodriguez-Artalejo (Universidad Complutense de Madrid, Spain) Yukiyoshi Kameyama (University of Tsukuba, Japan) German Vidal (Technical University of Valencia, Spain) ---------------------------------------------------------------------- LOCAL ORGANIZING COMMITTEE Elvira Albert Santiago Escobar Cesar Ferri Jose Hernandez Carlos Herrero Pascual Julian Marisa Llorens Gines Moreno Javier Oliver German Vidal Alicia Villanueva ---------------------------------------------------------------------- FURTHER INFORMATION WFLP 2003: http://www.dsic.upv.es/~rdp03/wflp Workshop contact: gvidal(a)dsic.upv.es RDP 2003: http://www.dsic.upv.es/~rdp03

1 0

Re: seeking ideas for short lecture on type classes
by Norman Ramsey 27 Jan '03

27 Jan '03

Now that I have made it abundantly clear that my understanding of type classes is highly imperfect, perhaps I will repeat my plea: * Can you recommend any interesting, elementary examples? * Of all the many articles on the topic, which few might you recommend for beginners? Would Faxen's static semantics be a good place to start? Jones's `Typing Haskell in Haskell'? One of Phil Wadler's papers (which one)? Thanks again for any help, Norman

2 1

existential typing question
by Dean Herington 27 Jan '03

27 Jan '03

Can someone explain why the type declaration for `g` is required in the following? class RT r t where rt :: r -> t data D t = Dt t | forall r. RT r t => Dr r f :: D t -> D t f = g where -- g :: D t -> D t g (Dr r) = Dt (rt r) As given above, the program evokes these error messages: with GHC 5.04.2: Bug4.hs:10: Could not deduce (RT r t1) from the context (RT r t) Probable fix: Add (RT r t1) to the existential context of a data constructor arising from use of `rt' at Bug4.hs:10 In the first argument of `Dt', namely `(rt r)' In the definition of `g': Dt (rt r) with Hugs: ERROR "Bug4.hs":6 - Cannot justify constraints in explicitly typed binding *** Expression : f *** Type : D a -> D a *** Given context : () *** Constraints : RT _6 a -- Dean

2 2

seeking ideas for short lecture on type classes
by nr＠eecs.harvard.edu 27 Jan '03

27 Jan '03

In a fit of madness, I have agreed to deliver a 50-minute lecture on type classes to an audience of undergraduate students. These students will have seen some simple typing rules for F2 and will have some exposure to Hindley-Milner type inference in the context of ML. I am soliciting advice about * Cool examples of type classes * Papers I could read to explain how to implement type classes, especially if I could show the `dictionary translation' which is then followed by ordinary Hindley-Milner type inference * Any other material on which I might base such a lecture I'm especially in need of a guide to the literature, as the `Haskell bookshelf' at haskell.org is silent on the topic of type classes. Please send me your recommendations. Norman Ramsey

5 5

Lazy evaluation alternative
by Chris Clearwater 26 Jan '03

26 Jan '03

I wonder if I could run an idea I've had by this list. It seems to me you could get some of the desired effects of lazy evaluation by using continuation passing style in code. For example, take this psuedo-code using CPS to represent an infinite data type. Using non-CPS this would be something like: ones = 1 : ones using strict evaluation this would lead to an infinite loop. However using CPS this could be represented as: ones c = c (1 : ones) where c is the continuation. This would not infinite loops as ones is still waiting for the continuation argument. Another example: natural n c = c (n : natural n+1) Again no infinite recursion! What do you think? Please CC me in any reply.

3 2

hot queue implementation
by Hal Daume III 24 Jan '03

24 Jan '03

Does anyone have an implementation of hot (heap on top) priority queues in Haskell (or perhaps ML)? Thanks! - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

1 0

Last Call for Papers: Deadline February 7
by SAS 2003 24 Jan '03

24 Jan '03

---------------------------------------------------------------------- Call for Papers SAS '03 10th Annual International Static Analysis Symposium June 11-13, 2003 : San Diego, California http://www.lix.polytechnique.fr/~radhia/sas03/index.html ACM Federated Computing Research Conference FCRC 2003 http://www.acm.org/sigs/conferences/fcrc/ ---------------------------------------------------------------------- Static Analysis is increasingly recognized as a fundamental tool for high performance implementations and verification systems of programming languages. The series of Static Analysis Symposia has served as the primary venue for presentation of theoretical, practical, and application advances in the area. The 10th International Static Analysis Symposium SAS'03 will be held at the Town and Country Resort & Conference Center in San Diego (USA) as part of the Federated Computing Research Conference FCRC 2003. Previous symposia were held in Madrid, Paris, Santa Barbara, Venice, Pisa, Paris, Aachen, Glasgow and Namur. The technical program for SAS'03 will consist of invited lectures, tutorials, panels, presentations of refereed papers, and software demonstrations. Contributions are welcome on all aspects of Static Analysis, including, but not limited to: abstract interpretation, data flow analysis, verification systems, program transformation, abstract domains, optimizing compilers, theoretical frameworks, type inference, abstract model checking, complexity analysis, abstract testing, security analysis, mobile code, hardware systems, distributed systems, embedded systems. Submissions can address any programming paradigm, including concurrent, constraint, functional, imperative, logic and object-oriented programming. Survey papers that present some aspect of the above topics with a new coherence are also welcome. Papers must describe original work, be written and presented in English, and must not substantially overlap with papers that have been published or that are simultaneously submitted to a journal or a conference with refereed proceedings. Submission instructions: All submissions must be performed electronically at http://www.lix.polytechnique.fr/~radhia/sas03/submission.html. Submitted papers should be at most 15 pages excluding bibliography and well-marked appendices. Program committee members are not required to read the appendices, and thus papers should be intelligible without them. Publication: The proceedings will be published by Springer in the Lecture Notes in Computer Science series (see http://www.springer.de/comp/lncs/authors.html for the LNCS Author's Instructions). Thus, adhering to that style already in the submission is strongly encouraged. Papers should be submitted either in PostScript or PDF format and they should be interpretable by Ghostscript or Acrobat Reader. Papers must be printable on either A4 paper or US letter, and preferably on both. Selected papers will be published in a special issue of a journal. Important dates: Deadline for submissions : February 7, 2003. Notification : March 18, 2003. Deadline for reception of the final versions : March 30, 2003. The conference : June 11-13, 2003. Program Committee: Radhia Cousot (Chair) CNRS and Ecole polytechnique, France Alex Aiken University of California, Berkeley, USA Luddy Harrison Intel Corporation, USA Susan Horwitz University of Wisconsin-Madison, USA Andy King University of Kent, UK Giorgio Levi University of Pisa, Italy Michael Lowry NASA Ames Research Center, USA Laurent Mauborgne Ecole normale superieure, France Alan Mycroft Cambridge University, UK Germ�n Puebla Technical University of Madrid, Spain Francesco Ranzato University of Padova, Italy Shmuel Sagiv Tel-Aviv University, Israel David Sands Chalmers U. and U. of Goteborg, Sweden Helmut Seidl University of Trier, Germany Mary Lou Soffa University of Pittsburgh, USA Harald S�ndergaard University of Melbourne, Australia Contact info: sas03(a)lix.polytechnique.fr

1 0

Re: Lazy evaluation alternative
by Kevin S. Millikin 24 Jan '03

24 Jan '03

>>>>> "Chris" == Chris Clearwater <chris(a)sharkzone.com> writes: Chris> LIAR. You want to steal my idea for yourself! It's MINE! :) I hate to be the one to break it to you, but we used to routinely show this trick to Intro to CS students. Chris> But anyways, it was to show that when a list is defined Chris> like that, (natural m) becomes a list itself because it is Chris> of the form: \c -> c hd tl after partial evaluation. Yes. But it's not the CPS that delays evaluation, it's just the lambda. Switching to a strict language, Scheme, one would write: > (define ones (lambda () (cons 1 ones))) Explicitly delaying the evaluation of (cons 1 ones) by putting it under a lambda. We *could* perform the CPS translation, but it's not necessary to delay evaluation, lambda does that all by itself. > ones #<procedure> > (ones) (1 . #<procedure>) > (cdr (ones)) #<procedure> > ((cdr (ones))) (1 . #<procedure>) Of course, if we wanted *lazy* evaluation, we would want to avoid performing the cons more than once if it is demanded more than once. We have to use something other than lambda for that: > (define ones (delay (begin (printf "forcing...~n") (cons 1 ones)))) > ones #<procedure> > (force ones) forcing... (1 . #<procedure>) > (force ones) (1 . #<procedure>) > (cdr (force ones)) #<procedure> > (force (cdr (force ones))) (1 . #<procedure>) Notice how many times (cons 1 ones) got evaluated. So your trick *is* used to implement lazy evaluation in other languages. It's not very pleasant if you write a lot of lazy code, because you have to explicitly suspend evaluation of values using delay and explicitly demand evaluation using force. Thus, we have lazy languages that make the laziness implicit. -- Kevin S. Millikin Architecture Technology Corporation Research Scientist Specialists in Computer Architecture (952)829-5864 x. 162 http://www.atcorp.com

3 2

Re: Lazy evaluation alternative
by Chris Clearwater 24 Jan '03

24 Jan '03

On Fri, Jan 24, 2003 at 03:07:48PM +0100, Thomas Johnsson wrote: > > > > > Yes I am. But the + should be in CPS form anyways to be perfectly > > correct, so: natural n c = (+) n 1 (\m -> c n : (natural m)) > > > > I think Jerzy (in his usual polite manner :-) refers to the every group has it's moshez (don't ask :) > cons operator, the :, which in a strongly typed language > the right argument, the tail, is required to be a list. > The function is declared as natural n c = ..., > so (natural m) must be a funcion. Well, let's pretend I made my own datatype then that supports the right type class interfaces, and has a function as a tail :) But also, this brings me to another idea! Data structures should be built from lambdas and CPS! For example, a list of integers: 1 : 2 : 3 list = \c -> c 1 (\c -> c 2 nil) now: natural n c = c n (natural n+1) full blown CPS: natural n c = (+) n 1 (\m -> c n (natural m)) so, here (nautral m) _is_ a list just like the above list! > Might I guess that you come from the lisp / scheme world? No. :) > > Regards, > -- Thomas > >

3 2

Lazy evaluation alternative
by Chris Clearwater 24 Jan '03

24 Jan '03

I wonder if I could run an idea I've had by this list. It seems to me you could get some of the desired effects of lazy evaluation by using continuation passing style in code. For example, take this psuedo-code using CPS to represent an infinite data type. Using non-CPS this would be something like: ones = 1 : ones using strict evaluation this would lead to an infinite loop. However using CPS this could be represented as: ones c = c (1 : ones) where c is the continuation. This would not infinite loop as ones is still waiting for the continuation argument. Another example: natural n c = c (n : natural n+1) Again no infinite recursion! What do you think? Please CC me in any reply.

2 2