Monday, May 13, 2013

Two Models of Computation: or, Why I'm Switching Trains


"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.

30 comments:

  1. 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

    ReplyDelete
  2. 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/

    ReplyDelete
  3. 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:foldMap
    Scala example: https://gist.github.com/seanparsons/1854485

    ReplyDelete
    Replies
    1. 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.

      Delete
  4. 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.

    ReplyDelete
  5. 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.

    ReplyDelete
  6. 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.

    ReplyDelete
    Replies
    1. 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.

      Delete
    2. 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.

      Delete
    3. 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.

      Delete
  7. 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".

    ReplyDelete
  8. Hi Jessie! You may find http://www.amazon.com/Computability-Turing-G%C3%B6del-Church-Beyond/dp/0262018993/ref=sr_1_1?ie=UTF8&qid=1393496630&sr=8-1&keywords=computability+church+turing+godel interesting, given this. Highly recommended.

    ReplyDelete
  9. 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.

    ReplyDelete
  10. The ego cannot think about being deceased. It has no way of it. But there is another aspect of interest that not only can understand it, but already knows about it. Klik4D

    ReplyDelete
  11. The ego cannot think about being deceased. It has no way of it. But there is another aspect of interest that not only can understand it, but. professional house cleaning

    ReplyDelete
  12. What other contractor can say they were involved in the design process of an all-electric service vehicle? Not many! Robichaud is a great example of a contractor on the cutting-edge of technology. pinterest

    ReplyDelete
  13. I’m really happy to find this site and did enjoy reading useful articles posted here. park office

    ReplyDelete
  14. Many manufacturers need to be more ideal and innovative about how they can use their display participation as a useful marketing. garnering interest for HCRC

    ReplyDelete
  15. There is a saying in the Zen personalized, “Birth and deficiency of way of lifestyle are the excellent problem.” That is where actual Buddhist perform out needs primary. best example

    ReplyDelete
  16. We are current because we are not dead; though our everyday way of lifestyle is loaded with the psychological jumble of ideas, emotions, and programs, at another level we have a low-level cautious program that is always looking out for existential risks. article about Christopher Cowdray

    ReplyDelete
  17. This can be amazing. Both of us watch this idea peace of mind when we are shocked. We’re fascinated by one of these pieces. Solitary appreciate your particular suggestion, and significance the effort inside this. Please keep enhancing. These are reall…More Info

    ReplyDelete
  18. This comment has been removed by the author.

    ReplyDelete
  19. The four singer/musicians—fiddler Fran Waggoner, basswoman Lizzie Hagstedt, multi-instrumentalist Bob Lutken and drummer Age Keep Area, who also has the most powerful. hop over to these guys

    ReplyDelete
  20. As almost everyone’s expenses knowledgeable, many organizations had to cut back on their display participation and the wide variety of individuals they sent to be existing at activities was considerably reduced. Consequently, some reveals stopped to are available or became much smaller versions of their halcyon periods. truth about cellulite joey atlas reviews

    ReplyDelete
  21. Robichaud also hired Bella Energy of Louisville, Colo., to install solar panels on Precision headquarters to help recharge the batteries for eight hours at night after technicians drive them 120 miles during the day. f4x quick start workout guide pdf

    ReplyDelete
  22. 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. check out 

    ReplyDelete
  23. I'm so glad I didn't do that, I'm still just beginning but I can see how valuable having more stitch options is going to be and I've already started using some of them. amateur slut

    ReplyDelete
  24. So, as a hobby economist, I actually followed this post and can see how silly it is to put a straight line on the graph. Detox Tea UK

    ReplyDelete
  25. I've already started using some of them. There wasnt a major growth but my boobs were a little more plump and full. Disappointed that it did not include a miter guide. I have even made adjustments so I can throw in a little ground flavored coffee while still using the grinder. old school new body book free download

    ReplyDelete
  26. As almost everyone’s costs experienced, many companies had to cut back on their display contribution and the variety of individuals they sent to be present at activities was significantly reduced. As a result, some reveals stopped to are available or became much smaller editions of their halcyon times. Lukas

    ReplyDelete