CS10: The Beauty and Joy of Computing - Fall 2015

Lecture 13: Functions as Data

• Call/Run, Building Our Own HoFs
• Building Keep Demo
• Combine
• Anonymous Functions and Ringification
• WeirdHoF Demo [extra]

2021

Since this lecture was originally done six years ago, some of the formatting in the code may look a little weird / out of date.

Higher Order Functions

A higher order procedure is a “procedure that takes another procedure as one of its arguments”.

• Also known as a higher order function or HoF.

​

We’ve seen 4 HoFs. Three that operate on lists, and one tester:

​

​

​

​

Minor trivia note: As mentioned much earlier in the course, in the real world people often use the word “function” to mean any procedure, even if it is not a “pure function”.

• Will be doing this throughout today’s lecture and the rest of the course.

Clicker Question

Which of the four HoFs we’ve seen are pure functions?

1. All of them.
2. All of them except test are pure functions.
3. Only test is a pure function.
4. None of them are pure functions.
5. It depends.

​

​

​

Reminder, a pure function is one for which:

• There are no side effects.
• The output is always the same for given inputs.�

​

Introducing Run and Call

Let’s now add two more HoFs to our toolbox:

• Run simply runs a function.
• Call runs a reporter and reports the result.

​

Run and call are varadic (variable number of arguments).

• Used to specify input parameters to the function called by run/call.
• Examples:

​

Both calls to run give the same square.

One Funny Thing

If you provide fewer input values that there are inputs, they are replicated to fill all available slots.

​

​

• Arguably not a very nice thing about Snap!: Can make code confusing.
• Arguably a great thing about Snap!: Allows you to do things like use as a square function.

Why Functions? (Why Review)?

Example, calling a function:

To avoid repetitive code, we make one function that can draw any square size.

Another Kind of Repetition

Highly redundant code is usually a sign that there is probably a better way.

• In this case, no big deal, since the redundancy is only a couple of lines.
• ...but imagine having to do this for a drawing program for every possible shape and line type.

​

How might creating a HoF help?

Creating a Draw Square HoF

Let’s generalize Draw Square into a HoF.

• Will be able to draw a square with ANY kind of line.
• Even lines that haven’t been invented yet!

Draw Square HoF Answer

Use “run” to invoke procedures.

What Run Does For Us

Run doesn’t do anything particularly magical.

• You’ll usually use it as a way to get around a lack of input bubbles for functions stored inside variables.
• As seen before, can also use to run functions not inside variables.

Building Keep

Run

We’ve now learned enough to rebuild the HoFs we already know.

• Let’s try to build keep from scratch.

​

Combine

How Combine Works (Below the Abstraction Line)

We know that combine takes a two-input function and somehow computes the result on a list.

​

Here’s how it really works:

• Takes the last two items of the list and computes the result on those:

• Takes the result of the previous computation and the 3rd to last item:

• Takes the result of the previous computation and the 4th to last item:

• etc...

Joinswap Clicker Question

What does the following code report?

1. abcd
2. acdb
3. bdac
4. dcba
5. (nothing)

Associativity

A dyadic function is a function with two inputs.

​

A dyadic function is said to be “associative” if f(a, f(b, c)) = f(f(a, b), c)).

• Associative:

​

• Not-associative:

​

• Equivalently: If you compose an associative function with itself, it doesn’t matter in which order you do the composition.

​

​

Associativity and Combine in Snap!

Combine in Snap! is right-associative (works its way from right to left).

• Combine in other languages may not be right-associative.
• If the input function is associative, doesn’t matter what order the language uses to implement combine.
• Could be left-associative, right-associative, random, or anything else.
• Extra for experience: Write a recursive “combine” HoF block. It’s very short.

Anonymous Functions and Ringification

Clicker Question

What is the value of x after the script below is run?

1. -3
2. 3
3. Undefined.
4. Undefined since the minus reporter is not associative.
5. A one input reporter that reports 3 less than the input value, i.e. “call(x) with inputs (5)” would report 2.

​

​

Ringification

In Snap!, reporters are ALWAYS evaluated before a value is returned.

• Even if you leave some inputs blank, it simply substitutes some default value.

​

If we want to prevent the reporter from actually running, we need to ringify it.

• One way: Right click on an input and click “ringify”:
• A ringified function is frozen in time, and must be invoked manually!

Using a Ringified Function

Below are two examples of how ringified functions behave.

• Note: These examples are a little silly, you’d never actually compute 5-3 using the code on the right.

When is Ringification Useful?

We’ve already used ringification!

• It’s always there, built right into map, keep, combine, draw square, etc.
• This is “implicit” ringification. Used it without even thinking.
• Explicit ringification is what we saw in the previous slide (freezing a function in time).
• Will see some uses soon, but first, some puzzles!

Puzzle

How many inputs does have?

1. 0
2. 1
3. 2

Puzzle

How many inputs does have?

• 0
• 1
• 2: A function and a length!

Puzzle (Don’t Discuss)

What will this code do:

​

1. Something weird, since there are two inputs but we only provide one.
2. Draws a square with a side length 100, where each line is wiggly.
3. Draws a square with a side length 100, where each line is normal.

Puzzle

How many inputs does have?

• 0
• 1
• 2

Puzzle

How many inputs does have?

• 0
• 1
• 2

​

There is only one input!

• This:

​

​

• Is equivalent to:

Input!

Puzzle (Discuss)

What will this code do:

​

• Something weird, since there are two inputs but we only provide one.
• Draws a square with a side length 100, where each line is wiggly.
• Draws a square with a side length 100, where each line is normal.

Explicit Ringification and Anonymous Functions

One common pattern when using HoFs is to define custom functions that are used as inputs to the HoF. Examples:

• The joinswap clicker question.
• Using map for homework 2 to encrypt characters.

​

Some programmers consider it silly to create such simple blocks, especially if they’re only used in exactly one place.

• Ringification lets us avoid this. Let’s try it out in Snap!...

Explicit Ringification and Anonymous Functions

One common pattern when using HoFs is to define custom functions that are used as inputs to the HoF. Examples:

• The joinswap clicker question.
• Using map for homework 2 to encrypt characters.

​

Some programmers consider it silly to create such simple blocks, especially if they’re only used in exactly one place.

• Ringification lets us avoid this. Let’s try it out in Snap!

These do exactly the same thing!

Explicit Ringification and Anonymous Functions

The ringified function and joinswap are exactly the same in behavior!

• Both take two arguments.
• Both report the join of those two arguments in reverse.
• The only difference is that the ringified function has no name.

​

Anonymous function: A function with no name.

• Example:

Weird HoF Demo

(Time Permitting)

Using HoFs

Courtesy of Dan Garcia (Berkeley’s primary CS10 architect), let’s try out a demo which uses another HoF called compose.

f(x) = x * 10 + 5

f(10) = 105