VI Appendices
29 Pyret for Racketeers and Schemers
If you’ve programmed before in a language like Scheme or the student levels of Racket (or the WeScheme programming environment), or for that matter even in certain parts of OCaml, Haskell, Scala, Erlang, Clojure, or other languages, you will find many parts of Pyret very familiar. This chapter is specifically written to help you make the transition from (student) Racket/Scheme/WeScheme (abbreviated “RSW”) to Pyret by showing you how to convert the syntax. Most of what we say applies to all these languages, though in some cases we will refer specifically to Racket (and WeScheme) features not found in Scheme.
In every example below, the two programs will produce the same results.
29.1 Numbers, Strings, and Booleans
Numbers are very similar between the two. Like Scheme, Pyret implements arbitraryprecision numbers and rationals. Some of the more exotic numeric systems of Scheme (such as complex numbers) aren’t in Pyret; Pyret also treats imprecise numbers slightly differently.
RSW  Pyret 
1 

RSW  Pyret 
1/2 

RSW  Pyret 
#i3.14 

Strings are also very similar, though Pyret allows you to use singlequotes as well.
RSW  Pyret 
"Hello, world!" 

RSW  Pyret 
"\"Hello\", he said" 

RSW  Pyret 
"\"Hello\", he said" 

Booleans have the same names:
RSW  Pyret 
true 

RSW  Pyret 
false 

29.2 Infix Expressions
Pyret uses an infix syntax, reminiscent of many other textual programming languages:
RSW  Pyret 
(+ 1 2) 

RSW  Pyret 
(* ( 4 2) 5) 

RSW  Pyret 
(/ 1 2 3 4) 

29.3 Function Definition and Application
RSW  Pyret 
(dist 3 4) 

RSW  Pyret  


29.4 Tests
RSW  Pyret 
(checkexpect 1 1) 

RSW  Pyret  


The second way is this: as an alias for check
we can also write
examples
. The two are functionally identical, but they capture
the human difference between examples (which explore the
problem, and are written before attempting a solution) and
tests (which try to find bugs in the solution, and are written
to probe its design).
where
block to accompany a function
definition. For instance:
fun double(n):
n + n
where:
double(0) is 0
double(10) is 20
double(1) is 2
end
check "squaring always produces nonnegatives":
(0 * 0) is 0
(2 * 2) is 4
(3 * 3) is 9
end
Just as in Racket, there are many testing operators in Pyret (in
addition to is
). See
the
documentation.
29.5 Variable Names
RSW  Pyret 
thisisaname 

thisname
(a variable) from
this  name
(a subtraction expression) because the 
in
the latter must be surrounded by spaces.
(define e^i*pi 1)
29.6 Data Definitions
RSW  Pyret 
(definestruct pt (x y)) 


in the middle:
data Point:  pt(x, y) end

, resulting
in the more readable
data Point: pt(x, y) end
;; A Point is either ;;  (pt number number), or ;;  (pt3d number number number)
data Point:
 pt(x, y)
 pt3d(x, y, z)
end
RSW  Pyret 
(pt 1 2) 

RSW  Pyret 
(pt? x)  ispt(x) 
cases
):
RSW  Pyret 
(ptx v) 

.x
extracts an x
field of any value
that has such a field, without attention to how it was
constructed. Thus, we can use .x
on a value whether it was
constructed by pt
or pt3d
(or indeed anything else with
that field). In contrast, cases
does pay attention to this
distinction.29.7 Conditionals
There are several kinds of conditionals in Pyret, one more than in the Racket student languages.
General conditionals can be written using if
, corresponding to
Racket’s if
but with more syntax.
RSW  Pyret  


RSW  Pyret  


if
includes else if
, which makes it possible
to list a collection of questions at the same level of indentation,
which if in Racket does not have. The corresponding code in
Racket would be written
(cond [fullmoon "howl"] [newmoon "bark"] [else "meow"])
ask
, designed to parallel cond
:
ask:
 fullmoon then: "howl"
 newmoon then: "bark"
 otherwise: "meow"
end
cond
to dispatch on a datatype:
(cond [(pt? v) (+ (ptx v) (pty v))] [(pt3d? v) (+ (ptx v) (ptz v))])
ask:
 ispt(v) then: v.x + v.y
 ispt3d(v) then: v.x + v.z
end
if ispt(v):
v.x + v.y
else if ispt3d(v):
v.x + v.z
end
cases (Point) v:
 pt(x, y) => x + y
 pt3d(x, y, z) => x + z
end
v
is a Point
, provides a clean
syntactic way of identifying the different branches, and makes
it possible to give a concise local name to each field position
instead of having to use selectors like .x
. In general, in
Pyret we prefer to use cases
to process data
definitions. However, there are times when, for instance, there many
variants of data but a function processes only very few of them. In
such situations, it makes more sense to explicitly use predicates and
selectors.29.8 Lists
In Racket, depending on the language level, lists are created using
either cons or list, with empty for the empty
list. The corresponding notions in Pyret are called link
,
list
, and empty
, respectively. link
is a
twoargument function, just as in Racket:
RSW  Pyret 
(cons 1 empty) 

RSW  Pyret 
(list 1 2 3) 

