• Home
• Schedule
• Homework
• Resources
• Software
• Style guide

State Monad and Applicative Parsing

This homework provides practice with the state monad and applicative parsing combinators by developing and implementing a small, imperative programming language. There are some sample Lu programs in the lu subdirectory of the project that you can read to get a sense of the language.

This project will require you to first read about the Lu programming language in the module LuSyntax and then work in two separate modules.

1. LuStepper (practice with State monad)
2. LuParser (practice with parsing)

You can mostly work on the two modules in either order, but you'll need to complete the parser before finishing the stepper function at the very end of LuStepper.

Throughout the assignment, feel free to import modules from the base or containers packages.

Once you have implemented the first two parts of the assignment, you can put them together in a "stepper" for the Lu language. This interactive program lets us observe the computation piece-by-piece.

You can get it started with stack ghci and then call the stepper function to start the interactive loop.

For example, here's an interaction with the factorial function.... Each line beginning with Lu> is a prompt for the tool, allowing the user to type commands such as :l (load a file for stepping), :n (step to next statement), :p (step to previous statement), or evaluate an expression in the current store. Both :n and :p take an optional argument for the number of steps.

Lines beginning with --> show the current step of the computation (before it has been executed).

ghci> stepper
Lu> :l lu/fact.lu                          -- load a file
Loaded lu/fact.lu, initializing stepper
--> n = 5                               -- ready to execute first assignment
fact.lu> :n
--> f = 1                               -- "next" ready to executed second assignment
fact.lu> :n
--> while n > 0 do                      -- now ready for the while loop
  x = n
  z = f
  while x > 1 do
    f = z + f
    x = x - 1
  end
  n = n - 1
end
fact.lu> :n                                -- inside the while loop
--> x = n
fact.lu> f                                 -- look up the value of a variable (f)
1
--> x = n
fact.lu> n                                 -- look up another variable (n)
5
--> x = n
fact.lu> x                                 -- we haven't yet assigned to x
nil
--> x = n
fact.lu> :p                                -- we can go backwards!
--> while n > 0 do
  x = n
  z = f
  while (x > 1) do
    f = z + f
    x = x - 1
  end
  n = n - 1
end
fact.lu> :p                                -- another backwards step
--> f = 1
fact.lu> f                                 -- now the variable is undefined
nil
--> f = 1

You can also run all of the tests in the assignment using the stack run command. Make sure that you are in the top-level directory of the project when you call the command in the terminal so that the test cases can find the .lu files.