5
$\begingroup$

In my answer to the question What are the advantages and disadvantages of making types as a first class value?, I point out that for the language I'm working on, I wanted to have the ability to do runtime checks on the type, because from my experience it is quite limiting/restrictive/cumbersome to only allow compile-time checks on the type, and it is really easy to understand and use type reflection and that sort of stuff (accessing type metadata at runtime, basically).

But as I point out there, for my case I am compiling my lang to JavaScript. If I include the 5000+ built-in types that exist for native JS classes/etc., that is roughly 1.5 megabytes of type metadata that would extremely bloat the output JS build file. So how can I reconcile this problem?

  1. I could not allow type reflection or metadata access at all.
  2. I could omit some type metadata in some cases (like props/fields), where they are never accessed at runtime (would cut out a lot). This would be hard to implement but possible.
  3. Any other solutions you can think of?

The fundamental underlying question is, do you really need type reflection? Can you build programming languages without it, and be able to do all your type checks and implement things in a nice and easy way (with no mentally burdening workarounds, like you often have in Rust as far as I've seen)? The surface level question though is, given I would like some sort of type reflection, or something that accomplishes a similar set of functionality possibilities, what are my options?

I added runtime type checks and the ability to do obj.type.fields.forEach because I want to build validations (like checking if a string matches the email type regex, etc.), and other things like documentation. But for docs (printing the type fields, for example), I guess that would be a different use case where I deal with the compiler-level AST instead of the "runtime AST"? But even then I can imagine a case where you are debugging runtime code, and want to inspect the type metadata/fields, so perhaps there is a "dev build", that would solve that. But maybe there are other cases where you still really need reflection (can't think of any off the top of my head)? Such as building an app which runs code and shows you a log of the objects that pass through it or something (the types, which it would have to access at runtime in order to log)?

Anyway, wondering how I can accomplish the functionality goal of having type reflection, without adding the bloat? I'm not sure if I need to cut out type reflection altogether, in which case I'd like to know how you can handle the cases/needs of dynamic type checking.

$\endgroup$
3
  • 4
    $\begingroup$ Swift just doesn't bother, so a statically-linked Hello World is six megabytes. $\endgroup$
    – Bbrk24
    Jul 6, 2023 at 19:33
  • $\begingroup$ @Bbrk24 Interesting, that's a good insight to keep in mind! Could Swift accomplish what it wants to accomplish without dynamic typechecking then (it sounds like Swift has dynamic type checking, I'm not familiar though), and ultimately cut out all the types from the build? $\endgroup$
    – Lance
    Jul 6, 2023 at 19:47
  • 1
    $\begingroup$ Swift is mostly statically typed, but it has Any. You can query whether an instance of Any adopts a certain protocol, and grab its vtable if it does (or get nil if not). Even without reflection -- which does exist, to a limited extent -- you need type metadata to be able to do that. $\endgroup$
    – Bbrk24
    Jul 6, 2023 at 19:53

3 Answers 3

5
$\begingroup$

You are building a dynamic type system.

Contrary to popular belief, even if we ignore gradually-typed languages, static typing are dynamic typing are by no means mutually exclusive. Many popular statically-typed languages also include a dynamic type system, and these two type systems are integrated at the language level.

In a “purely static” type system, the types are checked at compile-time and erased at runtime. Runtime values are not annotated with their types, they just store data. C is an example of a language with full runtime type erasure. Languages like Haskell and Rust are also fully type erased by default, though they have opt-in mechanisms for limited dynamic typing (Data.Dynamic in Haskell, std::any in Rust).

Other languages use hybrid systems. C++ includes a limited dynamic type system to support dynamic_cast and typeid on all class instances (though this can be disabled using compiler-specific flags). Java includes a very rich dynamic type system, which it uses to implement all of the following features:

  • Runtime type checks via the instanceof operator.

  • Safe, checked downcasting.

  • Runtime class loading and dynamic class compilation.

  • Runtime type reflection APIs.

Note that many of these features are tightly integrated with Java’s static type system, so the dynamic system cannot simply be dispensed with: dynamic type checks are necessary to support downcasting while retaining type soundness. Also note that, despite the richness of Java’s dynamic type system, generics infamously remain type-erased, so they are invisible from the dynamic type system’s perspective. (This is a frequent source of confusion for people learning Java generics.)

If you are building a hybrid system, you have a large design space available to you, and each point in the space comes with its own tradeoffs. An exhaustive discussion would be too detailed for a single answer to cover, but we can take a look at a few examples.

Checked dynamic casts

If your language supports nominal subtyping, and you want to be able to safely support downcasting on all values in your language, some amount of pervasive dynamic information is necessary. There’s just no other way around it.

However, this information can be quite minimal. For each type in the program, generate a global type information table of the following shape:

struct TypeInfo {
  id: TypeId,
  supertypes: [TypeInfo],
}

In many cases, the separate TypeId field can be omitted, and the identity of the TypeInfo structure itself can be used as the TypeId. For a native-like target, this identity would be provided by the structure’s address; for a JS-like target, it could be provided by object identity. The overhead of this information should be quite small, just a few bytes per type and a single pointer per object.

Datatype-generic programming

Datatype-generic programming is a technique used to write functions that operate on values of arbitrary datatypes by somehow representing the type’s structure as a value in the programming language. This can be done at both compile time and at runtime.

C++ template metaprogramming, Haskell typeclass metaprogramming, and Rust trait metaprogramming all provide mechanisms for compile-time datatype-generic programming. A similar but distinct strategy is to use a procedural macro system, as you allude to in your answer. Runtime datatype-generic programming is generally accomplished via runtime type reflection mechanisms. These different approaches have the following pros and cons:

  • Runtime generic programming techniques naturally need to be able to reflectively query the type information of values at runtime, which means that information must be preserved somewhere. This is not necessary with compile-time techniques.

  • Compile-time techniques generate specialized versions of the code for each type they’re applied to, so they can be as fast as their equivalent handwritten functions. Runtime generic programming techniques are generally much slower.

  • On the other hand, the specialized function copies generated by compile-time generic programming techniques can take up a lot of space, while runtime techniques only use a single copy of the function. This makes the choice between these two techniques a classic time–space tradeoff.

  • Runtime generic programming techniques can operate on values even if their precise types are not statically known. This is quite common in object-oriented languages, where values are often subtypes of their statically-declared types. Compile-time approaches cannot easily handle this case.

As you can see, there’s no clearly better or worse approach here, just a set of potential choices.

Opt-in dynamic typing

As mentioned in the first section of this answer, Haskell and Rust both provide opt-in dynamic typing. This allows users to explicitly request that runtime typing information be generated at use sites rather than definition sites. Since this is a demand-driven approach, code that does not need dynamic type information will not need to pay for it.

The trick these languages use leverages Haskell’s typeclasses and Rust’s traits (which are essentially the same thing with two different names). Typeclasses/traits can be viewed as functions from types to terms, so they provide a mechanism to obtain a runtime structure that represents an arbitrary type.

Crucially, this type information is always ultimately resolved statically, and this is true for all uses of typeclasses/traits. However, constraints in type signatures allow the point where the instance is selected to be deferred to function call sites, which allows the type to remain unknown at the point where the trait’s methods are directly used. Since the type must eventually be resolved statically, this approach is insufficient for systems that support subtyping for the same reasons noted in the previous section. However, if you don’t have subtyping, this strategy can work quite nicely.

Utilizing the dynamic type system of the host language

In your question, you note that you’re compiling to JavaScript. But JavaScript already has a dynamic type system! So perhaps you can get away with using its features rather than implementing your own dynamic type system on top.

Whether or not this is sufficient for your needs is, of course, difficult to say. Hybrid static/dynamic type systems usually need a little more structure to be able to connect the dynamic types back to the static types. However, if what you care about is code size, it may be possible to reconstitute a lot of this information at runtime rather than generating it all as code. This is another example of a time–space tradeoff.

$\endgroup$
1
$\begingroup$

In the language I'm working on, you can define a "class" or "type" like this:

form user
  link email, like text
  link name, like text

Say I wanted to make it "insertable" into a SQL database. Then I can do like Rust's diesel crate, where they have:

#[derive(Insertable)]
#[diesel(table_name = posts)]
pub struct NewPost<'a> {
    pub title: &'a str,
    pub body: &'a str,
}

