Formal definitions of semantics

think!compass!worley@EDDIE.MIT.EDU (Dale Worley)
Fri, 27 Jan 89 10:39:33 EST

          From comp.compilers

Related articles
Formal definitions of semantics think!compass!worley@EDDIE.MIT.EDU (1989-01-27)
Re: Formal definitions of semantics (1989-01-30)
| List of all articles for this month |

Date: Fri, 27 Jan 89 10:39:33 EST
From: think!compass!worley@EDDIE.MIT.EDU (Dale Worley)

        From: encore!uokmax!glcowin@Central.Sun.COM (Greg Cowin)

        Overlooking the real problem of defining a programming language
        seems to be very common. The problem is providing a formal
        semantic definition. This problem is not easily solved, although
        it can be done.

I beg to differ. Formally defining the semantics of a programming
language isn't as hard as it looks, *provided* you take one of two
approaches. The first is to describe the language entirely in terms
of a set of formal objects. For instance, the Lisp CONS operation can
be described as "Create a new CONS-cell object, whose first item is
the first argument, and second item is the second argument. Return
that object.", CAR is then "Return the first item of the CONS-cell
object which is the argument.", etc. The benefit (and problem) with
this method is that there is no leaking-through of the Von Neumann
machine which is implementing the language. The result is that Lisp
or Scheme programs which don't use I/O and other "known non-portable"
features are very portable.

The second method is to describe a mapping from the language features
into a generalized Von Neumann architecture. This is necessary, for
instance, in Fortran (EQUIVALENCE) and C (pointer arithmetic). This
allows the user to program "closer to the metal", and specify manually
things which an optimizing compiler should be doing for him. Trouble
starts brewing because the "generalized Von Neumann architecture"
usually has lots of unspoken assumptions which turn into gotchas when
someone constructs either hardware or a compiler that violates an
assumption. The ANSI C draft is wrestling with a bunch of them: an
address might not be decrementable, because it could step a pointer
off the beginning of a memory segment; the address of an object may be
representable in several ways, which are not obviously equivalent;
alignment; where padding may be inserted in structures and arrays.

Dale Worley, Compass, Inc. compass!
Seen in a technical journal: "You'll always offend someone when you deal with
a large group of people. There's always someone that can't stand Bambi."

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.