7 ms·

From Monads to Machine Code

181 points by mrkgnao 10y ago

mrkgnao 10y ago
(With a short detour through writing a JIT in LLVM, of course, but I didn't want to edit the title. Sadly, I accidentally added the "from" at the beginning.)
tomcam 10y ago
This is a gentle introduction to Haskell and also a brilliant tutorial on x86 assembly language – bonuses for anyone interested in compiler implementation. Exceptionally well written and clearly illustrated.
gue5t 10y ago
pflags = protRead <> protWrite mflags = mapAnon .|. mapPrivate What's the difference between these two operators?
- evincarofautumn 10y ago
  There’s no difference in this case—looks like an oversight. “<>” is the Monoid “append” operator (e.g., concat lists, union sets, compose functions). If you look in JIT.hs[1], you’ll see that there’s an instance of Monoid that just calls “.|.” (bitwise OR): instance Monoid ProtOption where mempty = protNone mappend (ProtOption a) (ProtOption b) = ProtOption (a .|. b) [1]: https://github.com/sdiehl/tinyjit/blob/master/src/JIT.hs https://github.com/sdiehl/tinyjit/blob/master/src/JIT.hs
  - mrkgnao 10y ago
    There is no canonical monoidal operation on booleans (just as the case is in any arbitrary ring), so I'd guess using the bitwise operators explicitly is good for disambiguation.
    - evincarofautumn 10y ago
      Yes and no—in practice in Haskell we tend to choose the most convenient instance and wrap things in newtypes to get at other instances. Writing code using generic operations (Monoid, Functor, Foldable) makes it easier to refactor datatypes later—coding to the interface and not the implementation, and all that. The bitwise OR operation makes sense for ProtOption because it’s basically a set.
      - mrkgnao 10y ago
        That's true, for bitflag-like things OR does make sense.
evincarofautumn 10y ago
Man, I always love how cleanly EDSLs come together in Haskell. If you’re a fan of “language-oriented programming” (e.g., in Lisps and Forths) but you want static types, Haskell is for you.
- shakna 10y ago
  My problem with Haskell, coming from the ease of Lisp, is that so much of the syntax is symbolic! I know mathematicians might love it, but forgetting a symbol can mean I don't understand an entire block of code. Whereas it could have been made so much clearer with one word.
  - evincarofautumn 10y ago
    Well, there’s really only a handful of operators in typical code that don’t appear in other languages, and these are bound to the standard abstractions (functions, Functor, Applicative, Alternative, Monad, Monoid) that are used all the time. Once you learn those it’s pretty much smooth sailing, but yeah, it was pretty daunting to me at first, and even now as an experienced Haskeller I don’t care for packages like Lens that can turn into operator soup. However, I do think the built-in symbolic syntax (::, ->, =>, =, |) is all pretty clear. And thankfully there’s Hoogle to find the meaning of any operator you don’t understand, or even to find a function that you think should exist of a certain type. So I dunno, we get by well enough. And you could actually write your code largely without operators if you wanted to, either because there’s a standard name already, or because it’s easy to define an alias.
  - runeks 10y ago
    Could you give an example of this? I don't quite follow what you mean by "symbolic syntax". Do you mean infix functions like >>= and <$>?
    - shakna 10y ago
      Syntax where symbols are used in leiu of words. For example, I have no clue what >>= and <$> mean from a glance. I have to look it up to get Monad and Functor. Why not use the word?
briansteffens 10y ago
It's so cool how similar the contents of the arith function are to actual x86 code. The relative offsets were also handled really cleanly.
lacampbell 10y ago
I got lost at the monads bit. Where's the best place to learn about them? I did basic Abstract Algebra in university, and I understand how to use the Maybe/Option/Optional monad.
- empath75 10y ago
  https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ https://bartoszmilewski.com/2014/10/28/category-theory-for-p...
  - danidiaz 10y ago
    Those articles (and the videos https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_ https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbm...) are great but one doesn't need to learn category theory to understand monads in Haskell. The Haskell Wikibook is an underrated resource: https://en.wikibooks.org/wiki/Haskell/Understanding_monads https://en.wikibooks.org/wiki/Haskell/Understanding_monads
    - lacampbell 10y ago
      Hmm, this stuff looks familiar, I tried to learn it once upon a time. The operators make sense to me except for "return" which just seems like a hack, or excessive syntax sugar. If you already have type constructors, why the magic "return" function that needs to sniff the surrounding scope to see what kind of monads you are actually dealing with?
      - gmartres 10y ago
        The whole point of monads (and most other typeclasses) is that they're an abstraction. If you use a type constructor then you cannot generalize your function to work with any kind of monad, see for example the definition of `mapM` in https://hackage.haskell.org/package/base-4.9.1.0/docs/src/GHC.Base.html https://hackage.haskell.org/package/base-4.9.1.0/docs/src/GH... which uses `return`
      - 10y ago

181 points by mrkgnao 10y ago

(With a short detour through writing a JIT in LLVM, of course, but I didn't want to edit the title. Sadly, I accidentally added the "from" at the beginning.)

tomcam 10y ago

This is a gentle introduction to Haskell and also a brilliant tutorial on x86 assembly language – bonuses for anyone interested in compiler implementation. Exceptionally well written and clearly illustrated.

gue5t 10y ago

pflags = protRead <> protWrite mflags = mapAnon .|. mapPrivate What's the difference between these two operators?

evincarofautumn 10y ago
There’s no difference in this case—looks like an oversight. “<>” is the Monoid “append” operator (e.g., concat lists, union sets, compose functions). If you look in JIT.hs[1], you’ll see that there’s an instance of Monoid that just calls “.|.” (bitwise OR): instance Monoid ProtOption where mempty = protNone mappend (ProtOption a) (ProtOption b) = ProtOption (a .|. b) [1]: https://github.com/sdiehl/tinyjit/blob/master/src/JIT.hs https://github.com/sdiehl/tinyjit/blob/master/src/JIT.hs
- mrkgnao 10y ago
  There is no canonical monoidal operation on booleans (just as the case is in any arbitrary ring), so I'd guess using the bitwise operators explicitly is good for disambiguation.
  - evincarofautumn 10y ago
    Yes and no—in practice in Haskell we tend to choose the most convenient instance and wrap things in newtypes to get at other instances. Writing code using generic operations (Monoid, Functor, Foldable) makes it easier to refactor datatypes later—coding to the interface and not the implementation, and all that. The bitwise OR operation makes sense for ProtOption because it’s basically a set.
    - mrkgnao 10y ago
      That's true, for bitflag-like things OR does make sense.

evincarofautumn 10y ago

Man, I always love how cleanly EDSLs come together in Haskell. If you’re a fan of “language-oriented programming” (e.g., in Lisps and Forths) but you want static types, Haskell is for you.

shakna 10y ago
My problem with Haskell, coming from the ease of Lisp, is that so much of the syntax is symbolic! I know mathematicians might love it, but forgetting a symbol can mean I don't understand an entire block of code. Whereas it could have been made so much clearer with one word.
- evincarofautumn 10y ago
  Well, there’s really only a handful of operators in typical code that don’t appear in other languages, and these are bound to the standard abstractions (functions, Functor, Applicative, Alternative, Monad, Monoid) that are used all the time. Once you learn those it’s pretty much smooth sailing, but yeah, it was pretty daunting to me at first, and even now as an experienced Haskeller I don’t care for packages like Lens that can turn into operator soup. However, I do think the built-in symbolic syntax (::, ->, =>, =, |) is all pretty clear. And thankfully there’s Hoogle to find the meaning of any operator you don’t understand, or even to find a function that you think should exist of a certain type. So I dunno, we get by well enough. And you could actually write your code largely without operators if you wanted to, either because there’s a standard name already, or because it’s easy to define an alias.
- runeks 10y ago
  Could you give an example of this? I don't quite follow what you mean by "symbolic syntax". Do you mean infix functions like >>= and <$>?
  - shakna 10y ago
    Syntax where symbols are used in leiu of words. For example, I have no clue what >>= and <$> mean from a glance. I have to look it up to get Monad and Functor. Why not use the word?

briansteffens 10y ago

It's so cool how similar the contents of the arith function are to actual x86 code. The relative offsets were also handled really cleanly.

lacampbell 10y ago

I got lost at the monads bit. Where's the best place to learn about them? I did basic Abstract Algebra in university, and I understand how to use the Maybe/Option/Optional monad.

empath75 10y ago
https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ https://bartoszmilewski.com/2014/10/28/category-theory-for-p...
- danidiaz 10y ago
  Those articles (and the videos https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_ https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbm...) are great but one doesn't need to learn category theory to understand monads in Haskell. The Haskell Wikibook is an underrated resource: https://en.wikibooks.org/wiki/Haskell/Understanding_monads https://en.wikibooks.org/wiki/Haskell/Understanding_monads
  - lacampbell 10y ago
    Hmm, this stuff looks familiar, I tried to learn it once upon a time. The operators make sense to me except for "return" which just seems like a hack, or excessive syntax sugar. If you already have type constructors, why the magic "return" function that needs to sniff the surrounding scope to see what kind of monads you are actually dealing with?
    - gmartres 10y ago
      The whole point of monads (and most other typeclasses) is that they're an abstraction. If you use a type constructor then you cannot generalize your function to work with any kind of monad, see for example the definition of `mapM` in https://hackage.haskell.org/package/base-4.9.1.0/docs/src/GHC.Base.html https://hackage.haskell.org/package/base-4.9.1.0/docs/src/GH... which uses `return`
    - 10y ago