# dfs

Published articles for dfs.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## two mechanisms for dynamic type checks

DevFeed: [two mechanisms for dynamic type checks](<https://devfeed.tech/articles/two-mechanisms-for-dynamic-type-checks-35030.md>)

Original publisher: [Read original article](<https://wingolog.org/archives/2026/02/18/two-mechanisms-for-dynamic-type-checks>)

Author: Andy Wingo

Published: 2026-02-18T16:21:10Z

Content type: tutorial

Language: en

Sources: [wingolog](<https://devfeed.tech/sources/wingolog.md>)

Topics: [virtual machines](<https://devfeed.tech/topics/virtual-machines.md>), [Inheritance](<https://devfeed.tech/topics/inheritance.md>), [WebAssembly](<https://devfeed.tech/topics/web-assembly.md>), [JIT](<https://devfeed.tech/topics/jit.md>), [Polymorphism](<https://devfeed.tech/topics/polymorphism.md>)

Tags: [cardelli](<https://devfeed.tech/tags/cardelli.md>), [cohen](<https://devfeed.tech/tags/cohen.md>), [dfs](<https://devfeed.tech/tags/dfs.md>), [display-hack](<https://devfeed.tech/tags/display-hack.md>), [dybvig](<https://devfeed.tech/tags/dybvig.md>), [scheme](<https://devfeed.tech/tags/scheme.md>), [vitek](<https://devfeed.tech/tags/vitek.md>), [wasm](<https://devfeed.tech/tags/wasm.md>), [webassembly](<https://devfeed.tech/tags/webassembly.md>)

### AI overview

This technical note explains two mechanisms for dynamic instance type checks in virtual machines with single inheritance. It describes DFS numbering when the type set is fixed and the display hack, based on per-type supertype arrays, when types can be added at run time.

### Source excerpt

Today, a very quick note on dynamic instance type checks in virtual machines with single inheritance. The problem is that given an object o whose type is t, you want to check if o actually is of some more specific type u. To my knowledge, there are two sensible ways to implement these type checks. if the set of types is fixed: dfs numbering Consider a set of types T := {t, u, ...} and a set of edges S := {<t|ε, u>, ...} indicating that t is the direct supertype of u, or ε if u is a top type. S should not contain cycles and is thus a direct acyclic graph rooted at ε. First, compute a pre-order and post-order numbering for each t in the graph by doing a depth-first search over S from ε. Something like this: def visit(t, counter): t.pre_order = counter counter = counter + 1 for u in S[t]: counter = visit(u, counter) t.post_order = counter return counter Then at run-time, when making an object of type t, you arrange to store the type's pre-order number (its tag) in the object itself. To test if the object is of type u, you extract the tag from the object and check if tag-u.pre_order mod 2n < u.post_order-u.pre_order. Two notes, probably obvious but anyway: one, you know the numbering for u at compile-time and so can embed those variables as immediates. Also, if the type has no subtypes, it can be a simple equality check. Note that this approach applies only if the set of types T is fixed. This is the case when statically compiling a WebAssembly module in a system that doesn't allow modules to be instantiated at run-time, like Wastrel. Interestingly, it can also be the case in JIT compilers, when modeling types inside the optimizer. if the set of types is unbounded: the display hack If types may be added to a system at run-time, maintaining a sorted set of type tags may be too much to ask. In that case, the standard solution is something I learned of as the display hack, but whose name is apparently ungooglable. It is described in a 4-page technical note by Norman H. Coh