1.3.2 Constructing Functions using Lambda Expressions

Permalink copied!

1.3.2

Constructing Functions using Lambda Expressions

In using sum as in section 1.3.1, it seems terribly awkward to have to declare trivial functions such as pi_term and pi_next just so we can use them as arguments to our higher-order function. Rather than declare pi_next and pi_term, it would be more convenient to have a way to directly specify the function that returns its input incremented by 4 and the function that returns the reciprocal of its input times its input plus 2. We can do this by introducing the lambda expression as a syntactic form for creating functions. Using lambda expressions, we can describe what we want as

x => x + 4

and

x => 1 / (x * (x + 2))

Then we can express our pi_sum function without declaring any auxiliary functions:

function pi_sum(a, b) {
    return sum(x => 1 / (x * (x + 2)),
               a,
               x => x + 4,
               b);
}

Again using a lambda expression, we can write the integral function without having to declare the auxiliary function add_dx:

function integral(f, a, b, dx) {
    return sum(f,
               a + dx / 2,
               x => x + dx,
               b)
           *
           dx;
}

In general, lambda expressions are used to create functions in the same way as function declarations, except that no name is specified for the function and the return keyword and braces are omitted (if there is only one parameter, the parentheses around the parameter list can also be omitted, as in the examples we have seen).

[1] ($parameters$) => $expression$

The resulting function is just as much a function as one that is created using a function declaration statement. The only difference is that it has not been associated with any name in the environment.

We consider

function plus4(x) { 
    return x + 4; 
}

to be equivalent to

[2]

const plus4 = x => x + 4;

We can read a lambda expression as follows:

//                      x         =>                   x    +   4
//                      ^         ^                    ^    ^   ^
// the function of an argument x that results in the value plus 4

Like any expression that has a function as its value, a lambda expression can be used as the function expression in an application such as

((x, y, z) => x + y + square(z))(1, 2, 3);

or, more generally, in any context where we would normally use a function name.

[3]

Note that => has lower precedence than function application and thus the parentheses around the lambda expression are necessary here.

Using const to create local names
const を使ったローカル名の作成

Another use of lambda expressions is in creating local names. We often need local names in our functions other than those that have been bound as parameters. For example, suppose we wish to compute the function

\[\begin{array}{lll} f(x, y)&=&x(1 + x y)^2 +y (1 - y) + (1 + x y)(1 - y) \end{array}\]

which we could also express as

\[\begin{array}{rll} a &=& 1+xy\\ b &=& 1-y\\ f(x, y) &= &x a^2 +y b + a b \end{array}\]

In writing a function to compute $f$, we would like to include as local names not only $x$ and $y$ but also the names of intermediate quantities like $a$ and $b$. One way to accomplish this is to use an auxiliary function to bind the local names:

function f(x, y) {
    function f_helper(a, b) {
        return x * square(a) + y * b + a * b;
    }
    return f_helper(1 + x * y, 1 - y);
}

Of course, we could use a lambda expression to specify an anonymous function for binding our local names. The function body then becomes a single call to that function:

function f_2(x, y) {
    return ( (a, b) => x * square(a) + y * b + a * b
           )(1 + x * y, 1 - y);
}

A more convenient way to declare local names is by using constant declarations within the body of the function. Using const, the function can be written as

function f_3(x, y) {
    const a = 1 + x * y;
    const b = 1 - y;
    return x * square(a) + y * b + a * b;
}

Names that are declared with const inside a block have the body of the immediately surrounding block as their scope.

[4]$^,$[5]

Conditional statements
条件文

We have seen that it is often useful to declare names that are local to function declarations. When functions become big, we should keep the scope of the names as narrow as possible. Consider for example expmod in exercise 1.26.

function expmod(base, exp, m) {
    return exp === 0
           ? 1
           : is_even(exp)
           ? (  expmod(base, exp / 2, m)
              * expmod(base, exp / 2, m)) % m
           : (base * expmod(base, exp - 1, m)) % m;
}

This function is unnecessarily inefficient, because it contains two identical calls:

expmod(base, exp / 2, m);

