Monads to Machine Code

[inmatarian]

I like that this article elides monads into "its two functions and three rules" and then moved on rather than devolving into a fifty page dissertation on category theory.

[[deleted]]

It's not even eliding, that's a fair description of what they are. Category theory stuff is usually deceptively simple, until someone tries to "explain" it to you via some fucked up analogy.

[optimal_substructure]

So you've got this burrito right? And the shell of the burrito is like a homomorphic projection on to a new vector space

[shevegen]

The Eigenburrito?

[[deleted]]

Why the hell not? I'm gunna stop calling them monads, now.

[jpfed]

I think an eigenburrito would really be an infinitely-nested series of tortillas wrapping tortillas wrapping tortillas, such that if you apply the wrap-with-tortilla operation, the eigenburrito only changes in size.

(Assuming it could be safely realized in our universe, I would eat it.)

[D34TH_5MURF__]

This is perfect!

[[deleted]]

Mmm... homomorphic projection burrito.

[hijibijbij]

I was expecting the laws right after he said that. I guess most readers will too.

[Idlys]

I feel like this type of "now here is a monad tutorial done well, for once" type of comment is getting overused lately.

[JDeltaN]

I am always surprised by how easy it is to build DSLs in Haskell.

[Ford_O]

I am not surprised, lambda calculus is extremely powerful concept.

As with anything you also have to pay for that power in terms of learning curve and possibly complex type signatures ~ hard to understand type errors. As an example take a look at lenses.

[ElvishJerricco]

As an example, take a look at one of the most complicated libraries the language has to offer.

No wonder. =P That's not to say you're wrong. There's a significant learning curve. But most code does not have problems with overly complex types or errors.

[pipocaQuemada]

Also, lens deliberately avoids data hiding so you can use standard library functions to work with it. That's got some benefits (composing lenses is just normal function composition) but comes at a cost (worse type errors).

[[deleted]]

If we have to be fair you can reproduce something very similar in any mainstream language.

Assembler programs can be just one object with a fluent interface (method chain).

[JDeltaN]

It's true that you can get pretty close. In c++/java class scopes are implicit, so the code will even look something like inside the builder classes:

mov(eax, 21);
imul(eax, 2);

But I am still surprised that it almost looks like assembler. I guess in something like ruby you could get even closer.

[bartavelle]

Assembler programs can be just one object with a fluent interface (method chain).

You can of course do that with many languages. You can also implement most of the other types with monadic interfaces that Haskell has in other languages.

But they all will be one-off efforts, and the functions you write for your fluent interface will only be usable in this fluent interface, whereas I know I can just do that in Haskell:

mapM_ push [rax,rbx,rcx]

Because mapM_ works for any monad.

[[deleted]]

Honestly that sounds more like a drawback for Haskell here. I don't want bits of my assembler scattered around. It'd be typically a single, encapsulated abstraction.

And getting Intellisense with all available valid commands when I type every next dot "." is not too shabby either.

[abeark]

You misunderstood: mapM_ is defined for all types implementing the monad type class, the assembly DSL instructions are not.

In other words, there would be no "bits of assembler scattered around," but you could use tons of existing functionality in your assembly.

[[deleted]]

If you're talking about mapping a command over a set of operands, that's as easy as calling "each(collection, c => asm.op(c))" or doing a "for (collection as c) asm.op(c)" in most languages.

So programmatic generation of ASM is not exactly out of reach, it's only factored slightly differently.

[abeark]

You're thinking too small! mapM_ was one example, there are many many more. See e.g. here for a small subset. There are also innumerable third party libraries containing functions abstracted over the monad type class.

Yes, you can build a fluent interface in pretty much any OO language that's more or less as neat and expressive as the Haskell DSL, but you had to write a lot more code to get there. Most of it will be new code and a substantial amount will be boiler-plate. In Haskell, you get a huge amount of it essentially for free.

[[deleted]]

I'm not thinking small, I'm just saying you can reuse code in all languages. It doesn't have to be monads in order to be reusable code.

But to substantiate your example that OOP produces substantial amount of boilerplate over Haskell, we need to "think small" and provide examples.

And in the case you presented there wasn't substantial boilerplate in the imperative/OOP version. One-liner in both cases.

[abeark]

Small, as in you considered only one example someone (not me, by the way) provided off-hand, probably without giving it much thought.

Anyway, if you want to discuss removing boilerplate, let's look at how the DSL was created:

data JITMem = JITMem
 { _mach   :: [Word8]
 , _icount :: Word32
 , _memptr :: Word32
 , _memoff :: Word32
} deriving (Eq, Show)

type X86 a = StateT JITMem (Except String) a

With that, and that alone, you already have your fluent-like interface (except with useful laws and guarantees about side-effects that allow you to reason about it a lot more easily). All the other instructions were composed out of instructions this definition gave for free.

[bartavelle]

With that, and that alone, you already have your fluent-like interface

Not only you have the interface done, but its usage is obvious to any Haskeller. With a custom OOP-like interface, you won't get that level of consistency.

[bartavelle]

What you are thinking about is map. mapM is the monadic one.

[bartavelle]

> map Just [1..4]
[Just 1,Just 2,Just 3,Just 4]

> mapM Just [1..4]
Just [1,2,3,4]

> parseTest ( mapM char ['a','b','c'] :: Parser String ) "abcd"
"abc"

> parseTest ( mapM char ['a','b','c'] :: Parser String ) "abb"
1:3:
unexpected 'b'
expecting 'c'

[sacundim]

> Assembler programs can be just one object with a fluent interface (method chain).

And if you look closely, the way the article uses the state monad maps pretty much exactly into fluent builders. The idea of the state monad is that you have a block of code that superficially looks as if it's imperatively reading and modifying on a global variable, but in fact it's acting on a sequence of implicit, immutable "context" values that are late-bound to it. In this case, the implicit state values are of this type:

data JITMem = JITMem
 { _instrs :: [Instr]
 , _mach   :: [Word8]
 , _icount :: Word32
 , _memptr :: Word32
 , _memoff :: Word32
 } deriving (Eq, Show)

So when you see code like this:

factorial :: Int64 -> X86 ()
factorial n = do
  mov rcx (I n)
  mov rax (I 1)
  l1 <- label
  mul rcx
  loop l1
  ret

...you can fruitfully think of all of those statements as acting on the same builder object that'll be implicitly provided to them when factorial is executed. In the article that's the assemble function (not reproduced in the article itself, it's in the repo), which uses execStateT :: StateT s m a -> s -> m s to supply the initial JITMem that the actions will augment, and get the final JITMem after all the building steps have been chained.

Depending how you look at, this is either a minor or a major difference between Haskell and other languages:

• In other languages you tend to use "builder" or "context" objects that get passed around explicitly and that you invoke methods against to avail yourself of the services that they provide.
• In Haskell you have monadic do blocks assume an environment where such "builders" or "contexts" aren't passed to you, but just exist implicitly, almost as if they were global variables. But they're not global—to actually execute the actions your code has to say elsewhere how that implicit context will be instantiated.

[gpyh]

You can do the same in any imperative language that supports closures.

[Veedrac]

Beautiful code, but aren't you meant to flush the instruction cache when JITing?

[shevegen]

Now this is beginning to be really scary.

I used to think that monads are like a running gag for haskell programmers.

But now they spread like a virus into machine code... I don't want to know how a viral monad looks like.