Planet Fp-Syd

I just released accelerate 0.9.0.0 on Hackage. This is the version that has been available from the GitHub repository for a while (supporting shape polymorphism, stencil computations, block I/O, and much more), but adapted such that it works with the forthcoming GHC 7.4.1 release. (I tested it with 7.4.1 RC2).

Permalink | Leave a comment  »

Free, nicely presented textbooks with good distribution have got quite an appeal.

Begun it has RT @stevedekorte: First version of Io Programming Guide available for free on iTunes book store itunes.apple.com/us/book/io/id4…

— Mac (@wmacgyver) January 26, 2012

Permalink | Leave a comment  »

I'm currently working on converting my http-proxy library from using the Data.Enumerator package to Data.Conduit (explanation of why in my last blog post).

During this conversion, I have been studying the sources of the Warp web server because my http-proxy was originally derived from the Enumerator version of Warp. While digging through the Warp code I found the following code (and comment) which is used to parse the number provided in the Content-Length field of a HTTP header:

  -- Note: This function produces garbage on invalid input. But serving an
  -- invalid content-length is a bad idea, mkay?
  readInt :: S.ByteString -> Integer
  readInt = S.foldl' (\x w -> x * 10 + fromIntegral w - 48) 0

The comment clearly states that that this function can produce garbage, specifically if the string contains anything other than ASCII digits. The comment is also correct that an invalid Content-Length is a bad idea. However, on seeing the above code, and remembering something I had seen recently in the standard library, I naively sent the Yesod project a patch replacing the above code with a version that uses the readDec function from the Numeric module:

  import Data.ByteString (ByteString)
  import qualified Data.ByteString.Char8 as B
  import qualified Numeric as N

  readInt :: ByteString -> Integer
  readInt s =
      case N.readDec (B.unpack s) of
          [] -> 0
          (x, _):_ -> x

About 3-4 hours after I submitted the patch I got an email from Michael Snoyman saying that parsing the Content-Length field is a hot spot for the performance of Warp and that I should benchmark it against the code I'm replacing to make sure there is no unacceptable performance penalty.

That's when I decided it was time to check out Bryan O'Sullivan's Criterion bench-marking library. A quick read of the docs and bit of messing around and I was able to prove to myself that using readDec was indeed much slower than the code I wanted to replace.

The initial disappointment of finding that a more correct implementation was significantly slower than the less correct version quickly turned to joy as I experimented with a couple of other implementations and eventually settled on this:

  import Data.ByteString (ByteString)
  import qualified Data.ByteString.Char8 as B
  import qualified Data.Char as C

  readIntTC :: Integral a => ByteString -> a
  readIntTC bs = fromIntegral
          $ B.foldl' (\i c -> i * 10 + C.digitToInt c) 0
          $ B.takeWhile C.isDigit bs

By using the Integral type class, this function converts the given ByteString to any integer type (ie any type belonging to the Integral type class). When used, this function will be specialized by the Haskell compiler at the call site to to produce code to read string values into Ints, Int64s or anything else that is a member of the Integral type class.

For a final sanity check I decided to use QuickCheck to make sure that the various versions of the generic function were correct for values of the type they returned. To do that I wrote a very simple QuickCheck property as follows:

  prop_read_show_idempotent :: Integral a => (ByteString -> a) -> a -> Bool
  prop_read_show_idempotent freader x =
      let posx = abs x
      in posx == freader (B.pack $ show posx)

This QuickCheck property takes the function under test freader and QuickCheck will then provide it values of the correct type. Since the function under test is designed to read Content-Length values which are always positive, we only test using the absolute value of the value randomly generated by QuickCheck.

The complete test program can be found on Github in this Gist and can be compiled and run as:

  ghc -Wall -O3 --make readInt.hs -o readInt && ./readInt

When run, the output of the program looks like this:

  Quickcheck tests.
  +++ OK, passed 100 tests.
  +++ OK, passed 100 tests.
  +++ OK, passed 100 tests.
  Criterion tests.
  warming up
  estimating clock resolution...
  mean is 3.109095 us (320001 iterations)
  found 27331 outliers among 319999 samples (8.5%)
    4477 (1.4%) low severe
    22854 (7.1%) high severe
  estimating cost of a clock call...
  mean is 719.4627 ns (22 iterations)

  benchmarking readIntOrig
  mean: 4.653041 us, lb 4.645949 us, ub 4.663823 us, ci 0.950
  std dev: 43.94805 ns, lb 31.52653 ns, ub 73.82125 ns, ci 0.950

  benchmarking readDec
  mean: 13.12692 us, lb 13.10881 us, ub 13.14411 us, ci 0.950
  std dev: 90.63362 ns, lb 77.52619 ns, ub 112.4304 ns, ci 0.950

  benchmarking readRaw
  mean: 591.8697 ns, lb 590.9466 ns, ub 594.1634 ns, ci 0.950
  std dev: 6.995869 ns, lb 3.557109 ns, ub 14.54708 ns, ci 0.950

  benchmarking readInt
  mean: 388.3835 ns, lb 387.9500 ns, ub 388.8342 ns, ci 0.950
  std dev: 2.261711 ns, lb 2.003214 ns, ub 2.585137 ns, ci 0.950

  benchmarking readInt64
  mean: 389.4380 ns, lb 388.9864 ns, ub 389.9312 ns, ci 0.950
  std dev: 2.399116 ns, lb 2.090363 ns, ub 2.865227 ns, ci 0.950

  benchmarking readInteger
  mean: 389.3450 ns, lb 388.8463 ns, ub 389.8626 ns, ci 0.950
  std dev: 2.599062 ns, lb 2.302428 ns, ub 2.963600 ns, ci 0.950

At the top of the output is proof that all three specializations of the generic function readIntTC satisfy the QuickCheck property. From the Criterion output its pretty obvious that the Numeric.readDec version is about 3 times slower that the original function. More importantly, all three version of this generic function are an order of magnitude faster than the original.

That's a win! I will be submitting my new function for inclusion in Warp.

Update : 14:13

At around the same time I submitted my latest version for readInt Vincent Hanquez posted a comment on the Github issue suggesting I look at the GHC MagicHash extension and pointed me to an example.

Sure enough, using the MagicHash technique resulted in something significantly faster again.

Update #2 : 2012-01-29 19:46

In version 0.3.0 and later of the bytestring-lexing package there is a function readDecimal that is even faster than the MagiHash version.

A brief history of personal computing platforms.twitpic.com/87bt3s

— Horace Dediu (@asymco) January 14, 2012

We are witnessing the transition from Windows on Intel to Unix on (mostly) ARM. It is a testament to the flexibility of the design that a system originally designed for mainframes achieves mass market appeal on resource-constrained mobile systems.

Permalink | Leave a comment  »

Below is a simple telnet client written using Haskell's new Conduit library. This library was written by Michael Snoyman the man behind the Yesod Web Framework for Haskell.

The Conduit library is a second generation approach to the problem of guaranteeing bounded memory usage in the presence of lazy evaluation. The first generation of these ideas were libraries like Iteratee, Enumerator, and IterIO. All of these first generation libraries use the the term enumerator for data producers and iteratee for data consumers. The new Conduit library calls data producers "sources" and data consumers "sinks" to make them a little more approachable.

The other big difference between Conduit and the early libraries in this space is to do with guaranteeing early clean up of potentially scarce resources like sockets. Although I have not looked in any detail at the IterIO library, both Iteratee and Enumerator simply rely on Haskell's garbage collector to clean up resources when they are no longer required. The Conduit library on the other hand uses Resource transformers to guarantee release of these resources as soon as possible.

The client looks like this (latest available here):

  import Control.Concurrent (forkIO, killThread)
  import Control.Monad.IO.Class (MonadIO, liftIO)
  import Control.Monad.Trans.Resource
  import Data.Conduit
  import Data.Conduit.Binary
  import Network (connectTo, PortID (..))
  import System.Environment (getArgs, getProgName)
  import System.IO


  main :: IO ()
  main = do
      args <- getArgs
      case args of
          [host, port] -> telnet host (read port :: Int)
          _ -> usageExit
    where
      usageExit = do
          name <- getProgName
          putStrLn $ "Usage : " ++ name ++ " host port"


  telnet :: String -> Int -> IO ()
  telnet host port = runResourceT $ do
      (releaseSock, hsock) <- with (connectTo host $ PortNumber $ fromIntegral port) hClose
      liftIO $ mapM_ (`hSetBuffering` LineBuffering) [ stdin, stdout, hsock ]
      (releaseThread, _) <- with (
                            forkIO $ runResourceT $ sourceHandle stdin $$ sinkHandle hsock
                            ) killThread
      sourceHandle hsock $$ sinkHandle stdout
      release releaseThread
      release releaseSock

There are basically three blocks, a bunch of imports at the top, the program's entry point main and the telnet function.

The telnet function is pretty simple. Most of the function runs inside a runResourceT resource transformer. The purpose of these resources transformers is to keep track of resources such as sockets, file handles, thread ids etc and make sure they get released in a timely manner. For example, in the telnet function, the connectTo function call opens a connection to the specified host and port number and returns a socket. By wrapping the connectTo in the call to with then the socket is registered with the resource transformer. The with function has the following prototype:

  with :: Resource m
       => Base m a             -- Base monad for the current monad stack
       -> (a -> Base m ())     -- Resource de-allocation function
       -> ResourceT m (ReleaseKey, a)

When the resource is registered, the user must also supply a function that will destroy and release the resource. The with function returns a ReleaseKey for the resource and the resource itself. Formulating the with function this way makes it hard to misuse.

The other thing of interest is that because a telnet client needs to send data in both directions, the server-to-client communication path and the client-to-server communication run in separate GHC runtime threads. The thread is spawned using forkIO and even though the thread identifier is thrown away, the resource transformer still records it and will later call killThread to clean up the thread.

The main core of the program are the two lines containing calls to sourceHandle and sinkHandle. The first of these lines pulls data from stdin and pushes it to the socket hsock while the second pulls from the socket and pushes it to stdout.

It should be noted that the final two calls to release are not strictly necessary since the resource transformer will clean up these resources automatically.

The experience of writing this telnet client suggests that the Conduit library is certainly easier to use than the Enumerator or Iteratee libraries.

Goanna 2.6 is now available from the download page. In this release we have focused on the usability of our Goanna Studio for Eclipse offering which at the same time increases stability and flexibility in the face of the many different configurations that are possible within the Eclipse CDT environment. Here is a summary of what has changed in this release:

- All versions

• Bounds checking for arrays of arbitrary dimension
• Bounds checking for arrays within classes, structs and unions
• Arrays of unspecified size are no longer considered to have size 0
• Constant global variables are now modelled with a value that does not change
• The constant “-1U” and others will now be modelled with an appropriately large value instead of -1
• Check FPT-misuse no longer warns about function pointers that are the result of the ternary operator (?:)
• Check ITR-uninit now works correctly for iterators that are initialized using operator=
• Check RED-unused-param no longer warns for parameters that have the GNU attribute (unused)
• Checks RED-cond-const-assign and EXP-cond-assign no longer consider “+=” and similar operators to be constant assignments
• Non-system #include files are now included in the analysis of a file that includes them.

- Goanna Studio for Visual Studio

• preprocessor macros within parentheses are expanded
• macros in comments are not expanded

- Goanna Central

• Cygwin support for windows, use –compiler-sort=cygwin to create a cygwin configuration
• Other compiler sort added, use –compiler-sort=other for an empty configuration
• Remove the dependencies on the hard to manage predefined_macro.txt files
• Predefined macros are now stored in the Goanna resource files, which are generated during configuration

- Goanna Studio for Eclipse

• Completely re-organised configuration
  • Per project configuration
  • File based (under a goanna directory in the project file system)
  • User editable, or use the Goanna Project Properties dialogs. (two way synchronisation)
• Menu item “Run Goanna on Selected File(s)” now appears when right-clicking on folders, and will analyse all files found in the selected folder.
• Cygwin toolchain support on windows

On the same day that the computing world lost Steve Jobs, the company I work for lost its own star, founder and CEO of bCODE, Michael Mak.

I remember meeting Michael in late 2005 when I first came to interview for a job with bCODE. Michael impressed me immediately with his keen intelligence and his easy going personality. As I worked with him over the years, my respect grew. I came to trust him and the rest of the management team far more than I had ever trusted any other employer. I always felt that Michael saw the employees as an important part of the company and he wouldn't do anything to further the company at the expense of the employees. This was even true when he had to retrench a third of the workforce after the global financial crisis of 2008. I saw first hand how much distress this caused him and our COO.

When Michael moved the business side of the enterprise to the US, he would still make regular trips back to visit the Sydney office. During these visits three or four of us would go out to lunch and he would regale us with tales of people he met and deals that he was working on. These were exciting times and Michael was a great motivator.

