Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #341 > unrolled thread

Formally Defining a Programming Language

Back to article view | Back to comp.compilers

Contents

  Formally Defining a Programming Language Seima Rao <seimarao@gmail.com> - 2011-11-19 19:15 +0530
    Re: Formally Defining a Programming Language Kaz Kylheku <kaz@kylheku.com> - 2011-11-21 17:16 +0000
      Re: Formally Defining a Programming Language "s_dubrovich@yahoo.com" <s_dubrovich@yahoo.com> - 2011-11-27 20:58 -0800
    Re: Formally Defining a Programming Language Christophe de Dinechin <christophe@taodyne.com> - 2011-11-22 20:45 -0800
    Re: Formally Defining a Programming Language federation2005@netzero.com - 2012-02-29 17:11 -0800
      Re: Formally Defining a Programming Language glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-03-02 22:35 +0000

#341 — Formally Defining a Programming Language

Hi,

n designing my own Programming Language and given the existence
of a lot of programming languages and an infinity of "knowhows" that
is the Internet, I resorted to adhoc adaptation methods that worked
incredibly well!

However, now, I want to formalize the definition of my programming
language. I find that the Backus Naur Form is a notation but reaching
to that form requires decisions such as the following illustration
would suggest:

         Illustration of Correct C++
         -----------------------------------

             function_declaration:

                 function_specifier return_type
                     fct_declarator '(' param_decl ')
                         cv_qualifier exception_specification ';'
                 ;

     In this illustration, I am inclined to ask:

     i) What is it that contributes to deciding that
         'inline' should be a separate "specifier"
        in the grammar?

    ii) How did the designers come up with
        something called a "specifier"?

    iii) What is a "specifier" in a non-C/C++ context
          by the way?

Therefore, I suspect that there is a Formal Study of Programming
Languages that occurs in Selected Schools.

Can readers of this forum help direct to relevant materials wrt
Formalism that I can study to learn about Formalisms that will help in
deciding about my Programming Language?

Sincerely,
Seima Rao.

[toc] | [next] | [standalone]

#346

On 2011-11-19, Seima Rao <seimarao@gmail.com> wrote:
> Hi,
>
> n designing my own Programming Language and given the existence
> of a lot of programming languages and an infinity of "knowhows" that
> is the Internet, I resorted to adhoc adaptation methods that worked
> incredibly well!
>
> However, now, I want to formalize the definition of my programming
> language. I find that the Backus Naur Form is a notation but reaching
> to that form requires decisions such as the following illustration
> would suggest:

BNF gives you only syntax, which is far, far from formalizing a language.

Semantics is the hard part to formalize.

>          Illustration of Correct C++
>          -----------------------------------
>
>              function_declaration:
>
>                  function_specifier return_type
>                      fct_declarator '(' param_decl ')
>                          cv_qualifier exception_specification ';'
>                  ;
>      In this illustration, I am inclined to ask:
>
>      i) What is it that contributes to deciding that
>          'inline' should be a separate "specifier"
>         in the grammar?

The syntax of C++ is the consequence of designer whim, constrained by
backward-compatibility considerations.

In general, syntax in computer languages is totally arbitrary: it starts
with something that seems like a nice notation, and then over the years,
cruft is piled on top of it.

Most programming languages do not have a technically designed syntax;
it is a process driven by taste, and a (often false) intution for
the psychology of the model programmer that the designer has in mind.

Syntax and semantics in human languages is arbitrary also.

For instance one language, a marker of past tense goes on a verb. In another,
tense indication may go onto an adjective.

  English:   ... is red    ... was red
  Japanese   ... akai      ... akakatta

Who decided that? It doesn't matter. In a sentence you have to convey
certain things, and how those map to the tree struture of the utterance
that is produced doesn't matter at all as long as the convention is
reasonably consistent.

>     ii) How did the designers come up with
>         something called a "specifier"?

This comes from ISO C, and may be a committee-invented retroactive naming for
something.

I don't have a copy of the first edition of The C Programming Language
(a.k.a.  K&R1) any more, but Dennis Ritchie himself might have called
this a specifier, in which case it was simply inherited into ISO C
when it was standardized. ISO C used that book as its principal base
document.

