9 ms·

Non-determinism: a sublanguage rather than a monad

97 points by panic 9y ago

worldsayshi 9y ago
Somewhat off topic: I'm very interested but as so often before with these kind of texts I'm at least somewhat stumped by the terminology. I can almost read this and I've done two and a half ish courses of Haskell. I've wasted so much energy feeling stupid when reading texts that I don't understand. But most of the time not understanding is not about "intelligence" but simply not having the right meaning assigned to the right amount of words. You're not stupid, you just don't have enough structured data yet. I wish I had that kind of insight and believed in it when I started out in university. Not that I'm completely convinced even now.
- mikekchar 9y ago
  I first learned Haskell so I could understand some of the papers I wanted to read that used Haskell for examples. Even when doing so, I realised that I would eventually have to learn ML, but haven't gotten around to doing it. I think it's a bit like literary researchers who have to learn ancient Greek or ancient Chinese to get to the bottom of things. It's funny that when I grew up I was always praised for being clever, so I never once doubted it. However, when I chose to learn Japanese and moved to Japan, suddenly many people assumed I was stupid -- because I could never quite understand what was going on. It's been an interesting experience. Which is it? Am I clever or stupid? Eventually I've come to the point: clever or stupid makes no difference. The only important things to ask are, "Do I understand" and "What do I need to do to understand". It's also made me realise that relying on my supposed cleverness has actually been a source of problems in my life that I had not thought about before (because I'm clever and clever is good, right?)
  - bojo 9y ago
    It's interesting to read this comment because I experienced nearly the same thing. Thought I was clever because everyone told me it was so, was admittedly quite arrogant about my technology skills, learned Japanese, moved to Japan, and could barely explain anything to my programming peers at the level of a five year old. It took several years of forced humbleness to erode the arrogance, stop thinking I was so clever, and simply apply myself to the task of learning the necessary Japanese to explain myself correctly. What I generally see with people new to learning Haskell (or similar) is that they approach it with their bag full of imperative language cleverness, and find the concepts and terminology hard to grasp because they refuse to become humble for a bit and examine it as a paradigm different from the one they know. To be fair I was no different until I finally started understanding it, but looking back, learning Haskell was similar to my Japan experience. It became much easier once I buckled down, learned the parts that didn't make sense, and most importantly began applying them.
  - equalunique 9y ago
    Your thoughts on cleverness reminded me of this quote from David Foster Wallace's Infinite Jest. Talent is sort of a dark gift ... talent is its own expectation: it is there from the start and either lived up to or lost.... Here is how to avoid thinking about any of this by practicing and playing until everything runs on autopilot and talent's unconscious exercise becomes a way to escape yourself, a long waking dream of pure play. The irony is that this makes you very good, and you start to become regarded as having a prodigious talent to live up to...
  - worldsayshi 9y ago
    My belief about intelligence is that it's mostly about your motivational properties. "What makes you tick?" "What makes you scared?" If math makes you tick and doesn't scare you will eventually learn a lot of it. It's not the whole story but I believe it accounts for a lot of it.
- agumonkey 9y ago
  That's my experience too. An amazing amount of "hard" things are just "ohhh that's what they meant".. basically a communication problem when reading others. What they see is not what you see and here lie most of the problems. For instance I failed linear algebra in college. Even though I loved CGI and 4 dimension matrices are bread and butter of 3D transforms. So I was eager to master it. I tried for 10 years reading a math text book and made no progress. I did lots of programming which helped me get a feel of what notation could be used to and also bought a stupid linalg book on amazon. Their wording and approach was different. All of a sudden everything became trivial. When I go back to the older book I understand what they mean now, but it hid so much meaning. I needed to get a culture of mathematical notation. Some kids might develop it naturally, or be able to grow with the help of teachers, I wasnt able at the time so I was left in the dark. Now most advanced abstract subjects feel different. It's gone from mental cramp to tiny things that MUST HAVE meaning, and I just have to change my perspective and I'll see too. And weirdly it applies to CS fields too. After that I could finally read fat compilers book full of succint notation. Combinatorics became reachable, same for fancy physics. The symbols carry almost no fear no. And in a way I'm still a bit sad that I didn't know that before, feels like a huge waste, for me but for other kids too. Lastly, going back to programming, haskell and the likes. After struggling to grok continuations and non determinism, I got a very very different picture of computing altogether. And I realize how crazy bad imperative first programming courses are. I didn't forget how impatients students can be and how efficient a simple statement sequence with visual output can be .. but gosh how far it sets you back in trying to approach different and vastly more useful ideas (say prolog).
  - alt2501 9y ago
    So the 'stupid linalg book' was the turning point? What am I missing here?
    - agumonkey 9y ago
      It was the final nail in the coffin. Linalg was a limit cas of something that was "hard", foreign and serious. The book itself was not all, that would be dishonest, I must say that reading FP for years also brought my mind up. It took me off the material side of things, no more thinking about setting memory with bits, and looking at abstractions instead (doesn't really matter how functions and types are done below, the semantics and algebra is the focus). That said the difference in mindset and perspective in that book (Gareth Williams Linalg 5th edition) told me that a topic can be approached in many different ways. What group A say about a domain may not speak to your brain, while group B perspective will fed your brain just the right way. What is hard is mostly "impedance mismatch", not a limit in the reader.
alphaalpha101 9y ago
Thank god. I've felt like we've been getting closer to breaching the peak of the hype curve for what I'd probably call 'monadic pure functional programming' i.e. Haskell, Scalaz, etc. It'll have its hardcore advocates forever, of course, but I think we might be finally getting to the point where people realise 'wait this sure is an absurd amount of complexity to represent some fairly simple functions, surely there must be a better way?'.
- danharaj 9y ago
  The majority of internet conversations about monads never get past the most shallow introduction. The most important feature of monads is that they can be composed via monad transformers. A la carte languages and algebraic effects are nice, but monad composition is more powerful. Also, as someone in the Haskell industry, I think you're wrong about trends. The last 5 or so years have been an accelerating trend of Haskell adoption. Of course it is still dwarfed by most other languages, but the number of multi-million dollar contracts I've seen executed in Haskell has been multiplying.
  - bojo 9y ago
    As a relatively tiny data point, I've introduced Haskell at a small telecom doing $350M/yr in revenue. This kind of environment screams "Enterprise", but as it turns out the vast majority of problems that need solved can be done quite gracefully with Haskell.
    - alphaalpha101 9y ago
      Yeah at the end of the day it's just another programming language, and you can really get things done in any programming language.
      - lmm 9y ago
        It's an incremental improvement on what's gone before, sure, but it does offer a bunch of genuinely useful facilities that a lot of programming languages just don't have. I'd never want to go back to a language that was missing HKT, missing libraries of generic operations on monads, missing libraries of generic operations on recursive datastructures via fixed points, or missing safe derivation of operations on structured data via typeclass derivation or similar.
graphememes 9y ago
Honestly I feel like Haskell and OCaml are severely over-engineered and overly focus on nuance far too much these concepts and ideas can be expressed in a more concise and legible manner in mathematical notation than the programming languages used as examples here.
- wyager 9y ago
  Haskell is an incredibly simple language with only a few core constructions. You have ADTs/pattern matching and lambda abstraction/application and that's basically it. Everything else in the standard language is (usually straightforward) syntactic sugar around those two concepts. This includes the vast majority of data structures, monads, etc. All the other things that people use exist as (individually) extremely simple extensions that you can learn in isolation in a few minutes. Haskell is possibly the least over-engineered language out there; it's almost as if laziness (no pun intended) was a guiding principle when building the language. Ocaml is more complicated, but I'd still consider it vasty simpler than C++ or Java (as long as you ignore ocaml's object layer).
  - Volt 9y ago
    If Haskell is so simple, why is GHC so big? I see your claim repeated often on HN, but I think it's disingenuous.
    - mej10 9y ago
      Because GHC isn't a compiler for just "Haskell -- the standardized language". It also implements a huge number of optional language extensions.
    - mikekchar 9y ago
      Hopefully other people more knowledgeable will answer, but there are a couple things that are pretty obvious off the top of my head: - lazy evaluation - type inference - ridiculous amounts of programmer tools (it *derives* type classes for you!!!) - lots of experimental ideas that are in the compiler but that people don't really use (it's a research tool after all). The language is simple from a conceptual standpoint. Not every thing in the compiler is there simply to support expression of an idea. Quite a lot of it is there to help the programmer. I think there is something to be said for the idea of writing a similar language which has a less monolithic set of tools (although, to be fair, I have not look at the architecture of GHC at all, so maybe it is really beautiful under the hood). The point is that I don't think that you can necessarily equate the simplicity of expression with the complexity of the tools.
