Introduction

This year, for the first time, we will be using Typed Racket as the programming language in CMSC 15100. Typed Racket provides automated checking for many kinds of common errors in your code, but it also introduces some new complexities that are not covered in the text book. The purpose of these notes is to provide supplementary information that will aid you in the programming assignments.

As we introduce new language features in class, we will extend this document.

For further reading, you can consult The Typed Racket Guide and The Typed Racket Reference.

An example

Racket is a dynamically typed language, which means that type errors are not detected until the erroneous code is actually executed. For example, we might define a function for squaring numbers.

;; sq : Number -> Number
;; return the square of a number
;;
(define (sq x) (* x x))

If we then attempt to apply it to two arguments or to the wrong kind of argument, we get a runtime type error

> (sq 1 2)
sq: expects only 1 argument, but found 2
> (sq "hi")
*: expects a number as 1st argument, given "hi"
>

In this simple example, waiting until runtime to find the error is not a big deal, but in larger programs such errors can be hidden from immediate detection. For example, consider the following (erroneous) function

;; f : Boolean Number Number -> Number
;;
(define (f flg a b)
  (cond
    [flg (sq a b)] ;; type error
    [else 1]))

Testing this function might not expose the error, since the error occurs on only one branch of the conditional. For example:

> (f #f 1 2)
1

In this simple example, an additional test case is sufficient to detect the error, but, in general, it may involve a significant amount of testing to check all of the potential dynamic type errors.

In Typed Racket, we write the type signature (or contract) of a function as part of the program’s syntax, instead of just as a comment. Returning to out sq function, we would write it in Typed Racket as follows:

#lang typed/racket

(: sq : Number -> Number)
;; return the square of a number
;;
(define (sq x) (* x x))

The first line is a directive that tells the Racket system that we are using the Typed Racket language. You will include this directive in all of your programs. The definition of the sq function is still three lines, but the first line is now a type annotation that tells the system what the type of the sq function is (a function from Number to Number).

(: f : Boolean Number Number -> Number)
;; silly test program
;;
(define (f flg a b)
  (cond
    [flg (sq a b)]
    [else 1]))

Basic types

Typed Racket defines a very large collection of basic types. We will only use a small subset of them in this course.

Numbers

Typed Racket divides numbers into many different types based on properties such as whether they are rational, integral, or not, their sign (positive or negitive), and how large their computer representation is. For this course, we use a small subset of these types, which are effectively organized in a heirarchy. We list them here in order of containment (_i.e., each type contains all of the previous types):

  • Natural

    is the type of the natural numbers (i.e., the integers that are greater or equal to zero).

  • Integer

    is the type of the integers.

  • Exact-Rational

    is the type of the rational numbers (i.e., numbers that can be written as a fraction).

  • Real

    is the type of the real numbers. Computer representations of the reals are necessarily inexact.

  • Number

    is the type of all numbers, including complex numbers.

Other basic types

  • Boolean

    is the type of logical values. It has two values true and false (these may also be written #t and #f).

  • Symbol

    is the type of symbols, which are sequences of identifier characters preceded by a single forward quotation mark. For example,

'red   '+   'abc-def  '+abc

are all examples of symbols.

  • String

    is the type of text strings.

Function types

Functions in racket take zero or more arguments and return a single result. We write the type of a function by listing the argument types, followed by the → symbol and the result type. For example, the type of a function that takes an Integer argument and a Boolean argument and returns a string is written as follows:

Integer Boolean -> String

Type annotations

As we have seen above, we can declare the type of a variable using the syntax

(: name : type)

Typed Racket accepts a number of different syntaxes for types and type annotations. First, function types can be written using a prefix notation; e.g.,

(: sq : -> Number Number)
(: f : -> Boolean Number Number Number)

While this syntax is more in keeping with the syntax of Racket, we prefer the infix syntax as it matches the syntax of type contracts in the text book and is easier to read. One can also leave off the second ":", but in that case function types need an extra set of parentheses.

(: sq (-> Number Number))
(: f (Boolean Number Number -> Number))

Function contracts

In this course (and in the text) each function definition is preceded by a contract and a header comment. Most of the contracts that we will use in this class can be captured by types and checked by the computer. The informal syntax used by the text for contracts is a close match to the formal syntax of types used by Typed Racket; and can be copied with only small changes. For example, the text gives the following contract, header, and purpose statement for the profit function:

;; profit : number -> number
;; to compute the profit as the difference between revenue and costs
;; at some given ticket-price
(define (profit ticket-price) ...)

The use of … to specify an incomplete function body is not supported in Typed Racket, so we give the function’s definition when we translate:

(: profit : Number -> Number)
;; to compute the profit as the difference between revenue and costs
;; at some given ticket-price
(define (profit ticket-price)
  (- (revenue ticket-price)
     (cost ticket-price)))

Notice that the only change that we had to make was to change "number" to "Number".

Variable definitions

Variable definitions should also be proceeded by a type annotation. The syntax is essentially the same as for functions. For example:

(: pi : Real)
(define PI 3.14159)

Testing

The student languages in DrRacket have a builtin testing mechanism called cehck-expect. This mechanism is also available in Typed Racket, but using it requires a bit more work. First, at the top of your definitions window (i.e., the beginning of the program) you will need a require directive as follows:

#lang typed/racket

(require typed/test-engine/racket-tests)

And at the end of your program, you need a command to run the tests:

(test)

There are two forms of test that you will use in this class. The check-expect form tests to see if an expression evaluates to an expected result.

(check-expect expr expected-expr)

For example, we can add tests for the sq function that we defined above:

(: sq : Number -> Number)
;; return the square of a number
;;
(define (sq x) (* x x))

(check-expect (sq 5) 25)
(check-expect (sq -1) 1)

When computing with real numbers, the results are often inexact. In that situation we use the check-within form to test if an expression evaluates to within a given delta of an expected result.

(check-within expr expected-expr delta-expr)

For example

(check-within (sq (sqrt 2)) 2 0.001)

Note that the test function runs all of the tests defined up to its invocation. Therefore, you should only invoke it once after all of the tests have been defined.

Querying types

It is possible to query the type of an identifier using DrRacket’s REPL using the :print-type function:

> (:print-type sq)
(-> Number Number)

Notice that Typed Racket prints function types using the prefix syntax. == Defining more types

Typed Racket provides mechanisms for defining both product and sum types.

Structs

As in the Chapter 6 of the textbook, Typed Racket provides the define-struct special form. The main difference is that unlike the form described in the book, in Typed Racket we must specify the types of the structure components. For example:

(define-struct Posn
  ([x : Real]
   [y : Real])
  #:transparent)

The other noticable difference is the #:transparent option, which tells Typed Racket to make this a transparent type (as opposed to an opaque type). Transparent struct types can be tested for equality in a check-expect and the contents of a transparent struct value will be printed in the REPL. While there are good software engineering principles for making types opaque, we will always use transparent structs in this course.

Note

The book describes a predefined posn type that is similar to the one we defined above. This builtin type is not available in Typed Racket.

The define-struct definition defines a new type named Name. It also generates the definitions of a bunch of operations on the struct type. For example, the definition of Posn generates functions with the following types:

(: make-Posn : Real Real -> Posn
(: Posn? : Any -> Boolean : Posn)
(: Posn-x : Posn -> Real)
(: Posn-y : Posn -> Real)

You may notice that the type of Posn? has three parts (Any, Boolean, and Posn). The first two are the same as any other function type and indicate that the predicate takes any value and returns a boolean. The third part, after the :, is a filter that tells the typechecker two things:

  1. If the predicate check succeeds, the argument variable has type Posn

  2. If the predicate check fails, the argument variable does not have type Posn

Predicates for all built-in types are annotated with similar filters that allow the type system to reason about predicate checks. This mechanism is called occurrence typing and allows functions, such as the following, to typecheck:

(: posn-x? : Any -> Integer)
(define (posn-x? p)
  (if (Posn? p) (Posn-x p) 0))

since the typechecker knows that p has type Posn in the ‘then’ branch of the if. This mechanism is restricted to arguments that are variables; testing the result of an expression and then expecting the

Note

Typed Racket also provides the struct special form, which has the same syntax as define-struct. The main difference is that the struct declaration introduces a function with the same name as the struct type.

Unions

Union types provide a mechanism to define a type that is one of several distinct choices. For example, we might define a representation of colored circles, where the available colors are red, green, or blue. We can use symbols to represent the distinct colors; i.e., 'red, 'green, and 'blue. A symbol in Typed Racket is its own type, as illustrated by the following code snippet:

(: R : 'red)
(define R 'red)

This kind of type is called a singleton type, since it is a type that has exactly one value. By unioning multiple singleton types, we can describe enumeration types. For example, our color type is the union of 'red, 'green, and 'blue. Two other useful singleton types are #t and #f (as one might guess, Boolean is the union of #t and #f).

We can define a function that maps colors to their names as follows:

(: color-to-string : (U 'red 'green 'blue) -> String)
;; convert a color to a string
;;
(define (color-to-string c)
  (cond
    [(symbol=? c 'red) "red"]
    [(symbol=? c 'blue) "blue"]
    [else "green"]))

Here the identifier U in the type stands for union. Also notice that the declared type of color-to-string guarantees that the else clause of the conditional will always be green.

Note

The order in which types appear in a union does not matter. For example, the type (U 'a 'b) is the same as the type (U 'b 'a).

Our definition of colored circles is as follows:

;; The represention of a colored circle
;;
(define-struct Circle
  ([center : Posn]
   [radius : Real]
   [color : (U 'red 'green 'blue)])
  #:transparent)

Now we can define a blue unit circle centered at (2, 3) as follows:

(: blue-circ : Circle)
(define blue-circ
  (make-Circle
    (make-posn 2 3)
    1
    'blue))

We can also define unions of all kinds of types. For example, we might a representation of colored rectangles:

;; The represention of a colored axis-aligned box
;;
(define-struct Rect
  ([center : Posn]
   [width : Real]
   [height : Real]
   [color : (U 'red 'green 'blue)])
  #:transparent)

and then define a function for getting the color from a shape

(: shape-color : (U Circle Rect) -> (U 'red 'green 'blue))
;; Get the color of a shape.
;;
(define (shape-color shape)
  (cond
    [(Circle? shape) (Circle-color shape)]
    [else (Rect-color shape)]))

This function is an example of the use of occurrence typing in a conditional. In the first clause of the conditional, the Circle? predicate determines that the shape variable has the type Color in the expression part and does not have that type in the rest of the conditional. Because the typechecker knows that the variable shape must be either a Circle or a Rect, it knows that the type of shape must be Rect in the else clause.

Type definitions

Since type expressions can get quite large and complicated, it is helpful to introduce names for such types. This objective fits nicely with the concept of a data definition that is introduced in the textbook (Section 6.4).

For example, instead of writing

;; A color is one of 'red, 'blue, or 'green.

we can give an explicit definition using the define-type construct

(define-type Color (U 'red 'blue 'green))

We can also give a name to our shape type:

(define-type Shape (U Circle Rect))

Subtyping

Union types give rise to a notion of subtyping; i.e., the idea that one type is contained in another. For example, the type 'red is contained in the type Color, so we say that 'red is a subtype of Color. Intuitively, you can think of subtyping in Typed Racket as corresponding to the subset relation of the sets of values in the types. For example, the value 'red is contained in the set of Color values {'red, 'green, 'blue}.

Another example of subtyping that you have already experienced is the hierarchy of numeric types. The type Natural is a subtype of Integer, Integer is a subtype of Exact-Rational, etc.

Subtyping comes into play when Typed Racket checks the types of arguments against the type of a function in an application. If an argument expression has a type that is a subtype of the expected type, then it is okay. For example, when checking the expression

(color-to-string 'red)

we have an argument of type 'red, which is a subtype of the expected type.

Patterns and pattern matching

Pattern matching is an elegant, useful feature of modern programming language design. Pattern matching is part of common idioms in functional programming languages including Standard ML, Haskell and their derivatives. Pattern matching is also part of the design of Typed Racket.

Programs that make use of pattern matching are cleaner, easier to read and more pleasant to work with than their pattern-free counterparts. Pattern matching is not addressed in How to Design Programs, but since it offers so many advantages, and no disadvantages, and is so well-suited to the style of programming taught in this course, we include it in our curriculum.

Typed Racket’s pattern matching offers a rich collection of syntactic forms, only some of which are included in this document. Note that you will find many other pattern matching forms in the language documentation, but, for the purposes of this course, you only need a few of the available forms.

Pattern matching basics

As conditional expressions are written with cond, pattern matching expressions are written with match. A match expression has the following general form:

(match exp_0
  [pat_1 exp_1]
  [pat_2 exp_2]
  ...
  [pat_k exp_k])

Match evaluation is similar to cond evaluation. First the expression exp_0 is evaluated to a value we’ll call v. Then v is compared against each pattern in turn, in the order given: pat_1, then pat_2, and so on, up to pat_k. If v matches pat_1, then the value of the whole expression is exp_1, and evaluation within the match goes no further. If pat_1 doesn’t match, then v is checked against pat_2, and the value is exp_2. Evaluation continues from pattern to pattern until a match is found (or none is).

Consider this match expression:

(match (+ 1 1)
  [2 "A"]
  [3 "B"])

In this case, (+ 1 1) is evaluated to 2. This is compared first against the first pattern in order, which is a constant pattern 2. This is a match, so the value of the whole expression is the string "A". With the following alteration, the value of the expression is "B":

(match (+ 1 2)
  [2 "A"]
  [3 "B"])

There are many useful kinds of patterns besides constant patterns: one such kind is variable patterns. A variable pattern consists of a variable name, and a) always succeeds and b) gives a name to the value matched. Consider this example:

(match (* 10 3)
  [n (+ n 1)])

The value of this expression is 31. Why? The expression immediately following match evaluates to 30. Then 30 is compared against the variable pattern n, which succeeds in matching (as variable patterns always do) and furthermore binds the name n to the expression’s value. When the expression (+ n 1) is evaluated, n is bound to 30, and we finally arrive at 31.

Because variable patterns always match, they can be used as catch-all or default patterns in a pattern match, playing a role not entirely unlike what else does in the last branch of a cond. For example:

(match (+ 8 9)
  [0 "zero"]
  [n "not zero"])

In this expression, the match of evaluated 17 against the constant pattern 0 fails. The match against n necessarily succeeds, and the value of the expression altogether is the string "not zero".

The variable pattern n in the last example is a suitable candidate for a wildcard pattern, written with the underscore character _. Recall that a variable pattern both matches a value and binds a name to it, but in this case (and many cases in practice) the name is not needed, since n is not subsequently used. In such cases as this, a wildcard pattern, informally known as a "don’t care" pattern, is a good choice. A wildcard pattern always succeeds in matching, like a variable pattern does, but doesn’t bind; that is, it associates no name with the matched value.

(match (+ 8 9)
  [0 "zero"]
  [_ "not zero"])

The underscore serves not only to catch any expression that falls past the constant pattern 0, but it also expresses clearly that the particular value of the matching expression is of no interest, only the fact that it did not match any previous pattern.

Matching structures and nested patterns

Matching against structures is a convenient way to, first, identify the particular struct under consideration, and also to name the individual components in the structure and thereby eliminate calls to selectors.

Define a point in 2-space as follows:

(define-struct Point
  ([x : Real]
   [y : Real])
  #:transparent)

Now assume there exists an expression of type Point bound to a variable p, and consider the following match:

(match p
  [(Point x y) (+ x y)])

This expression performs the (admittedly contrived) operation of adding together the x and y components of the point p. The pattern (Point x y) serves several purposes: Point ensures that p is actually a Point struct, and furthermore the names x and y are bound to its two components. Syntactically, this is a real bargain, although it will take practice and experience to appreciate why. Without pattern matching, a similar expression looks like this:

(+ (Point-x p) (Point-y p))

On the whole, the latter expression is no longer (in number of characters) than the first; however, in the part of the expression where the action is — namely, where x and y are added together — the former expression is a clean (+ x y), while the latter is cluttered up with selectors (Point-x and Point-y). Pattern matching often has this clarifying effect by separating the deconstruction of a compound value from computing with its elements.

Using nested patterns with nested structures pushes the advantages of structure matching still further. Consider a line segment structure containing two points as follows:

(define-struct Seg
  ([a : Point]
   [b : Point])
  #:transparent)

Now we consider the following (contrived) computation: to subtract the product of the segments y components from the product of its x components. We can write the expression with nested patterns like this:

(match s
  [(Seg (Point ax ay) (Point bx by)) (- (* ax bx) (* ay by))])

Compare that expression to this one that uses selectors:

(- (* (Point-x (Seg-a s)) (Point-x (Seg-b s)))
   (* (Point-y (Seg-a s)) (Point-y (Seg-b s))))

In the second expression, the selectors overwhelm the syntax and make reading the expression (comparatively) difficult; the matched alternative above (- (* ax bx) (* ay by)) is crystal clear by comparison.

Pattern matching in function definitions

Pattern matching is especially useful in the definition of functions. Here is a function definition using only selectors:

(: q1? : Point -> Boolean)
;; test whether the point is in the first quadrant
(define (q1? p)
  (and (positive? (Point-x p))
       (positive? (Point-y p))))

When we rewrite the function using a match, the code is not shorter, but its main expression is free of selectors and hence clearer:

(: pat-q1? : Point -> Boolean)
;; reimplementation of q1? using pattern matching
(define (pat-q1? p)
  (match p
    [(Point x y)
     (and (positive? x)
          (positive? y))]))

With nested structures, nested pattern matching cleans up and clarifies the computation to an even greater extent. The following two functions compute the same property of a line segment; compare the syntax of one to the other.

(: p1 : Seg -> Boolean)
(define (p1 s)
  (< (* (Point-x (Seg-a s)) (Point-y (Seg-b s)))
     (* (Point-x (Seg-b s)) (Point-y (Seg-a s)))))

(: p2 : Seg -> Boolean)
(define (p2 s)
  (match s
    [(Seg (Point ax ay) (Point bx by))
     (< (* ax by) (* bx ay))]))

Matches and disjoint unions

Recall the definition of the Shape type from above.

(define-type Shape (U Circle Rect))

We can use pattern matching to write functions that work over union types like Shape. For example, the shape-color function can be written using pattern matching as

(: shape-color : Shape -> Color)
;; Get the color of a shape.
;;
(define (shape-color shape)
  (match shape
    [(Circle _ _ col) col]
    [(Rect _ _ _ col) col]))

We use wild cards for the parts of the shapes that we are not interested in.

matching multiple expressions with match*

Typed Racket also provides a mechanism for matching against multiple values with multiple patterns. For example, say we wanted a function to test if two shapes are the same shape and color. We could write that as

(: same-shape-and-color? : Shape Shape -> Boolean)
;; test if two shapes are the same kind and have the same color.
;;
(define (same-shape-and-color? shape1 shape2)
  (match* (shape1 shape2)
    [((Circle _ _ col1) (Circle _ _ col2)) (symbol=? col1 col2)]
    [((Rect _ _ _ col1) (Rect _ _ _ col2)) (symbol=? col1 col2)]
    [(_ _) #f]))