So far, we've touched on the idea of higher-order programming as treating functions in the same way as values. So far, we've seen plenty of functions that take other functions as arguments. However, there are a few aspects of this that we haven't really touched on yet. For instance, the idea behind this is that we can treat functions in the same way as values.
One of the things we can do is create functions that produce other functions. Why would we want to do this? One of the limitations of some of the higher-order list operations we've discussed so far is that they only take one argument. For instance, we may want to double every element of a list of numbers. To do that, we might want to define a function like
(: double (-> Number Number))
;; Double the given number
(define (double x)
(* 2 x))and plug that in to map. Of course, there are two problems with this. First, it's really inconvenient to have to define a simple function like this every time we want to use it in another function. Secondly, what if we want to triple or quadruple elements of a list? That's another function or two we'd have to write. This seems like another pattern ripe for abstraction.
Hypothetically speaking, what we want to do is not difficult: we just want a way to say "multiply this by a given $n$". So what if we try the following?
(: mult-by (-> Number (-> Number Number)))
;; Create a function that multiplies its input by the given number
(define (mult-by n)
(local
{(: mult-by-n (-> Number Number))
;; Multiply the given number by n
(define (mult-by-n x)
(* n x))}
mult-by-n))What just happened? If we take a careful look at the type ascription for our function mult-by, we see that it takes a Number and produces... a (-> Number Number)? It produces a function!
Inside the definition of mult-by, we have defined an entire function based on the argument n. The result of a function call to mult-by is the function that was defined. Now, rather than writing a function for double or a function for triple, we can simply call (mult-by 2) or (mult-by 3) to get the function we want.
It's important to take a step back and really understand what is going on here. Up until now, we've only seen functions that produce values. This is very intuitive. For example, we are perfectly happy to recognize that (* 3 4) is an expression that, when we apply the * function, evaluates to the value 12. In other words, we recognize that we can simply substitute the expression and the value, and vice-versa.
What we have just done means that we can do the same for functions. Here, (mult-by 3) produces a function, This means that any place where we would use the name of a function, we can replace it with the above expression. This means something like
((mult-by 3) 4)is a valid Racket expression! This expression is evaluated as follows: (mult-by 3) evaluates to a function, and then we apply this function to 4 to get a value of 12.
Coincidentally, this is why Racket does not tolerate superfluous parentheses! As a reminder from the beginning of the quarter, the parentheses mean something in Racket: function application. Because expressions can evaluate to functions, this means that the extra parentheses were being interpreted as attempts at function applitcations where there were no functions.
Now, this is still not quite perfect. For instance, it is still kind of annoying that we need to write an entire type ascription and give this function a name inside of a function. For example, consider the following version of double.
(: double (-> Number Number))
;; Doubles the given number
(define (double x)
(local
{(: double-of-x Number)
(define double-of-x (* 2 x))}
double-of-x))This seems kind of ridiculous. For one thing, we don't use the name double-of-x anywhere except to return the value, so why did we need to define it? And secondly, there's no need to write a type ascription, because the types are guaranteed by the type of x, the types of the functions that are used in the expression, and the type ascription of the function double.
So why do we need that stuff for functions? All of these same arguments apply to the function that we defined inside of mult-by. So, maybe we don't?
Recall our discussion of expressions from our initial forays into the Racket language. Racket has a very simple syntactic structure in which an expression begins with a (, is followed by a keyword or function application, followed by arguments, and ends with a ). Such an expression typically evaluates to a value.
However, we have been discussing the idea of treating functions like values, but we have yet to see an expression that evaluates to a function. We've seen names and function applications evaluate to functions, but at some level, both of these things are being replaced by the "real" function. But what is the "real" function? Our treatment of functions and values implies that at some level, there must be an expression that evaluates to a function.
We will demonstrate this by the following example.
(: mult-by (-> Number (-> Number Number)))
;; Create a function that multiplies its input by the given number
(define (mult-by n)
(lambda ([x : Number]) (* n x)))Here, we have defined a function without giving it a name at any point. The function itself is called an anonymous function. But the mechanism by which we describe the function is called a λ (lambda) expression. Here, λ is the Greek letter which we call lambda and corresponds to l in the Latin alphabet.
First, to understand the syntax, let's consider a plain old function like we've been writing.
(: function-name (-> Type-x Type-y Type-z))
(define (function-name x y)
an expression that provides a value of Type-z goes here)An equivalent lambda expression (without the name and type ascription) looks like the following.
(lambda ([x : Type-x]
[y : Type-y])
an expression that provides a value of Type-z goes here)So there are three parts to a lambda expression:
lambda or λ,
Lambda expressions evaluate to functions, in the same way that a function call to a function that produces a function would. That is,
((lambda ([x : Integer]) (* 2 x)) 10)is an expression that evaluates to 20, since the lambda expression evaluates to a function, and we apply the function on 10 with the parentheses.
If we think about it, it is the parameters and the function body that are the important parts of the function. The name is a convenience that we use to refer to it, but there's nothing that says that we need a name. In fact, we can do funkier things like the following:
(: mult-by (-> Number (-> Number Number)))
(define mult-by
(lambda ([n : Number])
(lambda ([x : Number]) (* n x))))Observe that this definition is not a function definition like we've been writing! Rather, we have bound the name mult-by to an expression of type (-> Number (-> Number Number)). But this expression is a lambda expression, so it'll evaluate to a function!
This seems a bit strange, but it is only strange because we separated the idea of functions from values in the first place. It wouldn't be strange if we treated functions and values in the same way, and now lambda functions give us a way to do so. In fact, while we might think of lambda expressions as a "new" way to write functions, the truth is that we've been hiding the true nature of functions all along.
All function definitions in Racket are really lambda expressions.
You might reasonably think that I mean all functions in Racket are like lambda expressions, but what I mean is that they are literally lambda expressions. You see, when the Racket interpreter reads your function definitions, it actually turns them into lambda expressions.
With this in mind, we can revisit many of the functions we've written before, but instead use a lambda expression where before, we would've needed a function name (and the associated function definition and all that comes with it).
(: red-squares (-> (Listof Byte) (Listof Image)))
;; Produce a list with a square with colour red from each number
;; from the given list
(define (red-squares lst)
(map (lambda ([x : Byte]) (square 50 'solid (color x 0 0)))
lst))
(: lte140 (-> (Listof Integer) (Listof Integer)))
;; Given a list of integers, produce a list with only those
;; integers that are at most 140
(define (lte140 ns)
(filter (lambda ([n : Integer]) (<= n 140)) ns))
(: plot-points (-> (Listof (Pairof Integer Integer)) Image))
;; Plots points onto a square with respect to the top left corner
(define (plot-points pts)
(foldr (lambda ([pt : (Pairof Integer Integer)]
[bg : Image])
(match pt
[(Pairof x y)
(place-image (circle 2 'solid 'red)
x y
bg)]))
(empty-scene 100 100)
pts))
So at this point, you may wonder about the centrality of lambda expressions to the Racket language, particularly since there's a big ol' lambda staring at you every time you open DrRacket. We should note that lambda expressions are not unique to Racket or Lisp or even programming languages. Lambda expressions actually come to us from all the way back in 1936 due to Alonzo Church's lambda calculus, which, along with Turing's work, is one of the foundational works in what we now know as computer science.
The big idea here is the idea that functions and values are really the same thing. When phrased like this, it seems like something that's only of interest to, say, functional programmers. But the idea has some pretty significant consequences. For instance, the fact that functions and values are the same thing is what allows the idea of "software" or general purpose computing to exist: If we think of functions as programs and values as data, then it is clear that we implicitly treat programs as data when we do things like feed them into a compiler.