Home » forums » LtU Forum

Does these constructs solve the expression problem?

While thinking about the expression problem and toying with (toy) language design, a simple solution to the problem came to mind. The expression problem is about extending datatypes and adding functions without recompiling the orignal code, so why not have a simple construct to extend each of these?

Every time you add a constructor to an algebraric datatype, you need to extend each of the functions on the type with a case covering the constructor. The two construcs are thus: 1) extend a datatype and 2) extend a function. Addition of completely new functions comes for free in a functional setting.

Here is some pseudo-code illustrating the idea:

# declare a new algebraric datatype Expr with one constructor
type Expr:
    case CONST(Int)

# declare a new function eval
function eval Expr -> Int:
    case CONST(x):
        x

# extend the algebraric datatype Expr with another constructor
extend type Expr:
    case ADD(Expr, Expr)

# extend the function eval with another case
extend function eval Expr -> Int:
    case ADD(x, y):
        eval(x) + eval(y)

# declare an additional operation on Expr
function toString Expr -> String:
    case CONST(x):
        intToString(x)
    case ADD(x, y):
        eval(x) ++ "+" ++ eval(y)

I realize that the implementation of extendable functions would need indirection (so no inlining), but other than that I don't see any problems with it.

My formal education in PL theory is very limited still, and I'd appreciate any comments that visualize weakness in the above constructs, or any references to languages that have similar constructs.

By Ahnfelt at 2007-05-25 13:03 | LtU Forum | previous forum topic | next forum topic | other blogs | 4543 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

You don't seem to mention

You don't seem to mention the real problem with the expression problem wich is type safety. Perhaps its obvious but i don't think it would hurt to spend some time on how to type check your constructions.

By Felicia Li Svilling at Fri, 2007-05-25 14:30 | login or register to post comments

Oh, you're absolutely right.

Oh, you're absolutely right. I'm not done with the type checking rules yet, but I suspect they won't be much different from a standard functional language like ML.

The type of a function does not change when extending it, so extensions shouldn't break the typing old usages of it.

Adding a constructor to a type may indtroduce inexaustive pattern matching, but I can't see it breaking the typing in other ways.

Still, it certainly requires some investigation. Thank you for your comment.

By Ahnfelt at Fri, 2007-05-25 16:25 | login or register to post comments

Inexhaustive pattern matching

"Solving" the expression problem by allowing inexhaustive pattern matches is relatively easy. Your example above translates trivially into something like CLOS or Dylan (with constructor cases becoming subclasses, Scala-style).

A number of different sets of parameters have been given for what should constitute a "solution" to the expression problem, so one could argue that an approach that introduces inexhaustive pattern matches is acceptable. Still, some of the more desirable properties are:

- Type-checked (as you identify). In languages with loopholes in the type checking (e.g. Java/C# casts), this is usually interpreted as meaning that these features should not be used in the solution.

- Exhaustive. Ideally your example would give a static error if one added the ADD constructor without extending the definition of eval. Solutions that satisfy this property by requiring default implementations on all operations are often seen as less satisfactory (since the only sensible default might be to throw a run-time error).

- Modular. One of the easiest ways to guarantee exhaustiveness would be to collect all the disparate cases for datatypes and operations together and then check the resulting "complete" operations for exhaustiveness. This approach, however, could interfere with separate compilation, requiring consistency checks to be made at static (or even dynamic) link time.

- Independently Extensible. This is one of the things Scala tries to address. We would like to be able to take a module that adds a new operation and one that adds a new constructor case and define a new module that uses both extensions. Achieving this while still satisfying other desirable properties can be tricky.

It is probably worthwhile to decide which properties are valuable in your target domain (and checking the literature should provide a much better list than this one I threw together).

By Tim Foley at Fri, 2007-05-25 18:13 | login or register to post comments

It appears that there's more

It appears that there's more to the concept than I thought. Thank you for your list, it seems like a good pointer in the right direction. I'll find some more information on the subject before designing it further.

By Ahnfelt at Fri, 2007-05-25 19:39 | login or register to post comments

You may wish to see...

...this post. In particular, read "Independently Extensible Solutions to the Expression Problem," which has an excellent survey of the problem and the solution space explored thus far. As far as I know, only the Nice solution from that thread, and the gbeta solution from another thread, are missing from that survey.

By Paul Snively at Fri, 2007-05-25 20:39 | login or register to post comments

Thank you, that looks

Thank you, that looks interesting. I'll be sure to check it out.

By Ahnfelt at Fri, 2007-05-25 22:51 | login or register to post comments