This document includes notes on the Racket language and other topics covered by the first part of CS 251.

Contents

First Lens: Defining Racket

The Racket language is our first lens for examining programming language design in CS 251.

This document introduces the same kernel of the Racket language as covered in lecture. For additional reference, see the Racket Guide.

Racket, the child of Scheme and grandchild of LISP, falls into a broad category of programming languages often called functional programming languages. Functional refers to a focus on functions in the mathematical sense. Unfortunately, the term can be a bit confusing, since many other languages (such C, Python, and others) use constructs called functions, even though they do not always follow a “functional” style. Functional languages are built around the evaluation of expressions and the application of functions for their results, rather than the execution of sequences of commands for their effects on mutable stored data. In some sense, functional languages are a little closer to expressing what to compute, while imperative (command-, statement-, and assignment-focused) languages are closer to expressing how to compute it. Functional languages are closer to math; imperative languages are closer to the model presented by most modern computer hardware systems.

Goals

Our top-level goals in studying Racket are several, including:

  • Exposure to functional programming, which emphasizes the evaluation of expressions and functions on immutable data rather than the execution of commands for their effect on mutable storage. This experience (probably new to many of you) not only introduces you to a powerful, expressive, and elegant approach to programming, but it also helps you learn to think about problems in new ways.
  • Define and understand the syntax and dynamic semantics of a small programming language kernel:
    • Expressions, values, variables, bindings, environments
    • Basic compound values
    • First-class functions, higher-order functions, function closures
    • Lexical scope
  • Develop and apply foundations and meta-languages for defining:
    • Syntax via grammars
    • Semantics via judgments, inference rules, derivations, and the environment model

Learning Racket

You may be surprised that “learn the Racket language” is not listed as an explicit goal. Certainly you will learn Racket and other languages (a nice side effect of the course), but we are big picture goals are skills that are more transferable than intimate knowledge of a single programming language. Hence our references to using the language as a “lens” for studying big PL ideas. We will focus heavily on the core of the language, often starting with simplified, more restrictive definitions. Before long we will move on to use a new lens, but there is much more Racket to explore beyond our coverage.

Tools

We will use the DrRacket environment for Racket programming. Racket is part of a family of closely related languages supported by DrRacket. To indicate which language we are using, each Racket file must start with the line:

#lang racket

While we will do all of our Racket programming in the DrRacket environment, it is important to remember that the Racket Language is distinct from the tools we use to write or run Racket programs. (The same holds for any well-defined programming language and the related tools and implementations.)

Defining Racket: Expressions and Values

A Racket program consists of definitions and expressions, evaluated in order.

To define each new language feature, we:

  1. Define its syntax: What is its form? How is it written?
  2. Define its evaluation rules (dynamic semantics): What is its meaning? How is it evaluated?

Expressions

An expression e may or may not have a value v. An expression is evaluated to a value according to a set of evaluation rules. Each kind of expression has its own evaluation rules.

Values

The simplest kind of expression is a value. Consider numbers. The number 251 is written in Racket as the series of digits 251. The evaluation rule for values is that a value evaluates to itself. For example, the expression 251 evaluates to the number value 251, because it already is that value. All values are expressions, but not all expressions are values. In other words, values are expressions that cannot be evaluated any further.

Trivial as number values may seem, the way we defined them is important. We specified two things about number values:

  1. syntax: how to write a number value
  2. semantics: how to evaluate a number value (i.e., evaluation rules)

As we build up the core of the Racket language we will continue in this manner, rapidly adding more constructs to the language by describing their syntax and semantics (evaluation rules).

Other Values

Besides number values, Racket has several other types of values, including boolean values, with syntax #t (true) and #f (false). We will consider other kinds of values later. The syntax for different types of values differs, but their evaluation rules remain the same: a value evaluates to itself.

Arithmetic Expressions

As an example of a (slightly) more interesting expression, let us consider addition. The syntax of a Racket addition expression is:

(+ e1 e2)

