Lambda the Ultimate

Think of this as an experience paper. Nothing is very novel about the approach or even the domains (e.g., LibSH allows you to write shaders in C++ using a similar "retained mode" approach). My goal for this paper is to document and publicize the technique and show that it can be used to improve libraries that people use (WPF) in the languages that they use (C#) vs. say a new UI system in a language that doesn't get as wide use (e.g., FrTime/Scheme, though I wish this wasn't the case!). Put it this way: by working with the technologies that developers use, we can possibly have more impact; e.g., FRP is very academic/obscure right now, but databinding isn't...

Responses to your points:

(a) Actually, the embedded DSL approach as supported by LINQ doesn't require very much tool support, you just have to write an interpreter (e.g., you get Intellisense for free). The dedicated language approach on the other hand requires you to build tools, and these tools are expensive (look at how late JavaFX is). The "auto-generate" tools from specifications is still a pipe dream.

(b) Lightweight DSLs aren't restricted to no mutation. Its just the languages we've explored don't support mutation, so there is no need to look into this yet. We probably need to consider mutation later in future languages, especially as pixel shaders get more complicated.

(c) See LibSH as a language that follows a similar approach. I was pleasantly surprised to find this language, actually. The graphics community is really not very good at promoting their DSLs to the language community :)

(d) I wasn't aware of John Peterson's C++ FRP work. We don't rely on much lifting because either its not possible (pixel shading) or not desirable (ability to support inverses in the databinding DSL).

(e) Hmm, it seems that our use of inverse functions so that we can put expressions on either side of the bind is actually a novel contribution to FRP. E.g., we can write (left + width).bind = 10, which is something you can't write in another FRP language yet, and is actually very useful when right is defined as "left + width".

(f) An embedded DSL that was implemented by re-interpreting the language wouldn't be lightweight.

Thanks for the feedback!

Gotcha, thanks. I totally misread at least 2 parts of it in that first pass. I like winter as I actually have time to go back and more deeply read things :)

- Leo

In C#, extension methods are really limited. In the rewrite I'm working on now, I'm actually moving away from extension methods into more proxy-style objects, which allows me to expose more functionality as properties and play tricks with the setters. Also, in this rewrite, partial classes are used to separate out the WPF databinding and pixel shader layers from the generic language layer. So you could totally reuse the language layer without the databinding layer. I've also added a new layer for UI physics.

The biggest part of the rewrite is that I've unified all the DSLs into one, and decided to dynamically check to make sure that the DSLs don't overlap in bad ways. This means I can write a bunch of math/geometric functions to support all DSLs once, and also makes the library easier to reuse. The math/geometric functions are portable across all the DSLs and any future DSL, which is a big win.

Never been a fan of partial classes, but I can see how they make up for some abstraction limitations in .NET. By the way Signal is a partial class, but I don't see another partial implementation in Bling -- is it intended to be application-specific? I assume then there's no straightforward way to parameterize the language layer without source compilation.

Extension methods are limited, but I do like the way they uniformly handle all language values, even null. So you can propagate null or non-null values like a Maybe monad, without disrupting the structure of client code.

I don't yet have a feel for the limitations of the current Bling structure, but I look forward to seeing your changes. If you have a preliminary design doc I'd love to see it some time! What sorts of dynamic checks do you need?

For UI physics, I take it you mean various notions of rigidity of elements, elasticity, attraction, etc. Sounds interesting.

C# technically doesn't support separate compilation on the source level anyways; it seems to rely on a really fast (TM) compiler instead. There is separate compilation across assembly boundaries, so I'm limiting myself here. Eventually, I want to redo Bling in Scala the right way with mixins and virtual types (but Scala.NET isn't there yet). For now, partial classes are the way to go.

No docs right now, I'm just hacking this out. I'll eventually update the ECOOP submission with the new design regardless of whether it is accepted or not. I'm also working on a UI physics paper, basically, use physics-based integration to solve physical constraints, which takes FRP to the next level, I think.

Let me know if you upload the independent language layer some day! I'd love to check out the source without all the databinding layer-specific stuff.

Definitely, I'll upload it when its ready. I've basically finished databinding and shaders, and I'm getting physics done now.

