Adventures in Scheme
--------------------
Tue Nov  1 10:16:01 PM EDT 2022

A theme in my programming career has been a fixation on
exploring the mysterious, challenging, and powerful
corners of the craft.

It was the promise of speed that led me to Vim.

It was the allure of simplicity that led me to Plan 9.

And it's the stories of power that led me to LISP.

I'm being a bit dramatic, but it's true. I'm highly
susceptible to evangelist writings and deep rabbit holes.

LISP, and more specifically Scheme, has been on my radar for
a while now. I think my first encounter was probably through
Emacs--what was this builtin configuration language people
raved about? Later I started reading about LISP in general
through Hackernews and other forums.

In the past couple months, I finally got an excuse to do
some serious coding in it: implementing the interpreter from
"Crafting Interpreters" (Nystrom, 2021) as part of a book
club. I'm by no means an expert, but I've been enjoying it
enough I thought it deserved a phlog post!

It's kinda funny writing a post in 2022 in praise of Scheme.
It definitely is still praise-worthy, but I think a lot of
the things it excelled at (first class functions, tail
call optimization, even *lexical scope* with early lisps
using dynamic scope) are now common place in more popular
languages.

So in a way, it's a huge testament to the language that
there's anything left that it excels at that others don't do
better almost 50 years later.

I can't claim to be an expert yet, but I do see glimpses of
the "power". It took me hours of reading to wrap my head
around call/cc (continuations) and how they can be used for
things like coroutines. And I still have yet to write my
first macro (but I understand now how powerful it is to have
the source code of the language be data in the language
itself--macros can access and manipulate the input source
using primitive functions like map, car, cdr, etc).

I can report that things like dealing with the parenthesis
and infix notation becomes second nature pretty quickly (and
now I kinda like it!)

It's been a fun adventure so far, and I'll try to keep it
going a bit longer (at least to write some macros). If
there's one thing I've found in any of my explorations in
search of mysterious programming tools and languages, it's
that I always emerge with a newfound excitement to come into
work and a better perspective on problem solving.

-- Bonus Puzzle! --

I'll end with a continuation puzzle for you. To be honest, I
didn't fully grok it until I made the chart at the end, so
it's just as much for me! :)

Here's the code and the output:

