Assignment 1 Date
Part I February 12th (course week 4)
Part II February 26th (course week 6)


This assignment consists of 2 parts. In the first part, you will design, implement and test a Monad for programs that can be replayed. In the second part use this monad to implement a simple library for writing programs with web forms, implement an optimisation to your Replay monad that makes it much more useful, and use your web library to implement a simple application.

A monad for replaying computations

Consider the following scenario: a program is running. At some point, the program decides to stop, and produces a trace: a log of the computation so far.

The user would later on like to resume the program, making it run from the exact same point where it previously stopped. Not only should the program resume from where it stopped, but all values of all variables should be precisely the same as when the program decided to stop. The trace should contain all information necessary to do this.

The trace can thus be used as an input trace for rerunning the program, without repeating previously performed computations.

In this lab you will implement a monad called Replay for expressing such computations, capable of stopping to ask the user questions. This is the interface to the Replay monad:

instance Monad (Replay q r)

io  :: (Show a, Read a) => IO a -> Replay q r a
ask :: q -> Replay q r r

run :: Replay q r a -> Trace r -> IO (Either (q, Trace r) a)

The monad is parameterised on the types of questions (q) and answers (r, for result). There are two primitive operations in the monad besides return and >>=:

The run function takes a Replay program and a trace (possibly produced by a previous run of the program), and reruns the program using this trace. If the program stops with a question q, the result of the run function is Left (q, t), where t is the new trace. If there are no more questions, run results in Right x where x is the result of the whole computation.

It is important to note that Trace is going to be something that we can serialise. For our purposes this means being able to convert from and to a String, which we can then for instance write to a file.

An example

Here is an example of a program in the Replay monad. We have chosen the question and answer types to both be Strings:

import Data.Time

example :: Replay String String Int
example = do
  t0 <- io getCurrentTime
  io (putStrLn "Hello!")
  age <- ask "What is your age?"
  io (putStrLn ("You are " ++ age))
  name <- ask "What is your name?"
  io (putStrLn (name ++ " is " ++ age ++ " years old"))
  t1 <- io getCurrentTime
  io (putStrLn ("Total time: " ++ show (diffUTCTime t1 t0)))
  return (read age)

The example starts by getting the current time and printing a message, then stops the whole program asking "What is your age?". If the program is rerun from that point with an answer, it prints another message and then stops again, asking: "What is your name?". If the program is rerun from that point, a message is printed, and the total time for the whole process is calculated.

To understand how to deal with traces, here is a possible impementation for Trace:

type Trace r = [Item r]

data Item r = Answer r | Result String
  deriving (Show,Read)

emptyTrace = []
addAnswer t r = t ++ [Answer r]

When we run the above example, providing it with the empty trace, we get the following result:

GHCi> do x <- run example []; print x
Left ("What is your age?",[Result "1164117157",Result "()"])

We can see that the program printed the message, and then stopped, with the question "What is your age?", and a trace. The trace records what has happened in the program so far. When we have found the answer to the question, (for example 27), we can re-run the computation, augmenting the trace with an extra element:

GHCi> do x <- run example [Result "1164117157", Result "()", Answer "27"]; print x
You are 27.
Left ("What is your name?",[Result "1164117157",Result "()",Answer "27",Result "()"])

Again, the program prints its message, and stops with a question and a trace. Notice that we are running the same program (namely example) again, but now with a different trace! Again, we augment that trace with the answer we want to give, running the program again:

GHCi> do x <- run example [Result "1164117157", Result "()", Answer "27", Result "()",
Answer "Starbuck"]; print x
Starbuck is 27 years old
Total time: 19 seconds
Right 27

We can see that the program printed "Starbuck is 27 years old" on the screen, and calculated how long time the whole process took (from the beginning). The program then terminated normally with the result 27.

We can automate the process of re-running the program and augmenting it with the answer every time. This is done by another run function that re-runs the program with an answer every time the program stops and asks a question. Here is how:

running :: Replay String String a -> IO a
running prog = play emptyTrace
  play t = do
    r <- run prog t    -- this is the same prog every time!
    case r of
      Left (q,t2) -> do
        putStr ("Question: " ++ q ++ " ")
        r <- getLine
        play (addAnswer t2 r)
      Right x -> return x

There is very little reason for why we would like to use this particular run function, because it does not use the full generality of the Replay monad. Here is how it works on the example:

GHCi> running example
Question: What is your age? 59
You are 59
Question: What is your name? Adama
Adama is 59 years old
Total time: 5 seconds

