C9 Lectures: Dr. Ralf Lämmel - Advanced Functional Programming - The Expression Problem

Download this episode

Download Video


"The Expression Problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts)." - Philip Wadler

Welcome to another series of C9 Lectures covering functional programming. For this series, Dr. Ralf Lämmel has generously taken the time to produce videos for Channel 9 from his office at the University of Koblenz-Landau (Germany), where he is a professor of computer science. The idea here is to take the next step from Erik Meijer's fantastic introductory series on functional programming. Accordingly, Ralf's series will dive into more advanced areas of functional programming, again focusing on the Haskell language (the functional concepts here span beyond any one functional language, however).

To begin, Dr. Lämmel teaches us about the Expression Problem. Now put on your thinking caps, make yourself comfortable, and enjoy this installment of functional programming lectures on Channel 9. Huge thanks to Dr. Lämmel, both for doing this series for Channel 9 and for filming and producing it all by himself! Finally, thanks to Erik Meijer for suggesting this series and putting me in touch with Ralf.

See Dr. Lämmel's blog post about the new lecture series here: http://professor-fish.blogspot.com/2010/08/lecture-series-on-advanced-functional.html

[Homework assignment is on slide 26 - Get the slides]



Available formats for this video:

Actual format may change based on video formats available and browser capability.

    The Discussion

    • User profile image

      The Expression Problem. That reminds me of this paper


      Modular Visitor Components: A Practical Solution to the Expression Families Problem
      by Bruno C. d. S. OliveiraOxford University Computing Laboratory
      ECOOP 2009, Genova, Italy, July 2009.


      I guess the expression of the Expression Problem solution is simpler in Haskell!?


      I like the way you introduce all non-solutions first. Quite educational.

    • User profile image

      Nice lecture. Smiley


      For those who're interested, Ralf Lämmel has some older great lectures online here. Of these, I enjoyed the following lectures:

       They are great for exercising your brain. Smiley

    • User profile image

      In Javascript you could just add new functions to the object's prototypes. Objective-C has a similar ability to extend classes at runtime because like Javascript it uses dynamic dispatch.


      In C# you could simulate dynamic dispatch by having your visitor pattern function retrieve a delegate from a map that's keyed on type and operation.


      I'd like to know if this Expression Problem shows up in practice or whether it's just a theoretical curiosity. The only situations I can think of where you want to extend something you don't have the source to are all data extensions - e.g. adding controls to a GUI toolkit.

    • User profile image

      Thanks for the reference. This is one of these really uber-smart papers on the expression problem & friends. There is no shortage of such papers. Smiley I remember being a guest at North-Eastern in Boston a bit more than 3 years back where I also ran into Matthias Felleisen (a (F)PL highness) and we came to talk about the xproblem, which is when he made a funny remark along the lines (modulo my recollection): "every PL researcher has written at least one paper on the xproblem".


      And yes, Haskell's type-class-based solution is pretty simple. Well, you can judge for yourself if you see the next lecture.


    • User profile image

      I am flattered by your recommendation.

      Frankly, I hope I can do better than in those 3 lectures that you recommend.

      That is, in this new series, I want to specifically reach out to niners.

      In contrast, some parts of these recommended lectures are a bit esoteric in retrospect, no?


    • User profile image

      [ Sigh, meant to reply to rhm. ]


      Yes, I have totally avoided the entire wormhole/theme of runtime adaptation. Such expressiveness can be surely used in wonderful ways. Dynamic typing is Ok Smiley With Robert Hirschfeld, I have used Smalltalk (Squeak) to solve the expression problem in related and crazy ways: http://homepages.cwi.nl/~ralf/rd/ (Readers of this reply with static typomania must not follow this link.) 


      As you notice, my formulation of the xproblem (based on Wadler's original formulation) commits to static type safety (and separate compilation). Hence, your options (i.e., Javascript, maps in C#, dynamic dispatch in Objective C and elsewhere) would be wonderful candidates to add to the list of non-solutions that are already in the slide deck.


      I am really intrigued by your question whether the "Expression Problem shows up in practice or whether it's just a theoretical curiosity".


      You seem to suggest one scenario: adding controls to a GUI toolkit. I believe that this is a non-challenge though because any additional control should be like a *data* extension and that's easy with OO.  Please let me know whether you had an operation extension in mind (and which it is) in this context.


      Anyway, there is no easy answer to your question. This would be a very interesting question for a panel. Let me throw in some ideas here. a) The xproblem doesn't really show up in practice because there is no easy solution to it, and hence people regularly and naturally compromise on either separate compilation or static type safety. b) I feel somewhat hesitant to even name any practical scenario in support of the need for operation extensions in OO software because *any* scenario will do where you start from n virtual methods and you go to n+m virtual methods, which seems to be a very reasonable thing to do in OO programming. Smiley c) Like with any form of anticipated adaptation (i.e., with the xproblem anticipating additional data variants and additional operations), practice often requires software evolution such that any effort of anticipation turns out to be insufficient. For instance, in the case of the expression language, we may need to refactor expression forms prior to an addition of a new expression form, which immediately takes us out of the xproblem's anticipation scheme for separate compilation and static type safety. d) The kind of the xproblem's discussion of separate compilation and static type safety is a precursor to very practical problems in software engineering---such as efficient test-harness execution following local changes and impact analysis; (non-) solutions to the xproblem do not co-solve those practical problems, but they help in mining those latter solutions. e) Your question seems to be focusing on the OO paradigm's situation. In the FP paradigm, it is a very practical limitation that we cannot do data extensions easily; we 

      certainly do operation extensions *all* the time.


      To summarize, given current practice and current language support, the xproblem is more of a theoretical curiosity, but it is interesting in the same sense, as we like to ponder about the Halting problem while we have practical means of gaining confidence in the termination of our algorithms. 

    • User profile image

      Interested parties should read: http://citeseerx.ist.psu.edu/viewdoc/summary?doi= 

      It's a short paper showing a true OO solution to the expression problem using virtual classes and is written in easily understandable terms.

    • User profile image

      Well, yeah, they might be a bit esoteric... but imho there's nothing wrong with that. Smiley

    • User profile image

      The expression problem is my touchstone for thinking about a lot of design problems, and the tradeoffs and tensions involved. OO vs. FP, Rich vs. Reach, Code vs. Data ... I find it comes up over and over again in different forms. So I think every programmer should be familiar with the basic concept, thank you for posting this!

    • User profile image



      Would be even better if

      - it would use F#

      - F# would give us Type-Classes


      So PLEASE give us Type-Classes for the next release of F# - I guess it would have to be implemented into the CLR but after all we got generics, extension-methods etc. only for LINQ - so why not give us some nice functional sugar ? Wink

    • User profile image

      I am in no way informed or authorized to speak about F#/CLR/C# plans with regard to type class-like stuff.


      But let me bring up some thoughts anyway.


      a) One would probably want to get type classes in .NET as a generalization of interfaces---as opposed to adding type classes as a whole new language concept.

      b) If so, the retroactive property of type classes would deeply affect the runtime semantics of method calls with interface types. That is, implementations would need to be found either in the regular method table or in the pool of the retroactive interface implementation. So the CLR shall be affected.

      c) b) implies a whole wormhole of issues with backwards bytecode compatibility and performance penalties (distributed fat) as well as more complicated type-checking scheme subject to runtime/loadtime tests. As Stefan Wehr's thesis seems to show, these problems can be probably solved, but it would be quite a brain surgery to get it to production quality.

      d) There is also still design issues that are not totally clear. Let me just mention the example that not even in Haskell country we are totally decided on how to deal with type functions or type families or say multi-parameter type classes. Also, the transcription of type classes to OO brings up additional / new feature interactions that need to be worked out, e.g., the different kinds of polymorphism.


      I think my type-class lecture is going live tomorrow.

      Let's chat some more ... Smiley

    • User profile image

      Awesome to have you here, Ralf. Thank you.


      Indeed, tomorrow is Type Class Day. Thanks for another great lecture Smiley


    Comments closed

    Comments have been closed since this content was published more than 30 days ago, but if you'd like to send us feedback you can Contact Us.