[SCL] two comments

[pat hayes]

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

Right, but what I had in mind was, purely as an expository device, 
giving an EBNF-style presentation of a 'standard' linear concrete 
syntax for a full SCL language, solely in order to provide 
illustrative examples.  But even for that limited use, EBNF is too 
special.

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

True; and even in a 'conventional' syntax, we will want to allow 
unordered constructions like a *set* of role-value pairs.

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

Yes, we can use tricks like this.

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

Do we need to do this *in the syntax* ? This sounds like an issue 
that comes up when describing the model theory. One can certainly 
give an EBNF for a conventional FOL syntax, for example.

>There is a well-known formalism that handles the kind of context
>sensitivities introduced by Point #2:  the lambda calculus.

Well, yes, but surely that rather begs the question. If one starts 
with a generic variable-binder then it is hardly surprising that 
variable binding looks easy :-).

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

That sounds like the binding-vector idea often used to state the 
semantic conditions on a quantifier.  Yes I agree, although I think 
the term 'namespace' is likely to be misunderstood by many readers 
familiar with XML. Or did you mean that sense of 'namespace'?? Oh, 
reading on, perhaps you did, in fact. Hmmm, need to think about that. 
That seems like a lot of baggage just in order to describe the 
quantifiers.

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

Let us keep types as a separate matter, perhaps to be introduced when 
we describe restricted quantifiers as syntactic sugar. This would be 
an elegant way to do it, however.

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

This amounts to using URIs as Skolem names, in effect, right?

Pat

>John
>
>_______________________________________________
>SCL mailing list
>SCL at philebus.tamu.edu
>http://philebus.tamu.edu/mailman/listinfo/scl


-- 
---------------------------------------------------------------------
IHMC	(850)434 8903 or (650)494 3973   home
40 South Alcaniz St.	(850)202 4416   office
Pensacola			(850)202 4440   fax
FL 32501			(850)291 0667    cell
phayes at ihmc.us       http://www.ihmc.us/users/phayes