[Discussion item] Hi, I came across this article <...

# language-evolution

[Rohan Maity]

[Discussion item]
Hi,
I came across this article Expression problem and its solutions, in this author discusses various languages and how they fall short to solve the expression problem because of lack tools. Author further went and told how Closure though its language features it solves the expression problem

A brief explanation on expression problem

Imagine that we have a set of data types and a set of operations that act on these types. Sometimes we need to add more operations and make sure they work properly on all types; sometimes we need to add more types and make sure all operations work properly on them. Sometimes, however, we need to add both - and herein lies the problem. Most of the mainstream programming languages don't provide good tools to add both new types and new operations to an existing system without having to change existing code. This is called the "expression problem".


Now the crux of the Clojure language to solve the expression problem was open methods i.e you can add methods to the class without changing the source code

Here is the Clojure example by author: link


After going through this, it occurred to me, the extension functions of kotlin kinda does the almost same job. It allow us to add function to the already existing class without changing its source code in a way (I am excluding the part where in bytecode it creates a static function)


Here is my example for kotlin which I think solves the expression problem (gist link)

// Initially I have an interface Expr (just like in Java) and have two classes  (Constant
// and BinaryPlus) implement that interface 


interface Exp {
    fun eval(): Double
}

class Constant(val value:Double): Exp {
    override fun eval(): Double = value
}

class BinaryPlus(val lhs: Exp, val rhs: Exp): Exp {
    override fun eval(): Double {
        return lhs.eval() + rhs.eval()
    }
}


/**
* Here, I added the stringify() method (which is a tool or operation) to the interface Expr,
* without touching the interface and classes which are implementing it.
*/

fun Exp.stringify() : String {
    return when(this) {
        is Constant -> value.toString()
        is BinaryPlus -> "${lhs.stringify()} + ${rhs.stringify()}"
        else -> ""
    }
}

// Here is how, I can use it

fun main() {
    println(BinaryPlus(Constant(4.0), Constant(9.0)).stringify())
}

/**
* Now in object oriented languages, adding types is easier 
* and functional languages adding tools(or operations) is easier 
* but since kotlin can act as functional and object oriented and with my above given example.
* I think extension function solves the expression problem for kotlin.
*/

[Ruckus]

I am excluding the part where in bytecode it creates a static function

That's a pretty significant exclusion. While extension functions are pretty, that's all they are (syntax sugar). There's no functional difference between what you wrote and

fun stringify(exp: Exp) { ... }

println(stringify(BinaryPlus(...))

So I don't think this would actually qualify as a solution, but I may be reading the definition too narrowly.

[Rohan Maity]

In your example, it has become independent function, where as an Extension function (even though static) it becomes the part of class. Receiver is the class itself. So in a way you are attaching some functionality to a class. Thats what the one part of expression problem is, ablility to attach functionality to a data type.

I agree to the functional part, but I think from writing code perspective, if I want some behaviour to be a part of class (to which I don't or can't add code) I would prefer extension function. Even though it's syntax sugar but it's important one to help me distinguish what behaviour can be part of class and what can an independent one.

The issue could arise, when it's matter of accesing private fields. But I am not sure about it whether extensions should be able to access private fields in the first place.

But with current state of extension functions, I think it does solve the problem to some extent.

Please add points, if I am missing something

[Filip Dolník]

Unfortunately, using extension functions does not solve the issue. If you add a new class “FunctionCall” you will be forced to modify the stringify function. (The problem states that you cannot modify existing code.) Therefore, you are just flipping the expression problem matrix as shown in the article (section about the visitor pattern).

Note that you cannot write additional extensions, for example:

fun FunctionCall.stringify(): String {
    return "FunctionCall"
}

Well, technically, you can write it but it will not work as expected in the following case:

fun callStringify(exp: Exp) {
    // This will always call the original extension
    exp.stringify()
}

The reason is that extension functions in Kotlin are dispatched statically. In Closure solution, the method is dispatched dynamically even though it’s declared outside of the record/class body (like Kotlin extensions).

[Rohan Maity]

Yes, you are right. Extension function just flipped the matrix of expression problem.
I did not think it through after adding operation, what would happen if I happen to add one more type.

Now I think, kotlin with the help of extension functions can give you the flexibility on which side of matrix you would wanna be.

If you codebase is more on adding type side, stay object oriented and if it is on the adding tool or operation side, use extension functions

WDYT?

[Rohan Maity]

The reason extension functions in kotlin are dispatched statically but in clojure, they are dispatched dynamically

Can you shed more light on this? How does the static vs dynamic affects the solution of expression problem

IMO, compiler can still identify statically as well.

[Filip Dolník]

Dynamic dispatch means that the decision about which function is called is made at runtime based on the actual receiver type (because of that you can override methods). In this case, the compiler knows only a subset of methods from which exactly one will be called.

Whereas in the case of static dispatch the exact function is predetermined at the compile time based on the inferred type of the receiver.

Extension-like functions that would support dynamic dispatch solve the issue because you would be able to write this:

dynamic fun Constant.stringify(): String = value.toString()

dynamic fun BinaryPlus.stringify(): String = "${lhs.stringify()} + ${rhs.stringify()}"

...

Notice that the when expression is no longer there (and therefore you don’t have to modify it when adding new types). But in reality, the when expression is still there. It’s just performed at runtime by the dynamic dispatch.

[Rohan Maity]

Oh, ok. This clarifies the dynamic dispatch part. Even though compiler would be able to collect the information about different extension functions on different subtypes of Exp interface, but it would be at runtime only that actual or correct extension function would be selected

[Rohan Maity]

I did not think it through after adding operation, what would happen if I happen to add one more type.

Now I think, kotlin with the help of extension functions can give you the flexibility on which side of matrix you would wanna be.

If you codebase is more on adding type side, stay object oriented and if it is on the adding tool or operation side, use extension functions

Any comments on this?

[Dan Fingal-Surma]

The C++ in the blog post very strongly reminds me of the ZetaSQL (GoogleSQL) Resolved AST which I've worked with professionally. The way it solves the "new type" problem without dynamic casting is that Visitor has a DefaultVisit method that is the default impl of all specific Visit methods. Additionally, every Node has a ChildrenAccept method which calls accept on ever child node in order. So you can configure your visitor with what to do with a node it doesn't understand, and you have the ability to skip it and visit its children it makes sense for your use case. By default it will just return an error.

[Dan Fingal-Surma]

However, you still how to modify existing visitor classes to enable them to support new node types. You just don't have to do it in one CL.

[Dan Fingal-Surma]

Extension functions don't help at all IMO, because dynamic dispatch is a key requirement (esp for something like an AST), and there's no interface or protocol like thing that lets you accept "any object you can call foo() via an extension fn on"

[Rohan Maity]

Hmm, the more I read think about it, the more I understand that how dynamic dispatch is the key here.
I can only flip the matrix at Max with Extension function