Category: Uncategorized

  • The lambda revolution

    This article describes the entire process of writing, packaging and releasing a new Haskell library. If you love programming Haskell, and want to keep doing so, you’ll write some libraries and release them. The lambda revolution isn’t going to happen without your code!

    Creating Data.DList, it took about 60 minutes. People often need O(1) append, so about time we had a library for it. Here’s the entire transcript of creating a new Haskell project and releasing it to a public server. I then created a web page for the project, and announced it on the haskell@ mailing list. I used the following tools:

    Ready? Here we go!


    Script started on Mon Dec 11 13:47:40 2006
    
    $ cd dons/src
    $ mkdir dlist
    $ cd dlist
    
    $ mkcabal
    Project name: dlist
    What license ["GPL","LGPL","BSD3","BSD4","PublicDomain","AllRightsReserved"] ["BSD3"]:
    What kind of project [Executable,Library] [Executable]: Library
    Is this your name? - "Don Stewart " [Y/n]:
    Is this your email address? - "<dons@cse.unsw.edu.au>" [Y/n]:
    Created Setup.lhs and dlist.cabal
    
    $ cp ~/dons/src/yi/Yi/Lexers.hs .
    $ ls
    Lexers.hs   Setup.lhs   dlist.cabal
    
    $ mkdir Data
    $ mv Lexers.hs Data/DList.hs
    
    $ vim Data/DList.hs
    $ vim dlist.cabal
    
    $ darcs init
    $ darcs add dlist.cabal Setup.lhs Data/ Data/DList.hs
    $ darcs record --all
    Shall I record this change? (1/?)  [ynWsfqadjkc], or ? for help: a
    What is the patch name? Initial import of dlist package
    Do you want to add a long comment? [yn]n
    Finished recording patch 'Initial import of dlist package'
    
    $ runhaskell Setup.lhs configure --prefix=/home/dons
    Setup: Warning: No exposed modules or executables in this package.
    Setup: Error: Non-empty library, but empty exposed modules list. 
    Cabal may not build this library correctly
    
    $ vim dlist.cabal
    
    $ runhaskell Setup.lhs configure --prefix=/home/dons
    Configuring dlist-0.1...
    configure: /home/dons/bin/ghc-pkg
    configure: Dependency base-any: using base-2.0
    configure: Using install prefix: /home/dons
    configure: Binaries installed in: /home/dons/bin
    configure: Libraries installed in: /home/dons/lib/dlist-0.1/ghc-6.6
    configure: Private binaries installed in: /home/dons/libexec
    configure: Data files installed in: /home/dons/share/dlist-0.1
    configure: Using compiler: /home/dons/bin/ghc
    configure: Compiler flavor: GHC
    configure: Compiler version: 6.6
    configure: Using package tool: /home/dons/bin/ghc-pkg
    configure: Using ar found on system at: /usr/bin/ar
    configure: Using haddock found on system at: /home/dons/bin/haddock
    configure: No pfesetup found
    configure: Using ranlib found on system at: /usr/bin/ranlib
    configure: Using runghc found on system at: /home/dons/bin/runghc
    configure: Using runhugs found on system at: /home/dons/bin/runhugs
    configure: Using happy: /home/dons/bin/happy
    configure: Using alex: /home/dons/bin/alex
    configure: Using hsc2hs: /home/dons/bin/hsc2hs
    configure: No c2hs found
    configure: Using cpphs: /home/dons/bin/cpphs
    configure: No greencard found
    Preprocessing library dlist-0.1...
    Building dlist-0.1...
    
    $ runhaskell Setup.lhs build
    Preprocessing library dlist-0.1...
    Building dlist-0.1...
    Data/DList.hs:17:2: parse error on input `DList'
    
    $ vim Data/DList.hs +17
    
    $ runhaskell Setup.lhs build
    Preprocessing library dlist-0.1...
    Building dlist-0.1...
    [1 of 1] Compiling Data.DList       ( Data/DList.hs, /usr/obj/cabal/Data/DList.o )
    /usr/bin/ar: creating /usr/obj/cabal/libHSdlist-0.1.a
    
    $ runhaskell Setup.lhs install
    Installing: /home/dons/lib/dlist-0.1/ghc-6.6 & /home/dons/bin dlist-0.1...
    Registering dlist-0.1...
    Reading package info from ".installed-pkg-config" ... done.
    Saving old package config file... done.
    Writing new package config file... done.
    
    $ darcs amend-record
    Mon Dec 11 14:20:56 EST 2006  Don Stewart <dons@cse.unsw.edu.au>
      * Initial import of dlist package
    Shall I amend this patch? [yNvpq], or ? for help: y
    hunk ./Data/DList.hs 15
    -module Data.DList
    +module Data.DList (
    Shall I add this change? (1/?)  [ynWsfqadjkc], or ? for help: y
    hunk ./dlist.cabal 10
    +Exposed-modules:     Data.DList
    Shall I add this change? (2/?)  [ynWsfqadjkc], or ? for help: y
    Finished amending patch:
    Mon Dec 11 14:21:53 EST 2006  Don Stewart <dons@cse.unsw.edu.au>
      * Initial import of dlist package
    
    $ runhaskell Setup.lhs haddock
    Preprocessing library dlist-0.1...
    Running Haddock for dlist-0.1...
    Warning: cannot use package base-2.0:
       HTML directory /home/dons/share/ghc-6.6/html/libraries/base does not exist.
    /usr/obj/cabal/tmp/Data/DList.hs:"/usr/obj/cabal/tmp/Data/DList.hs": 37:1: parse error in doc string: [TokPara]
    
    $ vim Data/DList.hs +37
    
    $ runhaskell Setup.lhs haddock
    Preprocessing library dlist-0.1...
    Running Haddock for dlist-0.1...
    Warning: cannot use package base-2.0:
       HTML directory /home/dons/share/ghc-6.6/html/libraries/base does not exist.
    
    $ w3m -dump dist/doc/html/index.html 
     dlist-0.1:  Contents Index
    dlist-0.1:
    Differences lists: lists supporting efficient append
    Modules
    show/hideData
    Data.DList
    Produced by Haddock version 0.8
    
    $ mkdir tests
    $ vim tests/Properties.hs
    $ vim tests/Parallel.hs
    
    $ cd tests
    $ runhaskell Properties.hs 
    2: singleton                : OK, 1000 tests.
    1: model                    : OK, 1000 tests.
    2: snoc                     : OK, 1000 tests.
    1: append                   : OK, 1000 tests.
    $ cd ..
    
    $ darcs add tests
    $ darcs add tests/Parallel.hs tests/Properties.hs
    $ darcs whatsnew -s
    M ./Data/DList.hs -1 +1
    A ./tests/
    A ./tests/Parallel.hs
    A ./tests/Properties.hs
    
    $ darcs record --all
    ...
    Shall I record this change? (6/?)  [ynWsfqadjkc], or ? for help: y
    What is the patch name? Add QuickChecks
    Finished recording patch 'Add QuickChecks'
    
    $ darcs setpref test "cd tests ; runhaskell Properties.hs"
    Changing value of test from '' to 'cd tests ; runhaskell Properties.hs'
    changepref test
    cd tests ; runhaskell Properties.hs
    Shall I record this change? (1/?)  [ynWsfqadjkc], or ? for help: y
    What is the patch name? pre   run tests on each commit
    Do you want to add a long comment? [yn]n
    Running test...
    2: singleton                : OK, 1000 tests.
    2: snoc                     : OK, 1000 tests.
    1: model                    : OK, 1000 tests.
    2: append                   : OK, 1000 tests.
    Test ran successfully.
    Looks like a good patch.
    Finished recording patch 'run tests on each commit'
    
    $ darcs whatsnew -s
    No changes!
    
    $ darcs tag
    What is the version name? 0.1   dlist 0.1
    Finished tagging patch 'TAG dlist 0.1'
    
    $ runhaskell Setup.lhs sdist
    Building source dist for dlist-0.1...
    *** Exception: LICENSE: copyFile: does not exist (No such file or directory)
    
    $ cp ~/pqc/LICENSE .
    $ vim LICENSE 
    
    $ darcs add LICENSE
    $ darcs record
    addfile ./LICENSE
    Shall I record this change? (1/?)  [ynWsfqadjkc], or ? for help: y
    ...
    Shall I record this change? (2/?)  [ynWsfqadjkc], or ? for help: y
    What is the patch name? add license
    Do you want to add a long comment? [yn]n
    Running test...
    2: singleton                : OK, 1000 tests.
    2: snoc                     : OK, 1000 tests.
    1: model                    : OK, 1000 tests.
    2: append                   : OK, 1000 tests.
    Test ran successfully.
    Looks like a good patch.
    Finished recording patch 'add license'
    
    $ vim README
    $ darcs add README
    $ darcs record --all
    What is the patch name? Add a readme
    Do you want to add a long comment? [yn]n
    Running test...
    2: singleton                : OK, 1000 tests.
    2: snoc                     : OK, 1000 tests.
    1: model                    : OK, 1000 tests.
    2: append                   : OK, 1000 tests.
    Test ran successfully.
    Looks like a good patch.
    Finished recording patch 'Add a readme'
    
    $ ls
    Data        LICENSE     README      Setup.lhs   _darcs      dist        dlist.cabal tests
    
    $ darcs dist -d dlist-0.1. 
    Created dist as dlist-0.1.tar.gz
    
    $ darcs whatsnew -s
    No changes!
    
    $ darcs put pill00.cse.unsw.edu.au:/home/chakcvs/darcs/dlist/
    Finished applying...
    
    Script done on Mon Dec 11 15:04:54 2006
  • Quick interpreters with the Reader monad

    Rolling your own interpreters in Haskell is one of the joys of using this language, due to the support for:

    • algebraic data types
    • pattern matching on data
    • monadic environments
    • higher order functions

    Here’s a quick, complete interpreter for a simple math language of binary operators, with support for variables. It uses the Reader monad for a natural embedding of lexical scoping. Writing interpreters in Haskell is just so easy, no wonder Pugs was written in it.

    import qualified Data.Map as M
    import Control.Monad.Reader
    
    --
    -- A syntax tree type for simple math, with variables
    --
    data Exp = IntE Int
             | OpE  Op Exp Exp
             | VarE String
             | LetE String Exp Exp
    
    type Op = Int -> Int -> Int
    
    --
    -- The interpreter
    --
    eval (IntE n)       = return n
    eval (OpE op e1 e2) = liftM2 op (eval e1) (eval e2)
    
    eval (VarE x)       = do
        env <- ask
        return $ maybe (error "undefined variable") id (M.lookup x env)
    
    eval (LetE x e1 e2) = do
        env <- ask
        v   <- eval e1
        local (M.insert x v) (eval e2)
    
    --
    -- Run the interpreter
    --
    main = print $ runReader (eval test) M.empty
    
    --
    -- A simple text expression:
    --
    --      let x =
    --          let y = 5 + 6
    --          in y / 5
    --      in x * 3
    -- 
    -- ==>  6
    --
    test = LetE "x" (LetE "y" (OpE (+) (IntE 5) (IntE 6))
                          (OpE div y (IntE 5)))
                    (OpE (*) x (IntE 3))
        where x = VarE "x"
              y = VarE "y"

    Let’s run the test program:

    $ runhaskell A.hs
    6

    Adding a front end (with Parsec), and then implementing the rest of Ruby, is left as an exercise for the reader.