In a C declaration, there are specifiers and declarators. This is for
a reason: multiple declarators, separated by a comma, can share the
same "common stem" of specifiers:

  long int a, (*b)(), c[3];
           ^  ^^^^^^  ^^^^  declarators
  ^^^^ ^^^ specifiers

Of course, the declarators also specify something! To specify is to
declare something, and to declare something is to specify! If you're
passing through a border and you're asked to "declare" any goods in
your luggage, you are being asked to specify what is in there: to make
a statement which is specific about the contents.

But since there are two different components to type specification in
C, you need two words.  So this is all just a word game.

In Java you can do something like:

  int[3] a;

This illustrates how syntax is abitrary. The derivation of an array
type does not have to be strictly handled by the declarator syntax.
The language designer can easily move it to the specifier part.
Dennis Ritchie (arbitrarily!)  decided that specifiers will only
determine very basic things: storage class and type.  All complex type
derivation is played out in declarators.

(This is no longer the case in C++, in which specifiers can be
template types with arguments, and those arguments can be arbitrarily
complex expressions: my_array_type<int, 3> a; .  But C++ does not
deviate so far from C as to give you int[3] a;)


About naming, software is complex and people come up with whatever
names they can come up with.  Sometimes the names are silly. In the
Linux networking stack, why are objects which receive notifications
called "notifiers"? But everyone working with that code knows what it
means.

In one project long ago, we called the branches of a protocol stack in
a given scenario "trousers". A packet comes in up one "leg", is
processed by some routing protocol and then goes out the other "leg"
to the other device.  The block diagram looks like a pair of jeans.

>     iii) What is a "specifier" in a non-C/C++ context
>           by the way?

Something that specifies.

> Therefore, I suspect that there is a Formal Study of Programming
> Languages that occurs in Selected Schools.

ROFL! The word "specifier" is just something that popped into
someone's head, that's all.

You're not going to achieve formality just by mimicing some jargon
from C and C++.

To define a language formally, you have to say exactly what is the
structure and behavior of each construct.

It doesn't matter what words you use, as long as you define those
words and use them consistently.

Specifiers are symbols in a certain area of the syntax tree of a C++
declaration. That is their definition.  Forget about what the word
means anywhere else.  If you want to call them "slepnifiers", that
will work too, if you are consistent with the usage everywhere in the
document.

[toc] | [prev] | [next] | [standalone]

#364

> >     ii) How did the designers come up with
> >         something called a "specifier"?

It is a practical need.  With a language in one hand and the need to
implement it in the other hand.
Take the identifier 'a'.  Does it represent a variable, a function, or
what?  The language syntax should help indicate which.  Let's say the
syntax indicates it is a variable.  Now comes the implementation and
use of it as a variable.  This forces consideration of the underlying
hardware which may very well handle variables of 'float' differently
than those of 'int', and that 'sign' maybe an issue in
implementation.  So to pass along more information about 'a', a meta-
term is given called "specifier".  And a need to inform the translator
about such attributes of 'a' gives rise to another meta-term
"declaration".

Section 4.  What's in a name?

C bases the interpretation of an identifier upon two attributes of the
identifier: its _storage class_ and its _type_. ...

> ...
> ROFL! The word "specifier" is just something that popped into
> someone's head, that's all.
>
> You're not going to achieve formality just by mimicing some jargon
> from C and C++.
>
> To define a language formally, you have to say exactly what is the
> structure and behavior of each construct.
>

Doesn't LISP fit this though?

Steve

[toc] | [prev] | [next] | [standalone]

#349

On Nov 19, 2:45 pm, Seima Rao <seima...@gmail.com> wrote:
> Hi,
>
> n designing my own Programming Language and given the existence
> of a lot of programming languages and an infinity of "knowhows" that
> is the Internet, I resorted to adhoc adaptation methods that worked
> incredibly well!