The things I will remember about Michael was his enthusiasm, his integrity, his leadership and just being a great all round guy.

My condolences to his family and his girlfriend Emily. No one will miss Michael as much as them.

Michael was 37 years old.

The Brisbane FP Group (BFPG) kindly invited me to give a talk about our work on data parallel programming in Haskell. The talk motivates the use of functional programming for parallel, and in particular, data parallel programming and explains the difference between regular and irregular (or nested) data parallelism. It also discusses the Repa library (regular data parallelism for multicore CPUs), the embedded language Accelerate (regular data parallelism for GPUs), and Data Parallel Haskell (nested data parallelism for multicore CPUs).  The slides of the presentation are available in two formats: HTML5 slideshow and PDF. Thank you to everybody who attended. Special thanks go to OJ Reeves and Tony Morris for organising everything, to Rob Manthey for producing the video, to Mincom for the venue, and to Functional IO for the sponsorship.

Permalink | Leave a comment  »

Goanna 2.5 is now available from the download page. Here’s a summary of what’s changed in this release.

- All versions

• stored filenames are now specified as relative paths, allowing the Goanna database to be used in multiple locations
• better support for Unicode source code
• the ARR-inv-index check now allows for unbounded subscripts

- Goanna Central

• license server options can be specified on the command line
• the language choice, C or C++, can be given on the command line

- Visual Studio

• clicking on a warning in a project summary navigates to the relevant code
• better support for Win64 targets
• partial compatibility with Intel Parallel Studio (on VS2005 and VS2008, Goanna does not work with projects converted to use the Intel C++ compiler)

As usual, feedback is welcome.

Do you want to know more about software security? Learn about cyber defense? Meet some of the team behind the Goanna technology from NCITA at DSR 2011 in Singapore, August 3-5. We will be giving an overview of at the Symposium on Cyber Terrorism titled “Cyber Security at Software Development Time” and highlighting some of our experiences from the NIST/SAMATE program.

Recently, MITRE introduced the Common Weakness Scoring System (CWSS) for classifying and ranking common vulnerabilities. This systems has around 18 dimensions comprising technical severity, business impact, authentication/security barriers and overall probability mentioning just a few. While this is certainly a detailed scoring system it raises the common question: “Which of the detected issues should I fix first?”.

This is not an easy question to answer for any (automated) tool. While certain classes of bugs such as buffer overflows are likely more severe than, let’s say, unused function parameters it is not guaranteed that they have a larger impact. Sometimes a buffer overflow might only happen in a very unlikely scenario in some abandoned part of the code base, while the unused function parameter stems from a copy&paste mistake within the function leading to an always wrong and potentially dangerous result.  Similarly, it is difficult for any tool to tell, which parts of the code base are more important than others.

Having said that, we developed Goanna Studio and Goanna Central with openness in mind. This means all our detected issues can be easily exported and post-processed by the end user (you can even query our internal SQLite database if you really want to), filtered according to their needs and  ranked according to your system. Moreover, we provide a mapping of all issues to the common CWE criteria and we give you the following classification:

Goanna's Impact Guidance

This 2-dimensional  classification is used for all issues detected by Goanna (see user manuals):

Severity: How serious is this issue typically?
Certainty: How confident are we that this will likely happen?

Both dimensions are based on our experience from having analyzed literally hundreds of millions of lines of code. Severity is ranked similarly to the above example, where a buffer overflow is deemed to be serious. Certainty on the other hand addresses a number of sub-dimensions: How likely is this from our experience to happen in real-life? How certain is Goanna, i.e., does the analysis conclude the issue will appear on every program part or just on a few? How sensitive is the issue to input data etc.? The combined dimensions should give you a good idea where to spend your time first. And while we are looking into integrating a CWSS ranking, we believe that less is sometimes more.

In the latest round of development we aimed for the most rock solid and sane implementation of C/C++ static analysis that we could. We did this by working on three fronts: consistency, speed and features.

As usual, all current users get the upgrade for free. If you were a trial user in the past and need a trial extension visit: http://redlizards.com/trial-extension.

Whats new in 2.4?

General improvements:

• We revamped the integer arithmetic interval analysis engine with a new algorithm which affords us increased speed and precision. So much speed that we have also added the ability to track pointer arithmetic as mentioned in the previous blog post.
• Our interval analysis engine can handle new operations: Casts, Logical operators and shift operators.
• We have enabled floating licenses in our Studio and Central products; please contact us if you are interested.

Goanna Central improvements:

• The argument –parse-error=0 is now a default, this will cause Goanna to exit with an exit code of 0 when a parse error is encountered. We have also revamped the way parse errors are handled.
• The interprocedural analysis in the Goanna Central command line is now even simpler to use and manage by conveniently specifying a user-defined folder with the argument –ipa=<project name>.  All new database files are then stored in ~/.goanna_project_store/<project name>.

Goanna Studio improvements:

• In Eclipse there is now an option to not run the tool chain compiler during analysis.
• In Eclipse there is a new menu item to jump to the currently selected projects Goanna Studio Properties page.

Renamed checks for consistency:

• ATH-div-0-aft-assign -> ATH-div-0-assign
• ATH-div-0-aft-cmp -> ATH-div-0-cmp-aft
• ATH-div-0-bef-cmp -> ATH-div-0-cmp-bef
• ATH-div-0-param-unchk -> ATH-div-0-unchk-param
• PTR-param-unchk -> PTR-unchk-param
• PTR-param-unchk-some -> PTR-unchk-param-some
• RED-const-assign-cond -> RED-cond-const-assign
• RED-const-expr-cond -> RED-cond-const-expr
• SPC-ret-stack -> MEM-stack
• builtin_ctor_dtor_leak -> COP-ctor-dtor-leak

New checks:

• ARR-inv-index-ptr - A pointer is assigned to an array, static or dynamic, and it is accessed with an index that is out of the array’s bounds.
• ARR-inv-index-ptr-pos - A pointer is assigned to an array, static or dynamic, and it is accessed with an index that may be out of the array’s bounds.
• ATH-overflow-cast - An expression is cast to a different type, resulting in an overflow or underflow of its value.
• ATH-shift-neg - The left-hand side of a right shift operation may be a negative value.
• COP-dtor-throw - An exception is thrown, or may be thrown, in a class’ destructor.
• CPU-delete-throw - An exception is thrown, or may be thrown, in an overloaded delete or delete[] operator.
• FPT-arith-address - Performing pointer arithmetic on the address of a function.
• FPT-literal - Dereferencing a function pointer that refers to a literal address.
• FPT-misuse - A function pointer is used in an invalid context.
• ITR-end-cmp-aft - An iterator is used, then compared with end().
• ITR-invalidated - An iterator is assigned to point into a container, but subsequent modifications to that container have possibly invalidated the iterator. The iterator is then used or dereferenced, which may be undefined behavior.
• ITR-mismatch-alg - A pair of iterators passed to an STL algorithm function point to different containers.
• ITR-store - A container’s begin() or end() iterator is stored and subsequently used.
• MEM-malloc-diff-type - A call to malloc tries to allocate memory based on a sizeof operator, but the target type of the call is of a different type.
• MEM-stack-ref - A stack object is returned from a function as a reference.
• PTR-arith-field - Direct access to a field of a struct using an offset from the address of the struct.
• PTR-arith-var - Invalid pointer arithmetic with an automatic variable that is neither an array nor a pointer.
• RED-cond-var-always - The value of the variable used as a condition will always evaluate to non-zero or true. This means the condition will always be met.
• RED-cond-var-never - The value of the variable used as a condition will always evaluate to zero or false. This means the condition will never be met.

slides

Over the last few months we’ve been hard at work expanding our interval analysis and writing new checks for array bounds checking. I am happy to announce that we can now detect out-of-bounds array accesses for pointers to arrays, both automatic and dynamic. We also now fully handle pointers that offset arrays, allowing us to track their values and detect some extremely hard-to-find bugs.

For example:

int arr[15];

int example(int random){
  int *p = arr;
  p += 3;

  int offset = (random > 10 ? random : 10);
  return p[offset + 4];    //'p' points to 4th element, and index will be at least 14.
}

In this code sample, the pointer ‘p’ is used to alias the global, automatic array of ints, ‘arr’. This pointer is then increased by 3, making it point to the 4th element of the array.  An int, ‘offset’ , is set to be some unknown value, but we know it is at least 10. Finally, the pointer is accessed with index (offset + 4). Since the pointer already refers to the 4th element, and we are trying to access an at least 14 elements further along, Goanna will give the following warning:

8: warning: Goanna[ARR-inv-index-ptr] Array pointer `arr' is accessed with index [17,INF]
which is out of array bounds [0,14]

Similarly, we can perform the same analysis on dynamic arrays allocated with new or malloc. We also handle different syntactic forms of array access. The following example illustrates this, as well as our ability to warn for possible, as opposed to definite index violations, from a range of possible index values that may be out of bounds:

#include <malloc.h>
#include <assert.h>

int example2(int random){
  int *p = malloc(5 * sizeof(int));  //p is an array of size
  int offset = (random ? 7 : 3);
  return *(p + offset);    //'offset' will be either 7 or 3.
}

Here, ‘p’ points to a dynamic array of ints, with 5 elements. The ‘offset’ is set to be either 7 or 3. Accessing the index of value ‘offset’, by explicitly dereferencing the pointer, we know that the index may be within the bounds of the array, but it may be too large. Goanna will issue the following warning:

7: warning: Goanna[ARR-inv-index-ptr-pos] Array pointer `p' is accessed with index [3,7]
which may be out of array bounds [0,4]

Both these checks, along with some others we’ve been working on, will appear in the upcoming 2.4 release.

slides, etc...

Prompted by GHC's move to Git and the unreliability of the community.haskell.org infrastructure, I decided to move Data.Array.Accelerate to GitHub: mchakravarty/accelerate. The GitHub repository is now the main public repository for the project. I will also move the tickets of the old Trac bug tracker over to GitHub Issues.

Permalink | Leave a comment  »

Some of our users may have experienced a bug when using Goanna Studio for Eclipse or Goanna Central 2.3 on linux 64-bit systems. This error looked something like this:

internal error: assertion failed: conv_host_fp_to_double:
error on conversion of DBL_MAX: Numerical result out of range:
((double)1.7...e+308L) (float_pt.c, line 524)

This bug was caused by us upgrading our release build infrastructure that defined DBL_MAX to a value that contained a cast, and our parser was not able to deal with this. We are releasing a patch that will correct this issue. Please download version 2.3.1 if you are using goanna on a 64-bit linux system. Windows and 32-bit linux systems are not affected.

For the past several months we have received a lot of great feedback and support requests which have helped us dramatically improve the stability of our products Goanna Studio and Central. And yesterday we pushed a new version to our website which bear the fruits of our labor. At the same time we are releasing a bunch of new features that we hope will help people understand what Goanna is doing and make people more effective at using Goanna.

As usual, all current users get the upgrade for free. If you were a trial user in the past and need a trial extension visit: http://redlizards.com/trial-extension

What is new in 2.3?

New Checks:

• ATH-div-0-param-unchk: Dividing by a parameter value without first checking that it is not zero
• MEM-stack-global-field: storing the address of a field of a local struct in a global variable
• ITR-uninit: using (dereferencing or incrementing) an iterator that hasn’t been initialized
• ITR-end-cmp-bef: using an iterator after it has been compared with end(). This can occur when using an iterator after it is used in a loop.

New Goanna Studio features:

• access check descriptions and examples through the IDE
• added ability to manage warnings by suppressing/unsuppressing
• added ability to pass specific options to the Goanna command line that is used during analysis.

Goanna Studio for Eclipse:

• New ability to right-click on a file/project and run the Goanna analysis over just that item
• Project specific settings have been moved to the Properties of the project (out of the Goanna Preferences)
• Right-click menu now includes a link to the Goanna summary page for projects
• If you close the Goanna Warning view it can be reopened from the Goanna menu
• Improved stability of the Goanna warnings pane (with regards to close/open of Eclipse)

Goanna Studio for Visual Studio:

• redesign of menu structure, Goanna is now a top-level menu
• auto updating: no more uninstall-install updating.
  Note: you cannot do this from version 2.2 -> 2.3. It will work from now on.

General:

• Improved handling of floating point numbers in the data tracking analysis
• Warning suppression captured in the database structure
• Several bug fixes including handling of very large ASTs.

I recently ran into some “interesting” behaviour when using lambda in Python. Perhaps it’s only interesting because I learnt lambdas from a functional language background, where I expect that they work a particular way, and the rest of the world that learnt lambdas through Python, Ruby or JavaScript disagree. (Shouts out to you Objective-C developers who are discovering the wonders of blocks, too.) Nevertheless, I thought this would be blog-worthy. Here’s some Python code that shows the behaviour that I found on Stack Overflow:

