Guess the language by the error

[sassa_nf]

Vlad found a good bug in SICP-JS: https://juan-gandhi.dreamwidth.org/4681686.html?thread=126995414#cmt126995414.

So, I went ahead and implemented both merge and mul_merge versions in JS. My versions looked drastically different:

$ time node a.js // using merge, take 40
real	0m4.581s
user	0m4.332s
sys	0m0.386s

$ time node b.js // using mul_merge, take 40
real	0m0.261s
user	0m0.245s
sys	0m0.034s

I thought maybe my implementation of streams is dumb.
But no, their playground is of the same opinion: take 200

Line 189: Potential infinite recursion detected: pair(3600, [ 3645,
[ 3750,
...
[14400, [14580, [15000, [15360, [15552, [15625, [16000, [16200, null]]]]]]]] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ]).
      If you are certain your program is correct, press run again without editing your program.
      The time limit will be increased from 1 to 10 seconds.
      This page may be unresponsive for up to 10 seconds if you do so.

mul_merge isn't problematic. But I thought it actually might be a problem, because it creates new streams for every x in xs.

For the curious: paste here: https://sourceacademy.nus.edu.sg/playground

function stream_tail(stream) {
    return tail(stream)();
}
function merge(s1, s2) {
    if (is_null(s1)) {
        return s2;
    } else if (is_null(s2)) {
        return s1;
    } else {
        const s1head = head(s1);
        const s2head = head(s2);
        if (s1head < s2head) {
            return pair(s1head,
                        () => merge(stream_tail(s1), s2)
                       );
        } else if (s1head > s2head) {
            return pair(s2head,
                        () => merge(s1, stream_tail(s2))
                       );
        } else {
            return pair(s1head, () => merge(stream_tail(s1), stream_tail(s2)));
        }
    }
}

const S = pair(1, () => merge(stream_map(x => x * 2, S), merge(stream_map(x => x * 3, S), stream_map(x => x * 5, S))));

function stream_take(n, s) {
    if (n > 0 && !is_null(s)) {
        return pair(head(s), () => stream_take(n-1, tail(s)()));
    } else {
        return stream();
    }
}

function mul_merge(xs, ys) {
    const x = head(xs);
    const y = head(ys);
    return pair(x * y, () => merge(stream_map(y => x*y, stream_tail(ys)), mul_merge(stream_tail(xs), ys)));
}

function pows(x) {
    const v = pair(x, () => stream_map(y => x*y, v));
    return pair(1, () => v);
}

const S2 = mul_merge(pows(2), mul_merge(pows(3), pows(5)));
stream_to_list(stream_take(200, S));

I think what really is going on, is they (and I) do not memoize. Without memoization S gets recomputed tons of times (12337556 multiplications for just 40 elements in my version of streams), and the pows doesn't (888803 multiplications for 40 elements in my version of streams).

But, say, ghci timings are totally the opposite: merge version is way faster than mul_merge version.