panic 9y ago
If you like this article, the rest of Oleg's stuff on this style of embedded DSLs is also worth reading: http://okmij.org/ftp/tagless-final/index.html http://okmij.org/ftp/tagless-final/index.html One particularly cool (and surprising, to me at least) trick is defining interpreters that carry out composable optimization passes on a DSL without needing an intermediate representation: http://okmij.org/ftp/tagless-final/course/optimizations.html http://okmij.org/ftp/tagless-final/course/optimizations.html
lmm 9y ago
The trouble with this style is that your sublanguage program is no longer a value, so you can't reason about it or treat it as one. Instead you've created, effectively, an imperative method that accepts a bunch of callbacks that implements effects and runs those. I mean, the imperative programmers already knew they could write programs full of effects without monads. But there's a reason we regard that as bad style. As far as I can tell this piece is just a longwinded reinvention of imperative programming?
- panic 9y ago
  Yes, the program is written in terms of callbacks, just like monadic programs are written in terms of "return" and "bind" callbacks. This style isn't any more imperative than monadic programming. You could port this code to Haskell (using typeclasses instead of modules) and it'd work just as well.
  - lmm 9y ago
    Tagless final style programs are indeed written in terms of "return" and "bind" callbacks, but programs written with "vernacular monads" or free coproduct style aren't - they're plain old values and can be inspected as such. That's the style I prefer.

