Archive for the ‘Release’ Category

Sunroof: Clockwork Progress

Friday, April 12th, 2013

In this article, we are going to generate a JavaScript application. Last year, we wrote a blog post about using monad reification to implement a JavaScript compiler. The compiler, called Sunroof, is now in state that we can make the first public release. By way of a non-trivial example, this blog entry illustrates how to construct an analog clock as a self-contained JavaScript application that renders the clock using the HTML5 canvas element.

The Sunroof clock example

The Sunroof clock example

The JavaScript API for HTML5 canvas element is already provided by Sunroof in the module Language.Sunroof.JS.Canvas. Lets look how we can render one line of the clock face using Sunroof:

c # save
-- Draw one of the indicator lines
c # beginPath
c # moveTo (0, -u * 1.0)
ifB (n `mod` 5 ==* 0)
    (c # lineTo (0, -u * 0.8)) -- Minute line
    (c # lineTo (0, -u * 0.9)) -- Hour line
ifB (n `mod` 15 ==* 0)
    (c # setLineWidth 8 ) -- Quarter line
    (c # setLineWidth 3 ) -- Non-Quarter line
c # stroke
c # closePath
-- Draw of the hour numbers
ifB (n `mod` 5 ==* 0)
    (do
      c # translate (-u * 0.75, 0)
      c # rotate (-2 * pi / 4)
      c # fillText (cast $ n `div` 5) (0, 0)
    ) (return ())
c # restore

The monadic do-notation is used for sequencing JavaScript statements in a neat fashion.

The first few lines probably look familiar to people who have written JavaScript before.

c # save
-- Draw one of the indicator lines
c # beginPath
c # moveTo (0, -u * 1.0)

The #-operator is used instead of the .-operator in JavaScript. u represents the radius of the clock. Knowing this you can see that we are calling methods on the JavaScript object c (Our canvas context). The methods without parameters do not require empty parenthesis, as a Haskell programmer would expect. The tuple used in the call of moveTo is only there to indicate that this parameter is a coordinate, not two single numbers. You can also see that JavaScript numbers are neatly embedded using the Num-class and can be used naturally.

The next few lines show a branch.

ifB (n `mod` 5 ==* 0)
    (c # lineTo (0, -u * 0.8)) -- Minute line
    (c # lineTo (0, -u * 0.9)) -- Hour line

Haskell lacks the possibilities to deep embed branches and boolean expressions. For that reason we use the Data.Boolean package. Instead of if-then-else you are required to use ifB when writing JavaScript.

ifB (n `mod` 5 ==* 0)
    (do
      c # translate (-u * 0.75, 0)
      c # rotate (-2 * pi / 4)
      c # fillText (cast $ n `div` 5) (0, 0)
    ) (return ())

Note the cast operation in line five. As Haskell’s type system is more restrictive then the one used in JavaScript, we sometimes have to cast one value to another. This may seem more complicated then writing JavaScript by hand, but when using the API correctly (by not working around it) compile time errors can show mistakes in the code early.

Getting back to the initial code block: How do we render the other 59 lines of the clock face? We just wrap this code into a function. Of course, we do this at JavaScript level.

renderClockFaceLine <- function $ \
        ( c :: JSCanvas
        , u :: JSNumber
        , n :: JSNumber) -> do
  ...

We have just created the JavaScript function renderClockFaceLine with three parameters. So lets render the complete clock face using the forEach-method provided by arrays.

c # save
c # rotate (2 * pi / 4) -- 0 degrees is at the top
-- Draw all hour lines.
lines <- array [1..60::Int]
lines # forEach $ \n -> do
  c # save
  c # rotate ((2 * pi / 60) * n)
  renderClockFaceLine $$ (c, u, n)
  c # restore
c # restore -- Undo all the rotation.

The array combinator converts the list into a JavaScript array. The supplied function for the loop body takes the current element as a parameter. In the loop body you can see how the $$-operator is used just as the $-operator in Haskell to apply a JavaScript function to arguments. As the usefulness of partial application is questionable in the context of deep embedded JavaScript, we only allow uncurried functions.

Using these techniques we can render the clock with about 90 lines of Haskell.

clockJS :: JS A (JSFunction () ())
clockJS = function $ \() -> do
  -- Renders a single line (with number) of the clock face.
  renderClockFaceLine <- function $ \
        ( c :: JSCanvas
        , u :: JSNumber
        , n :: JSNumber) -> do
    c # save
    -- Draw one of the indicator lines
    c # beginPath
    c # moveTo (0, -u * 1.0)
    ifB (n `mod` 5 ==* 0)
        (c # lineTo (0, -u * 0.8)) -- Minute line
        (c # lineTo (0, -u * 0.9)) -- Hour line
    ifB (n `mod` 15 ==* 0)
        (c # setLineWidth 8 ) -- Quarter line
        (c # setLineWidth 3 ) -- Non-Quarter line
    c # stroke
    c # closePath
    -- Draw of the hour numbers
    ifB (n `mod` 5 ==* 0)
        (do
          c # translate (-u * 0.75, 0)
          c # rotate (-2 * pi / 4)
          c # fillText (cast $ n `div` 5) (0, 0)
        ) (return ())
    c # restore
  -- Renders a single clock pointer.
  renderClockPointer <- function $ \
        ( c :: JSCanvas
        , u :: JSNumber
        , angle :: JSNumber
        , width :: JSNumber
        , len :: JSNumber) -> do
    c # save
    c # setLineCap "round"
    c # rotate angle
    c # setLineWidth width
    c # beginPath
    c # moveTo (0, u * 0.1)
    c # lineTo (0, -u * len)
    c # stroke
    c # closePath
    c # restore
  -- Renders the clocks pointers for hours, minutes and seconds.
  renderClockPointers <- function $ \(c :: JSCanvas, u :: JSNumber) -> do
    (h, m, s) <- currentTime
    c # save
    c # setLineCap "round"
    -- Hour pointer
    renderClockPointer $$
      (c, u, (2 * pi / 12) * ((h `mod` 12) + (m `mod` 60) / 60), 15, 0.4)
    -- Minute pointer
    renderClockPointer $$
      ( c, u, (2 * pi / 60) * ((m `mod` 60) + (s `mod` 60) / 60), 10, 0.7)
    -- Second pointer
    c # setStrokeStyle "red"
    renderClockPointer $$ ( c, u, (2 * pi / 60) * (s `mod` 60), 4, 0.9)
    -- Restore everything
    c # restore
  -- Renders the complete face of the clock, without pointers.
  renderClockFace <- function $ \(c :: JSCanvas, u :: JSNumber) -> do
    c # save
    c # rotate (2 * pi / 4) -- 0 degrees is at the top
    -- Draw all hour lines.
    lines <- array [1..60::Int]
    lines # forEach $ \n -> do
      c # save
      c # rotate ((2 * pi / 60) * n)
      renderClockFaceLine $$ (c, u, n)
      c # restore
    c # restore -- Undo all the rotation.
  -- Renders the complete clock.
  renderClock <- continuation $ \() -> do
    u <- clockUnit
    (w,h) <- canvasSize
    c <- context
    -- Basic setup
    c # save
    c # setFillStyle "black"
    c # setStrokeStyle "black"
    c # setLineCap "round"
    c # setTextAlign "center"
    c # setFont ((cast $ u * 0.1) <> "px serif")
    c # setTextBaseline "top"
    c # clearRect (0,0) (w,h)
    c # translate (w / 2, h / 2)
    -- Draw all hour lines.
    renderClockFace $$ (c, u)
    -- Draw the clock pointers
    renderClockPointers $$ (c, u)
    c # restore
    return ()
  window # setInterval (goto renderClock) 1000
  -- and draw one now, rather than wait till later
  goto renderClock ()

  return ()

Using the sunroofCompileJSA function we can compile the deep embedded JavaScript into a string of actual JavaScript.

sunroofCompileJSA def "main" clockJS >>= writeFile "main.js"

The compiled string will contain a function main that executes our JavaScript. This is then called in the HTML file to execute.

There are a few small utilities used in the code. The current time is perceived by currentTime which uses the JavaScript date API provided by the module Language.Sunroof.JS.Date.

currentTime :: JS A (JSNumber, JSNumber, JSNumber)
currentTime = do
  date <- newDate ()
  h <- date # getHours
  m <- date # getMinutes
  s <- date # getSeconds
  return (h, m, s)

Note that this will literally copy the JavaScript produced by currentTime to where it is used, because it is not abstracted to a function in JavaScript. Every time you write Sunroof code that is not wrapped in a function, the Haskell binding will work like a macro.

The other helpers are just shortcuts to get certain values:

canvas :: JS A JSObject
canvas = document # getElementById "canvas"

context :: JS A JSCanvas
context = canvas >>= getContext "2d"

clockUnit :: JS A JSNumber
clockUnit = do
  (w, h) <- canvasSize
  return $ (maxB w h) / 2

canvasSize :: JS A (JSNumber, JSNumber)
canvasSize = do
  c <- jQuery "#canvas"
  w <- c # invoke "innerWidth" ()
  h <- c # invoke "innerHeight" ()
  return (w, h)

You can see the clock in action here.

As you can see Sunroof mirrors JavaScript closely, and allows access to the capabilities a browser provides. But is this Haskell for Haskell’s sake? We do not think so:

  • Sunroof is a deeply embedded DSL, so it is easy to write functions that generate custom code.
  • Sunroof provides some level of type safely on top of JavaScript, including typed arrays, finite maps, functions and continuations.
  • Sunroof also offers an abstraction over the JavaScript threading model, by providing two types of threads, atomic and (cooperatively) blocking. On top of this, Sunroof provides some Haskell concurrency patterns
    like MVar or Chan (JSMVar and JSChan).
  • Furthermore, the sunroof-server package offers a ready to use web-server to deploy generated JavaScript on the fly. It enables you to interleave Haskell and JavaScript computations as needed, through synchronous or asynchronous remote procedure calls.

A number of examples and a tutorial is provided on GitHub. Their Haskell sources can be found on github, they are part of the sunroof-examples package.

The Kansas University Rewrite Engine (KURE)

Friday, June 8th, 2012

The Kansas University Rewrite Engine (KURE) is a Haskell-hosted DSL for strategic programming. We`ve just released the third version of KURE, which adds lenses for navigation and a variant set of combinators to make change detection easier.

This post just overviews the basics, and gives a simple example of usage.

KURE Basics

KURE is based around the following data type:

data Translate c m a b = Translate {apply :: c -> a -> m b}

translate :: (c -> a -> m b) -> Translate c m a b
translate = Translate

There`s a lot of type parameters, but the essential idea is that Translate represents a transformation that can be applied to a value of type a in a context c, and produces a value of type b in the monad m. Actually, we require m to be a MonadPlus, as this allows us to encode notions of success and failure, which are integral to strategic programming. Specifically, mzero represents failure and mplus is a “catch” for both mzero and fail. To avoid clutter we`ll omit the class constraints, but just imagine that wherever you see an m there`s a (MonadPlus m => ...) to go with it.

We also define a synonym for the special case when the result and argument type coincide:

type Rewrite c m a = Translate c m a a

Translate itself forms a monad (and an arrow, and a bunch of other structures besides), which provides us with a lot of combinators for free. Two key definitions are composition and bind:

(>>>) :: Translate c m a b -> Translate c m b d -> Translate c m a d
t1 >>> t2 = translate $ \ c -> apply t1 c >=> apply t2 c

(>>=) :: Translate c m a b -> (b -> Translate c m a d) -> Translate c m a d
t >>= f = translate $ \ c a -> do b <- apply t c a
                                  apply (f b) c a

Observe the difference: composition takes the result of the first translation as the argument to the second translation, whereas bind uses the result to determine the second translation, but then applies that second translation to the original argument.

Another useful combinator is <+> (from the ArrowPlus class), which acts as a catch for Translate:

(<+>) :: Translate c m a b -> Translate c m a b -> Translate c m a b
t1 <+> t2 = translate $ \ c a -> apply t1 c a `mplus` apply t2 c a

We can now write strategic programming code, such as the classic try combinator:

tryR :: Rewrite c m a -> Rewrite c m a
tryR r = r <+> idR

Where idR is the identity rewrite:

idR : Rewrite c m a
idR = translate $ \ _ -> return

Finally, one combinator new to this version of KURE is sequential composition of rewrites that allows one rewrite to fail:

(>+>) :: Rewrite c m a -> Rewrite c m a -> Rewrite c m a

Example: Arithmetic Expressions with Fibonacci

Now let`s consider an example. Take a data type of arithmetic expressions augmented with a Fibonacci primitive:

data Arith = Lit Int | Add Arith Arith | Sub Arith Arith | Fib Arith

To keep things simple, we`ll work with an empty context, and use Maybe as our MonadPlus:

type RewriteA = Rewrite () Maybe Arith

Let`s start with some rewrites that perform basic arithmetic simplification:

addLitR :: RewriteA
addLitR = do Add (Lit m) (Lit n) <- idR
             return (Lit (m + n))

subLitR :: RewriteA
subLitR = do Sub (Lit m) (Lit n) <- idR
             return (Lit (m - n))

We`re exploiting the fact that Translate is a monad to use do-notation – something we have found extremely convenient. If the pattern match fails, this will just trigger the fail method of the monad, which we can then catch as desired.

Using >+>, we can combine these two rewrites into a single rewrite for arithmetic simplification:

arithR :: RewriteA
arithR = addLitR >+> subLitR

Next a more interesting rewrite, unfolding the definition of Fibonacci:

fibLitR :: RewriteA
fibLitR = do Fib (Lit n) <- idR
             case n of
               0  ->  return (Lit 0)
               1  ->  return (Lit 1)
               _  ->  return (Add (Fib (Sub (Lit n) (Lit 1)))
                                  (Fib (Sub (Lit n) (Lit 2)))
                             )

Tree Traversals

Thus far, we`ve only discussed rewrites that apply to the entire data structure we`re working with. But a key feature of KURE (and strategic programming) is the ability to traverse a structure applying rewrites to specific locations. For example, the anyR combinator applies a rewrite to each immediate child of a node, succeeding if any of those rewrites succeed:

anyR :: RewriteA -> RewriteA

At first glance this might sound simple, but there are a number of issues. Most notably, what if the children have distinct types from each other and their parent? How should such a combinator be typed? This isn`t an issue in this simple Fibonacci example, as there is only one type (Arith), but in general you could have an AST with multiple mutually recursive non-terminals. KURE solves this by constructing a sum data type of all non-terminals in the AST, and having traversal combinators operate over this data type (using Associated Types to specify the sum type for each non-terminal). This is the most significant feature of KURE, but it`d take too long to explain the details here. You can read about it in either of the following papers:

Using the anyR combinator (amongst others), KURE defines various traversal strategies (we just give the specialised types here):

anybuR :: RewriteA -> RewriteA
anybuR r = anyR (anybuR r) >+> r

innermostR :: RewriteA -> RewriteA
innermostR r = anybuR (r >>> tryR (innermostR r))

anybuR traverses a tree in a bottom-up manner, applying the rewrite to every node, whereas innermostR performs a fixed-point traversal, continuing until no more rewrites can be successfully applied. For example, we can define an evaluator for Arith using this strategy:

evalR :: RewriteA
evalR = innermostR (arithR >+> fibLitR)

Release

KURE 2.0.0 is now available on Hackage.

You can find this Fibonacci example, and several others, bundled with the source package. For a non-trivial example, KURE is being used as the underlying rewrite engine for the HERMIT tool. HERMIT hasn`t been released yet, but you can read about it in this paper:

Introducing the HERMIT Equational Reasoning Framework

The paper also describes how KURE uses lenses.

Kansas Lava

Sunday, November 6th, 2011

We are please to announce the first release of Kansas Lava, as well as the first release of Kansas Lava Cores.

Kansas Lava is Haskell library for simulating hardware and generating VHDL, in the spirit of Chalmers Lava and Xilinx Lava. We make extensive use of associated type functions, and other GHC extensions.

Kansas Cores are a set of libraries that use Kansas Lava to various build hardware components like UARTs and an LCD driver, as well as a monad and simulator for the Spartan3e.

Both are now available on hackage.

Kansas Lava has various online resources. The Kansas Lava webpage is

http://ittc.ku.edu/csdl/fpg/Tools/KansasLava

A video walkthrough of our tutorial has been started, and is available on youtube.

http://www.youtube.com/playlist?list=PL211F8711E3B3DF9C

The website for the functional programming group at KU is

http://ittc.ku.edu/csdl/fpg/Home

Kansas Lava Team @ KU

Robbing Hood?

Friday, April 2nd, 2010

The Kansas Lava team have been looking into improving Haskell debugging tools in order to tackle more complex Lava circuits. As part of this effort, we dusted off Hood, a small post-mortem debugger developed for GHC 4.X at OGI in 1999. Hood has now been ported to GHC 6.X, and re-released on hackage. Watch this space for Hood extensions in the coming months.

Hood is based on the concept of observation of intermediate data structures, rather than the more traditional stepping and variable examination paradigm used by imperative language debuggers. It can observe base types (Int, Bool, Float, etc.), finite and infinite structures (lists, trees, arrays, etc.), functions, and monadic actions. Notably, Hood preserves the type and strictness properties of the functions under observation, meaning your program can be debugged without affecting its semantics. Best of all, Hood can be extended to observe custom data types with simple instance declarations.

You can find more information, including examples and a tutorial, on the new Hood webpage:

http://www.ittc.ku.edu/csdl/fpg/Hood

We hope you find it useful!
Andrew Farmer, Andy Gill

ChalkBoard Release

Wednesday, December 2nd, 2009

CSDL and the FPG at KU are please to announce a new release of the experimental image description language ChalkBoard.

ChalkBoard is a Haskell hosted Domain Specific Language (DSL) for image generation and processing. The basic structure is a chalk board, a two-dimensional canvas of values, typically colors. Chalkboard provides the usual image processing functions (masking, overlaying, function mapping, cropping, warping, rotating) as well as a few more unusual ones. Images can be imported into Chalkboard, as first-class color chalk boards. Chalkboard also provides combinators for drawing shapes on directly on boards. The system is based loosely on Pan, but the principal image type, a Board, is abstract.

ChalkBoard is experimental, and everything might change! The primary concepts (functor based transformations of images, OpenGL acceleration) will remain, but we are still trying to balance and tune our observable sub-language. Applicative functors are also sure to follow, and many more experiments are needed.

ChalkBoard is available from the Haskell package server hackage. The ChalkBoard webpage is

http://www.ittc.ku.edu/csdl/fpg/ChalkBoard

Kevin Matlage, Andy Gill
The ChalkBoard Team