Home » forums » LtU Forum

A Variation of the Expression Problem and two Solutions in Scala

Abstract: The expression families problem can be defined as the problem of achieving reusability and composability across the components involved in a family of related datatypes and corresponding operations over those datatypes. Like with the traditional expression problem, adding new components (either variants or operations) should be possible while preserving modular and static type-safety. Moreover, different combinations of components should have different type identities and the subtyping relationships between the different combinations should be preserved. By generalizing previous work that explored the connection between type-theoretic encodings of datatypes and visitors, we propose two solutions for this problem in Scala using modular visitor components. These components can be grouped into features that can be easily composed in a feature-oriented programming style to obtain customized datatypes and operations.

This is a draft paper on a topic that I think is of the interest of the readers of this forum. It motivates a variation of the expression problem and proposes two solutions in Scala inspired by type-theoretic encodings of datatypes.

By Bruno Oliveira at 2008-12-26 05:39 | LtU Forum | previous forum topic | next forum topic | other blogs | 6355 reads

Comment viewing options

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

I went through this in

I went through this in Jiazzi and I've found that the problem with component-oriented programming isn't largely due to languages at all but rather a social/strategic problem (producing the components to be resued and reusing them is hard, even if a perfect language is assumed). But I digress...

You didn't compare to virtual classes. The virtual class encoding in Scala (styled after Jiazzi's open class pattern) provides all the features you list in your paper and more (you can add state to existing classes).

By Sean McDirmid at Sun, 2008-12-28 04:33 | login or register to post comments

Components and Virtual Classes

Hello Sean,

Thank you for the comments! Here's a quick reply for today.

I think your point about COP is a very good one and it is one that I do *not* disagree with. I believe that in general producing reusable components is hard and often it is many orders of magnitude harder than producing less reusable software. Although I do think that having better languages and better abstractions helps.
Did you comment about this because of this sentence: "the COP vision has not been fully realised, largely due to limitations of current programming languages"?

Regarding virtual classes, have you read section 7.5 (Virtual types)?
Unfortunately, I do not compare the solution with Jiazzi's open class pattern. But I do compare it with 3 other similar solutions.
Not only I compare the work in this paper with virtual types (as in Scala), virtual classes (as in GBeta) and Jx nested classes; but I also acknowledge that these solutions are pretty good... Take a second look!

By Bruno Oliveira at Sun, 2008-12-28 14:42 | login or register to post comments

Does the open class solution support object-level extensibility?

Hello Sean,

I'd like to elaborate a bit more on your comment:

The virtual class encoding in Scala (styled after Jiazzi's open class pattern) provides all the features you list in your paper and more (you can add state to existing classes).

What I mean in my paper by "Subtyping relations between components should be preserved." is related to what Torgersen calls object-level extensibility. I think I should have been a bit more clear when stating this requirement because this sentence is somewhat overloaded. There are two possible meanings here:

1) It can mean the following: "The subtyping relations between virtual types in an extended class should be preserved in relation to the same types in the original class". For instance, if I have a class A with virtual types B and C where C is a subtype of B, then in a class D that extends A, I should also have virtual types B and C where C is a subtype of B.

2) Or, it can mean that an object of some extension can be used in the context of some other extension if some suitable subtyping relationship between the components of the two extensions exists.
In particular, if you read the text motivating the subtyping requirement, you will see that what I expect here are things like extensions of expression datatypes are supertypes of the original datatypes.

Now, my solution supports 2) (See page 10) --- and it trivially supports something like 1)... But I don't think the standard open class pattern solution supports any form of object-level extensibility. In fact, I believe that Odersky and Zenger indirectly acknowledge this when they say
"An interesting variation of Torgersen’s solution uses JAVA’s wildcards to achieve object-level extensibility, i.e. reusability of actual expression objects across extensions." (in Independently Extensible Solutions to the Expression Problem).

I may be wrong, but I think the only other solution in the literature that actually satisfies this requirement is Torgersen's third solution to the expression problem.

What do you think?

By Bruno Oliveira at Mon, 2008-12-29 05:59 | login or register to post comments