Notes

This page collects notes for the course.

If you’d like to contribute to the notes, simply submit a pull-request to the course github repository.

The Approach of this Course

The goal of this course is to explore programming in the Racket ecosystem. It will probably be different from other courses you have taken at UMD in that it will be more open-ended, exploratory, and collaborative. There are no assignments per se and all work will be accomplished as a group. Think of this as three weeks of group play.

I don’t have strong preconceived notions about where this course will take us. What I would like us to do is come up with an idea for a project to work on for three weeks and then work on it.

The basic parameters are:

• it should touch on some of the interesting aspects of Racket.

  This should be easy to accomplish since there are so many cool things included with Racket: there’s a GUI library, a fancy object-oriented system, the world’s most sophisticated and extensible syntax system and a whole ethos of “language-oriented” design, nice libraries for writing distributed games that communicate over the network, solid testing facilities, a very cool web server, a fancy package manager, a flexible foreign function interface that makes it possible to interact with object code written in any language, etc. etc.

• it should be large enough that 30 people can reasonably collaborate on it over the course of three weeks, but also scoped in such a way that we can have something that works quickly.

Ideally, I think it should be something that brings us together as a group not just as programmers of the system, but as users. So I was thinking of something like a chat or game server and client or maybe an Among Us spin-off. Let your imagination fly.

Resources

We have a number of computing resources at our disposal for this course that we can take advantage.

• We have all the usual university infrastructure, such as GRACE, Panopto, ELMS, Zoom, etc. We will use Zoom to meet synchronously for the semester.

• We have a Discord server dedicated to the class that we will use to communicate asynchronously. See ELMS for the invite URL.

• We have static web space allocated on the department web server (i.e. the course home page).

• We have a public Github repository for the course, hosted within the PLUM Lab organization (The Lab for Programming Language Research at the University of Maryland). The lab has github resources available such as private repositories, GH action compute time, bandwith, storage, etc.

• We have a dedicated server machine (that lives in my basement) available at untyped.lambda-calcul.us. It has the most recent version of Racket installed. It is currently running the web server and could also be used as a universe server or any other kind of server we’d like to use. SSH access to the machine can be made available if needed. It is a Raspberry Pi 4B with 8GB of RAM and a 16GB micro SD card; it’s running Raspberry Pi OS 10. This machine is not used for anything else, so we can reconfigure it as we’d like.

If there’s anything else you think would be useful, please let me know on Discord and I will see what I can do.

Getting Started

To get started with Racket, you should download and install it. Racket works on every major computing platform. You can find it here, under Download:

https://racket-lang.org/

We will be using the Racket distribution and CS variant (if available for your platform). For more detailed instructions, you can read the Getting Started guide in the documentation for Racket.

We will primarily use Racket in two modes: either from within the Racket IDE, called DrRacket, or from the command line using the racket executable.

Once you have installed Racket, open up DrRacket and try to work through these tutorials (you might only skim through the last one):

• Quick: An Introduction to Racket with Pictures

• More: Systems Programming with Racket

• The Racket Guide

Introduction to Racket

Now that you have Racket installed, let’s get a quick introduction.

You can run Racket in a few different ways, but probably the easiest way to learn Racket is by programming within DrRacket, the Racket IDE.

When you open up DrRacket for the first time it will tell you to select a language. This is your first clue that Racket is unlike languages you’ve seen so far because it’s not just a single language, but a whole ecosystem of languages and tools for making new languages, all of which can coexist and interoperate with each other. But to start, we are going to be working with the Racket language. To do this, select the option to choose the language based on the text of the program and start your program with

Now press the Run button.

You’ll see the DrRacket split into two panes. The one on top contains the #lang racket bit, and the one below shows some information about the version of Racket you are using and displays a prompt (>).

The prompt is for a “read-eval-print loop” (or REPL), where you can type Racket expressions which will be read, evaluated, and the result printed for you. Let’s start there. Try typing some of the following:

Racket REPL

> (+ 1 2)

3

> (* 3 4)

12

> (* (+ 1 2) 4)

12

> (+ 1 2 3 4)

10

> (string-append "hello" "there")

"hellothere"

> (string-append "goodbye" ", " "friend")

"goodbye, friend"

> (even? 7)

#f

> (or (not (even? 7)) (odd? 0))

#t

Look at these examples and take a moment to think about what’s going on. What’s different from languages you are used to? What role are parentheses playing? What is the syntax for calling a function? What data types have you discovered so far? In answering these questions, you will have taught yourself a significant chunk of Racket.

Let’s do a few more examples. Try to for a mental model of what’s going on. Use your REPL to confirm, refute, and refine your mental model.

Racket REPL

> (+ 1 "two")

+: contract violation

expected: number?

given: "two"

> (define ten (+ 1 2 3 4))

> (* 2 ten)

20

> (define (goodbye friend)     (string-append "goodbye, " friend))

> (goodbye "pal")

"goodbye, pal"

> (goodbye "Elliot")

"goodbye, Elliot"

> (goodbye "Elliot" "Alderson")

goodbye: arity mismatch;

the expected number of arguments does not match the given

number

expected: 1

given: 2

> (define (hello title name)     (string-append "Hello, " title ". " name))

> (hello "Dr" "Racket")

