We're talking about the three things that every programming language has: primitives, a means of combination, and a means of abstraction. In this lecture, we discuss procedures, a powerful means of abstraction.
The associated reading is again from An Introduction to Scheme and its Implementation, specifically these parts of the "Procedures" section: "First Class Procedures", "Higher-order Procedures", "Anonymous Procedurese and lambda", and "Variable Arity".
We've identified several important things that appear in most powerful programming languages:
We discussed item 3 in terms of naming, but we're not finished with it yet.
In fact, we've hardly covered this important topic at all. I hinted at a
very important thing in the last lecture when I said that *
evaluates to an operation that does multiplication. This means that
* is really just a name for an object that performs
multiplication.
Now, we know that multiplication is a function. In Scheme and many other high-level languages, functions are objects that can be assigned names just like any other computational object. Being able to name algorithms gives us an extremely valuable tool for abstracting away the details of a computation.
None of this should come as a surprise to you since you've been dealing with this concept for years. For example, at some time in your life you probably learned how to do square roots by hand. Now when you tell someone to take the square root of a number, you don't communicate the entire process each time. You refer to the process of taking a square root by name and expect the other person to know what to do. Think of how complicated this process would be if you couldn't talk about the process by name.
You are, of course, familiar with named algorithms. They are commonly referred to as subroutines, subprograms, functions, or procedures depending on the particular language. Scheme's procedures are commonly called functions because they return a value. Let's not worry about what the differences are right now.
As an example, lets consider an algorithm for squaring a number. All of us know how to square a number, we multiply it by itself. We could write a Scheme function that squares a number like so:
(define squareOfX (* x x))
Assuming x had been previously defined, squareOfX would
now name the square of x. However, if we also wanted the square
of y, z, and so on, we'd have to rewrite the statement for each different
variable. In addition, the program's function might not be as clear. What
we need is a way of generalizing the idea of squaring a number without
worrying about which number we're squaring. We do this using a
special operator called, for historical reasons, lambda.
Lambda is a special operator that takes two operands, the first a list of parameter names and the second an expression defining the operation to be performed. So for example, we could write
==> ((lambda (x) (* x x)) 5)
25
To find out what's going on here, let's return to our evaluation algorithm
from the last section. This is a compound expression, so we first perform
step 1. It says to evaluate each of the subexpressions. The second
subexpression, 5, is easy, but what about the first? What is the value
of (lambda (x) (* x x))? When evaluated, the lambda operator
returns a procedure. To see this, let's evaluate the expression and look
at the result:
==> (lambda (x) (* x x))
#<procedure:1:1>
The result #<procedure:1:1>
(or something like it--the first number will change with each procedure
you define)
is the computer's
way of printing a procedure. Next evaluate the expression:
==> +
#<primitive:+>
The built-in procedure + is printed out in much the same way as the result of our lambda expression. Scheme treats all procedural object, whether user defined or built in, in much the same way.
So, when we evaluate (lambda (x) (* x x)), we get a procedure that
takes a single argument, named x and performs the operation
defined by (* x x). So when we evaluate ((lambda (x) (* x x))
5), the first subexpression returns an operation that performs the
square. When we perform step 2 in our evaluation algorithm, the 5 is
substituted in wherever x occurs in the body to give (* 5
5) and then the body is evaluated.
We still have a small problem; its not very convenient to have to write
(lambda (x) (* x x)) each time we want to perform the square
operation, and many lambda expression are much larger than this.
We can solve this problem by assigning a name to the value returned by the
lambda expression and then using the name to refer to it. For example:
==> (define square (lambda (x) (* x x)))
square
This says that we want to associate the name square with a procedure
that has a single argument, x, and is procedurally defined by the expression
(* x x). Note that we do not differentiate between giving names to
data objects such as 5 or 1988 and giving names to procedural objects such as
the results of lambda expressions.
Note: In Lecture 2, we saw how you could also define the same procedure using the following syntax:
While the two are equivalent, the lambda notation is much more flexible. This notation requires that you name the functions as you create them. The lambda notation allows you to define functions, then give names to them if you wish. Please try to get used to the lambda notation and use it. |
Having defined square, it can be used as follows:
==> (square 5)
25
==> (square (+ 3 3))
36
==> (square (square 3))
81
Notice that we can use the function name just as we would any other operator. The second example shows that the operand of out function can be an expression just like any other operator. The third example shows an expression returning a value that is used as the parameter for the function square. Notice that there is no difference in the way built-in operators and user-defined operators are used or applied. This simple syntax is one of the things that makes Scheme such a powerful language.
We can also use square as part of other function definitions. For
example x^2 + y^2 can be expressed as (+ (Square X) (Square
Y)) In Scheme. We Can Define A Function, SumOfSquares, that
given any two numbers as parameters produces the sum of their squares:
==> (define sum-of-squares (lambda (x y)
(+ (square x) (square y))))
sum-of-squares
The function sum-of-squares calls the function square
twice, once for each of its parameters, x and y, and
returns the sum. Having defined sum-of-squares, we can use it in
another function definition as follows:
==> (define any-old-func (lambda (w)
(sum-of-squares (- w 3) w)))
any-old-func
==> (any-old-func 5)
29
It should be clear to you why named procedures are so powerful: they allow us to hide details and solve the problem at a higher level of abstraction.
Just to make sure that the notion of procedures is clear, let's look at another example:
==> (define radius 5)
==> (define PI 3.14159)
==> (define circ (* 2 pi radius))
==> circ
31.4159
==> (define circ (lambda (radius) (* 2 pi radius)))
==> (circ 6)
37.69908
==> (circ radius)
31.4159
Here are some questions for review and entertainment!
circ and
the second definition of circ in the above example. square and once using the
definition of square. ((lambda...) 5
6) (+ 6 5) and (square 3).
a.) ((lambda (x y) (+ x y 5)) 3 4)
b.) ((lambda (a d g) (* a (+ d g))) 4 8 2)
c.) ((lambda (a) (square a)) 5)
d.) ((lambda (radians) (/ (* 3.14159 radians) 180)) 30)
e.) ((lambda (x) (x 3)) (lambda (x) (* x x)))
==> (define five (lambda () 5))
==> (five)
5
==> five
#[COMPOUND-PROCEDURE #x161FE4]
==> (define four 4)
==> four
4
==> (four)
Application of Non-Procedure Object 4
There is no environment available;
using the current read-eval-print environment.
Error->
Quit!
==>
Explain each result in the above transcript. In particular focus on the difference
between four and five.
(new-cos 1.2 radians)).
To find the sin of 46 degrees type (new-sin 46 degrees). Hint:
use (define degrees 0) and (define radians 1) and define
your functions assuming these definitions. We'll see later how to do this
without using auxiliary definitions.
What should the result of your functions be if the user types something
besides degrees or radians for the second argument?
We say a data type is first class when it is treated by the language the same way that other data objects are treated. We have seen that procedures can be named in the same way that any other data object can be named. They can also be stored in variables or in data structures. In fact, you can do just about anything in terms of naming, storing, passing, etc. with a procedure data type than you can with any other data type.
Values of some type are first-class if they can be:
How are functions treated by programming languages?
| Language | Passed as Arguments | Returned From Functions | Nested Scope |
| Java | No | No | No |
| C | Yes | Yes | No |
| C++ | Yes | Yes | No |
| Pascal | Yes | No | Yes |
| Modula-3 | Yes | No | Yes |
| Scheme | Yes | Yes | Yes |
| ML | Yes | Yes | Yes |
For procedures to be first class, we would also have to be able to pass them to other procedures as arguments and return them from procedures as results. We can.
Functions that operate on other functions (take functions as parameters and/or return other functions) are called higher-order functions.
As an example, consider function composition.f and g the composition of f
and g is defined as
(f o g)(x) ::= f(g(x))
(define compose
(lambda (f g)
(lambda (x)
(f (g x)))))
;Value: compose
add2 that adds 2 to its
argument:
(define add2
(lambda (n) (+ n 2)))
;Value: add2
(add2 4)
;Value: 6
(define add4 (compose add2 add2))
;Value: add4
(add4 5)
;Value: 9
((compose car cdr) '(1 2 3 4))
;Value: 2
You can use the power of first-class functions to do things you're not used to doing in other languages that don't have first-class functions. One of these is called currying (named after Haskell Curry, a mathematician who developed this technique). The idea of currying is to turn a function taking some number of parameters into one that accepts the first parameter and returns a curried version of a function taking the rest of the parameters.
For example, instead of writing an add function that takes two parameters:
(define add
(lambda (x y) (+ x y))))
you could write a curried version that takes one parameter and returns a function that takes the second parameter:
(define curried-add
(lambda (x)
(lambda (y) (+ x y))))
curried-add like this:
((curried-add 3) 4)
7
(define add3 (curried-add 3))
(add3 4)
7
By now, you're probably wondering why this is useful. In fact, it just seems like a lot more work to use
the function because now you have to make two function calls instead of one.
But the real power in this technique comes when you realize that the function add3 is now usable just
like any other function.
The term arity is used to describe the number of parmeters a function takes. Unary functions (arity 1) take one parameter, binary (arity 2) functions take two parameters, arity 5 functions take 5 parameters, and so on.
Some functions, though, can take any number of parameters. For example, the + function in Scheme can be used to add together any number of values:
(+ 1 2 3 4 5 6)
21
These functions are said to have variable arity. (Can you think of functions in C++ that have variable arity?)
In Scheme, variable-arity functions are defined using the lambda notation and
replacing the list of the formal parameters with a single variable to which
the entire list of parameters will be bound. (Sort of like how argv
works in C++.) So, instead of writing a two-parameter addition function:
(define add
(lambda (x y) (+ x y)))
we could write a variable-arity addition function:
(define add
(lambda lst-o-stuff (...)))
In this example, the list of formal parameters (x y) was replaced
by a single variable lst-o-stuff. When called, the variable lst-o-stuff
would be bound to a list containing all of the parameters passed to add.
So, if we called add with six parameters:
(add 1 2 3 4 5 6)
The variable lst-o-stuff would be bound to the list (1 2 3 4 5
6).
Here are a couple of scheme operators that use other functions:
| map | (map f lst) |
Calls |
| apply | (apply f lst) |
Calls f only one time and passes all of the items in lst
as parameters: (f 1 2 3) |
Last updated at 1:03 pm on Monday, June 28, 2004.