Diff-list appends

In preparation for a meeting where we will be discussing Guy’s suggestion (see also a paper by Aguila-Multner and Crysmann), I am trying to understand the problem with diff-list appends. I have never dealt with them directly, and all the information that I can find on the wiki and in the slides and in the paper is too dense for me. Apparently I lack some crucial background.

I would like to summarize my questions here. I don’t know if anything will/should be answered before the meeting; perhaps I will myself fill in some answers later. If, on the other hand, anyone would like to explain anything, that’ll be greatly appreciated.

  1. Does the definition of the diff-list come from PROLOG? If not, where from? Is it a TDL-specific definition?
  2. Does the definition of append come from PROLOG? If not, is it a TDL-specific definition? In the other thread, we said it was from Lisp, but now I am no longer 100% sure.
  3. In the Grammar Matrix, list := avm, with no additional constraints. What is the purpose of that?
  4. Can someone share a (broken) grammar illustrating a problem like this? Or like this?
  5. If you read Aguila-Multner & Crysmanns paper, do you understand the problem they are exemplifying in (25)?


In particular, why is 25-b an empty list, necessarily (as it does not say anything at all about what l is?) I suppose this is because in a diff-list by the PROLOG definition, LAST must be a free variable, but I still don’t really understand it at this point.

  1. In the GM’s dl-append example, what happens to “between”? To me it looks like it is deleted but surely this can’t be.