I'd like to share a few thoughts here, based on my experience with XL
(http://xlr.sf.net):

- Don't design a language today based on 30-years-old templates. XL
demonstrates that you can create a working, readable language with
user-extensible syntax using a recursive descent parser which is less
than 2000 lines of commented C++.

- Keep it simple. The C++ specification weights hundreds of pages, and
it's full of bugs and ambiguities. XL can be explained in twenty pages
or so, see http://xlr.sourceforge.net/sites/default/files/XLRef.pdf.

- Consider its applications, the ecosystem. Think about the library,
about meta-programming, about domain-specific languages, about IDE
integration (Eclipse, vi or emacs).


> Can readers of this forum help direct to relevant materials wrt
> Formalism that I can study to learn about Formalisms that will help in
> deciding about my Programming Language?

I assume you know about the Dragon Book (http://en.wikipedia.org/wiki/
Dragon_Book)?

[toc] | [prev] | [next] | [standalone]

#469

On Saturday, November 19, 2011 7:45:53 AM UTC-6, Seima Rao wrote:
> Can readers of this forum help direct to relevant materials wrt
> Formalism that I can study to learn about Formalisms that will help in
> deciding about my Programming Language?

To expand on a reply given by Kaz Kylheku: it's a dirty little secret that the
front ends of these languages are being designed by a process that amounts to
little more than wading in the dark -- except the part about it being a
secret.

It seems that a lot of the COBOL mind-set got caught up in the revisions that
went into making C++, C# (not to mention languages like SQL). This mind set
basically amounts to building the constraints directly into the syntax,
turning simplicity into a highly redundant convoluted affair. Take a look at
the ECML spec for C#, for instance.

http://www.ecma-international.org/publications/standards/Ecma-334.htm

You will see the same items appearing in similar-looking phrase
structure rules in a half-dozen different places. What the language
designer is doing is basically forcing the syntax to encapsulate
agreement rules or semantic constraints -- which is the First Cardinal
Sin of designing language front ends. The result is that the grammar
comes off looking more like COBOL (or even the original form of
Pascal, to some degree).

This seems to be starting to take root in the latest revision of C.
Though C is a relatively clean language, in terms of syntax, there
already were several places -- before the 201X revision -- where
constrains found their way into the syntax: the ordinary vs. abstract
declarators, two sets of rules for type specifiers as well, a mangling
of the syntax for cast-expressions, of the assignment operator (in
that case, semantic constraints for the assignment statement were
forced into the syntax by a weird doling out of expression priority
levels).

But now we come to 2010-2011, and we find that (last I checked) the
committee who does the ISO standards complete mangled the syntax for
structure expressions, basically duplicating it over, messing up the
syntax for cast-expressions, and forcing semantic constraints for
structured expressions into the syntax itself (e.g. that they can only
be type-cast). Those are thing you normally either (a) design around
by generalizing the language to allow for fewer restrictions, (b)
explicitly stipulating the constraint in the semantics section and
keeping it out of the syntax or (c) a bit of both.

As far as a language like C# or C++ goes (not to mention SQL!): I've seriously
thought about bringing a linguist(!) into the loop to work with me to analyze
the languages actually defined in the Standards to come up with a better
account of what the language is (count me as one such person, since I have
background in Linguistics, but there's a couple others I have in mind).

If I have time, I'm going to upload a simplified (but still basically
equivalent) account of the syntax for C -- 1989/1990, 1999 AND 2010 all in one
file. As to the larger questions you're asking (the REAL question BTW is what
kind of SEMANTIC formalism to use for the languages) -- I may follow up on the
syntax by showing a nice way to parse it, to derive a parser for it, that goes
beyond the traditional LR and LL parsing formalisms (i.e. algebraic methods
that use a calculus for context-free expressions).

I think you may find an article from a while back in the comp.compilers
archive where I gave a somewhat detailed account of my design of the language
C-BC (which is POSIX BC almost upgraded to C!) -- its execution model. A
similar approach is adopted by a language like Prolog, where an execution
model for it has been posed (the Warren Abstract Machine, WAM).

Now .. for me to try the same exercise of making a simplified syntax
for C++ (and externalizing its constraints) ... that's a much more
difficult and lengthy exercise that I've only begun considering. But
make no mistake: those phrase structure rules have got to come down in
number and complexity!

An enveloping grammar for C++ or even SQL ... too much to hope for?

