Functional Thinking

The University of Kansas is pleased to call for participation in the 12th Annual ICFP Programming Contest, hosted by the Computer Systems Design Laboratory at the Information and Telecommunication Technology Center.

http://icfpcontest.org/

The contest, associated with the International Conference on Functional Programming, will be held on the weekend of June 26-29. The contest task will be released sixteen seconds after 13:00 Central Daylight Time (US) on Friday, and entries will be accepted until 13:00:16 CDT on Monday (72 hours later). There is no preregistration required, and participation is free and open to all. Teams may participate from any location, and may use any programming language(s). Last year, over 330 teams participated from around the globe.

Solutions can be submitted to a lightning round (within the first 24 hours) and the regular 72-hour competition. First place, lightning round, and judges’ choice prizes will be awarded, which will include prize money to help defray the costs of travel to the conference for the winners as well as small cash prizes. In addition, the winners of the contest will receive bragging rights for the programming language of their choice. This makes the contest a popular avenue for demonstrating the superiority of a favorite language, or for exercising an experimental tool.

Stay tuned for more information as the contest approaches! Read the contest blog (http://www.icfpcontest.org/wordpress) or subscribe to the RSS feed (http://www.icfpcontest.org/wordpress/?feed=rss2) to receive timely updates before and during the contest.

~ 2009 Contest Organizers ~
The University of Kansas CSDL

Memoization is a well known and well studied optimization technique. In Haskell, the purely functional semantics allows function applications to reuse previous invocations, by looking up a cache or memo table.

Take the classical fib function.

fib :: Int -> Int
fib n = if n < 2 then 1 else fib (n-1) + fib (n-2)

There are many calls to fib with the same argument. But is there a way of memoizing this function without changing the original fib definition? Yes, there is already is, in GHC.

1. We choose an efficient representation, in this case a simple list of Ints. We can choose other structures, like tries, but lists keeps this short tutorial straightforward.

type Nat = Int
 
memo :: (Nat -> Int) -> [Int] 
memo f = map f [0..]
 
apply :: [Int] -> (Nat -> Int)
apply xs n = xs !! n

2. We define a worker function, which creates our memo table.

worker :: [Int]
worker = memo (inline fib)

inline is a magic GHC built-in function, so we need to import inline.

import GHC.Exts

This gives us a worker which builds the memo table, the list of Ints, but the rest of the program calls the original unmemoized fib.

3. Finally, we add a GHC RULE, to use the memo table everywhere.

{-# RULES "fib" forall xs . fib xs = apply worker xs #-}

Remember to use -O2, or the rule will not fire. Now wherever fib is called, including inside the right hand side of the definition, the memo table is queried instead. We have replaced fib with a memoized version of fib, without changing the original definition of fib.

This is a special case of the worker/wrapper transformation. Though the full benefits of worker/wrapper can not (yet) be realized inside GHC, memoization can be.

The use of inline is critical to this success of this transformation. If inline is not used, then we can reach the nonsense definition

worker :: [Int]
worker = memo (apply worker)

So remember the inline in your worker!

Thanks to Simon PJ, for pointing out that we can use inline in force inlining, and avoid the nonsense definition while still using GHC rules.

We’re pleased to announce the availability of the first public release of the Timber compiler. Timber is a modern language for building event-driven systems, based around the notion of reactive objects. It is also a purely functional language derived from Haskell, although with a strict evaluation semantics.

The Timber compiler currently runs on Linux and MacOS X platforms, but uses gcc as its back-end so it should be easily portable to most POSIX-like environments. For more info, language documentation, source code access and binary installers, see

Or simply grab the timberc package at http://hackage.haskell.org/.

The Timber Team

Have you ever wanted to pretty print more than ASCII text? Perhaps add color, hyperlinks, or other markup in your pretty printed code when rendering to HTML? A new version of the HughesPJ pretty printing library recently uploaded to hackage allows just this.

The library provides one new combinator, one new constructor, and makes Doc a type synonym.

-- The old Doc API
type Doc = MDoc ()
 
-- The new Doc, with marks
data MDoc a = ...
 
-- augmented TextDetails
data TextDetails a
                 = Chr  Char
                 | Str  String
                 | PStr String
                 | Mark a	-- new
 
-- new combinator; inserts a zero width mark 
-- into the output document                                                                          
mark :: a -> MDoc a
mark m = textBeside_ (Mark m) 0 Empty

A mark is a zero width datum inserted into the output stream, using Mark. For ASCII output, the marks are removed and ignored.

Using this library is straightforward. Here is the test from the package.

module Main where
 
-- we hide Doc becase we are going to rename it.
import Text.PrettyPrint.MarkedHughesPJ hiding (Doc)
 
-- simple datastructure
data Exp = App Exp [Exp]
         | Var String
         | Lit Int
         | List [Exp]
 
-- our pretty printer
pretty :: Exp -> Doc
pretty (App e args) = pretty e <+> sep (map (parens . pretty) args)
pretty (Var v)      = text v
pretty (Lit l)      = scope BOLD $ scope GREEN $ text (show l)
pretty (List es)    = brackets (scope RED (sep (punctuate (text ",") (map pretty es))))

So far, this looks like any other pretty printer, except we have also used a new combinator, scope.

type Doc = MDoc Markup
 
data Markup = Open MStyle | Close MStyle
 
data MStyle = BOLD | RED | GREEN
 
open :: MStyle -> Doc
open = mark . Open
 
close :: MStyle -> Doc
close = mark . Close
 
scope :: MStyle -> Doc -> Doc
scope s d = open s <> d <> close s

Here we define scope as an open and a close. We can now provide a function which outputs marked up HTML rather than ASCII (the default).

html_txt (Chr c) r      = concatMap escape [c] ++ r
html_txt (Str s) r      = concatMap escape s ++ r
html_txt (PStr s) r     = concatMap escape s ++ r
html_txt (Mark (Open BOLD)) r  = "<b>" ++ r 
html_txt (Mark (Close BOLD)) r = "</b>" ++ r
html_txt (Mark (Open RED)) r   = "<font color=\"red\">" ++ r 
html_txt (Mark (Close RED)) r  = "</font>" ++ r
html_txt (Mark (Open GREEN)) r   = "<font color=\"green\">" ++ r 
html_txt (Mark (Close GREEN)) r  = "</font>" ++ r
 
escape '<' = "&lt;"
escape '>' = "&gt;"
escape c   = [c]

Now we use both the default and html_txt render methods.

main = do
  putStrLn "<html><body><pre>"
  sequence_ [ putStrLn $ render (pretty ex)
             |  ex <- examples
            ]
  putStrLn $ "<hr>"
  sequence_ [ putStrLn $ fullRender PageMode 100 1.5 html_txt "" (pretty ex) 
             | ex <- examples
            ]
  putStrLn ...

This outputs the original style and new style of markup.

abc
cde
abc (cde)
99
abc (cde) (abc) (99) (cde) (abc) (cde) (99) (cde)
[abc,
 cde,
 abc (cde),
 99,
 abc (cde) (abc) (99) (cde) (abc) (cde) (99) (cde)]
abc (cde) ([abc,
            cde,
            abc (cde),
            99,
            abc (cde) (abc) (99) (cde) (abc) (cde) (99) (cde)])
99 (99)

abc
cde
abc (cde)
99
abc (cde) (abc) (99) (cde) (abc) (cde) (99) (cde)
[abc,
 cde,
 abc (cde),
 99,
 abc (cde) (abc) (99) (cde) (abc) (cde) (99) (cde)]
abc (cde) ([abc,
            cde,
            abc (cde),
            99,
            abc (cde) (abc) (99) (cde) (abc) (cde) (99) (cde)])
99 (99)

This is all there is to it - it is easy to add markup inside pretty printed documents. This library is used inside the Haskell Equational Reasoning Assistant, to facilitate the selectability of sub-expressions, make keywords bold, make symbols blue, etc. It is available from hackage, called marked-pretty.