The Expression Problem | Hacker News Reader

The Expression Problem

wiki.c2.com

96 pointsafiori45 comments

My favorite solution to the expression problem is the tagless-final style. It can be implemented in both ML-likes and Haskell-likes leveraging either expressive module systems or type class systems to combine the benefits of both shallow and deep embedding of DSL's. It requires one to bend their mind to really understand but once it clicks it is extremely powerful. Perhaps that "click" is the mind snapping once sufficiently bent.

http://okmij.org/ftp/tagless-final/

"The so-called ``tagless-final'' style is a method of embedding domain-specific languages (DSLs) in a typed functional host language such as Haskell, OCaml, Scala or Coq. It is an alternative to the more familiar embedding as a (generalized) algebraic data type. It is centered around interpreters: Evaluator, compiler, partial evaluator, pretty-printer, multi-pass optimizer are all interpreters of DSL expressions. Doing a tagless-final embedding is literally writing a denotational semantics for the DSL -- in a host programming language rather than on paper."

Tagless-final is also closely related to the technique of object algebras [0], which I use pretty often -- at least at the design stage, before flattening out some of the degrees of freedom. See this other blog post [1] for more about both.

[0] "Extensibility for the masses", https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf

[1] "From Object Algebras to Finally Tagless Interpreters", https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-objec...

Lovely! I think it speaks to the value of an idea that it is developed independently more than once.

It should be noted as it is in the abstract of your first reference that these are elaborations on the core idea of Church encodings (and Boehm-Berarducci encodings).

There is also that video [0] discussing object algebras as a solution to the expression problem.

[0] "Who's Afraid of Object Algebras?" https://www.infoq.com/presentations/object-algebras/

I think Julia has a neat answer to the Expression Problem:

- To add a case to a type, the type needs to be abstract, which allows you to declare concrete subtypes. (Julia's subtyping is not OOPy, and it doesn't have FP-style algebraic types.) Then you can add methods to generic functions that are called when passed an argument of your new concrete type, when they need special cases.

- To add operations to an existing type, define a new generic function. You can often do so using just abstract supertypes, and let the compiler optimize to concrete types, but you can also define special-case methods for specific concrete types if you need to.

Clicked on the article to post the same thing. I haven’t really had this issue any more since using Julia.

Yes, Julia has multimethods. This is called out in the article:

> Open functions (functions that can be extended with new pattern-matches), open data-types (data types that can be extended with new patterns), and MultiMethods ('open' specialized polymorphic functions with 'open' set of classes), and PredicateDispatching, are all viable approaches.

