Lambda the Ultimate The Programming Languages Weblog - join today!

Home

FAQ

Feedback

Departments

Discussions

(new topic)

Language Evaluation

PL Courses

Research Papers

Design Docs

Quotations

Genealogical Diagrams

Members Join Now Login

functional

AFP 2004
The 5th International Summer School on Advanced Functional Programming will be in Tartu Estonia (August 14-21). The program doesn't look very exciting, but I thought y'all might want to take a look anyway. Given the discussions going on, the lecture on Clean "Dynamics" may be of interest... Posted to functional by Ehud Lamm on 5/24/04; 8:19:13 AM Discuss (4 responses)

Moiell (aka Leoll++)
Sjoerd managed to get his favorite toy language to understand this code: sieve: [|p::ns| >p, sieve( ns[me mod p != 0] ) ] There's nothing better than some lazy functional programming to brighten up your morning... Posted to functional by Ehud Lamm on 5/13/04; 3:42:02 AM Discuss

Calculating the Sieve of Eratosthenes
There is a well-known "folklore" functional program for the Sieve of Eratosthenes. I presented a calculational derivation, based on the universal property of streams. Nice slides by Lambert Meertens. Posted to functional by Ehud Lamm on 4/19/04; 5:16:56 AM Discuss (2 responses)

Gibbons: Metamorphisms and streaming algorithms

Unfolds generate data structures,and folds consume them. A hylomorphism is a fold after an unfold,generating then consuming a virtual data structure. A metamorphism is the opposite composition,an unfold after a fold; typically,it will convert from one data representation to another. In general, metamorphisms are less interesting than hylomorphisms: there is no automatic fusion to deforest the intermediate virtual data structure. However, under certain conditions fusion is possible: some of the work of the unfold can be done before all of the work of the fold is complete. This permits streaming metamorphisms, and among other things allows conversion of infinite data representations. We present the theory of metamorphisms and outline some examples. The paper presents some nice examples (reformatting lines, radix conversion and continued fractions). Closely related to other recent papers by Gibbons that were mentioned here before, but natrually the discussion of metamorphisms here is more focused and detailed. Posted to functional by Ehud Lamm on 3/16/04; 7:39:43 AM Discuss

Book Review: Purely Functional Data Structures

Since Ehud needs a bit lighter material to shade himself through the day, what better than a slashdot discussion to fill that hole. The book reviewed is Purely Functional Data Structures by Chris Okasaki. Was first mentioned sometime ago on LtU. (Of course, book reviews are somewhat like movie reviews - if you haven't seen the movie, it's hard to discuss - and if you have seen the movie you already know the ending). Posted to functional by Chris Rathman on 3/3/04; 10:28:03 AM Discuss (8 responses)

Polymorphic Variants

We have demonstrated here how polymorphic variants allow one to combine the benefits of algebraic datatypes [...] with code re-use at a level of simplicity comparable with OO languages. The added expressive power is significant: encoding in either traditional variants or OO style would incur problems ranging from [...] The idea is that you don't define the combination of constructors A|B as some particular type, but instead deal directly with collections of constructors as required. It's then easy to add a bunch of extra constructors later. I read this paper last night (from here) and was impressed. It seems to be simple and neat, makes variants (sum types - the ones with "|"s in the syntax) a little more general, looks like it might help out when you're maintaining old code and need to get two systems working together, and suggests (to my uneducated eyes at least) a different approach to ad-hoc polymorphism (if functions can be defined multiple times, as in Haskell, with pattern matching to the left of "="). Unfortunately, it does make code more verbose. (And it's implemented in recent versions of OCaml) Posted to functional by andrew cooke on 2/28/04; 5:00:37 AM Discuss (2 responses)

Monads in Scheme

Much of the monadic programming literature gets the types right but the abstraction wrong. Using monadic parsing as the motivating example, we demonstrate standard monadic programs in Scheme, recognize how they violate abstraction boundaries, and recover clean abstraction crossings through monadic reflection. Looks interesting (haven't read it yet as I'm at work, but this place needs a link ;o) It's not this, and comes from here. Posted to functional by andrew cooke on 2/25/04; 2:26:03 PM Discuss (4 responses)

Python 'for' as Scheme 'let'

We show that the 'for' operator of Python quite unexpectedly can be represented by a 'let' form of Scheme. Another cool example from Oleg. This time, not only a nice example of Scheme macros, but of shift/reset operators as well. Allow me to draw the following diagram: list-comprehensions === monads === shift/reset === range The first two are truly equivalences: in Haskell, a list comprehension is just another form of the 'do' notation in the case of a List monad. Filinski showed that shift/reset can be used to implement monads in the general way. My 'range' is based on shift-and-reset. There is a difference however. If we avoid nested loops, then my shift/reset (called bshift/breset) are the same as shift/reset. Alas, regular shift/reset cannot nest. There are multi-level shift/reset, but they are difficult to use -- and hard to encapsulate in a macro such as 'range' because the macro needs to know on which level it operates. My bshift/breset are different. bshift/breset with different labels are unaware of each other. BTW, other control operators, e.g., those by Matthias Felleisen, do not have the indifference property. The operator 'cupto' has -- but to some extent. Several cupto operators have to be used in a stack-wise fashion. Mines don't have to. Posted to functional by Ehud Lamm on 2/23/04; 1:35:53 AM Discuss (2 responses)

OCaml, an Introduction

An introduction to OCaml in the latest issue of Linux Gazette. Object Caml is an ML type of language. For the non-gurus: it's a functional language that can also be programmed in a non-functional and object-oriented way. This language is really easy to learn. It's powerful and keeps impressing me with its speed. Programs written in this language are almost always stable by default. No segmentation faults, only occasional unending loops for the programmers that still hang on to program their own loops. It is really not needed to write most loops, since the libraries contain standard functions that are good enough in 99% of the cases. So try to use those functions: It really pays off in terms of stability of your programs, and, unless you have intimate knowledge of the inner works of this language, they tend to be better optimised. Posted to functional by Patrick Logan on 2/10/04; 11:14:48 AM Discuss (7 responses)

Algorithmic complexity of evaluation: lazy, eager, pure and impure

This is a pointer to an item in the discussion list from Jim Apple. This links to papers showing that lazy evaluation is sometime strictly faster than eager evaluation without assignment, and this shows that eager evaluation with assignment is sometimes strictly faster than eager evaluation without assignment. Are there any languages out there without lazy evaluation and without assignment? Posted to functional by Patrick Logan on 1/21/04; 8:41:53 AM Discuss (2 responses)

What is a Purely Functional Language?

Sabry, A. What is a purely functional language? Journal of Functional Programming (1997). We begin by showing that some proposed definitions that rely on confluence, soundness of the beta axiom, preservation of pure observational equivalences, and independence of the order of evaluation, do not withstand close scrutiny. We propose instead a definition based on parameter-passing independence. It's damn hard to give useful definition of referential transparency. This paper tries to eliminate the need for this by giving a different perspective on purity. Posted to functional by Ehud Lamm on 1/19/04; 3:08:13 AM Discuss

Continuations (and call/cc) in Haskell
Why does Haskell have no continuations? ... If continuations are incompatible with non-strict semantics, I'd appreciate an explanation. A nice thread on the Haskell mailing list. Posted to functional by Ehud Lamm on 1/3/04; 4:04:15 AM Discuss (4 responses)

Short Cut Fusion is Correct

Short Cut Fusion is Correct. Patricia Johann. Journal of Functional Programming, vol. 13(4) (2003), pp. 797 - 814. Short cut fusion has traditionally been treated purely syntactically, with little consideration given to the underlying semantics of the programs to which it is applied. In particular, the fact that the foldr-build rule holds only for languages admitting parametric models has been downplayed in the literature, and the application of short cut fusion to functional programs has been justified by appealing either to intuition about the operational behavior of build and foldr or to Wadler's "free theorems" (Wadler, 1989). But intuition is unsuitable as a basis for formal proofs, and the correctness of "free theorems" itself relies on the existence of parametric models. Since no parametric models for modern functional languages are known to exist, these justifications of short cut fusion for them are far from satisfactory. In this paper we provide the first-ever formal proof of the correctness of short cut fusion for a calculus supporting both higher-order polymorphic functions and fixpoint recursion. Interesting and important. Posted to functional by Ehud Lamm on 12/22/03; 11:07:58 PM Discuss (1 response)

