Home » forums » LtU Forum

How is structural typing checked?

If a language is decided to have structural type, how are the types checked?

With a nominal type system I can just have a table with the names, and lookup it. However with structural types is necessary to encode more info so I can know how do it.

How are this info encoded? How are the check performed?

By mamcx at 2016-10-15 00:15 | LtU Forum | previous forum topic | next forum topic | other blogs | 5543 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

What's difficult?

For structural types, you carry around a data structure representing the type instead of carrying around a name representing the type.

For type checking or inference, you might also carry around some type variables and a context - a list of (var,type) constraints - for unification. But that really isn't so different from nominative typing.

By dmbarbour at Mon, 2016-10-17 16:18 | login or register to post comments

But that is not carry all

But that is not carry all the type definition?

I mean,

If I have 2 types:


type Customer
fun Save(data:Dict)
fun print():String

type Product
fun Save(data:Dict)
fun print():String

type(cust) == type(prod) #to print true

So, I wonder if is implement to just put in a dict all this:


'print': void -> String
'Save': (Dict, ) -> String

But then I suspect the check become complex, If I put a hash to speed the strict equality still look for the sub-type and super-type will be complicated.

This have a better way to do it?

By mamcx at Wed, 2016-10-19 22:48 | login or register to post comments

re: carry all the type def

Pretty much that, yes. You just carry the entire type definition around as a value.

However, static structural type systems usually won't support a `type(X)` reification, and you usually won't compare types for equality.

A subprogram in a structural type system usually operates only on a slice or subset of a type's features. For example, we have a dictionary with `Save` and `print` AND some other things that we don't care about. We might represent this at our function as an input with with { Save, Print | remainder }. So asking for type(X) == type(Y) doesn't make much sense because we shouldn't locally care whether remainder(X) is the same as remainder(Y).

Subclassing is a separate issue from type substitutability, which is always context dependent.

By dmbarbour at Thu, 2016-10-20 15:10 | login or register to post comments

Ah, ok so instead I must

Ah, ok so instead I must check "Is type(x) included in type(y)"?

Where I can look about sub-classing?

By mamcx at Wed, 2016-10-26 16:44 | login or register to post comments

More specific?

Hello mamcx,

Could you be more specific with regard to what you call "structural typing"? Are you referring to type systems for object-oriented languages? As far as I know, this is the area where the terminology "nominal" (as in Java objects) vs. "structural" (as in OCaml objects) is the most common.

By adrieng at Mon, 2016-10-17 22:15 | login or register to post comments

I'm after the OCalm model.

I'm after the OCalm model.

By mamcx at Wed, 2016-10-19 22:40 | login or register to post comments

Implementation

I am working on a compiler at the moment, which is written in JavaScript. It turns out JavaScript is not such a terrible language to write a compiler in, as it is garbage collected (so code is simpler without worrying about freeing memory), it is dynamically typed (so the abstract-syntax-tree does not need a lot of boilerplate), and prototype methods provide a nice way implementing the Visitor pattern whilst keeping all the code for a compiler pass, or algorithm over the AST or typing tree together. It implements an OCaml like type system, and I have tried to keep the code as simple and readable as possible using a nano-pass architecture and several simplifications of the type system implementation that I have used in other projects. For example there are only two classes of object needed in the type system, type-variables and type-constructors. This simplifies the unification algorithm because it only needs to deal with two cases for each type (so four in total). You can see the source code on GitHub here: https://github.com/keean/zenscript and there are issues discussing the language design and compiler implementation.

By Keean Schupke at Fri, 2016-10-21 07:38 | login or register to post comments

Wild Guess

With a structural typing system you can also have named types but you often unfold their definitions. Which can make it more expensive since testing equivalence of two names (or symbols) is often more expensive than completely substituting definitions and comparing them.

By marco at Tue, 2016-10-18 12:17 | login or register to post comments