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)) # | # # | # # | # # | # # | # # | # # | # # | # # | # # | # # | # # | # # | # # | # # | # 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 :)