begriffs

What Code Does vs What Code Means

December 26, 2015

John Wiegley contrasts his work on C compilers with another way of thinking about code, a way he learned through Haskell. He now distinguishes the meaning of a program from the various physical or electronic effects it causes. In this talk John elaborates on the distinction and concludes with a tour of the Free Monad, a way of encoding meaning as a first-class value.

Summary

  • Haskell is practical and all, but what in particular makes it beautiful?
  • Is there a “Zen of Haskell?”
  • John started out by writing C/C++ compilers for 20-25 years
    • During all that time he never thought about the things covered in this talk
    • The main thing he cared about is “What does this code do”
    • All that code “does” is affect electrical current flowing around
    • Recommended talk about abstraction: How to think about parallel programming — Not!
    • From virtual memory to the modern x86 assembly interpreter running in hardware, the history of programming shows us moving away from what code does (mechanically)
    • Instead let’s ask what code means.
  • When we talk about meaning we’re talking about semantics. What is the identity or reality of something apart from the way it is implemented or executed.
    • Example: 5 + 5 means 10. It is equivalent to and substitutable for 10. That’s referential transparency.
    • But what does the code 5+5 do? A compiler could reduce it to 10 at compile time (constant folding). It might mean loading 5 into a register and calling ADD with that register as both operands. Etc etc.
    • Choosing what code does is sensitive to various factors: time, memory, latency, throughput. All are questions about what code does.
    • It’s much simpler to ask what code means.
  • Haskell encourages — and sometimes enforces that — you think in terms of meaning rather than operation.
    • Imperative code is a sequence of states that must change through a state machine in order to produce the results you expect.
    • Functional code relates values in one set to values in another set through functions. We build up a functional program by composing lots of these functions.
    • Haskell also encourages the functional paradigm by being lazy. It defers decisions until later in the composition pipeline.
    • Purity is another value (some might say pain point) that enforces you to specify what a function means through its type.
    • Finally Haskell allows generic functions whose types are highly polymorphic
  • The IO monad is a DSL for expressing actions to be taken on my behalf by the runtime.
    • In this DSL “putStrLn” is a verb. That’s all the types say.
    • We could make this DSL ourselves, creating a type called say Action, which includes the action of printing. Then provide a way to evaluate the DSL.
    • The way that we interpret Action in the IO monad is similar to the way the runtime interprets expressions in the IO monad
  • We can abstract the DSL/evaluator pattern by using the free monad.
    • To do it we modify our Action type to become a functor called ActionF. Using it in the Free type creates our final Action type.
    • The Free constructors provide constructs such as what we used to call Done.
    • So why would you even want to use Free? This looks more complicated than what we built before. You use Free to take advantage of some nice helpers.
    • Free does the recursion for you for instance.
  • John didn’t appreciate this aspect of Haskell until he started using a language which has no runtime.
    • He’s been using Coq at work. It’s a restrictive language that does very little. There is no hello world program because there is no runtime.
    • Although the program is so restrictive it does allow us to build a model of anything. Coq’s termination checker prevents us from writing an infinitely recursive function.
    • But we can model an infinitely recursive function.
    • For instance even though the Fibonacci sequence is infinite, you can finitely specify how to build it.
    • Similarly in Coq you can talk and reason about any set of verbs you want as long as you don’t have a “do it” function which tries to evaluate them.
    • You can design this way in Haskell too
  • But why would you want to do things this way, with a grammar and evaluator?
    • It allows us to assign different meanings to the same program.
    • In the hello world example, one meaning would be to print the message to the screen. Another meaning would be to output a C program for the Haskell code.
    • We remove ourselves from what the code does.
    • The free monad lifts meaning into a first class value
  • Design abstractly
    • Encode meaning in the types
    • Execute ideas