#t
not, by the way, is a function, not a special form like and or or, because its operand must
always be evaluated, and so needs no special treatment.
• Lists and Pairs: A large number of operations deal with pairs and lists (which again are built
of pairs and empty lists):
>>> (cons ’a ’b)
(a . b)
>>> (list ’a ’b)
(a b)
>>> (cons ’a (cons ’b ’()))
(a b)
>>> (car (cons ’a ’b))
a
>>> (cdr (cons ’a ’b))
b
>>> (cdr (list a b))
(b)
>>> (cadr ’(a b))
; An abbreviation for (car (cdr ’(a b)))
b
>>> (cddr ’(a b))
; Similarly, an abbreviation for (cdr (cdr ’(a b)))
()
>>> (list-tail ’(a b c) 0)
33
(a b c)
>>> (list-tail ’(a b c) 1)
(b c)
>>> (list-ref ’(a b c) 0)
a
>>> (list-ref ’(a b c) 2)
c
>>> (append ’(a b) ’(c d) ’() ’(e))
(a b c d e)
>>> ; All but the last list is copied.
The last is shared, so:
>>> (define L1 (list ’a ’b ’c))
>>> (define L2 (list ’d))
>>> (define L3 (append L1 L2))
>>> (set-car! L1 1)
>>> (set-car! L2 2)
>>> L3
(a b c 2)
>>> (null? ’())
#t
>>> (list? ’())
#t
>>> (list? ’(a b))
#t
>>> (list? ’(a . b))
#f
• Equivalence: The = operation is for numbers. For general equality of values, Scheme distin-
guishes eq? (like Python’s is), eqv? (similar, but is the same as = on numbers), and equal?
(compares list structures and strings for content). Generally, we use eqv? or equal?, except
in cases such as comparing symbols, booleans, or the null list:
>>> (eqv? ’a ’a)
#t
>>> (eqv? ’a ’b)
#f
>>> (eqv? 100 (+ 50 50))
#t
>>> (eqv? (list ’a ’b) (list ’a ’b))
#f
>>> (equal? (list ’a ’b) (list ’a ’b))
#t
• Types: Each type of value satisfies exactly one of the basic type predicates:
>>> (boolean? #f)
#t
>>> (integer? 3)
#t
>>> (pair? ’(a b))
#t
>>> (null? ’())
#t
>>> (symbol? ’a)
#t
>>> (procedure? +)
#t
• Input and Output: Scheme interpreters typically run a read-eval-print loop, but one can also
output things under explicit control of the program, using the same functions the interpreter does
internally:
34
>>> (begin (display ’a) (display ’b) (newline))
ab
Thus, (display x) is somewhat akin to Python’s
print(str(x), end="")
and (newline) is like print().
For input, the (read) function reads a Scheme expression from the current “port”. It does not
interpret the expression, but rather reads it as data:
>>> (read)
>>> (a b c)
(a b c)
• Evaluation: The apply function provides direct access to the function-calling operation:
>>> (apply cons ’(1 2))
(1 . 2)
>>> ;; Apply the function f to the arguments in L after g is
>>> ;; applied to each of them
>>> (define (compose-list f g L)
...
(apply f (map g L)))
>>> (compose-list + (lambda (x) (* x x)) ’(1 2 3))
14
An extension allows for some “fixed” arguments at the beginning:
>>> (apply + 1 2 ’(3 4 5))
15
The following function is not in Revised(4) Scheme, but is present in our versions of the interpreter (warning: a non-standard procedure that is not defined this way in later versions of
Scheme):
>>> (eval ’(+ 1 2))
3
That is, eval evaluates a piece of Scheme data that represents a correct Scheme expression.
This version evaluates its expression argument in the global environment. Our interpreter also
provides a way to specify a specific environment for the evaluation:
>>> (define (incr n) (lambda (x) (+ n x)))
>>> (define add5 (incr 5))
>>> (add5 13)
18
>>> (eval ’n (procedure-environment add5))
5
3.6.2 The Logo Language
Logo is another dialect of Lisp. It was designed for educational use, and so many design decisions in Logo are
meant to make the language more comfortable for a beginner. For example, most Logo procedures are invoked in
prefix form (first the procedure name, then the arguments), but the common arithmetic operators are also provided
in the customary infix form. The brilliance of Logo is that its simple, approachable syntax still provides amazing
expressivity for advanced programmers.
The central idea in Logo that accounts for its expressivity is that its built-in container type, the Logo sentence
(also called a list), can easily store Logo source code! Logo programs can write and interpret Logo expressions
as part of their evaluation process. Many dynamic languages support code generation, including Python, but no
language makes code generation quite as fun and accessible as Logo.
You may want to download a fully implemented Logo interpreter at this point to experiment with the language.
The standard implementation is Berkeley Logo (also known as UCBLogo), developed by Brian Harvey and his Berkeley students. For macintosh uses, ACSLogo is compatible with the latest version of Mac OSX and comes with a user guide that introduces many features of the Logo language.
35
Fundamentals. Logo is designed to be conversational. The prompt of its read-eval loop is a question mark
(?), evoking the question, “what shall I do next?” A natural starting point is to ask Logo to print a number:
? print 5
5
The Logo language employs an unusual call expression syntax that has no delimiting punctuation at all. Above,
the argument 5 is passed to print, which prints out its argument. The terminology used to describe the program-
ming constructs of Logo differs somewhat from that of Python. Logo has procedures rather than the equivalent
“functions” in Python, and procedures output values rather than “returning” them. The print procedure always
outputs None, but prints a string representation of its argument as a side effect. (Procedure arguments are typically
called inputs in Logo, but we will continue to call them arguments in this text for the sake of clarity.)
The most common data type in Logo is a word, a string without spaces. Words serve as general-purpose
values that can represent numbers, names, and boolean values. Tokens that can be interpreted as numbers or
boolean values, such as 5, evaluate to words directly. On the other hand, names such as five are interpreted as
procedure calls:
? 5
You do not say what to do with 5.
? five
I do not know how to five.
While 5 and five are interpreted differently, the Logo read-eval loop complains either way. The issue with
the first case is that Logo complains whenever a top-level expression it evaluates does not evaluate to None. Here,
we see the first structural difference between the interpreters for Logo and Calculator; the interface to the former
is a read-eval loop that expects the user to print results. The latter employed a more typical read-eval-print loop
that printed return values automatically. Python takes a hybrid approach: only non-None values are coerced to
strings using repr and then printed automatically.
A line of Logo can contain multiple expressions in sequence. The interpreter will evaluate each one in turn. It
will complain if any top-level expression in a line does not evaluate to None. Once an error occurs, the rest of the
line is ignored:
? print 1 print 2
1
2
? 3 print 4
You do not say what to do with 3.
Logo call expressions can be nested. In the version of Logo we will implement, each procedure takes a fixed
number of arguments. Therefore, the Logo interpreter is able to determine uniquely when the operands of a nested
call expression are complete. Consider, for instance, two procedures sum and difference that output the sum
and difference of their two arguments, respectively:
? print sum 10 difference 7 3
14
We can see from this nesting example that the parentheses and commas that delimit call expressions are not
strictly necessary. In the Calculator interpreter, punctuation allowed us to build expression trees as a purely syn-
tactic operation; without ever consulting the meaning of the operator names. In Logo, we must use our knowledge
of how many arguments each procedure takes in order to discover the correct structure of a nested expression.
This issue is addressed in further detail in the next section.
Logo also supports infix operators, such as + and *. The precedence of these operators is resolved according
to the standard rules of algebra; multiplication and division take precedence over addition and subtraction:
? 2 + 3 * 4
14
The details of how to implement operator precedence and infix operators to form correct expression trees is
left as an exercise. For the following discussion, we will concentrate on call expressions using prefix syntax.
Quotation. A bare name is interpreted as the beginning of a call expression, but we would also like to reference
words as data. A token that begins with a double quote is interpreted as a word literal. Note that word literals do
not have a trailing quotation mark in Logo:
36
? print "hello
hello
In dialects of Lisp (and Logo is such a dialect), any expression that is not evaluated is said to be quoted. This
notion of quotation is derived from a classic philosophical distinction between a thing, such as a dog, which runs
around and barks, and the word “dog” that is a linguistic construct for designating such things. When we use
“dog” in quotation marks, we do not refer to some dog in particular but instead to a word. In language, quotation
allow us to talk about language itself, and so it is in Logo. We can refer to the procedure for sum by name without
actually applying it by quoting it:
? print "sum
sum
In addition to words, Logo includes the sentence type, interchangeably called a list. Sentences are enclosed in
square brackets. The print procedure does not show brackets to preserve the conversational style of Logo, but
the square brackets can be printed in the output by using the show procedure:
? print [hello world]
hello world
? show [hello world]
[hello world]
Sentences can be constructed using three different two-argument procedures. The sentence procedure
combines its arguments into a sentence. It is polymorphic; it places its arguments into a new sentence if they are
words or concatenates its arguments if they are sentences. The result is always a sentence:
? show sentence 1 2
[1 2]
? show sentence 1 [2 3]
[1 2 3]
? show sentence [1 2] 3
[1 2 3]
? show sentence [1 2] [3 4]
[1 2 3 4]
The list procedure creates a sentence from two elements, which allows the user to create hierarchical data
structures:
? show list 1 2
[1 2]
? show list 1 [2 3]
[1 [2 3]]
? show list [1 2] 3
[[1 2] 3]
? show list [1 2] [3 4]
[[1 2] [3 4]]
Finally, the fput procedure creates a list from a first element and the rest of the list, as did the Rlist Python
constructor from earlier in the chapter:
? show fput 1 [2 3]
[1 2 3]
? show fput [1 2] [3 4]
[[1 2] 3 4]
Collectively, we can call sentence, list, and fput the sentence constructors in Logo. Deconstructing a
sentence into its first, last, and rest (called butfirst) in Logo is straightforward as well. Hence, we also
have a set of selector procedures for sentences:
37
? print first [1 2 3]
1
? print last [1 2 3]
3
? print butfirst [1 2 3]
[2 3]
Expressions as Data. The contents of a sentence is also quoted in the sense that it is not evaluated. Hence,
we can print Logo expressions without evaluating them:
? show [print sum 1 2]
[print sum 1 2]
The purpose of representing Logo expressions as sentences is typically not to print them out, but instead to
evaluate them using the run procedure:
? run [print sum 1 2]
3
Combining quotation, sentence constructors, and the run procedure, we arrive at a very general means of
combination that builds Logo expressions on the fly and then evaluates them:
? run sentence "print [sum 1 2]
3
? print run sentence "sum sentence 10 run [difference 7 3]
14
The point of this last example is to show that while the procedures sum and difference are not first-class
constructs in Logo (they cannot be placed in a sentence, for instance), their quoted names are first-class, and the
run procedure can resolve those names to the procedures to which they refer.
The ability to represent code as data and later interpret it as part of the program is a defining feature of Lisp-
style languages. The idea that a program can rewrite itself as it executes is a powerful one, and served as the
foundation for early research in artificial intelligence (AI). Lisp was the preferred language of AI researchers for
decades. The Lisp language was invented by John McCarthy, who coined the term “artificial intelligence” and played a critical role in defining the field. This code-as-data property of Lisp dialects, along with their simplicity
and elegance, continues to attract new Lisp programmers today.
Turtle graphics. No implementation of Logo is complete without graphical output based on the Logo turtle.
This turtle begins in the center of a canvas, moves and turns based on procedures, and draws lines behind it as
it moves. While the turtle was invented to engage children in the act of programming, it remains an entertaining
graphical tool for even advanced programmers.
At any moment during the course of executing a Logo program, the Logo turtle has a position and heading on
the canvas. Single-argument procedures such as forward and right change the position and heading of the
turtle. Common procedures have abbreviations: forward can also be called as fd, etc. The nested expression
below draws a star with a smaller star at each vertex:
? repeat 5 [fd 100 repeat 5 [fd 20 rt 144] rt 144]
38
The full repertoire of Turtle procedures is also built into Python as the turtle library module. A limited subset of these functions are exposed as Logo procedures in the companion project to this chapter.
Assignment. Logo supports binding names to values. As in Python, a Logo environment consists of a se-
quence of frames, and each frame can have at most one value bound to a given name. In Logo, names are bound
with the make procedure, which takes as arguments a name and a value:
? make "x 2
The first argument is the name x, rather than the output of applying the procedure x, and so it must be quoted.
The values bound to names are retrieved by evaluating expressions that begin with a colon:
? print :x
2
Any word that begins with a colon, such as :x, is called a variable. A variable evaluates to the value to which
the name of the variable is bound in the current environment.
The make procedure does not have the same effect as an assignment statement in Python. The name passed
to make is either already bound to a value or is currently unbound.
1. If the name is already bound, make re-binds that name in the first frame in which it is found.
2. If the name is not bound, make binds the name in the global frame.
This behavior contrasts sharply with the semantics of the Python assignment statement, which always binds a
name to a value in the first frame of the current environment. The first assignment rule above is similar to Python
assignment following a nonlocal statement. The second is similar to Python assignment following a global
statement.
Procedures. Logo supports user-defined procedures using definitions that begin with the to keyword. Def-
initions are the final type of expression in Logo, along with call expressions, primitive expressions, and quoted
expressions. The first line of a definition gives the name of the new procedure, followed by the formal parameters
as variables. The lines that follow constitute the body of the procedure, which can span multiple lines and must
end with a line that contains only the token end. The Logo read-eval loop prompts the user for procedure bodies
with a > continuation symbol. Values are output from a user-defined procedure using the output procedure:
? to double :x
> output sum :x :x
> end
? print double 4
8
Logo’s application process for a user-defined procedure is similar to the process in Python. Applying a pro-
cedure to a sequence of arguments begins by extending an environment with a new frame, binding the formal
parameters of the procedure to the argument values, and then evaluating the lines of the body of the procedure in
the environment that starts with that new frame.
A call to output has the same role in Logo as a return statement in Python: it halts the execution of the
body of a procedure and returns a value. A Logo procedure can return no value at all by calling stop:
? to count
> print 1
> print 2
> stop
> print 3
> end
? count
1
2
Scope. Logo is a dynamically scoped language. A lexically scoped language such as Python does not allow the
local names of one function to affect the evaluation of another function unless the second function was explicitly
defined within the first. The formal parameters of two top-level functions are completely isolated. In a dynamically
scoped language, there is no such isolation. When one function calls another function, the names bound in the
local frame for the first are accessible in the body of the second:
39
? to print_last_x
> print :x
> end
? to print_x :x
> print_last_x
> end
? print_x 5
5
While the name x is not bound in the global frame, it is bound in the local frame for print_x, the function
that is called first. Logo’s dynamic scoping rules allow the function print_last_x to refer to x, which was
bound as the formal parameter of print_x.
Dynamic scoping is implemented by a single change to the environment model of computation. The frame
that is created by calling a user-defined function always extends the current environment. For example, the call to
print_x above introduces a new frame that extends the current environment, which consists solely of the global
frame. Within the body of print_x, the call to print_last_x introduces another frame that extends the
current environment, which includes both the local frame for print_x and the global frame. As a result, looking
up the name x in the body of print_last_x finds that name bound to 5 in the local frame for print_x.
Alternatively, under the lexical scoping rules of Python, the frame for print_last_x would have extended
only the global frame and not the local frame for print_x.
A dynamically scoped language has the advantage that its procedures may not need to take as many arguments.
For instance, the print_last_x procedure above takes no arguments, and yet its behavior can be parameterized
by an enclosing scope.
General programming. Our tour of Logo is complete, and yet we have not introduced any advanced features,
such as an object system, higher-order procedures, or even statements. Learning to program effectively in Logo
requires piecing together the simple features of the language into effective combinations.
There is no conditional expression type in Logo; the procedures if and ifelse are applied using call expres-
sion evaluation rules. The first argument of if is a boolean word, either True or False. The second argument is
not an output value, but instead a sentence that contains the line of Logo code to be evaluated if the first argument
is True. An important consequence of this design is that the contents of the second argument is not evaluated at
all unless it will be used:
? 1/0
div raised a ZeroDivisionError: division by zero
? to reciprocal :x
> if not :x = 0 [output 1 / :x]
> output "infinity
> end
? print reciprocal 2
0.5
? print reciprocal 0
infinity
Not only does the Logo conditional expression not require a special syntax, but it can in fact be implemented
in terms of word and run. The primitive procedure ifelse takes three arguments: a boolean word, a sentence
to be evaluated if that word is True, and a sentence to be evaluated if that word is False. By clever naming of
the formal parameters, we can implement a user-defined procedure ifelse2 with the same behavior:
? to ifelse2 :predicate :True :False
> output run run word ": :predicate
> end
? print ifelse2 emptyp [] ["empty] ["full]
empty
Recursive procedures do not require any special syntax, and they can be used with run, sentence, first,
and butfirst to define general sequence operations on sentences. For instance, we can apply a procedure to an
argument by building a two-element sentence and running it. The argument must be quoted if it is a word:
40
? to apply_fn :fn :arg
> output run list :fn ifelse word? :arg [word "" :arg] [:arg]
> end
Next, we can define a procedure for mapping a procedure :fn over the words in a sentence :s incrementally:
? to map_fn :fn :s
> if emptyp :s [output []]
> output fput apply_fn :fn first :s map_fn :fn butfirst :s
> end
? show map "double [1 2 3]
[2 4 6]
The second line of the body of map_fn can also be written with parentheses to indicate the nested structure
of the call expression. However, parentheses show where call expressions begin and end, rather than surrounding
only the operands and not the operator:
> (output (fput (apply_fn :fn (first :s)) (map_fn :fn (butfirst :s))))
Parentheses are not necessary in Logo, but they often assist programmers in documenting the structure of
nested expressions. Most dialects of Lisp require parentheses and therefore have a syntax with explicit nesting.
As a final example, Logo can express recursive drawings using its turtle graphics in a remarkably compact
form. Sierpinski’s triangle is a fractal that draws each triangle as three neighboring triangles that have vertexes at
the midpoints of the legs of the triangle that contains them. It can be drawn to a finite recursive depth by this Logo
program:
? to triangle :exp
> repeat 3 [run :exp lt 120]
> end
? to sierpinski :d :k
> triangle [ifelse :k = 1 [fd :d] [leg :d :k]]
> end
? to leg :d :k
> sierpinski :d / 2 :k - 1
> penup fd :d pendown
> end
The triangle procedure is a general method for repeating a drawing procedure three times with a left turn
following each repetition. The sierpinski procedure takes a length and a recursive depth. It draws a plain
triangle if the depth is 1, and otherwise draws a triangle made up of calls to leg. The leg procedure draws a
single leg of a recursive Sierpinski triangle by a recursive call to sierpinski that fills the first half of the length