Functions of Functions

This material is adapted from Computer Science Logo Style volume 1: Symbolic Computing 2/e Copyright (C) 1997 MIT (Chapter 5: Functions of Functions). It has been edited to conform with the Imagine dialect of Logo, and to omit some explanation (which you may want to read later) about higher order functions in general.

This part of the workshop is about a way to deal systematically with data aggregates--collections of data. We want to be able to say "carry out this computation for each member of that aggregate." Processing large amounts of data uniformly is one of the abilities that distinguish computers from mere pocket calculators.

This character: » indicates an exercise, something for you to try. Many exercises include examples of how your procedures should behave, but your programs should work for any reasonable input, not just the one(s) shown.

The Problem: Initials

To make this concrete, we'll look at a very simple example. I'd like to write a procedure that can figure out a person's initials, like this:

? show initials [George Harrison]
[G H]

One obvious approach is to find the initials of the first name and the last name:

to initials :name
output sentence (first first :name) (first last :name)
end

The trouble is that this approach doesn't work for people with middle names. We'd like our initials procedure to be able to handle any length name. But it doesn't:

? show initials [John Alec Entwistle]
[J E]
? show initials [Peter Blair Denis Bernard Noone]
[P N]

What we want is this:

? show initials.in.our.dreams [John Alec Entwistle]
[J A E]
? show initials.in.our.dreams [Peter Blair Denis Bernard Noone]
[P B D B N]

If we knew that the input would have exactly five names, we could extract the first letter of each of them explicitly. But we want to be able to handle any number of words, one or five or fifty.

One Solution: Numeric Iteration

If you've programmed before in other languages, then one solution will immediately occur to you. You create a variable n whose value is the number of words in the input, then you have a variable i that takes on all possible values from 1 to n, and you select the ith word from the input and pull out its first letter. Most languages have a special notation for this sort of computation:

for i = 1 to n : ... : next i                (BASIC)
for 1 := 1 to n do begin ... end             (Pascal)
for (i=1; i<=n; i++) { ... }                 (C)

All of these have the same meaning: Carry out some instructions (the part shown as ... above) repeatedly, first with the variable named i having the value 1, then with i equal to 2, and so on, up to i equal to n. This technique is called numeric iteration. "Iteration" means repetition, and it's "numeric" iteration because the repetition is controlled by a variable that takes on a sequence of numeric values.

The easiest way to do something equivalent in Logo is this:

to initials :name
(let "result [])
repeat count :name [make "result se :result (first item repcount :name)]
output :result
end

The repcount (repeat count) primitive outputs 1 the first time through the repeat, outputs 2 the second time, and so on. So, for example, if we give Logo the instruction

show initials [Raymond Douglas Davies]

then the sequence of events is essentially this:

(let "result [])                          ; initialize result

COUNT :NAME outputs 3, so REPEAT does three repetitions.

First repetition:
  REPCOUNT outputs 1
  (ITEM REPCOUNT :NAME) outputs Raymond
make "result (se :result first "Raymond)  ; (result is now [R])

Second repetition:
  REPCOUNT outputs 2
  (ITEM REPCOUNT :NAME) outputs Douglas
make "result (se :result first "Douglas)  ; (result is now [R D])

Third repetition:
  REPCOUNT outputs 3
  (ITEM REPCOUNT :NAME) outputs Davies
make "result (se :result first "Davies)   ; (result is now [R D D])

REPEAT is finished; procedure outputs [R D D]

Critique of Numeric Iteration

Computers were originally built to deal with numbers. Numeric iteration matches closely the behind-the-scenes sequence of steps by which computers actually work. That's why just about every programming language supports this style of programming.

Nevertheless, keeping track of the number of repetitions in order to choose a word by its numeric position in the sentence isn't anything like the way you, a human being, would solve the initials problem without a computer. First of all, you wouldn't begin by counting the number of words in the name; you really don't have to know that. You'd just say, for example, "First of Raymond is R; first of Douglas is D; first of Davies is D." When you ran out of names, you'd stop.

