Using persistent environment in the Java interpreters

[saidooubella]

In your book you have mentioned that we can fix the environment issues by making it persistent. I tried to implement it on my own but i failed to do so. Can anyone please show me an example of how can I implement it.

[saidooubella]

Never mind! I figured out how to do it 😅.

[raghavio]

@saidooubella I'm kind of struggling with this. Do you have any inptus?

[saidooubella]

Hello @raghavio!

The following code snippet is in Kotlin.

sealed interface Value

data class IntValue(val value: Int) : Value

// This declaration would match a named function.
// For example in Kotlin this would be:
//  > fun f() {
//  >     println("Hello")
//  > }
data class FunValue(val name: String, val env: Env?, val block: (Env?) -> Unit) : Value {
    // I added `this` function to its environment to be able to reference itself.
    // for example in the case of recursion.
    fun execute() = block(env.with(name, this))
    override fun toString(): String = "FunValue(name=$name)"
}

// This declaration would match an `unnamed function`,`function expression`,
// `lambda function` or `anonymous function`.
// For example in Kotlin this would be:
//  > val x = { println("Hello") }
// Anonymous function can't reference themselves.
data class AnonymousFunValue(val env: Env?, val block: (Env?) -> Unit) : Value {
    fun execute() = block(env)
    override fun toString(): String = "FunValue(name=<anonymous-fn>)"
}

// A linked list of env nodes
data class Env(val name: String, val value: Value, val next: Env? = null) {
    override fun toString(): String = buildString {
        var current: Env? = this@Env
        while (current != null) current.run {
            appendLine("Env(name=${name}, value=$value)")
            current = next
        }
    }
}

// A convenient function to add FunValue avoiding name duplication
fun Env?.with(name: String, block: (Env?) -> Unit): Env = with(name, FunValue(name, this, block))

fun Env?.with(name: String, value: Value): Env = Env(name, value, this)

// tail-recursion optimized lookup for the nearest value named `name`
tailrec operator fun Env?.get(name: String): Value? = when {
    this == null -> null
    this.name == name -> value
    else -> next[name]
}

// Why you might ask? I hate writing (obj as Type).call().
// I prefer chaining :)
inline fun <reified T> Any?.cast(): T = this as T

fun main() {

    var env: Env? = Env("x", IntValue(2))
    env = env.with("f") { println(it) }
    env = env.with("g") { println(it) }

    env["f"].cast<FunValue>().execute()
    // ^ this would print:
    //     Env(name=f, value=FunValue(name=f))
    //     Env(name=x, value=IntValue(value=2))

    env["g"].cast<FunValue>().execute()
    // ^ this would print:
    //     Env(name=g, value=FunValue(name=g))
    //     Env(name=f, value=FunValue(name=f))
    //     Env(name=x, value=IntValue(value=2))
}

[raghavio]

Thanks for the explaination, @saidooubella. I don't understand it very well, but I did figure the solution on my own. My implementation is in Clojure, I was using persistent data structures in purily immutable way for my env to begin with, however implementing closures was getting very tricky. The approach I ended up with was using PDS but my env values are now references instead of immutable values. This way, I'm able to do snapshot envs and also let it reflect any reassignments to all snapshots.

How are you tackling this code snippet though:

fun isEven(n) {
  if (n == 0) return true;
  return isOdd(n - 1);
}

fun isOdd(n) {
  if (n == 0) return false;
  return isEven(n - 1);
}

print isEven(4); // expect: true
print isOdd(3); // expect: true

I've decided not to bother with this. If you do want to use a function that isn't defined yet, languages have a support of declaring an empty name first. That's how it happens in clojure as well.

[saidooubella]

Sorry @raghavio for replying so late. I had to do some research first.

Going purely immutable and doing this is impossible (according to my personal knowledge... I might be wrong) as the two functions need to know about each other. By the time isEven captures its environment it will not know about the existence of isOdd. Javascript for example defines the closed over variables first as undefined and then when the variables are defined their changes reflect in the closure scopes of the function.

As for the toy language I was working on, it did have an entry function (i.e. main function) so I treat top level declarations quite differently from local declarations. I define the top level declarations at once, and because they are global they have access to the global scope which contains the references to all top-level declarations. Therefor I didn't use a PDS for this matter you can check my implementation with top-level declarations in Java or this with support for top level statements in Kotlin.