Since I succumb to reading source code in blog posts by interpreting them as “blah”¹, a high-level overview of what that code does is:

1. iterate over a list of strings,
2. create a new list of functions that prints out the strings, and then
3. call those functions, which prints the strings.

Simple, eh? Prints “do”, then “re”, then “mi”, eh? Wrong. It prints out “mi”, then “mi”, then “mi”. Ka-what?

(I’d like to stress that this isn’t a theoretical example. I hit this problem in production code, and boy, it was lots of fun to debug. I hit the solution right away thanks to the wonders of Google and Stack Overflow, but it took me a long time to figure out that something was going wrong at that particular point in the code, and not somewhere else in my logic.)

The second answer to the Stack Overflow question is the clearest exposition of the problem, with a rather clever solution too. I won’t repeat it here since you all know how to follow links. However, while that answer explains the problem, there’s a deeper issue. The inconceivable Manuel Chakravarty provides a far more insightful answer when I emailed him to express my surprise at Python’s lambda semantics:

This is a very awkward semantics for lambdas. It is also probably almost impossible to have a reasonable semantics for lambdas in a language, such as Python.

The behaviour that the person on SO, and I guess you, found surprising is that the contents of the free variables of the lambdas body could change between the point in time where the closure for the lambda was created and when that closure was finally executed. The obvious solution is to put a copy of the value of the variable (instead of a pointer to the original variable) into the closure.

But how about a lambda where a free variable refers to a 100MB object graph? Do you want that to be deep copied by default? If not, you can get the same problem again.

So, the real issue here is the interaction between mutable storage and closures. Sometimes you want the free variables to be copied (so you get their value at closure creation time) and sometimes you don’t want them copied (so you get their value at closure execution time or simply because the value is big and you don’t want to copy it).

And, indeed, since I love being categorised as a massive Apple fanboy, I found the same surprising behaviour with Apple’s blocks semantics in C, too:

You can see the Gist page for this sample code to see how to work around the problem in Objective-C (basically: copy the block), and also to see what it’d look like in Haskell (with the correct behaviour).

In Python, the Stack Overflow solution that I linked to has an extremely concise way of giving the programmer the option to either copy the value or simply maintain a reference to it, and the syntax is clear enough—once you understand what on Earth what the problem is, that is. I don’t understand Ruby or JavaScript well enough to comment on how they’d capture the immediate value for lambdas or whether they considered this design problem. C++0x will, unsurprisingly, give programmers full control over lambda behaviour that will no doubt confuse the hell out of people. (See the C++0x language draft, section 5.1.2 on page 91.)

In his usual incredibly didactic manner, Manuel then went on to explain something else insightful:

I believe there is a deeper issue here. Copying features of FP languages is the hip thing in language design these days. That’s fine, but many of the high-powered FP language features derive their convenience from being unspecific, or at least unconventional, about the execution time of a piece of code. Lambdas delay code execution, laziness provides demand-dependent code execution plus memoisation, continuations capture closures including their environment (ie, the stack), etc. Another instance of that problem was highlighted by Joe Duffy in his STM retrospective.

I would say, mutability and flexible control flow are fundamentally at odds in language design.

Indeed, I’ve been doing some language exploration again lately as the lack of static typing in Python is really beginning to bug me, and almost all the modern languages that attempt to pull functional programming concepts into object-oriented land seem like a complete Frankenstein, partially due to mutability. Language designers, please, this is 2011: multicore computing is the norm now, whether we like it or not. If you’re going to make an imperative language—and that includes all your OO languages—I’ll paraphrase Tim Sweeney: in a concurrent world, mutable is the wrong default! I’d love a C++ or Objective-C where all variables are const by default.

One take-away point from all this is to try to keep your language semantics simple. I love Dan Ingall’s quote from Design Principles Behind Smalltalk: “if a system is to serve the creative spirit, it must be entirely comprehensible to a single individual”. I love Objective-C partially because its message-passing semantics are straightforward, and its runtime has a amazingly compact API and implementation considering how powerful it is. I’ve been using Python for a while now, and I still don’t really know the truly nitty-gritty details about subtle object behaviours (e.g. class variables, multiple inheritance). And I mostly agree with Guido’s assertion that Python should not have included lambda nor reduce, given what Python’s goals are. After discovering this quirk about them, I’m still using the lambda in production code because the code savings does justify the complexity, but you bet your ass there’s a big comment there saying “warning, pretentous code trickery be here!”

1. See point 13 of Knuth et al.’s Mathematical Writing report.

UPDATE: There’s a lot more subtlety at play here than I first realised, and a couple of statements I’ve made above are incorrect. Please see the comments if you want to really figure out what’s going on: I’d summarise the issues, but the interaction between various language semantics are extremely subtle and I fear I’d simply get it wrong again. Thank you to all the commenters for both correcting me and adding a lot of value to this post. (I like this Internet thing! Other people do my work for me!)

Update #2

I’ve been overwhelmed by the comments, in both the workload sense and in the pleasantly-surprised-that-this-provoked-some-discussion sense. Boy, did I get skooled in a couple of areas. I’ve had a couple of requests to try to summarise the issues here, so I’ll do my best to do so.

Retrospective: Python

It’s clear that my misunderstanding of Python’s scoping/namespace rules is the underlying cause of the problem: in Python, variables declared in for/while/if statements will be declared in the compound block’s existing scope, and not create a new scope. So in my example above, using a lambda inside the for loop creates a closure that references the variable m, but m’s value has changed by the end of the for loop to “mi”, which is why it prints “mi, mi, mi”. I’d prefer to link to the official Python documentation about this here rather than writing my own words that may be incorrect, but I can’t actually find anything in the official documentation that authoritatively defines this. I can find a lot of blog posts warning about it—just Google for “Python for while if scoping” to see a few—and I’ve perused the entire chapter on Python’s compound statements, but I just can’t find it. Please let me know in the comments if you do find a link, in which case I’ll retract half this paragraph and stand corrected, and also a little shorter.

I stand by my assertion that Python’s for/while/if scoping is slightly surprising, and for some particular scenarios—like this—it can cause some problems that are very difficult to debug. You may call me a dumbass for bringing assumptions about one language to another, and I will accept my dumbassery award. I will happily admit that this semantics has advantages, such as being able to access the last value assigned in a for loop, or not requiring definitions of variables before executing an if statement that assigns to those variables and using it later in the same scope. All language design decisions have advantages and disadvantages, and I respect Python’s choice here. However, I’ve been using Python for a few years, consider myself to be at least a somewhat competent programmer, and only just found out about this behaviour. I’m surprised 90% of my code actually works as intended given these semantics. In my defence, this behaviour was not mentioned at all in the excellent Python tutorials, and, as mentioned above, I can’t a reference for it in the official Python documentation. I’d expect that this behaviour is enough of a difference vs other languages to at least be mentioned. You may disagree with me and regard this as a minor issue that only shows up when you do crazy foo like use lambda inside a for loop, in which case I’ll shrug my shoulders and go drink another beer.

I’d be interested to see if anyone can come up an equivalent for the “Closures and lexical closures” example at http://c2.com/cgi/wiki?ScopeAndClosures, given another Python scoping rule that assignment to a variable automatically makes it a local variable. (Thus, the necessity for Python’s global keyword.) I’m guessing that you can create the createAdder closure example there with Python’s lambdas, but my brain is pretty bugged out today so I can’t find an equivalent for it right now. You can simply write a callable class to do that and instantiate an object, of course, which I do think is about 1000x clearer. There’s no point using closures when the culture understands objects a ton better, and the resulting code is more maintainable.

Python summary: understand how scoping in for/while/if blocks work, otherwise you’ll run into problems that can cost you hours, and get skooled publicly on the Internet for all your comrades to laugh at. Even with all the language design decisions that I consider weird, I still respect and like Python, and I feel that Guido’s answer to the stuff I was attempting would be “don’t do that”. Writing a callable class in Python is far less tricky than using closures, because a billion times more people understand their semantics. It’s always a design question of whether the extra trickiness is more maintainable or not.

Retrospective: Blocks in C

My C code with blocks failed for a completely different reason unrelated to the Python version, and this was a total beginner’s error with blocks, for which I’m slightly embarrassed. The block was being stack-allocated, so upon exit of the for loop that assigns the function list, the pointers to the blocks are effectively invalid. I was a little unlucky that the program didn’t crash. The correct solution is to perform a Block_copy, in which case things work as expected.

Retrospective: Closures

Not all closures are the same; or, rather, closures are closures, but their semantics can differ from language to language due to many different language design decisions—such as how one chooses to define the lexical environment. Wikipedia’s article on closures has an excellent section on differences in closure semantics.

Retrospective: Mutability

I stand by all my assertions about mutability. This is where the Haskell tribe will nod their collective heads, and all the anti-Haskell tribes think I’m an idiot. Look, I use a lot of languages, and I love and hate many things about each of them, Haskell included. I fought against Haskell for years and hated it until I finally realised that one of its massive benefits is that things bloody well work an unbelievable amount of the time once your code compiles. Don’t underestimate how much of a revelation this is, because that’s the point where the language’s beauty, elegance and crazy type system fade into the background and, for the first time, you see one gigantic pragmatic advantage of Haskell.

One of the things that Haskell does to achieve this is the severe restriction on making things immutable. Apart from the lovely checkbox reason that you can write concurrent-safe algorithms with far less fear, I truly believe that this makes for generally more maintainable code. You can read code and think once about what value a variable holds, rather than keep it in the back of your mind all the time. The human mind is better at keeping track of multiple names, rather than a single name with different states.

The interaction of state and control flow is perhaps the most complex thing to reason about in programming—think concurrency, re-entrancy, disruptive control flow such as longjmp, exceptions, co-routines—and mutability complicates that by an order of magnitude. The subtle difference in behaviour between all the languages discussed in the comments is exemplar that “well-understood” concepts such as lexical scoping, for loops and closures can produce a result that many people still don’t expect; at least for this simple example, these issues would have been avoided altogether if mutability was disallowed. Of course mutability has its place. I’m just advocating that we should restrict it where possible, and at least a smattering of other languages—and hopefully everyone who has to deal with thread-safe code—agrees with me.

Closing

I’d truly like to thank everyone who added their voice and spent the time to comment on this post. It’s been highly enlightening, humbling, and has renewed my interest in discussing programming languages again after a long time away from it. And hey, I’m blogging again. (Though perhaps after this post, you may not think that two of those things are good things.) It’s always nice when you learn something new, which I wouldn’t have if not for the excellent peer review. Science: it works, bitches!

The following command is in my shell history

				A青ポ0〜〜〜〜?
				

I think we can assume that is the work of Hikari.

I think it translates as:

A blue "po" Oooooooooh?

I recently managed to make a bit of a mess of things while doing some multi-process programming using fork(). While the box was still semi-usable I was unable to kill off the processes faster than they were being created and I ended up resorting to a reboot.

At the time I wasn't entirely sure what the problem was and not cherishing the prospect of more reboots I used taskset to constrain my shell, its child processes including test runs of my program and of course its forked children to a single CPU.

# taskset -p 01 $$

The result? A subsequent fork explosion was indeed constrained to one CPU and I was able to kill off all the processes quite easily.

My system is a single socket with four cores. I have disabled hyper-threading so there is only one thread per core. I am unsure how well this technique would work in other situations, especially in the case of multiple threads but only one socket and one core.

This will be a follow-up to a presentation I made on the same topic at the MobileFOSS Mini-Conf at Linux.conf.au 2011 in January. Material from that presentation

You don’t have to download Goanna to try out Goanna.

Once you have an account on redlizards.com, you can try out Goanna via the online demo at http://redlizards.com/products/demo.html. Just log in, paste in your code in the text box and click the “Analyze” button. The results will show up on the Web page.

We’ve limited the amount of code you can analyze in the demo to 250 lines (so you still might want to download Goanna for serious work).

I recently consolidated all my email on MobileMe (for easy access from both my Mac and iPad). However, I ran into a problem with the MobileMe IMAP server when I tried to move my old mail archives to the MobileMe IMAP server. MobileMe uses the Sun Java System Messaging Server (which has since become the Oracle Communications Messaging Exchange Server). It turns out that this IMAP server (like some others as well) is rather strict about the format of mail headers; hence, uploading old mail archives usually aborts with the following error message: "The IMAP command “APPEND” (to …) failed with server error: Message contains invalid header".

Permalink | Leave a comment  »

Over the past few weeks eastern Australia, including Brisbane, has been subjected to devastating floods. My sympathy and condolences are with anyone adversely effected by these events.

Last night a decision was made by the organisers and Linux Australia that despite the floods Linux.Conf.Au 2011 will go ahead next week in Brisbane as scheduled. I am delighted to be able to be part of the event.

In Tuesday I will be making a presentation at the MobileFOSS miniconf on using zboot to boot Linux directly from flash or, SD or MMC cards on SH-Mobile ARM.

