“In cognitive science, we only use the lambda-calculus model of computation,” says Dr Philipp Koralus (Phd, Philosophy & Neuroscience, on his way to be a lecturer at Oxford). “We want to talk about what the system is doing, and abstract the how.”
Two models of computation: lambda calculus and the Turing machine. Teacher and student, Church and Turing.
Years later, engineering catches up and we start building computers.
John McCarthy favored an encoding of the lambda calculus. John Von Neumann built a Turing machine, with a separation of processing and data. “Von Neumann won because he was smarter,” says Barbara Liskov. Von Neumann’s particular type of intelligence was a huge working memory: he could hold a crapton of state in his head and manipulate it. Practical computation took the Turing machine route, stateful and imperative.
Von Neumann’s intelligence is not reproducible. We looked for ways that normal people could write and maintain programs in this architecture. We abstracted to assembly, then C, then object-orientation. All abstractions that let us partition the program into small enough bits that each bit can fit in our heads. We created some design principles to add enough formal structure that, with great effort, we could port some pieces of solutions to other problems.
Meanwhile, lambda calculus and functional languages fell to academia. Now they’re coming back. Now memory and processes are plentiful enough that we can afford to force a different computational model onto Von Neumann’s architecture. But why would we?
What’s the difference that makes the functional model of computation more useful to theoreticial cognitive scientists, who are modeling the reasoning method of the human mind? Philipp says it’s the semantics and the systematicity. “You can’t get arbitrary novelty and recombination without a formal system.”
But what about reuse in imperative languages? We do manage this. “You can get similarity in templates,” says Philipp. We can have design patterns, frameworks, and libraries. We can attend conferences and learn the tools people have crafted so we can recognize when our problem might mostly fit. Bur for arbitrary novelty, we have to get down to the language and code it ourselves. With our fingers.
I used to think that FP concepts like monads and monoids were like OO design patterns, only more abstract. Now I see that they are fundamentally different. If code can be represented in a formal symbolic notation, then any piece can be broken away and used differently in a different place. Like you can pull any subexpression out of a mathematical equation and think about it on its own.
It’s the difference between a neural network, which can learn to recognize faces, and a symbolic representation of faces that says, “This is a nose. This is an eye. This is the distance between the nose and eye.” The symbolic system gives us meaningful dimensions we can use independently and learn from. The neural network tells us “You” or “Not you.”
Then, composition. In OO our idea of composition is a has-a relationship. Yet, the owner object must be written to accommodate and pass messages through to its components. Contrast this with functional composition, which works like this:
find . -name ‘*.txt’ | xargs cat | grep ‘ERROR’ | cut -d ‘:’ -f 2 | sort | uniq -c
Each symbol here, “find”, “cat”, “grep”, “sort” has an independent meaning and is useful alone. Functional composition is a fits-together relationship. Neither part knows anything about the others. We piece them together to serve arbitrary purposes. Best of all, we don’t have to be Von Neumann to understand any given piece or conjunction.
Now that the field of software development recognizes the value of a more “tell us what it does” declarative and recombinable-without-template-matching computational model, some of us are struggling. We grew up learning to think like Von Neumann.
I used to say at interviews that my best skill was holding the whole system in my head. Now I recognize that this was a crappy way to reason. It doesn’t scale, and I can’t pass that understanding on to others as a whole. The wiser goal is to eliminate a need to load everything into one head. It’s going to be a tough transition from the relatively-informal structure I’m used to, but now I’m sure it’s worth it. I only hope I can take some of you with me.
I've always thought the traditional Turing machine way of thinking about computation was a huge historical mistake. And it's a pain for every student learning about computability, algorithms, etc. There was an interesting book on computability and complexity theory that by contrast was based on a programming languages approach by Neil Jones: http://www.diku.dk/~neil/Comp2book.html
Great post! John Backus referred to this as the Von Neumann Bottleneck in his 1978 Turing (irony!) Award lecture – http://www.cs.cmu.edu/~crary/819-f09/Backus78.pdf. I also wrote about it here: http://gorodinski.com/blog/2012/05/31/abstractions/
One other aspect that comes out of the functional composition relates to typeclasses (which I always think of as a \”there-is-a\” relationship). For example the foldMap method where if the context is Foldable and the type resulting from a given function is a Monoid we get a simple way to accumulate the mapped values.Haskell: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Foldable.html#v:foldMapScala example: https://gist.github.com/seanparsons/1854485
Can't say I completely agree with you. Given the choice of Von Neumann and Lambda, your choice might be best but humans don't really think either way which is why it's takes so much effort to learn to program in any standard programming paradigm. Humans learn and communicate much for readily by example and extrapolation so the preferable programming paradigm is Bayesian. Problems with this are that Turing type systems don't tend to adapt to Bayesian learning well so we need new hardware systems to take full advantage, but we also get access to non-computable implementation as well. The other big problem rests in HCI…I would rather not teach a computer to interact with my from scratch…think Helen Keller but much less intelligent…ugh…so maybe the interactive portion should be kick started with more traditional programming and the \”business logic\” should be Bayesian…think Star Trek holodeck..you have the standard LCARS and voice interfaces but you create a program through examples.
I love typeclasses because they define behaviour to go with the data, but you can know exactly which one will be called at compile-time.
Very good articulation of the idea! I do UI related programming with a lot of incoming events and asynchronous processes going on in unknown order. I dropped imperative and started using FRP. My experience resonates with your post. Now I don't have to try to keep everything in my head. It's a lot easier to reason about the project.
I liked the article but I have no idea how to take the code –400K LOC or so of Mason, perl, and SQL– that I have inherited and even begin to factor it into something functional.PS. you win the useless use of cat award.
Computation model is only one part of the FP style, and we need to think about the wider picture too. For me, the \”golden rule\” of modern FP is that it is all about data, so takes data seriously and provides excellent tools for working with data (better types, pattern matching, HOFs, …). The Lambda-calc model supports this well. So a good way to approach the refactoring is to be more aware of the various kinds of data being manipulated (and where you can get more precise about the data, eg Maybe/Option instead of dummy values), and get your code to reflect this understanding.
Nice article, I empathise with the idea that the Von Neuman style requires the programmer to \”hold a crapton of state in his head and manipulate it\”. It seems analogous with the Yo-yo problem categorization http://en.wikipedia.org/wiki/Yo-yo_problem \”where the programmer has to keep flipping between many different class definitions in order to follow the control flow of the program\”.
I think there should be some higher level of the useless use of cat award for using it with xargs ;).Of course, it doesn't change anything on very good rest of the blogpost.
Of course, I am stupid … this is not a candidate for the useless use of cat award … find produces stream of filenames, not their content.
If this is an academic way of saying \”Functional Programming is better than Imperative Programming\” then I'm onboard completely. If I was senior enough I'd refuse to hire anyone who writes code with mutable state.
This comment has been removed by the author.
I don`t switch trains!