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 abitrary 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.


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.