One of the advantages of externalizing constraints, BTW, is that it puts the
spotlight not only on the "Why even have the constraint?" question but also on
the "why not just remove it?" question. This leads to cleaner languages.
People, after all, have to USE these languages and LEARN them! That's why
you're not supposed to clutter the grammar.

[toc] | [prev] | [next] | [standalone]

#471

federation2005@netzero.com wrote:
> On Saturday, November 19, 2011 7:45:53 AM UTC-6, Seima Rao wrote:
>> Can readers of this forum help direct to relevant materials wrt
>> Formalism that I can study to learn about Formalisms that will
>> help in deciding about my Programming Language?

Do you mean formalism in describing the language, or for designing
one in the first place? I suppose they are related, but they
seem different questions to me.

> To expand on a reply given by Kaz Kylheku: it's a dirty little
> secret that the front ends of these languages are being
> designed by a process that amounts to little more than wading
> in the dark -- except the part about it being a secret.

It seems te me that many languages could have been designed better
in the first place, except that the rules for good design
weren't yet known. But even more, trying to extend an existing
language, and maintain compatibility with the previous one,
tends to be ugly.

As I understand it, one of the original goals of PL/I was to
be Fortran-like, but not back compatible. (In addition to
bringing in features from ALGOL and COBOL.)

From "History of Programming Languages," edited by R. Wexelblat:

  "FORTRAN VI is not intended to be compatible with any known
   FORTRAN IV. It includes the functional capabilities of
   FORTRAN IV as well as those capabilities normally associated
   with "commmercial" and "algorithmic" languages. In order to
   embrace these capabilities in a usable and practical language,
   it has been found virtually impossible, and certainly
   undesirable, to retain FORTRAN IV as a compatible subset."

and further:

  "Compatibility with FORTRAN IV would preclude having a simple
   elegant streamlined language because FORTRAN IV itself is heavily
   burdened with curious restrictions and complexities that have
   accumulated during its long history of additions that maintained
   approximate compatibility with early versions."

(Note that the long history of additions was only about 10 years,
as that was in 1963.) In the following 45 years (through Fortran 2008)
many PL/I features have been added to Fortran, many restrictions
removed, but many of the "curious restrictions" are still there.

(snip)

> This seems to be starting to take root in the latest revision of C.
> Though C is a relatively clean language, in terms of syntax, there
> already were several places -- before the 201X revision -- where
> constrains found their way into the syntax: the ordinary vs. abstract
> declarators, two sets of rules for type specifiers as well, a mangling
> of the syntax for cast-expressions, of the assignment operator (in
> that case, semantic constraints for the assignment statement were
> forced into the syntax by a weird doling out of expression priority
> levels).

It seems to me that almost has to happen in the case of a language
with reserved words. Since users might have used those words in
their programs, it is difficult to maintain back compatibility
with those programs, and add new features with new words.

Fortran and PL/I were carefully (or not) designed without reserved
words. In the PL/I case, I believe it was partly to avoid the
problems of COBOL, where programmers have to keep nearby the
list to avoid using them. (I still haven't written a COBOL program,
so I can't say from experience.)

> But now we come to 2010-2011, and we find that (last I checked) the
> committee who does the ISO standards complete mangled the syntax for
> structure expressions, basically duplicating it over, messing up the
> syntax for cast-expressions, and forcing semantic constraints for
> structured expressions into the syntax itself (e.g. that they can only
> be type-cast). Those are thing you normally either (a) design around
> by generalizing the language to allow for fewer restrictions, (b)
> explicitly stipulating the constraint in the semantics section and
> keeping it out of the syntax or (c) a bit of both.

It seems that making a readable, usable to programmers, description
of a language is often different from a formal language definition.
It is nice to have both, and for them not to be too different.

Also, as noted above, it gets worse when a language is extended,
yet tries to stay compatible.

(medium sized snip)

-- glen
[The plan for PL/I was for it to be adequate to do anything you could
do in Fortran or Cobol, which it pretty much was, give or take some
serious efficiency issues.  IBM had a Fortran to PL/I translator which
worked but produced very ugly code to work around small differences in
features that worked almost but not quite the same. -John]

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web