What is Weak Head Normal Form?

Introduction

Lazy languages provide a way for developers to define expressions without necessarily forcing them to evaluate immediately. Rather than provide an immediate value, these languages will generate a thunk instead.

Show me

If you load up GHCi and bind an expression to a name:

λ> let five = 2 + 3 :: Int

We can check if this expression has been evaluated or not by using sprint. If the expression hasn’t been evaluated, sprint will show us an underscore _. This is how GHCi tells us that an expression is unevaluated.

λ> :sprint five
five = _

five is currently a thunk.

If we do force the expression to evaluate and then re-run this test, sprint tells us a different story:

λ> five
5
λ> :sprint five
five = 5

five has now been evaluated and as such, sprint is telling us the value.

Weak Head Normal Form

With some knowledge of thunks under our belt, we can move onto Weak Head Normal Form or WHNF. If we take our five example back to unevaluated, and use a mixture of take and cycle to generate a list of five, we’ll end up with another thunk:

λ> let five = 2 + 3 :: Int
λ> let fiveFives = take 5 $ cycle [five]
λ> :sprint fiveFives
fiveFives = _

If we use seq on this list, fiveFives we end up with two thunks getting concatenated.

λ> seq fiveFives []
[]
λ> :sprint fiveFives
fiveFives = _ : _

seq has evaluated fiveFives to head normal form here. In fact, hoogle says the following about seq:

Evaluates its first argument to head normal form, and then returns its second argument as the result.

seq is defined as follows

seq :: a -> b -> b

So, seq forced the list to be evaluated but not the components that make up the list. This is known as weak head normal form.

In summary

From this stack overflow question:

An expression in weak head normal form has been evaluated to the outermost data constructor or lambda abstraction (the head).

Mounting your Android phone with mtp

This post is really just a short-cut bookmark to the Arch documentation on the topic. This post will walk through the steps required to mount your Android phone using FUSE.

Install the package mtpfs if you don’t already have it on your system. After that’s installed, you’ll need to uncomment the line user_allow_other in your /etc/fuse.conf file.

Plug your phone in and issue the following.

To mount your device:

$ mtpfs -o allow_other /media/your_mountpoint_here

Once you’re done, you can unmount with:

$ fusermount -u /media/your_mountpoint_here

Getting started with OpenMP

Introduction

OpenMP is an API for performing shared memory multiprocessing tasks in a variety of different languages and platforms. OpenMP hides away the complexities of parallel programming so that the developer can focus on writing their applications.

In today’s post, I’ll run through building OpenMP applications, some examples and what the internal #pragma statements mean.

Building

Building applications against the OpenMP API is relatively simple. Using GCC:

$ gcc -o progname -fopenmp progname.c

Interestingly, the maximum number of threads that the framework will use (at runtime) can be controlled by setting the OMP_NUM_THREADS environment variable. This can be overridden in your programs with the omp_set_num_threads.

Hello MP!

The standard “Hello, World” application that you’ll find around the web is as follows:

#include <omp.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
  int th_id, nthreads;

  #pragma omp parallel private(th_id)
  {
    th_id = omp_get_thread_num();
    printf("Hello world from thread %d\n", th_id);

    #pragma omp barrier
    if (th_id == 0) {
      nthreads = omp_get_num_threads();
      printf("There are %d threads\n", nthreads);
    }
  }

  return EXIT_SUCCESS;
}

Immediately, you’ll notice the use of #pragma directives throughout the source. These are used to control the behaviour of the OpenMP API within your application. I’ll go through a few of these below.

#pragma omp parallel private forces the variable th_id to be private to the thread that’s executing. omp_get_thread_num (as the name suggests) gives you back the current thread number. #pragma omp barrier tells OpenMP to synchronize all threads to that point.

Some example invocations of this program look as follows:

$ OMP_NUM_THREADS=2 ./hello
Hello world from thread 0
Hello world from thread 1
There are 2 threads

$ OMP_NUM_THREADS=4 ./hello
Hello world from thread 0
Hello world from thread 3
Hello world from thread 2
Hello world from thread 1
There are 4 threads

Moving on, we’ll take a look at a few of the #pragma directives you can use to control OpenMP.

pragmas

All of the following directives in the table are applied in your source code with a #pragma omp prefix.

References

There is plenty of information around on this particular topic. Take a look at the following links to dig into these topics even further:

