LIPS Scheme 1.0.0-beta.22 with Continuations and TCO | LIPS Scheme

Skip to main content<br>I'm excited to introduce a new beta version of LIPS Scheme. The most important features of this<br>version are full continuations and TCO (Tail Call<br>Optimization). They were inspired by<br>JS-Scheme by Alex Yakovlev.

Continuations​

You can now finally play with continuations. Here is a simple<br>example of an early exit from a recursive named let.

(define (find fn lst)<br>(call/cc (lambda (return)<br>(let loop ((lst lst))<br>(if (null? lst)<br>(return #f)<br>(if (fn (car lst))<br>(return lst)<br>(loop (cdr lst))))))))

(find (lambda (x)<br>(print x)<br>(zero? x))<br>'(2 1 0 1 2 3 4 5 6 7))<br>;; ==> 2<br>;; ==> 1<br>;; ==> 0<br>;; ==> (0 1 2 3 4 5 6 7)

JavaScript Generators​

Finally, LIPS has native JavaScript generators. If you're not familiar with generators, they are like a<br>function that can yield a value, which suspends the execution and then resumes it later.

function* integers(n) {<br>let i = 0;<br>while (i n) {<br>yield i++;

for (const i of integers(10)) {<br>console.log(i);

// ==> 0<br>// ==> 1<br>// ==> 2<br>// ==> 3<br>// ==> 4<br>// ==> 5<br>// ==> 6<br>// ==> 7<br>// ==> 8<br>// ==> 9

Now, thanks to continuations, the same thing can be done in LIPS Scheme.

(define (integers x)<br>(generator (lambda (yield)<br>(let loop ((i 0))<br>(if ( i x)<br>(begin<br>(yield i)<br>(loop (+ i 1))))))))

(Array.from (integers 10))<br>;; ==> #(0 1 2 3 4 5 6 7 8 9)

You can also use the generator with the do-iterator macro:

(do-iterator<br>(i (integers 10000))<br>((= i 10) #void)<br>(print i))<br>;; ==> 0<br>;; ==> 1<br>;; ==> 2<br>;; ==> 3<br>;; ==> 4<br>;; ==> 5<br>;; ==> 6<br>;; ==> 7<br>;; ==> 8<br>;; ==> 9

You can also define an async generator:

(define (title url)<br>(let ((re #/([^>]+)/))<br>(--> (fetch url)<br>(text)<br>(match re)<br>1)))

(define (titles urls)<br>(async-generator (lambda (yield)<br>(let loop ((urls urls))<br>(if (not (null? urls))<br>(let ((url (car urls)))<br>(yield (title url))<br>(loop (cdr urls))))))))

(define urls '("https://scheme.org.pl/test/"<br>"https://terminal.jcubic.pl/"))

(write (Array.fromAsync (titles urls)))<br>;; ==> #("Scheme Programming Language"<br>;; ==> "jQuery Terminal: JavaScript Web Based Terminal Emulator")

The JavaScript generators are a syntax sugar for the<br>JavaScript iterator protocol

The implementation of generator use that protocol, the missing piece to be able to create a generator in LIPS<br>were continuations.

This is the source code that was based for the generator:

(define (generator proc)<br>"(generator function)

Higher order function that accepts a function with a single argument<br>(usually yield). Function returns JavaScript async generator that<br>produce values for each call to yield."<br>(define void (if #f #f))<br>(define return #f)<br>(define resume #f)<br>(define (yield v)<br>(call/cc (lambda (r)<br>(set! resume r)<br>(return v))))<br>(define (next)<br>(let ((value (call/cc<br>(lambda (cc)<br>(set! return cc)<br>(if resume<br>(resume void)<br>(begin<br>(proc yield)<br>(set! resume<br>(lambda (v)<br>(return (eof-object))))<br>(return (eof-object))))))))<br>`&(:value ,value :done ,(eof-object? value))))

(let* ((iterator `((next . ,next)<br>(,Symbol.iterator . ,(lambda () this)))))<br>(alist->object iterator)))

The implementation was inspired by<br>srfi-158 implementation of make-coroutine-generator.

The iterator in JavaScript is an object that has a next property that is a function that returns objects in a format:

"value": /* return value */,<br>"done": /* boolean indicator if the iteration ended */

There are two types of iterators: the normal iterator that has a Symbol.iterator property that<br>holds a function, which returns the iterator. Or async iterator with Symbol.asyncIterator that has<br>the same function. The function async-generator uses<br>Symbol.asyncIterator instead of Symbol.iterator.

The difference is that the next function in the async iterator can return a Promise.

For working with an iterator, there is also the iterator->array<br>function. Both macro do-iterator and function are iterator agnostic and<br>accept both iterators.

Tail Call Optimizations​

This is another feature implemented together with continuations<br>inspired by JS-Scheme. You can now use recursion that doesn't<br>consume the stack. There are still some memory increases, but the memory-allocated objects are<br>garbage collected during the long loop.

Here is an example that you can test:

(define (sum n)<br>(let loop ((n n) (acc 0))<br>(if ( n 0)<br>acc<br>(loop (- n 1) (+ acc n)))))

(sum 100000)<br>;; ==> 5000050000

"Stack" Trace​

You can create a 'stack' trace out of continuations:

(trace #t)

(let ((x 10))<br>(let ((y 20))<br>(stack-trace (call/cc (lambda (cc) cc)))))

;; ==> [0]: (let ((x 10)) (let ((y 20)) (stack-trace (call/cc (lambda (cc) cc)))))<br>;; ==> [1]: (let ((y 20)) (stack-trace (call/cc (lambda (cc) cc))))<br>;; ==> [2]: (stack-trace (call/cc (lambda (cc) cc)))<br>;; ==> [3]: (call/cc (lambda (cc) cc))<br>;; ==> [4]: (lambda (cc) cc)

(trace #f)

You can also directly inspect the continuations and extract meta information:

(trace #t)

(define cc (let ((x 10))<br>(let ((y 20))<br>(call/cc (lambda (cc) cc)))))

(define trace (cc.trace (lambda (cc i)<br>(let...