No tengo la menor idea

2010-05-10

Wreckage 0.0.0

Filed under: haskell — robgreayer @ 16:00

Haskell 98 (and Haskell 2010) has a ‘sort of’ record system, algegraic data type with named fields. The (unreleased, but githubbed) Wreckage library is yet another attempt to implement a better record system within Haskell, without sacrificing some of the nice features of the named fields system. There are a few other ’embedded’ record systems out there, such as records, has, and the well known hlist. Wreckage’s novelty is in its use of type level strings. It is implemented with generous support from type families (to implement things like type/value heterogeneous list sorting), Template Haskell, Quasi Quotation, and other non-standard features too numerous to mention. Indeed it is a veritable train-wreck of Haskell extensions, hence the name (‘wreck’ being homonymous with ‘rec’, shorthand for ‘record’. Hilarious, I know).

There are three key features of ADTs with named fields that would be a shame to sacrifice.

Construction With Field Names

Given an ADT with named fields, e.g.

    data Person = Person {
        name :: String,
        age :: !Int
    }

we can build a Person value using the field names, instead of relying on their positions within the record. We can supply the fields in any order, and can leave out non-strict fields:

    jane = Person { age = 21, name = "Jane Doe" }
    john = Person { age = 30 }

Access and Update with Field Names

Given the definitions above, we can access components of a Person value with a label:

    janesAge = age jane

and, with a special syntax, can update the fields of a person value:

jim = john { name = "Jim Beam" }
olderJane = jane { age = age jane + 5 }

Although the above syntax for update is convenient, it doesn’t compose well for ‘deep’ update (which is a problem Wreckage tries to resolve, in the style of fclabels).

Pattern Matching with Field Names

Field names work nicely with Haskell pattern matching:

    nameAndAge (Person { name = n, age = i }) = n ++ ": " + show i

Wreckage 0.0.0

Wreckage attempts to preserve these features, in spirit, while still implementing basic records ‘under the covers’ as simple algebraic data types. An equivalent Wreckage record would be defined as follows:

    wreck [d|
        data Person {
            name :: String,
            age :: !Int }
        |]

The declaration above creates a ‘Person’ data type with two fields, along with a constructor ‘mkPerson’, and many (many) instances of various type classes that will make record construction and destruction ‘work’.

Before showing examples of how to use Wreckage records, I’ll expand the example to illustrate one key feature of wreckage:

    wreck [d|
        data Pet {
            name :: String,
            age :: !Int
        }|]

    wreck [d|
        data Person {
            name :: String,
            age :: !Int,
            pet :: Maybe Pet
        }|]

As plain data declarations, these would be illegal in Haskell, because of the reuse of the names ‘name’ and ‘age’ between the two records. Wreckage lifts this restriction. Field names can be reused among records, regardless of what scope the wreckage record is declared in.

Now we can construct values of type Person and Pet:

    fido = mkPet ( ℓname =: "Fido" :* ℓage =: 7 :* ())
    jane = mkPerson ( ℓage =: 21 :* ℓname = "Jane Doe" :* ())

The syntax for construction is slightly different, but has the same essential features: we need only specify strict fields at the time of construction (not specifying a strict field would be a type error), and can specify the fields in any order. The ℓ-notation (which works by leveraging a GHC compiler feature, rather than a Haskell language extension) will be explained fully later, but it introduces a type-level string, which is used instead of a normal identifier to represent a field name.

Access and update of Wreckage records is straightforward if slightly different than with ADTs with named fields:

    janesAge = get ℓage jane
    janesPetsAge = get (ℓpet:-ℓage) jane

    -- change jane's pet's name
    jane' = set (ℓpet:-ℓage) jane 8

Fields can be composed, or chained, together for both access and update, as shown above. Multiple fields can be accessed simultaneously:

    (nm :* age) = get (ℓname :* ℓage) jane

Without much effort upon the part of the Wreckage library, we can pattern match on Wreckage records using the View Patterns extension, implemented in GHC:

    nameAndAge (get (ℓname:*ℓage) -> (n:*i)) = nm ++ ": " ++ show i

Note that the ‘nameAndAge’ function above works both on fido and on jane (i.e. on the Person type and on the Pet type). Or, indeed, on any other wreckage record type, declared in any module in any package, that happens to also have a name field and and age field. With other ’embedded’ record systems, an ‘age’ field defined in one module will clash with an ‘age’ field defined in another module, however the fields are defined.

Person and Pet are (under the covers) just algebraic data types (without field labels), so access and update ought to be about as efficient as with standard field labels.

Wreckage and extensability

Wreckage is intended to have a good story regarding exstensibility, implementing something like scoped labels. Right now, the implementation is rudimentary, with the addition of just two operations: extend and restrict (under the covers extension works right now much like HList, but I intend future versions to work a bit differently). A Wreckage record can be extended with addtional fields:

    janeV2 = jane `extend` (ℓheight =: 1.7)

    janesHeight = get ℓheight janeV2

A field can be removed from a record:

    janeV3 = janeV2 `restrict` ℓage

    s = nameAndAge janeV3 -- type error!

Records are ‘scoped’ in that you can extend a record with a field name it already contains. The new field simply hides the existing field (until the field is removed via ‘restrict’).

The egregious hack

The ℓ notation used above ‘works’ in GHC and GHCI through the use of the Haskell preprocessor feature of GHC. A program can be passed to GHC or GHCI, which is used to transform each .hs file just prior to compilation (and after CPP has possibly been run on the source):

    ghci -F -cmdF prewreck

The prewreck program (included with wreckage) transforms and input file by changing any ℓ sequence into a quasi-quotation. The quasi-quotation could be used directly, but the ℓ-notation is more readable. One day something almost as nice might work out of the box with GHC.

Caveats

Wreckage may have exposed a performance issue with the GHC compiler (6.12.1 or 6.12.2) in that there’s an exponential blowup of memory used by the compiler when trying to optimize (-O1) a wreckage client (no problem with the library itself). Turning off optimization (-O0) and clients compile quickly.

Wreckage doesn’t try to deal with polymorphic records, yet. There’s no technical difficulty with them, but the first implementation of the wreck function was made simpler by ignoring them, for now.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: