Generic Types

Well, that kinda sucked.

Even though implementing Sum Types was a bit painful, it was really rewarding to get things working. From that success, I moved on to implementing basic generic types. It involved a bit of work, but was pretty straight-forward once I figured out what I wanted. Previously, type declarations were pretty simple:

(identifier)+ :> (type-definition)

Product types added a new type definition, and sum types let them be composed, but the general syntax stayed the same. The design I ended up on looks very similar to the function syntax:

(identifier|parameter-decl)+ :> (type-definition)

Instead of being a simple name, a type can also have parameters. That is what a generic is after all, right? The type-definition would then have access to the parameter and could make references to it. The parameter's type would be a kind - essentially a type of a type, or in C# parlance, the constraint of the generic parameter.* The awesome thing then is that the right side is effectively the constructor for this type, so any generic references could be used to allow type inference in constructors. Haven't you always wanted that? Yes, it seems many of you did.

Presumably many of you have been humans for more than a few years, so you know that this is the point in the story where it comes crashing down. First, I ran into the issue of how to parse the generic parameters and then make them available to the rest of the declaration when the original code didn't know or care about such things. Scope is always the thing that takes more work then expected. Also note that I started off working on generic types, not any sort of generic inference in constructors. Once my parser said it couldn't figure out how to deal with things, I realized that the design required me to do at least some basic inference. Okay, whatever. Inference is tedious but I'd done it before and it's pretty straight-forward once you view it as a pattern matching exercise.

But then I ran into the big problem. Here is my test code for the feature:

Nothing :> enum { null }
(T)? :> T | Nothing;
do(x: int?) => void { 
  print "fn."; 
} 

entrypoint => void { 
  do 42; 
  do null; 
}

A stupid little program that verifies that C#-like nullable types can be done. I don't particularly care if the value is real or null, and I don't really care what the output is. All I want is int? to parse properly, and do to take an int and null and execute.

The big problem here is a little subtle - remember that the right side of a type declaration is the constructor of the type, and I use type inference to figure out what type to build from it. When the constructor sees null, what is T?

Since the parser works akin to a normal shift-reduce parser, I don't have any sort of context. null doesn't know that I'm trying to pass it into an int?, all it knows is that it is a Nothing and needs to reduce if possible. There is no way for it to know/guess T. So that sucks. What really sucks is that it took me all that time and effort to realize that T (anything) or Nothing (something) is just anything again.

About 2 weeks of brooding and thinking of things that didn't work led me to a good enough compromise. I already have dynamic dispatch on functions (see ADTs), so I can flip it around. Instead of having Nothing build T? and call do, I would generate do(T) and do(Nothing). Then when I have a clear Nothing, it can call the function directly without any inference. That though leads to Tangent's first "Really Weird Thing It Won't Allow For Arcane Reasons": you cannot declare a function that takes a generic Sum Type and uses a generic parameter of that type in its return type and that generic parameter isn't used in all of the alternatives of the sum type. The compiler will give you an error about the offending function and generic parameter, and fail. This seems like a tiny limitation, and lets stuff like the example above work.

An annoying, twisty, frustrating road - but now functional.


* - yes, I am aware that kinds in other languages do not refer to this sort of thing.