Functional Pearl: Implementing Tracing in JavaScript

Question

Ross Paterson: Arrows and Computation presents trace(on page 11):

trace :: ((a, c) -> (b, c)) -> a -> b
trace f a = let (b, c) = f (a, c) in b

The function traceis useful for modulating the magic feedback step in circular programs . For example, consider a well-known function that finds the minimum value of a leaf of a tree and creates an identical tree, each value of the leaves is replaced by the minimum value of the leaf in one pass by cleverly using lazy estimation and local recursion (as provided ): repminletrec

data Tree = Leaf Int | Node Tree Tree deriving Show

repmin :: Tree -> Tree
repmin = trace repmin'

repmin' :: (Tree, Int) -> (Tree, Int)
-- put the minimum value m into the leaf and return the old value n as the minimum
repmin' (Leaf n, m) = (Leaf m, n)
-- copy the minimum value m into both the left and right subtrees and
-- set the minimum value m to the minimum of both the left and right subtrees
repmin' (Node l r, m) = let (l', lmin) = repmin' l m in
                        let (r', rmin) = repmin' r m in
                        (Node l' r', lmin `min` rmin)

In any case, I was wondering how to implement the function tracein JavaScript, so that we can implement it repminas follows:

function Leaf(value) {
    this.value = value;
}

function Node(left, right) {
    this.left  = left;
    this.right = right;
}

var repmin = trace(function repmin(tree, min) {
    switch (tree.constructor) {
    case Leaf:
        return [new Leaf(min), tree.value];
    case Node:
        var [left,  lmin] = repmin(tree.left,  min);
        var [right, rmin] = repmin(tree.right, min);
        return [new Node(left, right), Math.min(lmin, rmin)];
    }
});

trace , letrec, - :

function trace(f) {
    return function (a) {
        var [b, c] = f(a, c);
        return b;
    };
}

, c . trace. , trace JavaScript ?

Answer 1

, , JavaScript letrec. thunks. , trace :

function trace(f) {
    return function (a) {
        var [b, c] = f(a, () => c);
        return b;
    };
}

trace, repmin :

var repmin = trace(function repmin(tree, min) {
    switch (tree.constructor) {
    case Leaf:
        return [new Leaf(min), tree.value];
    case Node:
        var [left,  lmin] = repmin(tree.left,  min);
        var [right, rmin] = repmin(tree.right, min);
        return [new Node(left, right), Math.min(lmin, rmin)];
    }
});

, getters:

function Leaf(value) {
    Object.defineProperty(this, "value", descOf(value));
}

function Node(left, right) {
    Object.defineProperty(this, "left",  descOf(left));
    Object.defineProperty(this, "right", descOf(right));
}

function descOf(value) {
    var desc = { enumerable: true };
    var prop = typeof value === "function" &&
        value.length === 0 ? "get" : "value";
    desc[prop] = value;
    return desc;
}

:

var tree = new Node(new Node(new Leaf(1), new Leaf(2)),
                    new Node(new Leaf(3), new Leaf(4)));

console.log("Input: ", show(tree));

console.log("Output:", show(repmin(tree)));

function show(tree) {
    switch (tree.constructor) {
    case Leaf: return "Leaf(" + tree.value + ")";
    case Node: return "Node(" + show(tree.left) + ", " + show(tree.right) + ")";
    }
}

<script>
function trace(f) {
    return function (a) {
        var [b, c] = f(a, () => c);
        return b;
    };
}

var repmin = trace(function repmin(tree, min) {
    switch (tree.constructor) {
    case Leaf:
        return [new Leaf(min), tree.value];
    case Node:
        var [left,  lmin] = repmin(tree.left,  min);
        var [right, rmin] = repmin(tree.right, min);
        return [new Node(left, right), Math.min(lmin, rmin)];
    }
});

function Leaf(value) {
    Object.defineProperty(this, "value", descOf(value));
}

function Node(left, right) {
    Object.defineProperty(this, "left",  descOf(left));
    Object.defineProperty(this, "right", descOf(right));
}

function descOf(value) {
    var desc = { enumerable: true };
    var prop = typeof value === "function" &&
        value.length === 0 ? "get" : "value";
    desc[prop] = value;
    return desc;
}
</script>

Hide result

, , :

var sqr = trace((x, y) => [y * y, x]);

, * . , mul:

var sqr = trace((x, y) => [mul(y, y), x]);

console.log(evaluate(sqr(10)));

function mul(a, b) {
    return function () {
        return evaluate(a) * evaluate(b);
    };
}

function evaluate(value) {
    return typeof value === "function" &&
        value.length === 0 ? value() : value;
}

function trace(f) {
    return function (a) {
        var [b, c] = f(a, () => c);
        return b;
    };
}

Hide result

, .