It works this time

When I started learning Haskell I heard that the type system could be used to check all kinds of constraints at compile time -- far beyond just the type of the data. For the most part I have found this not to be the case -- not because the type system can't do these things but because most people who program Haskell are either 1) not leet enough to use it that way (this includes me) or 2) too leet for me to understand their code, so I have no idea what kind of constraints are being checked.

But I did run into a beautiful example using Maps. A Map stores data with ordered keys, so to do that you need an ordering function, and they used the most obvious possible type signature for that ordering:

1 compare :: a -> a -> Ordering

And here's the great thing: the Map consistency cannot possibly be screwed up by using mutable keys.

Ah, but that's easy, you say: just use immutable keys -- make them const. But this is even better: you don't have to use immutable keys. I could use a key like this:

1 data Key = Key { 2 x :: Int 3 , y :: IORef Int 4 }

That's mutable. I can change it. Even while it's being used as a key. But there is no way (and I really hope someone doesn't come and tell me that there is a way because that would make me sad) for compare to see those changes -- because of its type.

In fact you can pack as much mutable state as you want into the Key, and it is partitioned off cleanly from ever affecting the ordering.

But here's what I really love about this: it works because the guys who wrote Map picked the simplest most obvious type for compare. It's the type you'd come up with if someone pointed a gun to your head and said "you have 5 seconds give me the type for compare". They could have written it

1 compare :: (Monad m) => a -> a -> m Ordering

except that that's substantially less obvious and in this case turns out to be undesirable.

It's not always like this. A lot of the standard functions for operating on lists could have been made monadic because they don't need consistency. This is one of those rare beautiful cases of the language working exactly the way it's supposed to.

(In other news, untracked side-effects may be "dangerous" but nothing beats the havoc of using a backtracking monad transformer on the ST monad. Nothing I tell you.)

Visual Editors

While I sit here typing away at an especially depressing bit of code there's about 85 lines of Vim script trying to make the indentation look pretty by searching the nearby text for symbols it likes and trying to shift things around appropriately, using lots of regexes. At first this seems like a terribly inefficient combination -- the compiler already has a parser that knows where the structural elements in the source code start and stop -- why does Vim have to duplicate (poorly) this logic using regexes?

Of course it doesn't work like that: the compiler is designed to accept a complete, fully written program, and as a service to you doesn't tolerate deviations from the syntax, but the editor has to accept gross syntactic problems because you're just about to change it.

Which is one reason why linear flowing text is such a great way to represent what is really a hierarchical and rigidly structured document -- it's more flexible than the document it's ultimately going to be, so it can represent incomplete syntax. I can write this:

if ( ) {
}

And fill in the details later.

I was thinking about this because I was wondering why visual editors -- like LabView's flow thingy or EasyC or Scratch aren't more commonly used. I don't use them and all the ones I've tried annoy the hell out of me but in theory they seem like a better idea than pure text editors because they could do so much more. (Even super fancy IDEs that do a ton ultimately start from just text, which is why they will always screw stuf up (and get confused by incompletely written code)).

So what's missing? There are a few things I can see rigt away. In my opinion, to be useful visual editors must:

1. Avoid visual distractions

This is where EasyC is very good and Scratch could be better. Think about what a text editor gives you: small characters freely placed on a large, blank canvass. Blocks that fill the screen, excessive background colors (notice most editors let you use background colors in syntax highlighting and no one uses them) or lines and arrows cluttering up the space will just make you sad when looking at your code.

2. Represent incomplete syntax flexibly.

This includes incomplete syntax in all directions -- maybe you write a loop and omit the body, or maybe you write the body but omit the loop -- any conceivable way to omit parts of a program must be possible.

3. Give the programmer flexibility in laying out the code.

This might not be so much of an issue for structured imperative languages like C (though I think it's still necessary), but it would be absolutely inconceivable to write Haskell (or Lisp dear god) in a language that did the layout for you -- functions can be combined in too many different ways to derive the feel of a piece of code from the syntax.

This gets at a deeper point which is that editors must be able to communicate more than the code; they also must communicate what the code means in your head, by more than just identifier names and comments. Python tries to wrest this ability from you by using indentation to indicate blocks, and to some extent does succeed in frustrating me like that but they left enough flexibility in the language to make the code expressive.

4. Not be marketed as a kids' toy.

Because while many adults might be ok spending their days playing with a kids' toy, there is a certain age at which this is very unfashionable, and it's an age where a lot of programming gets learned. And a lot of habits are frozen.

5. Be as polished as a typical text editor.

I would never use EasyC for serious programming because it jus takes too much pointing and clicking, and it's slow. The thing is, even if text editors are starting out from a disadvantage, they've just been around so much longer, so many more people use them, and have acquired so many more hours of development and testing that most of the sharp edges have been worn off. And with a tool that you interface with constantly it matters less that it have a clean design than that the sharp edges be removed.

This last point is also why I keep using Vim, despite the many horrific stories I have accumulated while using it. Like how I was wondering why paragraph formatting in comments works strangely -- it formats them OK and keeps the leading '#' but it seems to hit everything in the comment even when I use 'gqip' to get just one paragraph. The reason (of course) was that Vim over the years has acquired two entirely different ways of delimiting paragraphs: the one used to format paragraphs by gq, and an entirely different one used to capture a paragraph with ip -- the former being a series of hacks for getting around things like comments and lists and the latter being a huge list of NROFF macros describing spaces and such. But I keep using Vim because most of the sharp edges have been hacked away and it's scriptable so I can get rid of most of the ones that still bug me (except paragraph formatting which I don't have the energy to tackle).

This last point is also the reason I think it's unlikely we'll get away from programming in text any time soon -- there's just too much effort put into text editing to make it worth starting from scratch. NI is trying with LabView, and a number of researchers are trying with tools for kids to program. (Notice both of these are about getting people who otherwise wouldn't be programming (scientists who have other stuff to do, or kids who have other stuff to do) to do so in a very limited boxed-in way -- but importantly the target is people who don't have preconceived notions about what programming is. The scientists aren't going to turn into the next generation of software developers but the kids might -- maybe they'll change stuff. And maybe I'll hate it and end up complaining about how kids these days do it all wrong. But oh well.)

