call-with-current-continuation / letcc

turanct commented 8 years ago

I tried to implement a call-with-current-continuation function, that would allow us to do some "early returns" in recursive functions. It works fantastically, and i can now write functions in continuation passing style, which opens up a whole new dimention to functional programming.

The only problem i have with this, is the way of implementing it. I implemented it using a throw/catch scheme in php, which is of course completely hidden behind function calls. What are your opinions?

function let_cc($f)
{
    return function(...$params) use ($f) {
        $continuation = function($v) {
            throw new Continuation($v);
        };

        try {
            $result = call($f, cons($continuation), al($params)));
        } catch(Continuation $c) {
            $result = $c->getContinuation();
        }

        return $result;
    };
}

final class Continuation extends Exception {
    private $continuation;

    public function __construct($continuation)
    {
        $this->continuation = $continuation;
        parent::__construct('Continuation');
    }

    public function getContinuation()
    {
        return $this->continuation;
    }
}

An example of using it in a function:

// Get a list of numbers that appear after te last 1
function after_1($l)
{
    // We can break out of this whole let_cc() block by calling the $skip function,
    // that let_cc injects in our function.
    $after_1_ = let_cc(function($skip, $l) {
        $after_1__ = function($l) use ($skip, &$after_1__) {
            if (isempty($l)) {
                return l();
            }
            elseif (head($l) == 1) {
                // using the $skip function we can "forget" everything we already cons'ed
                // in previous recursions
                return $skip($after_1__($l));
            } else {
                return cons($first, $after_1__($l));
            }
        };

        return $after_1__($l);
    });

    return $after_1_($l);
}

$foo = after_1(l(1, 2, 3, 1, 4, 5)); // l(4, 5)
$bar = after_1(l(1, 2, 3, 4, 5)); // l(2, 3, 4, 5)
$baz = after_1(l(2, 3, 4, 5)); // l(2, 3, 4, 5)

mathiasverraes commented 8 years ago

How is it done in lisp?

turanct commented 8 years ago

@mathiasverraes From what i can see in Guile & Chicken Scheme, it's mostly language constructs or macro's. The compiler makes it happen.

Here are some more interesting pointers:

mathiasverraes / lambdalicious

call-with-current-continuation / letcc #40