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

Groups > comp.compilers > #1452

Fundamentals for a Compiler and Language (was: Writing A Plain English Compiler)

Show key headers only | View raw

On Tuesday, November 4, 2014 10:27:29 PM UTC-6, Gerry Rzeppa wrote:
> [And with that, this thread is over unless someone has something
> to say that's related to compilers. Thanks, all. -John]
> Exactly how does one go about writing a Plain English compiler?

What you should be focusing on (and to sorta abide by the moderator's wish) is
what goes on in the semantics, and on the back end more so than how the
language is presented to someone.

That means that the "fundamentals"
> 1. Type definitions;
> 2. Global Variable definitions;
> 3. Routine Headers;
> 4. Conditional Commands; and
> 5. Unconditional Commands.
have to be properly addressed; and first you have to ask whether these really
are the fundamentals, and if not, then what they should be.

In fact, you can get away with just the following for the procedural element:
   * the comma statement A, B (do A, discard its results, then do B [with
results])
   * the conditional A? B: C. The comma can be treated as a special case A, B
= A? B: B.
   * recursive definitions of continuation or call-return segments. Doing
things by continuations is preferrable since you can define call-return
semantics in terms of it, but not so easily the other way around.
   * the ability to reference continuations (i.e. gotos).

Fortran actually headed in that direction early on (as did the scripting
language DC), but decided to fall back in more recent years.

The distinction between locals and globals has to go one level deeper: to
include also the distinction between thread-local and shared.

Finally, as for type systems: it appears that contemporary languages have been
progressively trying to incorporate more and more of the Curry-Howard
isomorphism (or "Type-Proposition" correspondence), and ... in particular ...
the various modifications that try to this correspondence to include
quantifiers in predicate logic (which then requires indexed or parametrized
types). These are embodied by the various higher-order type theories that have
cropped up since Carnac and Goedel (Goedel's Dialectica interpretation,
Martin-Loef, Carnac's systems B and C, Lambek/Scott's formalism). I think C++
was moving in the direction of Hindley-Milnor type theory.

This aspect of the language design -- which is (in fact) the aspect that bears
the greatest affinity to natural language (think Montague semantics) -- is
highly non-trivial. This is borne witness by the large number of ways that
different language have tried to approach this issue.

In particular, what's non-trivial about it is that objects which can be named
and addressed can be contained in or contain other objects. Fortran actually
went a step further allowing *overlapping* objects (by way of the equivalence
statement). Languages like C++, in contrast, seem to shy away from this.

The Lambda operator *can* be incorporate *seamlessly* into any of these
languages provided you recognize the continuation for what it really is: an
infinitary lambda expression (i.e. an expression with an infinitary parse
tree.) So, for instance, the cyclic statement (while (E) S) followed by a
continuation Q would correspond to the infinitary expression E? (S (E? S (E? S
(...) Q) Q) Q, which is called "rational" since it has only a finite number of
distinct subexpressions. A goto label is simply a label of a subexpression,
and a goto statement is just a compact reference to the labelled
subexpression.

This works quite well with continuation semantics, since the call and return
are already factored out by the time you get to this semantics. All you have
are jumps. So, I won't belabor how you represent calls and returns in
continuation form.

The correspondence goes all the way back to Landin, via the following
equivalence for assignments to simple variables (x = A, Q) <-> (lambda x.Q) A,
where Q is a continuation. But Landin never incorporated the above-mentioned
insight on cyclic control-flow structures, so the whole programme languished
in the 1960's.

Ultimately, the correspondence is of the following form: to each statement S
is a context S[] (i.e. an infinitary expression with a missing subexpression)
such that S[Q] is the result of applying Q after executing S. Thus, for
instance, the context corresponding to the simple assignment statement x = A
is just (lambda x.[]) A.

But the non-trivial part: the type system, the objects residing within it and
pointers. What's non-trivial about is what goes on with the object-subobject
hierarchy; i.e. what does lambda V[I].Q mean, for instance, for the I element
of the vector V? There is, in fact, an facility native to the lambda calculus
for addressing this very issue; the equivalence
   lambda V[I].Q = (V[I] = [], Q)
   = (V = (lambda J.(I == J? []: V[J])), Q)
   = (lambda V.Q) (lambda J.(I == J? []: V[J]))
which effectively treats the structured object as a function applied to its
"designators" (here, the index [I]) and the assignment as a partial update to
the function itself.

A good translation method will be one that treats *all* instances equivalent
to this type of statement the same (no matter whether they come from an
assignment to a designated subobject or not) while avoiding any unnecessary
structure-wide copying of unchanged elements.

A proper account of how pointers fit into this meshes completely with the
question of how the inheritance and object/subobject hierarchies are defined
in the language. To each object type T, the corresponding pointer operator *
is actually a universal object (i.e. the type-cast pointer operator *(T *)) so
that if P is a pointer variable, then P is the designator that bears the same
relation to *P that the index I bears to component V[I]. This fits snugly into
the type/subtype hierarchy in such a way that if T' is a derived from T, then
the operator *(T' *) is a subobject of *(T *).

Back to comp.compilers | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Writing A Plain English Compiler "Gerry Rzeppa" <gerry.rzeppa@pobox.com> - 2014-11-04 15:50 -0600
  Re: Writing A Plain English Compiler Joshua Cranmer 🐧 <Pidgeot18@verizon.net> - 2014-11-05 00:54 -0600
    Re: Writing A Plain English Compiler "Gerry Rzeppa" <gerry.rzeppa@pobox.com> - 2014-11-06 18:52 -0600
      Re: Writing A Plain English Compiler Joshua Cranmer 🐧 <Pidgeot18@verizon.net> - 2014-11-07 22:54 -0600
        Re: Writing A Plain English Compiler "Gerry Rzeppa" <gerry.rzeppa@pobox.com> - 2014-11-08 02:41 -0600
        Re: Writing A Plain English Compiler "Gerry Rzeppa" <gerry.rzeppa@pobox.com> - 2014-11-08 03:46 -0600
          Re: Writing A Plain English Compiler "BartC" <bc@freeuk.com> - 2014-11-09 01:16 +0000
            Re: Writing A Plain English Compiler "Gerry Rzeppa" <gerry.rzeppa@pobox.com> - 2014-11-10 14:37 -0600
            Re: self-hosting, was Writing A Plain English Compiler Richard Hable <portempa@aon.at> - 2014-11-11 19:50 +0100
              Re: self-hosting, was Writing A Plain English Compiler "BartC" <bc@freeuk.com> - 2014-11-11 23:33 +0000
                Re: self-hosting, was Writing A Plain English Compiler anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-11-12 08:46 +0000
                Re: self-hosting, was Writing A Plain English Compiler "BartC" <bc@freeuk.com> - 2014-11-12 11:15 +0000
              Re: self-hosting, was Writing A Plain English Compiler anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-11-12 08:40 +0000
    Re: Writing A Plain English Compiler "BartC" <bcas@freeuk.com> - 2014-11-07 11:36 +0000
    Re: Writing A Plain English Compiler George Neuner <gneuner2@comcast.net> - 2014-11-07 16:23 -0500
      Re: Writing A Plain English Compiler Richard Hable <portempa@aon.at> - 2014-11-08 17:22 +0100
      Re: Writing A Plain English Compiler Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2014-11-08 10:48 -0600
        Re: language design models, was Writing A Plain English Compiler George Neuner <gneuner2@comcast.net> - 2014-11-09 14:30 -0500
          Re: language design models, was Writing A Plain English Compiler "Gerry Rzeppa" <gerry.rzeppa@pobox.com> - 2014-11-10 03:29 -0600
          Re: Writing A Plain English Compiler Tomasz Kowaltowski <tk@ic.unicamp.br> - 2014-11-10 09:13 -0200
            Re: Writing A Plain English Compiler "Gerry Rzeppa" <gerry.rzeppa@pobox.com> - 2014-11-10 17:19 -0600
      Re: matching tasks to languages, was Writing A Plain English Compiler Gene Wirchenko <genew@telus.net> - 2014-11-10 15:37 -0800
    Re: Writing A Plain English Compiler Martin Ward <martin@gkc.org.uk> - 2014-11-10 22:56 +0000
  Re: Writing A Plain English Compiler "BartC" <bcas@freeuk.com> - 2014-11-07 11:39 +0000
    Re: Writing A Plain English Compiler "BartC" <bc@freeuk.com> - 2014-11-08 00:35 +0000
  Fundamentals for a Compiler and Language (was: Writing A Plain English Compiler) federation2005@netzero.com - 2014-12-29 13:30 -0800

csiph-web