On this page:
24.1 Changing Representations
24.2 Errors
24.3 Changing Meaning
24.4 Representing the Environment

24 Representation Decisions

    24.1 Changing Representations

    24.2 Errors

    24.3 Changing Meaning

    24.4 Representing the Environment

Go back and look again at our interpreter for function as values (Functions Anywhere). Do you see something curiously non-uniform about it?

Do Now!

No, really, do. Do you?

Consider how we chose to represent our two different kinds of values: numbers and functions. Ignoring the superficial numV and closV wrappers, focus on the underlying data representations. We represented the interpreted language’s numbers as Pyret numbers, but we did not represent the interpreted language’s functions (closures) as Pyret functions (closures).

That’s our non-uniformity. It would have been more uniform to use Pyret’s representations for both, or also to not use Pyret’s representation for either. So why did we make this particular choice?

We were trying to illustrate and point, and that point is what we will explore right now.

24.1 Changing Representations

For a moment, let’s explore numbers. Pyret’s numbers make a good target for reuse because we get arbitrary-sized integers (bignums), rationals (which benefit from the bignum representation of integers), and so on. Therefore, they can represent most ordinary programming language number systems. However, that doesn’t mean they are what we want: they could be too little or too much.
  • They are too much if what we want is a more restricted number system. For instance, Java prescribes a very specific set of fixed-size representations (e.g., int is specified to be 32-bit). Numbers that fall outside these sets cannot be directly represented as numbers, and arithmetic must respect these sets (e.g., overflowing so that adding 1 to 2147483647 does not produce 2147483648).

  • They are too little if we want even richer numbers, whether quaternions or numbers with associated probabilities.

Worse, we didn’t even stop and ask what we wanted, but blithely proceeded with Pyret numbers.

The reason we did so is because we weren’t really interested in the study of numbers; rather, we were interested in programming language features such as functions-as-values. As language designers, however, you should be sure to ask these hard questions up front.

Now let’s talk about our representation of closures. We could have instead represented closures by exploiting Pyret’s corresponding concept, and correspondingly, function application with unvarnished Pyret application.

Do Now!

Replace the closure data structure with Pyret functions representing functions-as-values.

Here we go:
<hof-interp-closure-rep> ::=

    data Value:

      | numV (n :: Number)

      | closV (f :: (Value -> Value))

    end

    

    fun interp(e :: ExprC, nv :: List<Binding>) -> Value:

      cases (ExprC) e:

        | numC(n) => numV(n)

        | plusC(l, r) => plus-v(interp(l, nv), interp(r, nv))

        | multC(l, r) => mult-v(interp(l, nv), interp(r, nv))

        | idC(s) => lookup(s, nv)

        | fdC(a, b) =>

          closV(fun (arg-val):

              interp(b, xtnd-env(bind(a, arg-val), nv));)

        | appC(f, a) =>

          clos = interp(f, nv)

          arg-val = interp(a, nv)

          clos.f(arg-val)

      end

    end

Exercise

Observe a curious shift. In our previous implementation, the environment was extended in the appC case. Here, it’s extended in the fdC case. Is one of these incorrect? If not, why did this change occur?

This is certainly concise, but we’ve lost something very important: understanding. Saying that a source language function corresponds to a Pyret function-as-a-value tells us virtually nothing: if we already knew precisely what a Pyret functional value does we might not be studying it, and if we didn’t, this mapping would teach us absolutely nothing (and might, in fact, pile confusion on top of our ignorance). For the same reason, we did not use Pyret’s state to understand the varieties of stateful operators (Mutation: Structures and Variables).

Once we’ve understood the feature, however, we should feel to use it as a representation. Indeed, doing so might yield much more concise interpreters because we aren’t doing everything manually. In fact, some later interpreters [REF] will become virtually unreadable if we did not exploit these richer representations.It’s a little like saying, “Now that we understand addition in terms of increment-by-one, we can use addition to define multiplication: we don’t have to use only increment-by-one to define it.” Nevertheless, exploiting host language features has perils that we should safeguard against.

24.2 Errors

When programs go wrong, programmers need a careful presentation of errors. Using host language features runs the risk that users will see host language errors, which they will not understand. Therefore, we have to carefully translate error conditions into terms that the user of our language will understand, without letting the host language “leak through”.

Worse, programs that should error might not! For instance, suppose we decide that functions should only appear in top-level positions. If we fail to expressly check for this, desugaring into the more permissive Pyret functional value may result in an interpreter that produces answers where it should have halted with an error. Therefore, we have to take great care to permit only the intended surface language to be mapped to the host language.

As another example, consider the different mutation operations. In our language, attempting to mutate an unbound variable produces an error. In some languages, doing so results in the variable being defined. Failing to pin down our intended semantics is a common language designer error, saying instead, “It is whatever the implementation does”. This attitude (a) is lazy and sloppy, (b) may yield unexpected and negative consequences, and (c) makes it hard for you to move your language from one implementation platform to another. Don’t ever make this mistake!

24.3 Changing Meaning

Mapping functions-as-values to Pyret functions works especially because we intend for the two to have the same meaning. However, this makes it difficult to change the meaning of what a function does. Lemme give ya’ a hypothetic: suppose we wanted our language to implement dynamic scope.Don’t let this go past the hypothetical stage, please. In our original interpreter, this was easy (almost too easy, as history shows). But try to make the modified interpreter (<hof-interp-closure-rep>) implement dynamic scope. It can similarly be difficult or at least subtle to map eager evaluation onto a language with lazy application [REF].

Exercise

Convert the above interpreter to use dynamic scope.

The point is that the raw data structure representation does not make anything especially easy, but it usually doesn’t get in the way, either. In contrast, mapping to host language features can make some intents—mainly, those match what the host language already does!—especially easy, and others subtle or difficult. There is the added danger that we may not be certain of what the host language’s feature does (e.g., does its higher-order function actually implement static scope?).

The moral is that this is a good property to exploit only we want to “pass through” the base language’s meaning—and then it is especially wise because it ensures that we don’t accidentally change its meaning. If, however, we want to exploit a significant part of the base language and only augment its meaning, perhaps other implementation strategies [REF] will work just as well instead of writing an interpreter.

24.4 Representing the Environment

Let’s consider one more representation change. What is an environment?

An environment is a map from names to values (or locations, once we have mutation). We’ve chosen to implement the mapping through a data structure, but...do we have another way to represent maps? As functions, of course! An environment, then, is a function that takes a name as an argument and return its bound value (or an error):

# Env = (String -> Value)

What is the empty environment? It’s the one that returns an error no matter what name you try to look up:

fun mt-env(s :: String) -> Value:

  raise("unbound identifier: " + s)

end

Extending an environment with a binding creates a function that takes a name and checks whether it is the name just extended; if so it returns the corresponding value, otherwise it punts to the environment being extended:

fun xtnd-env(b :: Binding, rest :: (String -> Value)) -> (String -> Value):

  fun(s :: String) -> Value:

    if s == b.name: b.value

    else: rest(s);

  end

end

Finally, how do we look up a name in an environment? We simply apply the environment!

fun lookup(s :: String, nv :: (String -> Value)) -> Value:

  nv(s)

end

And with a little adjusting for the type of interp, we’re done!