Well I just learned what Rust's derive does, you essentially get the AST for the struct in this case, and handle that (to implement a custom Insertable for the derive procedural macro)! (Diesel's derive(Insertable) starts being implemented here, which goes to insertable#derive, to Model#from_item, FWIW, it's all about parsing that AST for the struct it looks like).

So in a similar fashion, I need basically a way to say "include the AST" in whatever I'm implementing. But you can take it further and say "include the AST in the runtime". So I think I may end up going that route.

The compiler is called "loom", since it weaves things together. So I am adding a special loom term to the definition of key things like the form (type/class), and the function object, or even to a module. By saying loom true you will get the final resultant AST for the object you need. This gives a way to access the AST!

With the AST in hand, we can easily iterate through the fields/props of a type, to do our insertion into the SQL database. It simply iterates through the fields, and creates a SQL insertion string or whatever. So I am thinking defining this might look like this for our form user:

form user
  link email, like text
  link name, like text

  task insert
    # `self` is the `user` instance
    take self, loom true # this adds the AST of `self` to `self`!

    walk self/form/links
      take link

      # for now, just print the prop/field "name" to the terminal
      show <{link/name}>

This would mean, I can omit all 5000+ native JS types' metadata, and only include 1 type AST/metadata, for that of the user type. By adding loom true, the compiler becomes aware that it needs to add the AST of the user type to the output build. I think that'll solve the problem?

If you want the AST for a specific task (function):

task insert
  loom true
  # ...

That would mean you can do insert.takes.forEach basically, to iterate through the inputs even, of the function. I know in JS you can do func.length to get the number of inputs to a function, but you can't further inspect the function. Basically you need to add the function AST to get that extra information.

If you want the AST for a whole module, just add it at the top level:

loom true

Anyway, at first glance this seems like it might solve the problem. Maybe there is another way to solve this problem (of inserting fields dynamically into a DB, without having to be explicit about each one). I'm guessing what Diesel is doing with derive is a lot of code generation, which will result in explicit instructions for each property to do an insert, for example. Doing that in my case would increase the JS output build size, so I want to avoid that. I'd be open to hearing ways of solving this differently if you're open to it!

$\endgroup$
1
$\begingroup$

Another option, if one is designing a language, would be to define a format of memory blob that would contain configurable information about a type, and allow programmers to indicate what information about various types (e.g. struct member names) should be included within those blobs.

This would make it possible for a library to offer "export to JSON" or "import from JSON" functionality that could work with bare in-memory structures, if the functions accepted a pointer to the structure to be processed as well as a pointer to a type-info object describing its layout. Only types whose layout was used for such purposes would need to have information included within the executable.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .