Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: syn-taxed [was Re: Complexity of syntax]
Message-ID: <14305:Jan800:43:4391@kramden.acf.nyu.edu>
Date: 8 Jan 91 00:43:43 GMT
References: <19876@yunexus.YorkU.CA> <23484:Jan619:01:5391@kramden.acf.nyu.edu> <1991Jan7.202423.23420@agate.berkeley.edu>
Organization: IR
Lines: 66

In article <1991Jan7.202423.23420@agate.berkeley.edu> jwl@garnet.berkeley.edu (James Wilbur Lewis) writes:
> 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.

Well, not really. I think the procedure has to be not only effective in
the theoretical sense but also practical. I don't care for a parser that
doesn't run at a reasonable speed. In this case, though, recognizing
doubled strings is quite practical.

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

I see what you're saying, but I don't agree. It really is possible to
define a language feature in such a way that it cannot be turned into
syntax.

Let's come down out of the clouds for a moment and consider a real
example. Is ``(a % b) + (a / b) * b always equals a,'' for integral a
and non-zero integral b, a semantic property or a syntactic property?

``Obviously semantic'' is everyone's first response. But consider the
integers from -32768 to 32767. An operation on integers in this range
doesn't have to be specified mathematically. It can be specified as just
one really big switch statement. Inside that switch statement, numbers
lose their meaning as such. ``57'' as a string reflects everything that
57 as a number does, because ``57'' only appears at a finite number of
spots inside our big switch statement---our parser---and has properties
entirely determined by the fixed symbols near it in the statement. (I'm
not explaining this too well, but bear with me.)

Now Programmer Dan chimes in. ``Real programmers don't use big, slow,
sloppy syntactic switch statements in place of efficient, concise
mathematical semantics,'' he says. That's true but it's besides the
point. Just because something is an awful mess when expressed
syntactically doesn't change the fact that it's syntactic!

But there is a problem with our switch statement. *It depends on the
integer size.* If the integer size is different, our semantic model of
integer operations stays the same. Our syntactic model explodes. *This*
is what makes the integer operations semantics and not syntax: no single
syntactic definition suffices for arbitrarily large integers.

Anyone understand what I'm getting at? Please try to explain it better
than I just did.

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

Agreed. I'd say that a feature is semantic if the most powerful *fixed*
grammar for the language can't express the feature.

---Dan