Chapter 1

Starting with Typed Scheme

If you already know PLT Scheme, or even some other Scheme, it should be easy to start using Typed Scheme.

1.1  A First Function

The following program defines the Fibonnaci function in PLT Scheme:

(module fib mzscheme
  (define (fib n)
    (cond [(= 0 n) 1]
          [(= 1 n) 1]
          [else (+ (fib (- n 1)) (fib (- n 2)))])))

This program defines the same program using Typed Scheme.

(module fib (planet "typed-scheme.ss"  ("plt" "typed-scheme.plt"))
  (define: (fib [n : number]) : number
    (cond [(= 0 n) 1]
          [(= 1 n) 1]
          [else (+ (fib (- n 1)) (fib (- n 2)))])))

There are three differences between these programs:

• The Language: mzscheme has been replaced in the language position by (planet "typed-scheme.ss" ("plt" "typed-scheme.plt")).

• The Binding Form: define has been replaced by define: as the top-level definition form.

• The Type Annotations: Both the argument n and the result (appearing after the arguments) have been annotated with types, in this case number.

In general, these are most of the changes that have to be made to a PLT Scheme program to transform it into a Typed Scheme program.¹

1.2  Adding more complexity

Other typed binding forms are also available. For example, we could have rewritten our fibonacci program as follows:

(module fib (planet "typed-scheme.ss"  ("plt" "typed-scheme.plt"))
  (define: (fib [n : number]) : number
    (let: ([base? : boolean (or (= 0 n) (= 1 n))])
      (if base? 1
          (+ (fib (- n 1)) (fib (- n 2))))))))

This program uses the let: binding form, which, like define:, allows types to be provided, as well as the boolean type.

We can also define mutually-recursive functions:

(module even-odd (planet "typed-scheme.ss"  ("plt" "typed-scheme.plt"))
  (define: (my-odd? [n : number]) : boolean
    (if (= 0 n) #f
        (my-even? (- n 1))))

  (define: (my-even? [n : number]) : boolean
    (if (= 0 n) #t
        (my-odd? (- n 1))))

  (display (my-even? 12)))

As expected, this program prints #t.

1.3  Defining New Datatypes

If our program requires anything more than atomic data, we must define new datatypes. In Typed Scheme, structures can be defined, similarly to PLT Scheme structures. The following program defines a date structure and a function that formats a date as a string, using PLT Scheme’s built-in format function.

(module date (planet "typed-scheme.ss"  ("plt" "typed-scheme.plt"))

  (define-typed-struct my-date ([day : number] [month : str] [year : number]))
  
  (define: (format-date [d : my-date]) : str
    (format "Today is day ~a of ~a in the year ~a" (my-date-day d) (my-date-month d) (my-date-year d)))
  
  (display (format-date (make-my-date 28 "November" 2006)))

Here we see the new built-in type str as well as a definition of the new user-defined type my-date. To define my-date, we provide all the information usually found in a define-struct, but added type annotations to the fields. Then we can use the functions that this declaration creates, just as we would have with define-struct.

1.4  Recursive Datatypes and Unions

Many data structures involve multiple variants. In Typed Scheme, we represent these using union types, written (U t1 t2 ...)

(module tree (planet "typed-scheme.ss"  ("plt" "typed-scheme.plt"))
  (define-typed-struct leaf ([val : number]))
  (define-typed-struct node ([left : (U node leaf)] [right : (U node leaf)]))
  
  (define: (tree-height [t : (U node leaf)]) : number
    (cond [(leaf? t) 1]
          [else (max (tree-height (node-left t))
                     (tree-height (node-right t)))]))

  (define: (tree-sum [t : (U node leaf)]) : number
    (cond [(leaf? t) (leaf-val t)]
          [else (+ (tree-sum (node-left t))
                   (tree-sum (node-right t)))])))

In this module, we have defined two new datatypes: leaf and node. We’ve also used the type (U node leaf), which represents a binary tree of numbers. In essence, we are saying that the tree-height function accepts either a node or a leaf and produces a number.

In order to calculate interesting facts about trees, we have to take them apart and get at their contents. But since accessors such as node-left require a node as input, not a (U node leaf), we have to determine which kind of input we were passed.

For this purpose, we use the predicates that come with each defined structure. For example, the leaf? predicate distinguishes leafs from all other Typed Scheme values. Therefore, in the first branch of the cond clause in tree-sum, we know that t is a leaf, and therefore we can get its value with the leaf-val function.

In the else clauses of both functions, we know that t is not a leaf, and since the type of t was (U node leaf) by process of elimination we can determine that t must be a node. Therefore, we can use accessors such as node-left and node-right with t as input.

1.5  Giving Names to Types

When a complex type is used repeatedly in a program, it can be helpful to give it a short name. In Typed Scheme, this can be done with type aliases. For example, we could have used a type alias to represent our tree datatype from the previous section.

(module tree (planet "typed-scheme.ss"  ("plt" "typed-scheme.plt"))
  (define-typed-struct leaf ([val : number]))
  (define-typed-struct node ([left : (U node leaf)] [right : (U node leaf)]))
  
  (define-type-alias tree (U node leaf))
  
  (define: (tree-height [t : tree]) : number
    (cond [(leaf? t) 1]
          [else (max (tree-height (node-left t))
                     (tree-height (node-right t)))]))
  
  (define: (tree-sum [t : tree]) : number
    (cond [(leaf? t) (leaf-val t)]
          [else (+ (tree-sum (node-left t))
                   (tree-sum (node-right t)))])))

The defintion (define-type-alias tree (U node leaf)) creates the type alias tree, which is just another name for the type (U node leaf). We can then use this type in subsequent definitions such as tree-sum.