Finally, I got this to work. First, I'll go over specifications of polymorphic type systems needed for the specpification of extensible records. Then, I'll try to explain the specification of a type system supporting extensible records based on row poplymorphism. All the examples in this article are aviailible on an online IDE (follow the links on the TIPER hompage) along with the slides for the invited talk at CoALP-Ty '16.

Review on Polymorphic Type Systems

I wrote about this in my blog article and it is also a published paper in FLOPS 2016. So, I won't go into detailed explnanations but just list the Prolog specifications of STLC, HM, and type-constructor polymorphism. We need at least the flexibility of type-constructor polymorphism in the type system to support row polymorphism because row variables need to be categorized by a separate kind other than the kind for types.

Let's start from STLC:

:- set_prolog_flag(occurs_check,true).
:- op(500,xfy,$).

type(C,var(X),     A) :- first(X:A,C).
type(C,lam(X,E),A->B) :- type([X:A|C], E,  B).
type(C,E1 $ E2,    B) :- type(C,E1,A->B), type(C,E2,A).
first(K:V,[K1:V1|_]) :- K = K1, V = V1.
first(K:V,[K1:_|Xs]) :- K\==K1, first(K:V, Xs).

Then, HM:

:- set_prolog_flag(occurs_check,true).
:- op(500,yfx,$).

type(C,var(X),     A) :- first(X:S,C), inst_ty(S,A).
type(C,lam(X,E),A->B) :- type([X:mono(A)|C],E,B).
type(C,E1 $ E2,    B) :- type(C,E1,A->B), type(KC,C,E2,A).
type(C,let(X=E0,E),T) :- type(C,E0,A), type([X:poly(C,A)|C],E,T).

inst_ty(poly(C,T),T1) :- copy_term(t(C,T),t(C,T1)).
inst_ty(mono(T),   T).

first(K:V,[K1:V1|_]) :- K = K1, V = V1.
first(K:V,[K1:_|Zs]) :- K\==K1, first(K:V, Zs).

Then, HM + Type Constructor Polymorphism:

:- set_prolog_flag(occurs_check,true).
:- op(500,yfx,$).
kind(KC,var(Z), K) :- first(Z:K,KC).
kind(KC,F $ G, K2) :- kind(KC,F,K1->K2), kind(KC,G,K1).
kind(KC,A -> B, o) :- kind(KC,A,o), kind(KC,B,o).
type(KC,C,var(X),     A) --> { first(X:S,C) }, inst_ty(KC,S,A).
type(KC,C,lam(X,E),A->B) --> type(KC,[X:mono(A)|C],E,B),
                             [ kind(KC,A->B,o) ].
type(KC,C,E1 $ E2,    B) --> type(KC,C,E1,A->B), type(KC,C,E2,A).
type(KC,C,let(X=E0,E),T) --> type(KC,C,E0,A),
inst_ty(KC,poly(C,T),T2) --> { copy_term(t(C,T),t(C,T1)),
                                     free_variables(T1,Xs1) },
                             samekinds(KC,Xs,Xs1), { T1=T2 }.
inst_ty(_, mono(T),   T) --> [].
samekinds(KC,[X|Xs],[Y|Ys]) --> { X\==Y },
                                [ kind(KC,X,K), kind(KC,Y,K) ],
samekinds(KC,[X|Xs],[X|Ys]) --> [], samekinds(KC,Xs,Ys).
samekinds(_ ,[],    []    ) --> [].

first(K:V,[K1:V1|_]) :- K = K1, V = V1.
first(K:V,[K1:_|Zs]) :- K\==K1, first(K:V, Zs).
variablize(var(X)) :- gensym(t,X).

What's going on there is that we do type and kind inference in two stages, where kinds are either o or K1 -> K2 where both K1 and K2 are kinds. Becase there are type constructor variables with different kinds, we need to make sure that all types are 'well-kinded' by satisfying the kind predicate just as we are making sure that all terms are 'well-typed' by the typed predidate. Firist, we do type inference and collect all queries (or constraints) for the kind inference as an yet uninterpreed list, which is using Definite Clause Grammars (DCGs). The type predicate is defined as a DCG. One can use phrase predicate to invoking queries of DCGs. Then, we run the kind predicates generated by the DCG query over type predicate. For example, we can use the code above as follows:


