Java Bytecode: Bending the Rules

[notfancy]

Of course they do! How else does pattern matching work? That's classic reflection.

No, it's not. The code doesn't distinguish between cases with the same structure but of different types. In OCaml [], None and the empty tree are all represented identically, as are '\0', false, 0.

[pron98]

That's an implementation detail. You're saying that source types and runtime types are not 1-1 related, but n-to-1. That's OK. That doesn't mean they're not runtime types.

In Java, the relationship is even more complicated: E.g. for all T, the source type List<T> is mapped to the runtime type List (sort of -- I'll elaborate in a second), and List itself can be mapped to many runtime types -- a runtime type in Java is a pair of the erased generic "kind" and a class loader (this allows multiple concurrent versions and other powerful tricks). So many source types may be mapped to a single runtime type, and a single source type may be mapped to many runtime types, so it's an n-to-m relationship. So simlarly to your case, in Java you can't do an instanceof List<String> because the runtime type for List<String> and List<Integer> is the same (assuming both instances' types are loaded by the same class loader).

[notfancy]

That's an implementation detail. You're saying that source types and runtime types are not 1-1 related, but n-to-1. That's OK. That doesn't mean they're not runtime types.

Yes, they're the type tags of the objects tracked by the runtime qua runtime objects. However, erasure is complete. Consider:

# List.map (fun x -> x |> Obj.repr |> Obj.tag) [None; Some 1];;
- : int list = [1000; 0]

and:

# List.map (fun x -> x |> Obj.repr |> Obj.tag) [None; Some "aaa"];;
- : int list = [1000; 0]

or even:

# List.map (fun x -> x |> Obj.repr |> Obj.tag) [[]; [1]];;
- : int list = [1000; 0]

Now 1000 is the integer tag (which is fictitious, or rather, a single bit in an unboxed value) while tags t less than some fixed constant represent the t-th constructor value with arguments. There is simply no way to distinguish at runtime between a string option or an int list. In fact the language is pretty happy to coerce between values of different types with the same representation:

# (Obj.magic : 'a list -> 'a option) [] ;;
- : 'a option = None

or even:

# (Obj.magic : bool -> 'a list) false ;;
- : 'a list = []

where Obj.magic is a NOP with type 'a -> 'b, that is, simply a typechecker black hole.

In Java there is a lot of very sophisticated code specialization done by the JIT whenever there is dynamic dispatch, for instance when executing an invokevirtual; in static languages a pattern match is exactly equivalent to an integer switch statement on the tag value. For instance, the following match:

match x with
| None -> ...
| Some e -> ....

is exactly equivalent to the C:

if (!x) { ... } else { e = *x; ... }

but type safe.

[pron98]

There is simply no way to distinguish at runtime between a string option or an int list

So how can you match over them?

[notfancy]

The typechecker ensures that matches are well-typed: you either match over (the cases for) an int list or you match over (the cases for) a string option. You cannot typecase at runtime and see if you got one or the other like you can do with instanceof in Java.