On Wednesday at 15:45 I will be making a presentation at the main conference on Network Bandwidth Control in Virtualized Environments. This covers the use of Linux's QoS facilities to control guest bandwidth usage.

Its going to be a great conference, I'm looking forward to it.

The LLVM backend for DDC that I've been working on sporadically since June is basically done. When compiling via the LLVM backend, all but three of 100+ tests in the DDC test suite pass. The tests that pass when going via the C backend but fail via the LLVM backend are of two kinds:

1. Use DDC's foreign import construct to name a C macro to perform a type cast where the macro is defined in one of C header files.
2. Use static inline functions in the C backend to do peek and poke operations on arrays of unboxed values.

In both of these cases, DDC is using features of the C language to make code generation easier. Obviously, the LLVM backend needs to do something else to get the same effect.

Fixing the type casting problem should be relatively simple. Ben is currently working on making type casts a primitive of the Core language so that both the C and LLVM backends can easily generate code for them.

The array peek and poke problem is little more complex. I suspect that it too will require the addition of new Core language primitive operations. This is a much more complex problem than the type casting one and I've only just begun to start thinking about it.

Now that the backend is nearly done, its not unreasonable to look at its performance. The following table shows the compile and run times of a couple of tests in the DDC test suite compiling via the C and the LLVM backend.

Although there is a small increase in compile times when compiling via LLVM, the LLVM run times are significantly reduced. The conceptual complexity of the LLVM backend is also low (the line count is about 4500 lines, which will probably fall with re-factoring) and thanks to LLVM's type checking being significantly better than C's, I think its reasonable to be more confident in the quality of the LLVM backend than the existing C backend. Finally, implementing things like proper tail call optimisation will be far easier in LLVM backend than in C.

All in all, I think doing this LLVM backend has been an interesting challenge and will definitely pay off in the long run.

There comes in the career of every motion picture that final occasion when all the artistry, all the earnest constructive endeavor of all the man-power and genius of the industry, and all the capital investment, too, must pour through the narrow gate of the projector on its way to the fulfilment of its purpose, the final delivery to the public.

The delivery is a constant miracle of men and mechanism in the projection rooms of the world’s fifty thousand theatres. That narrow ribbon, thirty-five millimetres, flowing at twenty-four frames a second through the scintillating blaze of the spot at the picture aperture and coursing by at an exactingly-precise 90 feet a minute past the light slit of the sound system, demands a quality of skill and faithful, unfailing attention upon which the whole great industry depends.

The projector lens is the neck in the bottle through which all must pass. The projectionist presiding over that mechanism is responsible for the ultimate performance upon which we must all depend.

The projector must not fail, and more importantly still, the man must not fail or permit it to waiver in its performance. It is to the tremendous credit of the skill of the modern projectionist that perfect presentation of the motion picture upon the screen is today a commonplace, a perfection that is taken as a matter of course.

Adolph Zukor, Chairman of Paramount Pictures, 1935. It still applies as much today as it did back then.

New feature for Visual Studio: For any Goanna warning in the VS ErrorList, right-click and choose “Describe Check”. You’ll get an editor tab filled with a description of the check that gave rise to the warning, the same text as in the User Guide. Coming soon to Eclipse.

I am thrilled to announce that Goanna Studio 2.2 is now the most stable version of Goanna Studio ever created. Goanna Studio 2.1 was an impressive piece of software, but thanks to all the great feedback we have received, we have nailed down all the outstanding issues and we are ready to let you reap the benefits of our efforts.

The major part of our efforts has been targeted at making the Goanna Studio experience much better. This means more features and more stability. On the Visual Studio front, Goanna Studio is now capable of fully handling the range of possible inputs that you can throw at it. That means full Unicode support in everything, from how we process filenames, to project names and folders names, even down to the default file name when you export your warnings to CSV format from the Goanna Summary web page. This means, Goanna works reliably now with, e.g., Korean, Chinese and Japanese Windows. In addition we have introduced a feature we are calling Macro Visualisation. It is a way of presenting to you exactly what your source code looks like underneath all that macro mess.

On the Eclipse side we have some amazing new features. Goanna Studio can now handle various custom CDT Tool Chain tools. It’s as simple as telling Goanna which Tool’s it should be emulating, and then the Goanna analysis in your build environment is one step closer to perfection. The long-standing annoyance that appears asking you to select a CDT Project when you first try to analyse something with Goanna is now fixed. In addition, Goanna Studio for Eclipse now works in Windows-based environments with the MinGW tool chain.

Another major feature we are pleased to announce is Flexelint and PC-Lint integration into the Goanna Studio for Eclipse package. This allows you to run your version of lint and Goanna analysis at the same time, and have all the warnings presented to you in one simple interface.

The fixed false positives and changes to checks include:

• ATH-div-0 - now warns for any expression that evaluates to 0
• ATH-div-0-* - these checks now only warn when there is a definite division by 0.
• ATH-neg-* - these checks no longer give warnings about floating point operations.
• ARR-inv-index - now warns about invalid global array accesses.
• COP-assign-op-ret - no longer warns about operator==.
• COP-copy-ctor - two false positives were fixed, no longer warns when the copy constructor is intentionally unimplemented, and now handles C++ structs properly.
• COP-member-uninit - now gives one warning for each uninitialised class member and now will also analyse assignment operators.
• LIB-* - we have added a number of new checks warning about the unsafe use of library functions
• RED-no-effect now has a more precise warning message.
• RED-unused-val - no longer warns when you return a value, and now warns more correctly and almost lines up with the MISRA coding standard rule: 0-1-6.
• SPC-ret-stack - no longer gives a warning when you return static local variables.
• MEM-double-free - gives less false positives due to assuming that delete operators can throw exceptions

Other minor improvements and bug fixes are:

• better handling of gcc arguments (particularly include path specifications).
• Goanna Central now smoothly handles multiple files on the same command line.

As usual, all current users get the upgrade for free. If you were a trial user in the past and need a trial extension visit: http://redlizards.com/trial-extension

After my last post on this topic, I ran into some problems with the AST (abstract syntax tree) that was being passed to my code for LLVM code generation. After discussing the problem with Ben, he spent some time cleaning up the AST definition, the result of which was that nearly all the stuff I already had, stopped working. This was a little disheartening. That and the fact that I was really busy, meant that I didn't touch the LLVM backend for a number of weeks.

When I finally did get back to it, I found that it wasn't as broken as I had initially thought. Although the immediate interface between Ben's code and mine had changed significantly, all the helper functions I had written were still usable. Over a week and a bit, I managed to patch everything up again and get back to where I was. I also did a lot of cleaning up and came up with a neat solution to a problem which was bugging me during my previous efforts.

The problem was that structs defined via the LLVM backend needed to have exactly the same memory layout as the structs defined via the C backend. This is a strict requirement for proper interaction between code generated via C and LLVM. This was made a little difficult by David Terei's haskell LLVM wrapper code (see previous post) which makes all structs packed by default, while structs on the C side were not packed. Another dimension of this problem was finding an easy way to generate LLVM code to access structs in a way that was easy to read and debug in the code generator and also not require different code paths for generating 32 and 64 bit code.

Struct layout is tricky. Consider a really simple struct like this:

  struct whatever
  {   int32_t tag ;
      char * pointer ;
  } ;

On a 32 bit system, that struct will take up 8 bytes; 4 bytes for the int32_t and 4 for the pointer. However, on a 64 bit system, where pointers are 8 bytes in size, the struct will take up 16 bytes. Why not 12 bytes? Well, some 64 bit CPUs (Alpha and Sparc64 are two I can think of) are not capable of unaligned memory accesses; a read from memory into a CPU register where the memory address (in bytes) is not an integer multiple of the size of the register. Other CPUs like x86_64 can read unaligned data, but reading unaligned data is usually slower than reading correctly aligned data.

In order to avoid unaligned, the compiler assumes that the start address of the struct will be aligned to the correct alignment for the biggest CPU register element in the struct, in this case the pointer. It then adds 4 bytes of padding between the int32_t and the pointer to ensure that if the struct is correctly aligned then the pointer will also be correctly aligned.

Because structs are packed in the David Terei's code, the above struct would require a different definition on 32 and 64 bit systems, ie

  ; 32 bit version of the struct
  %struct.whatever.32 = type { i32, i8 * }>

  ; 64 bit version of the struct
  %struct.whatever.64 = type { i32, [4 * i8], i8 * }>

where the 64 bit version contains 4 padding bytes. However, the difference between these two definitions causes another problem. To access fields within a struct, LLVM code uses the getelementptr operator which addresses fields by index. Unfortunately, the index (zero based) of the pointer is 1 for the 32 bit version and 2 for the 64 bit version. That would make code generation a bit of a pain in the neck.

The solution is allow the specification of LLVM structs in Haskell as a list of LlvmStructField elements, using

  data LlvmStructField
        = AField String LlvmType    -- Field name and type.
        | APadTo2                   -- Pad next field to a 2 byte offset.
        | APadTo4                   -- Pad next field to a 4 byte offset.
        | APadTo8                   -- Pad next field to a 8 byte offset.

        | APadTo8If64               -- Pad next field to a 8 byte offset only
                                    -- for 64 bit.

Note that the AField constructor requires both a name and the LlvmType. I then provide functions to convert the LlvmStructField list into an opaque LlvmStructDesc type and provide the following functions:

  -- | Turn an struct specified as an LlvmStructField list into an
  -- LlvmStructDesc and give it a name. The LlvmStructDesc may
  -- contain padding to make it conform to the definition.
  mkLlvmStructDesc :: String -> [LlvmStructField] -> LlvmStructDesc

  -- | Retrieve the struct's LlvmType from the LlvmStructDesc.
  llvmTypeOfStruct :: LlvmStructDesc -> LlvmType

  -- | Given and LlvmStructDesc and the name of a field within the
  -- LlvmStructDesc, retrieve a field's index with the struct and its
  -- LlvmType.
  structFieldLookup :: LlvmStructDesc -> String -> (Int, LlvmType)

Once the LlvmStructDesc is built for a given struct, fields within the struct can be addressed in the LLVM code generator by name, making the Haskell code generator code far easier to read.

Pretty soon after I got the above working I also managed to get enough LLVM code generation working to compile a complete small program which then runs correctly. I consider that to be milestone 3.

About 6 weeks ago, I got an email from Craig Sharkie, who runs the Sydney Javascript group, SydJS. He was contacting me because I run the Sydney functional programing group and he was asking if I knew anyone who might be able to give a presentation about tail call recursion at SydJS. In the spirit of FP-Syd outreach I volunteered to do it, even though I haven't really done all that much Javascript.

On the night, I showed up, had a beer and then presented my slides. I started off explaining what functional programming is and why its is interesting (hint; common language features like garbage collection, dynamic typing, lambda expression and type inference all started in functional languages).

I used the factorial function as an example of function that can be implemented recursively and I demoed the Javascript versions in a web browser. I gave the standard recursive form whose stack usage grows linearly with n:

  function factorial (n)
  {
      /* Termination condition. */
      if (n <= 1)
          return 1 ;

    /* Recursion. */
      return n * factorial (n - 1) ;
  }

followed by the tail recursive form:

  function factorial (n)
  {
      function fac_helper (n, fac)
      {
          if (n <= 1)
              return fac ;
          return fac_helper (n - 1, n * fac) ;
      }

      return fac_helper (n, 1) ;
  }

Unfortunately even though this is written in tail recursive form, it still doesn't run in constant stack space. That's because neither the ECMAScript 3 and 5 standards mandate tail call optimisation and few of the Javascript engines implement it.

For languages whose compilers do implement the TCO, the above function will run in constant stack space and I demonstrated this using the same function written in Ocaml:

  (* Compile using: ocamlopt nums.cmxa mlfactorial.ml -o mlfactorial *)

  open Big_int

  (*
      val mult_int_big_int : int -> big_int -> big_int
          Multiplication of a big integer by a small integer
  *)
  let ($*) = mult_int_big_int

  let factorial n =
      let rec fac_helper x fac =
          if x <= 1 then
              fac
          else
              fac_helper (x - 1) (x $* fac)
      in
      fac_helper n unit_big_int

  let () =
      let n = int_of_string Sys.argv.(1) in
      let facn = factorial n in
      Printf.printf "factorial %d = %s\n" n (string_of_big_int facn)

When this program is run through the Ocaml compiler, the compiler detects that the factorial function is written in tail recursive form and that it can therefore use the Tail Call Optimisation and create a executable that runs in constant stack space. I demostrated the constant stack space usage by running it under valgrind using valgrind's DRD tool:

  > valgrind --quiet --tool=drd --show-stack-usage=yes ./factorial 5
  factorial 5 = 120
  ==3320== thread 1 finished and used 11728 bytes out of 8388608 on its stack. Margin: 8376880 bytes.
  > valgrind --quiet --tool=drd --show-stack-usage=yes ./factorial 10
  factorial 10 = 3628800
  ==3323== thread 1 finished and used 11728 bytes out of 8388608 on its stack. Margin: 8376880 bytes.
  > valgrind --quiet --tool=drd --show-stack-usage=yes ./factorial 20
  factorial 20 = 2432902008176640000
  ==3326== thread 1 finished and used 11728 bytes out of 8388608 on its stack. Margin: 8376880 bytes.