Note that, in the above, the same program is re-run with a new trace, each time the answer to the question is provided by the user.

Part I

The first part of this assignment is to implement the Replay monad.

Task 1: the Replay monad

First create a Haskell module called Replay in an empty directory, then create a cabal library package called replay by running cabal init and answering all questions.

Look through the resulting cabal file and make sure you understand what it does and that your module is included in the package. Add any dependencies that you know you will need. Also you should relax the dependency on base to 4.* or similar. Implement a monad Replay with the following interface:

-- Types
Replay q r a
Trace r

-- Operations
instance Monad (Replay q r)
instance Show r => Show (Trace r)
instance Read r => Read (Trace r)

io  :: (Show a, Read a) => IO a -> Replay q r a
ask :: q -> Replay q r r

emptyTrace :: Trace r
addAnswer  :: Trace r -> r -> Trace r

run :: Replay q r a -> Trace r -> IO (Either (q, Trace r) a)

You can decide yourself how to implement the type Trace r, but it needs to be a type that can be written to and read from a file. (Ergo, it needs to be an instance of Show and Read.) Make sure that the example above can actually be run correctly!

Task 2: generalise the interface

For grades 4 and 5

Turn your Replay monad into a monad transformer ReplayT m, so that any underlying monad can be used, instead of only the IO monad. Add a function liftR for lifting computations from the underlying monad. Define Replay in terms of ReplayT:

type Replay q r a = ReplayT IO q r a

liftR :: (Monad m, Show a, Read a) => m a -> ReplayT m q r a

Remember to generalise all functions to the new interface where possible. Consider which functions are primitive and which are derived.

Question: why is it not possible to make your transformer an instance of MonadTrans?

Note: If you do this task, you should not submit the non-generalised version from task 1.

Task 3: testing the Replay monad

Once you have implemented your Replay monad transformer you should make sure that it works properly. Here is a small testing framework to help you get started: Test.hs. Put the framework in a subdirectory called test, then add this to your .cabal file to create a test suite:

Test-Suite test-replay
    type:            exitcode-stdio-1.0
    hs-source-dirs:  test
    main-is:         Test.hs
    build-depends:   base, replay

If done correctly this sequence of commands should execute your test suite:

cabal configure --enable-tests
cabal build
cabal test

The idea of the framework is to test replay computations with integers as answers and whose only IO action is to increment a counter a number of times. We check that when running the program on a list of input integers we get the correct result and that the counter has the right value.

You should write down enough test cases that you are confident that your implementation is correct. Try to think about possible corner cases.

For grades 4 and 5

Use the generalised interface from task 2, and replace the IO monad with a State monad.

For grade 5

Use QuickCheck to generate random test cases.

Part II

In the second part of the assignment you will extend your library with a web programming DSL on top of the Replay monad and write an example application.

Web programming

In this section we will explore programming web forms using the Replay monad. We suggest to use the light weight Haskell web server scotty.

A simple but dated way to implement web-based systems is as follows. A web form is sent to the user. The user fills in some information and sends it back to the server. The server looks at it and sends new content, which is filled by the user, and so forth.

A problem with programming web forms is the user's state: the inputted data so far, and the replies from the web server. It needs to be stored somewhere: either in the server, or in the client.

If it is saved in the server each client needs to somehow be identified, and the server state code can get quite complex: it is not clear what to do when the user uses the browser's "Back" button to go back to an earlier state, or the browsers "Clone" button, often resulting in web pages with inconsistent information and a really poor user experience.

In this part, we will explore the second alternative: store the state (or trace, if you will) on the client using the Replay monad.

Right below is a very simple web form program in Haskell using scotty. It produces a very simple HTML page, which contains a form. The user can provide information in the form and click OK. The program then gets the input of the form, and sends back a new web page. The client browser then reloads with this new web page.