Lambda Calculus
Shows how to reduce a subset of Scheme to LC. If you know a little Lisp/Scheme, and ever wondered what (lambda (x) (x x)) might be good for, this is for you. From Shiram Krishnamurti's lecture notes Posted to functional by Manuel Simoni on 11/27/03; 9:03:48 AM Discuss (2 responses)

Why Functional Programming Matters

by John Hughes (1984) As software becomes more and more complex, it is more and more important to structure it well. Well-structured software is easy to write, easy to debug, and provides a collection of modules that can be re-used to reduce future programming costs. Conventional languages place conceptual limits on the way problems can be modularised. Functional languages push those limits back. In this paper we show that two features of functional languages in particular, higher-order functions and lazy evaluation, can contribute greatly to modularity. This is a great paper because it's easy to read and it shows you why functional programming matters. It does this in the best of ways: by presenting beautiful programs. It's by far the best demonstration of lazy evaluation that I've found. (I was really surprised to find that this paper hasn't been featured here before, though it has been linked several times.) Posted to functional by Luke Gorrie on 11/27/03; 5:05:02 AM Discuss (9 responses)

An Unbounded Spigot Algorithm for the Digits of Pi

Jeremy Gibbons (2003). An Unbounded Spigot Algorithm for the Digits of Pi. Rabinowitz and Wagon (American Mathematical Monthly 102(3):195--203, 1995) present a spigot algorithm for computing the digits of Pi. A spigot algorithm yields its outputs incrementally, and does not reuse them after producing them. Their algorithm is inherently bounded; it requires a commitment in advance to the number of digits to be computed, and in fact might still produce an incorrect last few digits. We propose two streaming algorithms based on the same characterization of Pi, with the same incremental characteristics but without requiring the prior bound. Working with infinite seriers is always fun, and in a lazy language it's also quite easy. As you'd expect, this paper uses Haskell. Slightly more practical than the classic Hamming numbers example. Posted to functional by Ehud Lamm on 11/20/03; 4:07:05 AM Discuss

Vital: A Visual Interactive Typed Applicative Language

(via the Haskell mailing list) Vital is a visual programming environment based on Haskell, a contemporary functional programming language. It is particularly intended for supporting the open-ended, incremental style of development often preferred by end users (engineers, scientists, analysts, etc.). It may also be useful for teaching Haskell. I haven't installed this but the screenshots on the site look interesting. However, I was dissapointed to see the the dialect of Haskell used, called Hask, is severeley limited. The most notable missing features are types and type classes and monadic I/O operations. Posted to functional by Ehud Lamm on 11/12/03; 1:16:48 PM Discuss (1 response)

You call that a Monad? This HERE's a Monad.... And a Shell.

Arjen van Weelden and Rinus Plasmeijer. A Functional Shell that Dynamically Combines Compiled Code. Currently under review by the 15th International Workshop on the Implementation of Functional Languages, IFL 2003, Scotland, September 10-13, 2003. pdf. Now that the word Monad has appeared on a Microsoft-generated product, this must mean the world is at last ready for this concept. Not surprisingly, this work has already been done in a more innovative way by our friends at Nijmegen University (among others, such as the Scheme Shell, etc.). This paper describes Esther, a functional shell built in Clean that allows the functionally-literate system administrator to build scripts that interact with the operating system using higher-order-functions, folds, etc. The concept is being extended to an operating system called Hilde. Posted to functional by Brent Fulgham on 11/11/03; 11:36:22 AM Discuss (3 responses)

Conceptual Integrity in Erlang

Fred Brooks said that conceptual integrity was paramount in system design. Niklaus Wirth said that if we add things to a language we should throw away other things. Here is a proposal for a few small additons to Erlang. If we accept these proposals - we can throw away a lot of things and make Erlang even more powerful. Posted to functional by Patrick Logan on 10/24/03; 6:31:57 AM Discuss (25 responses)

State and modularity