(let* ((yin ((lambda (cc) (newline) (display #\@) cc) (call/cc (lambda (c) c))))
      (yang ((lambda (cc) (display #\*) cc) (call/cc (lambda (c) c)))))
   (yin yang))

@*
@**
@***
@****
@*****
@******
@*******
@********
@*********
..

But before we dive in, let's look at the strange oddity that
is call/cc (call-with-current-continuation). call/cc is a
function that calls another function with the current
continuation (as the name implies). The current continuation
itself is a function that, when invoked, returns from
call/cc with the value it was invoked with. In its simplest
form this can be used to abort a function:

(display (call/cc (lambda (cc)
                   (cc "hello world")
                   "not reached")))

Will print "hello world" since invoking cc will force the
return from call/cc early before it can return "not
reached".

OK this is fine. Languages have 'return' statements. We've
all been here. Ahhh but what if we _returned_ the
continuation? In scheme continuations are first class and
can be stored in variables--they can persist beyond the
block they were defined in. THIS is where it gets
interesting:

(define cc #f)
(display
 (+ 1
    (call/cc (lambda (c)
               (set! cc c)
               1))))
2

(cc 5)
6

In this example, we add 1 to the result of call/cc, which,
the first go around is just 1 (that's what the lambda
returns--we don't abort, just save it off into the cc
variable for later).

If we invoke it again, we *return to that point in the
code* even though it's been interpreted already. call/cc
returns 5 (since that's what we invoke cc with) and we print
6.

OK final twist--this just feels like a goto... but we can
also show that we package up the state of the callstack:

(define cc #f)

(define (prlist lst)
 (if (not (null? lst))
     (begin (display (car lst))
            (newline)
            (if (eq? (car lst) 'b)
              (call/cc (lambda (c) (set! cc c))))
            (prlist (cdr lst)))))

(prlist '(a b c))
(cc 0)

In this case, we have a simple recursive prlist that prints
each element until it reaches a null list. At element 'b, it
saves its continuation into cc. Calling cc later picks up
the loop from that point (printing c a second time):

a
b
c
c

Point being: the state of lst is captured in the
continuation!

So back to our example (without the newline):

1 | (let* ((yin ((lambda (cc)  (display #\@) cc) (call/cc (lambda (c) c))))
2 |        (yang ((lambda (cc) (display #\*) cc) (call/cc (lambda (c) c)))))
3 |    (yin yang))

Lets walk line by line, writing down the line just read, the
output, the name of the continuation (with ' to indicate a
return) and the state of each variable:

cc-id   | Line | Yin   | Yang  | Out
----------------------------------------
yin1    | 1    | yin1  | nil   | @
yang1   | 2    | yin1  | yang1 | @*

-->  L3: call yin1 on yang1 (jump back to L1 and
-->  return yang1 from call/cc, storing it in yin)

yin1'  | 1     | yang1 | nil   | @*@
yang2  | 2     | yang1 | yang2 | @*@*

-->  call yang1 on yang2 (jump back to L2 and
-->  return yang2. but NOTE yin has also gone
-->  back to its old value at the time yang1
-->  was crafted!)

yang1' | 2     | yin1  | yang2 | @*@**

--> call yin1 on yang2

yin1'  | 1     | yang2 | nil   | @*@**@
yang3  | 2     | yang2 | yang3 | @*@**@*

--> call yang2 on yang3

yang2' | 2     | yang1 | yang3 | @*@**@**

--> call yang1 on yang3

yang1' | 2     | yin1  | yang3 | @*@**@***

--> call yin1 on yang3

yin1'  | 1     | yang3 | nil   | @*@**@***@
yang4  | 2     | yang3 | yang4 | @*@**@***@*
yang3' | 2     | yang2 | yang4 | @*@**@***@**
yang2' | 2     | yang1 | yang4 | @*@**@***@***
yang1' | 2     | yin1  | yang4 | @*@**@***@****
yin1'  | 1     | yang4 | yang5 | @*@**@***@****@

And so on... because the continuation for yang encloses the
value of yin at the creation time, whenever we invoke yangN
on yangK, we print a * and invoke yangN-1 on yangK until
yang1 at which point yin goes back to yin1 and we print a
new @ and create a new yangN+1. yin is then yangN and the
cycle continues.

Wow, right?

This is also shown by looking at the following output of the
pointers for each variable (using CHICKEN Scheme):


(import (chicken memory) (chicken format))

(let* ((yin  ((lambda (cc)
               (newline) cc)
             (call/cc (lambda (c) c))))
      (yang ((lambda (cc) cc)
             (call/cc (lambda (c) c)))))
   (display (format "~A | ~A\n" (object->pointer yin) (object->pointer yang)))
   (yin yang))

#<pointer 0x7ffc780c6bb0> | #<pointer 0x7ffc780c1850>

#<pointer 0x7ffc780c1850> | #<pointer 0x7ffc780b6cc0>
#<pointer 0x7ffc780c6bb0> | #<pointer 0x7ffc780b6cc0>

#<pointer 0x7ffc780b6cc0> | #<pointer 0x7ffc780a6900>
#<pointer 0x7ffc780c1850> | #<pointer 0x7ffc780a6900>
#<pointer 0x7ffc780c6bb0> | #<pointer 0x7ffc780a6900>

#<pointer 0x7ffc780a6900> | #<pointer 0x7ffc78090d10>
#<pointer 0x7ffc780b6cc0> | #<pointer 0x7ffc78090d10>
#<pointer 0x7ffc780c1850> | #<pointer 0x7ffc78090d10>
#<pointer 0x7ffc780c6bb0> | #<pointer 0x7ffc78090d10>

#<pointer 0x7ffc78090d10> | #<pointer 0x7ffc780758f0>
#<pointer 0x7ffc780a6900> | #<pointer 0x7ffc780758f0>
#<pointer 0x7ffc780b6cc0> | #<pointer 0x7ffc780758f0>
#<pointer 0x7ffc780c1850> | #<pointer 0x7ffc780758f0>
#<pointer 0x7ffc780c6bb0> | #<pointer 0x7ffc780758f0>


Notice that we always get down to bb0 in yin and then start
over!

As a final note, I got super confused in the middle of
writing this because of this example:


(define cc #f)

(let ((state "foo"))
 (display
   (+ 1
      (call/cc (lambda (c)
                 (set! cc c)
                 1))))
 (newline)
 (display state)
 (set! state "bar")
 (newline))

(cc 5)


I thought surely that this would print:

2
foo
6
foo

Since the closure captured the value of "state" as "foo" at
the time. But instead it prints "bar". What gives??

My best guess here is that set! _modifies_ the continuation
environment in-place. In the yin-yang puzzle, each (let)
creates its own environment, so we end up with the
returning-to-old-values behavior, but when we use set! it
modifies the environment from underneath the continuation.

I'll do more research when it's not past midnight :)

You are viewing proxied material from alexkarle.com. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.