Lambda the Ultimate

Functional Pearl: Type-safe pattern combinators, by Morten Rhiger:

Macros still have not made their way into typed higher-order programming languages such as Haskell and Standard ML. Therefore, to extend the expressiveness of Haskell or Standard ML gradually, one must express new linguistic features in terms of functions that fit within the static type systems of these languages. This is particularly challenging when introducing features that span across multiple types and that bind variables. We address this challenge by developing, in a step-by-step manner, mechanisms for encoding patterns and pattern matching in Haskell in a type-safe way.

This approach relies on continuation-passing style for a full encoding of pattern matching. Tullsen's First-Class Patterns relies on a monadic encoding of pattern matching to achieve abstraction over patterns. Given the relationship between CPS and monads, the two approaches likely share an underlying structure.

Abstracting over patterns yields a whole new level of abstraction, which could significantly improve code reuse. The only concern is compiling these more flexible structures to the same efficient pattern matching code we get when the language natively supports patterns. Section 4.9 discusses the efficiency concerns, and suggests that partial evaluation can completely eliminate the overhead.

Merry Christmas!

@nonstroking:[rgb 0.9 0.1 0.1] & @TeX_bleed:2bp | [rotate 20°]*[scale y:2] [] (TeX `Merry Christmas, $\lambda$!´)
   >> \ obj → @width:3bp | [stroke [bbox obj 'bleed]] & obj

Or,

message: @nonstroking:[rgb 0.9 0.1 0.1] & @TeX_bleed:2bp
   | (TeX ("Merry Christmas, $\lambda$!"))
tf: [rotate 20^^]*[scale y:2]
obj: [tf message]
#page << @width:3bp | [stroke [bbox obj 'bleed]]
#page << obj


This post is an announcement of the functional drawing language Shapes. (Both block quotes above are complete Shapes programs, although the first is admittedly not the easiest program to read, and the second is slightly obscured by ASCII fallbacks.) There are several reasons for the announcement:

• Comments and feedback on the design would be most welcome.
• It would be fun if more people would like to join on the implementation-side of the project.
• The project is in great need of testers.
• Someone might actually find Shapes a useful tool!

While Shapes is a domain specific language, there exist other drawing languages for the same type of applications, so the raison d'être lies in how the end result is obtained — that is, what programming in the language is like. The primary audience for Shapes is the community of people with a taste for functional languages.

Then, given that a DSL is being developed, there is an opportunity to dwell upon the general purpose aspects of the language. This is an important motivation behind the development.

So, if you didn't follow the link at the top of the post, you might be wondering what Shapes is really like. Here is a short list of key properties:

• Syntax is tailored for the application at hand (path construction and LaTeX strings are prioritized use cases).
• Pure functions have no side effects.
• Pure functions may be implemented using states.
• Both lexical and dynamic binding.
• Named arguments.
• Dynamically typed.
• Lazy evaluation.
• CPS (currently only used for escape continuations).

Error messages are often helpful, there is a fair amount of documentation at the project web site, there is a friendly shapes-mode for Emacs, and I will personally be more than happy to help out in all ways. Please have a look at the online documentation and consider trying it out hands on!

Shapes is developed under the GPL, and implemented in C++.