I'm wondering if the combined language would be best marketed as a language like Processing? A C#-based DSL for designers and artists. Hmm...

Uploaded now on codeplex (codeplex.com/bling). Check out Bling directory of the source code repository (I'm using SVN, seems to be the most painless way to deal with codeplex). Still an early release, I'm going to add documentation, more examples, in the next week or so.

Great, thanks! Look forward to having some time to dig in. I've already skimmed some of it and can see the significant structural changes you mentioned. Hope I can figure out what they mean. :-)

New version of Bling is up on the codeplex site. Lots of goodness. I'm pretty sure the paper has been rejected. I guess the focus should have been on the language vs. the concept of doing FRP in plain old C#.

I wonder about a choice you made

Additionally, a bling can provide properties that do not exist in WPF directly but are computed as expressions over other properties. For example, a LeftTop point property combines canvas's left and top double properties, while a RightBottom point property is simply LeftTop + Size, and a CenterPosition point property is simly LeftTop + Size / 2. Although such properties are derived from expressions, they can still be assigned, with the assignment being translated into an assignment of the expression's left-most term.

Concerning the last point, that means that changing CenterPosition value changes LeftTop value doesn't it?

How well does this choice of the leftmost term work in practice? Is it in use in other constraint-based systems?

Correct, assigning to center position changes left top. This makes sense, as you are changing the position of the element not the size.

The leftmost term works really well in practice. Take Bezier curves, the value for a point p can be determined by an equation over the control points; e.g., for quadratic:

B(t) = (1-t)^2*P0 + 2*(1-t)*t*P1 + t^2*P2

We only care about assigning to the control points (P0, P1, P2), so we first rewrite the equation so the control points appear to the left of each term:

B(t) = P0*(1-t)^2 + P1*2*(1-t)*t + P2*t^2

Now, if I say B(0.5).Bind = (120,300), Bling will automatically assign P0 to a value that makes this true. Now, we can generalize B(t) so that we can control what term appears first:

B(K,t) = 
  var terms = List(P0*(1-t)^2, P1*2*(1-t)*t, P2*t^2);
  var answer = 0;
  for (int i = 0 until 3) 
    answer += terms((i + K) % 3);
  answer;

Now, I can define a Bezier curve by specifying where I want points on the line, e.g., B(0,0) = (0,0), B(1,.5) = (100,100), B(2,1.0) = (200, 0) will define a curve that goes through all these points. This is a much more user friendly way of defining Bezier curves!

Other constraints systems don't do this. If you look at Kaleidoscope, which I think was the most serious effort on OO imperative constraint programming, they use explicit "hold" expressions. The problem then is that you have to write your Bezier curve equations multiple times depending on what control point you want to assign.

Now is leftmost assignment a hack? Ya, kind of, but I think the convention is easy to understand. And the focus of this work is on usability, not formality.

Thank you for the detailed answer, looks good. I will rethink the constraint system I was looking into to see if that idea fits.

WPF is close to JavaFX in many regards, and Bling completes the similarity by providing similar syntax for databinding and animation. The only thing that is missing is JavaFX's object-model syntax, which C# already mostly has through its field initialization syntax. Basically, WPF + C# + another library (Bling) gives you 99% of JavaFX's features without having to invest in yet another language.

I guess the key question is; What is the 1% you don't have access to that differentiates JavaFX?

It is the custom scenarios that make a tool really useful. A claw hammer works 99% of the time, especially if you are a carpenter. But if you are metal working, a ball pean hammer comes in real handy.

My use of percents is just to say that they are really close in capabilities, but of course not equivalent. The pixel shader and UI physics DSLs in Bling are things that don't exist in JavaFX, and might not ever exist since they designed specific features into the language. On the other hand, JavaFX has a nice in-language markup model that they can do because they have their own parser, while Bling is stuck with whatever C# can do (maybe VB has better options?). And of course, since Bling is a lightweight language DSL, there are conversion/type inference issues that we have to deal with sometimes (e.g., convert double to DoubleBl to call a method on it!), where such issues can be dealt with in JavaFX through compiler hacking.

That is over-engineering.

I have done some pretty funny stuff with WPF (just ask Sean, he's seen my disgusting WPF meta-programming).

The key with WPF is to stick with the Silverlight subset.

btw, naasking hit the nail on the head... WPF should've made a generic complex event processing framework. The thing I want to tell controls the most is "Watch for this virtual event according to these declarative constraints, and send me this message when it occurs".

WPF should've made a generic complex event processing framework.

I started an FRP class library in a branch of my Sasa project, but since I'm not yet in a position where I can use it, just the basics are implemented (and not well tested). The evaluation model is based on FrTime, and the interface was modeled on OCaml React. I'll probably flesh it out sometime this summer.

Wow, cool. Have you had the time to look at other .NET libraries doing other things? It seems you have no problem seeing libraries outside .NET, but that might be thanks to the wealth of academic papers published on those two...

Yes, the FrTime paper and the React signatures were all I needed to understand what was going on. Of course, my implementation is still lacking recursion/delay, so perhaps I speak too soon... :-)

As for other libraries, Sean and I had a brief discussion about using Bling's signal library, but it turned out not to be suitable for my purposes. In fact, if I may tie two threads together, this is the exact reason why I couldn't just retarget Bling to my application. Safe extension is just far too difficult in C#.

I figured out a way to structure a retargetable signal library, basically, a way to write finally tagless interpreters in C#, but it's not a panacea.

Safe extension is not impossible in C#. I've come up with a modular mixin hack for C# that involves a bit of start-up reflection but not much overhead otherwise, especially since I'm generating code; see Extensions.cs in the NewBling project of the codeplex code. When you are generating code, a lot of hacks that are otherwise considered too slow become feasible--even an interpreter is OK if its just there to generate code that will do 99% of the application's work. Heck, you could even use Haskell without much perf consequence (as Conal does with Vertigo).

I'll certainly check it out! I meant specifically type constructor polymorphism as required for finally tagless interpreters: the technique results in an abstraction that's safe for clients to use, but requires a little care for anyone defining a new backend.

Actually, "tagless" isn't strictly accurate, as it involves a wrapper class for type safety and .NET carries runtime types; the type tags are not really used though.

This project uses the technique I was referring, if anyone's interested.

I mentioned this one to Sean via e-mail months ago just after his paper was finished, but Paul Stovell has his Obtics reactive programming library for WPF as well. I believe he is also a core contributor to Bindable LINQ. Microsoft developer Bart De Smet has also written a blog post about Update-able LINQ.

The other libraries you should look at on Codeplex are: Bindable LINQ, Obtics, and Continuous LINQ.

You may also want to pull out the Funcletization code from DLINQ. See Luke Hoban's reply in the MSDN C# Forums to Binding Lambdas when they are closures about that. Among other users, the commercial O/RM framework LLBLGen Pro uses it as part of its Linq to LLBLGen Pro API. This idiom allows you to serialize expression trees (if you note, the Expression API is not based on ISerializable objects, because .NET lifts variables out from the expression itself, and the workaround here is to perform some constant propagation, thus giving you Editable Expression Trees). This approach is really the only method that works, as you cannot wrap a closure within a closure and get it to serialize, since a closure is not serializable -- a generic compiler service cannot guarantee that what it encloses will be serializable. So, you write a mini compiler service -- the funcletizer -- to handle serializing expressions you know can be serialized.

Let me just say that I want a robust .NET utilities library as bad as anyone. I've looked at the code of various extension methods utilities on Codeplex, and some of them are just plain awful -- they don't document their algorithmic complexity, and, for example, I saw a String Join function that was poorly performant b/c it was calling the wrong underlying string function.

Part of this post is shameless finger wagging at some cool stuff .NET has happening, in the hopes it will attract more open source developers to .NET (well, Rotor and Mono and DotGNU).

Thanks for the links! They seem like some interesting projects, so I'll definitely check them out. Your "Binding Lambdas when they are closures" link is broken though. I also think the LINQ craze is a little over the top; processing expression trees requires too much complexity for building a dataflow graph, and they're a little inflexible in some cases.

For instance, the project I have in mind is dataflow for web UIs, but one which can transparently execute server-side or client-side (think "Bling for the web"). This could be done with expression trees, but they're actually more limiting than the finally tagless approach (FT), ie. all mobile code must be a lambda expression, so you can't translate a normal class method to JS and send it to the client; you can do it with FT.

I have done some pretty funny stuff with WPF (just ask Sean, he's seen my disgusting WPF meta-programming).

O.K. I ask Sean.

Sean, which pretty funny and disgusting stuff with WPF meta-programming did Z-Bo?

My apologies for sounding like an idiot. I had just been programming for 28 hours straight, and that was the last thing I said before I went to bed.

Some stuff I've done: Used MarkupExtension classes as Lispy reader macros, even transforming entire trees of XAML. For example, I convert at compile-time WPF stylesheets, which use the CLR's nominal type system, into my own structural type system. As the cost of doing this can be amortized to compile-time using the BAML compiler, it doesn't place any run-time configuration burden on the deployed application. You might wonder why on earth this is even necessary or important, and without a deep knowledge of the WPF class hierarchy, you would not understand its value. Basically, this structural type system allows me to use a *single* MarkupExtension to create a GoF Bridge pattern between various divergent class hierarchies. For example, the TextBlock control has the same property structure as other elements, but cannot be styled with WPF style sheets using Control targeting, because TextBlock is not a control.

Among the other things I do is I allow myself to plug-in any DSL for styling WPF controls, in a modular fashion. Unfortunately, neither of these tricks work in Silverlight (versions <=3). The second trick can work in Silverlight, but requires subclassing every control and exposing some better virtual event hooks similar to what Sandro's Sasa project does, effectively baking a "compiler service" into every FrameworkElement. This results in unacceptable assembly byte size overhead for shipping over the wire en masse. Similarly, other tricks I came up with for WPF failed in Silverlight land due to network performance considerations; I want my executable bits to be as lean as Jacques Lalane.

Back in August, when I had just finished my first WPF/Silverlight prototype, I decided I would release a large library of MarkupExtension classes and attached properties as an open source project called Cowbell, but I never released anything except for the general project outline and what the library would do (which is still very useful information not available anywhere else on the Web). I haven't updated that site except a few lines of links at the bottom since. Also, if it sounds a bit whacked and lacking a vigorous editorial pen, bare in mind I wrote it with two fingers while suffering from ulnar neuropathy (I'm better now).

Sean mentioned C# extension methods are somewhat limited, and I agree. Actually, the VB9 compiler can produce more efficient byte code for some extension scenarios than the C# compiler, due to better syntax hints. I am pretty close to finishing a series of blog posts, in tutorial style, explaining why Microsoft finally needs to release a MetaObjectProtocol.dll (although it may be too late). Put simply, the amount of code duplication (and design mistakes) that Microsoft has incurred from not having such a library in their code asset library is staggering. WCF and WPF each have their own implementation of DependencyProperty and DependencyObject, leaving WF 4 undecided as to which to use (ultimately the integration problem is now being pushed into the XAML Parser IIRC, a disgustingly awful abstraction decision 100x times worse than my Cowbell abstraction project). What's more, PowerShell, JScript.Net 8.0 Expando Properties, the now-defunct WinFS, and other places around .NET basically re-use the same meta-object concepts in various places, with roughly the same opt-in Flyweight implementation tricks. The big differences are how broken the interfaces are. What's more, this problem was acknowledged in 2003 by Don Box: "The fact that Longhorn currently has three models for property extensibility instead of one is an accident of history. Whether or not there is enough common functionality and model here to do unification is still an open question.". Box even jokingly nicknamed the problem as Longhorn: the eXpando Platform. Basically, the solution to the eXpando Platform problem was XAML: Indigo (WCF) now is using XAML as a bridge in much the same way I am using XAML MarkupExtension as a bridge, except their XAML Bridge is deeply integrated into the parser (a sure sign of bigger design problems). Intentional solution or accident of history? I'm not sure, but it is bad abstraction.

I always tell people "think of XAML as a poor man's Lisp, then you'll understand it for what it simply is, and not be as frustrated using it."