Literate literate literate programming

In an effort to better document my Haskell experiments I wrote a set of reST directives for Sweave-like literate programming.

What makes rstweaver different from Sweave is that a single reST document can write and execute multiple source files, in stages, and parts can be inserted or modified, then reexecuted. This gives the illusion of an interactive session for a language that is largely not interactive.

If you look at the tutorial you will notice that it too includes literate reST... which in turn includes literate Haskell. It is literate literate programming!

And the society for putting things inside of other things demands that we go one level further: an excerpt from the tutorial: I present you literate literate literate programming:

-- so-nested.rst --

You can name the stages: .. weaver:: test4.rst exec block .. haskell:: Named.hs :name: imports import Control.Monad And then go back and edit them: .. weaver:: test4.rst exec block .. haskell:: Named.hs redo :name: imports import Control.Monad import Control.Applicative Or insert a stage after a named stage: .. weaver:: test4.rst exec block .. haskell:: Named.hs :after: imports x = 5

You can name the stages:

-- test4.rst --

.. haskell:: Named.hs :name: imports import Control.Monad

-- Named.hs --

1 import Control.Monad

And then go back and edit them:

-- test4.rst (cont) --

.. haskell:: Named.hs redo :name: imports import Control.Monad import Control.Applicative

-- Named.hs (cont) --

1 import Control.Monad 2 import Control.Applicative

Or insert a stage after a named stage:

-- test4.rst (cont) --

.. haskell:: Named.hs :after: imports x = 5

-- Named.hs (cont) --

4 x = 5

Haskell is that guy

I've been programming a lot of Haskell recently, and I've noticed something.

Haskell is that guy. You know the one who's like "pshhh I don't need side-effects" and then obsesses over side-effects. And I mean obsesses.

I've been using Template Haskell, which involves traversing and creating syntax trees, so, a very tree-like sort of task, you know that kind that functional languages are just perfectly suited for. Except for one little thing.

The Quotation Monad.

It's really a terribly minor detail. It does one tiny tiny hardly significant thing: it keeps a counter to make unique names. It's really not at all what Template Haskell or my project are about. It would be better not to think about it.

The problem is that quotation, being a monad, changes the type of expressions, and you then have to pull that type up the syntax tree using <*>so<$>many=<<annotations>>=, or use a do block and make everything flat and linear, losing all the benefit of a functional language.

Here's an example:

-- Main.hs --

1 matchLambda kw (Match pat body whrs) = 2 let 3 names = patNames pat 4 parts = bodyParts body 5 qLams = [buildLambda (names ++ bNames) <$> (expToSimpExp kw x) 6 | (bNames, x) <- parts 7 ] 8 in do 9 lams <- sequence qLams 10 whrs' <- fmap (id =<<) $ sequence $ (decToSimpDecs kw) <$> whrs 11 tup <- buildTuple lams 12 return $ letify whrs' tup

