[erlang-questions] Frames proposal

Richard O'Keefe ok@REDACTED
Thu May 3 07:12:50 CEST 2012

On 2/05/2012, at 8:50 PM, Jan Burse wrote:
> I was more concerned with usage and complexity. Your frames have
> been invented many many times.

I know that.  The frames proposal SAYS that with specifics.
I haven't seen this particular implementation used for this
particular purpose, but it's not novel either.

> I remember also some proposals
> that retain the relational character, so that a pattern <{k1~v1,
> k2~vn|F}> with a tail frame would become a first class citizen
> of the language. These are then not called frames but rather
> feature structures.

Actually, they're called ψ-terms.
> I guess one way to implement real feature structures in a logic
> programming language

It has been done in at least two different ways.
LIFE (Logic, Inheritance, Functions, and Equations)
was described by Hassan Aït-Kaci and Patrick Lincoln
in 1989.  It was based on LOGIN, described in
3. A ̈ıt-Kaci, H. and Nasr, R., “LOGIN: A Logic Programming Language
with Built-in Inheritance.” Journal of Logic Programming 3(3), pp. 187–215. 1986.
(Bob Carpenter's "The Logic of Typed Feature Structures:
With Applications to Unification Grammars, Logic Programs And Constraint Resolution)
was published nearly 20 years later.
There was an interpreter for LIFE written in C called Wild LIFE
which can still be downloaded if you search for it (the link on
Peter van Roy's page appears to be dead).  I found it at
I was very unhappy when I learned that LIFE was dead.

The Wild LIFE system can't be compiled by an ANSI C compiler.  One
can figure out by reading the source code that it uses binary trees
to represent ψ-terms.

The other way that I know of is what Michael Covington did in his
book about natural language processing in Prolog, which is what I
did independently, and which I *suspect* but don't know that
Pl-PATR did as well, which is to use equations on paths rather than
displaying feature structures as ψ-terms, and precompiling the
grammar so that the paths work on plain on Prolog terms.  >>Feature
structures<< may be open, but the set of >>feature names<< is closed.
> The simple syntax there for feature structures is [k1:v1,
> k2:vn|F].

The syntax for ψ-terms looks like label(a => U, b => V) with
the 'tail' implied.

> And it seems to be rather the rule than the exception
> that a feature structure is open.

Yes.  But this is >>Erlang<< we are talking about, not Prolog,
and not LIFE, and not linguistics.  Erlang does not use unification.

> (*)
> Compiling Feature Structures into Terms:
> an Empirical Study in Prolog (1993)
> by Andreas Schöter , Buccleuch Place
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

You will note that this comes two years _after_ WildLIFE was released
and at least seven years after Aït-Kaci's work.
"Compiling to flat terms" is the technique I mentioned using above;
it is so obvious, so easy, and so effective that it's a wonder to me
that anyone ever used anything else.  In fact it was SO obvious and
SO easy that it never occurred to me that it was worth a publication.
(Erlang readers: this is actually very very close in spirit to the
way -record declarations are implemented now.  Savour the irony!)

Anyway, the *POINT* of the frames proposal is not to innovate but to
take a well established idea and adapt the details to make it suitable
for >>>replacing records<<< in a distributed functional language.
It's like a mouse's nest in a cat's ear: only the location is new.

More information about the erlang-questions mailing list