From Object Algebras to Finally Tagless Interpreters

Re:From Object Algebras to Finally Tagless Interpreters by StefanKarpinski on Saturday January 17, 2015 @02:00PM (#8905167)

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).

[ Parent | on HN ]

Re:From Object Algebras to Finally Tagless Interpreters by scscsc on Saturday January 17, 2015 @02:30PM (#8905256)

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

[ Parent | on HN ]

Re:From Object Algebras to Finally Tagless Interpreters by danking00 on Saturday January 17, 2015 @03:05PM (#8905351)

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.

[ Parent | on HN ]

Re:From Object Algebras to Finally Tagless Interpreters by yummyfajitas on Saturday January 17, 2015 @10:17PM (#8906471)

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).

[ Parent | on HN ]

Re:From Object Algebras to Finally Tagless Interpreters by seanmcdirmid on Saturday January 17, 2015 @10:32PM (#8906501)

As does C# with extension methods. It is especially useful when you have a generic class:

    class Foo<X> { ... }

    static class Foos {
      static void DoFooInt(this Foo<int> self) { .... }
    }

    new Foo<int>().DoFooInt();

I built a whole pimped library called "Bling" for C#/WPF to lift values into signal form around this technique.

http://bling.codeplex.com

Unfortunately, operators can't be externally extended in C#, so there is still a lot of wrapper creation, but extension methods can be used for that; e.g.

    Signal<int> a = ..., b = ...;
    var c = a.Bl() + b.Bl();

Bl is an extension method for signal ints that returns a wrapper around the argument that allows for access to the + method. Bl is overloaded for a variety of types to provide access to those wrappers.

[ Parent | on HN ]

Re:From Object Algebras to Finally Tagless Interpreters by beagle3 on Saturday January 17, 2015 @07:43PM (#8906153)

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

[ Parent | on HN ]

Re:From Object Algebras to Finally Tagless Interpreters by sclv on Sunday January 18, 2015 @02:17PM (#8908478)

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.

[ Parent | on HN ]

Re:From Object Algebras to Finally Tagless Interpreters by ddandd on Saturday January 17, 2015 @08:05PM (#8906194)

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

[ Parent | on HN ]

Re:From Object Algebras to Finally Tagless Interpreters by gclaramunt on Sunday January 18, 2015 @12:24AM (#8906746)

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.

[ Parent | on HN ]

Re:From Object Algebras to Finally Tagless Interpreters by StefanKarpinski on Sunday January 18, 2015 @11:10AM (#8907827)

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

– Fermat

[ Parent | on HN ]

Re:From Object Algebras to Finally Tagless Interpreters by gclaramunt on Monday January 19, 2015 @12:08PM (#8912771)

But those are pretty short to write (explaining the category theory machinery behind it takes several book chapters tho :) )

[ Parent | on HN ]