The Heart of Spritely: Distributed Objects and Capability Security

Here we will give an extremely brief taste of what programming in Goblins is like. The following code is adapted from the Guile version of Goblins.⁶

First, let us implement a friend who will greet us:

;; define with next argument wrapped in parentheses
;; defines a named function
define (^greeter _bcom our-name)   ; constructor (outer procedure)
  lambda (your-name)               ; behavior    (inner procedure)
    format #f "Hello ~a, my name is ~a!"     ; returned implicitly
           . your-name our-name

The outer procedure, defined by define, is named ^greeter, which is its constructor.⁷ The inner procedure, defined by the lambda (an "anonymous function"), is its behavior procedure, which implicitly returns a formatted string. Both of these are most easily understood by usage, so let's try instantiating one:⁸

;; define with next argument *not* in parentheses
;; defines an ordinary variable
REPL> define gary
_____   spawn ^greeter "Gary"

As we can see, spawn's first argument is the constructor for the Goblins object which will be spawned. For now, we'll ignore the _bcom, which is not used in this first example (an underscore prefix is the conventional way to note an unused variable; we'll see some examples where this is used soon). The rest of the arguments to spawn are passed in as the rest of the arguments to the constructor. So in our case, "Gary" is passed as the value of our-name.

The constructor returns the procedure representing its current behavior. In this case, that behavior is a simple anonymous lambda. We can now invoke our gary friend using the synchronous call-return $ operator:

REPL> $ gary "Alice"
;; => "Hello Alice, my name is Gary!"

As we can see, "Alice" is passed as the value for your-name to the inner lambda behavior-procedure. Since our-name was already bound through the outer constructor procedure, the inner behavior is able to pass both of these names to format to give a friendly greeting.

Let's introduce a simple cell which stores a value. This cell will have two methods: 'get retrieves the current value, and 'set replaces the current value with a new value.

define (^cell bcom val)
  methods            ; syntax for first-argument-symbol-based dispatch
    (get)            ; takes no arguments
      . val          ; returns current value
    (set new-val)    ; takes one argument, new-val
      bcom : ^cell bcom new-val  ; become a cell with the new value

Let's try it. Cells hold values, and so do treasure chests, so let's make a treasure chest flavored cell. Taking things out and putting them back in is easy.

REPL> define chest
_____   spawn ^cell "sword"
REPL> $ chest 'get
;; => "sword"
REPL> $ chest 'set "gold"
REPL> $ chest 'get
;; => "gold" 

Now we can see what bcom is: a capability specific to this object instance which allows it to change its behavior! (For this reason, bcom is pronounced "become"!)

methods was also new to this version. It turns out that methods is simply syntax sugar, a macro which returns a procedure which supports symbol dispatch on its first argument. There is nothing special about methods: you could easily write your own version or use it outside of Goblins objects to build general symbol-based-method-dispatch.

Objects can also contain and define other object references, including in their outer constructor procedure.

Here is the definition of a "counting greeter" we call ^cgreeter:

define (^cgreeter _bcom our-name)
  define times-called   ; keeps track of how many times 'greet called
    spawn ^cell 0      ; starts count at 0 
  methods
    (get-times-called)
      $ times-called 'get
    (greet your-name)
      define current-times-called
        $ times-called 'get
      ;; increase the number of times called
      $ times-called 'set
        + 1 current-times-called
      format #f "[~a] Hello ~a, my name is ~a!"
             $ times-called 'get
             . your-name our-name

As we can see near the top, times-called is instantiated as an ^cell like the one we defined earlier. The current value of this cell is returned by get-times-called and is updated every time the greet method is called:

REPL> define julius
_____   spawn ^cgreeter "Julius"
REPL> $ julius 'get-times-called
;; => 0
REPL> $ julius 'greet "Gaius"
;; => "[1] Hello Gaius, my name is Julius!"
REPL> $ julius 'greet "Brutus"
;; => "[2] Hello Brutus, my name is Julius!"
REPL> $ julius 'get-times-called
;; => 2

We have shown that the behavior of objects may be invoked synchronously with $. However, this only works if two objects are both defined on the same machine on the network and the same event loop within that machine. Since Goblins is designed to allow for object invocation across a distributed network, what can we do?

This is where <- comes in. In contrast to $, <- can be used against objects which live anywhere, even on remote machines. However, unlike invocation with $, we do not get back an immediate result, we get a promise:

REPL> <- julius 'greet "Lear"
;; => #<promise>

This promise must be listened to. The procedure to listen to promises in Goblins is called on:

REPL> on (<- julius 'greet)
_____   lambda (got-back)
_____     format #t "Heard back: ~a\n"
_____            . got-back
; prints (eventually):
;   Heard back: [4] Hello Lear, my name is Julius!

Not all communication goes as planned, especially in a distributed system. on also supports the keyword arguments of #:catch and #:finally, which both accept a procedure defining handling errors in the former case and code which will run regardless of successful resolution or failure in the latter case:

REPL> define (^broken-bob _bcom)
_____   lambda ()
_____     error "Yikes, I broke!"
REPL> define broken-bob
_____   spawn ^broken-bob
REPL> on (<- broken-bob)
_____    lambda (what-did-bob-say)
_____      format #t "Bob says: ~a\n" what-did-bob-say
_____    #:catch
_____    lambda (err)
_____      format #t "Got an error: ~a\n" err  
_____    #:finally
_____    lambda ()
_____      display "Whew, it's over!\n"  
; prints (eventually):
;   Got an error: <error ...>
;   Whew, it's over!

Mistakes happen, and when they do, we'd like damage to be minimal. But with many moving parts, accomplishing this can be difficult.

However, Goblins makes our life easier. To see how, let's intentionally insert a couple of print debugging lines (with pk, which is pronounced and means "peek") and then an error:

define (^borked-cgreeter _bcom our-name)
  define times-called
    spawn ^cell 0
  methods
    (get-times-called)
      $ times-called 'get
    (greet your-name)
      pk 'before-incr : $ times-called 'get
      ;; increase the number of times called
      $ times-called 'set
        + 1 ($ times-called 'get)
      pk 'after-incr : $ times-called 'get
      error "Yikes"
      format #f "[~a] Hello ~a, my name is ~a!"
             $ times-called 'get
             . your-name our-name

Now let's spawn this friend and invoke it:

REPL> define horatio
_____   spawn ^borked-cgreeter "Horatio"
REPL> $ horatio 'get-times-called
;; => 0
REPL> $ horatio 'greet "Hamlet"
;; pk debug: (before-incr 0)
;; pk debug: (after-incr 1)
;; ice-9/boot-9.scm:1685:16: In procedure raise-exception:
;;   Yikes
;; Entering a new prompt.  Type `,bt' for a backtrace or `,q' to continue.

Whoops! Looks like something went wrong! We can see from the pk debugging that the times-called cell should be incremented to 1. And yet…

REPL> $ horatio 'get-times-called
;; => 0

We will cover this in greater detail later, but the core idea here is that synchronous operations run with $ are all done together as one transaction. If an unhandled error occurs, any state changes resulting from synchronous operations within that transaction will simply not be committed. This is useful, because it means most otherwise difficult cleanup steps are handled automatically.

This also sits at the foundation of Spritely Goblins' time travel debugging features. All of this will be discussed in greater detail in sections later in this document: The vat model of computation, Turns are cheap transactions, and Time-travel distributed debugging.

"Machines grow faster and memories grow larger. But the speed of light is constant and New York is not getting any closer to Tokyo."

— Mark S. Miller, Robust Composition: Towards a Unified Approach to Access Control and Concurrency Control

Promise pipelining provides two different features at once:

• A convenient developer interface for describing a series of asynchronous actions, allowing for invoking the objects which promises will point to before they are even resolved (sometimes before the objects even exist!)
• A network abstraction that eliminates many round trips

Consider the following car factory, which makes cars carrying the company name of the factory:

;; Create a "car factory", which makes cars branded with
;; company-name.
define (^car-factory bcom company-name)
  ;; The constructor for cars we will create.
  define (^car bcom model color)
    methods                      ; methods for the ^car
      (drive)                    ; drive the car
        format #f "*Vroom vroom!*  You drive your ~a ~a ~a!"
               . color company-name model
  ;; methods for the ^car-factory instance
  methods                        ; methods for the ^car-factory
    (make-car model color)       ; create a car
      spawn ^car model color

Here is an instance of this car factory, which we will call fork-motors:

;; Interaction on machine A
REPL> define fork-motors
_____   spawn ^car-factory "Fork"

Since asynchronous message passing with <- works across machines, it does not matter whether interactions with =fork-motors are local or via objects communicating over the network. We will treat fork-motors as living on machine A, and so the following interactions will happen with invocations originating from machine B.

Let's send a message to fork-motors invoking the 'make-car method, receiving back a promise for the car which will be made, which we shall name car-vow (-vow being the conventional suffix given for promises in Goblins):

;; Interaction on machine B, communicating with fork-motors on A
REPL> define car-vow
_____   <- fork-motors 'make-car "Explorist" "blue"

So we have a promise to a future car reference, but not the reference itself. We would like to drive the car as soon as it rolls off the lot of the factory, which of course involves sending a message to the car.

Without promise pipelining, making use of the tools we have already shown (and following the pattern most other distributed programming systems use), we would end up with something like:

;; Interaction on machine B, communicating with A
REPL> on car-vow                  ; B->A: first resolve the car-vow
_____   lambda (our-car)          ; A->B: car-vow resolved as our-car
_____     on (<- our-car 'drive)  ; B->A: now we can message our-car
_____       lambda (val)          ; A->B: result of that message
_____         format #t "Heard: ~a\n" val
; prints (eventually):
;   Heard: *Vroom vroom!*  You drive your blue Fork Explorist!

With promise pipelining, we can simply message the promise of the car directly. The first benefit can be observed from code compactness, in that we do not need to do an on of car-vow to later message our-car, we can simply message car-vow directly:

;; Interaction on machine B, communicating with A
REPL> on (<- car-vow 'drive)     ; B->A: send message to future car
_____   lambda (val)             ; A->B: result of that message
_____     format #t "Heard: ~a\n" val
; prints (eventually):
;   Heard: *Vroom vroom!*  You drive your blue Fork Explorist!

While clearly a considerable programming convenience, the other advantage of promise pipelining is a reduction of round-trips, whether between our event-loop vats or across machines on the network.

This can be understood by looking at the comments to the right of the two above code interactions. The message flow in the first case looks like:

B => A => B => A => B

The message flow in the second case looks like:

B => A => B

In other words, machine B can say to machine A: "Make me a car, and as soon as that car is ready, I want to drive it!"

With this in mind, the promise behind Mark Miller's quote at the beginning of this section is clear.⁹ If two objects are on opposite ends of the planet, round trips are unavoidably expensive. Promise pipelining both allows us to make plans as programmers and allows for Goblins to optimize carrying out those steps as bulk operations over the network.

Thy wee bit heap o' leaves an' stibble,
Has cost thee mony a weary nibble!
Now thou's turn'd out, for a' thy trouble,
But house or hald,
To thole the winter's sleety dribble,
An' cranreuch cauld!

But, Mousie, thou art no thy-lane,
In proving foresight may be vain;
The best-laid schemes o' mice an' men
Gang aft agley,
An' lea'e us nought but grief an' pain,
For promis'd joy!

Still thou art blest, compar'd wi' me
The present only toucheth thee:
But, Och! I backward cast my e'e.
On prospects drear!
An' forward, tho' I canna see,
I guess an' fear!

— From "To a Mouse, on Turning Her Up in Her Nest With the Plough" by Robert Burns, 1785

Unexpected behavior can cause a cascade of failures. In a synchronous call-return system with exceptions, raising an exception causes not only the current procedure invocation to fail, but further invocations up the chain until the exception is caught (and if uncaught, possibly by allowing the program as a whole to fail). While potentially frustrating to encounter as a programmer or user, the alternative of proceeding without mitigating unhandled behavior could be equally disastrous. Still, if we can interpret each procedure as voluntarily "sending a message to its caller" that something has gone awry, we can see the great service that each callee performs for its caller (such a pattern is common when a language does not provide implicit exception support), allowing the caller to make new plans, or at least not move forward under assumptions that no longer hold. Even unhandled exceptions, observed by the programmer, can be an opportunity to study and make new plans so that things may work better next time.

In a highly asynchronous networked environment, the likeliness of unanticipated failures grows substantially. Even with the most well implemented, bug-free locally implemented code (itself usually less likely a possibility than its authors may think), network connections are fickle, and remote objects may misbehave. As such, if a promise is broken, a pipelined message to that promise will have nowhere to go. This too should be interpreted as a failure and handled correctly.

As an example of this, consider this broken implementation of a car factory:

define (^borked-car-factory bcom company-name)
  define (^car bcom model color)
    methods                      ; methods for the ^car
      (drive)                    ; drive the car
        format #f "*Vroom vroom!*  You drive your ~a ~a ~a!"
               . color company-name model
  ;; methods for the ^car-factory instance
  methods                        ; methods for the ^car-factory
    (make-car model color)       ; create a car
      error "Your car exploded on the factory floor!  Ooops!"
      spawn ^car model color

What would happen if we tried making a car using this factory and then pipeline a message to drive it?

REPL> define forked-motors
_____   spawn ^borked-car-factory "Forked"
REPL> define car-vow
_____   <- forked-motors 'make-car "Exploder" "red"
REPL> define drive-noise-vow
_____   <- car-vow 'drive
REPL> on drive-noise-vow
_____    lambda (val)
_____      format #t "Heard: ~a\n" val
_____    #:catch
_____    lambda (err)
_____      format #t "Caught: ~a\n" err
; prints (eventually):
;   Caught: <error...>

Even though it is car-vow which is initially broken, its exception propagates to drive-noise-vow. Since there would be no useful way to drive a broken promise of a car anyhow, this is the correct design, and the situation can be detected and dealt with.

Lauren Ipsdale has decided to run a newspaper for her local community. The first thing Lauren will need is a way to construct individual posts which can be widely read, but edited only by trusted editors.

Lauren creates a new post:

REPL> define-values (day-in-park-post day-in-park-editor)
_____   spawn-post-and-editor
_____     #:title "A Day in the Park"
_____     #:author "Lauren Ipsdale"
_____     #:body "It was a good day to take a walk..."

(We will show implementation details of these blogposts below, but first we will focus on narrative and use.)

spawn-post-and-editor returned two capabilities:

• day-in-park-post, which grants the authority to read Lauren's blogpost, but not to make changes to it.
• day-in-park-editor, which grants the authority to modify the blogpost.

Lauren wants the feedback of her friend Robert, but wants to decide whether or not to make or accept any changes herself. She shares day-in-park-post with Robert. Robert is able to view the post by running:

REPL> display-post day-in-park-post

Which prints out:

A Day in the Park
=================
  By: Lauren Ipsdale

It was a good day to take a walk...

Robert tells Lauren that he likes the blogpost, but that "a fine day" might sound more pleasant than "a good day" for the article's opening, and that maybe the name of the post should be "A Morning in the Park". Robert, not having access to day-in-park-editor, cannot make the changes himself.

Lauren deliberates on this feedback and decides that she agrees with the suggestion to change "good" to "fine" but that she thinks her title is good as-is. Lauren makes the change:

REPL> $ day-in-park-editor 'update
_____   #:body "It was a fine day to take a walk..."

Of course, a blogpost on its own is not itself a blog or newspaper. Lauren wants a collection of updated posts, not just a singular entry. Time to make the blog!

Lauren invokes spawn-blog-and-admin:

REPL> define-values (maple-valley-blog maple-valley-admin)
_____   spawn-blog-and-admin "Maple Valley News"

spawn-blog-and-admin returns two capabilities. The first is for the blog itself, which Lauren has locally bound to the variable maple-valley-blog only grants read access to the current set of posts. maple-valley-admin provides the ability to curate the set of posts itself. Lauren has a certain vision and standard of post quality she'd like to see held for Maple Valley News but would like it to be widely read, and thus she will share and encourage wide dissemination of the former capability but will more carefully guard the latter capability.

Since maple-valley-blog has just been initialized, it unsurprisingly reports having no posts:

REPL> $ maple-valley-blog 'get-posts
; => ()

Since Lauren is now happy with day-in-park-post, she can add it via maple-valley-admin, and maple-valley-blog will now report the new post's addition:

REPL> $ maple-valley-admin 'add-post day-in-park-post
REPL> $ maple-valley-blog 'get-posts
; => (#<local-object ^post>)

The blog can now also be read with display-blog:

REPL> display-blog maple-valley-blog

Which prints the following:

***********************
** Maple Valley News **
***********************

A Day in the Park
=================
  By: Lauren Ipsdale

It was a fine day to take a walk...

Robert tells Lauren he'd love to make an article of his own, and Lauren says she'd love to read it and see about including it. Robert pens a new post:

;; Run by Robert:
REPL> define-values (spelling-bee-post spelling-bee-editor)
_____  spawn-post-and-editor
_____    #:title "Spelling Bee a Success"
_____    #:author "Robert Busyfellow"
_____    #:body "Maple Valley School held its annual spelling bee..."

Robert sends this to Lauren for review. Lauren says that it's good, but could use a catchier title. Robert's years of community newspaper reporting leaves him with exactly the right idea for a change:

;; Run by Robert:
REPL> $ spelling-bee-editor 'update
_____   #:title "Town Buzzing About Spelling Bee"

Lauren checks the post and decides it's ready to go. She adds it to the blog:

REPL> $ maple-valley-admin 'add-post spelling-bee-post

Now maple-valley-blog is starting to look like it's got some real content going!

REPL> display-blog maple-valley-blog

***********************
** Maple Valley News **
***********************

Town Buzzing About Spelling Bee
===============================
  By: Robert Busyfellow

Maple Valley School held its annual spelling bee...


A Day in the Park
=================
  By: Lauren Ipsdale

It was a fine day to take a walk...

One implication from the way this code is currently written is that the blog is mostly a kind of aggregator of posts. While Lauren added Robert's post to Maple Valley News's collection of blogposts, since Robert did not share the edit capability with Lauren, Lauren cannot edit the post if she discovers a problem.

This can be an acceptable design, but Lauren has decided that she would like to ensure that any posts that are on the blog are editable by her or any other admins she gives access to. She also does not want to have to keep track of which edit capability is associated with which post: if she is looking at a post and catches an error, she wants to be able to jump straight into correcting it. Lauren wants to make sure her blogging administration software helps her ensure she is only adding objects which uphold these properties.

Under this rearchitecture, the admin interface is directly involved in constructing new posts and editors:

REPL> define-values (bumpy-ride-post bumpy-ride-editor)
_____   spawn-adminable-post-and-editor
_____     . maple-valley-admin
_____     #:title "Main Street's Bumpy Ride"
_____     #:author "Lauren Ipsdale"  

Using this approach, Lauren could edit bumpy-ride-post using bumpy-ride-editor, but she does not need to since she can also use maple-valley-admin to edit:

REPL> $ maple-valley-admin 'edit-post
_____   . bumpy-ride-post
_____   #:body "Anyone who's driven on main street recently..."

This new code also provides an assurance that any blogposts which are added are created through the internals of the code which runs "Maple Valley News". It will not be possible for any other object to spoof being a post which will not grant a user of maple-valley-admin the ability to edit the post and still be added to the blog.

Lauren decides that it may be time for her to not be the only person running things, but she wants to make sure that she can hold anyone she gives access to accountable for the decisions they make and, if something inappropriate happens, revoke that access.

Lauren realizes she can extend her system to accommodate this plan without rewriting any of the existing code. Instead she will define some new abstractions that compositionally extend the system that exists.

The first thing she will need is a logger.

REPL> define admin-log
_____   spawn ^logger

Robert has been a great collaborator and has expressed interest in helping run things. Lauren decides it's time to take him up on it.

Lauren uses a new utility, spawn-logged-revocable-proxy-pair, which can proxy any object and log actions associated with a username meaningful to Lauren:

REPL> define-values (admin-for-robert roberts-admin-revoked?)
_____   spawn-logged-revocable-proxy-pair
_____     . "Robert"            ; username Lauren holds responsible
_____     . maple-valley-admin  ; object to proxy
_____     . admin-log           ; log to write to

The first of the two returned capabilities, admin-for-robert, is the one she sends Robert. The second, roberts-admin-revoked?, is the cell which defaults to false, but Lauren can set to be true at any time, at which point messages from Robert will no longer pass through.

Robert thanks Lauren for the capability and soon decides that Lauren's post would be better with a different title:

REPL> <- admin-for-robert 'edit-post bumpy-ride-post
_____    #:title "Main Street Takes Some Bumps"

Later, Lauren suddenly notices with irritation that her blogpost isn't named what she remembered it being. She checks the log:

REPL> $ admin-log 'get-log
; => ((*entry* 
;      user "Robert"
;      object #<local-object ^admin>
;      args (edit-post #<local-object ^post> 
;            #:title "Main Street Takes Some Bumps")))

Lauren decides that Robert shouldn't be editing her or anyone else's posts on the blog until they've had a serious conversation.

REPL> $ roberts-admin-revoked? 'set #t

Robert tries to make another edit to the blogpost and notices that it didn't go through. He sees a frustrated message in his inbox from Lauren and apologizes. The two of them agree on what the proper etiquette for editing someone else's post should be in the future and Lauren feels satisfied enough to renew Robert's access.

REPL> $ roberts-admin-revoked? 'set #f

Some time has passed and Maple Valley News is doing well. Robert and Lauren have been knocking out a lot of well celebrated articles covering their community. Lauren is busy figuring out next steps for the newspaper, but Robert is exhausted and needs to go on the vacation he has long promised his family they would take. But Robert has an idea for a guest post article that could be published in his absence without having to interrupt Lauren.

Robert has a friend who works at the local school, Maple Valley Elementary, and has told Robert about how a young student named Matilda Sample won a distinguished prize in the regional science fair, assisted with the mentorship of her science teacher Mx. Beaker. Robert thinks this would be a great idea for a story. Robert asks if Matilda would be willing to write a story about her experience and whether Mx. Beaker would be willing to review and determine if and when the the article would be good enough to publish.

Everyone agrees, so Robert sets everything up. Robert runs the following:

;; Robert's interactions
REPL> define-values (science-fair-post science-fair-editor science-fair-reviewer)
_____   spawn-post-guest-editor-and-reviewer "Matilda Sample" admin-for-robert

Robert now sends out a message to Matilda and another to Mx. Beaker with the capabilities they will need:

• science-fair-post is given to both Matilda and Mx. Beaker and allows either of them to read the current state of the post.
• science-fair-editor is given to Matilda only; this allows Matilda to edit and author the post. This capability only allows Matilda to change the title and body, but not the author (which Robert has already set to "Matilda Sample"). However, this capability does not give Matilda the authority to publish the post.
• science-fair-reviewer is given to Mx. Beaker; this allows Mx. Beaker to approve and publish the post (but also will prevent future edits in the process). However, this capability does not give Mx. Beaker the authority to modify the post.

Matilda begins writing the post:

;; Matilda's interactions
REPL> <- science-fair-editor 'set-body
_____    . "My name is Matilda and I am twelve. I won the science fair..."

Matilda asks Mx. Beaker if it's good enough to publish. Mx. Beaker tells Matilda, not yet! The post needs a title, and Matilda's teacher explains how to make the post tell a more engaging and personal narrative.

Matilda updates the title and rewrites the body:

;; Matilda's interactions
REPL> <- science-fair-editor 'set-title
_____    . "Winning the Middle School Science Fair: A Personal Account"
REPL> <- science-fair-editor 'set-body
_____    . "At twelve years old, winning the local science fair has been..."

After another prompt for review, Mx. Beaker decides that the post now looks great and will be a great representation of both Matilda and the school. Feeling proud of their student, Mx. Beaker presses approve:

;; Teacher's interactions
REPL> <- science-fair-reviewer 'approve

And the post goes live!

Readers of the blog will see the new post, and will be able to share it widely:

;; Widely runnable (by blog readers and those they share it with)
REPL> display-blog maple-valley-blog

Robert, still on vacation, receives a message from Lauren. "Hey, I just saw that blogpost go live! It looks great! But I see in the log that you posted it… didn't you promise you weren't going to work while you left on vacation?"

Robert smiles and types up response. "Funny thing that… nice things can happen that serve multiple peoples' interests, and if you think far ahead enough, sometimes when you aren't even around…"

We have skipped over some important steps intentionally: we have not shown how to set up the network connections between parties, we have not shown how to produce capability references which can be passed along offline, and we have not shown how these posts might be persisted to long-term storage or upgraded.

Nonetheless, we have seen evidence of some powerful things:

• Distributed objects defined by behavior and bound together through capabilities are sufficient to represent sophisticated and useful social interactions between multiple parties.
• Our authorization mechanism relies on capability references and follows the "if you don't have it, you can't use it" philosophy. Sharing access remains as simple as reference passing. Everything is understandable as ordinary code.
• Despite the fact that our authorization mechanism itself is ambivalent about the identity of its participants, we are able to encode attribution of actions into the system. Combined with a revocation mechanism, this permits accountability. We have also added broader group-style access to administrate certain objects. All this without needing an access control list mechanism or the inherent ambient authority and confused deputy risks associated with such an approach.
• We are able to encode rich, multi-stakeholder arrangements that benefit everyone. Through the guest post with review example, we have demonstrated that special use cases like this can occur layered on top of an existing system rather than requiring a messy rewrite of existing behavior.

Here's the familiar "hello world", written in Scheme:

(display "Hello world!\n")

This prints "hello world!" to the screen. (The "\n" represents a "newline", like if you pressed enter after typing some text in a word processor.)

If you are familiar with other programming languages, this might look a little bit familiar and a little bit different. In most other programming languages, this might look like:

display("Hello world!\n")

In this sense, calling functions in Scheme (and other lisps like it) is not too different than other languages, except that the function name goes inside the parentheses.

Unlike in some other languages, math expressions like + and - are prefix functions just like any other function, and so they go first:

(+ 1 2)         ; => 3
(/ 10 2)        ; => 5
(/ 2 3)         ; => 2/3 

Most of these can accept multiple arguments:

(+ 1 8 10)   ; equivalent to "1 + 8 + 10" in infix notation

Procedures can also be nested, and we can use the "substitution method" to see how they simplify:

(* (- 8 (/ 30 5)) 21)   ; beginning expression
(* (- 8 6) 21)          ; simplify: (/ 30 5) => 6
(* 2 21)                ; simplify: (- 8 6)  => 2
42                      ; simplify: (* 2 21) => 42

A variety of types are supported. For example, here are some math types:

42          ; integer
98.6        ; floating point
2/3         ; fractions, or "rational" numbers
-42         ; these can all also be negative

Since Scheme supports both "exact" numbers like integers and fractions, and does not have any restriction on number size, it is very good for more precise scientific and mathematical computing. The floating point representation is considered "inexact", and throws away precision for speed.

Here are some more types:

'foo                           ; symbol
'(1 2 3)                       ; a list (of numbers, in this case)
(lambda (x) (* x 2))           ; procedure (we'll come back to this)
'(lambda (x) (* x 2))          ; a list of lists, symbols, and numbers
#t                             ; boolean representing "true"
#f                             ; boolean representing "false"
"Pangalactic Gargleblaster"    ; string (text)

Symbols are maybe the strangest type if you've come from non-lisp programming languages (with some exceptions). While symbols look kind of like strings, they represent something more programmatic. (In Goblins' methods syntax, we use symbols to represent method names.) Curiously, if a lisp expression itself is quoted with ', as in the quoted lambda expression above, the symbols inside are also automatically quoted.

We will devote some time to discussing lists in Lists and "cons". The combination of lists and symbols is featured very prominently in many Lisps, including Scheme, because they lie at the heart of Lisp's extensibility: code which can write code. We will see how to take advantage of this power in On the extensibility of Scheme (and Lisps in general).

We can assign values to variables using define:

REPL> (define name "Jane")
REPL> (string-append "Hello " name "!")
; => "Hello Jane!"

However, if what follows define is wrapped in parentheses, Scheme interprets this as a procedure definition:

(define (greet name)
  (string-append "Hello " name "!"))

Now that we have named this procedure we can invoke it:

REPL> (greet "Samantha")
; => "Hello Samantha!"

Note that Scheme has implicit return. By being the last expression in the procedure, the result of the string-append is automatically returned to its caller.

This second syntax for define is actually just syntactic sugar. These two definitions of greet are exactly the same:

(define (greet name)
  (string-append "Hello " name "!"))

(define greet
  (lambda (name)
    (string-append "Hello " name "!")))

lambda is the name for an "anonymous procedure" (ie, no name provided). While we have given this the name greet, the procedure would be usable without it:

REPL> ((lambda (name)
         (string-append "Hello " name "!"))
       "Horace")
; => "Hello Horace!"

There is also another way to name things aside from define, which is let, which allows for a sequence of bound variables and then a body which is evaluated with those bindings. let has the form:

(let ((<VARIABLE-NAME> <VALUE-EXPRESSION>) ...)
  <BODY> ...)

(The ... in the above example represents that its previous expression can be repeated multiple times.)

Here is an example of let in use:

REPL> (let ((name "Horace"))
        (string-append "Hello " name "!"))
; => "Hello Horace!"

Clever readers may notice that this looks very similar to the previous example, and in fact, let is syntax sugar for a lambda which is immediately applied with arguments. The two previous code examples are fully equivalent:

REPL> (let ((name "Horace"))
        (string-append "Hello " name "!"))
; => "Hello Horace!"
REPL> ((lambda (name)
         (string-append "Hello " name "!"))
       "Horace")
; => "Hello Horace!"

let* is like let, but allows bindings to refer to previous bindings within the expression:²⁵

REPL> (let* ((name "Horace")
             (greeting
              (string-append "Hello " name "!\n")))
        (display greeting))   ; print greeting to screen
; prints: Hello Horace!

It is possible to manually apply a list of arguments to a procedure using apply. for example, to sum a list of numbers, we can use apply and + in combination:

REPL> (apply + '(1 2 5))
; => 8

As the inverse of this, it is possible to capture a variable-length set of arguments using "dot notation".²⁶ Here we show this off while also demonstrating Guile's format (which when when called with #f as its first argument returns a formatted string as a value, and when called with #t as its first argument prints to the screen, the latter of which is what we want here):

REPL> (define (chatty-add chatty-name . nums)
        (format #t "<~a> If you add those together you get ~a!\n"
                chatty-name (apply + nums)))
REPL> (chatty-add "Chester" 2 4 8 6)
; Prints:
;   <Chester> If you add those together you get 20!

While not standard in Scheme, many Scheme implementations also support optional and keyword arguments. Guile implements this abstraction as define*:

REPL> (define* (shopkeeper thing-to-buy
                           #:optional (how-many 1)
                           (cost 20)
                           #:key (shopkeeper "Sammy")
                           (store "Plentiful Great Produce"))
        (format #t "You walk into ~a, grab something from the shelves,\n"
                store)
        (display "and walk up to the counter.\n\n")
        (format #t "~a looks at you and says, "
                shopkeeper)
        (format #t "'~a ~a, eh? That'll be ~a coins!\n"
                how-many thing-to-buy
                (* cost how-many)))
REPL> (shopkeeper "apples")
; Prints:
;   You walk into Plentiful Great Produce, grab something from the shelves,
;   and walk up to the counter.
;
;   Sammy looks at you and says, '1 apples, eh? That'll be 20 coins!'
REPL> (shopkeeper "bananas" 10 28)
; Prints:
;   You walk into Plentiful Great Produce, grab something from the shelves,
;   and walk up to the counter.
;
;   Sammy looks at you and says, '10 bananas, eh? That'll be 280 coins!'
REPL> (shopkeeper "screws" 3 2
                  #:shopkeeper "Horace"
                  #:store "Horace's Hardware")
; Prints:
;   You walk into Horace's Hardware, grab something from the shelves,
;   and walk up to the counter.
;
;   Horace looks at you and says, '3 screws, eh? That'll be 6 coins!'

Finally, Scheme's procedures can do something else interesting: they can return multiple values using… values! As a particularly silly example, perhaps we would like to compare what it's like to both add and multiply two numbers:

REPL> (define (add-and-multiply x y)
        (values (+ x y)
                (* x y)))
REPL> (add-and-multiply 2 8)
; => 10
; => 16
REPL> (define-values (added multiplied)
        (add-and-multiply 3 10))
REPL> added
; => 13
REPL> multiplied
; => 30

As you can see, we can capture said values with define-values, as shown above. (let-values and call-with-values can also be used, but that's enough new syntax for this section!)

Sometimes we would like to test whether or not something is true. For instance, we can see whether or not an object is a string by using the string?:²⁷

REPL> (string? "apple")
; => #t
REPL> (string? 128)
; => #f
REPL> (string? 'apple)
; => #f

(Remember that #t represents "true" and #f represents "false".)

We can use this in combination with if, which has the form:

(if <TEST>
    <CONSEQUENT>
    [<ALTERNATE>])

(The square brackets around <ALTERNATE> means that it is optional.)²⁸

So, we could write a silly function that excitedly reports on whether or not an object is a string or not:

REPL> (define (string-enthusiast obj)
        (if (string? obj)
            "Oh my gosh you gave me A STRING!!!"
            "That WASN'T A STRING AT ALL!! MORE STRINGS PLEASE!"))
REPL> (string-enthusiast "carrot")
; => "Oh my gosh you gave me A STRING!!!"
REPL> (string-enthusiast 529)
; => "That WASN'T A STRING AT ALL!! MORE STRINGS PLEASE!"

As we can see, unlike in some other popular languages, if also returns the value of evaluating whichever branch is chosen based on <TEST>.

Scheme also ships with some mathematical comparison tests. > and < stand for "greater than" and "less than" respectively, and >= and <= stand for "greater than or equal to" and "less than or equal to", while = checks for numerical equality:²⁹

REPL> (> 8 9)
; => #f
REPL> (< 8 9)
; => #t
REPL> (> 8 8)
; => #f
REPL> (>= 8 8)
; => #t

If we wanted to test for multiple possibilities, we could use nested if statements:

REPL> (define (goldilocks n smallest-ok biggest-ok)
        (if (< n smallest-ok)
            "Too small!"
            (if (> n biggest-ok)
                "Too big!"
                "Just right!")))
REPL> (goldilocks 3 10 20)
; => "Too small!"
REPL> (goldilocks 33 10 20)
; => "Too big!"
REPL> (goldilocks 12 10 20)
; => "Just right!"

However, there is a much nicer syntax named cond which we can use instead which has the following form:³⁰

(cond
 (<TEST>
  <THEN-BODY> ...) ...
 [(else <ELSE-BODY> ...)])

Compare how much nicer our goldilocks procedure looks with cond instead of nested if statements:

;; Nested "if" version
(define (goldilocks n smallest-ok biggest-ok)
  (if (< n smallest-ok)
      "Too small!"
      (if (> n biggest-ok)
          "Too big!"
          "Just right!")))

;; "cond" version
(define (goldilocks n smallest-ok biggest-ok)
  (cond
   ((< n smallest-ok)
    "Too small!")
   ((> n biggest-ok)
    "Too big!")
   (else
    "Just right!")))

Scheme also provides some different ways to compare whether or not two objects are the same thing. The shortest, simplest (but not comprehensive) summary of the zoo of equality predicates is that equal? compares based on content equivalence, whereas eq? compares based on object identity (as defined by the language's runtime).³¹ For example, list constructs a fresh list with a new identity every time, so the following are equal? but not eq?:

REPL> (define a-list (list 1 2 3))
REPL> (define b-list (list 1 2 3))
REPL> (equal? a-list a-list)
; => #t
REPL> (eq? a-list a-list)
; => #t
REPL> (equal? a-list b-list)
; => #t
REPL> (eq? a-list b-list)
; => #f

Finally, in Scheme, anything that's not #f is considered true. This is sometimes used with something like member, which looks for matching elements and returns the remaining list if anything is found, and #f otherwise:

REPL> (member 'b '(a b c))
; => (b c)
REPL> (member 'z '(a b c))
; => #f
REPL> (define (fruit-sleuth fruit basket)
        (if (member fruit basket)
            "Found the fruit you're looking for!"
            "No fruit found! Gadzooks!"))
REPL> (define fruit-basket '(apple banana citron))
REPL> (fruit-sleuth 'banana fruit-basket)
; => "Found the fruit you're looking for!"
REPL> (fruit-sleuth 'pineapple fruit-basket)
; => "No fruit found! Gadzooks!"

"My other CAR is a CDR"
  — Bumper sticker of a Lisp enthusiast

For structured data, Scheme supports lists, which can contain any other type.³² Here are two ways to write the same list:

REPL> (list 1 2 "cat" 33.8 'foo)
; => (1 2 "cat" 33.8 foo)
REPL> '(1 2 "cat" 33.8 foo)
; => (1 2 "cat" 33.8 foo)

One difference between the two above is that in the latter quoted example, the symbol "foo" did not need to be quoted, since the outer list's quoting implicitly quoted it.

There is a "special" list known as "the empty list", which is a list with no elements, simply designated '() (also known as nil, and which is the only object which will return #t in response to the predicate null? in standard Scheme). Lists in Scheme are actually "linked lists", which are combinations of pairs called "cons cells" that terminate in the empty list:

REPL> '()
; => ()
REPL> (cons 'a '())
; => (a)
REPL> (cons 'a (cons 'b (cons 'c '())))
; => (a b c)

The latter of which is equivalent to either:

REPL> (list 'a 'b 'c)
; => (a b c)
REPL> '(a b c)
; => (a b c)

For very historical reasons,³³ accessing the first element of a cons cell is done with car and the second element of a cons cell with cdr (pronounced "could-er"):³⁴

REPL> (car '(a b c))
; => a
REPL> (cdr '(a b c))
; => (b c)
REPL> (car (cdr '(a b c)))
; => b

The second member of cons does not have to be another cons cell or the empty list. If not, it is considered a "dotted list", and has an unusual-for-lisp infix syntax:

REPL> (cons 'a 'b)
; => (a . b)

Notice how this is structurally different from the following:

REPL> (cons 'a (cons 'b '()))
; => (a b)

It's easy to get caught up on piecing apart cons cells (arguably schemers do far too often, but cons is also elegantly powerful).³⁵

In a sense, this subsection is a digression. We intentionally do not use cons too much in this paper, and we have entirely kept car and cdr out of the main text. This may lead to the question, why contain this subsection on lists at all?

The reason is that we are building up to something we will explore further shortly, the extensibility of Scheme. Scheme is written in its core data types, and is modifiable as such. We will get to this more shortly, but as an example, we can quote any expression, transforming transforming code into data:

REPL> (+ 1 2 (- 8 4))
; => 7
REPL> '(+ 1 2 (- 8 4))
; => (+ 1 2 (- 8 4))
REPL> (let ((name "Horace"))
        (string-append "Hello " name "!"))
; => "Hello Horace!"
REPL> '(let ((name "Horace"))
         (string-append "Hello " name "!"))
; => (let ((name "Horace")) (string-append "Hello " name "!"))

This last example is especially curious: we finally see the reason for symbols in Scheme to be important, as the function and syntax names become captured as symbols upon being quoted. In this sense, Lisp (including Scheme) is written in Lisp: there is little distinction between the representation the programmer sees and the representation the compiler sees, as see in On the extensibility of Scheme (and Lisps in general).

By the way, the apostrophe quote is just a shorthand for (quote <EXPR>):

;; these two are the same
'foo
(quote foo)

;; and these two are the same
(lambda (x) (* x 2))
(quote (lambda (x) (* x 2)))

Lists can also be used as an associative mapping between keys and values, called alists (association lists). A variety of procedures for convenient lookup exist, such as assoc, which returns the pair if found or #f if not:

REPL> (define animal-noises
        '((cat . meow)
          (dog . woof)
          (sheep . baa)))
REPL> (assoc 'cat animal-noises
; => (cat . meow)
REPL> (assoc 'alien animal-noises)
; => #f

Association lists are easy to implement, look nice enough in Scheme's printed representation, and are easy to use with functional programming. (Want to add more to an alist? Just cons on another cons cell!) This means they tend to be popular with schemers. However, they are not always efficient. While assoc is fine for small alists, an alist that is one thousand elements long will take one thousand steps to find a key-value pair buried at its bottom. Other datastructures, such as hashmaps which provide constant-time average lookups, are commonly provided in many Scheme implementations, and are sometimes a better choice.

Aside from quote, it is also possible to use quasiquote, which uses the backtick to begin a quasiquote, and the comma to unquote. In this way we can move quickly between the world of data and code. For example, using a somewhat apocryphal metric for converting cat years to human years:

REPL> (define (cat-years years)
        (cond
         ((<= years 1)       ; first year equivalent to 15
          (* years 15))
         ((<= years 2)
          (+ 15 (* 9 (- years 1))))   ;      second year 9
         (else
          (+ 24 (* 4 (- years 2)))))) ; years after that 4
REPL> (define (cat-entry name age)
        `(cat (name ,name)
              (age  ,age)
              (cat-years-age ,(cat-years age))))
REPL> (cat-entry "Missy Rose" 16)
; => (cat (name "Missy Rose")
;         (age 16)
;         (cat-years-age 80))
REPL> (cat-entry "Kelsey" 22)
; => (cat (name "Kelsey")
;         (age 21)
;         (cat-years-age 104))

Wow! Those are some old cats!

Recall our earlier definition and use of goldilocks:

REPL> (define (goldilocks n smallest-ok biggest-ok)
        (cond
         ((< n smallest-ok)
          "Too small!")
         ((> n biggest-ok)
          "Too big!")
         (else
          "Just right!")))
REPL> (goldilocks 3 10 20)
; => "Too small!"
REPL> (goldilocks 33 10 20)
; => "Too big!"
REPL> (goldilocks 12 10 20)
; => "Just right!"

Entering the same values for smallest-ok and biggest-ok over and over again is tedious. Goldilocks' range of preferences are unlikely to change from invocation to invocation. Is there a way we could produce a version of Goldilocks with a kind of memory so we only have to pass in smallest-ok and biggest-ok once but still test against multiple versions of n? Indeed there is… closures to the rescue!

(define (make-goldilocks smallest-ok biggest-ok)
  (define (goldilocks n)   ; make a procedure which encloses
    (cond                  ;  smallest-ok and biggest-ok so
     ((< n smallest-ok)    ;  that only the n argument needs
      "Too small!")        ;  to be passed in  
     ((> n biggest-ok)
      "Too big!")
     (else
      "Just right!")))
  goldilocks)              ; return goldilocks procedure

We can now invoke make-goldilocks, which returns the enclosed goldilocks procedure.

REPL> (make-goldilocks 10 30)
; => #<procedure goldilocks (n)>

Now we can call the inner goldilocks over and over again.

REPL> (define goldi
        (make-goldilocks 10 30))
REPL> (goldi 7)
; => "Too small!"
REPL> (goldi 256)
; => "Too big!"
REPL> (goldi 22)
; => "Just right!"

The outer procedure "closes over" the inner procedure, giving it access to (and a memory of) smallest-ok and biggest-ok.

Notably, this is the same pattern Goblins uses to implement constructors for its objects: the outer procedure is the constructor, the inner procedure is the behavior of the object. (The primary difference is indeed that Goblins objects spawned with spawn get a bcom capability which they can use to change their behavior!)

Beautifully, we can also build our own cons cells out of pure abstraction using this same technique.

REPL> (define (abstract-cons car-data cdr-data)
        (lambda (method)
          (cond
           ((eq? method 'car)
            car-data)
           ((eq? method 'cdr)
            cdr-data)
           (else (error "Unknown method:" method)))))
REPL> (define our-cons (abstract-cons 'foo 'bar))
REPL> (our-cons 'car)
; => foo
REPL> (our-cons 'cdr)
; => bar

In this sense, closures are also datastructures built from the code flow of the program itself.

Closures are a property of lexical scoping. We take advantage of this in Goblins: the capabilities an object has access to is merely the capabilities it has within its behavior's scope.

Much of programming involves sequences of operations, especially on datastructures which contain other information. One especially useful procedure for functional programming which operates on lists is map, which applies its first argument's procedure to each element in its series.

For example, string-length gives the number of characters which exist in a given string:

REPL> (string-length "cat")
; => 3
REPL> (string-length "gorilla")
; => 7

So, using map, we could easily construct a list representing the length of each of its strings:

REPL> (map string-length '("cat" "dog" "gorilla" "salamander"))
; => (3 3 7 10)

We could also supply a procedure we define:

REPL> (define (symbol-length sym)
        (string-length (symbol->string sym)))
REPL> (map symbol-length '(basil oregano parsley thyme))
; => (5 7 7 5)

In fact, there is no requirement that we name the procedure… we can use lambda to construct an anonymous procedure which we pass to map directly:

REPL> (map (lambda (str)
             (string-append "I just love "
                            (string-upcase str)
                            "!!!"))
           '("strawberries" "bananas" "grapes"))
; => ("I just love STRAWBERRIES!!!"
;     "I just love BANANAS!!!"
;     "I just love GRAPES!!!")

map performs some extra work by building up a list of results every time. But what if we wanted to simply display our love of some food to the screen using display and did not care about operating on the data any further? We could use for-each, which has the same structure as map but does not build a result:

REPL> (for-each (lambda (str)
                  (display
                   (string-append "I just love "
                                  (string-upcase str)
                                  "!!!\n")))
                '("strawberries" "bananas" "grapes"))
; prints:
;   I just love ICE CREAM!!!
;   I just love FUDGE!!!
;   I just love COKIES!!!

Scheme has the surprising property that iteration is actually defined in terms of recursion!

Here is what we mean. We could define our own version of for-each:

(define (for-each proc lst)
  (if (eq? lst '())  ; End of the list?
      'done          ; We're done, so simply return "done"
      (let ((item (car lst)))  ; Otherwise... let's fetch this item
        (proc item)            ; Call the procedure with this item
        (for-each proc (cdr lst)))))  ; Iterate with the remaining work

This calls proc successively with each item from lst until it runs out of items. If you have experience with other programming languages, your expectation would probably be that this design could accidentally "blow the stack". However, Scheme is smart: it sees that there is no more work left to be done within the current version of for-each once we reach the last line… in other words, where for-each calls itself is in the "tail position". Because of this, Scheme is able to skip allocating a new frame on the stack and "jump" back to the beginning of for-each again with the new variables allocated. This is called tail call elimination and all iteration facilities are actually defined this way in terms of recursion in Scheme.

It is also possible to build recursive procedures. The following (somewhat advanced, if you don't follow this it's ok) procedure builds a binary tree:

(define (build-tree depth)
  (if (= depth 0)
      '(0)
      (list depth
            (build-tree (- depth 1))
            (build-tree (- depth 1)))))

REPL> (build-tree 3)
; => (3 (2 (1 (0)
;             (0))
;          (1 (0)
;             (0)))
;       (2 (1 (0)
;             (0))
;          (1 (0)
;             (0))))

Or, better visualized:

       3
      / \
     /   \
    2     2
   / \   / \
  1  1   1  1
 /\  /\ /\  /\
0 0 0 0 0 0 0 0

However, unlike for-each, build-tree does not call itself in the tail position. There is no way to simply "jump" to the beginning of the procedure without allocating work to be done on the stack with the way this code is written: more work needs to be done, as cons sits waiting for its results. As such, unlike for-each, build-tree is recursive but not iterative.

Finally, come conveniences. Here are two variants on let, both useful for recursive and iterative procedures. The first is letrec which allows for procedures to call and refer to themselves or others defined by the letrec, regardless of definition ordering:

REPL> (letrec ((alice
                (lambda (first?)
                  (report-status "Alice" first?)
                  (if first? (bob #f))))
               (bob
                (lambda (first?)
                  (report-status "Bob" first?)
                  (if first? (alice #f))))
               (report-status
                (lambda (name first?)
                  (display
                   (string-append name " is "
                                  (if first?
                                      "first"
                                      "second")
                                  "!\n")))))
        (alice #t)
        (display "-----\n")
        (bob #t))
; prints:
;   Alice is first!
;   Bob is second!
;   -----
;   Bob is first!
;   Alice is second!

The second useful abstraction is the named let variant of let, where a looping name identifier appears as the first argument:

REPL> (let loop ((strings '("carrot" "potato" "pea" "celery"))
                 (num-words 0)
                 (num-chars 0))
        (if (eq? strings '())
            (format #f "We found ~a words and ~a chars!"
                    num-words num-chars)
            (let* ((this-string (car strings))
                   (rest-strings (cdr strings)))
              (loop rest-strings
                    (+ num-words 1)
                    (+ num-chars (string-length this-string))))))
; => "We found 4 words and 21 chars!"

What a named let does is define the named procedure (here named loop) and immediately invokes it with the initial bindings of the let. The procedure is available within the body of the let for convenient recursive (perhaps iterative) calls.

This section is included for completeness. Notably, Goblins provides a different approach to much of this here which we will discuss towards the end.

Scheme ships with a way to reassign the current value of a variable using set!:

REPL> (define chest 'sword)
REPL> chest
; => sword
REPL> (set! chest 'gold)
REPL> chest
; => gold

This can even be combined with the techniques shown in Closures. For instance, here's an example of an object that counts down from an initial number n until it reaches its zero, and then always returns zero afterwards.

REPL> (define (make-countdown n)
        (lambda ()
          (define last-n n)
          (if (zero? n)
              0
              (begin
                (set! n (- n 1))
                last-n))))
REPL> (define cdown (make-countdown 3))
REPL> (cdown)
; => 3
REPL> (cdown)
; => 2
REPL> (cdown)
; => 1
REPL> (cdown)
; => 0
REPL> (cdown)
; => 0

There are several interesting things about this example:

• We have introduced time and change into our computations. Before the introduction of side effects such as assignment, calling a procedure with the same arguments will always produce the same result. But in the above example, cdown changes its response over time (even without being passed any arguments on invocation).
• Since we want to show the initial number the first time the procedure is called, we have to capture last-n before using set! to change n. If we accidentally reverse this order, we will introduce a bug where cdown would have started with 2 instead of 3 in the example above.
• Here we also see an interesting new piece of syntax: begin. begin executes several expressions in sequence, returning the value of the last expression.

This last one is interesting. Prior to introducing effects (such as the assignment shown above, displaying to the screen, logging to a file or database, etc), there is never any reason for begin. To understand this, recall the substitution method demonstrated at the beginning of this tutorial:

(* (- 8 (/ 30 5)) 21)   ; beginning expression
(* (- 8 6) 21)          ; simplify: (/ 30 5) => 6
(* 2 21)                ; simplify: (- 8 6)  => 2
42                      ; simplify: (* 2 21) => 42

Before effects, every procedure invoked is to compute a new part of the program. But since each branch of if only evaluates one expression, we must provide a way to sequence the alternate clause so that we can both set! and then return a value.³⁶ In other words, a purely functional program is really built to take a series of inputs and precisely compute a value, the same value, every time. This is a clean set of substitutions all the way up and down the evaluation. (In other worlds, before introducing time, we will have programs which are fully deterministic.)

However, by introducing mutation and side effects, we have introduced a powerful, but dangerous, new construct into our program: time. Our programs are no longer purely functional, time has made them imperative: do this, then do that. Time is change, and change requires sequences of events, not mere substitutions. And time means that the same programs and procedures run with the same inputs will not always produce the same outputs. We have traded a timeless world for one that changes.

Despite the caution, change can be desirable. We live in a world with time and change, and so too often do our programs. Scheme has a (somewhat inconsistent) naming convention for observing time and change: the addition of a ! suffix, as we have seen with set!. The ! can be seen as a kind of warning, as if the user is shouting about the possibility of mutation. (However, the runtime of Scheme provides no guarantee that the presence or absence of this suffix says anything about mutation whatsoever.)

However, set! is not the only form of change and mutation available in standard (and nonstandard) Scheme.³⁷ Another example is mutable vectors and vector-set!:

REPL> (define vec (vector 'a 'b 'c))
REPL> vec
; => #(a b c)
REPL> (vector-ref vec 1)
; => b
REPL> (vector-set! vec 1 'boop)
REPL> (vector-ref vec 1)
; => boop
REPL> vec
; => #(a boop c)

Both of these examples resemble mutation. However, we have already seen a different form of side effects in this tutorial, namely display, which writes to the screen. In fact, display itself builds on the idea of ports, which are mechanisms in Scheme for reading and writing from and to input and output devices.

All of these carry the same challenges of set!. Put simply, the introduction of ambient time makes our programs less timeless. However, if turns out that we cannot remove all time and change from our computers, as illustrated in this nested set of quotes:

As Simon Peyton Jones, a well-known functional programmer, likes to say, "All you can do without side effects is push a button and watch the box get hot for a while." (Which isn't technically true, since even the box getting hot is a side effect.)

— From Land of Lisp by Conrad Barski, M.D.

As Simon and Conrad point out, the challenge with functional programming is that even though side effects can be dangerous, they are in a sense all the user really cares about. At some point, in order for a computer to be useful, input must be read from the user and output must be given back, and these are inherently side-effectful. Even using the radiant heat of a busy computer to warm your house is a side effect. At some point, we must both enter and leave the realm of pure mathlandia.

Functional programmers sometimes solve this with a clever trick called monads. Monads will not be covered in this tutorial, but they can be thought of as a clever and explicit form of handling time by threading a bundle of state through an otherwise stateless program. This provides enormous power: time exists, but in a deterministic manner: the programmer becomes a time lord. However, they come at some cost, by exposing plumbing outward to the programmer.

Goblins takes an alternate approach, as discussed in Turns are cheap transactions and Time-travel distributed debugging. By capturing the nature of change within turns, the programmer gains the ability to traverse time. With language level safety features, as discussed in Application safety, library safety, and beyond, fully deterministic and contained execution can be guaranteed. All this can be done by abstracting the details of managing change such that the user need need think of them; the Goblins core kernel can take care of this for the user. This will be expanded upon in detail within a future paper.

Let's say we'd like some new syntax. For instance, maybe we want to run multiple pieces of code in sequence when a condition is met. We could write:

(if (our-test)
    (begin
      (do-thing-1)
      (do-thing-2)))

But this is kind of ugly. What if we created some new syntax specifically for this purpose?

(when (our-test)
  (do-thing-1)
  (do-thing-2))

when cannot be built as a function because we do not want to execute (do-thing-1) or (do-thing-2) unless (our-test) passes. We need new syntax.

Could we build the new syntax ourselves? Remembering that we can "write Lisp in Lisp", the answer seems to be yes:

REPL> (define (when test . body)
        `(if ,test
             ,(cons 'begin body)))
REPL> (when '(our-test)
        '(do-thing-1)
        '(do-thing-2))
; => (if (our-test)
;        (begin
;          (do-thing-1)
;          (do-thing-2)))

This does build out the appropriate syntax! And it does demonstrate that our claim that Lisp can "write code which writes code" is indeed true.³⁸

However, there are two obvious problems with this first attempt:

• We had to quote each argument passed to build-when. This is annoying to do.
• build-when does not actually run its code, it just returns the quoted structure that the code should expand to.

However, with just one tweak our procedure can be turned into a "macro": a special kind of procedure used by the compiler to expand code. Here is all we need to do:

(define-macro (when test . body)
  `(if ,test
       ,(cons 'begin body)))

All we needed to do was rename define to define-macro! Now Scheme knows it should use this for code expansion. This allows us to define new kinds of syntax forms.

define-macro shows very clearly what macros in Lisp and Scheme do: they operate on structure. Manually building up a list structure like this is how macros in Common Lisp work. However, this is not the general way to write macros in Scheme. Scheme macros look very similar though:

(define-syntax-rule (when test body ...)
  (if test
      (begin body ...)))

define-syntax-rule uses pattern matching to implement macros. The first argument to define-syntax-rule describes the pattern which the user will enter, and the second describes the template which will be expanded.³⁹ We can also notice that body ... appears in both the pattern and the template; the ... ellipsis in the pattern represents that multiple expressions will be captured from the user's input and the ... in the template indicates where the repeating should occur. We can see that we do not need to manually quote things using this mechanism; Scheme cleverly takes care of it for us.

Ultimately, the Scheme version of syntax definitions is less obvious as to how it works under the hood than the define-macro version is. However, there is an issue that arrives in syntax transformation systems called hygiene: that a syntax form / macro not introduce unexpected temporary identifiers into the body of the form it expands into. We will not get into the debate in this primer, but both Common Lisp and Scheme's macros have significant tradeoffs, with Scheme being much more likely to be properly "hygienic", easier to write for simple syntax forms, but harder to write for more complicated ones, and less obvious as to how they work under the hood. For this reason, even though you will likely never use the define-macro approach in Scheme, it is a useful way to understand the idea behind "code that writes code".

Now that we know how to produce new syntax the Scheme way, let's see if we can make our life more convenient than before. Let's revisit our use of for-each from earlier:

REPL> (for-each (lambda (str)
                  (display
                   (string-append "I just love "
                                  (string-upcase str)
                                  "!!!\n")))
                '("strawberries" "bananas" "grapes"))
; prints:
;   I just love ICE CREAM!!!
;   I just love FUDGE!!!
;   I just love COKIES!!!

This works, but it is also unnecessarily tedious. That lambda is an unnecessary piece of detail! A small new syntax definition lets us clean things up:

(define-syntax-rule (for (item lst) body ...)
  (for-each (lambda (item)
              body ...)
            lst))

Let's give it a try:

REPL> (for (str '("strawberries" "bananas" "grapes"))
        (display
         (string-append "I just love "
                        (string-upcase str)
                        "!!!\n")))
; prints:
;   I just love STRAWBERRIES!!!
;   I just love BANANAS!!!
;   I just love GRAPES!!!

It works! This is much easier to read.⁴⁰

We need not stop here. The methods feature in Spritely Goblins is an example of a macro. Here is a simplified version:

(define-syntax-rule (methods ((method-id method-args ...)
                              body ...) ...)
  (lambda (method . args)
    (letrec ((method-id
              (lambda (method-args ...)
                body ...)) ...)
      (cond
       ((eq? method (quote method-id))
        (apply method-id args)) ...
       (else
        (error "No such method:" method))))))

We can both see here simultaneously how expressive Scheme style pattern matching examples are, but also how with multiple layers of ellipses (the ...), it can be a bit challenging to see how the code expander is figuring out how to unpack things.

But let's not worry about that for now, and instead show an example of usage:

REPL> (define (make-enemy name hp)
        (methods
         ((get-name)
          name)
         ((damage-me weapon hp-lost)
          (cond
           ((dead?)
            (format #t "Poor ~a is already dead!\n" name))
           (else
            (set! hp (- hp hp-lost))
            (format #t "You attack ~a, doing ~a damage!\n"
                    name hp-lost))))
         ((dead?)
          (<= hp 0))))
REPL> (define hobgob
        (make-enemy "Hobgoblin" 25))
REPL> (hobgob 'get-name)
; => "Hobgoblin"
REPL> (hobgob 'dead?)
; => #f
REPL> (hobgob 'damage-me "club" 10)
; prints: You attack Hobgoblin, doing 10 damage!
REPL> (hobgob 'damage-me "sword" 20)
; prints: You attack Hobgoblin, doing 20 damage!
REPL> (hobgob 'damage-me "pickle" 2)
; prints: Poor Hobgoblin is already dead!
REPL> (hobgob 'dead?)
; => #t

We can go further. We can extend Scheme to include logic programming, we can add pattern matching, etc etc etc. Indeed, we will use a pattern matching system included in Guile's standard library in the next subsection.

Because of the syntactic extensibility of Lisp/Scheme, advanced programming language features can be implemented as libraries rather than as entirely separate sub-languages. Multiple problem domains can be combined into one system. For this reason, we say that languages in the Lisp language support composable domain specific languages.

It is also liberating. In other programming languages, users must pray at the altar of the programming language implementers for features to show up in the next official language release, features which would be only a few small and simple lines of code in the hand of a Lisp/Scheme user.

This is true power. But there is more. In the next section we will unlock Scheme itself, allowing us to configure and experiment with its underlying mechanisms, in a surprisingly compact amount of code.

Here is a working implementation of Scheme written in Scheme:

(use-modules (ice-9 match))

(define (env-lookup env name)
  (match (assoc name env)
    ((_key . val)
     val)
    (_
     (error "Variable unbound:" name))))

(define (extend-env env names vals)
  (if (eq? names '())
      env
      (cons (cons (car names) (car vals))
            (extend-env env (cdr names) (cdr vals)))))

(define (evaluate expr env)
  (match expr
    ;; Support builtin types
    ((or #t #f (? number?))
     expr)
    ;; Quoting
    (('quote quoted-expr)
     quoted-expr)
    ;; Variable lookup
    ((? symbol? name)
     (env-lookup env name))
    ;; Conditionals
    (('if test consequent alternate)
     (if (evaluate test env)
         (evaluate consequent env)
         (evaluate alternate env)))
    ;; Lambdas (Procedures)
    (('lambda (args ...) body)
     (lambda (. vals)
       (evaluate body (extend-env env args vals))))
    ;; Procedure Invocation (Application)
    ((proc-expr arg-exprs ...)
     (apply (evaluate proc-expr env)
            (map (lambda (arg-expr)
                   (evaluate arg-expr env))
                 arg-exprs)))))

Without comments, blank lines, and the pattern matching import at the top (not necessary, but convenient), this is a mere 30 lines of code. This evaluator, while bare bones, is complete enough to be able to compute anything we can imagine. (You could even write another similar Scheme evaluator on top of this one!)⁴¹

Our evaluator takes two arguments, a Scheme expression expr and an environment env. Scheme's lispy structure is of great benefit here, since as we have learned we can easily quote entire sections of code. (Indeed, that is exactly what we are going to do.) The env of the second argument is an association list mapping symbols for names and their associated procedures.

Seeing is believing. Let's do some simple arithmetic, passing in some procedures to the default environment which can do some math:

(define math-env
  `((+ . ,+)
    (- . ,-)
    (* . ,*)
    (/ . ,/)))

As we can see, the first "substitution method" example we wrote works just fine using this environment:

REPL> (evaluate '(* (- 8 (/ 30 5)) 21)
                math-env)
; => 42

What do you know, that's the same answer we got in our own program!

We can also make a lambda and apply it. Let's make one that can perform square roots:

REPL> (evaluate '((lambda (x)
                    (* x x))
                  4)
                math-env)
; => 16

Nice, works perfectly.

Let's do something more advanced. Supplying only two operators, + and -, we are able to compute the Fibonacci sequence:

REPL> (define fib-program
        '((lambda (prog arg)   ; boot
            (prog prog arg))
          (lambda (fib n)      ; main program
            (if (= n 0)
                0
                (if (= n 1)
                    1
                    (+ (fib fib (+ n -1))
                       (fib fib (+ n -2))))))
          10))                 ; argument
REPL> (define fib-env
        `((+ . ,+)
          (= . ,=)))
REPL> (evaluate fib-program fib-env)
; => 55

This seems like magic. But it works! The evaluator really is performing the underlying computation, using merely addition (on both positive and negative numbers) and numeric equality check procedures, which we have provided.

The main program needs to be able to call itself, so the first procedure (labeled boot) takes a program and an argument and invokes the procedure with itself and that argument.⁴² The second procedure (labeled main program) takes itself as the argument fib (supplied by our boot procedure) as well as an argument of n (also supplied by the boot procedure)… and it works! Our evaluator recursively builds up the Fibonacci sequence.

Our evaluator can also be easily understood. Let us break it down section by section.

(define (env-lookup env name)
  (match (assoc name env)
    ((_key . val)
     val)
    (_
     (error "Variable unbound:" name))))

This one is easy. We are defining environments as association lists, so all env-lookup does is search for a matching name in the list. Newer additions will be found first, meaning that the same name defined in a deeper scope will shadow the parent scope. This can be seen by usage:

REPL> (env-lookup '((foo . newer-foo)
                    (bar . bar)
                    (foo . older-foo))
                  'foo)
; => 'newer-foo

The next one is a utility:

(define (extend-env env names vals)
  (if (eq? names '())
      env
      (cons (cons (car names) (car vals))
            (extend-env env (cdr names) (cdr vals)))))

extend-env takes an environment and a list of names and a parallel list of values. This is a convenience which we will use in procedure definitions later. Once again, easily understood by usage:

REPL> (extend-env '((foo . foo-val))
                  '(bar quux)
                  '(bar-val quux-val))
; => ((bar . bar-val)
;     (quux . quux-val)
;     (foo . foo-val))

And now we are onto the evaluator. The shell of evaluate looks like so:

(define (evaluate expr env)
  (match expr
    (<MATCH-PATTERN>
     <MATCH-BODY> ...) ...))

evaluate takes two arguments:

• expr: the expression to evaluate
• env: the environment in which we will evaluate the expression

For the body of evaluate, we are dispatching our behavior depending on which patterns match expr. We are using match from Guile's pattern matching syntax (which came from our module import at the top). The short of it is though that if a <MATCH-PATTERN> matches, we will then stop searching for matches and evaluate <MATCH-BODY> (possibly with bindings set up from the <MATCH-PATTERN>).

So, now all we need to do is look at each pattern we support. The first is easy:

;; Support builtin types
((or #t #f (? number?))
 expr)

The or says we can match any one of its contained patterns. The first two are literally the true and false values from Scheme itself. The parentheses starting with a ? symbol indicates that we will try matching against a predicate, in this case number?. If any of these match, we simply return the very same expr we are matching against… borrowing booleans and numbers straight from the underlying Scheme implementation.

In other words, the above powers:

REPL> (evaluate #t '())
; => #t
REPL> (evaluate #f '())
; => #f
REPL> (evaluate 33 '())
; => 33
REPL> (evaluate -2/3 '())
; => -2/3

That was easy! The next one is also easy:

;; Quoting
(('quote quoted-expr)
 quoted-expr)

Recall that 'foo is just shorthand for (quote foo), and likewise '(1 2 3) is shorthand for (quote (1 2 3)). In this pattern, we look for anything matching a list starting with the 'quote symbol and a second element which is the expression to be quoted.

In other words, the above powers:

REPL> (evaluate ''foo '())
; => foo
REPL> (evaluate ''(1 2 3) '())
; => (1 2 3)
REPL> (evaluate (quote (quote (1 2 3))) '())
; => (1 2 3)

Those last two are the same. Note that we quote twice: once for quoting the entire program to be run, and once within the quoted program to say we want to quote an expression.

So far so good. The next one is still quite easy:

;; Variable lookup
((? symbol? name)
 (env-lookup env name))

The (? symbol? name) part binds name to the matching component. (In this case, name will be bound to the same value as the expr matched against, but this improves readability a little.)

As for the body… why, this is quite simple! We have already reviewed how env-lookup works. In other words if we see a symbol (not a quoted one of course, that has already been handled), we look up its corresponding value in the environment.

In other words, the above powers:

REPL> (evaluate 'x '((x . 33)))
; => 33

However, it will also empower variable lookups we define through lambda applications:

REPL> (evaluate '((lambda (x) x) 33) '())
; => 33

Of course, we have not yet gotten to lambda! But we are nearly there.

The next one, conditionals, also turns out to be fairly easy:

;; Conditionals
(('if test consequent alternate)
 (if (evaluate test env)
     (evaluate consequent env)
     (evaluate alternate env)))

In other words, a list starting with the symbol 'if will be matched, with the three sub-expressions following 'if bound to the variables test, consequent, and alternate in the match body. We use the underlying Scheme if, and first evaluate test against the current environment env (notice the recursion!), and the host Scheme's if helps us whether to evaluate the consequent or alternate inside of env, again using evaluate recursively.

Okay, now it's time to build procedures. This one is a little bit more complicated, but ultimately not too complicated either:

;; Lambdas (Procedures)
(('lambda (args ...) body)
 (lambda (. vals)
   (evaluate body (extend-env env args vals))))

The pattern here looks for a list starting with 'lambda, with the second list member being the set of arguments, with the body being captured as, well, body. We then return a procedure which is ready to be evaluated with the same number of arguments.⁴³ The inner body of the procedure we return recursively calls evaluate against the body expression of the lambda we are matching against, but with a newly extended environment, binding together the names within args and the vals from the procedure invocation.

In other words, the above powers:

REPL> ((evaluate '(lambda (x y) x) '())
       'first 'second)
; => first
REPL> ((evaluate '(lambda (x y) y) '())
       'first 'second)
; => second

There is only one more piece left… application!

;; Procedure Invocation (Application)
((proc-expr arg-exprs ...)
 (apply (evaluate proc-expr env)
        (map (lambda (arg-expr)
               (evaluate arg-expr env))
             arg-exprs)))

This is the general-purpose procedure application piece of the puzzle! At this point, the pattern will match any list with one or more arguments, determining that this must mean a procedure applied to arguments. We evaluate the proc-expr, representing the procedure to be evaluated, within the current arguments, calling evaluate recursively with the current environment, env. We also gather all the arg-expr argument expressions passed to this procedure by calling evaluate recursively on each with the current environment, env.

In other words, the above powers:

REPL> (evaluate '(* (- 8 (/ 30 5)) 21)
                math-env)
; => 42

And with all pieces combined, we have enough power not only to compute the Fibonacci sequence, but any computable problem imaginable!

To be fair, this does borrow a portion of Scheme's underlying power, but not as much as it may appear… certainly less than many languages implemented on top of other languages do (certainly, certainly far less than Clojure borrows from Java, for instance, or nearly any popular language borrows from C's standard library).⁴⁴ And it is not so complete as to implement any of the Scheme standards. But without too much extra work, we could get there, and it is enough for demonstration. But we also get to choose how much power we give the language, by modifying the initial environment the code evaluates in.

It is also a capability-secure language! Aside from going into an infinite loop and consuming too many resources in terms of memory or CPU power, there is nothing particularly dangerous this language can do. However, we can decide how much power we would like to give it. If we choose, we can provide an environment with mutable cells, or one with access to the filesystem. The choice is ours.

And with tiny tweaks, our evaluator can operate in different and marvelous ways. We can add new syntax. We can add new syntax to add new syntax (macros)! We can change evaluation order, we can add static type analysis, we can do many things.

We promised that you would have learned Scheme from this tutorial. If you have reached this point, you have reached much more: you are no longer just a user of scheme, but a builder of Scheme. The power is yours!⁴⁵