Functional Languages, Interpreters and Types: CS 350 Course Notes

If you take into a linguistics class, you will not take French one week, German the next, Mandarin after that, etc. Instead, you learn about the things that all languages are made of: sounds, words, syntax, semantics, etc. You might learn about the history of certain languages, and how some languages influenced each other, or how some languages have certain features while others don’t.

In the same way, this course is not about teaching you multiple different languages. It’s about teaching you what languages are made of. The idea is that you will then have the tools to understand the features of any language you encounter in your career. In particular, you will learn about semantics: what does a program mean, separate from a particular computer and input and environment that it’s run on. Some languages which are syntactically very different are semantically very similar, and some languages that look the same have very different features.

In this course, we will learn about functional programming, where a variable’s value never changes once it is set. Programming is focused around what a program is, not what a program does. There is no denying that functional programming is less popular in industry than imperative or object-oriented programming, so why are we going to learn it? We have a few reasons:

1. Functional languages have simple reasoning principles. In this course, code is not just a means to an end, but an object worthy of study. Just as one might study a bacterium or a mouse before studying human biology, we will examine simple languages before complex ones. While it is certainly possible to formally reason about code in languages like C++, Python, or Java, doing so is much more complicated, and is beyond the scope of an introductory class.
2. Functional languages are close to the “atoms” of programming languages. As we will see in the course, many concepts like mutable variables, loops, and objects are expressible using functions, datatypes, and recursion. Many of the concepts we language features we will learn about are obvious in functional languages, but implicit or hidden in other languages. So we can learn about those features more directly.
3. The functional paradigm is growing in popularity. Languages like F#, Clojure, Elixir, and Scala have introduced functional languages into existing ecosystems, yielding a bump in usage. More significantly, functional ideas are being added to more and more languages. Nearly every language has some kind of closure, with C being the main exception. JavaScript async is based around passing functions as arguments, and Rust’s design draws heavily from research on algebraic datatypes, pattern matching, and polymorphism.

You will not likely ever use Racket in industry (although the Naughty Dog video game company does use Racket to develop games like The Last of Us). But more importantly, I do not know what languages you will use in your career, and neither do you. So I hope this course can change the way you think about programming and understand what languages are made of, so that you are able to adapt and learn whatever language you need in your job ten or twenty years from now.

In addition to learning how to use language features, this course will teach you how to implement several of them. Interpreters are the simplest way to implement a programming language. To write a full-fledged compiler, one needs to understand machine code, memory layout, jumps, basic blocks, register allocation, etc. To write an interpreter, all we need is a few tree traversals.

More importantly, when we write an interpreter for a language in a purely functional source language, we get equations about programs. So we get a two-for-one: writing an interpreter for a language also serves to define the semantics of the language, and give us some rules and principles we can use to reason about programs in that language. So our interpreters will give us a way to think logically about programs in an abstract way, independent of machine-specific details, memory architectures, or execution contexts.

An interpreter is a program that is powerful enough to simulate every other program that has ever or will ever be written. Nevertheless, it is essentially just a recursive tree traversal, and can serve to show the simplicity and beauty that lies at the heart of computation.

Dr. Racket is the IDE for Racket, and language made using Racket, including Flit. To install it:

• Go to https://download.racket-lang.org/, select the appropriate installer for your system, download it and run it.

  On MacOS with Homebrew, you may also run brew install --cask racket.

  On Linux, you can install from Snap using sudo snap install racket. Many distributions also have their own packages, which you are welcome to use.

Dr. Racket is installed on computers in the following labs:

• CL 135.4
• CL 136

You can write, run, and submit your code from these computers if you do not have access to your own computer.

You will be provided with a password for your account via URCourses. If you wish to change your password, you may do so from Dr. Racket:

• Go to “File > Manage CS350 Handin Account”
• Enter your old and new passwords and submit

Do not use a password that is shared with another login. They are stored as MD5 hashes, which is secure enough for the handin tool, but not secure enough for sensitive personal information.

The editor window is where you will type your Racket program. The top of every file should begin with #lang flit, though if you’ve set up Racket as described above this will happen by default.

There are two main buttons you need on the toolbar.

First is the button, which will type-check and compile your code, as well as executing any tests or expressions that are in the file.

If there are syntax or type errors in your file, you will get an error message after clicking Run. You MUST read these error messages: code that produces a type or syntax error will be graded 0 by the handin tool, and the messages give you important information on how to fix the problem.

To jump to the location of the problem, click on the icon and

The other important button is the Handin Button. At the University of Regina, this looks like this: . When completing an assignment, clicking this button will submit your code to the handin server. This will run a few tests and, after a short time, return your grade, along with any tests that fail. Read the results of the test carefully, as they will tell you what your code is doing wrong, along with what result it should produce. You may hand in your code as many times as you like up until the deadline of an assignment, and each submission overwrites the last. There may be private tests on an assignment, where you are told that a test is failing but not provided information on which test that is. In these cases, read the problem specification carefully to determine if you have missed any edge-cases.

The interactions window features a Read-Evaluate-Print-Loop (REPL), where you can type in expressions to be read and evaluated, and have their results printed. This is very useful for quickly testing a piece of code you wrote, or running pre-existing code to better understand what it does. This is similar to the prompts that Python or JavaScript give you if you type python or node in a terminal window.

If your code contains no type or syntax errors, then anything that you define in the editor window can be used in the REPL.

All assignments are to be submitted using the Handin tool. There are two ways to do this:

• By clicking the “CS350 Handin” button in the Dr. Racket toolbar
  • This option is currently only available on-campus or when connected to the campus VPN, which you can set up using the instructions here
  • After you submit your code, you

• By uploading your file at https://racket.cs.uregina.ca/cs350-handin

  At any point, you can view the test results of your most recent assignment run, including your current grade, by logging in at https://racket.cs.uregina.ca/cs350-handin. The test results are also visible on URCourses.

Literals are expressions that evaluate to themselves, denoting fixed values of some type. For example:

3 ;; The number 3
#f ;; False (boolean literal)
#t ;; True (boolean literal)
"hello" ;; A String

If you write (foo bar baz) where foo is a keyword in Flit, then the result of the expression is computed however the keyword is defined.

Some keywords that we’ll see are if, let, type-case, and list.

Any expression of the form (f a) is interpreted as calling the function f with the argument a, for any expressions f and a, as long as f isn’t a keyword. This extends to functions with multiple arguments: (f a b c d ...) is a call to function f with arguments a, b, c, d, etc.

Function calls are the “default” for an expression with parentheses: any time there’s an expression (f a b c...), it is interpreted as a call to f unless f is a special Flit keyword.

There are no infix operators in Racket. There are only function calls. +, *, modulo, <, >, and = are all just normal functions.

So in C++, we might write:

!((3 + 4 * 5) == 23); // Type bool

The Flit equivalent of this is:

(not (= (+ 3 (* 4 5)) 23))

• * has two arguments, 4 and 5. It produces a number.
• + has two arguments, 3 and the result of (* 4 5). It produces a number.
• = has two arguments, the result of (+ 3 (* 4 5)) and 23. It produces a boolean.
• not has one argument, the result of (= (+ 3 (* 4 5)) 23).