Granted it's still shorter than it would have been in Java, but it could be so much better if not for that one little counter. If you look at my code it looks like I wrote 500 lines for manipulating the Q monad and maybe a little bit here and there that deals with syntax trees -- especially since the parts that don't use the Q monad are short and clean.

Worse, the monad operators are the most visually familiar parts of the code, so someone who had no idea what the code does but knows Haskell would look at it and say "well, I don't know what this does, but I can see you're using a monad".

The problem is that the inconvenience of using a monad grows with the depth with which it is nested in the syntax tree. So

-- Main.hs --

1 f <$> a

is no trouble but

-- Main.hs --

1 f <$> (g <$> (h <$> a) <*> (pure 2)) <*> (pure 3)

is a pain, and has none of the beauty of

-- Main.hs --

1 f (g a 2) 3

Is there any design reason (other than syntactic) why monads should be harder to use when they are deeper? I do not know -- it's possible there is and I haven't seen it yet.

It turns out it's actually fairly simple to insert the <$>applicative<*> operators in the right place automatically (simple in terms of the idea -- it took a lot of code to get right). I don't have the energy to describe it right now but it's kind of obvious if you think about it -- it's probably been done before but I don't know how to search for it. Just trust that the following code works:

-- Demo.hs --

1 {-# LANGUAGE TemplateHaskell #-} 2 3 import Language.Haskell.TH.MetaLang 4 import Language.Haskell.TH.MetaLang.ApplicativeLang 5 6 main = do 7 print $ $(apl [| 8 let a = (nd [0,1]) 9 in 10 (a, a, a) 11 |])

[(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)]

I mean no disrespect to Haskell -- it's a great language, this one problem has just been irritating me. But I may or may not have solved it now.

(It's also interesting that the Q monad shouldn't, I think, have the usual problem of the interaction between lazy evaluation and side-effects, because you don't care what order the counter gets incremented in, just that it does).

Other random things:

• pozorvlak's tutorial on Template Haskell is very goood.

You can scrap it and write something better but let me keep R ;)

Ross Ikaha (via Xi'an -- thanks ;) ) gives a nice example to show why R is basically impossible to optimize:

> f = function() {

> if (runif(1) > 0.5) {

> x = 10

> }

> x

> }

x in the last expression could be a local or a global, and this won't be known until runtime!

That's pretty good.

I wonder if this will always return 10:

> f = function() {

> a = 10

> a

> }

> f()

[1] 10

Maybe we could optimize it out? No:

> regular.equals <- `=`

> `=` = function(...) {

> with(parent.frame(), a <- 11)

> }

> f()

[1] 11

> `=` <- regular.equals

OK but assigning to `=` is really cheating. This is cheating too:

> regular.brace = `{`

> `{` = function(...) 11

> f()

[1] 11

> `{` = regular.brace

If `=` and `{` weren't available for assignment, is there any way to make f not return 10? Well there's this, but it's hardly "making f return 10":

> body(f) = quote(11)

> f()

[1] 11

I can't think of any other way to attack it; so if you block all those I guess we can declare this function safe ;)

How about this one:

> g = function(x, y) {

> x + y

> }

Could we safely say that while g() is being called, f() will never be called at the same time (ie so that we could overlay their stacks?)

No, not even close. There are a million ways to break that:

> g(f(), f())

[1] 22

(Lazy evaluation -- f() is called while executing g())

> normal.plus = `+`

> `+` = function(a, b) UseMethod("+")

> `+.numeric` = function(a, b) { f() * a * b }

> g(1, 2)

[1] 22

> `+` = normal.plus

(Generic `+` is not uncommon).

Well at least can we say g() will always evaluate both arguments? No:

> g(return(2), print("hi"))

[1] 2

Which can make code that looks like an error be valid:

> g(return(2), not.defined)

[1] 2

If you assume g() is strict you will knock out some perfectly legitimate R code :)

Likewise an explicit call to return() doesn't have to actually do anything:

> g = function(x) {

> 3

> }

> g(return(2))

[1] 3

I also find these hacks delightful:

> delayedAssign('b', {b <- 7; 8})

> a <- b

> a

[1] 8

> b

[1] 7

> x = '@'

> up = function() {

> x. <- x

> x <<- intToUtf8(utf8ToInt(x)+1L)

> delayedAssign(x, up(), ass=.GlobalEnv)

> x.

> }

> up()

[1] "@"

> A

[1] "A"

> B

[1] "B"

> C

[1] "C"

> D

[1] "D"

> backw = function(...) {

> args = as.list(substitute(list(...)))[-1L]

> env = parent.frame()

>

> for (arg in rev(args)) {

> res <- eval(arg, env)

> }

> res

> }

> environment(backw) = baseenv()

> `{` = backw

> fib = function(n) {

> a

> for (i in 1:n) {

> a = b - a

> b = a + b

> }

> b = 1

> a = 1

> }

> fib(8)

[1] 34

> lex.scope = function(...) {

> args = as.list(substitute(list(...)))[-1L]

> parent = parent.frame()

> env = new.env(parent=parent)

>

> for (arg in args) {

> res <- eval(arg, env)

> }

> res

> }

> environment(lex.scope) = baseenv()

> `{` = lex.scope

> {

> x = 2

> {

> x = 3

> }

> x

> }

[1] 2

(Hey, that one could actually be useful).

> evanescent = function(x, v) {

> force(v)

> env = parent.frame()

> name = as.character(substitute(x))

>

> delayedAssign(name, {

> env[[name]] = alist(x=)$x

> v

> }, ass = env

> )

> }

> environment(evanescent) = baseenv()

> `=` = evanescent

> a = 2

> a

[1] 2

> a

Error in eval(expr, envir, enclos) :

argument "a" is missing, with no default

My thoughts on all this: R is a wonderful and flexible language, but it is entirely not the right language for intense numerical calculation: it is simply too flexible to be fast. And unfortunately whenever you're trying some algorithm that hasn't been done before, it will necessarily not already be written in C, and you find yourself having to make a choice: at what point is it too slow to keep in R, and the best thing to do is to give up and rewrite it in C?

The thing is, as an interactive environment, R's flexibility really gains something (think how you'd implement with() in Python). I personally am OK with the current system of using R for high level code and ducking to C for tight loops; it's better than trying to make one language be good at 2 different things.

