Type erasure and reification

This explanation of continuations obfuscates more than it reveals.

You say that a continuation is a reification of return addresses. But what's reification? Never mind that, what's a return address? It's a return closure that consists of a text address? You mean, text, like, a string, an array of bytes? Oh, uh, no.

And, if you're really trying to explain this to a C programmer: what's a closure? Who are you imagining talking to that already understands what a closure is but doesn't know what a continuation is? Closures are at least as confusing as continuations; arguably more so.

What's "the tail position"? What does it mean to reuse a stack frame? ("This is a key point.") Are they different from function frames?

Who does this explanation serve? Certainly not a JS programmer trying to learn for the first time how to use function* and yield. Not a C programmer.

I think this explanation is for a Scheme programmer playing Ockham's razor to define things in terms of the smallest possible number of other things. This behavior can entertaining, but it's not educational, not explanatory.

You can define arithmetic in terms of set theory, but that's not how we teach arithmetic to children. Similarly, we shouldn't explain continuations in terms of implicit return closures.

Try this: Continuations allow you to pause and resume functions. The paused functions fold up into "continuation" values, which you use to resume the function where it left off.

There is a little nugget here that I've always found illuminating: the mention of the text address and frame pointer, sometimes called the ip-ep pair, short for instruction pointer and the environment pointer.

The environment that a function executes in is important if, as in most interesting languages, there can be any free variables within the body of the function. What is the environment of a running function? Usually, its a collection of variable-name binding frames that determine the value of a programs variables at any point in time. The ep stands for the pointer into the data-structure (e.g. stack and its back links) that determine how variables are attached to values at a particular moment.

Lots of languages use stacks to hold these frames. In dynamic scoping languages, for example some Lisps like Emacs Lisp, a free variable's value is found in the stack frames determined by the run-time order of calls. Most modern languages use static scoping and the frames that determine a function's free variables values are based on the static nesting of functions or modules as they appear in the source code. In either case, a stack is usually where these frames that bind names to values are found. Dynamic vs static scope just changes which frames are searched for the binding of a variable at runtime (optimizations make this faster enough to be practical).

The text address is the reference to the next instruction (symbolic, virtual, or machine level) to be executed in a text segment (or code segment), the part of an object file that holds executable instructions ; I think of it as the IP of assembly language.

These two elements form a pair that in a simplified view represent a program in execution at a specific moment in time. So, this (ip, ep) pair is like a frozen program that can be brought back to life by simply loading two values into the basic execution machinery, the instruction pointer and the environment pointer. They need to be stored somewhere when a function is invoked and reloaded so that the caller is resumed upon return of the called function. When narrowly interpreted as parts of a call stack it's easy to lose sight of the power of the (ip, ep) pair. Part of Scheme's beauty was the expicit embrace of continuations as first class objects that can be flexibly manipulated by a running program and reified to put the program into a previously frozen state and awakened to continue there.

The Borrough's 5700 was designed to support a specific model of computation (Algol 60) and it's hardware description in [1] has pretty diagrams of the interaction of the ip,ep pair and the hardware (although the book is quite dated now).

[1] E. Organick, Computer System Organization: The B5700/B6700 Series, 1973, https://www.amazon.com/Computer-System-Organization-B5700-B6...

The name reification comes from the latin res, thing, so it's the processus that transform something into a thing.

For a language runtime, it's the way to transform a language artifact to a runtime object.

By example, in Java, apart the reification of the type argument, the transformation of a lambda to a proxy that implement the functional interface is also a reification.

I was in a hurry. I forgot to add where the reification comes in! Scheme's call/cc is just taking the current function frame's return address closure and passing it as a function argument to the function given to call/cc -- this is the reification of the current function frame's return address closure.

Regardless of questions of what should or shouldn't be done, there is a serious issue with reifying generic types with type parameters that support subtyping, as the JVM does. It requires deciding on a variance policy (to determine the subtyping relationships among the generic types), and different languages choose different variance policies to fit with their overall design. Reifying generic types in this case would bake a single variance policy into the runtime, which would hinder the ability of different languages to share data structures. If the type parameters do not support subtyping, this is not a problem, and, indeed, when generic types will be instantiated with parameters of Java's upcoming value types (that cannot be subtyped), they will likely be reified and specialized.

> First off, I've seen some people suggest that type erasure is a problem because it leads to a loss of type safety. This isn't really true.

I'd argue it's the opposite.

Giving your programs the ability to access reified types at runtime weaken the robustness of your code, because you can second guess the compiler and introduce crashing code, such as incorrect type casts.

Reification also comes at a cost: performance, more problematic interoperability (Scala could notoriously not be ported to .net because it was not possible to make its type system work properly on a reified platform).

Contrary to popular belief, Java's choice of erasure was not dictated by backward compatibility concerns but because erasure is a sound approach for type system representation.

    import java.util.List;

    class Test {
      public void setListBoolean(List<Boolean> list) {}
      public void setListString(List<String> list) {}

      public List<Boolean> getListBoolean() { return null; }
      public List<String> getListString() { return null; }

      public static void main(String[] args) {}
    }

Haskell implementations typically pass around dictionaries at runtime when you use type classes. Since there is one per instance, this could be thought of as a form of type reification.

https://www.schoolofhaskell.com/user/jfischoff/instances-and...

It's a bunch of small things, none of which are showstopping, all of which are annoying.

You can't have these two functions co-existing in the same class:

  void Frob(List<String> someList) { ... }
  void Frob(List<Integer> someList) { ... }

because, after erasure, they have identical signatures.

You've got to repeat yourself a bunch, because generic methods don't know their own type parameters. So, to take an example using the Jackson JSON-handling library:

  MyClass foo = objectMapper.readValue(json, MyClass.class);

is a bit annoying if you're coming from a language like C#, where you'd expect to be able to write code more like:

  MyClass foo = objectMapper.readValue(json);

Generic type instantiations aren't really types in Java, they're more this sort of type-ish concept. List<String> and List<Integer> exist as distinctions made by Java's type checker, but their actual class is just List - there's no such thing as List<String>.class. That's what's going on with that method overload example above. It's also the reason that this won't even compile, and you've got to resort to hacky workarounds in this sort of situation:

  Node<MyClass> foo = objectMapper.readValue(json, Node<MyClass>.class);

Then there's all the stuff about boxing, and how you can't have generic collections of atomic values, only boxed values. Which is responsible for a lot of excess memory consumption and pointer chasing, and also for things like that whole extra side quest in Java 8 streams where you get classes like IntStream and DoubleStream (but not FloatStream).

    Object xyz = ...;
    if (xyz instanceof List<String>) { doA(); }
    else if (xyz instanceof List<Integer> { doB(); }

  if (xyz instanceof List) {
    if (xyz.isEmpty()) { ... }
    else if (xyz.get(0) instanceof String) { ... }
    else if (xyz.get(0) instanceof Integer) { ... }
  }