In the C++ version, the operator precedence told us that * was applied before +. In Flit and other S-Expression based languages, there is no need for operator precedence rules. The brackets make it clear what order the operations are being applied.

You do not need to count parentheses in Dr. Racket. If you put your cursor right before the opening bracket, it will highlight up to the closing bracket. Use this if you are getting syntax errors with brackets. Here, we have used color to indicate the matching brackets.

One of the goals of this course is to answer the question: what do programs mean?

It is tempting to say that the meaning of a program is what happens when you execute it on a CPU. But does this mean a program means something different when you run it on an Intel CPU vs. on an ARM chip? If you run a program twice and the OS allocates different addresses in memory, have you actually run two different programs? These are undesirable, because it means that one piece of source code can have multiple different meanings depending on the context you use it in.

You definitely have an informal notion of semantics in your head. When you look at a piece of code and imagine how it runs, you aren’t actually allocating memory addresses

In this course, we will take this informal idea of semantics, and make it into something formal that we can reason about logically.

Most of the programming languages that you have likely seen so far have mutable variables:

C, C++, Java, Python, JavaScript, Swift, and Go all have mutable variables. When you call a function or method, the result might be different each time you call it, even if the arguments are the same, because the body of the function can might access variables whose value has changed.

By contrast, Flit is a purely functional language:

In Flit, the value of an expression only depends on the initial values of the variables in that expression. This is because all variables in Flit are immutable:

Variables in Flit are more like the variables you have seen in mathematics. Consider the equation for a line, \(f(x) = mx + b\). The line is described by the different \(f(x)\) values that are possible for all the different values of \(x\), but when we’re computing a value for \(f(x)\), the value of \(x\) never changes during that computation. Each input value for \(x\) produces a single value for \(f(x)\), and the value of the output only depends on the values of the inputs.

In languages with mutable variables, the equals sign is a lie! Consider the following C++ code:

int x;
x = 3;
cout << x;
x = 4;

We have two “equations”, x = 3 and x = 4. But clearly we don’t have 3 = 4. So we can’t really say what the variable x means without talking about the state of memory at a particular point in time.

In purely functional languages, we can reason about actual equality. This gives us a very convenient way to describe what a program means, separately from any particular hardware. It also allows us to design programs using recipes, which we will learn about in the chapter on types.

It is possible to define semantics for programs with mutable variables, but that is (1) more complicated, and (2) ends up translating the programs to something that looks like a purely functional version anyways. We’ll see a bit more of this when we learn about tail recursion.

We will describe the semantics of Flit using equations. Here is our first semantic equation:

For example:

(+ 3 4) = 7
(+ 0 2) = 2

Notice that we have to distinguish “sum” in the mathematical sense from the symbol +. We are saying that, the function named + in flit takes in two numbers, and its value is those two numbers added together.

If you type (+ 2 3) into the bottom window of Dr. Racket, you will see output that looks like:

- Number
5

