Part 1 - Scheme Basics¶
Basic syntax¶
Scheme syntax is very simple: everything in the language is done with s-expressions. (sexp’s for short.) A simple s-expression is either one atom (such as a symbol, number, string), or a series of atoms surrounded by parentheses. S-expressions can be nested to any depth we want.
When we send an sexp to the interpreter to be evaluated, the interpreter evaluates all nested expressions, from the inside out, ending with evaluation of the outer sexpr. Evaluation of a parenthetical s-expr is done by calling the first atom as a function, with the remaining atoms passed as parameters, also called arguments. (In strict computer science circles, there are differences between the terms “procedure” and “function”, and between “parameter” and “argument”, but we are not going to worry about those here, you can take them as synonyms for now.)
; evaluating an sexp that calls the function bound to the symbol '+'
; evaluating this sexp calls the function with arguments and returns value 2
(+ 1 1)
s4m> 2
; post is a function, and we can pass nested sexprs to it
; post returns null, but prints as side effect
(post "1 + 1 is:" (+ 1 1))
s4m: 1 + 1 is: 2
s4m> ()
This syntax is called prefix notation - functions are in the first slot, followed by as many arguments as the function will permit.
; add more numbers!
(+ 1 2 3 4)
s4m> 10
Nesting is simple - just add more sexps. They are evaluated from the inside out.
;; a compound expression
(+ 1 (* 2 (+ 3 4)))
s4m> 15
In the above, three sexps get evaluated. First, (+ 3 4) evaluates to 7 by calling the + function with arguments 3 and 4, resulting in (+ 1 (* 2 7))). Next, (* 2 7) is evaluated by calling the * function with arguments 2 and 7, leaving (+ 1 14). Finally, the remaining sexp is evaluated by calling the + function with arguments 1 and 14. Each round of evaluation calls a function, replacing the sexp with the results.
This is critical to understand. Evaluation of an sexp calls the function (or special form) in the first slot, with the arguments from the rest of the sexp, and nested sexps are evaluated inside-out.
Variables¶
The define function creates a variable by binding a value to a symbol in the currently executing scope. If we run define at the top level of our program, this will be the global scope and this binding will be visible everywhere in our program. (Unless it is shadowed by another binding of the same symbol, which we will get to later…)
; define a variable by binding the symbol 'a' to the value 99
(define a 99)
s4m> 99
This function has a side-effect, meaning it does something other than just return a value. Its side effect is binding the variable. In s7 (but not all Schemes), define also returns the value that was bound. Which means we could, if we really wanted, do something like this:
; both b and a will be bound to 99
; not recommended, here for illustration only!
(define b (define a 99))
s4m> 99
Evaluation does not always mean calling a function. If we evaluate a form that is not a function call, we get something back, with what that something is depending on the form. Evaluating a basic type returns the value itself (no change) and evaluating a variable returns the value bound in the variable.
; evaluating a simple type like a number returns the value
99
s4m> 99
(define foo 99)
s4m> 99
; evaluating a variable returns the value bound to the variable
foo
s4m> 99
Once a variable has been created, we can assign a new value to it with the set! function. It’s a common Scheme convention to name functions with side-effects with a trailing exclamation mark. In s7, set! also returns the value set. We can only set a variable that has already been defined. In s7 (but not all Schemes), we can also set a new value on an existing variable by just redefining.
(define a 99)
s4m> 99
a
s4m> 99
(set! a 100)
s4m> 100
a
s4m> 100
(define a 101)
s4m> 101
a
s4m> 101
(set! z 999)
s4m> ERROR unbound variable z
Functions¶
Functions are defined using the special form lambda. Evaluating a lambda form will return an anonymous function, which we can in turn bind to a variable.
The lambda form takes two clauses: a parameter list and a body. The parameter list specifies the local bindings that will be active in the body of the function, based on the arguments passed in. The body gets evaluated when we call the function, with whatever arguments are passed in at call time substituted for the parameters.
; a lambda expression that takes an argument, x, and returns x + 1
; it returns a lambda procedure
(lambda (x) (+ 1 x))
s4m> #<lambda (x)>
; the same, but binding the function to the symbol my-fun
(define my-fun (lambda (x) (+ 1 x)))
s4m> my-fun
; now call the function
(my-fun 2)
s4m> 3
; this means we could just nest the lambda form in order to call it
; but this is not very readable, so less commonly done
((lambda (x) (+ 1 x)) 3)
s4m> 4
; a lambda form specifying a procedure with two parameters
(define my-adder (lambda (a b) (+ a b)))
s4m> my-adder
(my-adder 3 4)
s4m> 7
There is a shortcut in Scheme, (sometimes called “defun” notation, from Common Lisp), that allows us to define functions without explictly using lambda. Under the hood, it’s exactly the same.
; define a function called add-1, that adds 1 to its argument
(define (add-1 x) (+ 1 x))
s4m> add-1
; this is no different from the below
(define add-1 (lambda (x) (+ 1 x)))
; in S7 we could do this, because define returns the value bound
; again, not recommended, but a useful illustration
((define (add-1 x) (+ 1 x)) 2)
s4m> 3
Some texts only use the lambda form as it is more explicit, and thus clear what is going on. We will use both as space can be at a premium in a Max patch!
Output in Scheme For Max¶
In Scheme for Max, we have two functions we will use all the time for output, out and post. out is used to send values out the s4m object’s outlets. It takes two arguments, the outlet number, and the value to be sent out. In Scheme For Max, we call the first outlet “outlet 0”.
out is an example of a function that is called purely for its side-effect - output a number. We send output out a lot, so we don’t necessarily want to see every value sent out showing up in the Max console. For this reason, out returns null. This way, if our Scheme for Max object’s log-null attribute is false (the default), we will not see any console activity on a call to out.
In Scheme, null is technically the null list, and it’s printed representation is (). We will explain why later on. For now, just know this is null, and it means “empty value”.
; send the number 99 out the first outlet
; this function also returns the null list
(out 0 99)
; pretend we set @log-null to 1
(out 0 99)
s4m> ()
From now on, the tutorial will not always show the returned null value, such as after calls to post, as it does clutter up examples.
If we want to send out multiple values, so that the output is a Max list message, we use the list function:
; send the list 1 2 3 out the first outlet
; the list function returns a list
(out 0 (list 1 2 3))
The post function logs to the Max console. It accepts any number of arguments, automatically converting them to string representations and putting spaces between them. Because its being called for its side effect, it returns null. You’ll see that output in the console from post is prefixed with s4m: (with a colon), whereas the repl return prompt is s4m> (with a greater-than sign).
; post to console, with log-nulls set to true
(post 1 2 3)
s4m: 1 2 3
s4m> ()
; post a variable
(define a 99)
s4m> 99
(post "a is" a)
s4m: a is 99
s4m> ()
During development, it can be helpful to attach a print s4m-out: object to your outlet, which will additionally print the output from our s4m object’s outlet to the console as well:
; shows return value (if @log-nulls is 1) and the printed output from our print object
(out 0 :foobar)
s4m> ()
s4m-out: :foobar
Basic types¶
Scheme is dynamically typed, meaning that we do not have to specify in advance of what type a variable will be, and a variable’s type can be changed by setting it to a new value of a different type. But variables do have types.
Booleans and Predicates¶
In Scheme, we use #true and #false for boolean values, which can also be written as #t and #f. A predicate function is a function that checks the value of an expression against some criterion and returns a boolean. In Scheme, predicate functions normally have names ending in a question mark.
; make a boolean variable
(define my-boolean #t)
s4m> #t
; check if it is a boolean
(boolean? my-boolean)
s4m> #t
Some other useful predicates:
; check if a variable is a function/procedure with procedure?
(procedure? post)
s4m> #t
; the defined? predicate checks if a symbol is bound to a variable
(defined? foo)
s4m> #f
(define foo 1)
s4m> 1
(defined? foo)
s4m> #t
We can check whether something is null with the null? predicate.
; the out function returns null, so...
(null? (out 0 99))
s4m> #t
As an aside, remember that null is actually the null list, meaning that using the list? predicate on the return value of a call to out will also return true:
; the out function returns null, and null is the null list, so...
(list? (out 0 99))
s4m> #t
; just for fun...
(boolean? (list? (out 0 99)))
s4m> #t
Numerical Types¶
Like most programming languages, Scheme supports integers and floats, but in Scheme, both are sub-types of the number type. In Scheme, floats are inexact numbers, while integers are exact numbers. Unlike many other languages, Schemes also support fractions as a type, which is very helpful in music. There are number of predicate functions and conversion functions for working with numeric types, and there are some rules for automatic conversion you will want to know. The examples below provide enough to work with in Max, and for further details you can consult various online resources. (Dybvig is good here.)
; make an integer
(define x 1)
s4m> 1
(integer? x)
s4m> #t
(define y 2.0)
s4m> 2.0
; y is not an integer
(integer? y)
s4m> #f
; y is an inexact number
(inexact? y)
s4m> #t
; but both x and y are numbers, and real numbers
(and (number? x) (number? y)
s4m> #t
(and (real? x) (real? y))
s4m> #t
; mixing inexacts and exacts creates other inexacts
(/ 1 0.5)
s4m> 2.0
; integer math creates fractions
(define z (/ 3 4))
s4m> 3/4
; these are still exact
(exact? z)
s4m> #t
; which we can later cast to inexact
(exact->inexact (/ 3 4))
s4m> 0.75
; exacts stay exact until mixed with inexact
(* 1.0 (/ 3 4))
s4m> 0.75
Because of the support for fractions, we can stay exact through a chain of operations, only converting at the end, a vastly preferable situation for converting tuning or timing fractions compared to languages like JavaScript or C. This does mean that we need to be more explicit in coversions however, and so there are some helpers in the form of floor, ceiling, and round.
(floor 1.1)
s4m> 1.0
(ceiling 1.1)
s4m> 2.0
(round 1.5)
s4m> 1.0
(round 1.51)
s4m> 2.0
Symbols¶
Symbols are identifiers in Scheme that can be used as the name for functions and variables. Symbol names can use more characters than in most languages, because Lisps only use whitespace and parentheses for syntax. In Scheme, it’s common to include hyphens, exclamation marks, and questions marks in names.
; symbols for predicates usually end in question marks
(define is-one? (lambda (x) (= 1 x)))
Evaluating a symbol returns the value stored at that symbol:
(define answer 42)
sm4> 42
answer
s4m> 42
Strings and characters¶
Scheme also has a string type and a character type. Now strictly speaking, Max doesn’t really do strings - to Max they are just symbols with quotation marks. So we won’t discuss either of these in much detail, especially characters. A good rule of thumb in Max is to avoid strings unless you need a string. In Scheme, Strings use double quotes.
(define foo "foo")
s4m> "foo"
(define bar "bar")
s4m> "bar"
; join strings with string-append
(string-append foo bar)
"foobar"
s7 includes a variety of string conversion routines, which one can look up in the online Scheme references (Dybvig is my recommendation). Some of the more useful ones are:
(number->string 1)
s4m> "1"
(string->number "1")
s4m> 1
; note that string->number and number to string are smart about floats
(string->number "1.0")
s4m> 1.0
; and even fractions!
(string->number "3/4")
s4m> 3/4
; of course, there's a predicate...
(string? (number->string 1))
s4m> #t
We can also go back and forth between symbols and strings.
; make a symbol from a string
(symbol "foo")
s4m> foo
; and its predicate
(symbol? (symbol "foo"))
s4m> #t
; round and around
(string? (symbol->string (symbol "foo")))
s4m> #t
There are also functions for extracting characters from strings and building up strings, but I don’t find myself using these much in Max, so we’ll leave this to the reader to explore online. That’s all we’ll say about strings in this crash course.
Lists - an introduction¶
Lists are the most important compound data type in Lisps, including Scheme. So much so that Lisp originally stood for “List Processing”! We’ll be looking at lists in detail later, but right now we have a bit of a chicken-and-egg situation: we need to know at least a little bit about them for the next section to make sense.
We make a list using the list function:
; make a list
(list 1 2 3)
s4m> (1 2 3)
; store a list in a variable
(define l (list 1 2 3))
s4m> (1 2 3)
We can retrieve individual members of a list by index using list-ref, and we can set them using list-set!:
; get value of l at index 0
(list-ref l 0)
s4m> 1
; set value of l at index 0
(list-set! l 0 99)
s4m> 99
; eval the variable, and we get the (updated) list
l
s4m> (99 2 3)
In s7, we can also use what is called applicative-syntax, where we use a list in the function slot of a paranthetical expression, and put the index in the argument slot. Note that the syntax for set is a bit unusual, we use the syntax for getting an item to refer to a location, and the location is the argument to set!:
; get value of l at index 0, applicatively
(l 0)
s4m> 1
; set using applicative syntax
(set! (l 0) 100)
s4m> 100
l
s4m> (100 2 3)
Lists look at first like an array in other languages, but under the hood, lists in Lisp are actually implemented as linked lists. There is a whole family of functions for working with lists as linked-lists, and we’ll get to those soon.
The astute reader will have noticed that the printed representation we get back when evaluating a variable that holds a list (or a call to the list function), looks an awful lot like an s-expression. In the above example, it looks just like a call to a function called “100”. Hold that thought, it’s going to become very important!
Evaluation and quoting¶
At this point, we are able to make variables and functions, and we know about basic types and lists. It’s time for our first look at what make the Lisp family of languages unusual.
When we send an s-expression or atom to the interpreter to run, we are asking the interpreter to evaluate the expression. We can also do this explicitly using the eval function. In the case of a basic number or string, evaluation doesn’t change anything - it returns the same value:
; send a number to the interpreter, and we get the same thing back
99
s4m> 99
; as evaluating doesn't change it, the eval function won't either
(eval 99)
s4m> 99)
; thus nesting evals of a number doesn't either
(eval (eval 99))
s4m> 99
; strings also evaluate to themselves
(eval "foobar")
s4m> "foobar"
However, when we evaluate a symbol, the evaluation process returns that which the symbol points to. Which of course requires that this symbol is either bound in the language, or that we have by bound it ourselves by defining using the symbol. The value pointed to could be an atomic data item, in the case of a variable, or a function, in the case of a function name:
(define my-var 99)
s4m> 99
my-var
s4m> 99
(eval my-var)
s4m> 99
(define (add-1 x) (+ 1 x))
s4m> add-1
; evaluating the symbol that points to the function returns the function
add-1
s4m> add-1
(eval add-1)
s4m> add-1
But what if we evaluate a list? Hang on to your hats!
; evaluate a list
(eval (list 1 2 3))
s4m> Error; attempt to apply an integer 1 to (2 3) in (1 2 3)?
We get an error message about “applying an integer”, giving us a clue what’s going on. Let’s try that again, but instead of the just using the list function, we will add the use of the symbol function, which we recall creates a symbol from a string:
; make the symbol post, from a string
(symbol "post")
s4m> post
; make a list, starting with the symbol
(list (symbol "post") 1 2 3)
s4m> (post 1 2 3)
; evaluate this list, and we see we have called the post function
(eval (list (symbol "post") 1 2 3))
s4m: 1 2 3
s4m> ()
; or more concisely ...
(eval (list post 1 2 3))
s4m: 1 2 3
s4m> ()
Now we can see what is going on. Evaluating a list is the same as calling a function. Literally the same. The first element of the list is taken as pointing to a function, and the rest are used as its arguments. Scheme syntax consists of lists. We can build them with functions or special forms, and we can call them as functions with eval, but really it’s all lists.
Eval has a counterpart that does its opposite, called quote. When we use quote, we tell the interpreter to skip evaluation of something that it would otherwise evaluate. In a normal function call, expressions used as arguments are evaluated prior to the function call, and the values returned are passed to the function as arguments. For example:
; define a function that prints its argument
(define (my-post x) (post "in my-post, x is:" x))
s4m> my-post
; my-post gets passed the value returned by evaluating (+ 1 2)
(my-post (+ 1 2))
s4m: in my-post, x is: 3
s4m> ()
If we use quote, we tell the interpreter not to evaluate the expression and use the result as x, but rather to pass the expression itself, as code, in as a argument:
(my-post (quote (+ 1 2)))
s4m: in my-post, x is: (+ 1 2)
s4m> ()
This is used so frequently in Lisps that is has a special shortcut syntax, the single quote character:
(my-post '(+ 1 2) )
s4m: in my-post, x is: (+ 1 2)
s4m> ()
When we use the single-quote, it indicates that the rest of the immediately following s-expression should be used as it is written in code, not as it would evaluate. If we use it in front of a parenthetical expression, it thus returns a list, instead of calling a function:
; this returns the result of calling + with the args 1 and 2
(+ 1 2)
s4m> 3
; whereas this returns a list, the first element of which is +
'(+ 1 2)
s4m> (+ 1 2)
This means quote is also a shortcut for making lists:
(define l '(+ 1 2 3))
s4m> (+ 1 2 3)
l
s4m> (+ 1 2 3)
; now call that list as a function
(eval l)
s4m> 6
We can also use quote in front of a symbol to indicate that we want the symbol, not the value at which the symbol points. This will work even if the symbol has not been used to define a variable.
; make a list of symbols a b c
(list 'a 'b 'c)
s4m> (a b c)
; which is precisely equivalent to quoting the whole expression
'(list a b c)
s4m> (a b c)
; we could evaluate this, which will work if a b c are defined
; and a is function, but be an error if they are undefined
(eval '(a b c))
s4m> Error: unbound variable a in (a b c)
; an example that works
(define foo 99)
(eval '(post foo))
s4m: 99
s4m> ()
Quote and eval are opposites, so we can nest them as much as we want:
(eval '(post "hello world"))
s4m> hello world
(eval (quote (eval '(post "hello world"))))
s4m> hello world
Keywords¶
Some Lisp dialects, including s7, have keywords. A keyword is a symbol that starts with a colon and always evaluates to itself. A keyword can not be bound to anything other than itself - it can’t be the name of a variable or function. In this way, it acts like a simple type, such as a string or number. This also means a variable can hold a keyword, but a keyword can’t be a variable.
When we get to hash-tables and dictionaries, you’ll see that keywords are commonly used as keys. Conveniently, Max will let us use them in many places as well, including table and dict names.
; evaluating a keyword has no change
; much like evaluating a simple type
:my-keyword
s4m> :my-keyword
(define var-holding-a-keyword :my-keyword)
s4m> :my-keyword
(eval var-holding-a-keyword)
s4m> :my-keyword
; but no using them as variable names!
(define :my-keyword 99)
s4m> Error: keywords are constants
We will use quoting and evaluation a lot in Max, so keywords are very helpful. We can see at a glance that a symbol starting with a colon is a keyword, no matter the context. It doesn’t matter if we’re not sure whether it will get evaluated, because evaluation won’t change anything. This can make our Max code more readable when we use keywords in Max messages that we are going to send to the s4m object to evaluate.
Lists, in more depth¶
As we previously discussed, under the hood, Lips lists are linked-lists. In the computer memory, every cell in a list includes a value, and a pointer to the next item. The last item in a list has a pointer to a hidden cell that holds the null list. So if we look at a list of three elements, ‘(1 2 3), there are three cells with numbers and pointers, and one hidden cell with the null list, to which the third cell’s pointer points. Or another way of thinking of it is that there are three cells, the last of which points to the null list, which is a special case.
In this section we will look briefly at the classical Lisp list functions. I will admit these Lisp list functions have bizarre names: car, cdr, cons, etc. While these names seem annoying at first, they have stuck around as they are easy to type, and will become second nature pretty quickly. (They originally come from operating instruction names on very old IBM computers!)
We can get the first item of a list using the car function, and we can get the rest of the list, by using the cdr function. We can think of the combination of car and cdr as taking off the head of the list, which leaves us with one single item (the car) and the remaining linked list (the cdr). Thus cdr, if called on a proper list, always returns a list. Though the list it returns could be the null list, if the head was the last proper item. An example is worth a thousand words here:
; a list
(define l (list 1 2 3))
s4m> (1 2 3)
; get the car of l
(car l)
s4m> 1
; get the cdr of l, it's always a list
(cdr l)
s4m> (2 3)
Because cdr returns a list, we can get the cdr of a cdr - this is like chopping off the head twice - and we still get a list:
; get the cdr of cdr of l
(cdr (cdr l))
s4m> (3)
; note the above is a *list* with 3, not 3 itself!
; the very last cdr is the null list
(cdr (cdr (cdr l)))
s4m> ()
; which can be checked with the null? predicate
(null? (cdr (cdr (cdr l))))
s4m> #t
; but is also still a list!
(list? (cdr (cdr (cdr l))))
s4m> #t
So it’s important to remember that a proper list is a set of value/pointer entries, where the last one points to the null list. The value-pointer pairs have a special name: cons cells.
In addition to making lists with the list function, we can use the cons function. The list function does the magic for us, while cons involves us in the underlying linked-list. We use cons to add a new cons cell by passing in an item, and a list that our new cell should link to.
; extend our list at the front
(cons 0 (list 1 2 3))
s4m> (0 1 2 3)
Note that cons makes a new list. This is an important distinction. Making a new list by adding a cell to the head doesn’t change an old list starting at a different head:
(define list-a (1 2 3))
s4m> (1 2 3)
(define list-b (cons 0 list-a))
s4m> (0 1 2 3)
list-a
s4m> (1 2 3)
list-b
s4m> (0 1 2 3)
In the above example, the cdr of list-b is list-a.
To make a list from scratch with cons, we work backwards, starting with the null list. And we make the null list by quoting the printed representation of an empty list, ‘().
(null? '())
s4m> #t
; make a list by cons'ing to the null list
(cons 3 '())
s4m> (3)
; make a list by cons'ing 3 times
(cons 1 (cons 2 (cons 3 '())))
s4m> (1 2 3)
If we want to add to the end of a list, we need to use the append function, which takes multiple lists as arguments returns a new list consisting of the joined argument lists. This means that, unlike cons, the item to be added needs to itself be a list. Like cons, the result is a new list, and the original lists are unchanged.
; make a list, by joining two lists
(append (list 1 2 3) (list 4 5 6))
s4m> (1 2 3 4 5 6)
; add one item to a list
(define l (list 1 2 3)
s4m> (1 2 3)
(append l (list 4))
s4m> (1 2 3 4)
; note that l is unchanged!
l
s4m> (1 2 3)
; or with quote
(append l '(5))
s4m> (1 2 3 4 5)
Append can have as many arguments as you want
(append (list 1 2) (list 3 4) (list 5 6))
s4m> (1 2 3 4 5 6)
Note that if you call append with a final element that is not a list, you won’t get an error… but you also won’t get a proper list. This is because the final item is an atomic value instead of a value/pointer pair.
(append (list 1 2) 3)
s4m> (1 2 . 3)
The dot before 4 indicates that the list stopped being a proper list at the third item. Improper lists are used in various places, but most typically as pairs, also called dotted pairs. We get them when we use cons, without ending our chain with the null list:
; consing to an atomic value produces a dotted pair
(define my-pair (cons 1 2))
s4m> (1 . 2)
Under the hood, a dotted pair consists of two cells: the first has a value and a pointer to the next cell, and the second has only a value. This means we can still use car and cdr, but the cdr returns an atomic value instead of a list, and there is no cdr of the second element.
; consing to an atomic value produces a dotted pair
(define my-pair (cons 1 2))
s4m> (1 . 2)
(car my-pair)
s4m> 1
(cdr my-pair)
s4m> 2
(cdr (cdr my-pair))
s4m> Error: cdr argument 2 is an integer, but should be a pair.
Dotted-pairs and improper lists are important to understand as you’ll use them when looping through data structures such as association lists and hash-tables, both of which have pairs of key and value.
List accessor shortcuts¶
Finally, and these gets a bit silly but are sometimes convenient, there are shortcuts for combinations of car and cdr for working with nested lists. These can always be replaced by nested combinations of car and cdr, so you don’t need to know them. But you are quite likely to see them in other Lisp code, so it’s worth knowing they exist. And they can make some code more readable - or at least, to someone who knows these oddball functions!
; a nested list
(list (list 0 1) (list 2 3) (list 4 5)))
s4m> ((0 1) (2 3) (4 5))
; car of nested list
(car (list (list 0 1) (list 2 3) (list 4 5)))
s4m> (0 1)
; cdr of nested list
(cdr (list (list 0 1) (list 2 3) (list 4 5)))
s4m> ((2 3) (4 5))
; caar gets the car of the car
(caar (list (list 0 1) (list 2 3) (list 4 5)))
s4m> 0
; cdar gets the cdr, of the car - which is a list
(cdar (list (list 0 1) (list 2 3) (list 4 5)))
s4m> (1)
; cadr gets the car, of the cdr
; aka the first item of the cdr of the outer list
(cadr (list (list 0 1) (list 2 3) (list 4 5)))
s4m> (2 3)
; cddr gets the cdr of the cdr, which is a list of lists
(cddr (list (list 0 1) (list 2 3) (list 4 5)))
s4m> ((4 5))
This continues on to 5 letter combinations, like cadar, and honestly, you don’t need to know these. But as you may well encounter code with functions consisting of strings of c,a,d, and r, now you’ll know what you’re seeing. And maybe they’ll help in a game of Scrabble with programmers.
Optional function arguments¶
Now that we know about lists, we can use them for creating functions that can be called with a variable number of arguments. (Also known as “multi-arity functions” if you want to use fancy computer science terms…) This is done by using dotted notation in the function argument, which will put any arguments past the explicitly named arguments into a list. This list will be the null list if no additional arguments are given:
; one mandatory argument x, and 0 or more optionals
; that go in the list 'args
(define (my-fun x . args)
(post "called with" (length args) "optional args")
(post "optional args:" args))
s4m> my-fun
(my-fun 1)
s4m: called with 0 optional args
s4m: optional args: ()
s4m> '()
(my-fun 1 2 3)
s4m: called with 2 optional args
s4m: optional args: (2 3)
s4m> '()
This can be done with lambda as well, but lambda has an additional option. If the argument list for a lambda is only one symbol, this symbol will be bound to a list of all the arguments.
; a lambda that bundles all its args into a list
(define my-lambda (lambda args (post "args:" args)))
s4m> my-lambda
(my-lambda 1 2 3)
s4m: args: (1 2 3)
s4m> '()
s7 Scheme borrows heavily from Common Lisp, and includes two non-standard special forms, define* and lambda*, that give us the ability to use keyword arguments with default values in our function definitions. We do this by using lists of key and default value in place of arguments. To call the function with a keyword argument, we pass in a keyword and a value pair for that argument. This is most easily explained with the example below, taken straight from the s7 documentation:
; a function with one required argument, a, and two optional
; keyword args, b & c, with default values of 32 and "hi"
(define* (hi a (b 32) (c "hi"))
; returns a list of the arguments
(list a b c))
s4m> hi
; call hi with only one argument and we get the defaults
(hi 99)
s4m> (99 32 "hi")
; call hi with three arguments, and we use them all
(hi 99 88 77)
s4m> (99 88 77)
; call hi with one argument and one keyword argument
(hi 99 :c 77)
s4m> (99 32 77)
Vectors¶
Lists do have some disadvantages. Linked lists need to be traversed to get to their contents, which means that accessing elements deep in a long list can be slow. And adding items to the end of a list requires copying the entire list with append. In music situations, we often need to access anywhere in a sequential data structure, or add items at the end of a table, so for these types of cases, a more appropriate type is the vector. Like lists, vectors can hold any data type, and can hold multiple data types within a vector. If we want to model Max data that would be in a buffer or table in Max, the vector is likely what we want.
Note that the printed representation of a vector starts with # to differentiate it from a list.
; create a vector, containing 1 2 3 4
(define v (vector 10 11 12 13))
s4m> #(10 11 12 13)
; get its length
(vector-length v)
s4m> 4
; is it really a vector?
(vector? v)
s4m> #t
; access an element
(vector-ref v 2)
s4m> 12
; or with applicative syntax
(v 0)
s4m> 10
; set with vector-set!
(vector-set! v 0 99)
s4m> 99
v
s4m> (99 11 12 13)
; or with applicative syntax
(set! (v 0) 100)
s4m> 100
; make a vector using quote and the # sign
(define v '#(0 1 2 3))
s4m> #(0 1 2 3)
Note that Max only has a list type for messages, so when we cross the Max to Scheme boundary and vice versa, it’s worth thinking about which type is appropriate. Vectors can be converted to and from lists easily, and S4M will use vectors instead of lists in places where that makes sense. For example, in reading a Max dictionary into Scheme, arrays in the dictionary will be converted to vectors instead of Scheme lists. And s4m has functions for copying from tables and buffers to vectors, and vice versa. We won’t cover those here, but they are detailed in the s4m documentation.
; conversions
(vector->list '#(0 1 2 3))
s4m> (0 1 2 3)
(list->vector '(0 1 2 3))
s4m> #(0 1 2 3)
We can also make a vectors without specifying first what they will hold with make-vector:
; make a 4 point vector
(make-vector 4)
s4m> #( #<unspecified> #<unspecified> #<unspecified> #<unspecified> )
; this is more useful if we pass a starting value
(make-vector 4 0)
s4m> #(0 0 0 0)
s7 supports multi-dimensional vectors. We create these by passing a list to make vector where the vector size argument goes. The lists specifies the size in as many dimensions as we want.
; make a 2 x 3 vector, initialized to 0
(define v2x3 (make-vector (list 2 3) 0))
s4m> #2d((0 0 0) (0 0 0))
; read from the vector
(v2x3 1 2)
s4m> 0
; set with applicative syntax
(set! (v2x3 1 2) 99)
s4m> 99
v2x3
s4m> #2d((0 0 0) (0 0 99))
s7 has quite a few interesting additional vector functions, especially around multi-dimensional vectors, that you can read about on the official s7 page.
Hash-Tables¶
Hash-tables are key-value stores, similar to dictionaries in Python or JavaScript. A key can be anything we’d like, but it’s most common to use a keyword as a key, or barring that, a symbol. This is also the most compatible with Max’s implementation of dictionaries, so I’d recommend sticking to them whenever possible.
; create a hash-table, with keys :a and :b
(define my-hash (hash-table :a 1 :b 2)
s4m> (hash-table :a 1 :b 2)
; read value at :a
(hash-table-ref my-hash :a)
s4m> 1
; set value at :b
(hash-table-set! my-hash :b 99)
s4m> 99
Asking for a value that is not in a hash-table returns #f, and we can remove an item from a hash-table by storing #f at the key. We can put a new item in the hash-table by setting it’s value with a key.
; ask for a value not in our hash
(hash-table-ref my-hash :c)
s4m> #f
; add :c entry
(hash-table-set! my-hash :c 99)
s4m> 99
; delete entry :b by setting it to #f
(hash-table-set! my-hash :b #f)
s4m> #f
; inspect our hash now, b is now gone
my-hash
s4m> (hash-table :a 1 :c 99)
As noted earlier, s7 Scheme supports applicative syntax for compound data types, and this works for hash-tables too, allowing us to get a value from a hash-table by calling the hash-table as a function with the key as an argument:
; get :a, with applicative-syntax
(my-hash :a)
s4m> 1
As with lists, calling the hash-table with a key gives us a memory location, and we can thus also use this with set!:
; set :a, with applicative syntax
(set! (my-hash :a) 42)
s4m> 42
Hash-tables can be nested.
(define deep-hash (hash-table :a 1 :b (hash-table :c 3 :d 4)))
s4m> (hash-table :a 1 :b (hash-table :c 3 :d 4))
Applicative syntax is very helpful for nested hash-tables. Note that this syntax only works for applicative syntax, not for hash-table-ref:
; get contents of :c, at contents of :b
(deep-hash :b :c)
s4m> 3
We can set this way too:
; set :b :c
(set! (deep-hash :b :c) 99)
s4m> 99
Be aware though, that trying to use a chain of keys is an error past the first non-existent key, for either getting or setting:
(define deep-hash (hash-table :a 1 :b (hash-table :c 3 :d 4)))
s4m> (hash-table :a 1 :b (hash-table :c 3 :d 4))
(deep-hash :z)
s4m> #f
(deep-hash :a :z)
s4m> #f
(deep-hash :z :x)
s4m> Error....
(set! (deep-hash :z :y :x))
s4m> Error....
If we stick to simple types as keys (numbers, symbols, keywords), we can convert hash-tables to Max dictionaries and vice versa, writing and reading from Max dictionaries. See the Scheme For Max documentation for details on these functions.
Branching with if¶
In Scheme, we can branch using one of two special forms: if and cond. These are both special forms - they look like function calls but are not evaluated the same way as functions. The if special form takes three clauses. The first is the predicate, that which is tested to determine which branch we take. The second is the expression that is evaluated and returned if the predicate evaluates to true. And the third is the expression that is evaluated and returned if the predicate fails. Thus the value returned by an if expression is the value of evaluating either the first or second result clause. These clauses can be either simple values, or s-expressions that are evaluated to return a value. The reason if is a special form is that the s-expressions for the clauses only evaluate if that clause is to be returned.
; return 99 if test-var is 33, else return 66
(define test-var 99)
s4m> 99
(if (= 99 test-var) 33 66)
s4m> 33
; using the above to set a variable
(set! my-var (if (= 99 test-var) 33 66))
s4m> 33
; an if statement that returns the results of sexp evaluation
(if (= 99 test-var)
(+ 32 1)
(+ 66 4))
s4m> 33
Grouping statements with begin¶
So far, if looks just like a function. The fact that it is not a function is illustrated if we put side effects in our two clauses. If we want to add a side effect to a clause that will return a value, we can enclose child expressions in a begin statement. All expressions in the body of the begin are evaluated, but only the last expression is returned.
(begin 1 2 3)
s4m> 3
;; an if statement that returns the results of sexp evaluation
(if (= 1 1)
(begin (post "first clause!") (+ 32 1))
(begin (post "second clause!") (+ 66 4)))
s4m: first clause!
s4m> 33
When we run the above, we see that our console only shows the output from the first clause. Were if a function, we would see the output from both clauses, because of the fact that expressions are evaluated from the inside out. The fact that if breaks the rules of normal function execution is what makes it a special form.
We don’t need to use a begin statement, we could just put side effect expressions in the slots, as long as we have made sure that it’s ok that the entire if form evaluates to whatever is returned in the clause (i.e. the null list, potentially).
In s7, we can skip the final clause in an if statement, in which case the return value of the if is unspecified if the predicate fails.
;; if var = 1, if evaluates to null, else to unspecified
(define var 2)
s4m> 2
(if (= var 1)
; post returns null, so the if will too
(post "first clause!"))
s4m> <unspecified>
This is a good time to discuss predicates and truth in Scheme, because it’s a bit different from what you may be used to other languages.
In Scheme, only #false is false.
Repeat that three times, because if you’re coming from other languages, this will get you! False can be written as either #f or #false, but nothing else ever equals false. Not zero (like C), not the null list (like Common Lisp), not an empty data structure. Nothing except #false!
;; only false is false!
(if 0
(post "I post! Unlike in C family languages.")
(post "but I don't, because I never get evaluated!") )
Conveniently, this works out rather well in Max, because Max has no notion of boolean True or False. In Max, we express booleans with 1 or 0. Which means that we can indicate an invalid Max value using Scheme’s #false, and we can test for a valid (or existing) value by using the value in a predicate. This will come in handy when we get to dictionaries and hash-tables.
Scheme has many predicate functions built in, some of which we’ve seen already. However, it’s worth mentioning that not all Scheme implementations have the same predicates built in, so if you look up a predicate online, you probably want to test it in the REPL to make sure it’s in s74, or add it to your base file. I added some in the s74 shim layer, which you can inspect by looking at the S74.scm file in the Scheme For Max Package.
Testing equality¶
Testing equality in Scheme is a bit different than you might be used to in other languages as well.
Numeric equality is tested with =, but note that unlike almost all the other predicates, we don’t use a question mark. Types of numbers (integers, floats, fractions) will be properly cast to each other:
; testing numbers for equality
(= 1 1.0)
s4m> #t
(= 1 2/2)
s4m> #t
(define a 1)
s4m> 1
(= a 1.0)
s4> #t
Testing whether non-numeric values are the same can be done with eqv?. This tests whether the pointers point to the same thing.
; two variables holding the same list are equivalent
(define a (list 1 2 3))
(define a-alias a)
(eqv? a a-alias)
s4m> #t
; but not equivalent to some other list with the same values
(eqv? a (list 1 2 3)
s4m> #f
; this works for functions and symbols too
(define var-pointing-to-post post)
(eqv? var-pointing-to-post post)
s4m> #t
(define the-sym 'my-symbol)
(eqv? the-sym 'my-symbol)
s4m> #t
(eqv? 'my-symbol 'my-symbol)
s4m> #t
; simple types are equivalent only if no cast is involved
(eqv? 1 1)
s4m> #t
(eqv? 1 1.0)
s4m> #f
Testing whether compound types are the same, element by element, can be done with equal?. This tests the contents of the compound type, as opposed to where the pointers point.
; test a list
(equal? (list 1 2 3) (list 1 2 3))
s4m> #t
(define l1 (list 1 2 3))
(define l2 (list 1 2 3))
; their contents are the same
(equal? l1 l2)
s4m> #t
; but they don't point to the same address in memory
(eqv? l1 l2)
s4m> #f
; this works for strings, symbols, and keywords too
(equal? "foo" "foo")
s4m> #t
(equal? 'foo 'foo)
s4m> #t
(define keyfoo :foo)
(equal? keyfoo :foo)
s4m> #t
There is one more variant, eq?. In s7, eq? is almost entirely the same as eqv?, but this is not always the case in all Scheme implementations. For the most part, in s7 you can just use eq? and eqv? interchangeably. Different implementations vary in their treatment of the empty list (the “null list”), which we will cover in detail later, so if you’re dealing with the nulls and equivalence, it’s a good idea to check it.
; is the null list the same as the null list?
; s7 says yes! (not all do)
(eq? (list) (list))
s4m> #t
(eqv? (list) (list))
s4m> #t
When in doubt, test your equality checks in the repl! But in general, for numeric equivalence use =, non-numeric and compound type equality use equal?, and pointer comparison use eq? and/or eqv?.
Logical operators: and, or, not¶
Testing complex conditions often requires logical operators, for which Scheme provides us with and, or, and not.
; and returns true only if all predicates return true
(and (= 1 1) (> 2 1) (< 1 2))
s4m> #t
; or returns true if any return true
(or (= 1 2) (= 1 1))
s4m> #t
; not returns the negation of a boolean
(not (or (= 1 2) (= 1 1)))
s4m> #f
These are special forms, not regular functions, meaning that evaluation doesn’t follow the regular function evaluation rules of evaluating all subexpressions and passing the results in as arguments. Rather, these short-circuit. This can be useful if we want to evaluate some expressions only if previous expressions have returned either true or false. Remember, in a boolean context, only #false is #false!
; evaluate the second expression only if the first is true
; the return value is from the last *evaluated* expression
(and (= 1 0) (post "I don't get to run!"))
s4m> #f
If and were a function, we would see our post statement running regardless of the result of the first expression, when in fact, it only executes if all expressions return a non-false value:
(and (= 1 1) (post "I ran!"))
s4m: I ran!
s4m> ()
; add another non-false expression and it will be the return value
(and (= 1 1) (post "I ran!") 42)
s4m: I ran!
s4m> 42
This can be used with or as well, with expressions evaluating until one of them returns true. This can be a convenient way to make something happen if a previous something returns false. For example, we know that a hash-table returns false if asked for a non-existent key, so this can be used to assign a fall-back value:
(define h (hash-table :a 1 :b 2))
s4m> (hash-table :b 2 :a 1)
; get the value at a key, or some fall-back value
(or (h :a) 99)
s4m> 1
; looking up :c returns false, so we get 99
(or (h :c) 99)
s4m> 99
Branching with cond¶
The cond special form allows us to provide a series of predicate and result pairs. Evaluation stops when the first predicate passes. When combined with predicates and logical operators, this gives us everything we need to implement complex control flow.
; return some numbers for several values of x
(cond
((= x 1) (+ 9 x))
((= x 2) (+ 8 x))
((= x 3) (+ 7 x)))
; to illustrate that these are just pairs of expressions,
; here's a cond that returns 99
(cond (#f #f) (#t 99))
If no clause succeeds, cond will return unspecified (at least in S7!). To avoid this, it is common to return #f in an else clause. Interestingly, else is just a short-form for returning true - all we need is a predicate that passes.
; return 10 for several values of x, or false for unhandled instance
(cond
((= x 1) (+ 9 x))
((= x 2) (+ 8 x))
(else #f))
; because only false is false, this technically works too
; but you won't be popular coding like this....
(cond
((= x 1) (+ 9 x))
((= x 2) (+ 8 x))
(0 #f))
Unlike if, we don’t need to bundle up expressions with begin in a cond clause to create side effects. The cond clause will run as many expressions as we provide for each clause
; branching with side effects
(cond
((= x 1)
(post "x is 1")
(+ 9 x))
((= x 2)
(post "x is 2")
(+ 8 x))
(else
(post "unhandled x!")
#f))
Scopes with the let statement and inner defines¶
In computer science, ‘scope’ referes to where and when the binding of a symbol to a variable or function is in effect. Scheme is a lexically scoped language, allowing us to use functions and scopes in powerful ways, some of which we will look at in this book. To use Scheme effectively, and to take advantage of its lexical scoping for real time interactivity in Max, we need to understand Scheme scoping and how to use the let form.
When we make definitions in scm file or send them to the interpreter from Max messages, bindings execute in the global scope, also refered to as the “top-level scope”. These bindings are visible in any other expression or function, unless shadowed by bindings local to the expression or function.
; make a global variable
(define var 99)
s4m> 99
; define a function, it can access var
; if we tried to run this function prior to defining var
; we'd get an error
(define (my-fun)
(post "var:" var)
; return var + 1
(+ 1 var))
s4m> my-fun
(my-fun)
s4m: var: 99
s4m> 100
; change var in the global scope & the change is visible
; in the body of the function
(set! var 100)
s4m> 100
(my-fun)
s4m: var: 100
s4m> 101
If we change a variable from an outer scope inside a function body, by using set!, this will change the variable in the outer scope. A common convention in Scheme is to name our own functions ending in an exclamation mark if they have side-effects on external definitions.
; make a global var, var
(define var 99)
s4m> 99
; define a function that access and mutates var
(define (my-fun!)
; set outer var, and return the value
(set! var (+ 1 var)))
s4m> my-fun!
(my-fun!)
s4m> 100
; now var has also changed in the global scope
var
s4m> 100
Function parameters create bindings that are active in the function body, making an inner scope. This is also called “function scope”. The function scope will have the values of the arguments passed to the function bound to the symbols used as function parameters.
; make a function with a local binding
(define (my-fun-2 var)
(post "var in my-fun-2:" var)
(set! var (+ 1 var))
(post "var in my-fun-2 now:" var)
; return var
var)
s4m> my-fun-2
; call it
(my-fun-2 42)
s4m: var in my-fun-2: 42
s4m: var in my-fun-2 now: 43
s4m> 43
; make a global variable with the same name, 'var'
(define var 42)
s4m> 42
; call our function with it, returns 43 as before
(my-fun-2 var)
s4m: var in my-fun-2: 42
s4m: var in my-fun-2 now: 43
s4m> 43
; check our global var - no change!
(post var)
s4m: 42
So what’s going on here? The local binding of the symbol var in my-fun-2 is separate from the global binding; it’s a new variable that happens to have the same name. This results in the new variable - var in the scope of my-fun-2 - shadowing the global variable. When we use set! inside my-fun-2, only the local version is updated. After the function exits, its scope becomes inactive and the symbol ‘var’ will again refer to the global variable.
We can create inner scopes within a function by nesting define statements. This can be used for creating local variables and local functions that will only be visible in their enclosing scope:
; make a function with a nested variable
(define (my-fun)
; create a nested function and call it
(define inner-var 99)
(define (inner-fun)
(post "in inner-fun, inner-var is:" inner-var))
(inner-fun))
s4m> my-fun
(my-fun)
s4m> in inner-fun, inner-var is: 99
; inner-fun is not visible outside of my-fun
(inner-fun)
s4m> Error: unbound variable inner-fun
This works, but oftentimes a more elegant solution to inner scopes is the use of the let special form. It takes an expression with a series of bindings of symbol and value, and a body that is executed with those bindings. The let statement returns the value of the last expression in the body. Within the body of the let, any bindings defined by the let’s first clause will shadow any identically named bindings in outer scopes. Unlike a function, a let executes its body right away.
; make a scope with two local bindings
(let
((a 1) (b 2)) ; bindings
(+ a b)) ; body, does addition, returns value
s4m> 3
; the body can have many expressions
; the value returned by let is the last one
(let ((a 1) (b 2)) ; bindings
(post "a:" a) ; body with 3 expressions
(post "b:" b)
(+ a b))
s4m: "a:" 1
s4m: "b:" 2
s4m> 3
As far as scoping rules are concerned, variables defined by a let are treated in the body of the let exactly the same way as function paramaters are treated in the body of a function. Under the hood, they are the same. These two are completely equivalent:
; use a let
(let ((a 1) (b 2))
(+ a b))
s4m> 3
; use a lambda and call it immediately
((lambda (a b) (+ a b)) 1 2)
s4m> 3
In Scheme, a let literally is an immediately executed lambda. This is worth taking a moment to think about!
A regular let has all bindings defined at the same time, (order not guaranteed) meaning that a binding cannot refer to a previous binding:
; an error, the second binding won't work!
(let ((a 2) (b (* a a)))
(+ a b))
s4m> Error: unbound variable a ...
However, we can do this if we use let*:
; OK!
(let* ((a 2) (b (* a a)))
(+ a b))
s4m> 6
Under the hood, this actually executes as two nested lets:
(let ((a 2))
(let ((b (* a a)))
(+ a b)))
We can use a let in the body of a function to create temporary variables local to a function.
; define a function with an inner let
; the last sexpr in the let is returned by the let
; and thus also by my-fun
(define (my-fun a)
(let ((b 1) (c 2))
(+ a b c)))
(my-fun 3)
s4m> 6
The possible combinations of let and lambda are very powerful, but can get complicated. They can be used to create partial functions, objects with private data, and numerous other patterns. We will look at these in more depth in Part 2.
Looping¶
Looping in Scheme is also a bit unusual compared to other languages. If you’re used to languages with a for-loop, you might be surprised to find there isn’t one! Instead, it is most common to use functional programming constructs, in which the body of the loop is replaced by a call to a function. This is not as awkward as it might at first sound though, because lambda makes it easy to create temporary functions.
Map and for-each¶
The simplest looping constructs in Scheme are map and for-each. These are similar in that in each, we pass in two arguments: a function, and a list. The function is then repeatedly exectued over each item in the list, where the list item is used as the argument to the function. The difference between these two is that map returns a list of the results, while for-each is called for the side effect of calling the function (without collecting up the results in a new list).
In the example below, we pass map a function that returns the value of its single argument incremented by 1, and a list of integers. The call to map returns a new list, where each item is the old list item incremented by 1.
; a function to increment an argument by one
(define (add-1 x) (+ 1 x))
; a list to run this over
(define my-list (list 1 2 3))
; get a new list by calling map using the above
(map add-1 my-list)
s4m> (2 3 4)
Of course, we don’t need to pre-define either the function or list.
(map
(lambda (x) (+ 1 x))
(list 1 2 3))
s4m> (2 3 4)
If we don’t need the values to be returned from our loop, but rather want to trigger an event, we can use for-each. Because we aren’t calling it for the return value, for-each returns #<unspecified>.
; for-each will execute the functions, return #<unspecified>
(for-each
(lambda (x) (post "loop pass, x is:" x))
(list 1 2 3))
s4m: loop pass, x is: 1
s4m: loop pass, x is: 2
s4m: loop pass, x is: 3
s4m> #<unspecified>
If we want to combine side-effects and collection of values, we can have our function create the side-effect prior to returning its result:
; produce a side-effect, and collect the incremented value
(map
(lambda (x)
(post "loop pass, x is:" x)
(+ 1 x))
(list 1 2 3))
s4m: loop pass, x is: 1
s4m: loop pass, x is: 2
s4m: loop pass, x is: 3
s4m> (2 3 4)
If you’re used to for loops, you might be wanting to iterate over an index within a numerical range. We can do this by using the range function to create our list of index numbers:
; for-each will execute the functions, return #<unspecified>
(for-each
(lambda (x) (post "loop pass, x is:" x))
(range 0 4))
s4m: loop pass, x is: 0
s4m: loop pass, x is: 1
s4m: loop pass, x is: 2
s4m: loop pass, x is: 3
s4m> #<unspecified>
A nice feature of both map and for-each is that they can take any number of collections over which to iterate, and will use one from each as arguments to the function. Here’s an example of using this to make a list of lists:
(map
(lambda (x y) (list x y))
(list :a :b :c) ; first collection
(list 1 2 3)) ; second collection
s4m> ((:a 1) (:b 3) (:c 3))
The asute reader will have noticed that in this case, our lambda is optional, because we could just use the list function itself!
; use list as the function
(map list (list :a :b :c) (list 1 2 3))
s4m> ((:a 1) (:b 3) (:c 3))
If the lists are not equal in length, iteration stops when the first one runs out.
; stops at the end of the shorter list
(map list
(list :a :b :c)
(list 1 2 3 4 5 6))
s4m> ((:a 1) (:b 3) (:c 3))
; this can be handy combined with range and length
(define fruits (list 'apple 'pear 'banana))
(map list
(range 0 (length fruits))
fruits)
s4m> ((0 apple) (1 pear) (2 banana))
Looping with recursion¶
The second most common option for looping in Scheme is using functions recursively. We can have a function call itself until a condition is met. This requires us to have an if or cond statement in the function, with one branch that stops the loop and the other that continues it. The stopping branch is called the “base case”, and is written normally first. It returns a value that will be the return value of the whole loop. The other branch must call the function again, typically with an argument that is altered such that the loop only runs a finite number of times. For example, here is a function that recurses 4 times, counting down from 4 to 1:
; our looping function
(define (count-down x)
(post "count-down, x:" x)
(if (= x 1)
; the base case, stop by returning x
x
; otherwise, re-run with x decremented
(count-down (- x 1))))
; now run it!
(count-down 3)
s4m: count-down, x: 3
s4m: count-down, x: 2
s4m: count-down, x: 1
s4m> 1
A more real-world example of recursion would involve doing something with the argument, so that the base case returns something that was calculated from the recursive calls. Here’s an example of calculating a factorial. If you’re not familiar with a factorial, the factorial of a number is the result of multiplying a number by all the numbers smaller than that number. So factorial 4 (written 4!) is 4 x 3 x 2 x 1.
(define (factorial x)
(post "factorial call, x is:" x)
(if (= x 1)
; the base case, return 1
1
; otherwise, return the value of the current
; pass multiplied by the next recursion
(* x (factorial (- x 1)))))
; runnning should return 3 x 2 x 1
(factorial 3)
s4m: factorial call, x is: 3
s4m: factorial call, x is: 2
s4m: factorial call, x is: 1
s4m> 6
If you’re used to other programming languages you may be wondering how this could possibly be efficient, with a stack-frame created for each call. Won’t we run out of memory if using a very large value for the count? (If this means nothing to you, don’t worry about it…) The answer is that Scheme uses tail-call optimization. If the recursive function call is the last expression in the body of the function, the interpreter knows that it’s safe to implement the function recursion as a jump, under-the-hood. This means that we don’t actually make a new stack frame for each call, and thus tail-call recursion is efficient and safe. Recursion in Scheme is a big topic, and we will look at common patterns in future chapters.
Recursion with named let¶
Recursion can be confusing while you get used to it, and sometimes the syntax is just more verbose than it needs be, so Scheme includes an alternate way of looping that is secretely recursion, but looks much more like a “normal” loop. Named-let looks like a cross between a function call and a let statement, which makes sense when you remember that let and lambda are really the same thing in different syntax.
When we use named-let, we create a let block, but begin by giving it a name. Then we have any number of variable initializations, like a normal let. These are the starting values for the variables. Finally, when we call the name as if it’s a function, we use new arguments and the intepreter starts the let block again, with the arguments replacing the initial values for the let variables. As with recursive functions, we need a test to see if we should loop again, and a return value that is returned when we’re done looping.
Let’s start as simply as possible with our count-down again:
; name is count-down-loop, let vars consists of x and y
; because this is a let, it runs right away
(let count-down-loop ((x 3))
; body of the let
(post "x is: " x)
; if x is still greater than 1, repeat
(if (> x 1)
(count-down-loop (- x 1))))
s4m: x is: 3
s4m: x is: 2
s4m: x is: 1
s4m> #<unspecified>
A more complex example might return something from the let. Remember, a let returns its last expression. We’ll make a named-let to calculate a value, x, to some power, y.
; return x to the y: 2 to the 3rd power
(let exp-loop ((x 2) (y 3))
(post "exp-loop, x:" x "y:" y)
; if y is greater than one, repeat
(if (> y 1)
; on each pass, x is replaced with x times 2
(exp-loop (* x 2) (- y 1))
; if y is 1, return the value of x
x))
s4m: exp-loop, x: 2 y: 3
s4m: exp-loop, x: 4 y: 2
s4m: exp-loop, x: 8 y: 1
s4m> 8
Note that unlike recursion with a function, the binding for exp-loop is only valid in the let. We can’t call exp-loop from outside of the let, as if it’s a function. For illustration, here is the exact same construct, but implemented as an immediately executed function:
; as named let, executing immediately
(let exp-loop ((x 2) (y 3))
(if (> y 1)
(exp-loop (* x 2) (- y 1))
x))
s4m> 8
; as a function that is then called
(define (exp-function x y)
(if (> y 1)
(exp-function (* x 2) (- y 1))
x))
s4m> exp-function
(exp-function 2 3)
s4m> 8
; with the function, we can call it again
(exp-function 2 3)
; whereas is exp-loop is no longer in scope
(exp-loop 2 3)
s4m: s4m Error: ;unbound variable exp-loop in (exp-loop 2 3)
With any kind of recursion, we have to be careful not to get stuck in an infinite loop. Scheme For Max doesn’t provide any kind of protection here: Max will lock up and you will need to restart it. This is no different than with the JS object, but because recursion is easier to read in Scheme, you’re more likely to encounter it. Test your loops!
Looping with while¶
Though not part of the various Scheme standards, s7 also provides an implemention of the while loop. This is convenient when we want a simple, imperative loop, with the option to abort or continue. s7 is an unopinionated Scheme dialect, in that it doesn’t force us to program in a functional style.
While expressions consist of a condition and a body. The body is executed repeatedly as long as the condition is true. Additionally, we can abort execution of the body, jumping back to the beginning with continue, or break out of the loop entirely with break. We can combine this with the let form to ensure the variables we use in while are local.
(let ((count 0))
(while (< count 3)
(post "count:" count)
(set! count (+ 1 count))))
s4m: count: 0
s4m: count: 1
s4m: count: 2
s4m> ()
Here’s an example using break and continue with random, a construct we might use in a musical algorithm.
(let ((count 0))
; execute a maxium of 8 times
(while (< count 8)
(post "count:" count)
; a 1 in 4 chance we quit after each time
(if (= 0 (random 4))
(begin (post "aborting!") (break)))
; a 1 in 4 chance we stay on the same number
(if (= 0 (random 3))
(begin (post "continuing!") (continue)))
(set! count (+ 1 count))))
s4m: count: 0
s4m: count: 1
s4m: count: 2
s4m: count: 3
s4m: aborting!
s4m> ()
Conclusion of Part 1¶
Congratulations! You know now enough Scheme to productively work in Scheme For Max. To learn about the Max specific s4m functions, check out the Scheme For Max Documentation.
Future plans for this e-book include chapters on Lisp programming idioms and further narrative content on Scheme For Max common practices and recipes. You can follow the repository on GitHub to receive announcements. Also, please feel free to submit feedback via the GitHub issue tracker for this repository.