### 23` `Staging

#### 23.1` `Problem Definition

```
data ABT:
| unknown
| person(name :: String, bm :: ABT, bf :: ABT)
end
```

```
fun abt-size(p :: ABT):
doc: "Compute the number of known people in the ancestor tree"
cases (ABT) p:
| unknown => 0
| person(n, p1, p2) => 1 + abt-size(p1) + abt-size(p2)
end
end
```

Now let’s think about a slightly different function:
`how-many-named`

, which tells us how many people in a family have
a particular name. Not only can more than one person have the same
name, in some cultures it’s not uncommon to use the same name
across generations, either in successive generations or skipping one.

Do Now!

What is the contract for

`how-many-named`

? The contract for this function will be crucial, so make sure you do this step!

`how-many-named :: ABT, String -> Number`

Do Now!

Define

`how-many-named`

.

#### 23.2` `Initial Solution

```
fun how-many-named(p :: ABT, looking-for :: String):
cases (ABT) p:
| unknown => 0
| person(n, p1, p2) =>
if n == looking-for:
1 + how-many-named(p1, looking-for) + how-many-named(p2, looking-for)
else:
how-many-named(p1, looking-for) + how-many-named(p2, looking-for)
end
end
end
```

```
p =
person("A",
person("B",
person("A", unknown, unknown),
person("C",
person("A", unknown, unknown),
person("B", unknown, unknown))),
person("C", unknown, unknown))
```

```
check:
how-many-named(p, "A") is 3
end
```

#### 23.3` `Refactoring

Now let’s apply some transformations, sometimes called code refactorings, to this function.

```
fun how-many-named(p :: ABT, looking-for :: String):
cases (ABT) p:
| unknown => 0
| person(n, p1, p2) =>
(if n == looking-for: 1 else: 0 end)
+
how-many-named(p1, looking-for) + how-many-named(p2, looking-for)
end
end
```

`if`

is in fact an expression, which has a value; in this case the value
is either `0`

or `1`

. This value can then be used in an addition.Now let’s look at this code even more closely. Notice something interesting. We
keep passing two parameters to `how-many-named`

; however, only one of
those parameters (`p`

) is actually changing. The name we are
looking for does not change, as we would expect: we are looking for the same
name in the entire tree. How can we reflect this in the code?

```
fun how-many-named(looking-for :: String, p :: ABT):
cases (ABT) p:
| unknown => 0
| person(n, p1, p2) =>
(if n == looking-for: 1 else: 0 end)
+
how-many-named(looking-for, p1) + how-many-named(looking-for, p2)
end
end
```

`how-many-named :: ABT, String -> Number`

`how-many-named :: String, ABT -> Number`

`how-many-named("A", p)`

instead. Observe that the function calls inside `how-many-named`

have also
been altered in the same way.#### 23.4` `Separating Parameters

This sets us up for the next stage. The parameters of functions are meant to
indicate what might vary in a function. Because the name we’re looking for is a
constant once we initially have it, we’d like the actual search function to
take only one argument: where in the tree we’re searching. That is, we want its
contract to be `(ABT -> Number)`

. To achieve that, we need another
function that will take the `String`

part.

```
fun how-many-named(looking-for :: String) -> (ABT -> Number):
lam(p :: ABT) -> Number:
cases (ABT) p:
| unknown => 0
| person(n, p1, p2) =>
(if n == looking-for: 1 else: 0 end)
+
how-many-named(looking-for, p1) + how-many-named(looking-for, p2)
end
end
end
```

`how-many-named :: String -> (ABT -> Number)`

`how-many-named`

consumes a name and returns a function that will
consume the actual tree to check.However, this function body is not okay: the Pyret type-checker will give us
type errors. That’s because `how-many-named`

takes one parameter, not two,
as in the two recursive calls.

```
fun how-many-named(looking-for :: String) -> (ABT -> Number):
fun search-in(p :: ABT) -> Number:
cases (ABT) p:
| unknown => 0
| person(n, p1, p2) =>
(if n == looking-for: 1 else: 0 end)
+
search-in(p1) + search-in(p2)
end
end
end
```

`how-many-named`

does not seem to return any kind of value.`search-in`

. Therefore,
`how-many-named`

should just … return `search-in`

.
```
fun how-many-named(looking-for :: String) -> (ABT -> Number):
fun search-in(p :: ABT) -> Number:
cases (ABT) p:
| unknown => 0
| person(n, p1, p2) =>
(if n == looking-for: 1 else: 0 end)
+
search-in(p1) + search-in(p2)
end
end
search-in
end
```

`how-many-named("A")(p) is 3`

`search-in`

), is then applied to the particular tree.#### 23.5` `Context

The transformation we just applied is generally called currying, in honor of Haskell Curry, who was one of the early people to describe it, though it was earlier discovered by Moses Schönfinkel and even earlier by Gottlob Frege. The particular use of currying here, where we move more “static” arguments earlier and more “dynamic” ones later, and split on the static-dynamic divide, is called staging. It’s a very useful programming technique, and furthermore, one that enables some compilers to produce more time-efficient programs.

```
how-many-named :: (String, ABT -> Number)
how-many-named :: (String -> (ABT -> Number))
```

Do Now!

Is the former useful? When might we have the name also changing?

Imagine a slightly different problem: we want to know how often a child has the same name as a parent. Then, as we traverse the tree, as the name of the person (potentially) keeps changing, the name we’re looking for in the parent also changes.

Exercise

Write this function.

In contrast, the staged type rules out that interpretation and that behavior. In that way, it sends a signal to the reader about how the computation might behave just from the type. In the same way, the unstaged type can be read as giving the reader a hint that the behavior could depend on both parameters changing, therefore accommodating a much broader range of behaviors (e.g., checking for parent-child or grandparent-child name reuse).

There’s another very nice example of staging here: A Little Calculus.

Finally, it’s worth knowing that some languages, like Haskell and OCaml, do this transformation automatically. In fact, they don’t even have multiple-parameter functions: what look like multiple arguments are actually a sequence of staged functions. This can, in extremis, lead to a very elegant and powerful programming style. Pyret chose to not do this because, while this is a powerful tool in the hands of advanced programmers, for less experienced programmers, finding out about a mismatch in the number of parameters and arguments is very useful.