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

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

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


Add Your 2 Cents