type_and_print(KC,C,E,T) :-
  phrase(type(KC,C,E,T),Gs), print(success_type), nl,
  (bagof(Ty, X^Y^member(kind(X,Ty,Y),Gs), Tys); Tys = []),
  free_variables(Tys,Xs), maplist(variablize,Xs),
  write("kind ctx instantiated as: "), print(KC), nl, print(E : T), nl.
    /* your code goes here */
    type_and_print(_,[],lam(x,var(x)),_), nl,
    type_and_print(_,[],lam(x,lam(y,var(y)$var(x))),_), nl,
    type_and_print(_,[],let(id=lam(x,var(x)),var(id)$var(id)),_), nl,
    KC0 = [ 'Nat':o, 'List':(o->o) | _ ],
    Nat = var('Nat'), List = var('List'),
    C0 =     [ 'Zero':mono(Nat)
        , 'Succ':mono(Nat -> Nat)
        , 'Nil' :poly([], List$A)
        , 'Cons':poly([], A->((List$A)->(List$A))) ],

:- main.

On top of this we can also easily add kind polymorphism (it is basically HM at the type level) as in our previous work (FLOPS 2016), but for row polymorphism, this is enough. Kind polymorphism is not needed for row polymorphism.

Extensible Records based on Row Polymorphism

Here is how we extend HM + tycon poly with row polymorphism for extensible records:

:- set_prolog_flag(occurs_check,true).
:- op(500,yfx,$).

kind(KC,var(X),   K1) :- first(X:K,KC).
kind(KC,F $ G,    K2) :- K2\==row, kind(KC,F,K1->K2),
                         K1\==row, kind(KC,G,K1).
kind(KC,A -> B,    o) :- kind(KC,A,o), kind(KC,B,o).
kind(KC,{R},       o) :- kind(KC,R,row).
kind(KC,[],      row).
kind(KC,[X:T|R], row) :- kind(KC,T,o), kind(KC,R,row).

type(KC,C,var(X),     A) --> { first(X:S,C) }, inst_ty(KC,S,A).
type(KC,C,lam(X,E),A->B) --> type(KC,[X:mono(A)|C],E,B),
                             [ kind(KC,A->B,o) ].
type(KC,C,X $ Y,      B) --> type(KC,C,X,A->B), type(KC,C,Y,A1),
                             !, { eqty(A,A1) }. % note the cut !
type(KC,C,let(X=E0,E),T) --> type(KC,C,E0,A),
type(KC,C,{XEs},    {R}) --> { zip_with('=',Xs,Es,XEs) },
                             { zip_with(':',Xs,Ts,R) }.
type(KC,C,sel(L,X),   T) --> { first(X:T,R) }, type(KC,C,L,{R}).

first(K:V,[K1:V1|Xs]) :- K = K1, V=V1.
first(K:V,[K1:V1|Xs]) :- K\==K1, first(K:V, Xs).

inst_ty(KC,poly(C,T),T2) --> { copy_term(t(C,T),t(C,T1)), 
                               free_variables(T1,Xs1) },
                             samekinds(KC,Xs,Xs1), { T1=T2 }.
inst_ty(KC,mono(T),   T) --> [].

samekinds(KC,[],    []    ) --> [].
samekinds(KC,[X|Xs],[Y|Ys]) --> { X\==Y },
                                [ kind(KC,X,K), kind(KC,Y,K) ],
samekinds(KC,[X|Xs],[X|Ys]) --> [], samekinds(KC,Xs,Ys).

zip_with(F,[],    [],    []      ).
zip_with(F,[X|Xs],[Y|Ys],[FXY|Ps]) :- FXY=..[F,X,Y],

type_many(KC,C,[],    []    ) --> [].
type_many(KC,C,[E|Es],[T|Ts]) --> type(KC,C,E,T),

The kind predicate is extended for the row kind. The row kind is inhabited by row configurations. A row configuration can either be a row variable or an extension of a row configuration with a name--type pair. In addition, we use a more advanced notion of type equality on application terms to overcome the limits of the structural unification in Prolog. The type predicate is extended for typing rules for records accordingly using some helper predicates (zip_with and type_many), which is rather straightforward.

