Relational constraints, list appends

definitions

#1

Where can I find basic definitions of things like: relational constraints, list append (in particular)?

The index in Pollard&Sag does not list those; I also did not find anything in chapter 1; does anyone remember which chapter I should look in, or what other resource? I am assuming here that there must be an HPSG specific definition; if not, can someone let me know which universe in particular they come from (e.g. Lisp, databases?..)


#2

My impression is that a relational constraint is a kind of “brute force” definition – if you want to do something that can’t be done with unification, you can define a “relational constraint”. The term “relation” is used in the mathematical sense, but the mathematical notion of “relation” is so general that you could use this to do whatever you want.

Formally, a relation is a function from n objects to {true, false}. For list appends, it is a function from three lists to {true, false}, true whenever the third list is the first list combined with the second one, i.e. we have a function f, where f(A,B,C) is true whenever C=A+B.

(We could make the statement “whenever C=A+B” more formal, but doing so isn’t terribly enlightening.)


#3

Right – “relational constraints” are those that constrain the value of one feature to be some arbitrary function of the value of one or more other features. This is in contrast to systems without relational constraints where the value of a feature can be some specific type(d feature structure) or identified with the value of some other feature, or both, but that’s it.

“List append” refers to an operation on lists that takes two of them and produces a third list which is the second one appended to the first.

I don’t know of a general glossary for these terms.


#4

Right… I was hoping to to understand why is it that:

This [append] won’t work, however, if the length of the first list is unknown.

(from the Wiki)

It sounds like this relies on some specific implementation of append (that of Lisp?).


#5

For at least one anchoring citation for list append you could look at Bird (1989): https://www.cs.ox.ac.uk/files/3378/PRG56.pdf

I think that text on the wiki is a little misleading, given the example which shows appending a value to the head of a list.

The implementation in TDL has a head and a tail (FIRST and REST); you can’t get to the last element without walking the links, which would be a function (need to find the FIRST of the element with an empty REST). That’s why diff-lists include LAST so unification can stitch them together. (And yes, this structure goes back to Lisp cons cells.)


#6

Oh I think I get it now. Thank you, Chris!!


Diff-list appends