{-# LANGUAGE OverloadedStrings #-}
module Main where

import Web.Scotty
import Data.Monoid
import Data.Text.Lazy

main :: IO ()
main = scotty 3000 $ do
    get "/" serve
    post "/" serve
    serve :: ActionM ()
    serve = do
        i <- getInput
        html (page i)

    getInput :: ActionM Text
    getInput = param "text_input_id" `rescue` \ _ -> return ""

    page :: Text -> Text
    page s = mconcat $
        [ "<html><body>"
        , "<p>Input was: ", s, "</p>"
        , "<form method=post>"
        , "<p>Type something here:</p>"
        , "<input name=text_input_id>"
        , "<input type=submit value=OK>"
        , "</form>"
        , "</body></html>"

This program can either be compiled and then run, or you can just issue runghc TestScotty.hs. It will run a web server locally on port 3000, so you should be able to access it with your web browser on address http://localhost:3000/.

Whatever is filled in in the form is given as input to the scotty program when the user presses OK. Try experimenting with adding more <input> tags to the form and see how this affects the program. Both GET and POST requests are supported. Try changing the method in the form tag to get. You should see the inputted value in the query string of the address.

Make sure that you can run the above program and understand what is going on before you continue!

Task 1: a library for web forms

The idea is now that you will now extend your replay library with web form programming, based on your Replay monad. This library should have the following interface:

type Web a = Replay Form Answers a

type Form = ?

type Answers = ?

runWeb :: Web ? -> ActionM ()

In other words, the library provides a monad Web that is used to communicate with a user, by exchanging web-pages, and receiving answers.

The idea is that the programmer can send HTML forms to the user by using ask. When the user enters data in the form and sends it back, the Web program is re-run up to the point where ask was used, and continues with the answer that was gotten from the user.

In order for this to work, you need to do the following:

You may provide any extra functionality, or change the type Web if you feel the need for it.

Task 2: optimising the Replay monad

For grades 4 and 5

The Replay monad remembers all results ever computed, even if they are not affecting the current computation anymore. This is not very space-efficient.

For example, if we would ask for the user's age like this:

askAge :: ReplayT IO String String Int
askAge = do
     birth <- ask "What is your birth year?"
     now   <- io getCurrentYear
     return (read now - read birth)

Then every time we use this function both results would be remembered in the trace forever, although we know we will never actually use the fact that we now know the user's birth year and the current year. Instead, we would like to just remember the age, and shortcut the trace there.

Implement a function:

cut :: (Monad m, Read a, Show a) => ReplayT m q r a -> ReplayT m q r a

The idea with this function is that cut m should produce the same results as m; it only affects the replay behaviour. Namely, when we replay the computation cut m and it has completed, only the result of m is remembered, and none of the things that happened inside m to make this happen.

Thus the user can use cut to annotate their Replay programs and make them more space-efficient. For example, askAge above could be implemented as follows:

askAgeCut :: ReplayT IO String String Int
askAgeCut = cut askAge

In short, when you replay cut m, one of three things can happen.

  1. The replay-trace has not been here before. In this case, we enter m and look inside.

  2. The replay trace has been here before, but the last time we ran the program, somewhere inside m we stopped at an occurrence of ask. In this case, we enter m and trace normally.

  3. The replay trace has been here before and completed the computation m. In this case, we never look inside m, but the trace knows what the result of m was and we short cut the tracing behaviour.

In order to implement cut, you need to adapt your type Trace. There needs to be a way for the trace to keep track of the whether we should enter m, or if we already know the result of m. Don't forget to add test cases for cut. Again, think about corner cases such as cut (return 0).

Task 3: an interesting web program

Implement a more realistic example that uses your web library. Add it as an executable called web in your cabal package, similarly to how the example in lab 1 was implemented. The following elements should occur in your program:

Hint: remember that the monads scotty provides (ActionM and ScottyM) are instances of MonadIO and thus supports IO actions, so your program can interact with the server machine in any way. For instance you could make a little command shell that first takes commands such as ls, cd and cat. For some commands it will then require parameters to be supplied (i.e. a file name). It then displays the contents of directories and files.

Another idea would be one that fetches a given URL and transforms it in some way, for instance by asking the user for a two words and replacing one with the other. It then displays the modified page or writes it to a file on the web server and displays a link.

A third idea is to implement a simple small spreadsheet matrix, where entries may either be numbers, or expressions referring to other cells (or blocks of them).

These are considered ambitious to very ambitious for the purpose of grading; the minimal requirements are lower.

More information

(Feel free to send in suggestions on other good resources to put here.)

Extra assignments

These are completely voluntary, you can get grade 5 on the assignment without doing any of these.


Clean code

Before you submit your code, clean It Up! Submitting clean code is Really Important, and simply the polite thing to do. After you feel you are done, spend some time on cleaning your code; make it simpler, remove unnecessary things, etc. We will reject your solution if it is not clean. Clean code:

What to submit

Your submission needs to include the following information:

Use cabal sdist to generate the source tarball. Make sure the tarball is working by extracting it in another directory and running cabal configure --enable-tests, cabal build, cabal test and cabal haddock and checking that everything looks right.


Go to the Fire system!