Capturing abstractions in Lisp

I was skimming through SICP (after a pause) and I came across the chapter where Streams are discussed.

For those that have experience with JS Promises, Streams can be thought of as Promises. They allow us to make an illusion of infinity, e.g. all positive integers, by deferring evaluation.

For example, to generate all positive integers, we make a pair (1, next_int(1)), and then to evaluate the second member of that pair is (2, next_int(2)) and so on, for the nth number producing a list (1, (2, (…, (n, next_int(n))))) which will do n evaluations.

Here’s an implementation in Scheme that defines cons-stream (which will allow us to produce promises) and uses that to generate all integers infinitely (but not really, since all it does is just defer evaluation).

; delay needs to be a macro in order for the code to work correctly.
; Otherwise the invocation of delay will evaluate all its arguments eagerly.
(define-syntax delay
  (syntax-rules ()
    ((delay a)
     (lambda () a))))
; (defmacro delay (a) `(lambda () ,a))

; similarly for cons-stream
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
      (cons a (delay b)))))
; (defmacro cons-stream (a b) `(cons ,a (delay ,b)))

; force just evaluates
(define (force a) (a))

(define (next-integer x) (cons-stream x (next-integer (+ x 1))))

(define all-positive-integers (next-integer 0))

(define (integer-ref list i)
  (cond ((= i 0) (car list))
    (else (integer-ref (force (cdr list)) (- i 1)))))

; display 100th number:
(integer-ref all-positive-integers 100)

Looks and works pretty good!

Now, we can try doing the same in JS:

function force(x) {
    return x();
}
function cons_stream(a) {
    return function(b, c) {
        // this is delay basically but we can't abstract it in another method
        // since it will evaluate the params, so we need to use scope
        return function() {
            return [a].concat(b(c));
        }
    }
}

function next_integer(x) {
    return cons_stream(x)(next_integer, x+1);
}

function positive_integers() {
    return next_integer(0);
}

function integer_ref(list, j) {
    var item;

    // evaluate initially
    list = force(list);

    while (j != 0) {
        // get the last item from the list (promise)
        item = list.pop();

        // append it in its evaluated form
        list = list.concat(force(item));

        j--;
    }

    // exclude last item since it's a new promise
    return list[list.length - 2];
}

var all_positive_integers = positive_integers();

// display 100th number:
console.log(integer_ref(all_positive_integers, 100));

The code is a bit longer, but it works equally good.

In JS we can achieve the same effect that the Lisp macro does by using scopes.

But in my opinion, Lisp’s syntax is more powerful with the ability to not evaluate parameters because it allows us to capture abstractions such as delay, whereas in JS we couldn’t do the same.

Advertisements

2 thoughts on “Capturing abstractions in Lisp

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s