Summary

• Scope and local variables
• Currying and partial application
• Higher-order functions: map and filter

Scoping rules

We have seen that almost every modern programming language uses lexical scoping: For any variable reference that occurs in a program, we can look in the surrounding code to uniquely determine which variable definition it corresponds to.

This is really important for functions because it means that the variable meanings depend only on the place where the function was defined, not on where it gets called from. This follows the rough idea that a function should “do the same thing” no matter what context we use it in.

However, the precise scoping rules do vary by language. In C, C++, Java, and Rust, scopes are indicated explicitly with curly braces { and }. Every variable declaration binds a new name, which is valid from that point in the code, up until the end of the current scope (i.e. matching } token).

For example, consider the following simple Rust program:

fn main() {
    let x = 3;
    for i in 1..5 {
        println!("A {} {}", i, x);
        let x = 10;
        println!("B {} {}", i, x);
    }
}

On the “A” print statement, x refers to the outer declaration with value 3. But the “B” statement, x now refers to the inner declaration with value 10. This is true not just in the first iteration but every iteration of the loop.

Note, this is possible because C, C++, Java, and Rust make a distinction between variable declaration and variable (re)assignment. If we dropped the let on the x = 10 line (and declared x to be mutable), then the program behavior would be different!

But not all languages do things that way. For example, consider the same code in Python:

def main():
    x = 3
    for i in range(1,6):
        print(f"A {i} {x}")
        x = 10
        print(f"A {i} {x}")

How does the Python interpreter know whether each x = statement is supposed to be declaring a new local variable or re-assigning some existing one?

In Python, the answer is that new scopes are only created for functions, and nothing else. So each function has its own scope of local variables, consisting of any variable which gets assigned anywhere within that function. In the above example, x is declared just once (implicitly) as a local variable of main.

Because this isn’t always what the programmer wants, Python also has a way of specifying “I don’t want this variable to be a local variable; use the outer one.” That is done via the nonlocal keyword inside a function definition. For example, check out this small program:

def main():
    x = 10
    def nested():
        nonlocal x
        x = 20
        print(x)
    nested()
    print(x)

If we call main() as written here, it prints 20 twice. The reason is that the nexted() function modifies the x from main, rather than creating its own local variable x.

But if we took out the nonlocal x declaration, then calling main() would print 20 and 10 — the outer x doesn’t get changed in that case because it’s a local variable inside nested().

Bash works in pretty much the same way as Python with local and global variables. This presents an interesting trade-off in language design: Python and Bash have a simpler syntax because you don’t need to say anything special to declare a new variable binding. But the downside is that the semantics gets more complicated and the interpreter has to make some subtle choices about what is or isn’t a local variable.

Currying arguments

We have been looking at nested functions here — that is, functions defined inside other functions, and possibly functions returning other functions.

One common use of nested functions is for partial application — we basically have one function with multiple arguments, but want to split it up into two (or more) function calls, each of which specifies different arguments.

For example, here is a Scheme function which takes an integer and a string, and checks whether the string is at most that long:

(define short?
  (lambda (maxlen str)
    (<= (string-length str) maxlen)))
(short? 10 "apple") ; returns #t
(short? 4 "banana") ; returns #f

But now sometimes, we might want a function that just takes a string, and checks whether its length is at most some fixed number of characters, say 8. This corresponds to partial application of the short? function, where we specify the length separately from the string.

To make this possible, the standard trick is to change the function definition by having two nested functions, each of which takes one argument, like this:

(define curried-short
  (lambda (maxlen)
    (lambda (str)
      (<= (string-length str) maxlen))))
((curried-short 10) "apple") ; returns #t
(define check (curried-short 8))
(check "pineapple") ; returns #f

This technique is called currying - turning a multi-argument function into a nested series of single-argument functions. (It’s named after the logician Haskell Curry, who was a contemporary of Alonzo Church and developed much of the mathematics behind functional programming starting in the 1920s.)

You can do exactly the same thing in Python, like this:

def curried_short(maxlen):
    def inner(str):
        nonlocal maxlen
        return (len(str) <= maxlen)
    return inner
curried_short(10)("apple") # True
check = curried_short(8)
check("pineapple") # False

(Technical point: the nonlocal declaration isn’t really necessary here, because the value of maxlen is not changed in the inner function. But I think it’s nice to be explicit about it anyway!)

Map and filter

One reason to use currying is for higher-order functions that take other functions, and apply them across a data structure.

There are many such functions available in modern programming languages, but the two most common are:

• map applies the same function to each element in a list, returning a new list with all of the results.

• filter applies a predicate function to every element in a list, returning a new list containing only the elements for which the predicate returned True.

For example, in Scheme, we can use a lambda to double all the numbers in a list:

(map (lambda (x) (* 2 x))
     '(1 2 3 4))
; returns (2 4 6 8)

And we could use the curried-short curried function from above, to filter a list of strings for those with at most 5 letters:

(filter (curried-short 5)
        '("orange" "apple" "pear" "grape" "strawberry"))
; returns ("apple" "pear" "grape")

This same concept exists nowadays in many languages! For example, this Java program will do that same sort of filtering as in the Scheme example:

import java.util.function.Predicate;
import java.util.List;
import java.util.stream.Collectors;

public class Filterer {
    static Predicate<String> curriedShort(int maxlen) {
        return str -> str.length() <= maxlen;
    }

    public static void main(String[] args) {
        List<String> orig = List.of("orange", "apple", "pear", "grape", "strawberry");
        List<String> filtered = orig.stream()
            .filter(curriedShort(5))
            .collect(Collectors.toList());
        System.out.println(filtered);
    }
}