"Hello, Dr. Racket"

OK, so what have we seen so far:

• three data types: strings, booleans, numbers

• the syntax for function application is ( followed by a function name, followed by arguments, followed by ).

• the syntax for a variable definition is (define followed by the variable name, follwed by an expression, followed by ).

• the syntax for a function definition is (define ( followed by the function name, followed by the parameter names, followed by ) followed by an expression for the function body, which may refer to the parameter names, followed by ).

• some functions expect their arguments to be of a certain type and will cause an error if inappropriate arguments are given.

• some functions expect a certain number of arguments and will cause an error if an inappropriate number of arguments are given. (Some functions, like +, work on any number of arguments.

• there are some built-in functions like +, *, string-append, even?, odd?, or, and not.

Next we’ll take a look at more of the language by relating it to a langauge you may have already seen: OCaml.

From OCaml to Racket

Racket = OCaml with uniform syntax and no types (for now)

1 Basic values

Let’s start by looking at something you know: OCaml. In OCaml, expressions can include literals for numbers, strings, booleans. Here we are using the OCaml read-eval-print-loop (REPL) to type in examples and evaluate their results:

OCaml REPL

# 8;;
- : int = 8
# "ocaml";;
- : string = "ocaml"
# true;;
- : bool = true
# false;;
- : bool = false

Note that the ;; is not part of the expression syntax, but is a terminator token, signalling to the REPL that the expression is complete and ready to be evaluated.

The Racket REPL operates similarly, but doesn’t require a terminator:

Racket REPL

> 8

8

> "racket"

"racket"

> #t

#t

> #f

#f

OCaml prints out the type of each expression, in addition to its value, while Racket only prints the value. The notation for booleans is slightly different, but both languages agree on numbers, strings, and booleans. OCaml uses a # prompt, while Racket uses >, but these differences are immaterial. The languages are essentially the same so far.

2 Basic operations

OCaml uses an infix notation for writing operations.

OCaml REPL

# 1 + 2 * 2;;
- : int = 5

The order of operations follows the usual mathematical precendence rules (which you must memorize), or you can use parentheses to indicate grouping:

OCaml REPL

# 1 + (2 * 2);;
- : int = 5
# (1 + 2) * 2;;
- : int = 6

Extraneous parenthesis are fine:

OCaml REPL

# (((1))) + ((2 * 2));;
- : int = 5

Compared to many languages you may know, including OCaml, Racket employs a uniform, minimalistic concrete syntax based on the concept of parenthesized, prefix notation.

In this notation, parentheses play a much more central role. They are not optional and they signal the form of the expression.

Languages, like people, descend from their ancestors and inherit some of their properties. In the case of notation, Racket inherits the Lisp (and Scheme) notation for programs. It takes a bit of getting used to, but once aclimated, the notation should feel lightweight and consistent; there is verry little to memorize when it comes to syntax.

So in Racket, we would write:

Racket REPL

> (+ 1 (* 2 2))

5

> (* (+ 1 2) 2)

6

Note that there are no precendence rules for addition and multiplication: the form of the expression makes it unambiguous.

Parenthesis indicate function applications, so adding extraneous parens means something different than in OCaml:

Racket REPL

> (1)

application: not a procedure;

expected a procedure that can be applied to arguments

given: 1

Here the parens are indicating a function application. The “function” is the first subexpression within the parens, i.e. 1. Of course, 1 isn’t a function and can’t be applied, hence the error.

3 Functions

OCaml also has a notation for writing functions:

OCaml REPL

# fun x y -> x + y;;
- : int -> int -> int = <fun>

This make an anonymous function that consumes two integers and produces their sum.

To apply it, we can write it justapoxed with arguments:

OCaml REPL

# (fun x y -> x + y) 3 4;;
- : int = 7

Note that in OCaml, every function is a function of exactly one argument. Therefore fun x y -> x + y is actuallty shorthand for fun x -> fun y -> x + y.

Applying such a function to fewer than 2 arguments will do a partial function application, which will produce a function that take the remaining arguments:

OCaml REPL

# (fun x y -> x + y) 3;;
- : int -> int = <fun>

To encode functions that must be given two arguments, a tuple can be used:

OCaml REPL

# fun (x, y) -> x + y;;
- : int * int -> int = <fun>

To apply such a function, it must be given a pair of integers:

OCaml REPL

# (fun (x, y) -> x + y) (3, 4);;
- : int = 7

The use of (x, y) here in the function parameters is actually a pattern. This can be understood as shorthand for:

OCaml REPL

# fun p -> match p with (x, y) -> x + y;;
- : int * int -> int = <fun>

So even this function is actually taking a single argument (which must be a pair of numbers).

Racket has a similar notation for writing functions:

Racket REPL

> (λ (x) (λ (y) (+ x y)))

#<procedure>

You can also write this without the fancy λ by spelling it lambda:

Racket REPL

> (lambda (x) (lambda (y) (+ x y)))

#<procedure>

(In DrRacket, to insert a “λ” press Cmd+\.)

To apply it, it must be written in parens, juxtaposed with arguments:

Racket REPL

> (((λ (x) (λ (y) (+ x y))) 3) 4)

7

Functions in Racket do not always consume a single argument. They can consume 0, 1, or more arguments.

Racket REPL

> (λ (x y) (+ x y))

#<procedure>

This is not a shorthand for the function above it; rather it is a function that expects two arguments:

Racket REPL

> ((λ (x y) (+ x y)) 3 4)

7

Applying a function to the wrong number of arguments will result in an error (and not perform partial function application):

Racket REPL

> ((λ (x y) (+ x y)) 3)

#<procedure>: arity mismatch;

the expected number of arguments does not match the given

number

expected: 2

given: 1

4 Definitions

At the top-level in OCaml, variables can be defined with let and let rec:

OCaml REPL

# let x = 3;;
val x : int = 3
# let y = 4;;
val y : int = 4
# x + y;;
- : int = 7
# let rec fact = fun n ->
    match n with
    | 0 -> 1
    | n -> n * (fact (n - 1));;
val fact : int -> int = <fun>
# fact 5;;
- : int = 120

In Racket, variables are defined with the define form:

Racket REPL

> (define x 3)

> (define y 4)

> (+ x y)

7

> (define fact     (λ (n)      (match n        [0 1]        [n (* n (fact (- n 1)))])))

> (fact 5)

120

(Note that the use of square brackets here is stylistic: from Racket’s point of view as long as “parentheses” (e.g. ({[) match, any kind is acceptable.)

In OCaml, function definitions can be written as:

OCaml REPL

# let rec fact n =
    match n with
    | 0 -> 1
    | n -> n * (fact (n - 1));;
val fact : int -> int = <fun>

This is just a shorthand for the definition written above in terms of fun.

Similarly in Racket, function definitions can be written as:

Racket REPL

> (define (fact n)     (match n       [0 1]       [n (* n (fact (- n 1)))]))

which is shorthand for the definition above using λ.

Notice both OCaml and Racket have pattern matching forms, which are quite useful for writing function in terms of a number of "cases." More on this in a minute.

5 Lists

OCaml has a built-in list datatype. The empty list is written [] and :: is an operation for “consing” an element on to a list. So to build a list with three integer elements, 1, 2, and 3, you’d write:

OCaml REPL

# 1 :: 2 :: 3 :: [];;
- : int list = [1; 2; 3]

The notation [1; 2; 3] is just a shorthand for the above.

The notation (list 1 2 3) is shorthand for the above.

There is a slight difference here. For one, OCaml lists must be homogeneous. You can have a list of strings or a list of numbers, but you can’t have a list of strings and numbers.

OCaml REPL

# ["a"; 3];;
Error: This expression has type int but an expression was expected of type
         string

In Racket, there is no such restriction:

Racket REPL

> (list "a" 3)

'("a" 3)

Also, in Racket, cons plays the role of both tupling (making pairs) and making lists (making a pair of an element and another list).

So in OCaml, you could make a pair ("a", 3). In Racket, you’d write (cons "a" 3). Note this is a pair and not a proper list. In OCaml, tuples and lists are disjoint things. In Racket, lists and tuples (pairs) are made out of the same stuff.

This can be confusing the first time you encounter it, so let’s go over it a bit more.

In Racket (or any Lisp), cons plays the role of both the pair constructor and the list constructor. Non-empty lists are a subset of pairs: they are pairs whose second component is a list (either the empty list or another pair whose second component is a list, etc.).

You can make pairs out of any kind of element and you can make lists out of any kind of elements. We can precisely define these sets as:

Racket REPL

; type ListofAny =

; | '()

; | (cons Any ListofAny)

; type PairofAny =

; | (cons Any Any)

Or, to give more useful parameterized definitions:

Racket REPL

; type (Listof A) =

; | '()

; | (cons A (Listof A))

; type (Pairof A B) =

; | (cons A B)

The functions first and rest operate on non-empty lists, producing the first element of the list and the tail of the list, respectively.

Racket REPL

> (first (cons 3 (cons 4 '())))

3

> (rest (cons 3 (cons 4 '())))

'(4)

These function will produce errors if given something that is a pair but not a list:

Racket REPL

> (first (cons 3 4))

first: contract violation

expected: (and/c list? (not/c empty?))

given: '(3 . 4)

> (rest (cons 3 4))

rest: contract violation

expected: (and/c list? (not/c empty?))

given: '(3 . 4)

On the other hand, the functions car and cdr access the left and right components of a pair (the names are admittedly awful and an artifact of Lisp history):

Racket REPL

> (car (cons 3 4))

3

> (cdr (cons 3 4))

4

When given pairs that are also lists, they behave just like first and rest:

Racket REPL

> (car (cons 3 (cons 4 '())))

3

> (cdr (cons 3 (cons 4 '())))

'(4)

6 Pattern matching

OCaml has a very nice pattern matching for letting you express case analysis and decomposition in a concise way.

Each pattern maching expression has a sub-expression that produce a value to be matched against and a number of clauses. Each clause has a pattern and an expression. The pattern potentially consists of data constructors, variables, and literals. If the value matches the first pattern, meaning the value and the template match up on constructors and literals, then the variables are bound to the correspond parts of the value, and the right-hand side expression is evaluated. If the value doesn’t match, the next pattern is tried, and so on. It’s an error if none of the patterns match.

So for example, we can write a functiion that recognize even digits as:

OCaml REPL

# let even_digit n =
    match n with
    | 0 -> true
    | 2 -> true
    | 4 -> true
    | 6 -> true
    | 8 -> true
    | _ -> false;;
val even_digit : int -> bool = <fun>

The patterns here, save the last one, are just integer literals. If n is the same as any of these integers, the value true is produced. The last case uses a "wildcard," which matches anything and produces true.

Here’s an example that matches a tuple, binding each part of the tuple to a name and then using those names to construct a different tuple:

OCaml REPL

# let swap p =
    match p with
    | (x, y) -> (y, x);;
val swap : 'a * 'b -> 'b * 'a = <fun>

Here the pattern uses a data constructor (the tuple constructor). It matches any value that is made with the same constructor.

Here is a recursive function for computing the sum of a list of numbers, defined with pattern matching:

OCaml REPL

# let rec sum xs =
    match xs with
    | [] -> 0
    | x :: xs -> x + (sum xs);;
val sum : int list -> int = <fun>
# sum [4; 5; 6];;
- : int = 15

We can do the same in Racket:

Racket REPL

> (define (even-digit n)     (match n       [0 #t]       [2 #t]       [4 #t]       [6 #t]       [8 #t]       [_ #f]))

> (define (swap p)     (match p       [(cons x y) (cons y x)]))

> (define (sum xs)     (match xs       ['() 0]       [(cons x xs)        (+ x (sum xs))]))

> (sum (list 4 5 6))

15

7 Datatypes

OCaml has the ability to declare new datatypes. For example, we can define type for binary trees of numbers:

OCaml REPL

# type bt =
   | Leaf
   | Node of int * bt * bt;;
type bt = Leaf | Node of int * bt * bt

This declares a new type, named bt. There are two variants of the bt type, each with their own constructor: Leaf and Node. The Leaf constructor takes no arguments, so just writing Leaf creates a (empty) binary tree:

OCaml REPL

# Leaf;;
- : bt = Leaf

The Node constructor takes three arguments: an integer and two binary trees. Applying the constructor to a tuple of three things, makes a (non-empty) binary tree:

OCaml REPL

# Node (3, Leaf, Leaf);;
- : bt = Node (3, Leaf, Leaf)

Binary trees are an example of a recursive datatype, since one of the variants contains binary trees. This means we can build up arbitrarily large binary trees by nesting nodes within nodes:

OCaml REPL

# Node (3, Node (4, Leaf, Leaf), Node (7, Leaf, Leaf));;
- : bt = Node (3, Node (4, Leaf, Leaf), Node (7, Leaf, Leaf))

Pattern matching is used to do case analysis and deconstruct values. So for example, a function that determines if a binary tree is empty can be written as:

OCaml REPL

# let bt_is_empty bt =
    match bt with
    | Leaf -> true
    | Node _ -> false;;
val bt_is_empty : bt -> bool = <fun>
# bt_is_empty Leaf;;
- : bool = true
# bt_is_empty (Node (3, Leaf, Leaf));;
- : bool = false

The patterns use the constructor names to discriminate on which constructor was used for a given binary tree. The use of the wildcard here is just saying it doesn’t matter what’s inside a node; if you’re a node, you’re not empty.

Recursive functions work similarly, but use variables inside patterns to bind names to the binary trees contained inside a node:

OCaml REPL

# let rec bt_height bt =
    match bt with
    | Leaf -> 0
    | Node (_, left, right) ->
      1 + max (bt_height left) (bt_height right);;
val bt_height : bt -> int = <fun>
# bt_height Leaf;;
- : int = 0
# bt_height (Node (4, Node (2, Leaf, Leaf), Leaf));;
- : int = 2

We do something very similar in Racket using structures. A structure type is like a (single) variant of a data type in OCaml: it’s a way of combining several things into one new kind of value.

Racket REPL

> (struct leaf ())

> (struct node (i left right))

This declares two new kinds of values: leaf structures and node structures. For each, we get a constructor, which is a function named after the structure type. The leaf constructor takes no arguments. The node constructor takes 3 arguments.

Racket REPL

> (leaf)

(leaf)

> (node 5 (leaf) (leaf))

(node 5 (leaf) (leaf))

> (node 3 (node 2 (leaf) (leaf)) (leaf))

(node 3 (node 2 (leaf) (leaf)) (leaf))

There is no type system in Racket, but we can conceptually still define what we mean in a comment. Just like in OCaml, we can use pattern matching to discriminate and deconstruct:

Racket REPL

; type Bt = (leaf) | (node Integer Bt Bt)

> (define (bt-empty? bt)     (match bt       [(leaf) #t]       [(node _ _ _) #f]))

> (bt-empty? (leaf))

#t

> (bt-empty? (node 5 (leaf) (leaf)))

#f

> (define (bt-height bt)     (match bt       [(leaf) 0]       [(node _ left right)        (+ 1 (max (bt-height left)                  (bt-height right)))]))

> (bt-height (leaf))

0

> (bt-height (node 4 (node 2 (leaf) (leaf)) (leaf)))

2

8 Symbols

One of the built-in datatypes we will use often in Racket is that of a symbol. A symbol is just an atomic peice of data. A symbol is written using the quote notation (quote symbol-name), which is abbreviated 'symbol-name. What’s allowable as a symbol name follows the same rules as what’s allowable as a Racket identifier.

Symbols don’t have a whole lot of operations. The main thing you do with symbols is tell them apart from eachother:

Racket REPL

> (equal? 'fred 'fred)

#t

> (equal? 'fred 'wilma)

#f

It is possible to convert between symbols and strings:

Racket REPL

> (symbol->string 'fred)

"fred"

> (string->symbol "fred")

'fred

There’s also a convient function that produces a symbol that is guaranteed to have not been used so far each time you call it:

Racket REPL

> (gensym)

'g22192

> (gensym)

'g22193

> (gensym)

'g22194

They can be used to define “enum” like datatypes:

Racket REPL

; type Flintstone = 'fred | 'wilma | 'pebbles

You can use pattern matching to match symbols:

Racket REPL

> (define (flintstone? x)     (match x       ['fred #t]       ['wilma #t]       ['pebbles #t]       [_ #f]))

> (flintstone? 'fred)

#t

> (flintstone? 'barney)

#f

There’s really not a precise analog to symbols in OCaml. (There’s something called a polymorphic variant, which plays a similar role to symbols in OCaml, but it wasn’t covered in CMSC 330.)

9 Quote, quasiquote, and unquote

One of the distinguishing features of languages in the Lisp family (such as Scheme and Racket) is the quote operator and its closely related cousins quasiquote, unquote, and unquote-splicing.

Let’s start with quote.

The “tick” character 'd is used as a shorthand for (quote d).

You’ve already seen it show up with symbols: 'x is the symbol x. It also shows up in the notation for the empty list: '().

But you can also write quote around non-empty lists like '(x y z). This makes a list of symbols. It is equivalent to saying (list 'x 'y 'z).

In fact, you can nest lists within the quoted list: '((x) y (q r)). This is equivalent to (list (list 'x) 'y (list 'q 'r)).

So, anything you can write with quoted lists, you can write without quoted lists by pushing the quote inward until reaching a symbol or an empty set of parenthesis.

You can also put strings, booleans, and numbers inside of a quote. As you push the quote inward, it simply disappears when reaching a string, boolean or number. So '5 is just 5. Likewise '#t is #t and '"Fred" is "Fred".

You can also write pairs with quote, which uses the . notation for separating the left and right part of the pair. For example, '(1 . 2) is equivalent to (cons 1 2). If you write something like '(1 2 3 . 4), what you are in effect saying is (cons 1 (cons 2 (cons 3 4))), an improper list that ends in 4.

In essence, quote is a shorthand for conveniently constructing data and is a very concise notation for writing down ad-hoc data. It serves much the same purpose as formats like JSON and XML, except there’s even less noise.

To summarize, with quote, you can construct

• strings

• booleans

• numbers

• symbols

• and... pairs (or lists) of those things (including this one)

The kind of things you can construct with the quote form are often called s-expressions, short for symbolic expressions.

We can give a type definition for s-expressions:

Racket REPL

; type S-Expr =

; | String

; | Boolean

; | Number

; | Symbol

; | (Listof S-Expr)

The reason for this name is because anything you can write down as an expression, you can write down inside a quote to obtain a data representation of that expression. You can render an expression as a symbolic representation of itself.

For example, (+ 1 2) is an expression. When run, it applies the function bound to the variable + to the arguments 1 and 2 and produces 3. On the other hand: '(+ 1 2) constructs a peice of data, namely, a list of three elements. The first element is the symbol +, the second element is 2, the third element is 3.

We will be using (subsets of) s-expressions extensively as our data representation of AST and IR expressions, so it’s important to gain a level of fluency with them now.

Once you understand quote, moving on to quasiquote, unquote, and unquote-splicing are pretty straight-forward.

Let’s start with quasiquote. The “backtick” character `d is used as a shorthand for (quasiquote d) and the “comma” character ,e is shorthand for (unquote e). The (quasiquote d) form means the same thing as (quote d), with the exception that if (unquote e) appears anywhere inside d, then the expression e is evaluated and it’s value will be used in place of (unquote e).

This gives us the ability to “escape” out of a quoted peice of data and go back to expression mode.

If we think of quasiquote like quote in terms of “pushing in” then the rules are exactly the same except that when a quasiquote is pushed up next to an unquote, the two “cancel out.” So `,e is just e.

For example, `(+ 1 ,(+ 1 1)) is equivalent to (list '+ 1 (+ 1 1)), which is equivalent to (list '+ 1 2).

So if quote signals us to stop interpreting things as expressions, but instead as data, quasiquote signals us to stop interpreting things as expression, but instead as data.. unless we encounter a unquote, in which case you go back to interpreting things as expressions.

The last remaining peice is unquote-splicing, which is abbreviated with “comma-at”: ,@e means (unquote-splicing e). The unquote-splicing form is like unquote in that if it occurs within a quasiquote, it means we switch back in to expression mode. The difference is the expression must produce a list (or pair) and the elements of that list (or pair) are spliced in to the outer data.

So for example, `(+ 1 ,@(map add1 '(2 3))) is equivalent to (cons '+ (cons 1 (map add1 (list 2 3)))), which is equivalent to (list '+ 1 3 4), or '(+ 1 3 4).

If the expression inside the unquote-splicing produces something other than a pair, an error is signalled.

10 Poetry of s-expressions

The use of structures lets us program in a style very similar to idiomatic OCaml programming. For each variant data type, we can define a structure type for each variant and use pattern matching to process such values.

However, we are going to frequently employ a different idiom for programming with recursive variants which doesn’t rely on structures, but rather uses symbols in place of constructors and lists in place of fields.

Let’s revisit the binary tree example, using this style.

Notice that leaf structureq is a kind of atomic data. It doesn’t contain anything and its only real purpose is to be distinguishable from node structures. On the other hand a node structure needs to be distinguishable from leafs, but also contain 3 peices of data within it.

We can formulate definition of binary trees using only symbols and lists as:

Racket REPL

; type Bt = 'leaf | (list 'node Integer Bt Bt)

So the following are binary trees:

Racket REPL

> 'leaf

'leaf

> (list 'node 3 'leaf 'leaf)

'(node 3 leaf leaf)

> (list 'node 3         (list 'node 7 'leaf 'leaf)         (list 'node 9 'leaf 'leaf))

'(node 3 (node 7 leaf leaf) (node 9 leaf leaf))

This formulation has the added benefit that we write binary trees as s-expressions:

Racket REPL

> 'leaf

'leaf

> '(node 3 leaf leaf)

'(node 3 leaf leaf)

> '(node 3          (node 7 leaf leaf)          (node 9 leaf leaf))

'(node 3 (node 7 leaf leaf) (node 9 leaf leaf))

We re-write our functions to match this new datatype definition:

Racket REPL

> (define (bt-empty? bt)     (match bt       ['leaf #t]       [(cons 'node _) #f]))

> (bt-empty? 'leaf)

#t

> (bt-empty? '(node 3                     (node 7 leaf leaf)                     (node 9 leaf leaf)))

#f

> (define (bt-height bt)     (match bt       ['leaf 0]       [(list 'node _ left right)        (+ 1 (max (bt-height left)                  (bt-height right)))]))

> (bt-height 'leaf)

0

> (bt-height '(node 3                     (node 7 leaf leaf)                     (node 9 leaf leaf)))

2

We even can use quasiquote notation in patterns to write more concise definitions:

Racket REPL

> (define (bt-empty? bt)     (match bt       [`leaf #t]       [`(node . ,_) #f]))

> (bt-empty? 'leaf)

#t

> (bt-empty? '(node 3                     (node 7 leaf leaf)                     (node 9 leaf leaf)))

#f

> (define (bt-height bt)     (match bt       [`leaf 0]       [`(node ,_ ,left ,right)        (+ 1 (max (bt-height left)                  (bt-height right)))]))

> (bt-height 'leaf)

0

> (bt-height '(node 3                     (node 7 leaf leaf)                     (node 9 leaf leaf)))

2

Moreover, we can embrace quasiquotation at the type-level and write:

Racket REPL

; type Bt = `leaf | `(node ,Integer ,Bt ,Bt)

11 Testing, modules, submodules

We will take testing seriously in this class. Primarily this will take the form of unit tests, for which we will use the rackunit library. To use the library, you must require it.

Here is a simple example:

Racket REPL

> (require rackunit)

> (check-equal? (add1 4) 5)

> (check-equal? (* 2 3) 7)

-------------------- FAILURE name:       check-equal? location:   eval:76:0 actual:     6 expected:   7 --------------------

The check-equal? function takes two arguments (and an optional third for a message to display should the test fail) and checks that the first argument produces something that is equal? to the expected outcome given as the second argument.

There are many other forms of checks and utilities for building up larger test suites, but check-equal? will get us a long way.

As a matter of coding style, we will place tests nearby the function they are testing and locate them within their own module. Let’s talk about modules for a minute.

In Racket, a module is the basic unit of code organization. Every file is a module whose name is derived from the filename, but you can also write modules without saving them in a file. For example:

Racket REPL

> (module bt racket     (provide bt-height)     (define (bt-height bt)       (match bt         [`leaf 0]         [`(node ,_ ,left ,right)          (+ 1 (max (bt-height left)                    (bt-height right)))])))

This declares a module named bt. It provides a single value named bt-height.

We can require the module from the REPL to gain access to the modules provided values:

Racket REPL

> (require 'bt)

> (bt-height 'leaf)

0

We could have also used the #lang racket shorthand for (module bt racket ...) and saved this in a file called bt.rkt. To import from a file in the current directory, you’d write (require "bt.rkt"). But this doesn’t work well in REPL.

For the most part we will organize our programs into single module files using the #lang racket shorthand. But we will place tests within a “sub”-module, i.e. a module nested inside of the module that contains the code it tests. We will use a special form called module+ which declares a submodule that has access to the enclosing module. Moreover, repeated uses of module+ will add content to the submodule. By convention, we will name the testing submodule test.

So here’s a second version of the bt module with unit tests included (and more code). Note the use of all-defined-out to provide everything:

Racket REPL

> (module bt2 racket     ; provides everything defined in module     (provide (all-defined-out))        (module+ test       (require rackunit))        (define (bt-empty? bt)       (match bt         ['leaf #t]         [(cons 'node _) #f]))        (module+ test       (check-equal? (bt-empty? 'leaf) #t)       (check-equal? (bt-empty? '(node 3                                       (node 7 leaf leaf)                                       (node 9 leaf leaf)))                     #f))        (define (bt-height bt)       (match bt         [`leaf 0]         [`(node ,_ ,left ,right)          (+ 1 (max (bt-height left)                    (bt-height right)))]))        (module+ test       (check-equal? (bt-height 'leaf) 0)       ; intentionally wrong test:       (check-equal? (bt-height '(node 3 leaf leaf)) 2)))

Requiring this module with make bt-height, but it will not run the tests:

Racket REPL

> (require 'bt2)

Running the tests only happens when the test submodule is required:

Racket REPL

> (require (submod 'bt2 test))

-------------------- FAILURE name:       check-equal? location:   eval:80:0 actual:     1 expected:   2 --------------------

Putting it all together, we can write the following code and save it in a file called bt.rkt. (You can right-click the file name and save the code to try it out.)

bt/bt.rkt

#lang racket

(provide (all-defined-out))

(module+ test

(require rackunit))

;; type Bt =

;; | `leaf

;; | `(node ,Integer ,Bt ,Bt)

;; Bt -> Boolean

;; Is the binary tree empty?

(define (bt-empty? bt)

(match bt

['leaf #t]

[(cons 'node _) #f]))

(module+ test

(check-equal? (bt-empty? 'leaf) #t)

(check-equal? (bt-empty? '(node 3

(node 7 leaf leaf)

(node 9 leaf leaf)))

#f))

;; Bt -> Natural

;; Compute the height of a binary tree

(define (bt-height bt)

(match bt

[`leaf 0]

[`(node ,_ ,left ,right)

(+ 1 (max (bt-height left)

(bt-height right)))]))

(module+ test

(check-equal? (bt-height 'leaf) 0)

(check-equal? (bt-height '(node 3 leaf leaf)) 1)

(check-equal? (bt-height '(node 2 leaf (node 1 leaf leaf)))

2))

From the command line, you can run a module’s tests using the Racket command line testing tool raco test:

shell

> raco test bt.rkt
raco test: (submod "bt.rkt" test)
5 tests passed

Or simply give a directory name and test everything within that directory:

shell

> raco test .
raco test: (submod "./bt.rkt" test)
5 tests passed

Picture This

OK, now let’s do something a little more interesting.

In your web browser, go to the page for the course notes:

http://www.cs.umd.edu/class/winter2021/cmsc388Q/Notes.html

Right click the image of the blue spaceship and select “Copy image.” Now go back to DrRacket and paste (Ctl+V) in the REPL and press Enter. You should see something like this:

Racket REPL

>

What you see here is that images are just another kind of values in Racket. Just like the literal 7 is a value which means the number 7:

Racket REPL

> 7

7

The blue spaceship is a literal value that means the blue space ship image.

You can do things like put it in a list:

Racket REPL

> (cons  '())

(list )

Just as there are operations on lists, there are operations on images.

These operations are available in the "2htdp/image" library. To import the library, run:

Racket REPL

> (require 2htdp/image)

This makes a bunch of operations available to us.

We can give the spaceship value a name:

Racket REPL

> (define spaceship     )

Now refering to that name means the blue spaceship image:

Racket REPL

> spaceship

There are things like image-width for computing the width (in pixels) of an image:

Racket REPL

> (image-width spaceship)

124

As you’ve probably guessed, there’s also image-height. But we can also do things like this:

Racket REPL

> (rotate 35 spaceship)

We can scale:

Racket REPL

> (scale 2 spaceship)

> (scale 0.1 spaceship)

There are operations for making new images:

Racket REPL

> (rectangle 400 200 "solid" "yellow")

And there are operations for combining images. The overlay is conceputally like + but for images: it takes two images and combines them together into an image. It combines the given images by placing the first one on top of the second:

Racket REPL

> (overlay spaceship            (rectangle 400 200 "solid" "yellow"))

We could of course, first scale the spaceship before placing on the background:

Racket REPL

> (overlay (scale 0.7 spaceship)            (rectangle 400 200 "solid" "yellow"))

So you can see that it’s pretty easy to programmatically construct images or you can copy and paste things into the source code itself, or you can load things off the file system or internet.

To learn more about what’s possible, read the 2htdp/image library. You can right-click any identifier provided by the library and select “view documentation” to see the docs for that function.

Alright, now let’s do something a little more animated.

Let’s make a function that is given an angle and produces a spaceship rotated by that many degrees:

Racket REPL

> (define (spin i)     (rotate i spaceship))

We can use it like this:

Racket REPL

> (spin 0)

> (spin 1)

> (spin 2)

> (spin 90)

> (spin 180)

We could make a big list of images using build-list. Here is how build-list works:

Racket REPL

> (build-list 5 add1)

'(1 2 3 4 5)

> (build-list 5 sqr)

'(0 1 4 9 16)

Now:

Racket REPL

> (build-list 45 spin)

(list                                                                                          )

Notice how when you were scrolling it might’ve looked at times like the spaceship was moving. An animation, after all, is just a collection of still pictures which are shown in rapid succession to trick our eyes into seeing movement.

There’s a related library called 2htdp/universe that provides a function called animate that does just this: try running

(require 2htdp/universe)

(animate spin)

The animate function is given a function from natural numbers to images and calls the function with 0, 1, 2, etc. at a rate of 28 times per second, showing the results in a new window.

It’s a little unfortunate that the animation looks bad because as the image rotate, it’s dimensions change are cropped by the window. We can clean things up by placing the spaceship on a larger background image. Here’s a revised version of spin:

Racket REPL

> (define (spin i)     (overlay (rotate i spaceship)              (empty-scene (* 2 (image-width spaceship))                           (* 2 (image-height spaceship)))))

> (spin 0)

> (spin 45)

> (spin 90)

Now try the animation again.

The animate function is actually a simple use of a more general system called big-bang. To achieve the same result, we could have written:

(big-bang 0

[on-tick add1 1/28]

[to-draw spin])

The big-bang system generalizes animate in that you have control over how “counting” works. You specify where to start and how to go from the current moment in time to the next. In fact, you don’t even have to count with numbers; you can count from an arbitrary value. Whatever function you give for the on-tick clause specifies how to go from the current value to the next value. These values are rendered into pictorial form with the function given in to-draw clause.

Be sure to read the big-bang documentation for details.

Chatting with Myself and Others

The big-bang system can do more than just animation. The ticking of time is just one of the several different kinds of events for which a big-bang program can react. Other kinds of events include mouse events, keyboard events, and even network events.

Let’s explore how the big-bang system works by developing a program that reacts to some of these other kind of events. We’ll try to build a chat system. It may seem a bit weird, but we’ll start by designing a chat client where there’s no else we can chat with; just ourselves. Later, we’ll revise the design so that it works to communicate with other people.

To start with, consider a simple chat program. Something that might look like this:

Here there’s a chat history which identifies each user and the message they sent, listed in chronological order (so the oldest is at the top). The user is typing their next message at the prompt and there is a cursor indicating where they are making edits to the text:

Should the user type backspace, the cursor will delete the letter to the left of the cursor:

Now they’re happy with the message, so they hit enter, which sends the message off and commits it to the chat history, giving a fresh prompt for the next message:

OK, let’s take an inventory of everything here. A chat consists of a collection of previous messages, each of which consists of a user name and the content of that message. There can be an arbitrary number of previous messages. There’s also the current message being composed, which has some content and a cursor.

Here’s a potential data type definition for representing the state of a chat program:

; type Chat = (chat ID Line (Listof Entry))

(struct chat (user line entries) #:prefab)

; type Entry = (entry ID String)

(struct entry (user str) #:prefab)

; type Line = (line String Index)

(struct line (str i) #:prefab)

; type ID = String

Here’s a representation of the chat we saw to begin with:

(chat "John"

(line "netflix and chiill?" 15)

(list (entry "Bobby" "go play with your watch collection")

(entry "Phil" "harsh but true")

(entry "Jerry" "I'm not even dead yet")

(entry "Jerry" "oh shut up John, you're not in the band")

(entry "John" "your body is a wond...")

(entry "Bill" "just hanging")

(entry "Jerry" "not much")

(entry "Phil" "nada")

(entry "Bobby" "sup")))

Designing the program top-down, we can design the main entry point for the chat client:

; String -> Chat

; Start a chat client with given user

(define (start-chat user)

(big-bang (chat user (line "" 0) '())

[on-key     chat-press]

[to-draw    chat-scene]))

Switch to a bottom-up view, let’s focus in on the actions that happen when editing the line. The user can delete the letter to the left of the cursor (if there is one). They can move the cursor left (if not already all the way to the left). They can move the cursor right (if not already all the way to the right). They can insert a single letter.

We can design a function for each of these tasks and write unit tests:

(module+ test

(check-equal? (right (line "abc" 0)) (line "abc" 1))

(check-equal? (right (line "abc" 1)) (line "abc" 2))

(check-equal? (right (line "abc" 2)) (line "abc" 3))

(check-equal? (right (line "abc" 3)) (line "abc" 3)))

; Line -> Line

; Move the cursor to the right

(define (right l) ...)

(module+ test

(check-equal? (left (line "abc" 0)) (line "abc" 0))

(check-equal? (left (line "abc" 1)) (line "abc" 0))

(check-equal? (left (line "abc" 2)) (line "abc" 1))

(check-equal? (left (line "abc" 3)) (line "abc" 2)))

; Line -> Line

; Move the cursor to the left

(define (left l) ...)

(module+ test

(check-equal? (del (line "abc" 0)) (line "abc" 0))

(check-equal? (del (line "abc" 1)) (line "bc"  0))

(check-equal? (del (line "abc" 2)) (line "ac"  1))

(check-equal? (del (line "abc" 3)) (line "ab"  2)))

; Line -> Line

; Move the cursor to the left

(define (del l) ...)

(module+ test

(check-equal? (ins (line "abc" 0) "z") (line "zabc" 1))

(check-equal? (ins (line "abc" 1) "z") (line "azbc" 2))

(check-equal? (ins (line "abc" 2) "z") (line "abzc" 3))

(check-equal? (ins (line "abc" 3) "z") (line "abcz" 4)))

; Line 1String -> Line

; Insert a letter into line

(define (ins l c) ...)