3 ms·
I'm working on a type-inferencer for the Joy language (purely functional, stack-based, concatinative) and I wanted to be able to specify a kind of Kleene star t
by carapace 8y ago
I'm working on a type-inferencer for the Joy language (purely functional, stack-based, concatinative) and I wanted to be able to specify a kind of Kleene star type variable that can stand for zero or more of some other type. I realized I could use Brzozowski's derivative of the K-star at the right place in the unification algorithm. You "split the universe" into two and in one the K-star variable disappears and in the other it "spawns" a new type variable of it's, uh, "starred type". In both cases unification proceeds as normal. It seems to work fine.
The fact that you can splice the Kleene star part of the dRE algorithm into the unification algorithm suggests that you should be able to do the same with the other parts of it and be able to specify union types and intersection types. I'm kinda out of my league I think, and a lot of the papers that seems relevant are behind paywalls.