In the previous post, I discussed an idea I had for handling dynamic typing in a primarily statically-typed language. In this post, I intend to first, describe the idea a little better, and second, explain what are the problems with it.
The basic idea is:
For example, consider a function signature like:
let f[A, B](arg1: Int, arg2: A, arg3: B, arg4): Bool = ...
This declares a function f with two explicit type parameters A and B, and four regular value parameters arg1 to arg4. arg1 is declared with a concrete Int type. arg2 and arg3 are declared as having types passed in as type parameters. arg4 does not have an explicit type, so in effect it behaves as if the function had an extra type parameter C, and arg4 has type C.
When the function is called, the type arguments don't have to be passed explicitly; rather, they will be automatically provided by the types of the expressions used as arguments. So, if I call f(42, "hello", 1.0, True), the compiler will implicitly pass the types Str and Float for A and B, as well as Bool for the implicit type parameter C.
In the body of f, whenever the parameters with generic types are used, the corresponding type parameters can be consulted at run-time to find the approprate methods to call. For example, if arg2.foo() is called, a lookup for the method foo inside A will happen at run-time. This lookup might fail, in which case we would get an exception.
This all looks quite beautiful.
The problem is when you introduce generic data structures into the picture. Let's consider a generic list type List[T], where T is a type parameter. Now suppose you have a list like [42, "hello", 1.0, True] (which you might have obtained from deserializing a JSON file, for instance). What type can T be? The problem is that, unlike the case for functions, there is one type variable for multiple elements. If all type information must be encoded in the value of the type parameter, there is no way to handle a heterogeneous list like this.
Having a union type here (say, List[Int|Str|Float|Bool]) will not help us, because union types require some way to distinguish which element of the union a given value belongs to, but the premise was for all type information to be carried by the type parameter so you could avoid encoding the type information into the value.
For a different example, consider you want to have a list objects satisfying an interface, e.g., List[JSONSerializable]. Different elements of the list may have different types, and therefore different implementations of the interface, and you would need type information with each individual element to be able to know at run-time where to find the interface implementation for each element.
Could this be worked around? One way would be to have a Dynamic type, whose implementation would be roughly:
record Dynamic(
T: Type,
value: T,
)
The Dynamic type contains a value and its type. Note that the type is not declared as a type parameter of Dynamic: it is a member of Dynamic. The implication is that a value like Dynamic(Int, 5) is not of type Dynamic[Int], but simply Dynamic: there is a single Dynamic type container which can hold values of any type and carries all information about the value's type within itself. (I believe this is an existential type, but I honestly don't know enough type theory to be sure.)
Now our heterogeneous list can simply be a List[Dynamic]. The problem is that to use this list, you have to wrap your values into Dynamic records, and unwrap them to use the values. Could it happen implicitly? I'm not really sure. Suppose you have a List[Dynamic] and you want to pass it to a function expecting a List[Int]. We would like this to work, if we want static and dynamic code to run along seamlessly. But this is not really possible, because the elements of a List[Dynamic] and a List[Int] have different representations. You would have to produce a new list of integers from the original one, unwrapping every element of the original list out of its Dynamic container. The same would happen if you wanted to pass a List[Int] to a function expecting a List[Dynamic].
All of this may be workable, but it is a different experience from regular gradual typing where you expect this sort of mixing and matching of static and dynamic code to just work.
[Addendum (2020-05-31): On the other hand, if I had an ahead-of-time statically-typed compiled programming language that allowed me to toss around types like this, including allowing user-defined records like Dynamic, that would be really cool.]
That's all I have for today, folks. In a future post, I intend to explore how interfaces work in a variety of different languages.
I'm not very well educated in this area, wouldn't the problem with producing a new list List[Int] by unwrapping and checking each element in List[Dynamic] only be a problem if you expect to pass it by reference?
You mentioned problems with union types but what about using a list instead?
So your type is List[Int,Str,Float,Int,Int] (and say your function accepts List[Int..] -- a list of integers) which wouldn't have any larger memory footprint than a Dynamic type and let you pass the list by reference once the types have been checked.
@Bob: Hello! You are right that this is only a problem when passing by reference. I had implicitly assumed that would be the case (since generally you don't want to copy a whole list when passing it as an argument), but if you pass it by copy you could adapt the format while copying, yes.
About using a list instead of a union type, yes! That's essentially the idea I had in the followup post [1]-- took me a couple months to realize that :) The only difference is that there I made a distinction between a Tuple[T1, T2, ...] (heterogeneous sequence of elements) and a List[T] (all elements have the same type), but one could perhaps handle the uniform sequence as a special case of the heterogeneous one.
[1] https://elmord.org/blog/?entry=20200724-type-parameters-dynamic-types-2
@Vítor De Araújo: ah my mistake, I just found your blog and I am scanning through the posts looking for interesting entries; I didn't see your follow up before commenting.
An interesting side-effect, I think, of constructing types out of other data structures like that would be that the type system would reap the benefits that come along from optimising the data structures.
Copyright © 2010-2024 Vítor De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.
Powered by Blognir.
Vítor De Araújo ★, 2020-06-20 14:34:15 +0200 #
[This comment is just a test after migrating to the new server. Nothing to see here.]