Koka generates wrong code (possible a ctail error?)

[anfelor]

Consider the following implementation of weight biased leftist heaps as in section 3.1 of Okasaki (though the details aren't important):

import std/num/int32

alias elem = int

public type heap {
    E
    T(i : int32, e : elem, l : heap, r : heap)
}

public fun show-heap(h : heap) {
    match(h) {
        E -> "E"
        T(i, e, l, r) {
            "T(" ++ show(i.int) ++ ".int32, " ++ show(e) ++ ", " ++ show-heap(l) ++ ", " ++ show-heap(r) ++ ")"
        }
    }
}

public fun rank(h) {
    match(h) {
        E -> 0.int32
        T(r, _, _, _) -> r
    }
}

public fun broken-merge(h1, h2) {
    match(h1, h2) {
        (h, E) -> h
        (E, h) -> h
        (T(r1, x, a1, b1), T(r2, y, a2, b2)) {
            if(x < y) {
                if(rank(a1) < rank(b1) + r2)
                then T(r1 + r2, x, broken-merge(b1, h2), a1)
                else T(r1 + r2, x, a1, broken-merge(b1, h2))
            } else {
                if(rank(a2) < rank(b2) + r1)
                then T(r1 + r2, y, broken-merge(b2, h1), a2)
                else T(r1 + r2, y, a2, broken-merge(b2, h1))
            }
        }
    }
}

public fun merge(h1, h2) {
    match(h1, h2) {
        (h, E) -> h
        (E, h) -> h
        (T(r1, x, a1, b1), T(r2, y, a2, b2)) {
            if(x < y) {
                if(rank(a1) < rank(b1) + r2)
                then T(r1 + r2, x, merge(b1, T(r2, y, a2, b2)), a1)
                else T(r1 + r2, x, a1, merge(b1, T(r2, y, a2, b2)))
            } else {
                if(rank(a2) < rank(b2) + r1)
                then T(r1 + r2, y, merge(b2, T(r1, x, a1, b1)), a2)
                else T(r1 + r2, y, a2, merge(b2, T(r1, x, a1, b1)))
            }
        }
    }
}

public val a = T(1.int32, 3, E, E)
public val b = T(2.int32, 1, T(1.int32, 2, E, E), E)

As you can see, merge and broken-merge are nearly identical; except that in merge we have inlined h1 and h2 after the match. But their output is different:

> show-heap(merge(a, b)) 
"T(3.int32, 1, T(1.int32, 2, E, E), T(1.int32, 3, E, E))"

> show-heap(broken-merge(a, b))
"T(3.int32, 1, T(1.int32, 2, E, E), E)"

Koka v2.1.9, clang 12.0.5, macOS Big Sur on an M1 processor

[TimWhiting]

This seems to be fixed on the latest dev branch, maybe even the latest release?

[anfelor]

Yes, I can confirm that this is fixed now. From bisecting, it appears that this was fixed in b6067e75235bd5e6625ce4d0288134f5efc3280c when Daan re-discovered this issue in the code we were working on back then.