Regardless of the value of n the stack space used is constant (although, for much larger values of n, the Big_int calculations start easting a little more stack, but thats much less of a problem).

Finally, I showed a way of doing TCO by hand using a technique I found in Spencer Tipping's "Javascipt in Ten Minutes". The solution adds a couple of new properties to the prototype of the Function object to provide delimited continuations (another idea from functional programming). See the the code for the details. Suffice to say that this solution is really elegant and should be safe to run in just about any browser whose Javascript implementation is not completely broken.

As far as I am concerned, my presentation was received very well and the Twitter responses (all two of them) ranged from "brain melting" to "awesome".

I then hung around for the rest of the meeting, had another beer and chatted to people. One interesting part of the meeting was called "Di-script-ions", where a member of the audience would put up small 4-10 line snippets of Javascript code and asked the audience what they did and why. What was surprising to me that for some cases the semantics of a small piece of Javascript code is completely non-obvious. Javascript seems to have some very weird interactions between scoping rules, whether functions are defined directly or as a variable and the sequence of initialisation. Strange indeed.

Anyway, thanks to Craig Sharkie for inviting me. I had a great time.

We will present our paper Accelerating Haskell Array Codes with Multicore GPUs at ACM SIGLAN Declarative Aspects of Multicore Programming (DAMP 2011), which is co-located with POPL'11 in Austin, TX, in January. The final version of our paper is now available, and we plan to soon release a significantly improved version of the Accelerate library (matching the API used in the paper), which enables high-level GPGPU programming in Haskell based on NVIDIA's CUDA environment.

Permalink | Leave a comment  »