dl-append := avm & [APPARG1 [LIST #first,
                             LAST #between],
                    APPARG2 [LIST #between,
                             LAST #last],
                    RESULT  [LIST #first,
                             LAST #last]].

This is for a start :). Again, I will try to address as much as I can myself eventually, but if anyone feels like helping me out, thanks in advance :).

Start with number 3. This is fundamental for understanding lists.

Then go to number 6. This is fundamental for understanding diff-lists. The other points will follow. Well, except for the historical questions about PROLOG and Lisp… I don’t know about that, anyway :stuck_out_tongue:


list := avm doesn’t make sense on its own, but we also have:

  • cons := list & [FIRST *top*, REST list]
  • null := list

So list is the top of a mini-hierarchy, and crucially, REST is of type list.


Diff-lists are open lists – they don’t have a null at the end. This means the LIST of a diff-list is unifiable with a list of arbitrary length.

25b is an “empty” diff-list because it’s LAST is the beginning of the LIST – i.e. there are no elements before we get to LAST. We can add elements to LIST, but they come after LAST. “Empty” diff-lists are very different from empty normal lists (i.e. null)


To understand this, consider what ends up in RESULT.LIST.

The implicit assumption in dl-append is that each diff-list’s LAST occurs somewhere along its LIST. According to the definition of a diff-list, this isn’t necessary, but this has to happen for a diff-list to be useful.

It makes sense to start by thinking about lexical entries, where the diff-lists are defined. Each lexical diff-list has a normal list (in LIST), and LAST will point to the end of the LIST. The LASTs are there so that we can identify the end of one list with the beginning of another, so that we get one long list (the result of append).

Once things have been appended, the LASTs of the original lists stay where they were, so each LAST ends up just somewhere along the LIST, rather than actually at the end.

1 Like

Thank you very much, Guy. This feels very helpful though I will probably need to ask more questions.

So, #between ends up being pointed to by RESULT.LIST.LAST. Okay. But how would that be used in practice? Does this mean there will be rules relying on this specific knowledge? Something here does not make sense to me but it’s hard to pinpoint. What I probably need to do is create a grammar exemplifying these things but I am not sure what this grammar should look like exactly.

What would happen if we replaced all instances of list with avm ?

And actually, in matrix.tdl we have REST of type top, not list. Do you know why?

list := avm.

cons := list &
  [ FIRST *top*,
    REST *top* ].

0-1-list := list.
1-list := 0-1-list & cons &
  [ REST null ].
null := 0-1-list.
1-plus-list := cons &
  [ REST cons ].

From Guy’s proposal:

list-of-dlists := list &
[ START list,
END list ]

I don’t understand why this is a list of diff-lists rather than one diff-list?

The definition of a diff-list:

diff-list:= avm &
[ LIST list,
LAST list ]

Given that:

list := avm

Looks like two equal definitions to me? I am not getting something from Guy’s explanation of how list is the top of a small hierarchy and that’s important…

REST *top* is underconstrained. Any type other than list (and its subtypes) wouldn’t make sense – if any grammar used another type, I would regard it as a misuse of lists. In principle, we could also get rid of the list type, but this would leave open other misuses or bugs.

In fact, I would suggest changing matrix.tdl to have REST list.

It’s a list and a diff-list at the same time. But they are intertwined – the list contains normal diff-lists, and the START-END diff-list contains the concatenation of the normal diff-lists.

Yeah, agreed that that’s an error, and one that is probably rendered safe only because all uses of the list type are saying appropriate things about REST. It would be interesting to see if just making that change would pass all Matrix regression tests. I’ll file a ticket now.

Actually, could I ask about this again?

Still finding it counterintuitive that things just say:

a := b.

  • without any additional constraints.

a := b w/o further constraints can be meaningful if it sets up a contrast with c := b.

How would the contrast arise? I seem to be missing something fundamental. Aren’t a:=b and c:=b both say, about a and c: a and c can be described by the same structure as b? How would a contrast happen if there are no additional constraints?

By the shape of the type hierarchy itself. Two types unify to their unique GLB (greatest lower bound). In that hierarchy, a & c do not have a GLB and so they do not unify.

Oh. Yes, the GLB is what I was missing. I forgot about it (and I keep forgetting about Copestake 2002). The book has an explanation of GLB though I must say I don’t fully understand it, i.e. why the GLB property is needed in a type hierarchy. Is there an explicit linguistic/theoretical function or is it purely about implementation?

…And there is still something that trips me off. OK, no GLB for a and c, but what does b have to do with it? If we replace b with top (suppose b := top), that wouldn’t lead to a and c having a unique GLB?

Should we have a new category for JRF? Or is HPSG appropriate here, what do people think?

It is connected to a foundational design choice: closed-world v. open-world in the type hierarchy. There are variants of HPSG which make the open-world assumption, meaning you can create mutual subtypes on the fly. I’m not quite sure how one gets unification failures in such a set up, but I guess maybe only some parts of the hierarchy are open world?

The function of b is to capture what a and c have in common. For example, b might be case, which is the type that is the appropriate value for CASE, and then a is nom and c is acc. Or b might be list, the type of thing appropriate for any list-valued feature, including REST and a is null and c is cons (or nelist).

1 Like

Should we have a new category for JRF? Or is HPSG appropriate here, what do people think?

Pros: The JRF is a separate thing from HPSG.
Cons: We might not be consistent about allocating topics to one category or the other

If topics can be tagged with multiple categories, I vote yes :slight_smile:

Without GLBs, unification is not well-defined. When two feature structures are unified, we must assign a type to each feature path. If, for a given path, the types of the two input structures do not have a GLB, we do not have a unique type for the output.

The type hierarchy is more fundamental than type constraints. To define a grammar, we must first define the type hierarchy. Then we can define features (each feature being introduced at a unique point in the hierarchy). Then we can define feature structures. Then we can assign a feature structure to each type (these are the type constraints). Then we can define feature structures that satisfy the type constraints. TDL lets us mix these things together (which makes it easier to write a grammar), but mathematically, it makes sense to define them in that order, and the processing engines effectively do that for us. Copestake (2002) goes over this in more detail.

1 Like

Unfortunately, no, though there are also tags (which one can also subscribe to, I believe). I’ve been adding the “hpsg” tag to some of the GrammarMatrix category topics, for example. I suppose I will just add the “JRF” tag here.