That same multiple dispatch approach is in Common Lisp, though not used to as great an extent as in Julia (that is, things like + aren't open to extension without shadowing the main definition and creating your own).

I might be wrong, as my contact with Julia has been a while ago. But IIRC, Julia, having no type checker [1], cannot check whether every function is complete regarding the type in question.

This is somewhat comparable to OCaml's polymorphic variants, which only solve the expression problem if you give up the completeness check of pattern matching.

[1] yes, I know it does a lot of run-time stuff with things called types, but that's something fundamentally different. Really.

Within a single codebase, it's not too big a deal. You can add a new clause to each switch statement, pattern-match statement, or visitor class. The compile errors tell you what you need to do. Compile-time checking is good, right?

The issue gets stickier when you have a public API and can't make the upgrade in a single patch. What happens if one library defines an AST for a language, there are unknown downstream dependencies that define language tools for various purposes, and you want to change the language to add a new AST node type?

It seems fairly clear that you are revving the language and any tools you have need to be modified to handle the new language construct. They will work fine on v1 of the language but they don't know how to handle v2. This may be a backward-compatible change for programs, but it isn't for tools. They need to handle any possible program, so they need to upgrade or they will break for v2 programs.

But, do we want a lack of v2 support to be a compile error when building the tools? All the tools should work fine with v1. It's only for v2 code that we need the change.

It seems like for smooth migration you need to support multiple, similar versions of the language at the same time. v1 and v2 should be defined simultaneously and tools updated incrementally to support v2.

This gets to be a burden when you are changing the language a lot, though.

Not a complete solution, but hugely relevant: https://www.microsoft.com/en-us/research/uploads/prod/2016/1...

Framing this as OOP vs FP isn’t a good framing. Notably in FP you can use first class functions for your area and perimeter functions and experience either side of the “problem”. In other words, a struct with fields for area and perimeter functions is functionally equivalent to the Shape base class in the OOP example.

Ultimately, the problem boils down to language features that give you the option to update a single location or to update many locations, and each situation has its place (for example, sum types are generally less extensible to downstream packages).

The original framing was OOP vs FP by Wadler himself.

https://homepages.inf.ed.ac.uk/wadler/papers/expression/expr...

No doubt, I'm just arguing it wasn't a very good framing.

I still don't get the new "distributed" version of c2.com. It looks like a failure, based on traffic rates. Ward is a smart person, but he laid an egg on that project. (Ward pretty much invented the wiki concept.)

Ward Cunningham should go back to the original CGI wiki, but add the JavaScript from https://flak.tedunangst.com/ so that SPA-lovers can smile in satisfaction at a webpage with a goddamn loading screen.

> The ExpressionProblem is a specific example of a larger class of problems known generally as Cross Cutting Concerns [...] Many languages include designs to help solve the ExpressionProblem. Open functions (functions that can be extended with new pattern-matches), open data-types (data types that can be extended with new patterns), and MultiMethods ('open' specialized polymorphic functions with 'open' set of classes), and PredicateDispatching, are all viable approaches.

Working on GPU code, I feel like I'm always stuck in this problem of 'cross-cutting concerns'. I remember the guy who hired me years ago said during the interview, "we [programmers] have solved the problem of writing code for functionality, but we haven't solved the problem of writing code for performance." And this is what he meant, that cross-cutting concerns are ever present, and a new feature in the code can introduce the need for a complete refactor, or a major top-to-bottom flip in your data structures, etc.

Which languages & language features are good at both solving the expression problem functionally, and can do this with the highest priority being performance?

I also wouldn't mind hearing advice about how to evaluate when to use such features, because most often when I bump into this problem, it's not really due to lack of language features, it's due to having chosen not to use them from the start because there's some development time overhead, and I decided I most likely wouldn't use it, then over time painted myself into a corner.

> it's not really due to lack of language features, it's due to having chosen not to use them from the start

That itself is a language deficiency, though, right?

Knuth on this topic:

https://cr.yp.to/qhasm/literature.html

Yeah, I suppose you're right it can be viewed as a language deficiency if the right thing to do is difficult and the wrong thing is easy & tempting. I guess I take responsibility for it though because I'm not sure I can imagine a time when there won't be a tradeoff to be made. Good engineering always has, and I'm guessing always will...?

There definitely is something important in the ideas Knuth is expressing abstractly here, and thank you for the link. Perhaps this idea really is percolating slowly to the compiler writers, because at work we have conversations about how to talk to the compiler so that it can better optimize.

> if the right thing to do is difficult and the wrong thing is easy & tempting

That's not what I meant by linking to the Knuth piece. The deficiency lies in the language that doesn't allow you to start off doing the easy thing and then make it "right" through further dialogue, keeping the starting point easy.

I'm pretty sure this is the real intent behind Knuth's focus on literate programming.

This is not unlike any other engineering. One can't just arbitrarily change thermal isolation properties of a house without having to do some broader changes that can affect it's general structure and other aspects of it. Or you can't take a Cessna and dial up the performance requirements to make it fly as fast as a jet fighter.

For some reason SWE oftentimes hope to achieve some general-AI level tooling and methodologies that would magically let them ignore everything other than than aspect they desire to change.

Some interesting discussion here [0] about an OOP solution to the expression problem (object algebras).

[0]: http://lambda-the-ultimate.org/node/4572

I would be interested to hear how this interacts with typeclasses/traits. In seems like they maybe give you more flexibility to separate the requirement to have an area from the requirement to have a perimeter. But I think you still run into the problem of having to "update your code" everywhere, just in a different way.

Phillip Wadler coined the term (while recognizing that the concern was preexisting), and co-invented typeclasses specifically as an attempt to address it. So you're definitely right to think they're related.

The current situation is that it's like Karnaugh maps: If there are overlapping clauses and default/generic implementations, then yes, typeclasses/traits/interfaces can cut down on the amount of code needed. However, in the worst case, all of the implementations need to be provided.

This is a pretty good article that I think will answer your question: https://eli.thegreenplace.net/2018/more-thoughts-on-the-expr... - it shows how typeclasses almost but not quite solve the Expression Problem, then goes on to use higher-kinded types for a more complete solution.

Typeclasses are roughly equivalent to passing abstract factories around. This is enough to solve the expression problem and is known as Tagless final encoding, or object algebras in oop:

    interface Num<A> {
        A add(A l, A r);
        A lit(int i);
        ....
    }
    class PrintNum implements Num<String> {
         String lit(int i){ return Integer.toString(i); }
         String add(String l, String r) { return l + " + " + r;}
         ...
    }
    class NumInt implements Num<Int> {...}

    function A foo<A>(Num<A> f) {
        return f.add(f.lit(3), f.lit(4));
    }

You can add new functions by extending the interface, you can add new implementations by implementing those interfaces.

However you need one class which implements all necessary interfaces for your final type to run the code. This means boilerplate if the interfaces come from different libraries.

You can reduce copying by using adapters which implement some interfaces and forward the rest - but then all adapters have to forward all unrelated methods! This is known as the quadratic instance problem in MTL.

There are lots of attempts to solve this in haskell and currently they are all worse then Tagless final on some axis, usually performance.

Just adding to the related links on this topic, here's a talk by Guy Steele that I was reminded of

http://www.dreamsongs.com/ObjectsHaveNotFailedNarr.html

William Cook's paper on the deeper meaning (TM) of the expression problem: "Object-Oriented Programming Versus Abstract Data Types" (http://www.cs.utexas.edu/~wcook/papers/OOPvsADT/CookOOPvsADT...)

Common Lisp's generic functions solve this problem. One of these years the rest of the world will figure this out.

Dart solves this quite elegantly using mixins. https://dart.dev/guides/language/language-tour#adding-featur...

I'm not sure that it does? From the c2 example, the goal is to have all Shapes respond to area() and perimeter(), but in the example you linked to, only Musicians will respond to entertainMe(), not all Performers.

There is another solution to the area/perimeter problem used as an example.

Represent a shape as a series of edges and verticies. To compute the are of any shape, sum the lengths of the edges. To find the area, sum the signed areas of the triangles formed by each edge and the origin. Works for all shapes, just define a new one from points and edges.

The point of TFA remains. What abstraction or data structure you select can determine what opertions on the data are easy or hard. This is why we need to study data structures and such - so you can choose the right one for the problem at hand, not so you can pick your favorite and shoehorn every problem into it.

...But this isn't a matter of picking the right data structure, like swapping out a stack for a queue. The problem arises for elementary structs of finite size, simple data objects. If the list of operations a type needs to support never changes, of course it's more feasible to create a type that supports those operations.

The actual area to learn about here is designing for extension, and software architecture in general, so you can get better at identifying what kinds of changes are going to be simple and what kind will be expensive, so you can tailor your solution to the range of situations you think you're going to face.

My solution to represent shapes allows trivial extension in both way presented in TFA. Adding triangle simply requires some kind of definition in terms of what already exists. Adding a new measure (area/perimeter) means defining that once for what already exists.

The fundamental mistake here is building code that reflects human concepts rather than more fundamental mathematical ones.

Generalization is not the same as extensibility.

Writing general purpose code is harder up front. Extending your code for every new shape leads to complexity problems.

That already doesn't work with circles though.

>> That already doesn't work with circles though.

That depends on weather you want to use arc length and certain kinds of areas.

Calculus is a thing too.

That doesn't make any sense. If you want to represent an ideal circle, calculus doesn't help, best you can do is pick an epsilon and add zillions of points to create an approximate circle. Even then most computational geometry algorithms won't work for that DS. If you're applying algebraic operations to that circle (let's say shear) you'll have to modify each and every single point (inefficient). What you want to do is to preserve a list of ideal (Platonic) shapes, apply transformations to them, and then convert this geometry to a list of vertices, edges and faces. Source: I've been a researcher on making parametric CAD tools that deal with problems like this for years.

Arc length can be computed via integrals, but we dont really bother because breaking into segments is good enough (and elipses dont have a nice solution). For circular arcs, closed form solution exist even for the area. If you can accept the accuracy, the method of defining shapes from primitives is (to me) clearly simpler. It was of course just an example TFA used to highlight different approaches.

We are on the same page. Dont use line segments, use NURBS curves. Length and area can be evaluated via piece wise approximation or numerical integration along the curve - which is a different flavor of the same thing.

Yeah I guess my point was at that point you'll have different APIs for square and circle.

Since I'm rewriting, I don't need to update.

Reply on news.ycombinator.com