(This was originally discussed on the Yahoo pragprog list; I think it's important enough to present it on LtU as well.) In our experience, true state (destructively assignable entities) is essential for reasons of program modularity (which for this discussion I take as meaning: the ability to change one part of a program in a significant way without changing the rest of the program). Threaded state, e.g., monads as used by Haskell or DCGs as used by Prolog, cannot substitute for it. Here is a simple example to show the difference between true state and threaded state. Consider a system consisting of modules A, B, C, D, and E, all written in a purely functional way. Module A calls B, which calls C, which calls D, which calls E. Now let's say I want to instrument E, to count how many times it is performing some operation, and I want to observe this from A. If I want to program this in a purely functional way (e.g., in the pure subset of Haskell), then I am obliged to change the interfaces of all the modules A, B, C, D, and E (*). If I have true state, then I can get by with changes in just A and E. In other words, instead of changing everything on the path, I can get by with changing things on the ends. This is a major difference that has all kinds of software engineering ramifications. Here's how it works. (See CTM for more information: section 4.7.2 in the June 5 draft or section 4.8.2 in a later draft explains the idea with a similar example.) The new module E has two interfaces, IE1 and IE2. IE1 is the original interface (purely declarative) and is used as before. IE2 is a new interface with two operations: InitCounter which initializes the internal E counter to zero and GetCounter which returns the value of the internal E counter. (The E counter is of course incremented when we call IE1.) Then all we have to do is pass an IE2 reference to module A, which can then do what it likes with the counter. Modules B, C, and D see nothing at all. You can only do this if you have true state. Here is one way of seeing why. True state lets information pass "underground" between two interfaces, i.e., the information passes without any apparent connection between them. This is because the connection is the shared state, which is shared by the two interfaces yet hidden from the outside. The shared state is a kind of covert information channel: it lets a module pass information to other modules (or to itself in the future) without anybody else seeing it. There is a final point regarding static typing. The usual static type systems, such as Haskell's, do not support this technique. The question is, how can type systems be extended to support this technique? I am not an expert on type systems, but I leave this question open for you. One hint may be given by the preceeding paragraph: maybe the covert information channel should be typed. ------------------------- (*) You may counter that using monads can solve this problem in Haskell. I.e., just write all your modules in a monadic way from the start. Then there are three possibilities: Either you do it explicitly, in which case your whole program becomes more complicated, even those parts that have nothing to do with the instrumentation. For example, what happens if there are also modules A', B', C', and D', where A' calls B', etc., and D' calls E? They all have to carry around the instrumentation counter. Or you decide to hide the monadic operations from the programmer and let the compiler add them. In which case you have just implemented a stateful language on top of Haskell. Or you can use unsafePerformIO. In which case you are using true state. And I have not yet mentioned the real issue, which is declarative concurrency. Two concurrent activities execute independently. If you impose a state threading using monads, then they are no longer independent because you have to impose an order. This may seem bearable in a sequential system (such as the pure subset of Haskell) but it is simply not possible in a concurrent system (such as the declarative concurrent subset of Oz, which is pure and yet concurrent). Posted to functional by Peter Van Roy on 10/22/03; 3:04:50 AM Discuss (20 responses)

Erik Meijer: Visual Basic Programmers Love Anamorphisms

(via Kory Markevich in the discussion group) Pure functional programmers, your days are numbered. The grim reaper is knocking at your door. LtU readers will want to read this. Like Kory, I am not sure how much of this is tongue in cheek. But one thing I am sure of is that functional programmers we'll understand Erik's weblog post much more easily than VB users (no, they are not programmers, of course). Posted to functional by Ehud Lamm on 10/20/03; 12:33:30 PM Discuss (17 responses)

Advanced Functional Programming wiki @ Harvard

I must say that I am slightly disappointed with those LtU regulars (and even editors!) affiliated with this Harvard course, for not letting us know of this nice resource. The wiki belongs to the CS 252r AFP seminar, given by Norman Ramsey and includes such things as a reading list, potential programming problems and more. Posted to functional by Ehud Lamm on 10/19/03; 12:34:44 PM Discuss (1 response)

Alice

Alice is a functional programming language based on Standard ML, extended with support for concurrent, distributed, and constraint programming. Alice builds on our experience with developing the Mozart system. The current version of Alice is based on the Mozart virtual machine. Alice programs can therefore interoperate with Oz. I found the tour, especially the section on distribution, very interesting. Posted to functional by Manuel Simoni on 10/10/03; 4:13:33 AM Discuss (18 responses)

HaRe -- The Haskell Refactorer

[W]e are pleased to announce the availability of HaRe 0.1... a snapshot of our Haskell Refactorer prototype. This is an artefact of the Refactoring Functional Programs project (see previous LtU discussion).Also related to our never ending tool/IDE fetish... Take a look at the screen shots to get a feel for the (still somewhat limited) capabilities. Looks real nice! Posted to functional by Ehud Lamm on 10/2/03; 4:18:25 AM Discuss (1 response)

JScript is a Functional Language

Eric Lippert, a Microsoft developer that has worked on VBScript and JScript, explains that JScript (JavaScript) is a functional language with first-class functions, lambdas and closures. One of his eariler posts contains this gem: The august Waldemar Horwat -- who was at one time the lead Javascript developer at AOL-Time-Warner-Netscape -- once told me that he considered Javascript to be just another syntax for Common Lisp. I'm pretty sure he was being serious. Posted to functional by Dejan Jelovic on 9/18/03; 9:58:04 AM Discuss (26 responses)

Whither Self
And an Erlang language design discussion. Shouldn't there be a Self in funs? ... writing Fac = fun(0) -> 1; (N) -> N*Self(N-1) end I always make sure to follow the discussions Richard A. O'Keefe participates in. Luke, I thought erlang was your beat... Posted to functional by Ehud Lamm on 9/12/03; 8:03:26 AM Discuss (16 responses)

Future of Haskell discussion @ Haskell Workshop

This year's Haskell Workshop, held in Uppsala as a part of PLI, traditionally concluded with a discussion on the future of Haskell. This time an attempt was made to structure the discussion a little bit by focusing on two specific topics, and by having each topic being introduced by a short presentation. The first topic was Haskell records, introduced by Simon Peyton Jones, Microsoft Research, Cambridge, UK. The second topic was GUI libraries for Haskell, introduced by Axel Simon, the University of Kent, UK. An interesting thread on the Haskell mailing list. An example both of language design and of language community. Posted to functional by Ehud Lamm on 9/12/03; 7:51:57 AM Discuss (2 responses)

Functional Pearl: A fresh look at binary search trees

Ralf Hinze. Functional Pearl: A fresh look at binary search trees. Insertion into a BST is a simple, succinct, operation. Deletion is much harder. Why? Our own stab at explaining this phenomenon is algebraic or, if you like, linguistic. Arguably, the data type Tree with its two constructors, Leaf and Node, does not constitute a particularly elegant algebra. Nice example of the algebraic-stance, as well as of the power of abstraction. The paper also has a simple example of views, that readers may find useful. Posted to functional by Ehud Lamm on 9/10/03; 5:56:08 AM Discuss

Codata and Comonads in Haskell

Codata and Comonads in Haskell. Richard B. Kieburtz This paper suggests that a useful interpretation of comonads in programming is that they account for effects originating in the context of a program fragment, effects to which the program fragment may react and which it may further propagate. I cam across this paper browsing the Haskell Wiki, and it looks pretty interesting. I am not sure I fully grasp the utility of comonads, but maybe someone more knowledgeable will care to comment. Editors, we need to post some non-FP links quickly! Posted to functional by Ehud Lamm on 8/13/03; 5:32:35 AM Discuss (2 responses)

All About Monads

This tutorial aims to explain the concept of a monad and its application to functional programming in a way that is easy to understand and useful to beginning and intermediate Haskell programmers. Familiarity with the Haskell language is assumed, but no prior experience with monads is required. The tutorial covers a lot of material and the later sections require a thorough understanding of the earlier material. Many code examples are provided along the way to demonstrate monadic programming. It is not advisable to attempt to absorb all of the material in a single reading. Quite an extensive tutorial, that even covers things like monad transformers. Includes a large catalog of standard monads. I won't venture an opinion since I just read a tutorial about monads written by one of my students, and naturally I am a bit biased... Posted to functional by Ehud Lamm on 8/12/03; 2:06:16 PM Discuss (9 responses)

Calculating Functional Programs: maximum segment sum

Jeremy Gibbons. Calculating Functional Programs. In Proceedings of ISRG/SERG Research Colloquium, School of Computing and Mathematical Sciences, Oxford Brookes University, November 1997. A good way of developing a correct program is to calculate it from its specification. Functional programming languages are especially suitable for this, because their referential transparency greatly helps calculation. We discuss the ideas behind program calculation, and illustrate with an example (the maximum segment sum problem). We show that calculations are driven by promotion, and that promotion properties arise from universal properties of the data types involved. Everone should be familiar with Jon Bentley's Programming Pearl in which he discusses the design of a linear time algorithm for solving this problem (he calls it the maximun consecutive subsequence, if I am not mistaken. Try to guess why Gibbons calls it maximum segment sum...) A very short and elegant example. Posted to functional by Ehud Lamm on 8/11/03; 3:46:15 AM Discuss (7 responses)

Adaptation in HOT Languages

From Dave McQueen of the SML-NJ team with an accompanying Powerpoint presentation. What with Higher Order Type Systems being a "hot" topic of discussion and me being in the middle of working thru The Little MLer, this paper caught my eye. The paper describes the similarity and differences between FP and OOP languages, without getting too bogged down. A good exposition on FP for those that come from an OO background (such as myself). From the point of view of FP, what does OO have to offer? There is the clear utility of subtyping. There is state encapsulization (which can be provided by function closures or modules in ML). There is implementation inheritance, which we have argued is a mixed blessing. And finally there is the clear popular success of OO programming in the real world, which functional programming has not achieved so far. From the OO point of view, FP offers first­class functions as a lighter weight and more general way of binding data and code. It offers true parametric polymorphism (as opposed to macro­like templates), and it offers elegant and concise processing of tree­like data through algebraic data types with pattern matching. It offers clean and powerful module systems that go well beyond the capabilities of namespace management features like packages in Java. Posted to functional by Chris Rathman on 7/18/03; 8:30:21 AM Discuss (5 responses)

Reconciling OO and Haskell-Style Overloading
A powerpoint presentation by Mark Shields & Simon Peyton Jones. Presents the possible directions for Haskell to take in order to cope with OO method name overloading. The idea being that Haskell will inevitably have to be able to talk to OO components within the .Net environment. Posted to functional by Chris Rathman on 7/16/03; 11:24:54 AM Discuss

A Pointless Derivation of Radixsort

I found this paper via the recent discussion about point free style. I found the paper quite enjoyable and interesting so I wanted to point it out to other LtU readers. Aside from discussing how using point free style can help with proofs, this paper is a nice example of program transformation. The author shows how you can prove the correctness of radix sort by mechanically transforming a more intuitive sorting algorithm into an implementation of radix sort. Personally, I find radix sort quite intuitive. Convincing myself that the code for treesort in the paper is correct was slightly harder than grasping and proving why radix sort works, so perhaps in this respect this example isn't ideal for showing the importance of program transformation as a proof technique. Still this is a nice example, well worth playing with if you like Haskell. Notice that the code in appedix B can be useful for playing with the sorting code presented earlier in the paper. Posted to functional by Ehud Lamm on 7/1/03; 6:45:47 AM Discuss

A Foundation for Embedded Languages

Morten Rhiger BRICS, University of Aarhus Recent work on embedding object languages into Haskell use ``phantom types'' (i.e., parameterized types whose parameter does not occur on the right-hand side of the type definition) to ensure that the embedded object-language terms are simply typed. But is it a safe assumption that only simply-typed terms can be represented in Haskell using phantom types? And conversely, can all simply-typed terms be represented in Haskell under the restrictions imposed by phantom types? In this article we investigate the conditions under which these assumptions are true: We show that these questions can be answered affirmatively for an idealized Haskell-like language and discuss to which extent Haskell can be used as a meta-language This seems to be the same paper published in TOPLAS Volume 25, Issue 3 (May 2003). The paper explains how phantom types make it possible to embed not only the (abstract) syntax but also the type system of a monomorphic object language into a statically typed meta-language such as Haskell. The paper discusses the soundness and completeness of such embeddings. Posted to functional by Ehud Lamm on 5/18/03; 5:00:40 AM Discuss

Devils and Angels, via Monads

(on comp.lang.scheme) This note reminisces on a paper by Dan Friedman (with Haynes and Kohlbecker, 1984): "Programming with Continuations". That paper used call/cc and mutable state (via "set!") to describe an "exercise", which they called "devils and angels". This "exercise" has little practical point, per se: it is really the illustration of the combination of state and first-class continuations which was important... This note shows an alternative implementation: in terms of monads: a state monad lifted into a continuation monad... What this note does is to show an implementation, not in terms of the standard implementation of monads, but rather one based on Andrzej Filinski's paper "Representing Monads". That paper shows how a "monadic" program may be written in direct style--i.e. how to add "effects" to an Scheme/ML program without completely transforming that program into the normal monadic style. Shift and reset--delimited continuations-- are used to achieve this. Reflection and monad transformers play an important role in this tour de force. Posted to functional by Ehud Lamm on 5/11/03; 8:44:22 AM Discuss (1 response)

Functional Programming with Apomorphisms / Corecursion

In the mainstream categorical approach to typed (total) functional programming, functions with inductive source types defined by primitive recursion are called paramorphisms; the utility of primitive recursion as a scheme for defining functions in programming is well-known. We draw attention to the dual notion of apomorphisms--functions with coinductive target types defined by primitive corecursion-- and show on examples that primitive corecursion is useful in programming. Apomorphisms were never mentioned on LtU before. This is simply not right... Posted to functional by Ehud Lamm on 5/1/03; 3:30:48 AM Discuss

Haskell Wiki
The Haskell wiki is now at a new location. The new wiki is much more friendly than the old one, so hopefully more people will be inclined to add content. Posted to functional by Ehud Lamm on 4/21/03; 12:16:46 PM Discuss

Implicit Parameters: Dynamic Scoping with Static Types

Implicit Parameters: Dynamic Scoping with Static Types. Jeffrey Lewis, Mark Shields, Erik Meijer, John Launchbury. To appear in the 27th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'00), Boston, Massachusetts, January 19-21, 2000. 11 pages. A nice language design paper. The paper proposes a mechanism for implicit dynamically scope parameters for Haskell. The proposed language construct was implemented in both Hugs and GHC and used, and the paper describes several interesting usage examples. Posted to functional by Ehud Lamm on 4/7/03; 12:21:04 PM Discuss

Functional Images
A nice writeup about the Pan DSEL for creating images, that was mentioned here a few times in the past. This is a chapter from the upcoming The Fun of Programming book, from the symposium in honour of Professor Richard Bird's 60th birthday. Posted to functional by Ehud Lamm on 3/26/03; 1:07:42 PM Discuss (5 responses)

Representing Monads

Andrzej Filinski. Representing monads. In Conference Record of POPL '94: 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Portland, Oregon, pages 446--457 We show that any monad whose unit and extension operations are expressible as purely functional terms can be embedded in a call-by-value language with "composable continuations". Another way of stating this result is to say that any monadic effect whose definition is itself experssible in a functional language can be synthesize from just two "impure" constructs: first-class continutations and a storage cell. Thus languages like Scheme and ML are, in fact, "monadically complete" in the sense that any program expressible in the somewhat contorted monadic style can also be written direct style. This is a rather technical paper, that discusses the connection between monads, CPS, and composable continutations. Posted to functional by Ehud Lamm on 3/24/03; 8:15:46 AM Discuss (1 response)

Selective Memoization

Umut Acar, Guy Blelloch, and Robert Harper. Selective Memoization. ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New Orleans, LA, January, 2003. We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be applied according to the needs of an application. Two key properties of the framework are that it is efficient and yields programs whose performance can be analyzed using standard techniques. We describe the framework in the context of a functional language and an implementation as an SML library. The language is based on a modal type system and allows the programmer to express programs that reveal their true data dependences when executed. The SML implementation cannot support this modal type system statically, but instead employs run-time checks to ensure correct usage of primitives. The authors present a small functional language, called MFL, that supports selective memoization. MFL is equipped with a modality for tracking dependences on data structures within memoized code. The paper proves a soundness theorem stating that memoization does not affect the outcome of a computation compared to a standard, non-memoizing semantics. Section 2, Background and Related Work, is a nice overview of the design pressures in implementing memoization. Posted to functional by Ehud Lamm on 3/14/03; 4:53:46 AM Discuss

Call-by-name is dual to call-by-value

(in the same sense that And is dual to Or) Philip Wadler. New Jersey Programming Language Seminar, 21 February 2003. The rules of classical logic may be formulated in pairs corresponding to DeMorgan duals: rules about And are dual to rules about Or. Church's lambda calculus (1932) provides a computational interpretation for Gentzen's intuitionistic natural deduction (1934), as described by Howard (1980). One might ask, what calculus provides a computational interpretaion for Gentzen's classical sequent calculus (1934)? A sequence of results explore this question, including the work of Filinski (1989), Griffin (1990), Parigot (1992), Barbanera and Berardi (1996), Selinger (2001), and Curien and Herbelin (2000). A startling conclusion of this line of work, not widely appreciated, is that call-by-value is the DeMorgan dual of call-by-name. This paper presents a dual calculus that has a direct connection with the rules for And, Or, Not, and Cut in Gentzen's sequent calculus. and demonstrates the duality in a direct way. The paper unifies and sharpens previous results regarding the translation from a dual calculus into continuation-passing style. Curien and Herbelin (2000) give a soundness result for beta reductions, but do not show completeness and do not treat eta rules. Selinger (2001) gives a soundness and completeness result and treats beta and eta rules, but considers only equations and not reductions. This paper gives a soundness and completeness result for beta and eta reductions. "Not widely appreciated" indeed... I'll try. Posted to functional by Ken Shan on 3/2/03; 6:40:22 PM Discuss (7 responses)

Parallel Functional Programming: An Introduction

K. Hammond. Parallel Functional Programming: An Introduction. PASCO'94, First Intl. Symposium on Parallel Symbolic Computation, Hagenberg/Linz, Austria, 26-28 September. (compressed postrcript) Due to the absence of side-effects in a purely functional program, it is relatively easy to partition programs so that sub-programs can be executed in parallel: any computation which is needed to produce the result of the program may be run as a separate task. There may, however, be implicit control- and data- dependencies between parallel tasks, which will limit parallelism to a greater or lesser extent... The paper contains 97 references selected from the 500 or so publications in this field. In section 2 the paper provides a brief history of the field. Section 3 is perhaps the most interesting and deals with exploiting parallelism (e.g., Serial Combinators,Commutative Monads, Algorithmic Skeletons and Data Parallelism). Posted to functional by Ehud Lamm on 3/1/03; 8:55:23 AM Discuss (1 response)

Notes on "Algebra of Programming"
The "banana-split" law in action. The notes show how this theorem can be used to reason about two algorithms for calculating the average of a list of numbers, and prove their equivalence: A straightforward inefficient solution (sum/len) and more careful implementation that only traverses the list once. Posted to functional by Ehud Lamm on 2/27/03; 12:00:18 PM Discuss

Clean Now Available under LGPL License

Via LTU Discussion They've finally done it -- provided the long-promised release of Clean 2.0 under an LGPL license. I think this is important news because: Clean is a pragmatic implementation of a pure, lazy, functional language (very much like Haskell.) It's seen actual production/industrial use, and reflects the needs of working programmers (i.e., is not soley focused on investigation of language constructs and research.) It's another good example of a company Open Sourcing a key technology to aid in its adoption. Hmmm. Perhaps a Debian package will be forthcoming soon? Posted to functional by Brent Fulgham on 2/26/03; 5:28:40 PM Discuss (1 response)

Clean now available under LGPL license

This isn't exactly "hot off the presses," as the change happened concurrently with the most recent release in December of last year, but it's welcome regardless: the latest release of the Clean functional language is now available under either an LGPL or commercial license, removing the previous non-commercial restriction on the freely-downloadable version. Clean is another in the Haskell/Miranda family of lazy functional languages, but has a number of interesting features: an integrated proof system, full native application support including a standard GUI library under Windows, and support for Dynamics, a framework for serializable, dynamically typechecked expressions. Posted to functional by Lennon Day-Reynolds on 2/26/03; 4:49:53 PM Discuss

Trees with parent "pointers"

The subject of creating cyclical data structures in a functional language has been discussed on LtU before. Now Oleg shows that we can create DAGs and general cyclic data structures even in a strict language! The paradoxical tree is built by a procedure add-thunk-parent-pt, which is defined in section 'Solution 3' of the source code. The procedure is deceptively simple. It took 21 lines of Scheme code to implement the algorithm and 26 (full-length) lines of comments to explain it (see the section about thunked parent pointers). The backlink isn't really a reference, it is a nullary procedure, a thunk, which, when applied, yields the node that is the parent of the current node. Posted to functional by Ehud Lamm on 2/20/03; 12:58:14 AM Discuss

Learning Haskell portal
I don't often link to language specific sites, especially those oriented towards beginners. However, Haskell being the functional language of choice around here I thought it might be appropriate to mention this resource. Posted to functional by Ehud Lamm on 2/16/03; 12:46:03 AM Discuss (1 response)

Paul Graham: Accumulator Generator

The problem: Write a function foo that takes a number n and returns a function that takes a number i, and returns n incremented by i. A comparison between about twenty languages. Paul Graham's Arc and NewtonScript (a selfish and schemish language-OS hybrid for the Apple Newton) seem have the most pragmatic syntaxes. NewtonScript link via Steve Dekorte. Posted to functional by Manuel Simoni on 2/13/03; 6:17:10 AM Discuss (13 responses)

Wearing the hair shirt: a retrospective on Haskell

Simon Peyton Jones Wearing the hair shirt: a retrospective on Haskell. Invited talk at POPL 2003. In this talk, which is very much a personal view, I take a look back at the language, and try to tease out what we have learned from the experience of designing and implementing it. The main areas I discuss are: syntax (briefly), laziness (the hair shirt of the title), type classes, and sexy types. This talk is both an overview of the intellectual history and development of Haskell, and a penetrating look into its essential features (surprise: laziness is less important than you might think). The talk also mentions important areas where research is still needed. Posted to functional by Ehud Lamm on 2/11/03; 2:22:17 AM Discuss (4 responses)

Typed Logical Variables in Haskell

Koen Claessen and Peter Ljunglof. Typed logical variables in Haskell. In Proceedings Haskell Workshop 2000, 2000. Another Prolog in Haskell exercise (a student of mine is working on this topic, so expect more!). The work presented follows the approach suggested by Seres and Spivey (see here and here). The focus of this paper (sec. 4) is on making the embedded language strongly typed. Backtracking is implemented, as usuall, using a monad transformer. Posted to functional by Ehud Lamm on 1/20/03; 7:15:49 AM Discuss

Rewriting as a practical optimisation technique

Playing by the rules: rewriting as a practical optimisation technique in GHC. Simon Peyton Jones, Andrew Tolmach and Tony Hoare; Haskell workshop 2001. We describe a facility for improving optimization of Haskell programs using rewrite rules. Library authors can use rules to express domain-specific optimizations that the compiler cannot discover for itself. The compiler can also generate rules internally to propagate information obtained from automated analyses. The rewrite mechanism is fully implemented in the released Glasgow Haskell Compiler. For some reason this paper wasn't mentioned here before. It is very much worth reading if you are interested in optimizing functional languages. The paper is very readable and contains a few itneresting examples of deforestation. Posted to functional by Ehud Lamm on 1/16/03; 5:44:27 AM Discuss (1 response)

Y in Practical Programs
Bruce McAdam. Y in Practical Programs. Extended abstract presented at FICS 2001 Amazingly this paper wasn't mentioned here before. It's really cute. Posted to functional by Ehud Lamm on 12/30/02; 3:32:43 PM Discuss (5 responses)

Es: A shell with higher-order functions

(via GIGO) While rc was an experiment in adding modern syntax to Bourne shell semantics, es is an exploration of new semantics combined with rc-influenced syntax: es has lexically scoped variables, first-class functions, and an exception mechanism, which are concepts borrowed from modern programming languages such as Scheme and ML. I never heard of anyone using this shell, but it sounds cool. The paper is quite readable and describes many interesting details (including garbage collection and a discussion of the implementation). The es version described in the paper is not properly tail recursive (I am not sure about the current version). Now, a shell that would provide call/cc would be reallly interesting... Posted to functional by Ehud Lamm on 12/27/02; 2:40:19 PM Discuss (1 response)

Designing and Using Combinators
Useful teaching materials from John Hughes. Most of the papers mentioned were discussed here in one way or another, but there are also lecture slides and exercises. Posted to functional by Ehud Lamm on 12/23/02; 12:30:41 PM Discuss (1 response)

The Fun of Programming

A symposium in honour of Professor Richard Bird's 60th birthday Examination Schools, Oxford. 24th and 25th March, 2003 If any LtU reader is going to be there, I here by announce that we will gladly publish your report here on the best PL web site on the net. The list of speakers is very impressive, so the book is likely to become a must. But don't worry, I can think of many more topics for the next festschrift, and we will continue to mention them here daily (since I don't know is who is going to turn 60 next and, more importantly, when ). Posted to functional by Ehud Lamm on 12/22/02; 6:59:16 AM Discuss (2 responses)

Yampa: Functional Reactive Programming with Arrows

Yampa is the culmination of our efforts to provide domain-specific embedded languages for the programming of hybrid systems using the concepts of functional reactive programming (FRP). Yampa is structured using arrows, which greatly reduce the chance of introducing space- and time-leaks into reactive, time-varying systems. Arrows applied to graphics and realtime systems (especially robots). Sucessor to Fran and FRP. Used to be called AFRP, but they decided that was too hard to pronounce. A development snapshot tarball is available, tested on linux/x86 and solaris/sparc. Posted to functional by Bryn Keller on 12/18/02; 11:38:03 AM Discuss

Tackling the awkward squad
Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell Simon Peyton Jones. Presented at the 2000 Marktoberdorf Summer School. This well known tutorial was recently updated (25 July 2002). Also notice the set of very useful slides. Posted to functional by Ehud Lamm on 12/18/02; 5:41:55 AM Discuss

De-biforestation

Deforestation is usually defined as the elimination of an intermediate data structure between a single producer and a single consumer. Jorge Adriano showed an interesting example of one producer feeding two independent consumers. The two streams of data are mutually dependent. Furthermore, the rate of production is non-uniform: Generating an element in one stream may require generating trillion items in the other stream. If the first consumer is being evaluated, that consumer causes the evaluation of the producer until the latter yields an item. The trillion of items incidentally produced in the other stream have to be stored somewhere. In more OS-centric terms, the evaluator can't generally reduce two expressions in parallel. If it chooses one stream consumer, the other consumer is set aside. While the first stream consumer "waits" for a value, the second stream consumer is "blocked", and hence the corresponding stream must be buffered, sometimes at great expense. A cool (and practical) example of program transformation. But why can't the optimizer do such transformation for us? Warning: If you are out of practice, the Haskell notation may be a bit taxing. Posted to functional by Ehud Lamm on 12/8/02; 6:04:19 AM Discuss (1 response)

The Architecture of a Debugger for Lazy Functional Languages
Uses Evaluation Dependence Trees to overcome the fact that in lazy languages the order of evaluation is opaque. A related paper is The Evaluation Dependence Tree as a Basis for Lazy Functional Debugging. Several other papers about debugging in lazy functional languages are available from Jan Sparud home page. Posted to functional by Ehud Lamm on 11/30/02; 11:53:55 AM Discuss

First Class Patterns

Mark Tullsen. First Class Patterns. Practical Aspects of Declarative Languages, Second International Workshop, PADL 2000. volume 1753 of Lecture Notes in Computer Science. January 2000. The key idea presented in this paper is to treat patterns as functions of type a -> Maybe b, thus making patterns into (first class) functions. Aside from all else, this is a nice example of language design. The pattern language is embedded in the host language (Haskell). Posted to functional by Ehud Lamm on 11/29/02; 3:40:13 PM Discuss (1 response)

Strafunski update

Strafunski, the Haskell generic toolkit based on functional strategies, was mentioned here before. The web site now has some new papers that may be of interest: A Strafunski Application Letter (PADL'03) describes some case studies. Typed Combinators for Generic Traversal (PADL'02) is a detailed description of the traversal combinators, and shows how to implement the extract method refactoring. We didn't really discuss this system. There are several research directions about genericity and Haskell, and it is easy to confuse them. The site does a good job comparing strategies with parametric polymorphism and polytypic functions. Posted to functional by Ehud Lamm on 11/11/02; 9:05:59 AM Discuss

Generic Haskell: Practice and Theory

Ralf Hinze and Johan Jeuring. Generic Haskell: Practice and Theory. Summer School on Generic Programming. 2002. Just how abstract can you get? If you always see one more level of abstraction, this is for you. These notes are quite detailed (and long, at 50 pages). The theoretical part is a bit dense, but the first part gives many examples and should be clear to anyone who fits the description in the first sentence of this message. Posted to functional by Ehud Lamm on 10/29/02; 7:16:37 AM Discuss

Type-Directed Natural Language Parsing

Sebastian Shaumyan, Paul Hudak. Linguistic, Philosopical, and Pragmatic Aspects of Type-Directed Natural Language Parsing presented at the 1997 Conference on Logical Aspects of Computational Linguistics. Why this should interest LtU readers is, I hope, obvious. This is related to things we discussed recently. However, the approach here is slightly different. An earlier version of this work is also available. Posted to functional by Ehud Lamm on 10/26/02; 9:07:55 AM Discuss (3 responses)

Deriving backtracking monad transformers

Hinze, Ralf. 2000. Deriving backtracking monad transformers. In ICFP '00: Proceedings of the ACM international conference on functional programming, vol. 35(9) of ACM SIGPLAN Notices, 186-197. New York: ACM Press. In a paper about pretty printing J. Hughes introduced two fundamental techniques for deriving programs from their specification, where a specification consists of a signature and properties that the operations of the signature are required to satisfy. Briefly, the first technique, the term implementation, represents the operations by terms and works by defining a mapping from operations to observations -- this mapping can be seen as defining a simple interpreter. The second, the context-passing implementation, represents operations as functions from their calling context to observations. We apply both techniques to derive a backtracking monad transformer that adds backtracking to an arbitrary monad. In addition to the usual backtracking operations -- failure and nondeterministic choice -- the Prolog cut and an operation for delimiting the effect of a cut are supported. A shining and useful example of deriving programs from specifications. Posted to functional by Ken Shan on 10/16/02; 2:09:00 PM Discuss (1 response)

Haskell tutorial in Hebrew

A student of mine wrote a short tutorial on basic programing in Haskell. This is the first Hebrew Haskell tutorial I know of. If anyone is interested, let me know and I'll ask the student to send you a copy. The tutorial covers: simple functions, working with lists, algebraic datatypes, lazy evaluation and type inference. It is aimed at experienced programmers who have no functional programming experience. The tutorial doesn't cover monadic programming. Posted to functional by Ehud Lamm on 10/13/02; 5:01:52 AM Discuss (7 responses)

ICFP programming contest results

The results of the ICFP (International Contest on Functional Programming) programming competition have been posted. Once again, an entry written in ocaml won the contest, while second prize went to an entry written in plain old C (!). The judges' prize went to an entry written in python, which I believe is a first for this contest. So far the source code for the entries hasn't been posted, but stay tuned. I'm not a fan of programming contests at all, but I like this one. One reason is that its goal is primarily to highlight the languages used, and only secondarily the skills of the contestants. The other is that the rewards are mostly peer recognition, with a little bit of money thrown in. I guess this contest proves that C is the second-best functional programming language ;-) The horror, the horror... Posted to functional by Michael Vanier on 10/7/02; 1:28:57 AM Discuss (4 responses)

Fold and Unfold for Program Semantics

"The paper is based upon categorical work on semantics, but explaining the ideas using Haskell makes them simpler, accessible to a wider audience, and executable." This paper explains how to use fold and unfold to build executable semantic models. The equivalence between denotational semantics and folding over syntax trees is demonstrated with a simple example. A denotational semantics for addition is defined with fold and then redefined to compile "expressions into a list of instructions for execution using a stack." Next, the relation between unfold and operational semantics is illustrated: "In operational semantics, the meaning of terms is defined using a transition relation that captures execution steps in an appropriate abstract machine... we explain how an operational semantics can be characterised as a semantics defined by unfolding to transition trees." The last part of the paper deals with a more involved example: Milner's Calculus of Concurrent Systems (CCS) which is "defined in an abstract manner as least fixpoints of functors" again using Haskell. (Fold and Unfold for Program Semantics, Graham Hutton) Posted to functional by jon fernquest on 10/5/02; 3:54:21 AM Discuss (1 response)

Devils and Angels
A solution in Haskell to a well-known continuations problem. The problem is described online in Continuations in Programming Practice: Introduction and Survey (Felleisen and Sabry, 1999) [Source] as well as in A Modular Monadic Action Semantics. Posted to functional by jon fernquest on 10/2/02; 2:58:45 AM Discuss

Algebraic patterns in Scheme
Eli Barzilay is doing some cool things with Scheme. His latest hack is extending Scheme with pattern matching (a la ML). Example: > (map (lambda ((list x y)) (list y x)) '((1 2) (3 4))) ((2 1) (4 3)) Posted to functional by Ehud Lamm on 10/1/02; 12:21:59 AM Discuss (4 responses)

Introduction to Functional Programming
A set of lectures about functional programming and Haskell. The slides can be used for self-study, and contain exercises. Includes a few examples of the IO monad. Posted to functional by Ehud Lamm on 9/30/02; 9:37:06 AM Discuss

Generator and Search Objects in Java

"Generator classes are defined in the object oriented programming language Java by using continuation-style programming. Generator objects are used to write Prolog-like programs in Java to solve combinatorial constraint satisfaction problems." Examples include the N-Queens problem and some useful web search functions: "GenURLsFromURL generates the URLs found in the page specified by a given URL, and GenURLcontainsString succeeds if a page contains a given string and fails otherwise." This paper adds Java to the several other LTU postings on generators: [1, 2, 3] (Generator and Search Objects in Java, Lloyd Allison, 2000) Posted to functional by jon fernquest on 9/29/02; 4:09:43 AM Discuss

Multi-Paradigm Tcl-Tk
Several entries in the Tcl-er's Wiki use ideas from the functional and logic programming paradigms: Steps towards functional programming Haskell Closures List Comprehension Tuplespaces Prolog Posted to functional by jon fernquest on 9/24/02; 1:51:27 AM Discuss

Building cyclic data structures in pure languages

(From Oleg) Henry Baker once remarked that pure functional objects are cycle-free. It seems then it's impossible to process cyclic graphs in a pure-functional language. Well, Henry Baker's assertion is true only for strict languages. A non-strict language can easily create and traverse cyclic graphs. Oleg has more to say about cyclic graphs and the Credit Card Transform. Just the other day a student of mine told me he spent some time trying to prove that pure languages can't create cycles. Since he was talking about Haskell I was only too glad to tell him that things are a bit more complicated than that. Posted to functional by Ehud Lamm on 9/18/02; 9:26:17 AM Discuss

Parsec, a fast combinator parser

A combination user guide, reference manual, and tutorial for a Haskell combinator parser library. It has the most easily understandable examples and explanations that I have ever seen in a text about functional languages, both small code snippets to convey essential ideas and full parsers for some small languages. The clear and easy to understand explanations are apparently part of the author's philosophy of making his parsing library maximally usable. The library also sports a BSD style license to encourage widespread use. [Parsec Homepage] (Parsec, a fast combinator parser, Daan Leijen, 2001) Posted to functional by jon fernquest on 9/15/02; 8:58:16 AM Discuss (1 response)

LPS: Language Prototyping System
"LPS is a system for writing modular interpreters implemented in Haskell. It is part of ongoing research for my PhD Thesis. The goal is to provide a framework for the development of language prototypes." The page includes a working version of the system to download and links to relevant papers by several authors. Posted to functional by jon fernquest on 9/11/02; 2:19:55 AM Discuss (2 responses)

Sendmail Meets Erlang

Our software engineering team needed to create a system that moves data from a set of legacy applications with diverse properties to data repositories scattered around the network. This system had to be highly concurrent, straightforward to extend, have high performance, and be coded rapidly by a small development staff. Because of these requirements, the authors embarked upon an experiment to write this application in Erlang. This paper describes what we did, why we did it, and what we learned over the course of our development effort. It is our hope that this chronicle may be useful to others thinking about coding in Erlang for the first time and to the incumbent Erlang community to hear an outsider's perspective on this fine language. Good to see commerical applications of functional languages. It may be interesting to compare their wish-list against what a typical theorist may want (static-typing isn't there, more code examples is). Posted to functional by Noel Welsh on 9/2/02; 5:55:48 AM Discuss

A Modular Monadic Action Semantics

This down to earth 246 page master's thesis fuses the readability of action semantics with the formal manipulability and provability of modular monadic semantics [Scheme Semantic Lego, Liang and Hudak, 1996] into a more useful whole: Modular Monadic Action Semantics (MMAS). "Modular monadic action semantics replaces the structural operational semantics that formalises action semantics with a modular monadic semantics. This replacement provides the flexibility to modify or delete existing facets of action semantics or to add entirely new ones and will allow the use of the theories of modular monadic semantics and of denotational semantics to theorise about actions... The integrated semantics adds a continuational facet to represent call-current-continuation. The thesis includes a clear non-theoretical explanation of the two semantics that are integrated: action semantics and modular monadic semantics. A toy functional language EL is built in modular monadic semantics with Haskell. The 1200 line Haskell implementation of the integrated system is provided as a "literate Gofer script" in appendix e. The whole thesis is written in a literate programming fashion and never strays far from source code. Although neither a compiler nor an interpreter is built with the integrated system, in appendix a two programming problems are solved. (A Modular Monadic Action Semantics, Keith Wansbrough, 1997) Posted to functional by jon fernquest on 8/30/02; 1:31:55 AM Discuss (1 response)

Overloading and higher-order polymorphism

Mark P. Jones. Functional programming with overloading and higher-order polymorphism. In Johan Jeuring and Erik Meijer, editors, Advanced Functional Programming: First International Spring School on Advanced Functional Programming Techniques, number 925 in Lecture Notes in Computer Science, pages 97-136. Springer-Verlag, Berlin, 1995. Our very own Ken Shan mentioned this interestng paper over on the Haskell mailing list. As a polymorphism lover (i.e., fanatic) I liked the general approach. The explanation of type classes in Haskell is especially good. The last section of the paper may be too abstract for some... Posted to functional by Ehud Lamm on 8/25/02; 5:54:13 AM Discuss (1 response)

Making Haskell programs faster and smaller
(via the Haskell mailing list) The pros and cons of lazy evaluation. You may want to read the original message from the mailing list. Posted to functional by Ehud Lamm on 8/23/02; 4:46:00 AM Discuss (2 responses)

Informal Scheme Workshop in London
There will be an informal Scheme workshop held in London. Date 26th of August, 2002 (the Bank Holiday Monday) Time Noon Venue To be arranged Contact If you are interested in this event or, future events of a similiar ilk, please email Noel. Apologies if you consider this inappropriate for LtU Posted to functional by Noel Welsh on 8/20/02; 3:54:53 AM Discuss (10 responses)

Hacker's Introduction to Partial Evaluation

A partial evaluator automatically specializes a program given some of its data. We show how it arises naturally out of hand-coding specialized program generators, yielding a simple online partial evaluation library. ...It's usually seen as a high-tech tool needing sophisticated theory to build and sometimes even to use; this tutorial article tries to turn it into a meat-and-potatoes technique. A rewrite interpreter for simplifying algebraic expressions from Norvig's Paradigms of Artificial Intelligence is translated into Scheme and transformed into a compiler using partial evaluation. (Note: the author Darius Bacon also has a calculator programmable with rewrite rules (req) on his homepage that you can use with the Q Equational Programming Language). Posted to functional by jon fernquest on 8/15/02; 3:24:31 AM Discuss (1 response)

What the hell are Monads?
A nice basic introduction to monads in Haskell. There's a Further Reading section at the end with a few links to related research papers. Posted to functional by Ehud Lamm on 8/5/02; 2:24:15 AM Discuss

Structuring Depth-First Search Algorithms in Haskell

In this paper David Kind and John Launchbury show how to implement several important graph algorithms (e.g., connceted components) via reusable components in Haskell. As opposed to many examples of functional programming the authors are quite interested in efficiency and, more importantly, the time complexity of the various algorithms. Posted to functional by Ehud Lamm on 8/4/02; 6:10:24 AM Discuss

Template metaprogramming for Haskell

Template metaprogramming for Haskell. Tim Sheard and Simon Peyton Jones. 16 pages, May 2002. Submitted to the Haskell Workshop 2002. We propose a new extension to the purely functional programming language Haskell that supports compile-time meta-programming. The purpose of the system is to support the algorithmic construction of programs at compile-time. While the previous post was about working with generic data, this is about compile time generic code (I use generic in the Ada sense of the word). Detailed comparison with Scheme macros is provided as well as a discussion of the differences between the presented approach and MetaML (staging). Even C++ templates are mentioned. Typing in a compile time meta-system like Template Haskell is done on two levels (see section 7): First the template invocation must be checked. Next, after template expansion, the resulting object-language code (pure Haskell) is type checked. Template Haskell is strongly typed. The usuall macrology topics of scoping, quotation and quasiquoutation are there, of course, too. Posted to functional by Ehud Lamm on 8/3/02; 5:13:57 AM Discuss (3 responses)

A practical approach to generic programming

Scrap your boilerplate: a practical approach to generic programming. Ralf Laemmel and Simon Peyton Jones. 12 pages, July 2002. Submitted to POPL 2003. We describe a design pattern that for writing programs that traverse data structures built from rich mutually-recursive data types. Such programs often have a great deal of "boilerplate" code that simply walks the structure, hiding a small amount of "real" code that constitutes the reason for the traversal... Our approach is simple to understand, reasonably efficient, and it handles all the data types found in conventional functional programming languages. It makes essential use of rank-2 polymorphism, an extension found in some implementations of Haskell. For example, applying a function incS to all nodes of algebraic datatype Company, would look something like increase :: Float -> Company -> Company increase k = everywhere (mkT (incS k)) Section 9.3 compares the work presented with other techniques including polytypic programing, generalized folds and visitors. Posted to functional by Ehud Lamm on 8/3/02; 4:31:25 AM Discuss (2 responses)

The Boost Lambda Library

The Boost Lambda Library (BLL in the sequel) is a C++ template library, which implements form of lambda abstractions for C++. ... The primary motivation for the BLL is to provide flexible and convenient means to define unnamed function objects for STL algorithms. In explaining what the library is about, a line of code says more than a thousand words; the following line outputs the elements of some STL container a separated by spaces: for_each(a.begin(), a.end(), std::cout << _1 << ' '); Look's interesting, but is it worth it? While it does make code more readable, I'm worried about the reaction of programmers not familiar with this library if asked to maintain such code. Also, doesn't implement closures (obviously), but does suggest some workarounds: int foo(int); for_each(v.begin(), v.end(), _1 = bind(foo, _1)); Posted to functional by Dan Shappir on 7/31/02; 9:39:15 AM Discuss (4 responses)

Clean and Haskell compared
A well written and unbiased comparison of two important functional languages. LtU readers should know by now that I am not a great fan of language comparisons and critiques, as these are often misleading, inflammatory and fruitless. Not this one though. Posted to functional by Ehud Lamm on 7/24/02; 12:31:20 AM Discuss (1 response)

Lazy Functional Parser Combinators in Java

"This paper shows how to use parser combinators in a functional language as well as Java, and shows how parser combinators can be implemented in Java. Implementing parser combinators is accomplished by combining two libraries. The first one, writtenin Haskell, defines error-correcting and analysing parser combinators.The second one consists of a small Java library implementing lazy functional behavior. The combinator library is straightforwardly coded inJava, using lazy behavior where necessary. Using Java makes this functional approach to recursive descent parsing more accessible to programmers and projects working in mainstream languages. Note Prof. Swierstra's site with additional papers and combinator parsing web pages. See also Parser Combinators in C . Posted to functional by jon fernquest on 7/23/02; 3:34:22 AM Discuss (7 responses)

The Essence of Strategic Programming

Sub-titled "An inquiry into trans-paradigmatic genericity." ...a programming paradigm-independent characterisation of strategic programming (a generic programming idiom where programs are constructed using strategies). The kind of genericity enabled by strategies is geared towards processing heterogeneous data, such as parse trees and documents. Different combinators allow the idiom to be used in different programming paradigms: term-rewrite, functional, object-oriented, and logical. Includes a comparison with Aspect Oriented Programming and and a critique of XSLT. Many of the ideas seem to be similar to those in Simonyi's writings on Intentional Programming without the biological metaphors, vagueness, and proprietary secrecy. Posted to functional by jon fernquest on 7/23/02; 12:52:44 AM Discuss (5 responses)

Refactoring Functional Programs

We might program in an exploratory way: first establishing the functionality we seek, and then refactoring into a more elegant form. We suspect that functional languages are particularly suited to this form of programming, because their clean semantic basis makes wholesale transformations more feasible than for a language in the C family, say. The site contains a catalog of Haskell refactorings a case study in refactoring student "Semantic Tableaux" programs (propositional logic background here), a presentation, source code for the refactoring example, and a difference utility. Here's a rough distribution of refactorings in the catalog: types (7), function input arguments (4), case switches (2), monads (1), folds (1), set comprehensions (1), iteration/fixed point (1). Refactoring might be a useful tool in getting people to adopt functional languages in .NET, SML.NET and F#, when they have a comparative advantage over the languages that everyone is familiar with: Java, C++, and C#. Posted to functional by jon fernquest on 7/10/02; 6:20:12 AM Discuss (13 responses)

Declarative Event-Oriented Programming
Another interesting link from Jon (who should become an editor). Thanks! Posted to functional by Ehud Lamm on 7/6/02; 2:10:21 PM Discuss

Linear Types and Monads
Patrick tries to explain what linear types and mondas are all about. I guess the target audience is people with no functional programming background. The short explanation is well written and to the point. Small typo: state y2 should be state t2 Posted to functional by Ehud Lamm on 6/27/02; 7:22:27 AM Discuss (1 response)

Shiro Kawai - Shooting A Moving Target

How can you track complex information flow for an organization rapidly changing its structure and workflow? ... To cope with this situation, we've been using a Lisp-based object oriented database (OODB) from the beginning of the production. Lisp's flexibility allows us to change internal data structures quickly while maintaining the compatibility with the other parts of the production, which turned out to be the key requirement for such a fluid structure. Trying to clear the backlog of items from before the conference... Shiro Kawai tells an interesting story about a database intensive project (we are talking terabytes here) implemented in Lisp. Another aspect of the design was using an open and well-defined scripting API, implemented (obviously) in Lisp. If you find this interesting, do read the second article Shiro wrote about these issues. Oleg, who pointed me in the direction of these articles, also suggested a comp.lang.scheme thread discussing these projects. Posted to functional by Ehud Lamm on 6/25/02; 2:35:21 AM Discuss (1 response)

Chameleon

Chameleon is a Haskell-style language which provides a flexible overloading mechanism based on Constraint Handling Rules (CHRs). The user can impose conditions on overloaded identifiers via CHRs. For example, consider the functional dependency class Collects ce e | ce -> e where ... In Chameleon, we would provide instead the following CHR: rule Collects ce e, Collects ce e' ==> e=e' [...] Also available are three papers "Beyond Type Classes", describing the connection and differences compared to Haskell-style type classes. "A Theory of Overloading", describing the theoretical machinery behind the Chameleon language. "A Theory of Overloading Part II: Semantics and Coherence", describing an implementation scheme which we yet have to implement. Posted to functional by Bryn Keller on 6/21/02; 9:33:41 AM Discuss (4 responses)

SML.NET now out
From an email I received this morning: You previously expressed an interest in SML.NET. An initial release is now available for download [...] We will be making an announcement on newsgroups and mailing lists shortly. Comments or suggestions welcome! Posted to functional by andrew cooke on 6/17/02; 6:35:14 AM Discuss

Eager Haskell

Jan-Willem Maessen's dissertation, Hybrid Eager and Lazy Evaluation for Efficient Compilation of Haskellthesis has recently been released, and the author says an implementation is on the way: I'm presently working hard on making a production-quality version of the Eager Haskell compiler. If you have any questions about Eager Haskell, or would like to see a pre-release version of the compiler along with the programs I used as benchmarks, drop me a line. A full release of the unified pH / EH compiler is slated for mid-August. Here's the first paragraph of the abstract: The advantage of a non-strict, purely functional language such as Haskell lies in its clean equational semantics. However, lazy implementations of Haskell fall short: they cannot express tail recursion gracefully without annotation. We describe resource-bounded hybrid evaluation, a mixture of strict and lazy evaluation, and its realization in Eager Haskell. From the programmer's perspective, Eager Haskell is simply another implementation of Haskell with the same clean equational semantics. Iteration can be expressed using tail recursion, without the need to resort to program annotations. Under hybrid evaluation, computations are ordinarily executed in program order just as in a strict functional language. When particular stack, heap, or time bounds are exceeded, suspensions are generated for all outstanding computations. These suspensions are re-started in a demand-driven fashion from the root. Posted to functional by Bryn Keller on 6/4/02; 4:09:29 PM Discuss (2 responses)

Adaptive Functional Programming

Robert Harper. Adaptive Functional Programming. Indiana University, February, 2002. (PPT slides). An adaptive computation maintains the relationship between its input and output as the input changes. This allows for efficient recomputation, when input changes. Only the relevant parts of the program have to be executed again. This presentation explains the motivation and basic approach. Formal semantics and the relation to modal type systems are presented. You may also want to check out the paper Adaptive Functional Programming by Umut Acar, Guy Blelloch, and Robert Harper (ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Portland, January 2002). Posted to functional by Ehud Lamm on 5/30/02; 8:31:53 AM Discuss