8
$\begingroup$

Making them a "first-class value" means that instances of them can be returned from functions, passed into functions, or constructed at runtime, which I'd presume is useful. But, I would also presume that it has somewhat of a performance overhead. So, what are the other advantages and disadvantages of making types as a first class value?

Credit to fess for the similar idea on Area 51.

$\endgroup$
11
  • $\begingroup$ Why a performance overhead? If you don't use the feature in your program then it shouldn't affect your program's performance. If you do then it's not an overhead, just a normal cost. $\endgroup$
    – kaya3
    Jul 5, 2023 at 11:35
  • 1
    $\begingroup$ @kaya3-supportthestrike at least one kind of implied performance overhead would be if the introduction of this feature forces the language to switch from static to dynamic typing. (Although that is not necessarily the case, as the feature could be implemented exclusively in compile-time, like in Zig) $\endgroup$
    – abel1502
    Jul 5, 2023 at 11:38
  • 2
    $\begingroup$ If a program uses first-class types, and first-class types have a performance cost, that performance cost is not unnecessary for that program. $\endgroup$
    – kaya3
    Jul 5, 2023 at 12:41
  • 1
    $\begingroup$ But first class types aren't necessary always @kaya3-supportthestrike $\endgroup$ Jul 5, 2023 at 12:42
  • 2
    $\begingroup$ They are for programs that use them. Programs that don't use them don't have to pay a cost for them. It's only a penalty (or unnecessary cost) if the same thing can be done cheaper, otherwise it is just a cost. $\endgroup$
    – kaya3
    Jul 5, 2023 at 12:55

5 Answers 5

9
$\begingroup$

I think the way in which you represent types as values affects the kind of performance characteristics. Here are a few:

Types as guard predicates

A type is usable as a function that is called to check that a value may be assigned to a cell that the type guards.

Some languages make these equivalent

let guardedCell: SomeTypeExpression = initialValue();

// is equivalent to using temporaries to capture
// the peices and invoking the guard to check the value

let tGuard = SomeTypeExpression;
let tInit = initialValue();
if (!tGuard(tInit)) { panic(); }
let guardedCell = tInit;

Obviously, any dynamic type checking involves runtime overhead because of the function call. Where you statically know the type, and you know that the assigned type is compatible you can erase the guard call.

Typically, when using types as guard functions, you do suffer some performance cost because it limits your ability to do type erasure. For example, to know whether an empty list is a string list or some other kind of list, you need to store the element type with the list.

Also, widespread use of expensive guards that can't be optimized out might make programs slow in practice.

Things can get a tad wacky when instead of just staying "types are value predicates" you also say "value predicates can be put in type place."

JavaScript allows overriding instanceof to arbitrary method calls, so you could have arbitrarily complex guards at runtime like a PrimeNumber guard so if you go the types-as-guards route, it's worth considering how users might be surprised by expensive guards.

// JavaScript
// This is expensive
let PrimeNumber = {
  [Symbol.hasInstance](x) {
    if (!Number.isSafeInteger(x) || x < 0) {
      return false
    }
    console.log(`Pretending to do expensive operation on ${x}`);
    return x === 2 || x === 3 || x === 5 || x === 7;
  }
};
// But people reading the below might think it's cheap.
console.log(
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  .filter((x) => x instanceof PrimeNumber)
);

Types as factory functions

Python treats type expressions as factories. string(my_int) constructs a string from an int and MyClass(*args) allocates memory creates a new instance of the class.

This doesn't carry much of a performance penalty, and Python still gets type introspection via the type and isinstance functions.

Types as reflective facilities

Smalltalk reifies types as meta-classes and Java uses a similar trick with its Class<T> reification of types.

There are many benefits to separating reflection from the values. Mirrors allow limiting or reinterpreting reflection.

Reflection via meta-values often requires storing type information with all values that could be reflected over which can increase the size of values. It also complicates optimizations like erasing boundaries around single property structs (inline types).

Mirror approaches, where the types you want to reflect over is declared, might allow for better managing that overhead than where TopType.doReflectiveStuff can possibly reflect over any type but in practice only affects a few.

$\endgroup$
7
$\begingroup$

DRY and Consistency

You have a list of integers and want to box each into a vector. The simplest way to do it is via a map function:

let xs = [42, 1917, 1921]
    ys = map (λx. [x]) xs
    in
ys = [[42], [1917], [1921]]

Now you have a list of types and want to box each into a vector type. According to the DRY Principle, the code should be the same for there should not exist two different map functions that repeat themselves:

let xs = [Int, String, StateRef Natural1]
    ys = map (λa. Vector a) xs
    in
