►A Data-Centric Introduction to Computing
▼III Foundations:   Bonus Materials
    contents  ← prev  up  next → 

19 Staging

Let’s consider a generic binary tree representing people: 

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

We have seen functions over binary trees such as this: 

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!

Here is one meaningful contract: 

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

It takes a tree in which to search, a name to search for, and returns a count.

Do Now!

Define how-many-named.

Presumably you ended up with something like this: 

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

Let’s say you have defined this person: 

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

With that, we can write a test like 

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

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

First, notice the repeated expression. What the whole conditional is essentially saying is that we want to know how much this person is contributing to the overall count; the rest of the count stays the same regardless. We can therefore write this more concisely (and, if we know how to read such code, more meaningfully) as the following instead: 

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 you have prior programming experience, this may look a bit odd to you, but 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?

First, we’ll do something that looks a little useless, but it’s also an innocent change, so it shouldn’t irk us too much: we’ll change the order of the arguments. 

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

What we have now done is put the “constant” argument first, and the “varying” argument second. That is, our contract has changed from 

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

to 

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

so the way we call it also has to change: 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.

We achieve this by breaking up the parameter list: 

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

Thus, the contract has become 

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

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

How do we fix this? Remember, the whole point of this change is we don’t want to change the name, only the tree. That means we want to recur on the inner function. We currently can’t do this because it doesn’t have a name! So we have to give it a name: 

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

This now lets us recur on just the part that should vary, leaving the name we’re looking for unchanged (and hence, fixed for the duration of the search). However, the above body has a syntax error, because how-many-named does not seem to return any kind of value.

What should it return? Once we provide the function with a name, we should get back a function that searches for that name in a tree. But we already have exactly such a function: 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

And we’re set! We would call this function as 

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

The outer function application returns a function value (bound to 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.

Even more subtly but importantly, the staged computation tells a different story than the unstaged one, and we can read this off just from the contract: 

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

The first one says the string could co-vary with the person. The second one rules out that interpretation.

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.

    contents  ← prev  up  next →