### 19` `Staging

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

```
fun abt-size(p :: ABT):
cases (ABT) p:
| unknown => 0
| a-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. (By now we know
that more than one person can have the same name. In fact, in many 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`

.

```
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
```

```
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.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.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.