ys = [Vector Int, Vector String, Vector (StateRef Natural1)]

Now of course, many languages do not do that, and those indeed all violate DRY:

  • They require duplicate semantics for values, types, value functions, and type functions, assuming those semantics actually are similar.
  • They duplicate syntax (f(x) vs F[X] vs F<X> vs F!X).

Each time you write this kind of code:

generic<a, b>
func map(f: a -> b, xs: []a) []b
{
    match xs {
        (x :: ys) -> f x :: map f ys
        [] -> []
    }
}

generic<f: generic<type>, xs: typeseq>
struct MapTypes
{
    static if xs.length = 0 {
        static const result = make_typeseq<>;
    }
    else {
        static const result = make_typeseq<f<xs.head>, MapTypes<f, xs.tail>.result>;
    }
}

the DRY God looks at you with a saddened expression on its face for it is disappointed.

And as noted, some languages even have totally different and unrelated semantics for types and values, to the point of having colanguages incompatible with each other inside of a single one.
C++ is the perfect example of this: C++ actually has full-fledged dynamically-dispatched multimethods! It just is limited to templates accepting types and literal constants. Compared to this, C++ "functions" are second-class citizens.

template<int x>
struct fac
{
    static size_t val = x * fac<(x - 1)>::val;
};
template<>
struct fac<0> //first-class multimethod!
{
    static size_t val = 1;
};

In fact C++ goes further by reinventing boolean logic (std::true_type, std::false_type) and arithmetic (std::integral_constant and friends) in its template colanguage (none of which are related to nor share semantics with bool, int etc... because).
Until first-class and typechecked concepts were introduced, it was also impossible to statically type-check any of this.
Realising this, next time someone asks you what category it falls in, you should smile kindly and say "C++ is a dynamically-typed, interpreted language."

$\endgroup$
5
$\begingroup$

Simple syntax for generics / template / comptime

Having types as first class language construct permits a generic/templating syntax where generic parameters are common arguments:

def List( T type )
{ }

var listCodes = new List( int );
var listNames = new List( str );

Avoid (a lot) of reflection

Types then can have properties and methods, and so facilitate a lot of reflexive computation:

def List( T type , capacity T )
{ }

var list32 = new List( u32 , u32.MaxValue );
var list64 = new List( u64 );

Types returning types

Say, you want specialized variations of your types. Things like machine fast integers, floating point numbers that set flags instead of generating errors/NaNs, optionals, Either<T,Error>. These specialized types are very detailed but very expensive to write in normal use.

But with first class types, these specializations can be write in very concise form:

def AddFast( u32.fast a , u32.fast b ) as u32.fast  { ... }
def Div( u32 a , u32 b ) as u32.flags { ... } // nothrow
def ParseJson() as JsonNode.opt  { ... } // nothrow

Source only first class types