Here, e1 and e2 are expressions. For example, we could write (+ 251 251) and we could also write (+ (+ 240 251) (+ 235 301)) or even (+ #t 251). The parentheses are mandatory. Racket uses prefix notation, where operators in expressions like addition are written before their operands rather than between. The latter approach, familiar from many other programming languages, is called infix notation.

The evaluation rule for an addition expression is:

  1. Evaluate expression e1 to value v1 and then evaluate expression e2 to value v2; then
  2. If both v1 and v2 are numbers, then the result is a number value that is the arithmetic sum of v1 and v2, otherwise a type error occurs.

There are two interesting considerations arising from the syntax and evaluation rules for Racket addition:

  1. Dynamic Type-Checking: Every value has a type. For example, 251 is a number value, while #t is a boolean value. The evaluation rule for Racket + makes it clear that Racket does dynamic type-checking, meaning it checks specific types of values when evaluation reaches an operation that actually requires a particular type of value. For example, Racket + requires that its operands be numbers. This is in contrast to compile-time static type-checking that you know from the Java language or others. We will return to discuss dynamic vs. static type-checking later.

  2. Recursive Structure and Evaluation: Expressions that are not values contain other expressions, meaning the structure of an expression is recursive in nature. This is visible in the syntax. Since the structure of an expression may be arbitrarily deep, its evaluation must proceed recursively. To evaluate an addition expression (which is clearly not a value), we must first evaluate its subexpressions. The requirement for the subexpressions to evaluated first is called eager evaluation or call-by-value. Later in the course, we will discuss the implications of this choice and explore alternative orders of evaluation, but the recursive structure will remain.

The Language of Languages

We have introduced a few values and one more interesting expression form so far. We used careful English definitions of the syntax and semantics of each language feature and we will continue to do so. However, English can be devilishly ambiguous. In our study of programming languages, we will often need to be precise about subtle differences in definitions that could have not-so-subtle effects on language behavior. To meet this need, we will use formal notations or meta-languages to give more precise definitions.

Syntax Definitions with Grammars

To define the syntax of a language, we will use grammars. Formally, grammars are powerful tools with many variations. (CS 235 includes extended study of context-free grammars and the languages they can describe.) We use a notation similar to Backus-Naur Form (BNF). (For now, rather than quoting all terminals and angle bracketing all non-terminals, we use different font faces to distinguish grammar elements.)

Grammar Notation

A grammar defines the different abstract structures of a language, called non-terminal symbols, each of which may take one or more distinct shapes, called productions. Each production of a non-terminal symbol is defined in terms of a string of non-terminal and terminal symbols (concrete characters of the language syntax). Here is a grammar describing Racket expressions as we know them so far:

We can read the notation above as follows: “An expression, $\nt{e}$, is one of:

  • a value, $\nt{v}$; or
  • an addition expression, $\texttt{( + } \nt{e}\ \nt{e} \texttt{ )}$, of any two expressions.”

The grammar definition has several parts:

  • The blue italic “$\nt{e}$” and “$\nt{v}$” are non-terminal symbols (non-terminals for short), representing classes of larger syntactic structures. (Note, we have not introduced the definition of $\nt{v}$ yet.)
  • The black monospace characters are terminal symbols (terminals for short), representing concrete characters of the language syntax.
  • The red notations “$\Defn$” and “$\Pipe$” are meta-syntax, showing the structure of the grammar itself. “$\Defn$” indicates the definition of the non-terminal to its left, by the productions to its right. A non-terminal may have 1 or more productions, separated by “$\Pipe$” in the grammar.

Racket Syntax So Far

Here is the grammar for all Racket syntax we have defined thus far, including expressions ($\nt{e}$), literal values ($\nt{v}$), and numbers ($\nt{n}$):

While we demonstrate how a (very large!) grammar could define the non-terminal $\nt{n}$ to stand for any number notation, we will generally take shortcuts to define parts of the syntax like number values outside the grammar.

Grammar Derivations

Note that one of the productions of $\nt{e}$ is recursive: it is defined in terms of $\nt{e}$. Recursion naturally captures the tree structures common to programming language syntax. For example we can expand the non-terminal $\nt{e}$ to show how the Racket expression (+ (+ 1 2) #f) is structured. Here, we will use subscripts to help keep track of separate occurrences of the same non-terminal.

  • $\nt{e} \to \t{( + } \nt{e_1} \ \ \nt{e_2} \t{ )}$
    • $\nt{e_1} \to \t{( + } \nt{e_3} \ \ \nt{e_4} \t{ )}$
      • $\nt{e_3} \to \nt{v_3}$
        • $\nt{v_3} \to \nt{n_3}$
          • $\nt{n_3} \to \t{1}$
      • $\nt{e_4} \to \nt{v_4}$
        • $\nt{v_4} \to \nt{n_4}$
          • $\nt{n_4} \to \t{2}$
    • $\nt{e_2} \to \nt{v_2}$
      • $\nt{v_2} \to \t{#f}$

Or we can redraw this as a tree (more with that later).

Notation Conventions

As we proceed to define formal semantics, we will refer to elements of this grammar. When we do so:

  • Use of a non-terminal symbol, such as $e$, in syntax examples and evaluation rules means any expression matching one of the productions of e in the grammar.
  • Two uses of $e$ in the same context are aliases; they mean the same expression. (Note that this differs from how we treat $e$ in the grammar itself.)
  • Subscripts (or suffixes) distinguish separate instances of a single non-terminal, e.g., $e_1, e_2, …, e_n$ or e1, e2, ..., en.

Formal Semantics Definitions

When defining the semantics of language forms, we will three connected formal tools to define an operational semantics:

  • Judgments are formal assertions. They frequently act like “functions” in the “programming language” of semantics definitions.
  • Inference rules define implications between judgments, like cases of functions calling other functions.
  • Derivations are deductions based on chaining inference rules, like applying functions.

Judgments and Inference Rules Formalize Semantics

The judgment $\EvalExprNoEnv{e}{v}$ means “expression $e$ evaluates to value $v$.” To define the various evaluation rules for different kinds of expressions, we will employ inference rules. The $\downarrow$ here is meta-syntax we have invented – not part of Racket.

An inference rule has any number of premises, drawn above a horizontal bar, and a single conclusion, drawn below the horizontal bar.

Also written:

The rule means: “if all the premises hold then the conclusion holds.”

A rule with no premises is an axiom. The horizontal bar is optional in this case. As an example, consider the evaluation rule for values: a value evaluates to itself.

Now review the evaluation rule for addition. It can be written as an inference rule like this:

where the premise $\EqSum{n}{n_1}{n_2}$ uses red symbols to indicate that $n$ is the arithmetic sum (not Racket plus) of the two numbers $n_1$ and $n_2$.

Notice that this rule makes dynamic type-checking implicit. This rule can apply only if the two subexpressions evaluate to numbers. If they evaluate to, say, Booleans, this rule does not fit this result and cannot be applied.

Evaluation Derivations

So far, the Racket expressions we have seen are enough to use as a simple calculator. Evaluating expressions by hand (trivial as they may seem so far) is good practice to become familiar with the evaluation rules or to help debug programs.

Using the evaluation judgment e ↓ v, which asserts that expression e evaluates to value v, we can give evaluation derivations to show how an expression evaluates to a value by chaining together rules.

For example, it should be obvious that (+ 3 (+ 5 4)) ↓ 12. Written in conclusion-at-the-top bulleted form, we can justify this with a derivation in which we apply all of the evaluation rules necessary to prove the assertion.

  • (+ 3 (+ 5 4)) ↓ 12, by the addition evaluation rule, because:
    • 3 ↓ 3, by the value evaluation rule
    • and (+ 5 4) ↓ 9, by the addition evaluation rule, because:
      • 5 ↓ 5, by the value evaluation rule
      • and 4 ↓ 4, by the value evaluation rule
      • and 5 and 4 are both number values
      • and adding 5 and 4 results in 9
    • and 3 and 9 are both number values
    • and adding 3 and 9 results in 12

Using the more formal notation, we can chain the inference rules explicitly:

(In lecture, we also show a vertically stacked format that is easier to draw when tight on horizontal space, especially for large derivations or for drawing by hand.)

The recursive structure of expressions and the recursive nature of their evaluation becomes apparent in this derivation. Each inference rule provides some concrete conclusion; its premises are satisfied by the conclusions of further rule instantiations until eventually reaching axioms (with no premises).

There are two ways to view an evaluation derivation:

  1. It corresponds to a sequence of recursive calls an evaluator program (a.k.a. interpreter) could make to evaluate this expression on a computer.
  2. It corresponds to a proof that this expression evaluates to this value.

Errors Are Modeled by “Stuck” Derivations

As noted earlier, the formal $\RuleRef{add}$ rule for addition did not do explicit dynamic type-checking. Instead, its premises were constrained such that they could only be satisfied by a well-typed result. This is the pattern we use in general when specifying semantics. It models run-time errors like dynamic type errors by derivations that get “stuck”. Consider the expression (+ #t (+ 5 4)). It will result in a dynamic type error when evaluated, because #t is not a number value. In an evaluation derivation, we know that this expression must be handled by the $\RuleRef{add}$ rule, due to the matching shape of its conclusion.

However, this rule indicates that we need a (sub-) evaluation derivation showing that the first subexpression, $e_1$ or #t in this case, evaluates to a number. In this case we need to show that $\EvalExprNoEnv{\t{#t}}{n_1}$. Any number value $n_1$ will do! Yet no such derivation exists: no rule ever produces an assertion of this shape as its conclusion. We are stuck in trying to use the rules of our semantics to show a derivation of this expression – for good reason, evaluating #t to a number makes to sense in Racket. This “stuckness” models run-time errors. If we have defined the semantics accurately, then derivations are stuck exactly for those expressions that would raise errors upon evaluation.

Back to Expressions…

Other Arithmetic

Racket has nearly identical syntax and evaluation rules for other arithmetic operations, including - (difference), * (product), / (division, with fraction results), quotient (truncated integer division as familiar from other programming languages). For non-commutative arithmetic operations, the left-to-right order of operands is the same in prefix notation as in postfix notation. For example, (- 251 240) in Racket is equivalent to (251 - 240) in arithmetic. While +, -, and * always succeed, / and quotient cause errors if attempting to divide by 0.

Number Comparison Expressions

So far, we have boolean values, but no non-value expressions that result in boolean values. The less than comparison expression results in a boolean value. Its syntax is:

(< e1 e2)

Here, e1 and e2 are expressions. The evaluation rule for less than is:

  1. Evaluate e1 to a value v1 then evaluate e2 to a value e2.
  2. If v1 and v2 are both number values, then:
    • the result is the boolean value #t if the number v1 is less than the number v2;
    • otherwise the result is the boolean value #f

    Otherwise (if one or both values are not numbers), a type error occurs.

Other number comparison expressions with analogous syntax and evaluation rules are: >, <=, >=, and =.

Exercise

Define the English evaluation rule for quotient. Define formal evaluation rules for quotient and <. Pay special attention to the circumstances under which these expressions can and cannot be evaluated.

Conditional if Expressions

Recall that, as a functional language, Racket is focused on the evaluation of expressions. There are no statements or commands, so the if statement that is familiar from languages like Java or C does not make sense. Instead Racket has an if expression. Its syntax is:

(if e1 e2 e3)

Here, e1, e2, and e3 are all expressions.

The evaluation rule is:

  1. Evaluate e1 to value v1.
  2. If v1 is any value except #f, the result of evaluating the entire if expression is the result of evaluating e2. Otherwise, the result of evaluating the entire if expression is the result of evaluating e3.

This informal evaluation rule can be expressed by a pair of formal evaluation rules:

Notice that only one of these two rules can possibly apply: either $e_1$ evaluates to a non-false value or it evaluates to a false value; it cannot evaluate to both. This is a common pattern in using inference rules: sometimes a single form may have multiple possible evaluation outcomes, often represented by corresponding rules.

if is an expression

As an expression the if expression can appear anywhere any expression can appear. For example, we might write:

(if (< 9 (- 251 240))
    (+ 4 (* 3 2))
    (+ 4 (* 3 3)))

Or equivalently, with fewer symbols:

(+ 4 (* 3 (if (< 9 (- 251 240) 2 3))))

Note that, unlike the Racket addition expression, the Racket if expression does not evaluate all of its subexpressions! So far, it might seem that this is not an important distinction, since all we are doing is arithmetic, but consider the following two expressions:

(if #t 251 (/ 251 0))

(if #f (+ #t 251) 251)

Both expressions contain subexpressions that, if evaluated, cause errors: division by zero in the first case and attempting to add a non-number value in the second. In both cases, our intuition for what the value of this expression should be (hopefully) matches the evaluation rule. Even though one subexpression of the if contains an expression whose value is undefined, would cause an error when evaluated, it does not matter, because the condition expression selects the other branch of the if. As we generalize some ideas later, we will see that this makes if “special” as compared to +, for example.

Environments, Variables, and Bindings

The Racket expressions we have explored thus far do not include variables. Now we introduce variable definitions (or bindings) and variable references into the language. To do this, we need more syntax, some new evaluation rules, and a new component of our dynamic semantics: the environment.

Dynamic Environments

Dynamic environments are sequences of bindings of variables to values that allow us to determine the value of a variable when it is referenced. The syntax of environments, as we write them in our formal semantics, is:

where $\nt{x}$ is any variable identifier and $\nt{v}$ is any value.

The empty dynamic environment, with no bindings, is written “$\cdot$”. Larger environments are written as a sequence of bindings. For example, in the following environment, num is bound to 17, absZero is bound to -273, and true is bound to #t:

For convenience in notation, the “$\cdot$” may be written as “.” or, when the environment is non-empty, omitted entirely.

We use the syntax $E(x)$ to indicate looking up the value $v$ that is bound to the variable $x$ in environment $E$. Lookup proceeds by searching from left to right, returning the value of the first binding of the variable in question. For example, let $E$ refer to the environment shown above. Then $E(\t{absZero}) = \t{-273}$.

Note that this is meta-syntax it is syntax of the formal system that we have created to help define the meaning of Racket programs. It is not Racket syntax.

Variable Reference Expressions

Variable references are expressions. Their syntax is x, where x is a valid identifier. (See the Racket Guide for the long list of characters allowed as part of identifiers.

The evaluation rule for a variable is:

  • Look up x in the current dynamic environment, $E$, and return the value, $v$, to which x is bound. If there is no binding for x, a name error occurs.

Environments in Formal Semantics

Program evaluation maintains a current environment that is passed through expression evaluation to provide the context that is necessary to evaluate a variable reference. In our informal English evaluation rule above, this “current dynamic environment” is implicitly available. To model this in our formal semantics, we must revise our original evaluation judgment, $\EvalExprNoEnv{e}{v}$ to explicitly model the environment. The new judgment is:

which means “under dynamic environment $E$, expression $e$ evaluates to value $v$.” We can now define a rule for variable reference:

Now, we need to update all of our existing formal semantics rules to use the new evaluation judgment that supports environments. Why? Without it, we have no way of evaluating a variable reference, like x, when it is nested within another expression, such as (if (< 3 x) x 7). Every expression evaluation rule must explicitly pass the environment through to the evaluation of any subexpressions. For example, the evaluation rule for the addition expression (+ e1 e2) would change to:

  1. Under the current dynamic environment, $E$, evaluate e1 to a value v1.
  2. Under the current dynamic environment, $E$, evaluate e2 to a value v2.
  3. etc.

The updated formal evaluation rules make this all explicit:

Bindings

A definition is a kind of binding. Definitions and bindings in general appear in a few different shapes. Most notably, bindings are not expressions. For now, we will consider definitions with the following syntax:

(define x e)

Here, define is a keyword, x can be any identifier (a.k.a. variable), and e can be any expression.

The evaluation rule for a binding is:

  1. Under the current environment, $E$, evaluate e to a value v.
  2. Produce a new environment, $E’$, by extending the current environment, $E$, with the binding x ⟼ v.

Prime

If you have not seen the $E’$ notation before, the apostrophe-like mark is pronounced “prime”. It indicates another separate entity, usually one that is somehow related to $E$. In this case $E’$ is $E$ plus one more binding.

Notice that, while evaluating a binding involves the evaluation of an expression, the binding itself is not an expression and its evaluation does not result in a value. Rather, it results in a new environment, under which following parts of the program will be evaluated. To formalize evaluation of bindings, we thus need a separate judgment, since $\EvalExpr{E}{e}{v}$ cannot express the proper meaning of bindings.

The new judgment is: $\EvalBinding{E}{b}{E’}$, where $E$ is the initial environment, $b$ is the binding, and $E’$ is the environment that results from evaluating binding $b$ under environment $E$. There is (for now) a single rule that implements this judgment:

The English evaluation rule above corresponds exactly to this formal rule.

Binding is not Assigment

Remember to resist the temptation to associate words like variable with meanings from other programming languages you know. Here, we will treat a variable as in math – a name for an unknown value. Once we attach the name to a particular value, we never change it.1 (If you must use an analogy, choose the notion of a constant from other languages.)

Example with Environments, Bindings, and Variables

This example shows how new environments are created and used as we evaluate a simple Racket program: a sequence of bindings and expressions. When notating environments in plain text we replace “$\mapsto$” with “-->”.

  ; E0 = .
(define x (+ 1 2))
  ; E1 = x --> 3, .         (abbreviated x --> 3) 
(define y (* 4 x))
  ; E2 = y --> 12, x --> 3  (most recent binding first)
(define diff (- y x))
  ; E3 = diff --> 9, y --> 12, x --> 3
(define test (< x diff))
  ; E4 = test --> #t, diff --> 9, y --> 12, x --> 3
(if test (+ (* x 5) diff) 17)
  ;                         (environment here is still E4)
(define x (* x y))
  ; E5 = x --> 36, test --> #t, diff --> 9, y --> 12, x --> 3
  ; Note: binding x --> 36 “shadows” x --> 3 , hiding the latter.

Functions

With all the commotion about Racket being a functional programming language, we should probably look at functions. The big reveal here is that functions are values. It will take us a while to appreciate all the implications of this fact, but for now, we can start small.

Function Definitions

A function definition is an expression with the following syntax:

(lambda (x1 ... xn) e)

Here, lambda2 is a keyword indicating a function definition, x1 through xn are zero or more identifiers, called the function parameters, and e is any expression, called the function body.

The evaluation rule for a function definition is simple:

  1. The result is a function closure, $\langle E, \t{(lambda (} x_1 \ \ldots \ x_n \t{) } e \t{)}\rangle$, holding the current environment, $E$, and the function.

Formally:

A function definition is an expression that creates a new function closure value – there is no further evaluation. Specifically, we do not evaluate the function body expression e now.

Note that the closure captures both the function and the current environment. Shortly, we will begin to understand why when we define the semantics of function application (a.k.a. function call), but we will understand the full impact and power of this feature only later.

Function Application

Function definitions only become useful if we can apply the functions defined. Function application or function call has the following syntax:

(e0 e1 ... en)

Here, e0 is a required expression and e1 through en are zero or more expressions. Note that, syntactically, function application looks similar to many other expressions (and one non-expression) seen so far. e0 is referred to as the function expression and e1 through en are the argument expressions

The evaluation rule for function application is:

  1. Under the current dynamic environment, $E$, evaluate $e_0$ through $e_n$ to values $v_0$, …, $v_n$.
  2. If $v_0$ is a function closure of n arguments, $\langle E’, \t{(lambda (} x_1 \ \ldots \ x_n \t{) } e \t{)}\rangle$, then the result is the result of evaluating the closure’s function body, $e$, under the closure’s environment, $E’$, extended with argument bindings: $x_1 \mapsto v_1, \ldots, x_n \mapsto v_n$. Otherwise, there is a type error.

Formally:

Important:

  1. The entity in function position can be any expression whose result is a function closure, not just a function definition expression.
  2. The function expression and the argument expressions are evaluated in the current dynamic environment.
  3. To evaluate the function body, we always extend the environment that was current when the function was defined – the $E’$ that was captured in the closure, not the current environment, $E$, that is in effect at the function call. For now, we will carefully avoid the implications of this distinction, but we will study it in great detail later.

Function Application Example

Here is a simple function application for a function that squares its argument:

((lambda (x) (* x x)) (- 12 8))

This should evaluate to 16, starting in the empty environment.

$\EvalExpr{E}{\t{((lambda (x) (* x x)) (- 12 8))}}{16}$, by the function application evaluation rule $\RuleRef{apply}$, because:

  • $\EvalExpr{E}{\t{(lambda (x) (* x x))}}{\langle E’, \t{(lambda (x) (* x x))} \rangle}$, by the function definition expression evaluation rule $\RuleRef{closure}$;
  • and $\EvalExpr{E}{\t{(- 12 8)}}{4}$, by the subtraction evaluation rule $\RuleRef{sub}$, because:
    • $\EvalExpr{E}{\t{12}}{12}$, by the value evaluation rule $\RuleRef{value}$;
    • and $\EvalExpr{E}{\t{8}}{8}$, by the value evaluation rule $\RuleRef{value}$;
    • and `$12$ and $8$ are both number values;
    • and $12 - 8$ is $4$.
  • and $\langle E’, \t{(lambda (x) (* x x))} \rangle$ is a closure whose function takes one argument and one argument is given;
  • and $\EvalExpr{\t{x} \mapsto 4, E’}{\t{(* x x)}}{16}$, by the multiplication evaluation rule $\RuleRef{mult}$ because:
    • $\EvalExpr{\t{x} \mapsto 4, E’}{\t{x}}{4}$, by the variable evaluation rule $\RuleRef{var}$;
    • and $\EvalExpr{\t{x} \mapsto 4, E’}{\t{x}}{4}$, by the variable evaluation rule $\RuleRef{var}$;
    • and $4$ and $4$ are both number values;
    • and $4 \times 4$ is $16$.

Evaluating a function definition in the DrRacket REPL shows the resulting function value, although the way it displays the value is only mildly informative:

> (lambda (x) (* x x))
#<procedure>

DrRacket has printed an opaque representation of the function closure value created by the definition, showing that it is some procedure (function closure). A function closure is a value, so why does it not show us (lambda (x) (* x x)) as the resulting value? Later…

Function Bindings and Recursion

Notice that our evaluation rule for function definition does not add any bindings to the current dynamic environment, nor does it require any further evaluation. In other words, we have defined a function, but we have not given it a name. It is anonymous. Creating a function with a name is not necessary to use it, but is nonetheless easy to do. In fact, you may notice that we currently have no way to define a recursive function. The fix is simple.

Just as with other values, functions may be used in define bindings. Recall the syntax and evaluation rules for variable bindings. Evaluation of (define x e) first evaluates expression e to value v, then creates a new dynamic environment by adding the mapping x → v to the current dynamic environment. Since a function definition is an expression, it may be used in a binding. For example, here is the square function, now named:

(define square
    (lambda (x)
        (* x x)))

Now we can easily reuse this function to call (square 4) or (square 251). Now, consider the following function, which defines an intended recursive function that computes the result of raising a given base to a given non-negative exponent, and binds the name pow to it.

(define pow
    (lambda (base exp)
        (if (< exp 1)
            1
            (* base (pow base (- exp 1))))))

The define binding actually does a little more than we described earlier. It adds the binding for x to the environment for following bindings and expressions, but it also adds the binding for x to the environment used by the function itself. This is crucial to enable recursion. Recall that a function call evaluates the function body in the environment where the function was defined, extended with bindings of its parameters to the actual function argument values. If the function’s own name is not in this environment, the function cannot call itself. We will return to define this a bit more precisely when we discuss a larger related issue later. For now, define introduces bindings that support recursion.

Syntactic Sugar

In fact, introducing a define binding for a function definition is common enough that it has its own special syntax. The following code is semantically equivalent to the previous code:

(define (pow base exp)
    (if (< exp 1)
        1
        (* base (pow base (- exp 1)))))

Special (typically, shorter) syntax for something that is already expressible in the language is called syntactic sugar.

Special Forms

Having defined functions, let us try to generalize some of our earlier definitions. We initially defined new syntax and evaluation rules for each arithmetic operation. However, examining the syntax, expressions like (+ 1 2) are syntactically similar to function calls. Their evaluation rules even look suspiciously similar to the evaluation rules for function application. In fact, we may think of +, -, *, /, quotient, <, and friends as bindings to functions that are predefined in the language. Treating them as bindings to built-in functions, we no longer need specific evaluation rules for these constructs: they are simply functions applied to arguments.

By adding functions, we might argue that our language definition has actually gotten smaller! How far can we go? Can we consider define to be the name of a special function? Unfortunately, no, since (define x e) is not an expression, it cannot be a function application. define and a handful of other keywords are so-called special forms in Racket.

What about (if e1 e2 e3)? Can we consider if to be a binding for a specially-defined function that returns its second argument if its first argument is not #f and returns its third argument otherwise?

No. (if e1 e2 e3) is an expression, but consider its evaluation rules as compared to those of function application. While function application evaluates all of its subexpressions before applying the function, if evaluates only two out of three of its subexpressions. In fact, the short-circuit boolean operations and and or (like && and || in many other languages) are also not functions, for the same reason: they do not always evaluate all of their subexpressions. However, we can define short-circuit and and or using syntactic sugar:

(and e1 e2)

is equivalent to

(if e1 e2 #f)

Consider a few examples and try to describe exactly the conditions that lead to e1 or e2 being evaluated in each of these cases.

Of the constructs we have defined so far, if, and, or, define, and lambda are not simply bindings for built-in functions. On the other hand, not can be defined as a function, since it has one argument that is always evaluated:

(define (not x)
    (if x #f #t))
    
(not #t)

Cons and Lists

Racket is descended from Scheme, which is descended from LISP, the first functional programming language, invented in the 1950s at MIT. LISP stood for LISt Processing. Support for lists is central to the LISP language and its descendants.

Thus far, the values we have seen are atoms, values that are indivisible and are not composed of smaller values. The other major category of values is built using the cons cell.3

Cons Cells

A cons cell is a value that is a pair of other values. The first value in the pair is called the car and the second value is called the cdr (pronounced could-er). “Cons” stands for “construct,” which makes sense in context of functions used to manipulate cells. The other two names are historical accidents that refer to hardware features of the first computer on which the LISP language was implemented, but were too ingrained in LISP culture to change by the time they were reconsidered. (A mnemonic to remember their order is that car comes first in alphabetical order, so it accesses the first of the pair.)

A new cons cell may be created with the built-in cons functions, which takes any two arguments (in order) to build a pair. There is no requirement what type of values are pair in the cell. Given a pair as its single argument, the built-in car function returns the first value in the pair. Given a pair as its single argument, the cdr function returns the second value in the pair.

Like any value, a cons cell, once constructed, evaluates to itself – there is no further computation required. Furthermore, a cons cell may be the result of a function application, which makes it simple to return a pair of values from a function, something that is more cumbersome in a language like Java.

Evaluating (car (cdr (cons 1 (cons 2 3)))) yields 2. Step through the evaluation to convince yourself. Recall that car, cdr, and cons are bindings of built-in functions, so this expression consists of several nested function applications.

The following function takes a pair of values and results in a new pair in which their order is reversed. It does not change the pair originally passed to the function.

(define (swap-pair pair)
    (cons ((cdr pair) (car pair))))

Here is a silly function to “sort” a pair of values given in a cons cell, reusing the swap-pair function:

(define (sort-pair pair)
    (if (< (car pair) (cdr pair))
        pair
        (swap pair)))

Dot Notation

DrRacket displays cons cells as follows:

> (cons 1 2)
'(1 . 2)

We will discuss the significance of this notation later. It has some subtleties, so, for now, do not try to create cons cells with the dot notation in your Racket programs. Use cons.

Lists

Although a cons cell may hold any pair of values, it is most commonly used to represent lists in a singly-linked list form. A list is a recursive data structure that is either:

  • null, an atom used to represent the empty list, with zero elements; or
  • a cons cell whose car is the first element in the list and whose cdr is a list that is the rest of the elements in the list.

For example, the following expression builds the list “1, 2, 3”:

(cons 1 (cons 2 (cons 3 null)))

Lists are so central to Racket that there is another shorter expression that results in the same list structure:

(list 1 2 3)

This is actually a function that takes a variable number of arguments and returns a chain of cons cells representing the desired list. (Surprise, the arithmetic functions accept variable numbers of arguments too!)

Quoted List Notation

DrRacket displays linked cons cells that form a valid list as follows:

> (cons 1 (cons 2 (cons 3 null)))
'(1 2 3)
> (list 4 5 6)
'(4 5 6)

We will discuss the significance of this notation later. It has some subtleties, so, for now, do not try to create lists by writing the quoted notation in your Racket programs. Use cons or list.

List Functions

Given the representation of lists as chains of cons cells, applying the car function to a list returns the head of that list, i.e., its first element. The cdr function returns the tail (or rest) of the given list, i.e., a list containing all but the first element of the given list. Note that the term tail is used differently when describing lists in a functional language than when describing the tail of a linked list data structure in imperative languages, where it typically refers to the last element instead of the list of all elements except the first.

Many functions over Racket lists are naturally recursive. To distinguish between the base case (an empty list represented by null) and the recursive case (a non-empty list represented by a cons cell), two built-in functions are useful:

  • null? returns #t if its argument is null and #f if its argument is not null.
  • pair? returns #t if its argument is a cons cell and #f if its argument is not a cons cell.

Our first recursive list function is sum, which takes a list and returns the sum of its elements, assuming they are all numbers:

(define (sum xs)
    (if (null? xs)
        0
        (+ (car xs) (sum (cdr xs)))))

(Note, xs is pronounced exes, as the plural of x. This is a naming idiom that will make more sense as we go along.) What does this function do?

(define (countdown n)
    (if (= n 0)
        null
        (cons n (countdown (- n 1)))))

Append two lists to create one long list:

(define (list-append xs ys)
    (if (null? xs)
        ys
        (cons (car xs) (list-append (cdr xs) ys))))

Any list function that might ever care about more than the first element of the list is recursive. Writing recursive list functions can be beautifully simple when compared to write loops and worrying about index variables and assignment statements. Recursive list functions must simply define:

  • the answer for the base case, if the list in question is the empty list; and
  • the answer for the recursive case, if the list in question is a non-empty list, in terms of the answer for the rest of the list.

Consider the list-append function, which employs recursion over its first argument, xs. If xs is empty, then appending a list ys to the end of the empty list is the same as ys itself. Otherwise, we want to append ys after the list of all xs elements except the first (with a recursive call to list-append), which is almost all of the appended list. Finally, we need to cons the first element of xs onto the front of the resulting appended list. (Yes, cons is also a verb, but car and cdr are nouns.) This works by requesting append operations with shorter and shorter versions of xs, until reaching the empty list, at which point it begins to return, consing the elements of xs onto the beginning of ys one at a time, from last to first.

Local Bindings and Scope

Earlier, we described define bindings to bind variables to values. Unfortunately, as they are not expressions, define bindings are poorly suited for use within function definitions (or any expressions for that matter), where your programming experience so far has hopefully shown local variables to be invaluable.

Let expressions introduce bindings into a local scope and are themselves expressions. They are not just a nicety; they also support efficient code that avoids recomputing results.

The syntax of a let expression is:

(let ([x1 e1] ... [xn en]) e)

First, note the use of square brackets. Racket allows [ ] anywhere it allows ( ), as long as they are matched (i.e., (+ 2 3] is not legal). When nesting many S-expressions (the name for the parenthesis-bounded syntactic units), judicious use of the different bracket types and line breaks can be useful to help with readability. In fact, you may notice that this document often splits if expressions into three lines for clarity. A similar convention is often applied to let expressions:

(let ([x1 e1]
      ...
      [xn en])
  e)

The amount or type of whitespace does not matter. Here, x1 through xn are one or more variable names and e1 through en are expressions.

The evaluation rule for let expressions is:

  1. Evaluate e1 through en to v1 through vn, in order, in the current dynamic environment.
  2. Create a new dynamic environment by extending the current dynamic environment with bindings x1 → xn, in order.
  3. Evaluate e to a value v in the new dynamic environment. v is the result of the entire let expression.

Scope

Every binding has a scope, the expressions in which the variable it binds can be used. The scope of a define binding is the entire remainder of the enclosing scope (typically the whole file) following the binding. The scope of a let binding is the body (the main subexpression, e in the syntax above) of the let expression. The following silly example shows two uses of the x variable. The first (as the body of the let expression) is within the scope of the binding shown here. The second is outside that binding’s scope.

(+  (let ([x 4]) x)  x)  ; error: second use of x is outside scope of let

The binding introduced within the let expression is visible only within its body. In other words, the binding is discarded as evaluation leaves the associated let expression.

We discuss the scope of bindings introduced in let expressions below. Later, we will explore scope in more depth along with functions.

Scope Within Bindings

Notice that all of the expressions e1 through en are evaluated in the environment that is in place when entering the let expression. This means that none of the bindings introduced by the let are visible when evaluating later bindings in the same let. For example, in the following code, the expression (+ x x) does not refer to the binding of x introduced in this let expression, but (* x y) does. Comments to the right show the environment after evaluating the line. . indicates the initial environment.

                     ; env: .
(let ([x 4]          ; env: .
      [y (+ x x)])   ; error, x not bound
  (* x y))

Assuming there is not already a binding for x in the environment in which the entire let expression is evaluated, evaluating this expression would result in an error, since x is not bound in the environment in which (+ x x) is evaluated.

The likely desired behavior here can be implemented by nesting let expressions. Comments to the right show the environment after evaluating the line:

                        ; env: .
(let ([x 4])            ; env: x --> 4, .
    (let ([y (+ x x)])  ; env: y --> 8, x --> 4, .
        (* x y)))       ; env: .

Consider the evaluation rules carefully to convince yourself that this expression evaluates to 32. The bindings introduced within the let expressions are only visible within their bodies. The bindings are discarded as evaluation leaves their associated let expressions.

Another form, let*, uses the same syntax (except with let replaced by let*). Its evaluation evaluates each binding in turn, starting with e1 to v1 in the original environment, then evaluating e2 in the current environment extended with x1 → v1, and so on, where each expression is evaluated in the new environment created by the previous binding. The following let* expression evaluates to 32. The comment to the right of each line shows the environment after evaluating that line.

                     ; env: .
(let* ([x 4]         ; env: x --> 4, .
       [y (+ x x)])  ; env: y --> 8, x --> 4, .
   (* x y))          ; env .

The bindings introduced within the let expression are only visible within later bindings in the let* expression and in the main expression. They are discarded as evaluation leaves the scope of the let*.

Shadowing

When looking up variables in environments, the matching binding most recently added to the current environment is used. This means that if the same variable is bound twice, the “closer enclosing binding wins.” This is quite simple to visualize in code in two different ways. Consider the following code, where expressions in each line are evaluated in the environment listed on the line above and the resulting environment is listed to the right of the line:

                        ; env: .
(let ([x 2])            ; env: x --> 2, .
    (let ([x (* x x)])  ; env: x --> 4, x --> 2, .
        (+ x 3)))       ; env: .

This expression evaluates to 7. Each use of the variable x refers to the closest enclosing binding of x. DrRacket includes a nice visual representation of this if you hover over variables. Additionally, bindings are added to the environment (as notated here) on the left, which represents the closest enclosing scope. Lookup also happens from the left, and the first matching binding is taken. Thus when evaluating x in (+ x 3) above, looking up x in the current environment returns 4, as added by the closest enclosing let binding. Here, we say the binding x → 4 shadows the binding x → 2.

Understanding shadowing helps cement your understanding of the environment, but using shadowing in code can be confusing and should generally be avoided for style reasons. In fact, Racket prohibits shadowing of define bindings by other define bindings in the top level of a Racket file (for reasons we will not consider), but allows any shadowing in the REPL and allows let bindings to shadow anywhere.

Local Function Bindings

Reasonable helper functions are good style. In Java, we might define helper methods and make them private, since they are an implementation detail that should be encapsulated in the containing class, but this still leaves the helper methods visible to other methods in the same class, which is not always desired. Racket lets us go even further. Since functions definitions are expressions, we can bind a name to a function in a local let binding, as seen in this silly example which is not particularly good style:

(define (quad x)
    (let ([square (lambda (x) (* x x))])
        (square (square x))))

However, unlike like define, let does not support recursion. To define a local recursive function, we need a new form, letrec, which makes its bindings visible for recursive function definitions, in the spirit of define, but in the form of an expression.

For example, here is our first attempt at a function that returns a list with x elements, the integers 1 through x:

(define (count-up-from-1 x)
    (letrec ([count (lambda (from to)
                    (if (= from to)
                        (cons to null)
                        (cons from (count (+ from 1) to))))])
       (count 1 x)))

This works and it hides its helper function from all others in good style, but the helper function itself is not quite in good functional style yet. Recall that a function call evaluates the function body in the environment where the function was defined, extended with bindings of its parameters to the actual function argument values. Our call to (count 1 x) then binds the variable to to the value of x. In the definition of count, even in recursive calls, we always pass the same value for to. Yet x is bound to this same value in the environment in which count’s body is evaluated. A better version omits to entirely:

(define (count-up-from-1-better x)
    (letrec ([count (lambda (from)
                    (if (= from x)
                        (cons x null)
                        (cons from (count (+ from 1)))))])
       (count 1)))

There is another way to introduce a local recursive function binding using define, but we will omit it to avoid dealing with the fact that a define binding is not an expression.

Let for Efficiency

One important use of let expressions is to avoid reevaluating an expensive expression because its value is needed more than once.

Consider this naive implementation of a function that returns the maximum value in a list of numbers:

(define (bad-max xs)
    (if (null? xs)
        null ; max is not defined on empty list
        (if (null? (cdr xs))
            (car xs)
            (if (> (car xs) (bad-max (cdr xs)))
                (car xs)
                (bad-max (cdr xs))))))

First, note that maximum is not defined on the empty set (or empty list). To represent this, bad-max returns null for this case instead of a number. This is not the best design choice, but we will leave it alone and consider a worse design choice.

How many (recursive) calls to bad-max occur in the application (bad-max (list 1))? (bad-max (list 1 2 3 4))? For the list holding 1 through 30, in order? Things rapidly get out of hand, passing 1 billion recursive calls for the 30-element ordered list. This is exponential blowup. The bad-max function has O(2n) running time for an n-element list. Each recursive level makes 2 calls, each of which makes 2 calls, each of which… (To keep things tricky, though, a list of 30 numbers in descending order takes only 30 recursive calls.)

The max-finding algorithm need not be so expensive, and let expressions help avoid this level of inefficiency:

(define (good-max xs)
    (if (null? xs)
        null
        (if (null? (cdr xs))
            (car xs)
            (let ([rest-max (good-max (cdr xs))])
                (if (> (car xs) rest-max)
                    (car xs)
                    rest-max)))))

This implementation has running time that is Θ(n). Each recursive call makes 0 or 1 recursive calls.

Let is Sugar

let expressions are not special – they can be implemented using functions. A let expression of the form:

(let ([x1 e1]
      ...
      [xn en])
  e)

is semantically equivalent to the following anonymous function application:

((lambda (x1 ... xn) e)
    e1 ... en)

Consider the evaluation rules of both constructs to see how this is true.

Properly Desugaring (or e1 e2)

It would seem that the expression (or e1 e2) could be desugared as (if e1 #t e2), but this is not actually the meaning of Racket’s or expression. Unlike short-circuit && and || in languages you like know already, Racket’s and and or do not guarantee to return exactly #t or #f. Specifically, while #f is the only “false” value, any non-#f is “true”. Thus an expression like (or e1 e2) actually returns #f if both e1 and e2 evaluate to #f. It returns the result of evaluating e1 if this result is non-#f, otherwise it returns the result of evaluating e2. While the (and e1 e2) desugaring given earlier ((if e1 e2 #f)) still holds, the (or e1 e2) desugaring is:

(let ([x1 e1])
    (if x1 x1 e2))

where x1 is some variable name not used (without first being bound) within e1 or e2.

First-class and Higher-order Functions

A language with first-class functions provides all the privileges of a value to a function: a first-class function is a value. Examples of these privileges are: passing a function as an argument to another function, returning a function as the result of a function, storing a function in a data structure, and several more.

A higher-order function* is a function that takes other functions as arguments or returns other functions as results.

A function closure is a function that refers to bindings created outside the function that were present in the environment where the function was defined.

These three ideas are powerful (and often confused with each other). In Racket, we have already seen that functions are values, but we will now consider many more interesting implications of this fact.

The ill-defined concept of a functional language or programming style is often attached to these features, but also more generally to many others, like (or at least a minimum) of mutation, a focus on evaluation of expressions instead of execution of commands, a syntax that looks closer to math than to C. Yet it is possible to program in a functional style, even in an imperative, curly-brace, statement language like C or Java. In fact, after experience programming in the “functional languages” we consider in this course, you may find that your Java or C programming begins to use more immutable data, fewer loops, or trying to emulate some of the benefits of first-class functions where they are not present by cobbling together other language features.

Functions as Arguments

Higher-order functions that take other functions as arguments are classic tools in the functional programming toolbox. They support the goal of abstracting repeated patterns in a way that is arguably more flexible than allowed by many languages without higher-order functions.

Map

A classic function that takes functions as arguments is map. The map function takes a function, f, and a list, xs, and returns a new list where each element is the result of applying f to the corresponding element of xs:

(define (map f xs)
    (if (null? xs)
        null
        (cons (f (car xs)) (map f (cdr xs)))))

For example, given the increment function:

(define (inc x) (+ x 1))

the following function application:

(map inc (list 1 2 3 4 5))

results in the list containing incremented versions of the original values: '(2 3 4 5 6).

The map function is so heavily use that it is available in the default environment in Racket.

Filter

Another classic higher-order function is filter, which takes a function f and a list xs and returns a list whose elements are all elements x of xs for which (f x) evaluates to a non-#f value.

(define (filter f xs)
    (if (null? xs)
        null
        (if (f (car xs))
            (cons (car xs) (filter f (cdr xs)))
            (filter f (cdr xs)))))

Given the function even? which returns #t for even numbers and #f for others:

(define (even? x) (= 0 (modulo x 2)))

the following function application:

(filter even? (list 1 2 3 4 5))

evaluates to the list containing just 2 and 4: '(2 4).

The filter function is so heavily use that it is available in the default environment in Racket.

Anonymous Functions as Arguments

Anonymous functions (lambda) really shine with higher-order functions like map and filter. For example, let us use a one-off function written just for this particular task: find the multiples of 23 in a list of numbers:

(filter (lambda (x) (= 0 (modulo x 23)))
    (list 46 87 49 23 14 92 99))

Lexical Scope and Function Closures

As promised earlier when defining evaluation rules for functions, we have taken care to keep things simple when using functions as values. The functions we have passed as arguments thus far have all been closed, meaning their bodies refer only to their own parameters or locally defined variables and not to any other variables bound outside the function definition. However, our evaluation rule for function calls says that a function’s body is evaluated in an environment including bindings of its parameters to its arguments and any bindings present in the environment where the function was defined. Exploiting this last part holds great potential, but only if we get the semantics right!

When a function is called, its body is evaluated in the environment where the function was defined, not the environment where the function is called.

This example demonstrates the difference:

(define x 1)
(define f (lambda (y) (+ x y)))
(define z
    (let ([x 2]
          [y 3])
      (f (+ x y))))

The name f is bound to a function with parameter y. Its body also looks up x in the environment where f was defined. Regardless of where it is called, this function always increments its argument, because it always refers to the binding of x that was in scope when it was defined: 1. Later, we have a different environment where f maps to this function, x maps to 2, y maps to 3, and we evaluate the function call (f x). Let us apply the function call evaluation rule to see the result:

  1. Evaluate the function expression f. f is a variable, so we lookup its value in the environment, which yields the function we described.

  2. Evaluate the argument expression (+ x y). This looks up x and y in the current environment. They are mapped to 2 and 3, respectively, so the result is 5.

  3. Call the function with the argument 5, which evaluates the body, (+ x y) in the environment that was in effect when the function was defined (x → 1) extended by mapping the parameter variable y to the argument value 5. Evaluating the addition requires looking up x and y in this environment, yielding 1 and 5, so the sum—and thus the result of the function call—is 6.

The argument was evaluated in the current environment, but the function body was evaluated in the “old” environment. This rule is called lexical scope.

We will consider the alternative—and generally more problematic—dynamic scope later. (It would yield 7 above.) The original LISP language of the 1950s employed dynamic scope, which was later “fixed” in Scheme (Racket’s parent) and other languages.

Lexical Scope via Environments and Closures

We have been a little loose with our claim that functions are values. A function value, known as a function closure, or just closure for short, has to parts:

  • The function definition (its parameter names and its body expression); and
  • The environment where the function definition was evaluated.

To be clear, this pair is not a cons cell that can be manipulated within the language. Closures are created only by the evaluation of function definitions and their parts are used only by function applications.

The term closure arises from the fact that the act of attaching an environment to a function definition closes an otherwise open function—a function whose body may contain free variables, variables that are not local variable bindings or parameters of the function. Creating a closure closes up the function with everything it needs for later application. A closure is closed in that no binding in the environment of a function call can affect the evaluation of the function on a given argument. The closure is a black box whose only input is the function argument.

Here are two tricky examples to illustrate the details of lexical scope and closures.

Example 1

(define x 1)
(define f
    (lambda (y)
        (let ([x (+ y 1)])
            (lambda (z) (+ x y z)))))
(define z
    (let ([x 3]
          [g (f 4)]
          [y 5])
      (g 6)))

This example binds f to a closure that maps x to 1. When we later evaluate (f 4), we evaluate the function’s body (let ([x (+ y 1)]) (lambda (z) (+ x y z))) in an environment where x maps to 1, extended to mapy to 4. But then due to the let binding of x, we shadow x and evaluate (lambda (z) (+ x y z)) in an environment where x maps to 5 and y maps to 4. The (lambda (z) (+ x y z)) expression itself evaluates to a closure with the environment we just described. So (f 4) returns a closure that, when called, will always add 5 and 4 to its argument, no matter the environment where it is called. Finally, in the last line, (g 6) evaluates to 15, even though the current environment maps x to 3 and y to 5. So z is bound to 15.

Example 2

(define f
    (lambda (g)
        (let ([x 3])
            (g 2))))
(define x 4)
(define h
    (lambda (y)
        (+ x y)))
(define z (f h))

In this example, f is bound to a closure that takes another function as an argument and returns the result of applying that function to the value 2. The closures bound to h always adds 4 to its argument because the argument is y, the body is (+ x y), and the function is defined in an environment where x maps to 4. In the last line, z will be bound to 6. The let binding of x to 3 is irrelevant: the call (g 2) is evaluated by looking up g to get the closure that was passed in and then using that closure with its environment (in which x maps to 4) with 2 for an argument.

Why Lexical Scope

While it takes practice to unlock the power of lexical scope and higher-order functions, decades of experience make clear that this semantics is what we want. Much of the rest of this section will describe various widespread, powerful idioms that rely on lexical scope.

But first we can also motivate lexical scope by showing how dynamic scope (where you just have one current environment and use it to evaluate function bodies) leads to some fundamental problems.

First, suppose in Example 1 above the body of f was changed to (let ([q (+ y 1)]) (lambda (z) (+ q y z))). Under lexical scope this is fine: we can always change the name of a local variable and its uses without it affecting anything. Under dynamic scope, now the call to (g 6) will make no sense: we will try to look up q, but there is no q in the environment at the function call site.

Similar issues arise with Example 2: The body of f in this example is awful: we have a local binding we never use. Under lexical scope we can remove it, changing the body to (g 2), and know that this has no effect on the rest of the program. Under dynamic scope it would have an effect. Also, under lexical scope we know that any use of the closure bound to h will add 4 to its argument regardless of how other functions like g are implemented and what variable names they use. This is a key separation of concerns that only lexical scope provides.

For “regular” variables in programs, lexical scope is the way to go. There are some compelling uses for dynamic scoping for certain idioms, but few languages have special support for these (Racket does, but we will not explore it in depth) and very few if any modern languages have dynamic scoping as the default. Interestingly, LISP (origin ancestor of Racket) “got this wrong” and used dynamic scope.

Additional Reference

The Racket Guide is an excellent, readable reference for the full Racket language. We study only the core of the language for our purposes in 251. There are many other interesting language features, some of which we may return to consider later, including: contracts, a dynamic checking system that can check properties beyond dynamic type-checking; hygienic macros, a system for principled definitions of syntactic sugar by end-programmers; and first-class continuations, a construct for capturing, saving, and manipulating the “rest of the computation to be done”.

Acknowledgments

These notes mix adaptations of notes on the ML and Racket languages by Dan Grossman at the University of Washington (by permission) and new material for CS 251 by Ben Wood and Lyn Turbak.

  1. I have chosen words carefully here. By “we never change it”, I mean: Racket will allow us to mutate bindings via something like assignment, but we will avoid this feature entirely in our use of the language. In general, mutation of bindings is available, but used rarely in Racket programs. As we leave Racket behind for our next case study language, ML, bindings really will be immutable. ↩

  2. The name lambda comes from the Greek letter λ as used in the λ-caluculus, the formal foundation of the Racket language. ↩

  3. Racket includes other compound values besides cons cells. We focus on the simplest primitives. ↩