The manipulation of the result variable to collect the results also seems unnatural. You wouldn't think, "I'm going to start with an empty result; then, whatever value result has, I'll throw in an R; then, whatever value result now has, I'll throw in a D" and so on.

In fact, if you had to explain to someone else how to solve this problem, you probably wouldn't talk about a sequence of steps at all. Rather, you'd draw a picture like this one:

To explain the picture, you'd say something like "Just take the first of each word." You wouldn't even mention the need to put the results together into a sentence; you'd take that for granted.

In Logo we can write an initials procedure using the same way of thinking that you'd use in English:

to initials :name
output map "first :name
end

The map procedure means "collect the results of doing this for each of those."

As this example illustrates, map is easy to use. But it's a little hard to talk about, because it's a function of a function.

Functions of Functions: Map

Map takes two inputs. The first is a word, which must be the name of a one-input Logo operation. The second can be any word or list. The output from map is a list. The members of the output list are the results of applying the named operation to the members of the second input.

? show map "first [Rod Argent]
[R A]

In this example, the output is a list of two members, just as the second input is a list of two members. Each member of the output is the result of applying first to one of the members of map's second input.

Many people, when they first meet map, are confused by the quoting of its first input. Usually, quoted words are data, and procedure names aren't quoted:

? show "date
date

? show date
[27 8 2005 6]

You've learned that a quoted word means the word itself, while an unquoted word asks Logo to invoke a procedure. But now, when I want to use the first procedure as input to map, I'm quoting its name. Why?

Start by ignoring the Logo notation and think about the domain of the map function. We want the map function to have another function, the function "first" in this case, as one of its inputs:

It's tempting to say that in Logo, a function is represented by a procedure, so map represents map, and first represents first. If this were algebra notation, I'd say map(first, Rod Argent), so in Logo I'll say

show map first [Rod Argent]            ;; wrong!

But when a Logo instruction has two unquoted procedure names in a row, that doesn't mean that the second function is used as input to the first! Instead, it means that the output from invoking the second function is used as the input to the first. In this case, we'd be composing map and first:

As the plumbing diagram shows, the list that we intended as the second input to map actually ends up as the input to first, and Logo will complain because map isn't given enough inputs.

Instead, we must use the name of the first procedure to represent it. That gives this diagram:

Ordinarily map works with one-input functions. But we can give map extra inputs (by enclosing the invocation of map in parentheses, as usual) so that it can work with functions of more than one input.