Our paper Singleton: A General-Purpose Dependently-Typed Assembly Language will be presented at the ACM SIGPLAN Workshop on
Types in Language Design and Implementation (TLDI'11) co-located with POPL'11 in Austin, TX, in January. The final version of the paper is now available. See this previous post for some more information and proof scripts.

Permalink | Leave a comment  »

Pixar’s latest short film. I’m so proud and honoured to be working with such an amazing group of people.

Thanks to several evil friends of mine, I started to take an interest in photography at the end of last year. I’ve always wanted to have a “real” camera instead of a point and shoot, so at the start of 2010, I bit the bullet and bought myself a Panasonic Lumix DMC-GF1, usually just called The GF1 amongst the camera geeks.

I tossed up between the GF1 and the then-just-released Canon EOS 550D (a.k.a. the Rebel T2i in the USA) for a long time. I figured that getting a compact camera would make me tote it around a lot more, and after ten months of using it, I think I was right. I recently went to a wedding in Sydney, and I literally kept the camera in my suit pocket instead of having to lug it around strapped to my body or neck. I definitely wouldn’t be able to do that with a Canon or Nikon DSLR. The camera’s so small with the kit 20mm f/1.7 lens that I stopped using the UV filter with it, because I didn’t like the 2-3mm that the filter added to the camera depth. Here’s a size comparison of the Nikon D3000 vs the GF1.

(Image stolen from dpreview.com’s review.)

I won’t write up a comprehensive review of the GF1 here; other sites have done that, in much more depth than I can be bothered to go into. If you’re after a good review, the three articles that swayed me to the GF1 in the end were DPreview’s review, and Craig Mod’s GF1 photo field test article and video tests. What follows is my own impressions and experiences of using the camera. The one-sentence summary: the GF1 perfect for a DSLR newbie like me, the micro four-thirds lens system it uses looks like it has enough legs that your lens investments will be good for the future, and learning photography with the GF1 is great and deserves a Unicode snowman: ☃.

The reason you want the camera is to use the 20mm f/1.7 lens. For the non-photography geeks, that means that it’s not a zoom lens, i.e. you can’t zoom in and out with it, and the f/1.7 means that it can take pretty good shots in low light without a flash. All the reviews of it are right: that lens is what makes the camera so fantastic. Do not even bother with 14-45mm kit lens. The 20mm lens is fast enough that you can shoot with it at night, and the focal length’s versatile enough to take both close-up/portrait shots (whee food porn), and swing out a bit wider for landscape photos or group photos. It’s no wide-angle nor zoom and it’s not a super-fast f/1.4, but it’s versatile enough and so tiny that you will end up using it almost all the time. It feels weird to get a DSLR and only have one lens for it, but the pancake 20mm lens is so damn good that it’s all you really need. The only thing it really can’t do at all is go super-zoomalicious, for wildlife/distance shots.

The 20mm non-zoom (a.k.a. “prime”) lens has another advantage: it teaches you to compose. Despite all the technology and all the geek speak, photography is ultimately about your composition skills. Prime lenses force you to move around to find the perfect framing for the shot you’re trying to do; I think learning with a prime lens moves your composition skills along much faster than it would if you were using a standard zoom lens. If you’re a photography beginner, like me, shoot with a prime. It’s a totally different experience than shooting with a zoom, and you learn a lot more. Plus, primes are cheap: the Canon 50mm f/1.8 is USD$100, and Canon’s near top-of-the-line 50mm f/1.4 is USD$350. The Canon 35mm f/2, for something that’s similar in focal length to the Panasonic 20mm prime, is USD$300. (You need to multiply the 20mm by 2 to convert between micro four-thirds and 35mm framing, so the actual focal length of the 20mm in traditional camera speak is 20mm*2=40mm.)

After playing it for a few months, you realise that the GF1 is a fun camera to use. The combination of the 20mm prime lens, the super-fast focus, the size, and the great UI design just begs you to take pictures with it. You feel like you’re wielding a real camera rather than a toy: one that wants you to shoot with it. It’s not imposing like a bigger DSLR so it doesn’t feel like the camera is with you all the time, but it’s not so small that you feel like you’re just snipping super-casually with something that’s cheap. And did I mention the excellent UI? It’s excellent. The better controls are a good reason to get the GF1 over its rivals, the Olympus EP series.

One big bonus: I’ve found that the full-auto mode (“iAuto” as Panasonic brands it) very rarely gets stuff wrong. This is useful if you hand the camera over to someone else who doesn’t know how to use DSLRs so that they can take a picture of you… or, like me, if you just don’t know quite what aperture/shutter speeds to use for the particular shot you’re taking. The full-auto just adds to the joy of using it. I usually shoot in full-auto or aperture priority mode, but honestly, I could probably shoot on full-auto mode all the time. I can’t recall a single occasion where it didn’t guess f/1.7 or a landscape correctly.

Do follow DPreview and Craig Mod’s advice and shoot RAW, not JPEG. Honestly, I’d prefer to shoot JPEG if I could, but RAW lets you turn some bad shots into good shots. I use it because gives you a second chance, not because I want to maximise picture quality. Here’s one photo that was accidentally taken with the wrong settings: I had the camera on full-manual mode, and didn’t realise that the shutter speed and ISO settings were totally incorrect.

However, since I shot it in RAW, I could lift up the exposure up two stops, pulled up the shadows and pulled down the highlights, and here’s the result:

Seriously, that’s just frickin’ amazing. Sure, that photo might not be super-awesome: it’s a little grainy, and it looks a bit post-processed if you squint right, but it’s still a photo of a precious memory that I wouldn’t have otherwise had, and you know what? That photo’s just fine. If I shot JPEG, I would’ve had no choice but to throw it away. RAW’s a small pain in the arse since the file sizes are far bigger and you need to wait a long time for your computer to do the RAW processing if you’ve taken hundreds of photos, but boy, it’s worth it.

I did finally buy a wide-angle lens for the GF1—the Olympus 9-18mm f/4-5.6—and have been using it a lot for landscape shots. I bought the Olympus 9-18mm over the Panasonic 7-14 f/4.0 because it was cheaper, and also smaller. I figured that if I was getting a GF1, it was because I wanted something compact, so I wanted to keep the lenses as small as possible. (Otherwise, if you don’t care about size, then a full-blown Canon or Nikon DSLR would probably serve you much better.) I’ve always wanted a wide-angle lens from the first day that I asked “how do those real estate agents make those rooms look so bloody large?”, so now I have one, woohoo. The next lens on my shopping will probably be the Panasonic 45-200mm. (Never mind the quality, feel the price!) Here’s a shot taken with the Olympus 9-18mm; click through to see the original picture on Flickr.

The main thing that I wish for in a future version of the camera would be image stabilisation. Panasonic follow the Canon path and put image stabilisation in the lens, rather than in the body. I think Olympus made the right decision by putting image stabilisation in the body for their compact DSLRs; you can keep the lenses smaller that way, and you then get image stabilisation with all your lenses instead of the ones that only support it explicitly, e.g. the 20mm f/1.7 prime doesn’t have image stabilision, boo. In-body image stabilisation just seems more in-line with the size reduction goal for micro four-thirds cameras. I’d love to get my hands on an Olympus EP for a week and shoot with the 20mm to see if image stabilisation makes a difference when it’s dark and the environment is starting to challenge the f/1.7 speeds.

The only other thing I wish for would be a better sensor. The GF1’s great up to ISO 800: at ISO 1600+, it starts getting grainy. 1600 is acceptable, and you can do wondrous things with the modern noise reduction algorithms that are in Lightroom if you really need to save a shot. Shoot at ISO 3200+ though, and it’s just too grainy. This is the main advantage that more traditional DSLRs have: their larger sensors are simply better than the GF1’s. I’ve seen shots taken with a Nikon D50 at ISO 6400 in the dark because a slower f/4 lens was being used, and bam, the shot comes out fine. Don’t even try to compare this thing to a Canon 5D Mk II. The GF1 just can’t do high ISO. Here’s an ISO 3200 shot, which is just starting to get a little too grainy. It’s fine for Facebook-sized images, but if you click through to the original, you’ll see it’s noisy.

But y’know, despite the two nitpicks above, the GF1 is a fine camera, and the 20mm f/1.7 lens is an amazing do-it-all lens that’s absolutely perfect to learn with. There’s really nothing else out there like it except for the Olympus EP range (the EP-1, EP-2 and EPL-1), which you should definitely consider, but get it with the 20mm f/1.7 lens if you do. I’ve had a total blast learning photography with the GF1, and I’ve captured hundreds of memories in the past year that made the investment completely worthwhile. I don’t think I’m at the point yet where I feel like I need another camera yet, but it feels good knowing that the micro four-thirds format will be around for a while so that I can use my existing lenses with future cameras I buy. If you’re interested in learning photography, the GF1 is a fantastic starting point.

After a bit of a hiatus I have updated my photo gallery.

• Hikari November 2010 - Happy first birthday!
• Hikari October 2010
• Hikari October 2009
• Nikko (Featuring Hikari)
• Shirakawa-go (With special guest, Hikari)
• Seville

On Thursday October 21st, we held the 29th meeting of the Sydney Functional Programming group. The meeting was held at Google's Sydney offices and we had about 22 people show up to hear our two presenters.

First up we had Benjamin Johnston with a presentation titled "How to Dance the Robot". As part of his work an University of Technology here in Sydney, Ben gets to program robots. One of the results, is robots that dance (thanks to Mark Wotton for capturing this video on his iPhone):

Ben's language of choice is Prolog (not functional but definitely declarative) and he used Prolog to tackle the problem of making the programming of a robot dance easier. A complete dance might last 3 minutes or more, the music is likely to have a tempo of around 100 beats per minute and the dance moves are usually timed down to the half beat. That means some 600 odd half beat events for a 3 minute dance. Entering 600 odd events manually would be somewhat tedious.

Ben's solution to this problem was a compiler for a domain specific language (DSL) which allowed easier specification of the dance in terms of musical sections, repeated moves etc. Writing the compiler was made easier by making good use of Prolog's search and backtracking capabilities and the compiler generated Python output code that was uploaded to the robot.

Our second presenter for the evening was Sean Seefried on the subject of the "The Expression Problem", in Haskell. In Sean's paper (with Manuel M. T. Chakravarty), "Solving the expression problem with true separate compilation" he describes the expression problem as:

"the difficulty of extending the variants and methods on a data type without modifying existing code and while respecting separate compilation"

There are a number of other languages which have solutions to the expression problem, but Sean's work was the first real Haskell solution. With the use of multi-parameter type classes, scoped type variables, kind annotations, zero constructor data types and recursive dictionaries, Sean was able to make it work with GHC 6.4 and later. At the end, Sean also presented some ideas to make the solution of this problem easier and more practical.

A big thanks to Ben and Sean for presenting and Google for providing the meeting venue and refreshments.

Common Weakness Enumeration (CWE) is a widely accepted, community-developed list of general software vulnerabilities. The CWE website, which contains detailed definitions of each weakness, is here.

Over the last couple of weeks, I’ve been looking into how Goanna maps to the current CWE list. That is, for each of Goanna’s (currently) 100 checks, I’ve reported the CWE items that may be the cause of a warning. I’ve also reported on the mapping in the other direction: for each CWE item, the checks that may report on it are listed. These two mappings are tabulated below.

The table on the left lists all the CWE items that are identified by Goanna, along with each check that may warn about code with each weakness. Code with one of the listed weaknesses will not necessarily fail each associated check, but it may fail some. This table is useful for identifying the checks that are designed to find certain weaknesses. This may help identify the checks that should be enabled or disabled, in order to get the most useful feedback from Goanna.

The table on the right lists each check performed by Goanna, along with each CWE item that may cause the check to fail and yield a warning. The table can be useful for identifying the potential weaknesses in code, based on the warning that Goanna provides.

In the Goanna userguides with the next release, the relevant CWE IDs (from the table on the right) will appear with the detailed descriptions of each check. These two tables will also be included, and updated as more checks are added.

These results are comparable to thosee market-leading analysis tools, and while there is some overlap, there are many CWE items that some leading tools don’t find, such as mismatching the standard and array versions of the new and delete operators, dismissing return values of certain library functions, and the use of uninitialized pointers, just to name a few.

Goanna can currently identify 41 CWE items, including many of the most serious (null pointer dereferences, memory leaks and array index violations), and 61% of our current checks identify the existence of at least one of these vulnerabilities.  Combine this with our relatively low rate of false positives compared to competing tools, and it’s easy to see that Goanna is essential for efficiently finding the most serious vulnerabilities in any software project.

Static analysis of the past has been like an episode of CSI. Some guys in specially marked uniforms enter the scene and photograph memory leaks, establish attack vectors and scrape some dangling pointers off the ceiling. Then they go back to the lab and try to figure out what happened. It’s a post-mortem investigation of something that went horribly wrong.

This could be the tale of a real mission critical bug in the wild or just something that slipped through until final system testing. By any means it probably indicates that someone or something got burned. While many of our customers use our Goanna static analysis tools to establish final code quality or to do some forensic analysis, there are also many opportunities for prevention available that are often overlooked.

We carefully designed Goanna Central and Goanna Studio for two different purposes: Goanna Central can be quickly integrated into the build process and invoked either nightly or at the finish of a project. In any case it gives you an accurate snapshot of your code confidence. This is a must. But ideally, you want your code as clean as possible before it moves upstream in the SDLC. Just imagine how much could be saved by only committing “non-lethal” code to your project; If developers are empowered and can fix code right when they produce it. No more blame games.

We at Red Lizard Software really believe that the maximum value of static analysis tools comes from their usage by developers on an everyday and even every minute base. We try to make deep static analysis ridiculously easy. Checks that still required dedicated severs a few years ago will run on simple laptops with Goanna Studio today.

The advantages are clear: Developers can fix bugs before they are committed, development-testing periods are drastically reduced and products can hit the market sooner with higher quality. Maybe one day we will not need the CSI guys at all.

hackage http://www.google.com/search?hl=en&as_sitesearch=hackage.haskell.org%2Fpackage&as_q={query}

hoogle  http://www.haskell.org/hoogle/?hoogle={query}

Permalink | Leave a comment  »

Filesystems are fundamental things for computer systems: after all, you need to store your data somewhere, somehow. Modern operating systems largely use the same concepts for filesystems: a file’s just a bucket that holds some bytes, and files are organised into directories, which can be hierarchical. Some fancier filesystems keep track of file versions and have record-based I/O, and many filesystems now have multiple streams and extended attributes. However, filesystem organisation ideas have stayed largely the same over the past few decades.

I’d argue that the most important stuff on your machine is your data. There are designated places to put this data. On Windows, all the most important stuff on my computer should really live in C:\Documents and Settings\Andre Pang\My Documents. In practice, because of lax permissions, almost everyone I know doesn’t store their documents there: they splatter it over a bunch of random directories hanging off C:\, resulting in a giant lovely mess of directories where some are owned by applications and the system, and some are owned by the user.

Mac OS X is better, but only because I have discipline: /Users/andrep is where I put my stuff. However, I’ve seen plenty of Mac users have data and personal folders hanging off their root directory. I’m pretty sure that my parents have no idea that /Users/your-name-here is where you are meant to put your stuff, and to this day, I’m not quite sure where my dad keeps all his important documents on his Mac. I hope it’s in ~/Documents, but if not, can I blame him? (UNIX only gets this right because it enforces permissions on you. Try saving to / and it won’t work. If you argue that this is a good thing, you’re missing the point of this entire article.)

One OS that actually got this pretty much correct was classic Mac OS: all system stuff went into the System folder (which all the Cool Kids named “System ƒ”, of course). The entire system essentials were contained in just two files: System, and Finder, and you could even copy those files to any floppy disk and make a bootable disk (wow, imagine that). The entire rest of the filesystem was yours: with the exception of the System folder, you organised the file system as you pleased, rather than the filesystem enforcing a hierarchy on you. The stark difference in filesystem organisation between classic Mac OS and Mac OS X is largely due to a user-centric approach for Mac OS from the ground-up, whereas Mac OS X had to carry all its UNIX weight with it, so it had to compromise and use a more traditionally organised computer filesystem.

As an example, in Mac OS X, if you want to delete Photoshop’s preferences, you delete the ~/Library/Preferences/com.adobe.Photoshop.plist file. Or; maybe you should call it the Bibliothèque folder in France (because that’s what it’s displayed as in the Finder if you switch to French)… and why isn’t the Preferences folder name localised too, and what mere mortal is going to understand why it’s called com.adobe.Photoshop.plist? On a technical level, I completely understand why the Photoshop preferences file is in the ~/Library/Preferences/ directory. But at a user experience level, this is a giant step backwards from Mac OS, where you simply went to the System folder and you trashed the Adobe Photoshop Preferences file there. How is this progress?

I think the fundamental problem is that Windows Explorer, Finder, Nautilus and all the other file managers in the world are designed, by definition, to browse the filesystem. However, what we really want is an abstraction level for users that hides the filesystem from them, and only shows them relevant material, organised in a way that’s sensible for them. The main “file managers” on desktop OSs (Finder and Windows Explorer) should be operating at an abstraction level above the filesystem. The operating system should figure out where to put files on a technical (i.e. filesystem) level, but the filesystem hierarchy should be completely abstracted so that a user doesn’t even realise their stuff is going into /Users/joebloggs.

iTunes and iPhoto are an example of what I’m advocating, because they deal with all the file management for you. You don’t need to worry where your music is or how your photos are organised on the filesystem: you just know about songs and photos. There’s no reason why this can’t work for other types of documents too, and there’s no reason why such an abstracted view of the filesystem can’t work on a systemwide basis. It’s time for the operating system to completely abstract out the filesystem from the user experience, and to turn our main interaction with our documents—i.e. the Finder, Windows Explorer et al—into something that abstracts away the geek details to a sensible view of the documents that are important to us.

One modern operating system has already done this: iOS. iOS is remarkable for being an OS that I often forget is a full-fledged UNIX at its heart. In the iOS user experience, the notion of files is completely gone: the only filenames you ever see are usually email attachments. You think about things as photos, notes, voice memos, mail, and media; not files. I’d argue that this is a huge reason that users find an iPhone and iPad much more simple than a “real” computer: the OS organises the files for them, so they don’t have to think that a computer deals with files. A computer deal with photos and music instead.

There are problems with the iOS approach: the enforced sandboxing per app means that you can’t share files between apps, which is one of the most powerful (and useful) aspects of desktop operating systems. This is a surmountable goal, though, and I don’t think it’d be a difficult task to store documents that can be shared between apps. After all, it’s what desktop OSs do today: the main challenge is in presenting a view of the files that are sensible for the user. I don’t think we can—nor should—banish files, since we still need to serialise all of a document’s data into a form that’s easily transportable. However, a file manager should be metadata-centric and display document titles, keywords, and tags rather than filenames. For many documents, you can derive a filename from its metadata that you can then use to transport the file around.

We’ve tried making the filesystem more amenable to a better user experience by adding features such as extended attributes (think Mac OS type/creator information), and querying and indexing features, ala BFS. However, with the additional complexity of issues such as display names (i.e. localisation), requiring directory hierarchies that should remain invisible to users, and the simple but massive baggage of supporting traditional filesystem structures (/bin/ and /lib/ aren’t going away anytime soon, and make good technical sense), I don’t think we can shoehorn a filesystem browser anymore into something that’s friendly for users. We need a filesystem abstraction layer that’s system-wide. iOS has proven that it can be done. With Apple’s relentless progress march and willingness to change system APIs, Linux’s innovation in the filesystem arena and experimentation with the desktop computing metaphor, and Microsoft’s ambitious plans for Windows 8, maybe we can achieve this sometime in the next decade.

I just found a very suspicious bit torrent download available here:

The file being shared is intended to look like the Windows 64 bit installer for libsndfile-1.0.23 and seems to be widely available on this and a number of other torrent sites.

However, the file on the torrent sites is called libsndfile-64-bit-1.0.23.exe while the one I distribute is called libsndfile-1.0.23-w64-setup.exe.

I haven't analyzed the torrent version of the file; I simply don't have the tools or the knowledge to investigate it. I don't even have access to a machine that runs 64 bit Windows. The setup file on my website was cross compiled from Linux to 64 bit Windows using the very wonderful MinGW w64 tools and the setup installer created using INNO Setup running under Wine. However, the file is named differently and has a different md5sum. That in itself is more than enough reason to be suspicious.

The valid file that I distribute has the following md5 and sha256 sums:

    md5sum    : efe73b7cb52724e7db7bb7d6ce145929
    sha256sum : 30896dac1002a7b509b6f4620317dad730d8ad761e4ff0402db5a94b0d4c09a2

I'm not really aware of how problems like this are addressed on Windows. Is there a safe, secure, verifiable way of distributing Windows software packages? If so, I'd appreciate it if someone could let me know how its done.

For Linux this is much easier. Firstly, the vast majority of people on Linux install libsndfile via their Linux distribution. The person who packages libsndfile for any given distribution grabs the source code tarball from my web site. At the same time they should also grab the GPG signature file and verify that the source code tarball is correct and valid.

I don't know what happens in all distributions, but in Debian, the person doing the packaging GPG signs the package before uploading to the Debian servers. Once the GPG signed package is uploaded, the packager's GPG signature is checked before it goes into the unstable distribution. From there the validity of the package is tracked all the way to where an end user installs it on a machine via the process documented here. This process means that its very difficult to get malware onto a Linux machine via the distribution's package manager.

I suppose this in one more reason why people should be running Linux rather than Windows.

Goanna now supports Unicode filenames in a principled way. Until now, we allowed Latin-1 names in the Visual Studio versions of Goanna by using an ad hoc encoding. While that approach was effective for many languages, it left us unable to support languages with non-Latin-1 character sets.

Thanks to the authors of the Camomile library for the OCaml language, which allows us to work with Unicode directly.

For Eclipse and command-line users of Goanna, you get Unicode support if your terminal program is set to use UTF-8. That seems to be the default in recent Linux distros.

In the paper Accelerating Haskell Array Codes with Multicore GPUs, we describe Accelerate, embedded language for array computations in Haskell, as well as a dynamic code generator targeting NVIDIA's CUDA GPGPU programming environment.  Our CUDA code generator is based on the idea of algorithmic skeletons for parallel programming, minimises re-compilation overheads, and overlaps host-to-device data transfers, code generation, and kernel execution.

Permalink | Leave a comment  »

One of the very common sound file formats that libsndfile reads and writes is the WAV format. This format uses unsigned 32 bit integers internally to specify chunk lengths which limits the total size of well formed file to be about 4 gigabytes in size. On modern systems with high bit widths, multiple channels and high sample rates, this 4Gig limit can be run into very easily. For instance at a sample rate of 96kHz, with 24 bit samples, a 5.1 surround sound recording will run into the 4Gig limit after about 41 minutes.

In order to overcome the limitations of WAV, the European Broadcasting Union decided in 2006 to start the specification of an extended WAV file format capable of handling 64 bit file offsets. The document that resulted from this specification process was first released in 2006 and the latest update was made in 2009 and is available here. I have a number of problems with this specification document.

First and foremost, in section 3.5, the document states:

In spite of higher sampling frequencies and multi-channel audio, some production audio files will inevitably be smaller than 4 Gbyte and they should therefore stay in Broadcast Wave Format.

The problem arises that a recording application cannot know in advance whether the recorded audio it is compiling will exceed 4 Gbyte or not at end of recording (i.e. whether it needs to use RF64 or not).

The solution is to enable the recording application to switch from BWF to RF64 on the fly at the 4 Gbyte size-limit, while the recording is still going on.

This is achieved by reserving additional space in the BWF by inserting a 'JUNK' chunk 3 that is of the same size as a 'ds64' chunk. This reserved space has no meaning for Broadcast Wave, but will become the 'ds64' chunk, if a transition to RF64 is necessary.

In short, the suggestion above for writing a file boils down to:

1. Open the file and write a RIFF/WAV file header with a JUNK section big enough to allow the header to be replaced with an RF64 header if needed.
2. If the file ends up bigger than 4 gigabytes, go back and replace the existing header with an RF64 header.

There are two problems with this suggestion; it makes testing difficult and it makes the software more complex which means its more likely to contain bugs. The testing problem arises because testing that the RF64 header is written correctly can only be done by writing a 4 gigabyte file. Programmers can then either choose not to test this (which means the software is is highly unlikely to work as specified) or test write a full 4 Gig file. However, programmers also want their tests to run quickly (so that they can be run often) and writing 4 gigabytes of data to disk is definitely not going to be quick. Of course, a smaller unit test might be able to bypass the requirement of writing 4 gigabytes, but it would still be prudent to do a real test at the WAV to RF64 switch over point. The complexity problem is simply that writing a WAV file header first and then overwriting it with an RF64 header later is far more complicated than just writing an RF64 header to begin with. Complexity breeds bugs.

The libsndfile project has had, from the very beginning, a pretty comprehensive test suite and the running of that test suite takes about 30 seconds on current hardware. In order to comprehensively test the reading and writing of RF64 files, libsndfile disregards the rather silly suggestion of the EBU to convert on the fly between WAV and RF64 files. If the software calling libsndfile specifies that an RF64 file be generated, libsndfile will write an RF64 file, even if that file only contains 100 bytes.

A second problem with the RF64 specification is that the specification is ambiguous in a very subtle way. The problem is with how the binary chunks within the file are specified. For WAV files, chunks are specified in this document as:

  typedef unsigned long DWORD ;
  typedef unsigned char BYTE ;

  typedef DWORD FOURCC ;            // Four-character code
  typedef FOURCC CKID ;             // Four-character-code chunk identifier
  typedef DWORD CKSIZE ;            // 32-bit unsigned size value

  typedef struct {                  // Chunk structure
      CKID        ckID ;                   // Chunk type identifier
      CKSIZE      ckSize ;                 // Chunk size field (size of ckData)
      BYTE        ckData [ckSize] ;        // Chunk data
  } CK;

This specifies that a chunk has a 4 byte identifier, followed by a 4 byte chunk size, followed by the chunk data. The important thing to note here is that the chunk size does not include the 4 byte chunk identifier and the 4 byte chunk size field. Inspecting real WAV files found in the wild will confirm that this is the case for all common chunks found in WAV files.

Now contrast the above with how the chunks are specified in the EBU document. Ror instance the 'fmt ' chunk (which is common to both WAV and RF64) is specified as:

  struct FormatChunk5                // declare FormatChunk structure
  {
      char           chunkId[4];     // 'fmt '
      unsigned int32 chunkSize;      // 4 byte size of the 'fmt ' chunk
      unsigned int16 formatType;     // WAVE_FORMAT_PCM = 0x0001, etc.
      unsigned int16 channelCount;   // 1 = mono, 2 = stereo, etc.
      unsigned int32 sampleRate;     // 32000, 44100, 48000, etc.
      unsigned int32 bytesPerSecond; // only important for compressed formats
      unsigned int16 blockAlignment; // container size (in bytes) of one set of samples
      unsigned int16 bitsPerSample;  // valid bits per sample 16, 20 or 24
      unsigned int16 cbSize;         // extra information (after cbSize) to store
      char           extraData[22];  // extra data of WAVE_FORMAT_EXTENSIBLE when necessary
  };

Here, the chunkSize field is simply the "size of the 'fmt ' chunk" and nowhere in the EBU document is it specified exactly how that chunkSize field should be calculated. However, if you give the EBU documentation to any experienced software engineer with no previous knowledge of RIFF/WAV files, they would almost certainly assume that the chunkSize field should be the size of the whole chunk, including the chunkID and chunkSize fields. However, someone who knows about RIFF/WAV files will be less likely to follow that path.

This leaves the programmer implementing code to read and write this format with a couple of possibilities:

• Assume that the document is right and should be followed to the letter.
• Assume the document is wrong and that the 'fmt ' chunk of an RF64 file should be identical to that of a WAV file.
• Give up and go home.

However, the last part of section 3.5 of the EBU/RF64 document describes how a WAV file is to be upgraded to an RF64 file, and that description makes no mention of the 'fmt ' chunk being modified during that upgrade. One can only assume from this, that the 'fmt ' chunk in an RF64 file should be identical to that of a WAV file and that the EBU/RF64 specification is misleading.

For libsndfile, I have decided to assume that the specification is indeed misleading. Unfortunately, I'm pretty sure that at some point I will be asked to at least read files which strictly adhere to the literal interpretation of the document. I'm also pretty sure that implementing code to read files written to conform to both interpretations of the spec will be a very painful exercise.

libsndfile is cross platform and is expected to run on 32 and 64 bit CPUs on any system that is reasonably POSIX compliant (ie even Windows). It also has a lot of low level code that does things like endian swapping and bit shifting etc. Although I compile and test the code on all the systems I have access to, I don't have access to everything. That's why libsndfile has a test suite.

The libsndfile test suite is as comprehensive as I can make it. Its taken a lot or work, over man years to get to where it is, but has saved me many times that amount of work tracking obscure bugs.

The test suite is important. That's why I suggest that anyone building libsndfile from source should run the test suite before using the library. This is especially true for people packaging libsndfile for distributions. That's why is so disappointing to see something like this Gentoo bug.

Gentoo managed to mess up their build meta-data resulting in a libsndfile binary that was horribly broken on 32 bit systems. It was broken in such a way that just about every single test in the libsndfile test suite would have failed. Unfortunately, since Gentoo didn't run the test suite they distributed their broken build meta-data to users. And the users started emailing me with weird bug reports.

Fortunately, other distributions like Debian get it right. Debian even keeps build logs for all releases of all packages on all architectures and makes them available on the web. For instance, the build log for libsndfile version 1.0.21-3 on the MIPS can be found here.

If anyone is using a distro which does not routinely run the test suite when building packages which supply a test suite, I recommend that they switch to a distro that does.

As GLaDOS would say, It’s been a long time. How have you been?

I was invited a few weeks ago to keynote at /dev/world 2010, a conference for Mac developers in Australia. It was my first-ever keynote, and you know, inspirational talks turn out to be kinda harder to give than technical talks. For those who didn’t attend, the talk intended to address the two most frequent questions I get asked about Pixar (“how did you get there?” and “what do you, uhh, actually do?”), and provide some insight into Pixar’s culture.

Two videos that I referred to in the talk and I think are an absolute must-see—whether you’re an engineer, CEO, manager, designer, artist or otherwise—are

• Ed Catmull’s talk at Stanford Business School: Keep Your Crises Small (~40 minutes, minus question time)
• Randy Nelson’s Learning and Working in the Collaborative Age (~10 minutes)

They complement Steve Jobs’s amazing commencement speech at Stanford in 2005. The number of insightful, genuine sound bites you can take away from those three talks are off the charts.

For all those who attended my keynote, I hope it was worthwhile. Thank you to everyone in the audience for giving me such a warm reception and for making me feel back at home, and thank you to the AUC for putting on a great conference.

Also, new website look, oooooo. It almost looks like it was made after 2000. Hopefully this will mean more regular updates on my blog than once per decade. I guess we’ll find out!

When Goanna reports a warning, sometimes a C preprocessor macro makes it hard to know what’s really going on in the code. I’ve added a new feature to the Visual Studio implementation that highlights each preprocessor macro invocation with a blue “squiggly”; the associated tooltip shows the (one-level) expansion of the macro. The context menu for the code document allows you to toggle between the macro markers and purple squigglies associated with Goanna warnings.

In the Goanna Central version, you’ll be able to dump all preprocessor macros in a file with an appropriate flag.

On Thursday September 16th, we held the 28th meeting of the Sydney Functional Programming group. The meeting was held at Google's Sydney offices and we had a bit less than 20 people show up to hear our two presenters.

First up we had Shane Stephens with a presentation titled "Exploring 3D Graphics with Togra". Togra (code available here) is a library for 3D graphics that Shane has at different times tried implementing in Python (with C for speed), Ocaml and Haskell before settling on the use of Arrows in Haskell.

Shane started off showing how he used to do it in Python and C and explained that the Python/C code was difficult to maintain and contained significant chunks of code that implemented type checking of data objects passed from Python. He also mentioned very briefly a failed attempt to implement the library with Monads. With the library is not finished, or even really ready for playing with Shane does think that Arrows are the right solution.

Our second presenter for the evening was Anthony Sloane of Macquarie University on the subject of the "Launchbury's Natural Semantics for Lazy Evaluation" with Scala code available on the same page. Tony set up a simple language and then walked us through the reduction rules for the language. This was a real nice introduction to a topic that can be daunting for people unfamiliar with the topic.

A big thanks to Shane and Tony for presenting and Google for providing the meeting venue and refreshments.

We’ve created a command-line version of Goanna for Windows, tentatively called “GoRun”. It’s simple to use: on the command line, just invoke the tool with a Visual Studio solution file and optionally, the particular projects you’d like to analyze.

If you’d like to try out the tool, please send an email to me, paul.steckler AT redlizards.com. You need to have Goanna Studio v.2.1 for VS2005, VS2008, or VS2010 installed.

I have released version 1.19-rc4 of Perdition. The key changes are:

• Fix parsing of NIS maps
• Fix a segmentation fault on start-up when the bind_address configuration option is used.
• Fix handling of the debug and quiet options when specified a configuration file
• Building without PAM libraries installed
• Documentation enhancements

The code and related libraries are available as tarballs here. More information is available in the announcement email. More information about perdition here.

Goanna Studio 2.0 has been a great hit, we have gotten a lot of positive feedback and we have also acted on very nearly all suggestions and bug reports to produce a shiny new Goanna Studio update 2.1. This means that a great many false positives have been eliminated, greater accuracy has been achieved and we have also fixed some bugs and there is even a performance improvement or two.

The fixed false positives and changes to checks include:

• ATH-sizeof-by-sizeof - a false positive involving array sizeofs has been fixed.
• FPT-cmp-null - a false negative when warning about using a function pointer directly in a condition, not using a condition operator.
• RED-unused-var-all now considers sizeof(x) to be a use of x.
• MEM-stack-global, MEM-stack-param and MEM-stack-param-ref now take into account re-assignments for globals or parameters
• SPC-uninit-struct now considers a struct with a field which is an array to be accessible without warning.
• ATH-cmp-unsigned-pos and ATH-cmp-unsigned-neg take into account comparisons with (unsigned)-1
• MEM-free-some doesn’t warn when you check the result of a malloc and exit (or return) if it is invalid
• RED-dead no longer warns about goto’s and breaks
• PTR-null-const-pos doesn’t warn about string literals
• EXP-null-stmt no longer warns about a non-empty else block or when there is an assignment or function call in the condition
• SEM-nonconst-call has been renamed to SEM-const-call
• SEM-global-write has been renamed to SEM-pure-global
• SEM-impure-call has been renamed to SEM-pure-call
• ATH-shift-bounds now warns when you shift by 64
• COP-assign-op-ret now warns about assignment operators that do not return a non-const reference to this

The Goanna Studio for Visualstudio also has some improvements and bug fixes:

• Support for additional options and CL environment variable support.
• Fixed bug involving a non Win32 or Win64 build target and the verbose flag
• Support for environmnent variables with non-alphabetic characters
• ProjectDir and SolutionDir macros now expand with a trailing backslash

We’ve also worked hard to squeeze even more performance where we can, and overall the Goanna analysis engine now scales better with the number of checks that are being used, and Interprocedural analysis is now slightly faster.

Other minor improvements and bug fixes are:

• Better handling of types that have been typedef’ed
• Better handling of implicit this parameter in member functions
• Better handling of simple conditions containing only variables
• Better identification of compound declarations
• Better handling of throw and catch statements
• Support for -std=gnu++0x and -std=c++0x command line arguments
• Improved support for c++0x standard (still incomplete)
• With Goanna Central Linux - ability to use specific rc files
• Goannacc now correctly identifies versions of GCC that are built for different targets

As usual, all current users get the upgrade for free. If you were a trial user in the past and need a trial extension visit: http://redlizards.com/trial-extension

As part of our efforts to expand the scope of Goanna’s C++ checks, we decided to look into copy control, since this backbone of class architecture can also cause plenty of problems. The most common bugs relating to copy control are memory leaks, which are hard to identify and track down, as they will generally not cause the program to crash. Therefore, they are a priority for us to find.

In addition to finding and warning about the most common flaws in copy control functions, we decided to take the opportunity to cover some of the rarer problems, too. Our ultimate aim was to give some kind of useful warning in any case of potential misuse of a class, since copy control is something that a lot of people can have trouble grasping.

While many of our copy control checks warn for convention violations rather than definite bugs, they all combine to ensure that classes follow widely-accepted best practices, to improve the overall readability and robustness of code. As a case study, I’ll demonstrate the construction of a simple class, showing the bugs and suggestions that Goanna points out along the way.

We’ll start with a class with an int pointer. Of course, if we want the pointer to point somewhere, we need to allocate some memory for it, so we’ll do that in a constructor.

1   class MyClass {
2     public:
3       MyClass();  //constructor
4     private:
5       int* xp;
6   };
7
8   //default constructor
9   MyClass::MyClass(){
10     xp = new int[10];
11  }

We all know what the problem with this is:

cop.cc:9: warning: Goanna[COP-dtor] Missing destructor for class `MyClass' whose
function `MyClass::MyClass()' allocates memory

cop.cc:9: warning: Goanna[COP-member-uninit] Not all members initialized in this
constructor

If there is no explicit destructor, the compiler will only call the synthesized destructor, which is a problem for our allocated memory. The synthesized destructor will release the pointer xp, but not the memory allocated to it - this is our responsibility.

The second warning is there because even though we have allocated memory to ‘xp’, we have failed to initialize the values in the array, which should really be done in the constructor.

Because we’re lazy, let’s define an empty destructor to make the warnings go away (because that’s what half of programming is all about). Here’s the updated class:

1   class MyClass {
2     public:
3       MyClass();    //default constructor
4       ~MyClass(){}  //destructor
5     private:
6       int* xp;
7   };
8  
9   //default constructor
10  MyClass::MyClass(){
11    xp = new int[10];
12    for (int i=0; i!=10; ++i){
13      xp[i] = 0;
14    }
15  }

Alas, Goanna still isn’t happy:

cop.cc:4: warning: Goanna[COP-dealloc-dtor] Class field `xp' has memory allocated
in a constructor that is not freed in the destructor

Let’s release the memory in the destructor.

17  //destructor
18  MyClass::~MyClass(){
19    delete[] xp;
20  }

Now our class is free from bugs. So when we run Goanna, we should get the all clear. Right?

cop.cc:18: warning: Goanna[COP-assign-op] Missing assignment operator for class
`MyClass' which uses dynamic memory allocation

cop.cc:18: warning: Goanna[COP-copy-ctor] Missing copy constructor for class
`MyClass' which uses dynamic memory allocation

Wrong! It seems we’re just digging ourselves deeper. The destructor is not the only thing the compiler will synthesize. In fact, for any class, it will synthesize up to 3 functions if they are not explicitly defined:

1. Destructor - there will always be one synthesized to release stack memory
2. Copy constructor - a constructor taking in a reference of the class type
3. Assignment operator - operator=() defined for the class

Even though we have defined a default constructor (with no parameters), the compiler will still synthesize a copy constructor if we have not provided one. The copy constructor is used when instances of a class are copied, for example, passed as parameters or used in containers. Surprisingly, it is also invoked when an instance of the class is initialized at its declaration. For example:

MyClass a;       //default constructor
MyClass b(a);    //copy constructor
MyClass c = a;   //copy constructor
MyClass d; d=a;  //default constructor; assignment operator

It can sometimes be confusing which operators or functions are being invoked, and for such reasons it is important to ensure that all functions are explicitly defined when appropriate. Basically, if a user-defined destructor is required, then an assignment operator and copy constructor will also be required. This is sometimes called the ‘Rule of 3′, suggesting that if one of these three is required, all probably are.

So let’s add our copy constructor and assignment operator to the class, and to avoid any additional warnings, we’d better make sure we allocate the memory required for xp. And while we’re at it, we should get rid of the magic number used for the array size:

1   class MyClass {
2     public:
3       MyClass();                             //default constructor
4       MyClass(const MyClass& other);         //copy constructor
5       void operator=(const MyClass& other);  //assignment operator
6       ~MyClass();                            //destructor
7     private:
8       static const int ARR_INIT_SIZE = 10;
9       int* xp;
10  };
...
18  //copy constructor
19  MyClass::MyClass(const MyClass& other){
20    xp = new int[ARR_INIT_SIZE];
21    for (int i=0; i!=ARR_INIT_SIZE; ++i){
22      xp[i] = other.xp[i];
23    }
24  }
25
26  //assignment operator
27  void MyClass::operator=(const MyClass& other){
28    delete[] xp;  //reallocate the memory in case the size has changed
29    xp = new int[ARR_INIT_SIZE];
30    for (int i=0; i!=ARR_INIT_SIZE; ++i){
31      xp[i] = other.xp[i];
32    }
33  }

The class is starting to get bulky, but at least we can be sure we’re helping to make it safe for any creating, copying and destroying that we might be doing. However, Goanna isn’t quite happy with the class yet:

cop.cc:27: warning: Goanna[COP-assign-op-ret] Assignment operator `MyClass::operator='
does not return a non-const reference to `this'

cop.cc:29: warning: Goanna[COP-assign-op-self] Assignment operator `MyClass::operator='
does not check for self-assignment before allocating memory to a class member

The first warning is there because it is the convention that an assignment operator will return a reference to the target of the assignment. Such conventions exist so that all objects can be treated like primitive types, and to give the programmer more freedom to write intuitive code. For example:

MyClass a,b,c;
(a = b) = c;
(a = c).f();

The problem causing the second warning, is that self-assignment is generally perfectly legal code. For example:

MyClass c;
c = c;

However, calling a class’ assignment operator on itself will cause problems if dynamic memory allocation takes place. In our assignment operator, we free the memory allocated to ‘xp’, before allocating a fresh store. If the class instance called the assignment operator on itself, then the memory that being copied from in the 4th line of the operator will also be fresh. This means that self-assignment will basically lead to the object being populated with uninitialized data, which is almost certainly not the intention of the programmer. To handle this, we simply need to ensure memory manipulation only takes place if ‘this’ and the parameter refer to different instances of the class.

Our assignment operator must be altered to fix these two problems:

25  //assignment operator
26  MyClass& MyClass::operator=(const MyClass& other){
27    if (this != &other){  //check for self-assignment
28      delete[] xp;  //reallocate the memory in case the size has changed
29      xp = new int[ARR_INIT_SIZE];
30      for (int i=0; i!=ARR_INIT_SIZE; ++i){
31        xp[i] = other.xp[i];
32      }
33    }
34    return *this;  //return a reference to 'this'
35  }

After these changes, Goanna will not give any more warnings, and the class will be very robust. Hopefully this has provided you with some insight to some of our copy control checks, and given you a quick revision on some of the important things to keep in mind when creating classes. We’re still trying to expand our range of C++ checks further, to include checks on the proper use of iterators, containers and exception handling, and many other constructs.

Here is our completed class:

1   class MyClass {
2     public:
3       MyClass();                                 //constructor
4       MyClass(const MyClass& other);             //copy constructor
5       MyClass& operator=(const MyClass& other);  //assignment operator
6       ~MyClass();                                //destructor
7     private:
8       static const int ARR_INIT_SIZE = 10;
9       int* xp;
10  };
11 
12  //default constructor
13  MyClass::MyClass(){
14    xp = new int[ARR_INIT_SIZE];
15    for (int i=0; i!=ARR_INIT_SIZE; ++i){
16      xp[i] = 0;
17    }
18  }
19 
20  //copy constructor
21  MyClass::MyClass(const MyClass& other){
22    xp = new int[ARR_INIT_SIZE];
23    for (int i=0; i!=ARR_INIT_SIZE; ++i){
24      xp[i] = other.xp[i];
25    }
26  }
27 
28  //assignment operator
29  MyClass& MyClass::operator=(const MyClass& other){
30    if (this != &other){  //check for self-assignment
31      delete[] xp;  //reallocate the memory in case the size has changed
32      xp = new int[ARR_INIT_SIZE];
33      for (int i=0; i!=ARR_INIT_SIZE; ++i){
34        xp[i] = other.xp[i];
35      }
36    }
37    return *this;  //return a reference to 'this'
38  }
39 
40  //destructor
41  MyClass::~MyClass(){
42    delete[] xp;
43  }

The second beta release of Data.Array.Accelerate (version 0.8.0.0) includes support for all array operations in the CUDA backend — except for a new stencil operation that is new in this release and currently only supported by the interpreter.  The CUDA backend requires CUDA 3.x and has been tested on consumer-grade GeForce cards, TESLA high-performance GPUs, and the new Fermi cards.

Permalink | Leave a comment  »

For a couple of weeks after AusHac 2010 I didn't manage to find any time to working on DDC at all, but I'm now back on it and late last week I reached the second milestone on the LLVM backend for DDC. The backend now has the ability to box and unbox 32 bit integers and perform simple arithmetic operations on valid combinations of them.

Disciple code that can currently be compiled correctly via LLVM includes basic stuff like:

  identInt :: Int -> Int
  identInt a = a

  plusOneInt :: Int -> Int
  plusOneInt x = x + 1

  addInt :: Int -> Int -> Int
  addInt a b = a + b

  addInt32U :: Int32# -> Int32# -> Int32#
  addInt32U a b = a + b

  addMixedInt :: Int32# -> Int -> Int
  addMixedInt a b = boxInt32 (a + unboxInt32 b)

  cafOneInt :: Int
  cafOneInt = 1

  plusOne :: Int -> Int
  plusOne x = x + cafOneInt

where Int32# specifies an unboxed 32 bit integer and Int32 specifies the boxed version.

While writing the Haskell code for DDC, I'm finding that its easiest to generate LLVM code for a specific narrow case first and then generalize it as more cases come to light. I also found that the way I had been doing the LLVM code generation was tedious and ugly, invloving lots of concatenation of small lists. To fix this I built myself an LlvmM monad on top of the StateT monad:

  type LlvmM = StateT [[LlvmStatement]] IO

Using this I can then generate a block of LLVM code as a list of LlvmStatements and add it to the monad using an addBlock function which basically pushes the blocks of code down onto a stack:

  addBlock :: [LlvmStatement] -> LlvmM ()
  addBlock code
   = do	  state	<- get
          put (code : state)

The addBlock function is then used as the base building block for a bunch of more specific functions like these:

  unboxInt32 :: LlvmVar -> LlvmM LlvmVar
  unboxInt32 objptr
   | getVarType objptr == pObj
   = do     int32    <- lift $ newUniqueReg i32
            iptr0    <- lift $ newUniqueNamedReg "iptr0" (pLift i32)
            iptr1    <- lift $ newUniqueNamedReg "iptr1" (pLift i32)
            addBlock
                    [ Comment [ show int32 ++ " = unboxInt32 (" ++ show objptr ++ ")" ]
                    , Assignment iptr0 (GetElemPtr True objptr [llvmWordLitVar 0, i32LitVar 0])
                    , Assignment iptr1 (GetElemPtr True iptr0 [llvmWordLitVar 1])
                    , Assignment int32 (Load iptr1) ]
            return  int32


  readSlot :: Int -> LlvmM LlvmVar
  readSlot 0
   = do   dstreg    <- lift $ newUniqueNamedReg "slot.0" pObj
          addBlock  [ Comment [ show dstreg ++ " = readSlot 0" ]
                    , Assignment dstreg (Load localSlotBase) ]
          return    dstreg

  readSlot n
   | n > 0
   = do   dstreg    <- lift $ newUniqueNamedReg ("slot." ++ show n) pObj
          r0        <- lift $ newUniqueReg pObj
          addBlock  [ Comment [ show dstreg ++ " = readSlot " ++ show n ]
                    , Assignment r0 (GetElemPtr True localSlotBase [llvmWordLitVar n])
                    , Assignment dstreg (Load (pVarLift r0)) ]
          return    dstreg

  readSlot n = panic stage $ "readSlot with slot == " ++ show n

which are finally hooked up to do things like:

  llvmVarOfExp (XUnbox ty@TCon{} (XSlot v _ i))
   = do   objptr    <- readSlot i
          unboxAny (toLlvmType ty) objptr

  llvmVarOfExp (XUnbox ty@TCon{} (XForce (XSlot _ _ i)))
   = do   orig      <- readSlot i
          forced    <- forceObj orig
          unboxAny (toLlvmType ty) forced

When the code generation of a single function is complete it the list of LlvmStatement blocks is then retrieved, reversed and concatenated to produce the list of LlvmStatements for the function.

With the LlvmM monad in place converting DDC's Sea AST into LLVM code is now pretty straight forward. Its just a matter of finding and implementing all the missing pieces.