From Object Algebras to Finally Tagless Interpreters

https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-object-algebras-to-finally-tagless-interpreters-2/

by lelf • 12 years ago

76 16 12 years ago

oleksandrmanzyuk.wordpress.com

tel• 12 years ago

This is fantastic! This is the kind of connection between OO and FP that I think should be heralded much more.

Finally tagless style is an important architectural style for Haskell programming since it allows you to pass algebra joining up into the Prolog solver. This is more than adequate for simple combinations of algebras and workable (with a little elbow grease and commentary) for more complex ones.

Edit: Also, that boilerplate reduction on slide 30-32!

manilafolder• 12 years ago

Here's a link to the author's blog post on the subject, which has the text from the talk (in addition to the examples contained in the PDF slides): https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-objec...

dang• 12 years ago

Thanks—we changed the URL to that from http://kievfprog.net/talks/oleksandr-manzyuk.pdf, which is linked in the first paragraph.

StefanKarpinski2• 12 years ago

Multiple dispatch solves the expression problem so intuitively and straightforwardly that it's often hard to remember why it was a problem in the first place. In Julia, for example:

    abstract Exp

    immutable Lit <: Exp
        value::Int
    end

    immutable Add <: Exp
        left::Exp
        right::Exp
    end

    evaluate(lit::Lit) = lit.value
    evaluate(add::Add) = evaluate(add.left) + evaluate(add.right)

If you want to add a new operation, it's straightforward:

    view(lit::Lit) = string(lit.value)
    view(add::Add) = string("(", view(add.left), " + ", view(add.right), ")")

If you want to add a new type of expression, it's also straightforward:

    immutable Mul <: Exp
        left::Exp
        right::Exp
    end

    evaluate(mul::Mul) = evaluate(mul.left) * evaluate(mul.right)
    view(mul::Mul) = string("(", view(mul.left), " * ", view(mul.right), ")")

That's all there is to it. Of course, it's actually the external dispatch that's crucial, not the multiple dispatch. (But multiple part is very handy for other things, especially in numerical work).

scscsc• 12 years ago

If you forget to write view for the Mul case, does the compiler issue an error? (in other words, is it strongly typed?)

danking00• 12 years ago

This seems like a likewise elegant solution. However, it's not immediately obvious to me how to make this work with a static type discipline. Are there languages that do this?

It seems like part of the benefits of the approaches described in the blog post is that the type system will catch incomplete extensions to the existing data or methods.

beagle3• 12 years ago

Nim Lang (previously Nimrod) can do that, if I understand correctly.

yummyfajitas• 12 years ago

In Scala, for algebraic data types like expressions and addition, you'd just use pattern matching. That would encompass the example fully.

Scala has an "external" dispatch mechanism as well, basically a way to create new typed methods, namely pimping:

    implicit class FooWrapper(foo: Foo) extends AnyVal {
      def newMethod: Int = ...
    }

    val x: Foo = new Foo()
    x.newMethod

These are all checked at compile time.

Note that the example given above is actually not multiple dispatch, but merely adding methods to a type. It differs from function overloading (a Java/C++) feature only syntactically.

Multiple dispatch would be dispatch on multiple type arguments, not simply one (which Julia has, but Scala does not).

ddandd• 12 years ago

I believe that a similar approach can also be used in C++ with the help of ADL [1] and some template magic. Though it may only work on expressions whose concrete type may be known at compile-time (which makes it pretty useless).

[1] http://en.wikipedia.org/wiki/Argument-dependent_name_lookup

gclaramunt2• 12 years ago

Hmm, but when you add a new type of expression, you still have to write the particular implementation of the functions for that type. There are other approaches to generic programming where when you add a new datatype, all the already defined functions work, and if you add a new function, it automatically works for all the datatypes.

StefanKarpinski2• 12 years ago

I started to write those but it got a bit long for a comment.

– Fermat

sclv• 12 years ago

It is well known that in the untyped (or dynamically typed if you prefer that language) case then the expression problem trivializes.

In fact, if we sacrifice type-safety then the problem trivializes in a typed language too.

skybrian• 12 years ago

It seems like a nice pattern. For popularizing this to Java programmers, I think the name "parameterized factory" might work better. Parameterizing a factory for nodes of an AST by the type of node returned (which might not be an AST node at all if it's fully evaluated) seems like a nice idea.

I think that over time, as you add new node types, you'd end up with lots of interface types, so you'd have to go back and clean them up after extending the language. But it will make the transition easier.

Also, real languages have multiple node types (expressions, statements, types, etc) that aren't interchangeable,so that might result in lots of type variables.

scotty79• 12 years ago

It seems that this structure could be implemented in C# with inheritance (to add new entities) and extension methods (to add new operations) and var keyword to achieve type inference to verify correctness at compile time.

From Object Algebras to Finally Tagless Interpreters

Related Stories