• Intel support for OpenMP
• OpenMP Examples
• GCC OpenMP Manual

Functional Reactive Programming with Yampa

Introduction

Functional reactive programming is a programming paradigm that allows a developer to express interesting events as a stream. Developers place pieces of code in this stream called signals which allow them to target and respond to the events that matter to them.

Haskell offers a library called Yampa for this field of computing. Yampa uses the Arrow abstraction to allow developers to build/compose their signals.

In today’s post, I’ll take you through a few of the pieces I’ve learned about Yampa so that you can get started quicker.

What is a Signal Function?

A signal function is what you’ll put in the pipeline or stream of events so that you’re able to respond to events and ultimately change the course of execution. A signal function is defined as having both input and output as so:

data SF a b

I found it easier to think that you’ll write functions that return signal functions. Better yet, you’ll write arrow compositions by combining simpler arrows (to make more complex arrows) that will end up as an SF type.

Built in Signal Functions

Out of the box, Yampa gives you some functions returning SF types all ready for you to put to work.

The first of these functions is identity.

identity :: SF a a

As the type signature suggests, identity will return a signal function that will take the input that is given to it and return it.

The next of these functions is constant.

constant :: b -> SF a b

constant wants an initial argument. It will return a signal function that gives you back that initially supplied value.

The next function is time.

time :: SF a Time

This function is a little more interesting. Rather than echoing back to us information that’s been supplied, time will give you the time that has passed. When moving through a stream of events, you’ll always be working with respect to dt or time that has passed.

Running Signal Functions

Yampa provides us with the embed function which gives us the ability to run our signal functions over a pre-defined stream (or array).

embed :: SF a b
      -> (a, [(DTime, Maybe a)])
      -> [b]

The embed function says: give me a signal function SF a b and a pair (a, [(DTime, Maybe a)]) and it will give you back the resulting modified stream [b]. The second argument to this function could use a little more definition:

The first item in the pair, a is an initial value for the stream. It’s where the stream starts. If you’re dealing with mouse data, this could be (0, 0) as the origin point of the mouse cursor or RobotStateOff if you’re controlling a robot or 0 if you’re just animating an integer.

The second item in the pair, [(DTime, Maybe a)] is a list of the values to supply to your stream. The pair at each index of the list wants to know DTime (how much time has passed) and Maybe a (the associated value at this time).

A few practical examples may help clear up my explanations. To make a plain-old-number-example a little more interesting - let’s say that we’re trying to model the temperature of a cup of coffee as it cools down. We’ll get sensor data from our virtual thermometer every 60 seconds. We can model our sensor data like so:

let sensorData = (80.0, [(60.0, Just 74.6), (60.0, Just 68.9), (60.0, Just 61.5)])

So this “sensor data” that we’ve captured from somewhere is saying that:

• The coffee started at 80 degrees
• After 60 seconds, the temperature dropped to 74.6
• Next 60 seconds, to 68.9
• Next 60 seconds, to 61.5

Then we turned our sensor off. We didn’t collect any more data than this.

Using the functions above:

λ> embed (constant 77) sensorData
[77,77,77,77]
λ> embed identity sensorData
[80.0,74.6,68.9,61.5]
λ> embed time sensorData
[0.0,60.0,120.0,180.0]

As we went through above. constant just gave us a set of 77’s back. This is what we supplied as the input to constant. identity gave us each of the temperature readings and time gave us the time intervals that had passed.

Using embed is a great way to see how signal functions react to test data, but what we really want to do is create our own signal functions and run them through.

Creating signal functions

We compose some of the more fundamental, pre-provided signal functions to make more complex scenarios. In this case, we’re going to say that the cup of coffee loses 0.001 degrees for every second that passes.

In this example, we’ll say that the coffee cools down at 1 degree per second. Pretty unrealistic, but it’ll do for the purposes of this example.

let cooling t0 = (constant (-1) >>> integral) >>^ (+ t0)

Breaking this down, we’re integrating our “cool-down constant” of -0.001 over time using integral and then applying this to the original temperature passed in (+ t0). Testing this out now using embed and some new test data:

λ> embed (cooling (80.0 :: Double)) (Nothing, take 20 $ cycle [(1.0, Nothing)])
[80.0,79.0,78.0,77.0,76.0,75.0,74.0,73.0,72.0,71.0,70.0,69.0,68.0,67.0,66.0,65.0,64.0,63.0,62.0,61.0,60.0]