97 points by panic 9y ago

Somewhat off topic: I'm very interested but as so often before with these kind of texts I'm at least somewhat stumped by the terminology. I can almost read this and I've done two and a half ish courses of Haskell. I've wasted so much energy feeling stupid when reading texts that I don't understand. But most of the time not understanding is not about "intelligence" but simply not having the right meaning assigned to the right amount of words. You're not stupid, you just don't have enough structured data yet. I wish I had that kind of insight and believed in it when I started out in university. Not that I'm completely convinced even now.

mikekchar 9y ago
I first learned Haskell so I could understand some of the papers I wanted to read that used Haskell for examples. Even when doing so, I realised that I would eventually have to learn ML, but haven't gotten around to doing it. I think it's a bit like literary researchers who have to learn ancient Greek or ancient Chinese to get to the bottom of things. It's funny that when I grew up I was always praised for being clever, so I never once doubted it. However, when I chose to learn Japanese and moved to Japan, suddenly many people assumed I was stupid -- because I could never quite understand what was going on. It's been an interesting experience. Which is it? Am I clever or stupid? Eventually I've come to the point: clever or stupid makes no difference. The only important things to ask are, "Do I understand" and "What do I need to do to understand". It's also made me realise that relying on my supposed cleverness has actually been a source of problems in my life that I had not thought about before (because I'm clever and clever is good, right?)
- bojo 9y ago
  It's interesting to read this comment because I experienced nearly the same thing. Thought I was clever because everyone told me it was so, was admittedly quite arrogant about my technology skills, learned Japanese, moved to Japan, and could barely explain anything to my programming peers at the level of a five year old. It took several years of forced humbleness to erode the arrogance, stop thinking I was so clever, and simply apply myself to the task of learning the necessary Japanese to explain myself correctly. What I generally see with people new to learning Haskell (or similar) is that they approach it with their bag full of imperative language cleverness, and find the concepts and terminology hard to grasp because they refuse to become humble for a bit and examine it as a paradigm different from the one they know. To be fair I was no different until I finally started understanding it, but looking back, learning Haskell was similar to my Japan experience. It became much easier once I buckled down, learned the parts that didn't make sense, and most importantly began applying them.
- equalunique 9y ago
  Your thoughts on cleverness reminded me of this quote from David Foster Wallace's Infinite Jest. Talent is sort of a dark gift ... talent is its own expectation: it is there from the start and either lived up to or lost.... Here is how to avoid thinking about any of this by practicing and playing until everything runs on autopilot and talent's unconscious exercise becomes a way to escape yourself, a long waking dream of pure play. The irony is that this makes you very good, and you start to become regarded as having a prodigious talent to live up to...
- worldsayshi 9y ago
  My belief about intelligence is that it's mostly about your motivational properties. "What makes you tick?" "What makes you scared?" If math makes you tick and doesn't scare you will eventually learn a lot of it. It's not the whole story but I believe it accounts for a lot of it.
agumonkey 9y ago
That's my experience too. An amazing amount of "hard" things are just "ohhh that's what they meant".. basically a communication problem when reading others. What they see is not what you see and here lie most of the problems. For instance I failed linear algebra in college. Even though I loved CGI and 4 dimension matrices are bread and butter of 3D transforms. So I was eager to master it. I tried for 10 years reading a math text book and made no progress. I did lots of programming which helped me get a feel of what notation could be used to and also bought a stupid linalg book on amazon. Their wording and approach was different. All of a sudden everything became trivial. When I go back to the older book I understand what they mean now, but it hid so much meaning. I needed to get a culture of mathematical notation. Some kids might develop it naturally, or be able to grow with the help of teachers, I wasnt able at the time so I was left in the dark. Now most advanced abstract subjects feel different. It's gone from mental cramp to tiny things that MUST HAVE meaning, and I just have to change my perspective and I'll see too. And weirdly it applies to CS fields too. After that I could finally read fat compilers book full of succint notation. Combinatorics became reachable, same for fancy physics. The symbols carry almost no fear no. And in a way I'm still a bit sad that I didn't know that before, feels like a huge waste, for me but for other kids too. Lastly, going back to programming, haskell and the likes. After struggling to grok continuations and non determinism, I got a very very different picture of computing altogether. And I realize how crazy bad imperative first programming courses are. I didn't forget how impatients students can be and how efficient a simple statement sequence with visual output can be .. but gosh how far it sets you back in trying to approach different and vastly more useful ideas (say prolog).
- alt2501 9y ago
  So the 'stupid linalg book' was the turning point? What am I missing here?
  - agumonkey 9y ago
    It was the final nail in the coffin. Linalg was a limit cas of something that was "hard", foreign and serious. The book itself was not all, that would be dishonest, I must say that reading FP for years also brought my mind up. It took me off the material side of things, no more thinking about setting memory with bits, and looking at abstractions instead (doesn't really matter how functions and types are done below, the semantics and algebra is the focus). That said the difference in mindset and perspective in that book (Gareth Williams Linalg 5th edition) told me that a topic can be approached in many different ways. What group A say about a domain may not speak to your brain, while group B perspective will fed your brain just the right way. What is hard is mostly "impedance mismatch", not a limit in the reader.

alphaalpha101 9y ago

Thank god. I've felt like we've been getting closer to breaching the peak of the hype curve for what I'd probably call 'monadic pure functional programming' i.e. Haskell, Scalaz, etc. It'll have its hardcore advocates forever, of course, but I think we might be finally getting to the point where people realise 'wait this sure is an absurd amount of complexity to represent some fairly simple functions, surely there must be a better way?'.

danharaj 9y ago
The majority of internet conversations about monads never get past the most shallow introduction. The most important feature of monads is that they can be composed via monad transformers. A la carte languages and algebraic effects are nice, but monad composition is more powerful. Also, as someone in the Haskell industry, I think you're wrong about trends. The last 5 or so years have been an accelerating trend of Haskell adoption. Of course it is still dwarfed by most other languages, but the number of multi-million dollar contracts I've seen executed in Haskell has been multiplying.
- bojo 9y ago
  As a relatively tiny data point, I've introduced Haskell at a small telecom doing $350M/yr in revenue. This kind of environment screams "Enterprise", but as it turns out the vast majority of problems that need solved can be done quite gracefully with Haskell.
  - alphaalpha101 9y ago
    Yeah at the end of the day it's just another programming language, and you can really get things done in any programming language.
    - lmm 9y ago
      It's an incremental improvement on what's gone before, sure, but it does offer a bunch of genuinely useful facilities that a lot of programming languages just don't have. I'd never want to go back to a language that was missing HKT, missing libraries of generic operations on monads, missing libraries of generic operations on recursive datastructures via fixed points, or missing safe derivation of operations on structured data via typeclass derivation or similar.

graphememes 9y ago

Honestly I feel like Haskell and OCaml are severely over-engineered and overly focus on nuance far too much these concepts and ideas can be expressed in a more concise and legible manner in mathematical notation than the programming languages used as examples here.

wyager 9y ago
Haskell is an incredibly simple language with only a few core constructions. You have ADTs/pattern matching and lambda abstraction/application and that's basically it. Everything else in the standard language is (usually straightforward) syntactic sugar around those two concepts. This includes the vast majority of data structures, monads, etc. All the other things that people use exist as (individually) extremely simple extensions that you can learn in isolation in a few minutes. Haskell is possibly the least over-engineered language out there; it's almost as if laziness (no pun intended) was a guiding principle when building the language. Ocaml is more complicated, but I'd still consider it vasty simpler than C++ or Java (as long as you ignore ocaml's object layer).
- Volt 9y ago
  If Haskell is so simple, why is GHC so big? I see your claim repeated often on HN, but I think it's disingenuous.
  - mej10 9y ago
    Because GHC isn't a compiler for just "Haskell -- the standardized language". It also implements a huge number of optional language extensions.
  - mikekchar 9y ago
    Hopefully other people more knowledgeable will answer, but there are a couple things that are pretty obvious off the top of my head: - lazy evaluation - type inference - ridiculous amounts of programmer tools (it *derives* type classes for you!!!) - lots of experimental ideas that are in the compiler but that people don't really use (it's a research tool after all). The language is simple from a conceptual standpoint. Not every thing in the compiler is there simply to support expression of an idea. Quite a lot of it is there to help the programmer. I think there is something to be said for the idea of writing a similar language which has a less monolithic set of tools (although, to be fair, I have not look at the architecture of GHC at all, so maybe it is really beautiful under the hood). The point is that I don't think that you can necessarily equate the simplicity of expression with the complexity of the tools.