GHC ImplicitParams are nice, but they're not really Haskellesque

With appropriate options, GHC let's you do something like:

-- imp-params.hs --

1 {-# LANGUAGE ImplicitParams #-} 2 3 main = do 4 let exp = ?x + ?y 5 print exp where 6 ?x = 3 7 ?y = 7

10

If you look at the type of ?x + ?y you can see that the unbound variables are reflected in the type.

-- imp-params.hs --

1 {-# LANGUAGE ImplicitParams #-} 2 {-# LANGUAGE NoMonomorphismRestriction #-} 3 4 dexp = ?x + ?y

ghci> :t dexp

dexp :: (?x::a, ?y::a, Num a) => a

(Sorry about lifting the monomorphism restriction -- I didn't want to add a type signature because that would defeat the whole point of inspecting the type with ghci).

I like this feature, but it's not really in the spirit of Haskell. Though they did do a good job of covering up the problems; if you look at that type signature you'll see that, even though dexp takes parameters, it does not have a function type: it has the type of its result. This is important because

ghci> :t (+)

(+) :: (Num a) => a -> a -> a

In particular, if ?x were a function type (like the name "implicit parameters" suggests), you would not be allowed to use + on it. But you can see that this is deceptive...

-- deceptive.hs --

1 {-# LANGUAGE ImplicitParams #-} 2 3 dexp :: (?x::Int) => Int 4 dexp = ?x

ghci> :t dexp

dexp :: (?x::Int) => Int

ghci> print dexp

<interactive>:1:6: Unbound implicit parameter (?x::Int) arising from a use of `dexp' at <interactive>:1:6-9 In the first argument of `print', namely `dexp' In the expression: print dexp In the definition of `it': it = print dexp

If it were really just an Int as its type claims, you should be allowed to print it. But if it's not really just an Int you should not be allowed to use + on it.

(Actually technically you are allowed to print it, which is why I had to use ghci to get that error:

-- deceptive.hs (cont) --

1 {-# LANGUAGE ImplicitParams #-} 2 3 dexp :: (?x::Int) => Int 4 dexp = ?x 5 6 main = do 7 print dexp

deceptive.hs:6:0: Implicit parameters escape from the monomorphic top-level binding of `main': ?x::Int arising from a use of `dexp' at deceptive.hs:7:10-13 Probable fix: give these definition(s) an explicit type signature or use -XNoMonomorphismRestriction When generalising the type(s) for `main'

You see the unbound variables leaked all the way out in to main, changed its type, and hit the monorphism restriction. Sneaky.)

Haskell has of course encountered this dilemma before, which is where functors come from. And in functors the magic is always made explicit:

-- params-with-functors.hs --

1 dexp :: Int -> Int 2 dexp = id 3 4 instance Functor ((->) a) where 5 fmap f p = f . p

ghci> :t fmap (5-) dexp

fmap (5-) dexp :: Int -> Int

ghci> fmap (5-) dexp 3

2

It's just like an implicit (unnamed) parameter, except it doesn't leak up the call stack by itself -- you have to do so explicitly with fmap.

But whether or not we're ok with this breach of Haskellinity is really beside the point: you can't do that much with implicit parameters anyway. As I pointed out last time you have no runtime access to implicit parameters, so you can't do anything like R's with(), which would really be the biggest use for dynamic binding.

But this is Haskell, surely we can implement dynamic binding!

Since an "unbound expression" is basically a map from a named set of parameters to its resulting value, we could represent it as a map taking an HList Record.

-- dyn-bind.hs --

1 {-# LANGUAGE EmptyDataDecls #-} 2 {-# LANGUAGE TemplateHaskell #-} 3 {-# LANGUAGE DeriveDataTypeable #-} 4 5 import Data.HList 6 import Data.HList.Label4 7 import Data.HList.TypeEqGeneric1 8 import Data.HList.TypeCastGeneric1 9 import Data.HList.MakeLabels 10 11 $(makeLabels ["labX", "labY"]) 12 13 x rec = rec # labX 14 y rec = rec # labY 15 16 z rec = (x rec) + (y rec)

Here x represents ?x, ie it takes the supplied variables and just grabs the one called x. Likewise for y. Then z represents ?x + ?y. These have types:

ghci> :t x

x :: (HasField (Proxy LabX) r v) => r -> v

ghci> :t y

y :: (HasField (Proxy LabY) r v) => r -> v

ghci> :t z

z :: (HasField (Proxy LabX) r v, HasField (Proxy LabY) r v, Num v) => r -> v

And we can bind them:

-- dyn-bind.hs (cont) --

18 bindings = 19 labX .=. 5 .*. 20 labY .=. 7 .*. 21 emptyRecord 22 23 main = do 24 print $ x bindings 25 print $ y bindings 26 print $ z bindings

5 7 12

And rebind them:

-- dyn-bind.hs (cont) --

18 b1 = 19 labX .=. 5 .*. 20 labY .=. 7 .*. 21 emptyRecord 22 23 b2 = 24 labX .=. 9 .*. 25 labY .=. 12 .*. 26 emptyRecord 27 28 main = do 29 print $ z b1 30 print $ z b2

12 21

So that's all the structure we need; now we just need ways to combine them. Here you can see we are going to run into problems, because if we start with say +, which is (Num a) => a -> a -> a, and bind it to its first dynamic argument, we will get a dynamic function. Meaning the seconding binding has a different type signature. Or, as an example,

-- dyn-bind.hs (cont) --

18 call1 f dexp rec = f (dexp rec)

ghci> :t (+)

(+) :: (Num a) => a -> a -> a

ghci> :t call1 (+) x

call1 (+) x :: (Num t1, HasField (Proxy LabX) t t1) => t -> t1 -> t1

ghci> :t call1 (call1 (+) x) y

call1 (call1 (+) x) y :: (Num t1, HasField (Proxy LabX) t11 t1, HasField (Proxy LabY) t t11) => t -> t1 -> t1

That does not look at all like the right type. And of course binding it fails:

ghci> (call1 (call1 (+) x) y) b1

<interactive>:1:18: No instance for (HasField (Proxy LabX) Integer t1) arising from a use of `x' at <interactive>:1:18 Possible fix: add an instance declaration for (HasField (Proxy LabX) Integer t1) In the second argument of `call1', namely `x' In the first argument of `call1', namely `(call1 (+) x)' In the expression: (call1 (call1 (+) x) y) b1

So the second binding is a different type...

-- dyn-bind.hs (cont) --

18 call1 f dexp rec = f (dexp rec) 19 call2 f dexp rec = (f rec) (dexp rec)

ghci> (call2 (call1 (+) x) y) b1

12

It is of course totally contrary to the spirit of dynamic binding to require the programmer to pay such close attention to whether this is the first or second or any dynamic combination. And this is where things start to fall apart...

The natural way to make the call operation generalize the signatures of call1 and call2 would be to use a typeclass:

-- dyn-bind2.hs --

1 {-# LANGUAGE EmptyDataDecls #-} 2 {-# LANGUAGE TemplateHaskell #-} 3 {-# LANGUAGE DeriveDataTypeable #-} 4 {-# LANGUAGE MultiParamTypeClasses #-} 5 {-# LANGUAGE FunctionalDependencies #-} 6 {-# LANGUAGE FlexibleInstances #-} 7 8 import Data.HList 9 import Data.HList.Label4 10 import Data.HList.TypeEqGeneric1 11 import Data.HList.TypeCastGeneric1 12 import Data.HList.MakeLabels 13 14 $(makeLabels ["labX", "labY"])

16 class Call a b c | a b -> c where 17 call :: a -> b -> c

19 infixl <*> 20 f <*> x = call f x 21 22 instance Call (a -> b) a b where 23 call f x = f x

Which gets us regular function application, sort of:

ghci> ((+) :: Int -> Int -> Int) <*> (2::Int) <*> (3::Int)

5

ghci> (+) <*> 2 <*> 3

<interactive>:1:0: No instance for (Call (a -> a -> a) t c) arising from a use of `<*>' at <interactive>:1:0-8 Possible fix: add an instance declaration for (Call (a -> a -> a) t c) In the first argument of `(<*>)', namely `(+) <*> 2' In the expression: (+) <*> 2 <*> 3 In the definition of `it': it = (+) <*> 2 <*> 3

It performs correctly but we utterly and completely lose type inference, because the typeclass needs things very specific before it is willing to do anything.

Note that if we were looking for just regular no dynamic binding Haskell we could have written the functional dependency

-- dyn-bind2.hs (cont) --

16 class Call a b c | a -> b c where 17 call :: a -> b -> c

And now we have type inference again,

ghci> (+) <*> 2 <*> 3

5

But that won't work if (+) shoul be able to be applied both to dynamic and to not-dynamic expressions.

I wrestled with a few other variations on this path -- I don't think it's the right way to go. As with most things in Haskell the most reliable way to deal with ambiguity is to make things more explicit. And here that means that every little node in the formuala tree should be decorated to show what its dynamic variables are.

-- dyn-bind3.hs --

1 {-# LANGUAGE EmptyDataDecls #-} 2 {-# LANGUAGE TemplateHaskell #-} 3 {-# LANGUAGE DeriveDataTypeable #-} 4 5 module DynBind where 6 7 import Data.HList hiding (apply,Apply) 8 import Data.HList.Label4 9 import Data.HList.TypeEqGeneric1 10 import Data.HList.TypeCastGeneric1 11 import Data.HList.MakeLabels 12 13 $(makeLabels ["labX", "labY"])

So we make it explicit that this is a dynamically bindable expression:

-- dyn-bind3.hs (cont) --

15 data DynExp a b = DynExp (a -> b)

A leaf is an expression with no dynamic variables:

-- dyn-bind3.hs (cont) --

17 leaf x = DynExp (\t -> x)

And then dynVar introduces one variable:

-- dyn-bind3.hs (cont) --

19 dynVar label = DynExp grab where 20 grab rec = rec # label

When we combine expressions by applying, we may as well just pass the whole record on to both branches: they'll just ignore the fields they don't need (exercise: why is this a bad idea?):

-- dyn-bind3.hs (cont) --

22 apply (DynExp f) (DynExp x) = DynExp g where 23 g rec = (f rec) (x rec) 24 25 infixl <*> 26 a <*> b = apply a b 27 28 with hl (DynExp f) = f hl

So let's test that...

-- dyn-bind3.hs (cont) --

30 expr = (leaf (+)) <*> (dynVar labX) <*> (dynVar labY) 31 bindings = 32 labX .=. 5 .*. 33 labY .=. 3 .*. 34 emptyRecord 35 36 main = do 37 print $ with bindings expr

8

So far it seems to work. But then problems develop...

-- dyn-bind3.hs (cont) --

30 expr = (leaf (+)) <*> (dynVar labX) <*> (dynVar labY) 31 b1 = 32 labX .=. 5 .*. 33 labY .=. 3 .*. 34 emptyRecord 35 b2 = 36 labY .=. 3 .*. 37 labX .=. 5 .*. 38 emptyRecord 39 40 main = do 41 print $ with b1 expr 42 print $ with b2 expr

dyn-bind3.hs:42:20: Couldn't match expected type `LabY' against inferred type `LabX' Expected type: DynExp (Record (HCons (LVPair (Proxy LabY) t) (HCons (LVPair (Proxy LabX) t1) HNil))) t2 Inferred type: DynExp (Record (HCons (LVPair (Proxy LabX) t3) (HCons (LVPair (Proxy LabY) t4) HNil))) a In the second argument of `with', namely `expr' In the second argument of `($)', namely `with b2 expr'

That's a tricky one. So does it matter what order you specify the labels in?

-- dyn-bind3.hs (cont) --

30 expr = (leaf (+)) <*> (dynVar labX) <*> (dynVar labY) 31 b1 = 32 labX .=. 5 .*. 33 labY .=. 3 .*. 34 emptyRecord 35 b2 = 36 labY .=. 3 .*. 37 labX .=. 5 .*. 38 emptyRecord 39 40 main = do 41 print $ with b2 expr

8

No... it just won't work if you do it 2 different ways. What is going on here? What if you don't specify them any ways?

-- dyn-bind3.hs (cont) --

30 expr = (leaf (+)) <*> (dynVar labX) <*> (dynVar labY) 31 32 main = do 33 print "hi"

dyn-bind3.hs:30:23: No instance for (HasField (Proxy LabX) t1 t) arising from a use of `dynVar' at dyn-bind3.hs:30:23-33 Possible fix: add an instance declaration for (HasField (Proxy LabX) t1 t) In the second argument of `(<*>)', namely `(dynVar labX)' In the first argument of `(<*>)', namely `(leaf (+)) <*> (dynVar labX)' In the expression: (leaf (+)) <*> (dynVar labX) <*> (dynVar labY) dyn-bind3.hs:30:41: No instance for (HasField (Proxy LabY) t1 t) arising from a use of `dynVar' at dyn-bind3.hs:30:41-51 Possible fix: add an instance declaration for (HasField (Proxy LabY) t1 t) In the second argument of `(<*>)', namely `(dynVar labY)' In the expression: (leaf (+)) <*> (dynVar labX) <*> (dynVar labY) In the definition of `expr': expr = (leaf (+)) <*> (dynVar labX) <*> (dynVar labY)

And now it becomes apparent... notice that this works:

-- dyn-bind3.hs (cont) --

30 expr rec = with rec $ (leaf (+)) <*> (dynVar labX) <*> (dynVar labY) 31 32 main = do 33 print "hi"

"hi"

In other words it would appear that we have hit the monomorphism restriction ;)

We could just lift the restriction, but I prefer another approach that makes types more explicit all around:

-- dyn-bind4.hs --

1 {-# LANGUAGE FlexibleContexts #-} 2 {-# LANGUAGE EmptyDataDecls #-} 3 {-# LANGUAGE TemplateHaskell #-} 4 {-# LANGUAGE DeriveDataTypeable #-} 5 6 import Data.HList hiding (apply,Apply) 7 import Data.HList.Label4 8 import Data.HList.TypeEqGeneric1 9 import Data.HList.TypeCastGeneric1 10 import Data.HList.MakeLabels 11 12 $(makeLabels ["labX", "labY"]) 13 14 data DynExp a b = DynExp (a -> b)

Leaves explicitly take no parameters:

-- dyn-bind4.hs (cont) --

16 leaf :: v -> DynExp (Record HNil) v 17 leaf x = DynExp (\t -> x)

dynVars explicitly take just one:

-- dyn-bind4.hs (cont) --

19 dynVar :: label -> DynExp (Record (HCons (LVPair label v) HNil)) v 20 dynVar label = DynExp grab where 21 grab (Record (HCons (LVPair v) HNil)) = v

And apply uses the functional dependency in HLeftUnion to give its result an explicit type as well (which is why we have to give an explicit type signature, which is why we have to specify all that other stuff):

-- dyn-bind4.hs (cont) --

23 apply (DynExp f) (DynExp x) = DynExp (splitApply f x) 24 25 splitApply :: ( 26 HLeftUnion (Record hl1) (Record hl2) (Record hlU), 27 H2ProjectByLabels ls1 hlU hl1' uu1, 28 H2ProjectByLabels ls2 hlU hl2' uu2, 29 HRearrange ls1 hl1' hl1, 30 HRearrange ls2 hl2' hl2, 31 HLabelSet ls1, 32 HLabelSet ls2, 33 HRLabelSet hl1', 34 HRLabelSet hl2', 35 RecordLabels hl1 ls1, 36 RecordLabels hl2 ls2 37 ) => 38 (Record hl1 -> a -> b) -> 39 (Record hl2 -> a) -> 40 Record hlU -> 41 b 42 splitApply f x hl = f (hMoldByType hl) (x (hMoldByType hl))

And my favorite are these infinitily recursive adaptor functions:

-- dyn-bind4.hs (cont) --

44 hProjectByType r1 = r2 where 45 r2 = hProjectByLabels r2Labels r1 46 r2Labels = recordLabels r2 47 48 hMoldByType r1 = r2 where 49 r2 = hRearrange r2Labels $ hProjectByLabels r2Labels r1 50 r2Labels = recordLabels r2 51 52 infixl <*> 53 a <*> b = apply a b 54 55 with hl (DynExp f) = f $ hMoldByType hl

And now everything works:

-- dyn-bind4.hs (cont) --

57 expr = (leaf (+)) <*> (dynVar labX) <*> (dynVar labY) 58 b1 = 59 labX .=. 5 .*. 60 labY .=. 3 .*. 61 emptyRecord 62 b2 = 63 labY .=. 3 .*. 64 labX .=. 5 .*. 65 emptyRecord 66 67 main = do 68 print $ with b1 expr 69 print $ with b2 expr

8 8

This is of course an extremely ugly way to write expressions, but since we're already using Template Haskell we may as well use Template Haskell.

-- Leafify.hs --

1 {-# LANGUAGE EmptyDataDecls #-} 2 {-# LANGUAGE TemplateHaskell #-} 3 {-# LANGUAGE DeriveDataTypeable #-} 4 5 module Leafify where 6 7 import DynBind 8 9 import Language.Haskell.TH 10 import Language.Haskell.TH.Quote 11 import Language.Haskell.Meta.Parse 12 import Data.List.Utils 13 14 var str = VarE (mkName str) 15 vLeaf = var "leaf" 16 vDynVar = var "dynVar" 17 vApply = var "apply" 18 vFlip = var "flip" 19 20 fromRight (Right x) = x 21 22 lf = QuasiQuoter { 23 quoteExp = doLf, 24 quotePat = doLfPat 25 } 26 27 -- Not used, but will warn if we don't provide it. 28 doLf :: String -> Q Exp 29 doLf str = do 30 return $ leafify' $ fromRight $ parseExp str 31 32 doLfPat :: String -> Q Pat 33 doLfPat str = do 34 return $ WildP 35 36 infixl <**> 37 a <**> b = AppE a b 38 39 -- This isn't really the best way to do things; we should really 40 -- do all of this in the Q monad. But this is flatter ;) 41 leafify' :: Exp -> Exp 42 leafify' (VarE v) = 43 let name = nameBase v in 44 if startswith "lab" name 45 then vDynVar <**> (VarE v) 46 else vLeaf <**> (VarE v) 47 leafify' (ConE x) = vLeaf <**> (ConE x) 48 leafify' (LitE x) = vLeaf <**> (LitE x) 49 leafify' (AppE f x) = vApply <**> (leafify' f) <**> (leafify' x) 50 leafify' (InfixE Nothing op Nothing) = 51 vLeaf <**> (InfixE Nothing op Nothing) 52 leafify' (InfixE (Just a) op Nothing) = expr where 53 expr = vApply <**> (vLeaf <**> f) <**> (leafify' a) 54 f = InfixE Nothing op Nothing 55 leafify' (InfixE Nothing op (Just b)) = expr where 56 expr = vApply <**> (vLeaf <**> f) <**> (leafify' b) 57 f = vFlip <**> (InfixE Nothing op Nothing) 58 leafify' (InfixE (Just a) op (Just b)) = expr where 59 expr = vApply <**> expr1 <**> (leafify' b) 60 expr1 = vApply <**> (vLeaf <**> f) <**> (leafify' a) 61 f = InfixE Nothing op Nothing 62 leafify' (LamE ps x) = LamE ps (leafify' x) 63 leafify' (TupE xs) = TupE (fmap leafify' xs) 64 leafify' (CondE x y z) = 65 CondE (leafify' x) (leafify' y) (leafify' z) 66 leafify' (ListE xs) = ListE (fmap leafify' xs) 67 68 -- Not Implemented 69 --leafify' (LetE d x) 70 --leafify' (CaseE x m) 71 --leafify' (DoE sts) 72 --leafify' (CompE sts) 73 --leafify' (ArithSeqE r) 74 --leafify' (SigE x t) 75 --leafify' (RecConE n fes) 76 --leafify' (RecUpdE x fes)

So that we can write

-- dyn-bind5.hs --

1 {-# LANGUAGE TemplateHaskell #-} 2 {-# LANGUAGE QuasiQuotes #-} 3 {-# LANGUAGE EmptyDataDecls #-} 4 {-# LANGUAGE DeriveDataTypeable #-} 5 6 import Leafify 7 import DynBind 8 9 import Data.HList hiding (apply,Apply) 10 import Data.HList.Label4 11 import Data.HList.TypeEqGeneric1 12 import Data.HList.TypeCastGeneric1 13 import Data.HList.MakeLabels 14 15 $(makeLabels ["labX", "labY", "labZ"]) 16 17 expr = [$lf| 18 (labX + labY) * labX - labZ/2 19 |] 20 21 bindings = 22 labX .=. 5 .*. 23 labY .=. 7 .*. 24 labZ .=. 10 .*. 25 emptyRecord 26 27 main = do 28 print $ with bindings expr

55.0

Man that is hacky... but it works.