We can see, using our cooling function that the temperature of our coffee is getting colder at a constant rate. We can re-write this function using arrow notation and a proc block to make it a little more readable.

cooling :: Double -> SF () (Double)
cooling t0 = proc input -> do
               t0' <- integral >>^ (+ t0) -< -1
               returnA -< t0'

Our function takes the current temperature of the coffee. It returns a SF () (Double), which means that it doesn’t have any input to work with (), but will be returning our new temerature (Double).

switch; the reactive part

The whole idea of this programming paradigm is to respond to changes. Whilst we’ve been modifying attributes of our program with respect to time, we really need to conditionally change course at runtime. This is where switch comes into the picture.

switch :: SF a (b, Event c)
       -> (c -> SF a b)
       -> SF a b

From the Yampa page on switches.

A switch in Yampa provides change of behavior of signal functions (SF) during runtime. The function ‘switch’ is the simplest form which can only be switched once. The signature is read like this: “Be a SF which is always fed a signal of type ‘in’ and returns a signal of type ‘out’. Start with an initial SF of the same type but which may also return a transition event of type ‘Event t’. In case of an Event, Yampa feeds the variable ‘t’ to the continuation function ‘k’ which produces the new SF based on the variable ‘t’, again with the same input and output types.”

Going through the parameters, switch expects a signal function SF a (b, Event c). This function is what determines if we actually need to switch or react to a particular condition. The next input parameter (c -> SF a b) is a function producing a signal function. It’s what we’ll switch to if we receive the correct event information supplied from the output of the first parameter.

We’ll create a new signal function that will employ both switch and our original cooling function so that when the temperature reaches a certain point, it’ll just maintain that temperature. Sort of like when the temperature reaches room temperature.

coolingWithFloor :: Double -> SF () (Double)
coolingWithFloor t0 = switch cooling' atRoomTemp
    where cooling' = proc _ -> do
                       t' <- cooling t0 -< ()
                       e <- edge -< t' <= 18
                       returnA -< (t', e `tag` t')
          atRoomTemp _ = (constant 18)

There’s a little bit to explain in this one. cooling' is our new cooling function. It still uses the original cooling function under the covers. cooling' then uses edge which takes a Bool as its input and returns a Event (). We finally prepare the signal function for return.

The use of the tag function will just perform an fmap of t' over e. What’s interesting is that if the case is met in the call to edge, we’ll receive back a Event a - otherwise it’ll just be NoEvent. This is really the meat and potatoes as to what’s driving the decision that we’re leaving up to switch.

Our test that we’re performing is t' <= 18, so it makes sense that the function that we’d switch to just sends 18 out. Once the temperature reaches 18, that’s where it’ll stay. embed confirms our requirements through execution.

λ> embed (coolingWithFloor 25)
         ((), take 10 $ cycle [(1.0, Just ())])
[25.0,24.0,23.0,22.0,21.0,20.0,19.0,18.0,18.0,18.0,18.0]

There are other alternatives to switch as well that each have their own nuances. rSwitch allows you to specify the signal function to move to using the Event value. kSwitch allows you to freeze a signal function and use its state in a continuation, later on.

reactimate

Up until this point, we’ve been running all of our simulations through embed. This has been good for our testing purposes however Yampa also provides the reactimate function, which guided by our configurations will manage the stream that our signal functions work on - for us.

reactimate
  :: IO a
     -> (Bool -> IO (DTime, Maybe a))
     -> (Bool -> b -> IO Bool)
     -> SF a b
     -> IO ()

reactimate takes 4 arguments.

IO a is an IO action that performs the initialisation for the process. Here’s where you’d get ready for the stream to start.

The second parameter is our input function. Ignore the Bool input argument. From all of the reading that I’ve done, this isn’t used. This parameter will be repeatedly called by reactimate to feed the stream with sensor data.

The third parameter is our output function. What do you want to do with the data? What ever it is, it goes into this function. The Bool input argument is again ignored however, the output of this action determines if reactimate continues working. True will stop the process for us.

The final input parameter is our signal function that’s processing the stream.

Here is coolingWithFloor being hosted by reactimate, with the current temperature being written to the console.

