C9 Lectures: Dr. Ralf Lämmel - Advanced Functional Programming - The Expression Problem
- Posted: Aug 10, 2010 at 11:22 AM
- 51,980 Views
- 12 Comments
Download
How do I download the videos?
- To download, right click the file type you would like and pick “Save target as…” or “Save link as…”
Why should I download videos from Channel9?
- It's an easy way to save the videos you like locally.
- You can save the videos in order to watch them offline.
- If all you want is to hear the audio, you can download the MP3!
Which version should I choose?
- If you want to view the video on your PC, Xbox or Media Center, download the High Quality WMV file (this is the highest quality version we have available).
- If you'd like a lower bitrate version, to reduce the download time or cost, then choose the Medium Quality WMV file.
- If you have a Zune, WP7, iPhone, iPad, or iPod device, choose the low or medium MP4 file.
- If you just want to hear the audio of the video, choose the MP3 file.
Right click “Save as…”
- WMV (WMV Video)
- MP3 (Audio only)
- MP4 (iPod, Zune HD)
- Mid Quality WMV (Lo-band, Mobile)
"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]
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]
Comments Closed
Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation,
please create a new thread in our Forums,
or
Contact Us and let us know.
Follow the Discussion
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. Oliveira, Oxford 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.
Nice lecture.
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.
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.
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.
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.
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?
[ 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
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.
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.
Interested parties should read: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.5386
It's a short paper showing a true OO solution to the expression problem using virtual classes and is written in easily understandable terms.
Well, yeah, they might be a bit esoteric... but imho there's nothing wrong with that.
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!
Nice.
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 ?
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 ...
Awesome to have you here, Ralf. Thank you.
Indeed, tomorrow is Type Class Day. Thanks for another great lecture
C
Remove this comment
Remove this thread
close