? show (map "item [2 1 2 3] [john paul george ringo])
[o p e n]
? show (map "sum [1 2 3] [40 50 60] [700 800 900])
[741 852 963]

Each input after the first provides values for one input to the mapped function. For example, [2 1 2 3] provides four values for the first input to item. The input lists must all have the same length (two lists of length four in the item example, three lists of length three in the sum example).

In the examples so far, the input data have been lists. Here's an example in which we use map with words. Let's say we're writing a program to play Hangman, the word game in which one player guesses letters in a secret word chosen by the other player. At first the guesser sees only a row of dashes indicating the number of letters in the word; for each guess, more letters are revealed. We aren't going to write the entire program, but we're ready to write the operation that takes the secret word, and a list of the letters that have been guessed so far, and outputs a row of letters and dashes as appropriate. Since map outputs a list, and I want a word, I have to call word with all the members of the output from map as inputs. Another function of functions, called apply, will do that:

to hangword :secret :guessed
output apply "word map "hangletter :secret
end

to hangletter :letter
output ifelse memberp :letter :guessed [:letter] ["_]
end

? print hangword "potsticker [e t a o i n]
_ot_ti__er
? print hangword "gelato [e t a o i n]
_e_ato

» Write an operation exaggerate that takes a sentence as input and outputs an exaggerated version:

? print exaggerate [I ate 3 potstickers]
I ate 6 potstickers
? print exaggerate [The chow fun is good here]
The chow fun is great here

It should double all the numbers in the sentence, and replace "good" with "great," "bad" with "terrible," and so on.

A function whose domain or range includes functions is called a higher order function. The function represented by the map procedure is a higher order function. (We can loosely say that map is a "higher order procedure," but in Logo that isn't technically true. Procedures aren't data in Logo, so the input to map is a word, the name of a procedure, and not the procedure itself.)

» Write a procedure transform.beatles that takes a procedure as an input, applies it to each of the Beatles, and returns the results in a sentence:

to amazify :name
output word "|the-amazing-| :name
end

? show transform.beatles "amazify
[the-amazing-John the-amazing-Paul the-amazing-George the-amazing-Ringo]

Higher Order Selection: Filter

The purpose of map is to transform each member of a list by applying some function to it. Another higher order function, filter, is used to select some members of a list, but not others, based on a criterion expressed as a predicate function. For example:

? show filter "number? [76 trombones, 4 calling birds, and 8 days]
[76 4 8]

to beatle? :person
output member? :person [John Paul George Ringo]
end

? show filter "beatle? [Bob George Jeff Roy Tom]
[George]

What happens if we use the initials procedure that we wrote with people's names in mind for other kinds of names, such as organizations or book titles? Some of them work well:

? show initials [Computer Science Logo Style]
[C S L S]
? show initials [American Civil Liberties Union]
[A C L U]

but others don't give quite the results we'd like:

? show initials [Association for Computing Machinery]
[A f C M]
? show initials [People's Republic of China]
[P R o C]

We'd like to eliminate words like "for" and "of" before taking the first letters of the remaining words. This is a job for filter:

to important? :word
output not member? :word [the an a of for by with in to and or]
end

to initials :name
output map "first (filter "important? :name)
end

? show initials [Association for Computing Machinery]
[A C M]
? show initials [People's Republic of China]
[P R C]

» Write a procedure choose.beatles that takes a predicate function as its input and returns a sentence of just those Beatles (John, Paul, George, and Ringo) that satisfy the predicate. For example:

to ends.vowel? :word
output vowel? last :word
end

to vowel? :letter
output member? :letter "aeiou
end

? show choose.beatles "ends.vowel?
[George Ringo]

» Write a predicate true.for.all? that takes two inputs, a predicate procedure and a sentence. It should return true if the predicate input returns true for every word in the sentence.

to even? :number
output equal? (mod :number 2) 0
end

? show true.for.all? "even? [2 4 6 8]
true

? show true.for.all? "even? [2 6 3 4]
false

» Write a predicate true.for.any? that takes two inputs, a predicate procedure and a sentence. It should return true if the predicate input returns true for at least one word in the sentence.

? show true.for.any? "even? [3 4 7 9]
true

? show true.for.any? "even? [3 5 7 9]
false

Many to One: Apply

Of course, what we'd really like is to have those initials in the form of a single word: ACLU, CSLS, ACM, and so on. For this purpose we need yet another higher order function, one that invokes a combining function to join the members of a list.

? show apply "word [C S L S]
CSLS
? show apply "sum [3 4 5 6]
18

Apply takes two inputs. The first must be the name of a procedure; the second is a list of suitable inputs to the procedure. Apply can be used with any procedure, as long as you use a list of suitable inputs:

? show apply "mod [100 7]
2

But in practice, the most common use of apply is with accumulators: procedures that take any number of inputs, and combine them in some way, such as word, sum, or product.

to acronym :name
output apply "word initials :name
end

? show acronym [Association for Computing Machinery]
ACM

We can use apply "word [...] to turn a sentence into a word. What if we want to do the opposite, turning a word into a sentence of one-letter words? Unfortunately, we can't say

? show apply "sentence "UNICEF

because the second input to apply must be a list, not a word. Here's one way that works:

? show map "first "UNICEF
[U N I C E F]

This works because map does accept a word as its second input, operating on each letter of the word. Don't try too hard to understand what first is doing in that example; it doesn't really do anything, because each time map calls it, the input is a single-letter word, and first "a is just a.

» Write a procedure letter.count that takes a sentence as its input and returns the total number of letters (not spaces> in the sentence:

? show letter.count [fixing a hole]
11

» Write a GPA procedure. It should take a sentence of grades as its input and should output the corresponding grade point average:

? show gpa [A |A+| |B+| B]
3.665

Hint: write a helper procedure base.grade that takes a grade as input and returns 0, 1, 2, 3, or 4, and another helper procedure grade.modifier that returns -.33, 0, or .33, depending on whether the grade has a minus, a plus, or neither.

Choosing the Right Tool

So far you've seen three higher order functions: map, filter, and apply. How do you decide which one to use for a particular problem?

Map transforms each member of a list individually. The result contains as many members as the input.

Filter selects certain members of a list and discards the others. The members of the result are members of the input, without transformation, but the result may be smaller than the original.

Apply transforms the entire list into a single result by combining all of the members in some way.

Anonymous Functions

In several of the examples in this chapter, I've had to write "helper" procedures such as hangletter and importantp that will never be used independently, but are needed only to provide the function input to a higher order function. It would be simpler if we could avoid writing these as separate procedures.

Does that sound confusing? This is one of those ideas for which an example is worth 1000 words:

to hangword :secret :guessed
output apply "word map [ifelse member? :% :guessed [:%] ["_]] :secret
end

Until now, the first input to map has always been a word, used to represent the function with that word as its name. In this example we see how a nameless function can be represented: as a list containing a Logo expression, but with :% (that is, a request for the value of a variable named %) where the function's input belongs. Such a list is called a template.

? show filter [member? :% [John Paul George Ringo]] [Bob George Jeff Roy Tom]
[George]

Notice that the templates don't say output, as the named procedures did. That's because procedures are made of instructions, whereas these are expression templates. When input values are "plugged in" for :%, the template becomes a Logo expression, which means that when evaluated it has a value. If the template said output, it would be saying to use that value as the output from the procedure containing it! (This is just a particular example of something you already know: that output immediately stops the procedure it's in, even if there are more instructions below it.)

The :% works only for functions of one input, so it can't be used with multi-input map.

» Write prepend.every:

? show prepend.every "s [he aid he aid]
[she said she said]

? show prepend.every "anti [dote pasto gone body]
[antidote antipasto antigone antibody]

» Write a procedure called letterwords that takes as its inputs a letter and a sentence. It returns a sentence containing only those words from the input sentence that contain the input letter: \extag{\letwds}

? show letterwords "o [got to get you into my life]
[got to you into]

» Write a procedure common.words that takes two sentences as inputs and returns a sentence containing only those words that appear both in the first sentence and in the second sentence.

? show common.words [i want to tell you] [got to get you into my life]
[to you]

» Write a function appearances that takes two inputs, a word and a sentence. It outputs the number of times the word appears in the sentence:

? show appearances "yeah [she loves you, yeah yeah yeah]
3

» Write a procedure unabbrev that takes two sentences as inputs. It should return a sentence that's the same as the first sentence, except that any numbers in the original sentence should be replaced with words from the second sentence. A number 2 in the first sentence should be replaced with the second word of the second sentence, a 6 with the sixth word, and so on.

? show unabbrev [John 1 Wayne Fred 4] [Bill Hank Kermit Joey]
[John Bill Wayne Fred Joey]

? show unabbrev [I 3 4 Tell 2] [Do You Want To Know A Secret?]
[I Want To Tell You]

» Write a procedure first.last whose input will be a sentence. It should return a sentence containing only those words in the input sentence whose first and last letters are the same:

? show first.last [california ohio nebraska alabama alaska massachusetts]
[ohio alabama alaska]

» Write a procedure substitute that takes three inputs: two words and a sentence. It should return a version of the sentence, but with every instance of the second word replaced with the first word:

? show substitute "maybe "yeah [she loves you yeah yeah yeah]
[she loves you maybe maybe maybe]

Nested Mapping

Suppose we have two sets of things, and we want all the pairings of one of these with one of those. An example will make clear what's desired:

? show crossproduct [red blue green] [shirt pants]
[[red shirt] [blue shirt] [green shirt] [red pants] [blue pants] [green pants]]

This is a tricky example because there are two different mistakes we could make. We don't want to "flatten" the result into a sentence:

[red shirt blue shirt green shirt red pants blue pants green pants]

but we also don't want all the shirts in one list and all the pants in another:

[[[red shirt] [blue shirt] [green shirt]]
 [[red pants] [blue pants] [green pants]]]

Here's the solution:

to crossproduct :these :those
output apply "sentence [prepend.each :these :%] :those
end

to prepend.each :these :that
output map [sentence :% :that] :these
end

» Notice that this solution uses apply "sentence with the result of one call to map but not with the other one. Try to predict what would happen if you used apply "sentence both times, or neither time, or interchanged the two. Then try it on the computer and be sure you understand what happens and why!

By the way, this is a case in which we still need a named helper function despite the use of templates, because otherwise we'd have one template inside the other, and Logo couldn't figure out which :% to replace with what:

to crossproduct :these :those
output apply "sentence map [map [sentence :% :%] :these] :those  ; (wrong!)
end

Map as a Command

Sometimes what you want isn't a function at all. You want to take some action for each member of a list. The most common one is to print each member on a separate line, in situations where you've computed a long list of things. You can use map with an instruction template, rather than an expression template as we've done until now.

? map "print (crossproduct [[ultra chocolate] pumpkin [root beer swirl] ginger] [cone cup])
ultra chocolate cone
pumpkin cone
root beer swirl cone
ginger cone
ultra chocolate cup
pumpkin cup
root beer swirl cup
ginger cup

If you look closely at the letters on your computer screen you'll see that they are made up of little dots. One simple pattern represents each letter in a rectangle of dots five wide and seven high, like this:

  *    *****  *****  ****   *****
 * *   *   *  *      *   *  *
*   *  *   *  *      *   *  *
*****  ****   *      *   *  ***
*   *  *   *  *      *   *  *
*   *  *   *  *      *   *  *
*   *  *****  *****  ****   *****

The following program allows you to spell words on the screen in big letters like these. Each letter's shape is kept as the value of a global variable with the letter as its name. (I haven't actually listed all 26 letters.) The value is a list of seven words, each of which contains five characters, some combination of spaces and asterisks.

to say :word
repeat 7 [map [sayrow repcount :%] :word  print []]
print []
end

to sayrow :row :letter
type item :row thing :letter
type "|  |
end

make "b [|*****| |*   *| |*   *| |**** | |*   *| |*   *| |*****|]
make "r [|*****| |*   *| |*   *| |*****| |* *  | |*  * | |*   *|]
make "i [|*****| |  *  | |  *  | |  *  | |  *  | |  *  | |*****|]
make "a [|  *  | | * * | |*   *| |*****| |*   *| |*   *| |*   *|]
make "n [|*   *| |**  *| |**  *| |* * *| |*  **| |*  **| |*   *|]

? say "brian
*****  *****  *****    *    *   *
*   *  *   *    *     * *   **  *
*   *  *   *    *    *   *  **  *
****   *****    *    *****  * * *
*   *  * *      *    *   *  *  **
*   *  *  *     *    *   *  *  **
*****  *   *  *****  *   *  *   *

» Modify the program so that say takes another input, a number representing the size in which you want to print the letters. If the number is 1, then the program should work as before. If the number is 2, each dot should be printed as a two-by-two square of spaces or asterisks; if the number is 3, a three-by-three square, and so on.

Repeated Invocation: Generate

Finally, sometimes you want to compose a function with itself several times:

? print first bf bf bf bf [The Continuing Story of Bungalow Bill]
Bungalow

? show generate 5 "bf [The Continuing Story of Bungalow Bill]
[[The Continuing Story of Bungalow Bill]
 [Continuing Story of Bungalow Bill]
 [Story of Bungalow Bill]
 [of Bungalow Bill]
 [Bungalow Bill]]

Notice that, since the starting value is included in the result, we have to ask for five elements in the result in order to apply bf four times.

Often it's only the final result that we care about, not all the results along the way; in that case, just take last of the value output by generate:

? print first last (generate 5 "bf [The Continuing Story of Bungalow Bill])
Bungalow

Generate takes three inputs. The first is a number, indicating how many elements you want in the list of results. The second input is the function to invoke repeatedly. The third input is the starting value.

to power :base :exponent
output last generate :exponent+1 [:% * :base] 1
end

? print power 2 8
256

to iseq :from :to
output generate :to-:from+1 [:%+1] :from
end

? show iseq 3 8
[3 4 5 6 7 8]

If you'd like to apply a multi-input function repeatedly with generate, put all the inputs into a list. One example in which multi-input generate is useful is the Fibonacci sequence. Each number in the sequence is the sum of the two previous numbers; the first two numbers are 1. So the sequence starts

A formal definition of the sequence looks like this:

In order to compute, say, F₂₃, we must know both F₂₂ and F₂₁. As we work our way up, we must always remember the two most recent values, like this:

To express this using generate, put the most recent two values in a list, starting with the initial values [1 1].

to fib :n
output first last generate :n+1 [list (last :%) (sum first :% last :%)] [1 1]
end

? print fib 5
8
? print fib 23
46368

It's output first last ... because generate generates a list of two-number lists. We want the first number of the last number-pair generated.

Another situation in which generate with two-element lists can be useful is to process every member of a list, using the first element to remember the already-processed ones and the second element to remember the still-waiting ones. The simplest example is reversing the words in a sentence:

to reverse :sent
output first last generate (count :sent)+1
                           [list (fput first last :% first :%) (bf last :%)]
                           list [] :sent
end

? print reverse [how now brown cow]
cow brown now how

Invent Your Own Higher-Order Functions

But I think the fib and reverse examples are too complicated, because the generate function's interface isn't quite what I want. So I can invent a notation I like better:

to gen2 :n :fun1 :start1 :fun2 :start2
output last generate :n+1 [list apply :fun1 (list :%) apply :fun2 (list :%)]
                          list :start1 :start2
end

to %1
output first :%
end

to %2
output last :%
end

I've made three changes in my modified version of generate:

to fib :n
output first gen2 :n [%2] 1 [%1+%2] 1
end

to reverse :sent
output first gen2 count :sent [fput first %2 %1] [] [bf %2] :sent
end

to repeated :fn :num :input
output last generate :num+1 :fn :input
end

? show repeated "bf 5 [a b c d e f g h i j k l]
[f g h i j k l]

red green blue violet

red orange yellow green

? master "roygbiv 4 "false

What's your guess?
royg
You have 1 correct-position matches
and 2 incorrect-position matches.

What's your guess?
rogy
You have 1 correct-position matches
and 2 incorrect-position matches.

What's your guess?
orygbv
You must guess exactly 4 colors.

What's your guess?
oryx
The available colors are: roygbiv

What's your guess?
oryr
No fair guessing the same color twice!

What's your guess?
oryg
You have 0 correct-position matches
and 3 incorrect-position matches.

What's your guess?
rbyg
You have 1 correct-position matches
and 2 incorrect-position matches.

What's your guess?
boyg
You have 0 correct-position matches
and 3 incorrect-position matches.

What's your guess?
roby
You have 1 correct-position matches
and 3 incorrect-position matches.

What's your guess?
rybo
You have 2 correct-position matches
and 2 incorrect-position matches.

What's your guess?
ryob
You win in 8 guesses!
?

? print choose.nodup 4 "roygbiv
briy

? print pick [Pete John Roger Keith]
John
? print pick [Pete John Roger Keith]
Keith
? print pick "roygbiv
b

generate :number.wanted+1
         [list add.one.color.to.first.:%
               remove.that.color.from.last.:%]
         (list " :colors)

? rotate "roygbiv
ygbivro
? rotate "roygbiv
vroygbi
? rotate "roygbiv
bivroyg

? print exact "rgrb "yrrr
1
? print inexact "rgrb "yrrr
1
? print inexact "royg "rgbo
2