While this can be easily fixed in this example using the square function, this is not so easy in general. Without using square, we would be tempted to introduce a local name for the expression as follows:

function expmod(base, exp, m) {
    const half_exp = expmod(base, exp / 2, m);
    return exp === 0
           ? 1
           : is_even(exp)
           ? (half_exp * half_exp) % m
           : (base * expmod(base, exp - 1, m)) % m;
}

This would make the function not just inefficient, but actually nonterminating! The problem is that the constant declaration appears outside the conditional expression, which means that it is executed even when the base case exp === 0 is met. To avoid this situation, we provide for conditional statements, and allow return statements to appear in the branches of the statement. Using a conditional statement, we can write the function expmod as follows:

function expmod(base, exp, m) {
    if (exp === 0) {
        return 1;
    } else {
        if (is_even(exp)) {
            const half_exp = expmod(base, exp / 2, m);
            return (half_exp * half_exp) % m;
        } else {
            return (base * expmod(base, exp - 1, m)) % m;
        }
    }	    
}

The general form of a conditional statement is

if ($predicate$) { $consequent$-$statements$ } else { $alternative$-$statements$ }

As for a conditional expression, the interpreter first evaluates the $predicate$. If it evaluates to true, the interpreter evaluates the $consequent$-$statements$ in sequence, and if it evaluates to false, the interpreter evaluates the $alternative$-$statements$ in sequence. Evaluation of a return statement returns from the surrounding function, ignoring any statements in the sequence after the return statement and any statements after the conditional statement. Note that any constant declarations occurring in either part are local to that part, because each part is enclosed in braces and thus forms its own block.

Exercise 1.34

Suppose we declare

function f(g) {
   return g(2);
}

Then we have

f(square);

f(z => z * (z + 1));

What happens if we (perversely) ask the interpreter to evaluate the application f(f)? Explain.

Let's use the substitution model to illustrate what happens:

f(f)
f(2)
2(2)

The application 2(2) leads to an error, since 2 is neither a primitive nor a compound function.

[1]

In section 2.2.4, we will extend the syntax of lambda expressions to allow a block as the body rather than just an expression, as in function declaration statements.

[2]

In JavaScript, there are subtle differences between the two versions: A function declaration statement is automatically ``hoisted'' (moved) to the beginning of the surrounding block or to the beginning of the program if it occurs outside of any block, whereas a constant declaration is not moved. Names declared with function declaration can be reassigned using assignment (section 3.1.1), whereas names declared with constant declarations can't. In this book, we avoid these features and treat a function declaration as equivalent to the corresponding constant declaration.

[3]

It would be clearer and less intimidating to people learning JavaScript if a term more obvious than lambda expression, such as function definition, were used. But the convention is very firmly entrenched, not just for Lisp and Scheme but also for JavaScript, Java and other languages, no doubt partly due to the influence of the Scheme editions of this book. The notation is adopted from the $\lambda$ calculus, a mathematical formalism introduced by the mathematical logician Alonzo Church (1941). Church developed the $\lambda$ calculus to provide a rigorous foundation for studying the notions of function and function application. The $\lambda$ calculus has become a basic tool for mathematical investigations of the semantics of programming languages.

[4]

Note that a name declared in a block cannot be used before the declaration is fully evaluated, regardless of whether the same name is declared outside the block. Thus in the program below, the attempt to use the a declared at the top level to provide a value for the calculation of the b declared in f cannot work.

const a = 1;
function f(x) {      
    const b = a + x;
    const a = 5;
    return a + b;
}
f(10);

The program leads to an error, because the a in a + x is used before its declaration is evaluated. We will return to this program in section 4.1.6 (exercise 4.19), after we learn more about evaluation.

[5]

The substitution model can be expanded to say that for a constant declaration, the value of the expression after = is substituted for the name before = in the rest of the block body (after the declaration), similar to the substitution of arguments for parameters in the evaluation of a function application.

< Previous

Next >

1.3.2

Constructing Functions using Lambda Expressions

Using const to create local names const を使ったローカル名の作成

Conditional statements条件文

Using const to create local names
const を使ったローカル名の作成

Conditional statements
条件文