Incomplete expanded type constraints

There seem to be some cases where the LKB does not fully expand type constraints, e.g. compiling the following as the entire grammar:

list := *top*.
cons := list &
  [ FIRST *top*,
    REST list ].
0-1-list := list.
1-list := 0-1-list & cons &
  [ REST null ].
null := 0-1-list.
1-plus-list := cons &
  [ REST cons ].

list-wrapper := *top* &
  [ LIST list ].
diff-list := list-wrapper &
  [ LAST list ].

wrapped-list-with-diff-list := list-wrapper &
  [ LIST list-with-diff-list ].

list-with-diff-list := list &
  [ RESULT diff-list ].
cons-with-diff-list := cons & list-with-diff-list &
  [ FIRST #first,
    REST list-with-diff-list & [ RESULT [ LIST #rest,
                                          LAST #end ]],
    RESULT [ LIST [ FIRST #first,
                    REST #rest ],
             LAST #end ]].
0-1-list-with-diff-list := 0-1-list & list-with-diff-list.
null-with-diff-list := null & 0-1-list-with-diff-list &
  [ RESULT [ LIST #end,
             LAST #end ]].
1-list-with-diff-list := 1-list & 0-1-list-with-diff-list & cons-with-diff-list.
1-plus-list-with-diff-list := 1-plus-list & cons-with-diff-list.

test := *top* &
  [ TEST wrapped-list-with-diff-list & [ LIST null ]].

The type constraints for null-with-diff-list include a re-entrancy. However, in the type test, this re-entrancy is lost.

Strangely, commenting out the definition of 1-list-with-diff-list recovers the re-entrancy, even though this type does not appear in the feature structure. Similarly, commenting out the constraints on cons-with-diff-list also recovers the re-entrancy, even though again this type does not appear in the feature structure.

I’m not 100% sure what the conditions are which cause this bug, but they must be quite specific, given the above behaviour, and given that the LKB can handle much larger and more complicated type constraint expansions.

I’ve tested this with the most recent release of LKB-FOS (as well as an older release).

It’s possible that @olzama has come up against this problem before, without realising it.

I can confirm that upon loading this hierarchy in ACE, the “test” type has the expected reentrancy:
testavm

Obviously I don’t know what’s going on in LKB, but the conditions you describe are possibly consistent with type inference not pushing the authored “null” value down to “null-with-diff-list” but instead to some intermediate value. For instance, adding or removing seemingly unrelated types can sometimes impact what GLB types are inserted into the hierarchy. In the hierarchy created by ACE from your source file, there are no GLB types, and I don’t see any reason to put one in, so this seems an unlikely explanation, but hey, the circumstances are unlikely too :slight_smile:

2 Likes

I can take a look at what’s going on in the LKB - but I won’t be able to get to it until next week.

To be more precise, here is the expanded type in the LKB, where all the types are correct, but the re-entrancy is missing:
incomplete

The type hierarchy in the LKB looks correct, exactly matching @sweaglesw’s hierarchy from ACE.

I believe I have asked that in the past, but I can’t remember where and what the answer was! How to test those examples from @guyemerson in LKB and ACE? That is, what is the minimum script to load the TDL above in LKB and what is the minimum config for ACE?

Besides inspecting the expanded hierarchy, If I remember right from Paris Summit, execution is done by parsing, right @guyemerson? So how do you ‘test’ these data structures? Do you have some minimal lexical entries?

In this case, I’m just using the LKB to compile the type system. There are no lexical entries, and no parsing. The test here is compiling the type system and viewing the expanded type constraints for the type test.

I’ve been using a modified LKB script from the Grammar Matrix, but it looks like the minimum script would be something like:

(defparameter *toptype* '*top*)
(read-tdl-type-file-aux (lkb-pathname (parent-directory) "incomplete.tdl"))

(assuming the TDL is saved as “incomplete.tdl”, in the parent directory)

In the demo grammar that I presented at this year’s summit, there are a number of LKB scripts, but only one of them (script-pseudoenglish) is designed for parsing. The other scripts load a type system, then you can inspect the expanded type constraints and do interactive unification.

Thank you to @johnca for finding and fixing the bug! For details, see: [developers] Incomplete expanded type constraints