Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!usc!apple!agate!garnet.berkeley.edu!jwl
From: jwl@garnet.berkeley.edu (James Wilbur Lewis)
Newsgroups: comp.lang.misc
Subject: Re: syn-taxed [was Re: Complexity of syntax]
Message-ID: <1991Jan7.202423.23420@agate.berkeley.edu>
Date: 7 Jan 91 20:24:23 GMT
References: <14679:Jan509:13:1391@kramden.acf.nyu.edu> <19876@yunexus.YorkU.CA> <23484:Jan619:01:5391@kramden.acf.nyu.edu>
Sender: usenet@agate.berkeley.edu (USENET Administrator)
Organization: University of California, Berkeley
Lines: 70

In article <23484:Jan619:01:5391@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>In article <19876@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes:
>>    ... we defined a rule of inference to be an effetive test to decide
>>    wheter a string s can be deduced from a set of strings s1,...sn.
>
>In the article that you're responding to I gave exactly such an
>effective test. I conclude that the repeated-variable-in-declaration
>problem is syntactic, by Minsky's definition (which I agree with). Done.

There's something fishy with this line of reasoning.  You seem to think
that the existence of an effective procedure to distinguish valid from
non-valid strings implies that the property of "validity" is purely
syntactic.  Now in a sense, this is true because any effective recognition
procedure corresponds to some Type 0 grammar.  But this, to me, stretches
the traditional notion of "syntax" well past the breaking point.  Does the
existence of a Type 0 grammar for prime numbers imply that primeness is
a syntactic property?  Or what about an effective procedure for computing
the meaning (object code) of a C source file?  In principle, we could pair 
off the C strings with their meanings in some suitable notation and capture the 
relationship in an unrestricted grammar,  and so (by this fishy defininition)
render all discussions of "C semantics" meaningless.  

This is where the fuzziness between syntax and semantics comes from.  For
a given language, one can either specify it with a relatively simple
grammar and allow the possibility of syntactically valid but meaningless
strings, or use a more powerful grammar formalism and reduce most questions of
validity to purely syntactic issues.   

To me, this implies that when someone claims "X is a syntactic property
of language L", it is a reasonable thing to ask them what grammar they're 
using.  To be honest, I *was* surprised to hear that Algol 68 used a
context-sensitive grammar to syntactically enforce its declaration rules.
I'm still curious to see what the grammar rules look like -- that challenge
of mine wasn't totally facetious, though I'd better retract the part about
"eating my hat" if Dan comes up with a grammar having the desired
properties. :-)  But I'm still not going to be impressed with a 
non-constructive existence proof for a Type 0 grammar, for the reasons
outlined above.

We should also be aware of the difference between formal language specification
and the practical realities of compiler construction.  If feature X is
specified by a context-sensitive grammar, but implemented via semantic
actions in a parser using a context-free grammar, is X "syntax" or
"semantics"?  

I think any linguist would take a dim view of resorting to the existence
of a Type 0 grammar as an argument for some language feature being a
syntactic property.  According to Chomsky (quoted in Winograd, _Language
as a Cognitive Process_): "Reduction of the class of grammars is the
major goal of linguistic theory".  His characterization of the problem:

   "The gravest defect of the theory of transformational grammar is
    its enormous latitude and descriptive power.  Virtually anything
    can be expressed as a phrase-marker...virtually any imaginable
    rule can be described in transformational terms.  Therefore, a
    critical problem in making transformational grammar a substantive
    theory with explanatory force is to restrict the category of 
    admissible phrase-markers, admissible transformations, and admissible 
    derivations."

These arguments apply just as well to the languages that computer
scientists are accustomed to dealing with, so it's not surprising that
we tend to think in terms of CFL's when dealing with issues of syntax.
Not only is it not a defect in the CS curriculum (most of us, after all,
*have* been exposed to the more powerful classes of formal grammars), but
as Chomsky argues above, it's good linguistic sense.  And *that* is
about as close to the horse's mouth as we are going to get in this
discussion!

-- Jim Lewis