wffs vs graphsJohn McCarthy <firstname.lastname@example.org>
Date: Fri, 25 Feb 94 11:39:37 -0800
From: John McCarthy <email@example.com>
Cc: firstname.lastname@example.org, email@example.com, firstname.lastname@example.org,
interlingua@ISI.EDU, email@example.com, firstname.lastname@example.org
In-reply-to: <199402251846.NAA15811@cherry.cs.rochester.edu> (email@example.com)
Subject: wffs vs graphs
My own opinion is that the inability of standard syntax formalisms to
handle bound variables decently is the fault of the syntax formalisms
and not a reason to abandon bound variables. It is rather a reason to
invent new syntax formalisms.
Here is an example in what may be a simpler context. Consider
programs with labels and gotos. The condition that every label occur
just once, and every goto have a label to go to is a syntactic
condition that context free languages don't handle decently. Here
is how to handle it.
The syntactic entities are triples of the form
(<program fragment>, <set of labels in the fragment>, <set of
destinations of unsatisfied gotos in the fragment>
Two fragments are compatible if their sets of labels are disjoint and
if so can be confined to give a new fragment with the concatenation
of the fragments, the union of the sets of labels, and the set of
unsatisfied destinations the union of the previous sets reduced by
the sets of labels.
A proper program is one with empty set of unsatisfied destinations.
I have not been looking at the literature so maybe someone did this
long ago, and if so, I would like to know about it.
A proper syntactic formalism for expressions with bound variables is
an extension of this problem.