[SCL] two comments

[John F. Sowa]

Pat and Jay,

There are several features of SCL syntax and semantics that
must be considered:

 > Your final point about context-sensitivity is well taken, and
 > I agree. We still however need a way to present the ideas that
 > is not automatically tied to context-free modes, such as EBNF.
 > Can you suggest a widely accepted and understandable formal
 > notation, analogous to EBNF, for displaying non-context-free
 > syntax?

EBNF is both context-free and specialized for languages that have
a well-defined linear ordering.  The following features of SCL
cannot be expressed in EBNF without further extensions:

  1. Graphical languages, such as CGs, do not assume a linear
     ordering.  A CG context, for example, represents the
     conjunction of all CGs nested in that context, independent
     of their layout on a two-dimensional surface (in the CG
     display form) or in a one-dimensional string (in CGIF).

  2. The scope of variables is defined by the structure of a
     formula, which depends partly on the left-to-right order
     and partly on the nesting of parentheses.  EBNF does not
     provide any convenient way of stating which variables
     are bound by which quantifiers.

Point #1 is addressed in some versions of extended BNF by
providing a kind of bracket that encloses a set or bag of
constituents instead of a sequence.

Point #2 is usually addressed in specifications of programming
languages by providing some way of defining a symbol table,
which keeps track of the type and point of definition of each
variable.

There is a well-known formalism that handles the kind of context
sensitivities introduced by Point #2:  the lambda calculus.
Montague made liberal use of that feature of the lambda calculus
in defining his famous, but widely feared and little understood
Montague Grammar.

I believe that more of our readers are likely be familiar with the
notion of namespace than with lambda calculus or Montague Grammar.
Therefore, I would recommend that we introduce the notion of namespace
as a place-holder for specifying a collection of variable symbols,
each associated with an optional type declaration.  For example,
the following construction

    (forall ((?x Cat) (?y Dog)) ...)

would create a namespace with two variables ?x and ?y and with the
type Cat associated with ?x and the type Dog associated with ?y.

In the semantics, we would say that each quantifier symbol specifies
a namespace for the list of variable names that follow.  We could
even have something like the following:

    (external ((?x URL="http://.....") (?y URL="....")) ...)

which would have the logical effect of an existential quantifier
and some extra information associated with ?x and ?y.

John