The Expression Problem and Tables | Hacker News Reader

The Expression Problem and Tables

joelburget.com

42 pointsqubitcoder19 comments

Clojure has the best solution to expression problem I've seen in a real programming language

    (defmulti sound class)
    (defmulti eat class)
    (defmulti attack class)

    (defmethod sound ::cow [c] "Moo!")
    (defmethod sound ::dog [c] "Roof!")
    (defmethod sound ::cat [c] "Miau!")

    (defmethod attack ::dog [c] (bite c))
    (defmethod attack ::cat [c] (scratch c))

    (defmethod eat ::cow [c] ...)
    (defmethod eat ::dog [c] ...)
    (defmethod eat ::cat [c] ...)

    ...

    (derive ::mad-cow ::cow)
    (defmethod sound ::mad-cow [c] "MooOOOooooOOOOoooo!")
    (defmethod attack ::mad-cow [c] (stampede c))

The layout problem remains, and I would like to be able to do sql- or prolog-like queries on code, but IMHO it's IDE and tooling problem more than missing language feature.

Also in clojure you can add arbitrary http://clojure.org/metadata to each value, so marking your function as deprecated/in-progress/whatever is easy (but it seems you can't easily add metadata to separate implementations of multimethod right now).

    ...
    (defmulti "Attacks."
              {:deprecated "Use eat instead.",
               :author "me"}
              attack class)
    ...

Also - to confirm that people want to specify rules in tables - I've been working at 2 different companies where we had code generators with .xlsx files as input and .java as output.

Yup, multimethods are awesome. By the way, they come from CLOS - Common Lisp Object System - so Common Lisp supports them as well.

I'm not sure if Clojure supports that, but in CL you can also have :before, :after and :around methods that will be called before, after and instead of an actual method, respectively. This gives you another interesting boost to extensibility.

EDIT:

RE querying - using Metaobject Protocol (MOP) you can do all sorts of queries you like. For instance, to compute "animals that eat" you could use generic-function-methods on a generic eat to get a list of all method metaobjects (objects associated with methods), from which you can determine for which classes an eat method is defined.

CLOS + MOP is quite possibly the most powerful object system ever made.

How so? You ignore that the expression problem is about using static types. See the original problem statement.

In languages like Smalltalk or Lisp, the Expression Problem has easy solutions - but they are not statically typed.

The point is to not violate the type safety of the language used. There are plenty of dynamic languages that don't offer a solution to the expression problem.

With that said, you can add gradual typing to Clojure with Core.Typed and still solve the expression problem using multimethods without violating type safety.

Everything looks like a good idea in a blog post. Your homework, if you are serious about this, is to crack open a non-trivial, but not huge, program and apply this idea to it. See how the table looks when you're trying to fit a few dozen elements into it in each direction, where the contours of some real problem created the structure (very important!). You can tweak the organization of the program a bit, because changing paradigms often requires tweaks to the best solution, but it's important that whatever the problem was is still solved at the end of the tweaking (i.e., no fair "simplifying" until you've simplified the entire problem away).

I say this not because it will prove impossible or useless, but because you will learn things in the process that will help you refine the idea. Refinement into "what I want is not really possible at scale" is certainly one possible outcome, but there are many other possibilities.

(Certainly one problem you'll encounter is that real code is horrifyingly non-"normal", in the statistical distribution sense. A program of 100 classes is very likely to have 90 of them part of one hierarchy, with the remaining 10 each doing isolated things. Understanding the table representation of such things may have the MEGO ("my eyes glaze over") problem, but then, perhaps you can find something for that.)

As others have said, the key is to solve the expression problem without discarding type safety. :)

I think that this problem is basically a simple structural relation on sum types in disguise. That's how I interpret the "Data Types a la Carte" paper anyway.

So if you have:

  class Foo a where
    foo :: a -> String

And say:

  instance Foo A+B where
    foo A = "a"
    foo B = "b"

And:

  instance Foo C+D where
    foo C = "c"
    foo D = "d"

Then if you extend your data type to A+B+C+D, then a simple instance generator should be enough to tie it all together:

  instance (Foo v, Foo w) => Foo v+w where
    foo (inl v') = foo v'
    foo (inr w') = foo w'

I have a (currently internal to my company) Haskell-like language with structural sum/product/variant/record types where we can do this kind of thing. Otherwise "Data Types a la Carte" has the solution in the typed setting of vanilla Haskell (even if it's a little wordy).

Sum types + exhaustiveness checking already do this, right? For this example:

  type animal = Cat | Dog
  type action = Sound | Eat | Attack

  let cat_sound () = printf "meow"
  let cat_attack () = printf "scratch"
  let dog_sound () = printf "woof"

  let act animal action = match animal,action with
  | Cat, Sound  -> cat_sound ()
  | Cat, Attack -> cat_attack ()
  | Dog, Sound  -> dog_sound ()

Compiling this yields:

  Warning 8: this pattern-matching is not exhaustive.
  Here is an example of a value that is not matched:
  (Dog, (Eat|Attack))

just as we'd like.

The problem is not so much if the compiler will catch it, but how to lay out the new code/types in an editor, hopefully all in one place or accessible from one place.

C++ will catch a missing combination at compile time as well.

Note that the given example has only one place where all combinations are defined. Not sure if this could be done in C++.

Adding new animals or actions requires access to and recompiling this code. The expression problem attempts to find a way around that.

I'm not proposing this as a solution to the expression problem (which has actual solutions, as noted in the other comments [0] and elsewhere [1]).

It is, however, an extremely simple way of implementing the table-style dispatch outlined in the post, with a reasonable layout and compile-time completeness checks.

It's not open to extension outside the compilation unit, but in exchange it is dead simple and you still only ever need to change exactly two places in the code if you want to extend along either axis. Sometimes you just don't need polymorphism when a switch statement will do.

[0] https://news.ycombinator.com/item?id=9409779 [1] (PDF) http://www.math.nagoya-u.ac.jp/~garrigue/papers/variant-reus...

A staticly-typed solution:

https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-objec...

https://news.ycombinator.com/item?id=8904182

Multimethods, introspection and a good IDE can get you very far in this direction. For an example, see https://opendylan.org/history/apple-dylan/screenshots/browse... [There likely are older Lisp or Smalltalk implementations of this idea]

"we gain the power to query: implementations calling a deprecated function, implementations marked TODO, unimplemented cases, animals which eat, functions written by me, with no tests"

I think what you're looking for is a good IDE and Scala or Java

No IDE needed with Common Lisp, you can get most of this data via standard language features and Metaobject Protocol, and for whatever else you need to keep track of, just write a few macros and you're done.

Go's implicit interfaces are one possible solution to this problem.

> animals which eat

    type eater interface { eat() }
    somEater, isEater := value.(eater)

Or something, my Go isn't very good.

This text reminds me of row polymorphism in OCaml object system. Or maybe I got it all wrong.

Reminds me of TOP - Table Oriented Programming - as discussed in the c2 wiki. I use those simple but helpful ideas to this day.

I thought of this too. I remember reading it years ago and wondering why this idea had no traction. I honestly think some sort of tuple oriented programming paradigm will eventually emerge at the forefront. Look at R datatables for example.

Reply on news.ycombinator.com