panic 9y ago

If you like this article, the rest of Oleg's stuff on this style of embedded DSLs is also worth reading: http://okmij.org/ftp/tagless-final/index.html http://okmij.org/ftp/tagless-final/index.html One particularly cool (and surprising, to me at least) trick is defining interpreters that carry out composable optimization passes on a DSL without needing an intermediate representation: http://okmij.org/ftp/tagless-final/course/optimizations.html http://okmij.org/ftp/tagless-final/course/optimizations.html

lmm 9y ago

The trouble with this style is that your sublanguage program is no longer a value, so you can't reason about it or treat it as one. Instead you've created, effectively, an imperative method that accepts a bunch of callbacks that implements effects and runs those. I mean, the imperative programmers already knew they could write programs full of effects without monads. But there's a reason we regard that as bad style. As far as I can tell this piece is just a longwinded reinvention of imperative programming?

panic 9y ago
Yes, the program is written in terms of callbacks, just like monadic programs are written in terms of "return" and "bind" callbacks. This style isn't any more imperative than monadic programming. You could port this code to Haskell (using typeclasses instead of modules) and it'd work just as well.
- lmm 9y ago
  Tagless final style programs are indeed written in terms of "return" and "bind" callbacks, but programs written with "vernacular monads" or free coproduct style aren't - they're plain old values and can be inspected as such. That's the style I prefer.