A more subtle part of the change worth explaning further is the use of a more advanced notion of type equaity (eqty) in the clause for the application term, which is defined as follows:

eqty(A1,A2) :- (var(A1); var(A2)), !, A1=A2.
eqty({R1},{R2}) :- !, unify_oemap(R1,R2). % permutation(R1,R2) is not enough
eqty(A1->B1,A2->B2) :- !, eqty(A2,A1), !, eqty(B1,B2). % in case of subtyping

The eqty predicate extends structural unification with a notion of opend-ended map unification (unify_oemap) with name--value pairs, where names are atomic terms in Prolog and values are unifiable objects modulo eqty (thus, eqty and uunify_oemap are mutually recursive definitions). Because we represent an extensible records as possibly opend-ended list by a row variable, using a Prolog standard library predicate such as perumtation, which works for finite lists, is not going to work well. In addition, we use cut in to prevent backtracking from eqty because this eqty predicate is intended to be a decision procedure that does not need backtraking. The use of eqty in application terms is in sync the with common wisdom of performing more advanced notions of type matching in applications (e.g., argument value is a subtyping of a formal argument of a function in type systems with subtyping) when developing syntax-directed rules for type systems. In terms of constraint generation and solving, we can also understand this as forcing to solve the collected constraints for records whenever the type system tries to type-infer (or type-check) the application terms. Ordinary structural unification is nativly handled by the Prolog where no manual control is needed for the constraint-generation and constraint-solving (except for delaying kind inference after type inference using DCGs). But open-ended records by membership constraints is more like handling constraints, therefore, some manual control is inevitable. What !, { eqty(A,A1) } is doing in the type predicate is that it prevents generating infinite hopless candidates for open-ended map unification (e.g., hopelessly trying to unify [x:_|_], [_,x:_|_], [_,_,x:_|_], ... with []) and decides to fail.

The predicate for open ended map unification (unify_oemap) is defined as follows:

% related paper:
% Membership-Constraints and Complexity in Logic Programming with Sets,
% Frieder Stolzenburg (1996).

% unify finite maps
unify_map(A,B) :- submap_of(A,B), submap_of(B,A).

submap_of([], _).
submap_of([X:V|R],M) :- first(X:V1,M), eqty(V,V1), submap_of(R,M).

% finite map minus
mapminus([X:V|Ps],B,C) :- first(X:V1,B), !, eqty(V,V1) -> mapminus(Ps,B,C).
mapminus([X:V|Ps],B,[X:V|C]) :- mapminus(Ps,B,C).

% unify open ended maps with possibly uninstantiated variable tail at the end
unify_oemap(A,B) :- ( var(A); var(B) ), !, A=B.
unify_oemap(A,B) :-
        split_heads(A,Xs-T1), make_map(Xs,M1),
        split_heads(B,Ys-T2), make_map(Ys,M2),
        unify_oe_map(M1-T1, M2-T2).

make_map(L,M) :- setof(X:V,first(X:V,L),M). % remove duplicates

split_heads([X:V|T],[X:V]-T) :- var(T), !, true.
split_heads([X:V|Ps],[X:V|Hs]-T) :- split_heads(Ps,Hs-T).

% helper function for unify_oemap
unify_oe_map(Xs-T1,Ys-T2) :- T1==[], T2==[], unify_map(Xs,Ys).
unify_oe_map(Xs-T1,Ys-T2) :- T1==[], submap_of(Ys,Xs), mapminus(Xs,Ys,T2).
unify_oe_map(Xs-T1,Ys-T2) :- T2==[], submap_of(Xs,Ys), mapminus(Ys,Xs,T1).
unify_oe_map(Xs-T1,Ys-T2) :- 
        mapminus(Ys,Xs,L1), append(L1,T,T1),
        mapminus(Xs,Ys,L2), append(L2,T,T2).

%% ?- unify_oemap([z:string,y:bool|M1],[y:T,x:int|M2]).
%% M1 = [x:int|_G1426],
%% T = bool,
%% M2 = [z:string|_G1426].

You can run the full example code at .