Some languages have full instantiable types that require a bigger runtime and incur in some performance overhead (C#, Java). but is possible to have the same comfort with types existing only for templating or comptime evaluation (Zig, C++).

$\endgroup$
3
$\begingroup$

Being able to use types as run-time values enables some dynamic constructs, but the extension beyond static generic type parameters is not large. Being able to use dynamic values as types expands the world of what you can have types express, enforce, and do significantly. These are the most interesting extensions.

First-Class Dynamic Types in the 2019 DLS was an exploration of this. We took a language with an existing dynamic pattern-matching system and allowed those patterns to be used as types: anywhere that a type annotation could be written, a pattern expression could be written instead. Whenever a value passed through one of these annotations the pattern would be applied, and a match failure would be a run-time type error. The ordinary types of the language produced patterns matching values of that type, so those slotted in as equals with the first-class types.

Just this addition enabled a number of case studies (given in more detail in Section 4 of the paper). In brief, they were:

  • Structural type checking using reflection: this can be implemented entirely in user code, whether it matches the language's native type system or not
  • Nominal type checking using object brands
  • Range or restricted subtypes:
    class RangeType(min, max) {
        method match(obj) {
            def int = obj.asInteger
            if ((int < min) || (int > max)) {
                return failedMatch(obj)
            }
            successfulMatch(int)
        }
    }
    type Byte = Range(0, 255)
    method printByte(b : Byte) { ... }
    
    These can abstract arbitrarily-complex validation logic out into reusable pieces, with syntactic support from the type annotations.
  • Argument-dependent patterns: matching happened in order left-to-right, so method getItem(list, index : be >= 0 & be <= list.size) worked with a careful be object with suitable operator overloads.
  • Higher-order dependent types: for example, a library could define a Matrix type, and a method could define its input and output validation with enforced types
    class myMatrix {
        method *(other : Matrix(self.width, Number)) -> Matrix(self.height, other.width) { ... }
    }
    
  • Coercion and clamping: as patterns had not just a success or failure, but an enclosed value, types could also coerce their input values into range. This is... not obviously a good thing, but there are cases you might want to opt in explictly to var x : Stringify or rating : Clamped(0, 10).
  • Decorators on other types: these are in part the "constructed at run time" side of things, where a wrapper could enforce additional constraints on top of another first-class type simply by implementing a suitable match method on the object, or (to some extent) relax those constraints.
  • General pre- and post-conditions asserted as types: the dynamic assertion could be determined by information outside or even unrelated to the scrutinee value, only leveraging the enforcement point. This is not particularly desirable on the language-design level, where you would probably just include those as a feature.

It's a working system and you can actually try it if you like, including (very slowly) in your browser, including small examples of several of these case studies. Any arbitrary computable property can be used as the basis of a type, not just the ones listed.

There are associated costs with all of this, including whatever the direct costs of the dynamic tests in use are but also second-order effects from losing the firm constraints on shape and type that static types, or ordinary types enforced dynamically, provide to the run-time system.

There's also a choice to make about just when to bind these type expressions. Our system used very late binding, evaluating the expressions fresh each time, enabling some extremely dynamic behaviour. Another is to evaluate them early, at object construction time, and cache the resulting types: this provides more consistency, but less dynamicity. If you want static checking to exist alongside, extreme dynamism may not be what you want, but there are some tradeoffs to consider.

Racket's run-time contracts system permits dynamic user-defined checking, including the sort of dynamic value replacement used in some of the examples above. These are strictly more powerful because of higher-order contracts, impersonators, and contract defining forms, and you might not consider all of them to be "types", but all of these things exist on a continuum. These are described in Takikawa et al. Gradual Typing for First-class Classes, OOPSLA 2012. A number of functional languages support some of this range of run-time checks, using first-class function values for types without their necessarily being "first class" values in their capacity as types.


First-Class Dynamic Types. Michael Homer, Timothy Jones, James Noble. Dynamic Language Symposium (DLS), 2019. https://doi.org/10.1145/3359619.3359740

Gradual Typing for First-class Classes. Asumu Takikawa, T. Stephen Strickland, Christos Dimoulas, Sam Tobin-Hochstadt, and Matthias Felleisen. OOPSLA, 2012. https://doi.org/10.1145/2398857.2384674

$\endgroup$
2
$\begingroup$

I am no expert in the theory of programming languages, but I have been working on a programming language for many years, and have always wanted these features:

  • Ability to do reflection (get the type of an object)
  • Iterate the "properties/columns/fields" of a type (if it's a so-called "record type"). This is useful for documentation (you take the AST basically of the type and can iterate the props, etc.). It is also interesting to just inspect the type properties for doing validation and other things at runtime. More reflection-oriented stuff.

So I went about designing the language with the idea that you could do:

obj.type.fields.forEach(field => log(field.name))

if (obj.type.name == 'user') log('is user')
// or better
if (obj.type == UserType) log('is user')

and stuff like that. That would make programming so much easier IMO.

But you could also use the "types" at compile time, to do typechecking and other things.

The problem I am currently facing with this approach is based on the fact that I am compiling my language to JavaScript (for the browser). There are over 1000 types (more like 5000 types) defined for the browser / JS, some with dozens of properties. Lets say each type is 300 bytes of code, that is 1.5 megabytes or so of just types! If I allowed obj.type.fields.forEach on any possible object, that would mean I have to include this 1.5mb of mostly useless code from a programming perspective, into the final build JS file. That is way over the ideal size limit of about 100kb, in this case like 15x the appropriate size. Of course you could minify and gzip, but the point is clear, it adds a lot of text to the final build.

So now I'm facing a dilemma (which I'd love to hear solutions for as well in the comments, if you have any suggestions, or maybe someday I'll ask a related question). The dilemma is, do I have to go back and cut this feature out, and rethink a tone of core functionality. Or can I somehow include only a subset of the type definitions in the final build? By that I mean, if the .fields is never accessed, but .type.name is, then perhaps I can omit the fields from the build, but include just the type names. I have a feeling other languages face a similar challenge in some sense, but I'm not sure how they handle it.

Anyway, just wanted to answer that there is this problem if you make your types first-class values. Types add a not insignificant amount of code to your codebase, and having to include that in any final build might be problematic like I've shown. But perhaps there are workarounds?

$\endgroup$

You must log in to answer this question.

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