Higher order functions - Lambda for the rest of us

What with all the foolish notions about lambda be passed around since the start of this month, a nice introductory article on Using functions for such higher order purposes as arguments, function-generating functions, and anonymous functions is just what the doctor ordered.

Functions are the wonderful and powerful building blocks of computer programs. Functions allow you to break code down into simpler, more manageable steps. They also allow you to break programs into reusable parts -- parts that are both reusable within the program and in other programs as well. In this article, learn how to create new functions at runtime based on templates, how to create functions that are configurable at runtime using function parameters, and how the Scheme language can be a valuable tool with functions.

Pugs, Practicing the Theories.

A lot of language theory goes past here on Lambda the Ultimate, but we rarely see that theory directly impacting commercial programmers.

I'm a great fan of theoretical concepts like arrows, but at the same time I'm a self-employed programmer interested in solving my clients' problems.

Pugs is notable in that it profitably uses recent developments such as GADTs and Template Haskell for an implementation of Perl6.

I recently became a regular on the #perl6 irc channel and soon after joined the list of committers.

In just a few days I've seen a lot. I've seen enthusiastic members of the Perl community learning Haskell. I've seen myself learning Perl. I've also seen how daily Perl programmers work with abstractions like monad transformers. I've seen how some structures are easy to extend for programmers new to both the Pugs codebase and Haskell.

The Pugs project was started 64 days ago by Autrijus Tang, as an exercise while reading TaPL. Pugs already includes network and threading primitives. New tests and code are add at an amazing rate, as evidenced by the smoke tests.

I don't know if I'll end up using Perl after Pugs is written, but I am learning how to practice the theory of programming language design and implementation.

Reproducing Programs implement Lazy Lists

Along the lines of the quine discussion happening in another thread, Manfred von Thun wrote a new page for the Joy site, Reproducing Programs implement Lazy Lists. This connects nicely with Jeremy Gibbons spigot algorithms paper, one example of which is his IOHCC 2004 submission PiSpigot.

OCaml vs. C++ for Dynamic Programming

Some might want to check this /. thread,

On one particular problem instance (a garden of size 7x3), my C++ implementation finished in 1 second, while the OCaml implementation was still running after 16 minutes. Bear in mind that my OCaml implementation was dramatically faster than my equivalent Haskell code... If you write OCaml code that is isomorphic to C code, it will be fast---what about if you use OCaml the way it was meant to be used?

My critical view of this sort of thing is well known, and I don't want another holy war (the Knuth thread is enough for my taste), but I guess we should check comparisons of this sort from time to time, if only to keep everyone honest (including ourselves).

Educational Pearl: Automata as Macros

Shriram Krishnamurthi's classic macro automaton example, well known from his LL1 presentation, is now written up as an educational pearl for JFP.

As you may recall, the example shows how to use Scheme macros to create an an automata DSL, and concentrates on the importance of proper tail-calls for achieving the desired semantics.

De-typechecker: converting from a type to a term

This message presents polymorphic functions that derive a term for a given type -- for a class of fully polymorphic functions: proper and improper combinators.

Oleg's converter can let us `visualize' what a function with a particular type may be doing. It can be helpful in understanding functions written in point-free style.

And to top it off, we are shown how to do SLD resolution using Haskell typeclasses...

Embedded Interpreters

This is a tutorial on using type-indexed embedding projection pairs when writing interpreters in statically-typed functional languages. The method allows (higher-order) values in the interpreting language to be embedded in the interpreted language and values from the interpreted language may be projected back into the interpreting one. This is particularly useful when adding command-line interfaces or scripting languages to applications written in functional languages. We first describe the basic idea and show how it may be extended to languages with recursive types and applied to elementary meta-programming. We then show how the method combines with Filinski's continuation-based monadic reflection operations to define an extensional version of the call-by-value monadic translation and hence to allow values to be mapped bidirectionally between the levels of an interpreter for a functional language parameterized by an arbitrary monad. Finally, we show how SML functions may be embedded into, and projected from, an interpreter for an asynchronous pi-calculus via an extensional variant of a standard translation from lambda into pi.

Another paper from Nick Benton.

Like the previous one this paper is dense and detailed, but this time there are some useful practical techniques that may come handy next time you build a DSL in a functional language.

Functional Geometry

Frank Buss commented on c.l.l. how he never really understood how to use higher order functions as combinators, until he read the article from Peter Henderson about Functional Geometry. He has written his own article about how he used these concepts and Common Lisp to re-create the famous recursive fish drawing by M.C. Escher.

Nothing new for most readers, but it's fun anyway.

Region Streams: Functional Macroprogramming for Sensor Networks

This paper presents the design of a functional macroprogramming language for sensor networks, called Regiment. The essential data model in Regiment is based on region streams, which represent spatially distributed,time-varying collections of node state. A region stream might represent the set of sensor values across all nodes in an area or the aggregation of sensor values within that area. Regiment is a purely functional language, which gives the compiler considerable leeway in terms of realizing region stream operations across sensor nodes and exploiting redundancy within the network.

The operations on region streams include fold and map. The language uses monads to represent time varying values.

I know nothing about sensor networks (this paper is from DMSN 2004: the First Workshop on Data Management for Sensor Networks) so I can't judge how useful this project really is.

Notice that Regiment isn't implemented yet. Only a highly restricted (dynamically typed) subset is.

Implicit parallel functional programming

This discussion over on the Haskell Mailing List might interest those readers following the debates on concurrency issues in the discussion group...

XML feed