λ> reactimate (return ())
              (\_ -> return (1.0, Nothing))
              (\_ b -> (putStrLn $ show b) >> return False)
              (coolingWithFloor 25.0)
25.0
24.0
23.0
22.0
21.0
20.0
19.0
18.0
18.0
18.0
18.0

That’s it for today’s post on functional reactive programming in Haskell using Yampa.

Practical Arrow Usage

Introduction

Arrows provide you with a way to represent computation. They provide some interesting compositional combinations for building more complex operations that you’re not going to find for Monads.

The Arrow Class is defined in the base libraries and can be imported from Control.Arrows. From Haskell.org’s Arrow page:

Arrows are a new abstract view of computation, defined by John Hughes [Hug00]. They serve much the same purpose as monads – providing a common structure for libraries – but are more general. In particular they allow notions of computation that may be partially static (independent of the input) or may take multiple inputs. If your application works fine with monads, you might as well stick with them. But if you’re using a structure that’s very like a monad, but isn’t one, maybe it’s an arrow.

Some interesting links on the topic follow:

• Haskell Wiki page on Arrows
• Arrows on Haskell.org
• Understanding Arrows
• The Arrow Tutorial on Haskell Wiki

If you’re interested in learning the theory behind Arrows or want to gain a deeper insight, I strongly suggest that you read through the above links.

Today’s post is going to take you through Arrows in practice when working in Haskell.

returnA

returnA gives you the identity arrow. It’s what you use in place of return that you would use in monadic contexts.

λ> :t returnA
returnA :: Arrow a => a b b
λ> :t returnA 5
returnA 5 :: Num b => b

arr

arr will take an ordinary function and make an arrow out of it.

λ> let a1 = arr (+)
λ> :t a1
a1 :: (Arrow a, Num b) => a b (b -> b)

Invoking your arrow is simple now with returnA and arr.

λ> a1 (returnA 5) 6
11

»>

»> performs left to right composition on arrows. This is very similar to what »= provides for monads.

λ> let a1 = arr (+5)
λ> let a2 = arr (*2)
λ> a1 >>> a2 $ 3
16

The next few functions that I’ll list here will work on pairs of values. This is where arrows really start to pull away from monads in terms of compositional capability. For example’s sake, I’ve defined q as a simple pair of integers:

λ> let q = (1,2)

first

first feeds the first element of a pair into the arrow for processing and leaves the second item untouched.

λ> first a1 q
(6,2)

second

second feeds the second element, but leaves the first untouched.

λ> second a1 q
(1,7)

***

*** will feed the first element of a pair through the first arrow, the second element will go through the second arrow. In the example below, the value 1 goes through the arrow a1 and 2 goes through a2.

λ> a1 *** a2 $ q
(6,4)

&&&

&&& will duplicate the input given to it and feed a copy to each arrow, returning a pair.

λ> a1 &&& a2 $ 5
(10,10)

proc

proc (arrow abstraction) builds a lambda that constructs an arrow as opposed to a function. proc allows you to build expressions (or arrows) using arrow notation.

{-# Language Arrows #-}

import Control.Arrow

addA :: Arrow a => a b Int -> a b Int -> a b Int
addA f g = proc x -> do
            y <- f -< x
            z <- g -< x
            returnA -< y + z

In this example, the type signature for addA is asking for two arrows from b to Int (a b Int) and will return an arrow of the same type.

The proc block has a lambda variable of x which is applied when the arrow is invoked. Remember, we’re only constructing an arrow here - not running it (yet).

The following lines make use of a new operator -< (arrow application). It feeds the value of an expression into an arrow. I think it helps to look at it like this:

variable binding pattern <- arrow -< pure expression giving arrow input

Invoking addA is done like so:

λ> let a1 = arr (+4)
λ> addA a1 a1 (returnA 3)
14

Here we have our arrow a1 that is just (+4). a1 is being supplied as the first and second parameter of addA. Lastly, we give addA our pure value returnA 3.

So, you can see here that (+4) has been applied to 3, and then (+4) gets applied to 3. Yes, I said the same thing twice. It’s only because I’ve used a1 as both input parameters. The output of these arrow invocations is then added together, to give the result of 14. Our pure value is being supplied by returnA 3.

These have just been some very fundamental examples of arrow usage. Read up some more on them using the links I’ve provided above. You can see how they’re quite a powerful construct.