Note that the syntax [1, 2, 3]
, which represents lists in many
languages, is not legal in Pyret: lists are not privileged with
their own syntax. Rather, we must use an explicit constructor:
just as [list: 1, 2, 3]
constructs a list, [set: 1, 2,
3]
constructs a set instead of a list.In fact, we can
create our own constructors
and use them with this syntax.
Exercise
Try typing
[1, 2, 3]
and see the error message.
cases
. There are two variants, empty
and link
(which we used to construct the lists):
RSW  Pyret  


f
and r
(for
“first” and “rest”). Of course, this convention does not work if
there are other things by the same name; in particular, when writing a
nested destructuring of a list, we conventionally write fr
and
rr
(for “first of the rest” and “rest of the rest”).29.9 FirstClass Functions
lam
:
RSW  Pyret 
(lambda (x y) (+ x y)) 

29.10 Annotations
; square: Number > Number ; sortnums: List<Number> > List<Number> ; sort: List<T> * (T * T > Boolean) > List<T>
fun square(n :: Number) > Number: ...
fun sortnums(l :: List<Number>) > List<Number>: ...
fun sort<T>(l :: List<T>, cmp :: (T, T > Boolean)) > List<T>: ...
29.11 What Else?
If there are other parts of Scheme or Racket syntax that you would like to see translated, please let us know.
30 Glossary
The bandwidth between two network nodes is the quantity of data that can be transferred in a unit of time between the nodes.
A cache is an instance of a ☛ spacetime tradeoff: it trades space for time by using the space to avoid recomputing an answer. The act of using a cache is called caching. The word “cache” is often used loosely; we use it only for information that can be perfectly reconstructed even if it were lost: this enables a program that needs to reverse the trade—
i.e., use less space in return for more time— to do so safely, knowing it will lose no information and thus not sacrifice correctness.
Coinduction is a proof principle for mathematical structures that are equipped with methods of observation rather than of construction. Conversely, functions over inductive data take them apart; functions over coinductive data construct them. The classic tutorial on the topic will be useful to mathematically sophisticated readers.
An idempotent operator is one whose repeated application to any value in its domain yields the same result as a single application (note that this implies the range is a subset of the domain). Thus, a function \(f\) is idempotent if, for all \(x\) in its domain, \(f(f(x)) = f(x)\) (and by induction this holds for additional applications of \(f\)).
Invariants are assertions about programs that are intended to always be true (“invaryant”—
never varying). For instance, a sorting routine may have as an invariant that the list it returns is sorted.
The latency between two network nodes is the time it takes for packets to get between the nodes.
A metasyntactic variable is one that lives outside the language, and ranges over a fragment of syntax. For instance, if we write “for expressions
e1
ande2
, the sume1 + e2
”, we do not mean the programmer literally wrote “e1
” in the program; rather we are usinge1
to refer to whatever the programmer might write on the left of the addition sign. Therefore,e1
is metasyntax.
At the machine level, a packed representation is one that ignores traditional alignment boundaries (in older or smaller machines, bytes; on most contemporary machines, words) to let multiple values fit inside or even spill over the boundary.
For instance, say we wish to store a vector of four values, each of which represents one of four options. A traditional representation would store one value per alignment boundary, thereby consuming four units of memory. A packed representation would recognize that each value requires two bits, and four of them can fit into eight bits, so a single byte can hold all four values. Suppose instead we wished to store four values representing five options each, therefore requiring three bits for each value. A byte or wordaligned representation would not fundamentally change, but the packed representation would use two bytes to store the twelve bits, even permitting the third value’s three bytes to be split across a byte boundary.
Of course, packed representations have a cost. Extracting the values requires more careful and complex operations. Thus, they represent a classic ☛ spacetime tradeoff: using more time to shrink space consumption. More subtly, packed representations can confound certain runtime systems that may have expected data to be aligned.
Parsing is, very broadly speaking, the act of converting content in one kind of structured input into content in another. The structures could be very similar, but usually they are quite different. Often, the input format is simple while the output format is expected to capture rich information about the content of the input. For instance, the input might be a linear sequence of chacters on an input stream, and the output might be expected to be a rich, treestructured according to some datatype: most program and naturallanguage parsers are faced with this task.
Reduction is a relationship between a pair of situations—
problems, functions, data structures, etc.— where one is defined in terms of the other. A reduction R is a function from situations of the form P to ones of the form Q if, for every instance of P, R can construct an instance of Q such that it preserves the meaning of P. Note that the converse strictly does not need to hold.
Suppose you have an expensive computation that always produces the same answer for a given set of inputs. Once you have computed the answer once, you now have a choice: store the answer so that you can simply look it up when you need it again, or throw it away and recompute it the next time. The former uses more space, but saves time; the latter uses less space, but consumes more time. This, at its heart, is the spacetime tradeoff. Memoization [Avoiding Recomputation by Remembering Answers] and using a ☛ cache are both instances of it.
Type variables are identifiers in the type language that (usually) range over actual types.
A notation used to transmit data across, as opposed to within, a closed platform (such as a virtual machine). These are usually expected to be relatively simple because they must be implemented in many languages and on weak processes. They are also expected to be unambiguous to aid simple, fast, and correct parsing. Popular examples include XML, JSON, and sexpressions.