The value of the expression is 5, but Racket is also informing us that the type of the expression is Number. If you instead write (and #t #f), we will get a value of #f with a type of Boolean. And if you write "hello", we will get a value "hello" with the type String.

We will learn more about types in a later chapter.

Let’s use the equational rules we have so far to evaluate some example code to a result.

(if (< 3 4) (if (= (+ 2 6) 4) (* 3 33) (+ 50 50)) 9001)

We can deduce this result by applying our rules. We use the underscore _ to show which part of the expression is being simplified by the rule.

Evaluating examples like this will get much more interesting once we have functions and variables, which we’ll see below.

Functions are defined using the define keyword. The name of the function occurs in brackets, followed by the name of its input variables. For example:

(define (square x) ;; Gives a name to the input variable
   (* x x)) ;; Return value for whatever the input is

It is not a coincidence that the function is defined using similar notation to function calls: the definition is saying “for any value x, the value of (square x) is defined to be (* x x)”. Try pasting the definition of square into your code window, then typing (square 5) into the bottom window (i.e. the REPL). You should get a result of 25.

In our definition, x is just a name for a variable we chose. It would be exactly equivalent to write:

(define (square someNumberInput) ;; Gives a name to the input variable
   (* someNumberInput someNumberInput)) ;; Return value for whatever the input is

A key skill in this course is paying attention to which things are keywords and which things are arbitrary names we choose.

We can use any expression in the body of a function. Conditionals are now useful, since we can choose to do something different depending on the value of a function’s input. For example, to calculate the absolute value of a number:

(define (abs num)
  (if (> num 0)
      num
      (* num -1)))
     
(abs 3) ;; Gives 3
(abs -2) ;; Gives 2

This says “if the input num is greater than zero, return num. Otherwise, multiply num by -1 and return that”.

We can define multiple argument functions by giving multiple variable names when we define a function, and can call a function with multiple variables.

(define (triangleArea base height)
  (/ (* base height) 2))
 
(triangleArea 3 4) ;; Gives 6

Again, base and height are just the names we chose to give the input variables.

We can capture the above intuition for functions as a formal rule. Fundamentally, functions are about substitution:

The above toThePowerOf4 example looks like the following in Flit:

  (define (toThePowerOf4 x)
    (let ([xSquared (* x x)])
    (* xSquared xSquared)))
 
  (toThePowerOf4 2) ;; Gives 16

The syntax is as follows. We have:

• The keyword let
• A set of (usually round) brackets
• A sequence of variable-definition pairs (usually in square brackets)
• A final expression, which uses the defined values to compute a value

Note that the round vs. square brackets are just for readability. One can use round brackets everywhere and it will work the same.

In the above example, when we call (toThePowerOf4 2), the number 2 is used as the value for x. Then, a local variable xSquared is defined with the value * 2 2, which is 4. Finally, the result of the whole let expression, and the function call itself, is * xSquared xSquared. Since xSquared was defined to be 4, this gives us 16.

We can define multiple variables at once, and we can even use previous definitions when defining later variables. This is the reason for the nested brackets above: the first (round) set of brackets is around the sequence of variable declarations, and each square brackets in those round brackets contain a variable-expression pair. For example:

  (define (sumOfSquares x y)
    (let ([xSquared (* x x)]
          [ySquared (* y y)])
      (+ xSquared ySquared)))
     
  (sumOfSquares 2 3) ;; Gives 13

We may sometimes write let* instead of let, since this is the syntax for multiple definitions in Racket that can refer to previous variables. In Flit let and let* are defined to be identical.

Just as with functions, we can precisely describe the meaning of let-expressions using substitution.

Intuitively, to run a let, we through the list of variables, computing its value from the given expression, using the values of previous variables where necessary. Finally, we get to the final expression, where we replace the variables with the values we had previously computed. The value of the final expression is the value of the entire let expression.

Anything we can write with let, we can write without, by replacing each variable with its value. In a language with no side-effects, like Flit, there will be no difference in the results, although it might be slower, since some computations might be run more times than the would have with let.

In the theory of programming languages, it is conventional to use the colon `:` to mean “has type”. So when we write x : Number, this means that x is an expression that has type Number.

There is a version of this you can use in Flit. For any expression e, you can write (has-type e : T), and the compiler will check that e actually does have type T. For example:

(has-type 3 : Number)
(has-type #t : Boolean)
(has-type "hello" : String)

Note that this doesn’t do anything. It just takes whatever expression you give it, and produces that same expression as a result, unless the type you’ve given mismatches the expression’s actual type, in which case the compiler raises an error.

Flit has type inference, meaning that it can deduce the types of expressions without the programmer writing them down. So why bother writing types?

• Writing a type is like running an infinite number of tests. The compiler ensures that for every possible input to the program, the inputs to each function will match what the function expects.
• Types are a sanity check: if you have one set of types in your head, but the actual type of some code is different, writing down what you expect the types to be lets you know, early on, if your intuition does not match the code.
• Types are an important form of documentation. When you look at a function in an API or library, the first question is often “how the heck do I call this thing?” Types make it very clear exactly how you should invoke a function. Even in languages like JavaScript and Python, types have been adopted to a limited degree for the purposes of documentation.

There are two man questions to ask when looking at a type, which will help to understand that type:

• How can I directly create a value of this type?
• How can I directly use a value of this type?

We specify “directly” because you can always create a value of type T by calling a function that returns type T, and use a value of type T by giving it to a function that takes a T as input. But how are would those functions be defined? Eventually you need some primitive operations for dealing with values of a type.

Much like you’ve seen in C++, Flit has built-in types Number, String, and Boolean.

In Flit, if is not a function. The reason for this is that we don’t want to evaluate both branches of the if, just the true branch or the false branch, depending whether the condition was true or false. If we have “if some condition, then fire the missiles, else print OK”, you don’t want to fire the missiles, print OK, and then check afterwards which one was the correct action to take. This will be very important later with recursion, where only evaluating one branch is critical to making sure things don’t run forever.

Because if is not a function, we can’t give it a function type. Instead, we have to specify a rule, which is built into the Flit compiler, for when an if expression is or isn’t well typed. The rule is as follows:

There are two ways to look at this rule. One is from a checking perspective. Suppose the programmer writes (if x y z). Then the Flit compiler will:

• check that x has type Boolean
• check that y and z have the same type, regardless of what that type is. Let’s call this type T.
• Assign T as the type of the whole expression (if x y z), which is used to check however it is used.

So Flit does not let you write (if x 3 "hello"). Every expression in Flit must have a type, but what would the type of this expression be? It can’t be Number, since we get a String if x is false. But it can’t be String since this doesn’t work if x is true.

The second perspective is from a building perspective. Say we’re trying to make a value of some type T. The typing rule for if says that, one way to build a T is with a boolean, and two other values of type T. We’ll see more about this perspective in the section on holes.

We’ve already seen some examples of function types with our primitive operations on numbers and strings. The function type (S -> T) is the type of functions that take an argument of type S and produce a return value of type T.

There are two typing rules for functions: one for making functions, and one for calling functions.

Some functions in Flit are polymorphic, meaning they work with any number of types. This is similar to templates that you might have seen in C++, like vector<T>, which, for any type T, is the type of vectors whose elements are of type T. Then if you call push_back(x) on a value of type vector<int>, the x you give should have type int, and if you call it on vector<bool>, then x should be a boolean, etc. We will see the syntax for polymorphism, and many examples, in our section on lists.

There is an informal process to writing code in a functional language with holes. To write a function with type (T1 T2 ... T_N -> S)

• Write a dummy function with the correct type
  • Leave the function’s body as TODO.
• Write some tests that capture the expected behaviour of the function
• Repeat until all tests pass and the function has no more holes:
  • Pick a hole
  • Fill in that hole with something that matches the goal type
    • This might contain more holes
  • If a test fails, find the part of the code producing the wrong output and replace it with a TODO

If programming is like building a sculpture, then typed functional programming is like building with Lego. There are many types of pieces, but they all have to fit together in a certain way.

There are standard things we can do when trying to replace a hole in a function with an actual implementation. Just like Lego, the pieces of a functional program fit together in a predictable way. Below are some common steps you might take when trying to write a function:

We consider only natural numbers \(\mathbb{N}\), e.g., whole, non-negative numbers, e.g. 0,1,2.... Every natural number is equal to either:

• 0, or;
• monePlus for some other natural number, e.g. m = n-1

What this means for recursion is that, 0 will be the typical base case, and when (> n 0) is true, the typical recursive call we will make is with argument (- n 1).

To start, we’ll look at how to program by cases for natural numbers, without recursion. As an example, consider a function that we’ll call predecessor. For positive numbers, (predecessor n) is just (- n 1), e.g. the number right before that number. However, if we want our result to be non-negative, then we can’t do (- 0 1). So we’ll define (predecessor 0) to be 0.

Essentially, the predcecessor function moves one step back on the number line, unless we’re at the end, in which case it doesn’t move at all.

As Flit code, it looks like this:

(define (predecessor [n : Number])
  : Number
  (if (zero? n)
      0 ;; zero case
      (- n 1)) ;;non-zero case
)
;; tests
(predecessor 5)
(predecessor 9001)
(predecessor 0)

Running those tests gives the expected results:

Let’s look a little closer at what this function does. It starts with an input n, which we know nothing about, except that it is a number. To learn something about it, we check if it is zero. (Recall that zero? has type (Number -> Boolean)). In the case that it is zero, we return zero, which matches the specification above. If it is not zero, and we assume that it was a natural number to begin with, then it is safe to subtract one from it. So in the case that n is not zero, we can return (- n 1).

The format of predecessor is quite general, and can be used any time we want a function with different cases depending on if a number is zero or not. The template looks like this:

(define (NUMBER_NONREC_TEMPLATE [n : Number])
  : 'T
  (if (zero? n)
      TODO ;; zero case
      (let ;;non-zero case means that n is one plus some smalelr number
          ([nMinus1 (- n 1)])
        TODO)))

This is valid Flit code, which you can copy when completing your assignments. It won’t run, because each branch is just a TODO The template can be modified to add extra parameters of any type, and we have left the return type as a generic type 'T, which you can replace with whatever the return type is for the function you’re trying to write.

What this template says is, if you’re writing a function that looks at a number, and you want to produce a return value of type 'T, then it is enough to give a 'T to be returned for when n is zero, and to give a way to compute a 'T from (- n 1) when n is greater than zero. We make a new variable named nMinus1, and give it the value (- n 1), assuming that whatever fills in the second TODO will refer to that variable. It isn’t strictly necessary to use a let and a variable here, but it saves us from possibly having to write (- n 1) a bunch of times, and makes it more clear that we have decomposed n into 1 plus some smaller value.

There aren’t a lot of useful functions we can write with this template. We need to make it more powerful by adding recursion, which we do in the next section.

One thing to notice about the template above is that, as long as our number is a non-negative integer, there are only a finite number of times that we can decompose a number into the number one smaller before we hit zero. So if we make a function that calls itself, but that only ever calls itself on n-1 when computing (f n), there will be a finite number of recursive calls, since we will eventually hit a base case of zero.

This means that you can trust the recursion: you do not need to “unroll” the recursion in your head and think about a sequence of functions calling itself. Instead, you can just pretend that you already have a magic oracle which will give the correct answer for the function you’re trying to write, as long as you only call it on smaller numbers than the current input.

To see this, let’s look at the factorial function, which is kind of the “hello, world” of recursion. You might remember from math class that \(n! = 1 \times 2 \times \ldots \times n\). So:

• \(0! = 1\)
• \(1! = 1\)
• \(2! = 1 \times 2 = 2\)
• \(3! = 1 \times 2 \times 3 = 6\)
• … etc.

It might seem a bit strange, but \(0!\) is defined to be 1², the reasons for which will be more clear once we try writing our recursive function. A general guideline is that, for something with addition, zero is a good value for the base case, and for multiplication, one will be a good value. If you chose zero, and then multiplied it with anything, you would only ever get zero, which is usually not what you want.

How can we write a function that computes factorial in Flit? We can start with our template.

(define (factorial [n : Number])
  : Number
  (if (zero? n)
      TODO
      (let
          ([nMinus1 (- n 1)])
          TODO)))

We know that factorial takes a number as input, and returns a number as output, so we know the types for our template. And we even already know what we should return if n is zero, since we saw above that \(0! = 1\). So we can fill in the first TODO:

(define (factorial [n : Number])
  : Number
  (if (zero? n)
      1
      (let
          ([nMinus1 (- n 1)])
          TODO)))

Now the question is, how can we caculate the factorial for \(n-1\)? Remember, the rule with recursion is we can assume the function gives the right result as long as we call it on a smaller input. So we can call ourselves recursively on nMinus1 and be confident that what it returns is the correct value for \((n-1)!\). We’ll make a new variable for the result of this recursive call and add it to what we have so far:

(define (factorial [n : Number])
  : Number
  (if (zero? n)
      1
      (let
          ([nMinus1 (- n 1)]
           [factnMinus1 (factorial nMinus1)])
          TODO)))

So now we have the value of (factorial (- n 1)), and we need to return the correct result for (factorial n). Going by our pen-and-paper definition of factorial, we can see that \((n-1)! = 1 \times 2 \times \ldots n-1\), and that \(n! = 1 \times 2 \ldots \times n-1 \times n = (n-1)! \times n\). So given the value of (factorial (- n 1)), we can get the factorial of n by multiplying by n:

(define (factorial [n : Number])
  : Number
  (if (zero? n)
      1
      (let
          ([nMinus1 (- n 1)]
           [factnMinus1 (factorial nMinus1)])
          (* n factnMinus1))))
         
;; Test it now that we can run it
(factorial 0)
(factorial 1)
(factorial 2)
(factorial 3)
(factorial 4)
(factorial 5)

Running this code, we can see that it gives the correct results:

1
1
2
6
24
120

The way we figured out factorial is broadly applicable to anything we are computing with natural numbers. In general, the template for recursion on natural numbers is as follows:

(define (NUMBER_REC_TEMPLATE [n : Number])
  : 'T
  (if (zero? n)
      TODO ;; base case
      (let
          ([nMinus1 (- n 1)]
           [recursiveResult (NUMBER_REC_TEMPLATE  nMinus1)])
          TODO)))

The template is exactly like our non-recursive version, except that we make a recursive call on (- n 1) in the non-zero case.

This means that, to write a function computing something for a value n, it is enough to figure out:

• What the function should return for \(0\) (base case)
• Given the result of the function for \(n-1\), what should the result for \(n\) be

The challenge of writing a recursive function is figuring out what the base case should be, and figuring out what to do with the recursive result to get the right final result. The recipe gives you the structure of your code, but these last steps require cleverness, or at least trial and error.

To create a list in Flit, we make an S-Expression that begins with the list keyword. Each thing after is an element that is in the list. For example:

(list 1 2 3)

This is the list containing 1, 2, and 3. The order matters: (list 1 2 3) is not the same as (list 3 2 1). We can give any expressions as the arguments to list, and Flit will evaluate them when making the list. For example:

(list (+ 3 5) (* 2 2) (if (zero? 0) 99 100))

This produces (list 8 4 99).

There is a very important list, called the empty list, which in Flit is written '(). You can also write (list ) i.e. with no arguments, or you can write empty, or (empty), and they will produce the same thing. The empty list is often called nil or null for historical reasons, where they were represented with a null pointer.

For every type T in Flit, there is a type (Listof T). A value has type (Listof T) if it is a list whose elements are all of type T. Critically, Listof is not a type. Instead, it is called a type constructor: you give it a type T, and it makes the type of lists of T values. So (Listof Number), (Listof String), and (Listof Boolean) are all types, but Listof on its own is not.

Flit lists are homogeneous: they only contain elements of the same type. So there is no way to write (list 1 #t "hello"), because this does not fit (Listof Number) or (Listof Boolean) or (Listof String). This is similar to arrays in C++, but is different from lists in untyped languages like Python or JavaScript.

Because (Listof T) is a type whenever T is, it is a valid type to give to Listof. So (Listof (Listof Number)) is a valid type, whose elements are lists, where each element of such a list is itself a list with number elements. There can be lists, lists of lists, list of lists of lists, etc. However, we cannot mix levels. One cannot write (list 3 (list 4 5) because the elements are not all the same type: 3 has type Number, while (list 4 5) has type (Listof Number).

Many list operations are polymorphic: they work on lists, regardless of what type of elements are in that list. For example, consider the type of the append operation which concatenates two lists together:

append : ((Listof 'a) (Listof 'a) -> (Listof 'a))

This says that append takes any two lists, as long as they have the same element type, and produces a new list whose elements are the same type as it. The 'a here is a type variable, e.g. a placeholder which can stand in for any type. Any time you see a single-quote before a name in a type, it denotes a type variable, so 'b, 'myVariable, and 'foo are all type variables.

When you call append, Flit figures out what concrete type will replace the type variable. So (append (list 1 2) (list 3 4)) is allowed, and produces (list 1 2 3 4). Flit figures out that replacing 'a with Number will make the call work, and hence the return type of the function is (Listof Number).

List literals are good when we know exactly what should be in our list at the start, but in many cases we want to programatically create lists throughout our function.

In our sum above, we did two things that are extremely common when doing recursion with lists:

• We used a call to empty? to make sure that it was safe to call first and rest. This is less than ideal, since there was nothing stopping us from accidentally calling them in the empty case.
• We declared new variables h and t, which contained the head and tail of the original list in the non-empty case.

These two operations are so common in Flit that there is a special syntax which combines them, while also providing the safety that first and rest are missing. The syntax is called pattern matching, and is used with the keyword type-case in Flit. Using it in sum looks like this:

(define (sum [myList : (Listof Number)])
  : Number
  (type-case (Listof Number) myList
    [(empty)
       0]
    [(cons h t)
       (+ h (sum t))]))

There are several things happening at once here.

• The first keyword (type-case ...) signals that we are beginning a pattern match expression
• The second part, (Listof Number) tells Flit what the type of the thing we’re matching on. We need this because, as we will see later, Flit allows you to match on any datatype you define.
• The third part, myList, is the expression that we’re matching on. That is, it’s the thing of type (Listof Number) that the pattern-match will look at to check if it is empty or not.
• After that, we have a list of branches. Each branch contains two parts: a pattern that we match myList against, and a result to produce if myList contains that pattern.
• The first branch’s pattern is (empty), and its result is 0. So this match says “if myList is empty, then return 0”.
• The second branch’s pattern is (cons h t). Here, cons is the constructor of the pattern, and h and t are variable names that we have chosen

Essentially the pattern match is saying “for whatever myList is, look at it. If it is empty, then produce 0. Otherwise, if it is cons of something and something else, then store that first something in the variable h, store that second something in the variable t, and evaluate (+ h (sum t)) using the values we just stored in h and t.”

So pattern matching combines the operations of (1) checking whether the list is empty or not, (2) getting the head and tail out of a non-empty list, and (3) declaring new variables to store the head and the tail of the list to use in the result we are producing.

It is convention to have each branch surrounded by square brackets, but using round brackets instead would make no difference to how the code works. Likewise, having the pattern and result of each branch on a separate line makes things more readable, but is not required.

The process we used for sum applies generally: checking if a list is empty, returning a base case result if it is, and making a recursive call on the tail of the list if it isn’t. Just like with numbers, we can write a general template for list recursion:

(define (LIST_REC_TEMPLATE [myList : (Listof 'elemType)])
  : 'T
  (type-case (Listof 'elemType) myList
    [(empty)
      TODO]
    [(cons h t)
       (let ([resultForTail (LIST_REC_TEMPLATE t)])
         TODO)]))

That is, regardless of what problem we are solving for a list, if we want to process the elements one by one, we can pattern match on the list. We return some base case result of it is empty; which result we return depends on what problem we’re trying to solve. In the case that the list is not empty, we name its first element h (for head) and the rest of the list t (for tail). Since t is smaller than myList (it is one element shorter), it is safe to make a recursive call on it, the result of which we name resultForTail. The problem-specific part is taking h, t, and resultForTail and putting them together in the way that gives the desired output for whatever specific problem it is you’re trying to solve.

To see our template in action, we’ll look at some examples

To create a pair out of values x and y, in Flit one writes (pair x y). If x : S and t : T, then (pair x y) : (S * T). This type is saying if you take an S and take a T and put them together in a pair, then the result will contain an S AND a T.

For example:

(pair 3 #t) ;; Has type (Number * Boolean)
(pair "Hello" 8) ;; Has type (String * Number)
(pair (list 1 2 3) 7) ;; Has type ( (Listof Number) * 7)

Every pair has exactly two elements: one cannot write (pair 3) or (pair 4 5 6) in Flit. If you need more than two elements, you can always chain pair types: the type (Number * (Number * Number)) contains a number AND a pair, which in turn contains two numbers. However, in most cases it is better to define a custom datatype for more than two elements.

There are only two primitive operations on a pair: you can either access the first element, or access the second element. For any pair pr : ('S * 'T), we have (pairFst pr) : 'S and (pairSnd pr): 'T. That is, if you have an S and a T, then the first thing you have is an S, and the second thing you have is a T.

For example, let’s look at the pairs we made above.

(define p1 : (Number * Boolean)
   (pair 3 #t)) ;; Has type (Number * Boolean)
(define p2 : (String * Number)
  (pair "Hello" 8)) ;; Has type (string * number)
(define p3 : ((Listof Number) * Number)
  (pair (list 1 2 3) 7)) ;; Has type ( (Listof Number) * 7)
 
 
(pairFst p1) ;; Has type Number
(pairSnd p1) ;; Has type Boolean

(pairFst p2) ;; Has type String
(pairSnd p2) ;; Has type Number

(pairFst p3) ;; Has type (Listof Number)
(pairSnd p3) ;; Has type Number

Calling pairFst and pairSnd gives the first and second value sof each pair, respectively.

Most languages have a datatype for pairs, so that you do not need to define a struct every time you need to return multiple values from a function. The C++ standard library has a template std::pair<S,T>, which lets you make the type of pairs between any two types S and T. Python has pairs, and more generally, it has tuples, which are pairs generalized to more than two elements. Pairs in more modern languages, like Swift or Rust, tend to more closely resemble Flit’s pairs.

It is critical to remember that pairs and lists are NOT the same in Flit.

• Lists are an unbounded, homogeneous datatype.
  • Unbounded means that there is no limit to the length of elements of (Listof T). The lists '(), (list 99), (list 1 2 3), and (list 5 6 8 2 4 77 2000 1000000 all have the same type, even though they have lengths 0, 1, 3, and 8 respectively.
  • Homogeneous means that all the values in a list have the same type. We cannot write (list 3 #t "hello"), because the elements would have different types.
• Pairs are a fixed size, heterogeneous datatype
  • Fixed size means that every pair contains the same number of sub-values: two. A value of (Number * Boolean) contains exactly one number and exactly one boolean. A value of (String * String) contains exactly two strings.
  • Heterogeneous means that the two elements of a pair may have different types. So (pair 3 #t) is allowed, and will have type (Number * Boolean).

If you were making a system to record all of the books in a library, you would use pairs (or a more complex record type) to record the properties of each book. There will be a fixed number of data you are interested in, and they may have different types. For example, the publication year of a book is a Number, the tile and author will be String, there might be an isHardcover Boolean, etc. Then, to store the records for the entire library, you would make a list of records: you don’t know before-hand exactly how many books there will be in your library, and for each book, you are storing the same information.

We have named pairFst and pairSnd to help avoid confusion with first : ((Listof 'a) -> a): they are not interchangeable, and serve different purposes.

Note that we can make lists of any type that exist, and we can make pairs of any type that exist. So there can be lists of pairs, or pairs were one or both elements of the pair is a list.

We have already seen how to use pattern matching on lists. Pattern matching on a list is a concise way to give separate empty and cons branches, and to give names to the head and tail of the list in the cons case. In Flit, pattern matching extends to any datatype: we can use the same syntax as with list to check which constructor was used to create a datatype and give names to the fields.

The semantics for pattern matching on lists generalize to pattern matching on any datatypes in the way one would expect.

(type-case TYPE (Ctor arg1 ... argn)
  [(OtherCtor1 x1a ... x1z) otherResult1]
  ...
  [(Ctor y1 ... yn) resultExpr]
  ...
  [(OtherCtorM xMa ... xMz) otherResultM])

That is, if you have (Ctor arg1 arg2 ... argn), matching on that value will go to the branch with pattern (Ctor x1 x2 ... xn), and arg1 ... argn are used as the values for the variables x1 x2 ... xn.

Just as with functions, substitution is the key operation: we write a branch in terms of a datatype value where we don’t know the values of its field, or even what fields it has, since we don’t know what constructor it has. We write an expression that produces a result for any possible value we give, and then when we match on a particular value, the correct branch is selected, and its actual parts replace the placeholder variables that we used when writing the pattern match expression.

The typing rules for pattern matching and datatypes are as follows:

    (type-case TYPE EXPR
      [(Ctor1 x1_1 ... x1_num1) result1]
      ...
      [(CtorN xN_1 ... xN_numN) resultN])

For constructors, if the datatype is TYPE, the constructor is a function whose return type is TYPE, and the argument types are just the types of the fields for the constructor.

The typing rule for pattern matching looks like a combination of the rule for if and the rule for functions: the value we’re matching on must have a type that matches the type written in the pattern match. Then, each branch result has to have the same type, and the whole pattern match expression has the same type as the branch result. However, each branch result is typed under the assumption that the pattern variables have the types corresponding to the constructor’s fields.

For example, in area, each branch has a result type of Number, but the Circle branch is typed under the assumption that r : Number, whereas the Rectangle is typed under the assumption that l and w both have type Number, since those match the types of Circle and Rectangle’s fields respectively. Then, the whole pattern match expression has type Number, so it’s a valid expression to be the body of a Number-returning function.

Sometimes you have a large number of cases, and you want to return the same thing for many of them, without accessing any of the fields. In this case, you can use else as the last patter in a match, and it will match any patterns which weren’t previously specified. Similarly, if there are fields whose value you never use, you can write _ in place of a variable name to ignore the field (and ensure it is unused).

For example, let’s define a datatype for days of the week, where we either have a Number for the number of classes on weekdays, or a string describing someone’s plans for the weekend:

(define-type Day
  (Monday [classes : Number])
  (Tuesday [classes : Number])
  (Wednesday [classes : Number])
  (Thursday [classes : Number])
  (Friday [classes : Number])
  (Saturday [plans : String])
  (Sunday [plans : String]))

Then, say we want to make a Boolean-returning function which checks if the given day is a weekend or not. We could define this as:

(define (isWeekend? [d : Day])
  : Boolean
  (type-case Day d
    [(Saturday _)
      #t]
    [(Sunday _)
      #t]
    [else #f]))

This is is equivalent to the following, much more verbose definition:

(define (isWeekend? [d : Day])
  : Boolean
  (type-case Day d
    [(Saturday plans)
      #t]
    [(Sunday plans)
      #t]
    [(Monday classes)
       #f]
    [(Tuesday classes)
       #f]
    [(Wednesday classes)
       #f]
    [(Thursday classes)
       #f]
    [(Friday classes)
       #f]))

Datatype definitions are highly general and very powerful. Many of the types we have already seen are equivalent to datatype definition. Often they are built in to Flit, for performance or historical reasons, or they use special syntax, so the definitions below may not actually compile in Flit. But it is important to realize when types are conceptually instances of the general concept of datatypes.

In data structures courses, you may have come across binary search trees, AVL trees, Red-Black trees, 2-3 trees, B-trees, or other specific kinds of tree data structures. Likewise, if you’ve studied graph theory, you may know a tree as an acyclic undirected graph. In this course, when we say “trees”, we mean something much more general: any datatype which has a hierarchical structure, where some constructor’s field has the same shape as the type itself. We are able more specific kinds of trees as specific datatype definitions, as we will see in the following sections.

With lists we had a recipe for problem solving using recursion: pattern match on the list you’re looking at, give the answer for the base case, and in the cons case, make a recursive call on the tail of the list. The reason this works is because the tail of the list has the same type as the whole list, so it has the right type to do a recursive call on.

Trees generalize this recipe. To solve a problem that has a tree type as input, you pattern match on the input. For each leaf case (e.g. case with no recursive fields), you just figure out what the desired result is, given the information you have in the fields that are present. In a recursive case, you have some fields that have the same type as the whole tree itself, which means that

Let’s look at the most fundamental operation on numbers: addition. We’ll start with some TODOs:

(define (natPlus [l : Nat]
                 [r : Nat])
  : Nat
  (type-case Nat l
    [(zero)
       TODO]
    [(onePlus l-1)
       TODO]))

In the case where l = (zero), adding l to r should just produce r. So in that case, we can return r:

(define (natPlus [l : Nat]
                 [r : Nat])
  : Nat
  (type-case Nat l
    [(zero)
       r]
    [(onePlus l-1)
       TODO]))

In the onePlus case, we have l = (onePlus l-1). l-1 is smaller than l, so we can make a recursive call on it:

(define (natPlus [l : Nat]
                 [r : Nat])
  : Nat
  (type-case Nat l
    [(zero)
       r]
    [(onePlus l-1)
       (let ([l-1+r (natPlus l-1 r)])
         TODO)]))

Now we have l-1+r of type Nat in scope. So if we know (natPlus l-1 r), and l is one more than l-1, then (natPlus l r) should be one more than (natPlus l-1 r). This leads us to:

(define (natPlus [l : Nat]
                 [r : Nat])
  : Nat
  (type-case Nat l
    [(zero)
       r]
    [(onePlus l-1)
       (let ([l-1+r (natPlus l-1 r)])
         (onePlus l-1+r))]))
;; Tests now that the definition is complete
(define one (onePlus (zero)))
(define two (onePlus one))
(define three (onePlus two))

(natPlus three two)
(natPlus two (zero))
(natPlus (zero) two)

Running this gives us a somewhat indirect representation of 5 and 2, nevertheless is the correct result:

(onePlus (onePlus (onePlus (onePlus (onePlus (zero))))))
(onePlus (onePlus (zero)))
(onePlus (onePlus (zero)))

Once we have addition defined, we can define multiplication for Peano numbers using recursion:

(define (natTimes [l : Nat]
                  [r : Nat])
  : Nat
  (type-case Nat l
    [(zero)
       (zero)]
    [(onePlus l-1)
       (natPlus r (natTimes l-1 r))]))
;; tests
(natTimes two three)
(natTimes (zero) two)
(natTimes two (zero))
(natTimes one three)
(natTimes three one)

Let’s talk about the cases. If l is zero, then multiplying r by l should give zero. So the base case produces zero. If l = (onePlus l-1) for some l-1, then we can make a recursive call on ~l-1, which gives us l-1 times r. So if we know what l-1 times r is, and l is one more than l-1, then l times r can be computed by adding one more r to l-1 times r.

Running this on our tests gives the usual result from multiplication, if we count the ~onePlus~es.

In a data structures class, you probably saw binary search trees, with a complicated definition involving pointers and references. Datatypes let us define binary search trees in a more straightforward way:

(define-type (BST 'elem)
  (leaf)
  (node [left : (BST 'elem)]
        [right : (BST 'elem)]
        [key : Number]
        [data : 'elem]))

That is, a binary search tree (BST) is either an empty tree, with no data, or it is a node, which contains a key, some data associated with that key, as well as (possibly empty) left and right trees. The type is recursive, because the left and right trees are themselves binary search trees.

The key invariant for a binary search tree is that, for each node, any nodes in the left have keys that are less than or equal to their parent, and any nodes in the right have keys that are strictly greater than their parent’s key. Types alone are not enough to enforce this invariant of binary search trees, but we can write a function that checks whether a binary search tree is well formed:

(define (BST-inrange [t : (BST 'elem)]
                     [strict-lower-bound : Number]
                     [upper-bound : Number]) : Boolean
  (type-case (BST 'elem) t
    ;; A tree with no data is always in range
    [(leaf) #t]
    ;; non-empty: check if index in range
    ;; and that left/right are all smaller/bigger
    [(node left right index data)
     (and
      (> index strict-lower-bound)
      (<= index upper-bound)
      ;; Left tree should be in range, and <= this node
      (BST-inrange left strict-lower-bound index)
      ;; Right tree should be in range, and > this node
      (BST-inrange right index upper-bound))]))

This function looks at a given range, and checks whether the root of the tree’s key is in the given range, and that each child is also well-formed. To check an entire tree, we can do a range check with a starting range of all numbers:

(define (BST-wellformed [t : (BST 'elem)]) : Boolean
  ;; We check if all nodes are in the correct range,
  ;; with a starting range
  ;; of -infinity to +infinity i.e. all numbers
  (BST-inrange t -inf.0 +inf.0))

Like with association lists, the key operations for BSTs are adding a new key and value, and looking up the value for a given key. Both of these are defined using recursion: since the left and right children of a tree are themselves trees, they are candidates for making recursive calls, though the speed of binary search trees comes from the fact that we only ever do a recursive call on the left or right child, not both.

Another hierarchical structure that you have likely already encountered is a filesystem. A filesystem has folders, which can contain either files or other folders. Those folders themselves can contain files, or other folders, which can contain files etc. We can model a filesystem as a datatype:

(define-type Filesystem
  (File [name : String]
        [data : Number])
  (Folder [name : String]
          [contents : (Listof Filesystem)]))

That is, a Filesystem is either a file, which has a name and some data, or a folder, which has a name and some contents, each of which is either a file or a folder, i.e., another Filesystem. Unlike a BST, there is no particular structure to which subtree things are stored, so to find something in a Filesystem we will need to look at the entire structure.

Operations on Filesystems can be implemented using pattern matching and recursion. As with other recursive types, the recursive calls we make will match the recursive occurences in the datatype. However, there is a whole list of Filesystems in a Folder, so how many recursive calls should we make?

What we will do instead is define a function by mutual recursion: one function that works on filesystems, and one that works on lists of filesystems. These functions will both call each other:

(define (search [target : String]
                [fs : Filesystem]) : (Optionof Number)
  (type-case Filesystem fs
             [(File name data)
              (if (string=? name target)
                  (some data)
                  (none))]
             [(Folder _ contents)
               (searchList target contents)]))
             
             
(define (searchList [target : String]
                    [files : (Listof Filesystem)])
        : (Optionof Number)
  (type-case (Listof Filesystem) files
             [empty (none)]
             [(cons h t)
              (let ([result (search target h)])
                (if (none? result)
                    (searchList target t)
                    result))
              ]))

The search function implements a traversal of a filesystem that returns the data of the first file, if any, whose name matches the given string. There are two cases: a file, which is a leaf, or a folder, which contains a list of files.

If the filesystem we’re looking at is a single file, then the only thing to do is check if that file’s name matches the one we’re looking for. If it does, we return its data wrapped in some. If it doesn’t, we return none. If the filesystem is a folder, we use searchList to look in each member of a file.

The searchList function also uses pattern matching, but matching on a list, rather than a filesystem, looking for an occurence of a file with a given name in any of the filesystems in the list. In the case that the list is (empty), then there are no filesystems to contain the given file, so we return none to signal that we did not find it. In the (cons) case, we have one filesystem as a head and a list of filesystems as a tail. We can make two recursive calls: recursively calling search on the head and searchList on the tail. If searching in the head returns none, then we need to recursively search in the tail. Otherwise, we can just return the result of searching in the head, since it found a file with the given name.

Recall that when we wrote the types of functions, we would write something like (T1 T2 ... Tn -> S). This is the type of functions that take in n arguments, with types T1 to Tn respectively, and return a value of type S.

In Flit and other functional languages, function types are not special, and can be used anywhere that another type is used. So one can write ((Nat -> Nat) -> Boolean), which is a function that takes in another function. The argument function takes in a natural number and returns a natural number, and the entire function produces a boolean. Likewise, one can write (Listof (String -> Number)), which is a list of functions, each of which takes a string argument and produces a number. Or one can write (Optionof (Boolean -> Boolean)), which is either none or (some f) for some f that takes a boolean and returns a boolean.

Depending on how many types you want to write down, there are several variants of the Lambda syntax:

#+begin_src racket
;; Type annotation
(lambda ([x : Number]) : Number
  (+ x 1))
 
;; Multiple arguments
(lambda (x y) (+ x (+ x y)))

;;Multiple type annotations
(lambda ([x : Number]
   [y : Number]) (+ x (+ x y)))
 
;; Unicode Greek lambda
;; In Dr. Racket: either cmd-\ or ctrl-\ depending on os
(λ (x) (+ x x))

In the theory of programming languages, calling a function, especially a lambda, is sometimes referred to as “applying” that function. Applying a function and calling the function mean the exact same thing, and we may use both terms through the course.

The semantics and typing rules for lambda are exactly like those for function definitions,

There are no equations for lambda before we call it: a lambda just makes a function that is waiting to be called, but actually creating the function doesn’t do anything.

In practice, we never write code that looks like ((lambda (x) (+ x 1) 3), e.g. where we write a lambda then immediately give it an argument. But when we call a higher order function, the variable for its function argument might get replaced with a lambda, so after some steps of evaluation we will end up with a lambda directly called on an argument.

When you define a function, Racket actually converts it into a lambda, so writing:

(define (f x) (+ x 1))

produces the exact same thing as writing:

(define f (lambda (x) (+ x 1)))

Like with the equations, there is a typing rule for lambda that looks very similar to the one for function definitions:

This means that, if we have a hole of type (S -> T), we can replace it with (lambda (x) TODO). The new hole will have type T, but in that hole, there will be a variable x in scope, that you can refer to when making your solution. The main difference is that, since a lambda does not need to occur at the top level in your file, the body EXPR can refer to any variables that are in-scope

The typing rules for calling lambda is the exact same as for calling a function definition: to write (f x), we need f : (S -> T) and x : S, and then (f x ) : T. Whether the function being called is made with define or with lambda does not affect the typing rules at all.

As we’ve mentioned, lambda does not need to be used at the top level. This means that we are allowed to write function using lambda that depend on other variables. For example, here’s how to write a function that adds n to each element of a list:

(define (addNToEach [numToAdd : Number]
                    [xs : (Listof Number)]) : (Listof Number)
  (mapNum (lambda(x) (+ x numToAdd)) xs))
(addNToEach 3 '(1 2 3 4))

'(4 5 6 7)

This function takes in a number to add and a list of numbers. In its body, it uses lambda to dynamically create a function, which takes in an argument x and adds whatever number we gave to x. This function is then passed to mapNum, which calls it on each element of the list xs.

There is a special kind of function which takes functions as both input and output, called a combinator:

So a combinator is a way to transform a function into a related function. For example, we can make a function which “adds” two functions together, for any f and g, it will produce the function that returns the sum of (f x) and (g x) for each x:

(define (+fun [f : (Number -> Number)]
              [g : (Number -> Number)]) : (Number -> Number)
  (lambda (x) (+ (f x) (g x))))
;; e.g. Make the function that adds (f x) and (g x) for any x
;; Tests:
(define x^2+3x (+fun (lambda (x) (* x x)) (lambda (x) (* 3 x))))
(x^2+3x 1)
(x^2+3x 2)
(x^2+3x 0)

4
10
0

The function takes two arguments: f and g, which each have type (Number -> Number). Then we want our result to have type (Number -> Number), so we make a lambda. This gives us a variable x with type Number, and a goal type of Number for the body of the lambda. The expressions (f x) and (g x) each have type Number, so we can add them together to get our final number for the lambda’s body.

Just calling +fun doesn’t do anything, except make a new function that we can call on other arguments. But when we run the tests above, we can see that it does indeed produce the sum of \(x^2\) and \(3x\) for each \(x\) we give it:

4
10
0

There are no special rules for higher order functions or combinators. We can reason about programs with them using all the rules we have already. For example, let’s look at using +fun on a function that negates its argument:

(define (negate x) (* x -1))

(+fun negate negate)
= (lambda (x) (+ (negate x) (negate x)))
= (lambda (x) (+ (* x -1) (* x -1)))

So:
((+fun negate negate) 3)
= ((lambda (x) (+ (* x -1) (* x -1))) 3)
= (+ (* 3 -1) (* 3 -1))
= (+ -3 -3)
= -6

Combinators are particularly useful for “lifting” functions on element types to work on data structures. For example, we can lift any operation on numbers to work on (Optionof Number).

(define (liftOption [f : (Number -> Number)])
  : ((Optionof Number) -> (Optionof Number))
  (lambda ([optionN : (Optionof Number)])
    (type-case (Optionof Number) optionN
      [(none) (none)]
      [(some x) (some (f x))]
      )))

Given a function that works on numbers, liftOption returns a lambda. This lambda looks at its argument, which is an (Optionof Number), and checks if it is none. If it is, then it returns none, since there’s no way to apply an operation to a number that isn’t there. If the number (some x), then the function returns (some (f x)).

Remember back to when you were learning your first non-functional language. For example, when first learning arrays in C++, students learn to write code that looks like this:

int myArray[N];

for (int i = 0; i < N; i++){
  int current = myArray[i];
  // Do something with current
 }

Every single time you want to do something with each element of an array in left-to-right order, this is the code you want to call.

In with higher-order polymorphic functions, you don’t have to repeatedly write this pattern, because the pattern can be captured as an actual function. Somebody else wrote map, put it in a library, and now you never need to write that boilerplate code again.

We can use filter to implement the generic sorting algorithm that we were wishing for at the start of this section. In a functional language, quicksort is one of the easiest and fastest sorting algorithms to implement. The idea is as follows:

• If your list is empty, then there’s nothing to sort

• If your list has at least one element, we can divide the rest of the list into things smaller than that element, and things bigger than that element. Each of those lists has stricly fewer elements than the own list, so we can sort them recursively. Then, we can just put them together into a bigger list, since we know both recursive results are sorted, and each only contained things smaller (or larger) than the head of the list, respectively. As code, this looks like:

   
   (define (sortBy [compare : ('a 'a -> Boolean)]
                  [xs : (Listof 'a)]) : (Listof 'a)
    (type-case (Listof 'a) xs
               [empty
                 empty]
               [(cons head tail)
                 (let
                   ([smallers
                      (filter (lambda (x) (compare x head))
                              tail)]
                    [biggers
                      (filter (lambda (x) (not (compare x head)))
                              tail)])
                   (append (sortBy compare smallers)
                           (cons head
                                 (sortBy compare biggers))))]))
  

  We make a lambda that checks whether its argument is less than the head of the list, and another that checks the opposite. This is another example of a dynamic lambda: we don’t know what thing to compare x to until we’re actually inside the function and have a value for head. Calling filter with those lambdas gives two lists: one whose elements are all smaller, and one whose elements are all larger. We can recursively sort those. Then all that remains is to append the sorted lists together in the right order, with the head in the middle.

  Another pair of useful functions we can define with filter are all? and any?. These each take a predicate and a list. Then all? returns true if the predicate holds (returns true) for every element of the list, and any? returns true if it holds for at least one element of the list. They can be implemented as:

  (define (all? [pred : ('a -> Boolean)]
                [elems : (Listof 'a)]) : Boolean
    (empty? (filter (lambda (x) (not (pred x))) elems)))
   
   
  (define (any? [pred : ('a -> Boolean)]
                [elems : (Listof 'a)]) : Boolean
    (not (empty? (filter pred elems))))
  

  That is, all? filters out all of the elements that satisfy the predicate, then checks if there are any left that don’t satisfy it. Likewise, any? filters the list down to all of the ones that do satisfy the predicate, and then make sure that the resulting list is not empty.

In many cases, with polymorphic higher-order functions, there is only one way to write the correct function: the types guide us to a solution, because with generic types, we can only use the arguments we have in front of us. For example, let’s look at the identity function, which just returns whatever input it is given:

(define (id [x : 'a])
  : 'a
  TODO)

We have x : 'a in scope, and a goal type of 'a. What could we possible do to produce a value of type 'a when we have no idea what type will stand in for the type variable 'a ? We could crash, but that seems useless. The only possible value we can return is x. So we define:

(define (id [x : 'a])
  : 'a
  x)

For functions that take multiple arguments, we can write a function that gives a value for one of those arguments, and returns a new function waiting for the second argument:

  (define (curry [f : ('a 'b -> 'c)]
                 [x : 'a])
          : ('b -> 'c)
    (lambda (y) (f x y)))

This is known as currying, and is named after the American logician Haskell Curry, who was instrumental in developing the theory of functions, types, and the lambda calculus⁶. The curry function takes in a two-argument function and a first-argument for it. Since we want to produce a new function, we can make a lambda for our result. This lambda is waiting for its argument y, but when it gets it, it calls f with the x that curry was passed, as well as whatever y the lambda was given.

What if we want to give the second argument, but not the first? Well there’s a combinator for that too:

  (define (flip [f : ('a 'b -> 'c)])
    : ('b 'a -> 'c)
    (lambda (bVal aVal) (f aVal bVal)))

The flip function takes a function and makes a new function that does the exact same thing, but takes its arguments in reverse order.

For example, say we have a list of numbers, and we want to get the remainder when dividing each number by 3. We want to map modulo over the list, but the number we’re dividing by is the second argument to modulo. So we can do:

;; Gets (modulo x 2) for each x in the list
(map (curry (flip modulo) 3)
     '(1 2 3 4 5 6 7 8))

Which gives us:

'(1 2 0 1 2 0 1 2)

This style of programming, where you build up functions using composition and other combinators, us called point-free programming. In general, anything you can do with point-free programming, you can do with lambda, so which to use us generally a matter of which is more readable in the specific case, and personal preference.

There are several useful combinators for handling Optionals. These allow us to write code for possibly-failing operations that look a lot like the code for non-failing operations.

The core operation is liftOption, which lets you take an operation on T and turn it into one on Optionof T for any type T:

  (define (liftOption [f : ('a -> 'b)])
                      : ((Optionof 'a) -> (Optionof 'b))
        (lambda (maybeX)
          (type-case (Optionof 'a) maybeX
            [(none)
               (none)]
            [(some x)
               (some (f x))])))
  ;; Tests
  ((liftOption add1) (some 3))
  ((liftOption add1) (none))

  (some 4)
  (none)

That is, liftOption takes a function of type ('a -> 'b) and transforms it into a function of type (Optionof 'a -> Optionof 'b).