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

Groups > comp.compilers > #1412 > unrolled thread

Writing A Plain English Compiler

Back to article view | Back to comp.compilers

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#1434

Tomasz says:
This discussion reminds me of the history of mathematical notation.
The notation we use today was adopted mainly in the 17th century and
contributed to rapid development of mathematics. Before that equations
were usually written in "Plain Latin" or "Plain Arabic", or ""Plain
Whatever". I don't think anybody would recommend going back ;-).

Gerry replies:
We agree that mathematical notation is useful in its place; that's why we
believe the "ultimate" programming language will be a hybrid of different
syntaxes (and graphics, as well) as described here:

https://www.indiegogo.com/projects/the-hybrid-programming-language/x/8950932

But we also think that starting with mathematical notation and "bubbling it
up" to the rest of a programming language is and was a mistake.
""Graphics_Lib.ClrScrn(0x000000)" simply can't compete with "Clear the
screen." And most of most programs fall are not mathematical in nature at
all. Most of most programs are things like "move this" or "draw that" or
"put this on the disk". It is our belief that if programming was invented by
poets (with a little help from mathematicians) -- rather than being invented
by mathematicians with an utter disregard for poets -- we'd be further along
the road to computers like the HAL 9000 (which the poets thought would
arrive in 2001).

But things are looking up. We've got Apple's SIRI, Wolfram's ALPHA, Nelson's
INFORM, Microsoft's CORTANA, and now Amazon's ECHO. And, of course, Plain
English!
[This argument has gone about as far as it's going to. Back to compiler design,
please. -John]

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

#1435 — Re: matching tasks to languages, was Writing A Plain English Compiler

On Fri, 07 Nov 2014 16:23:06 -0500, George Neuner
<gneuner2@comcast.net> wrote:

[snip]

>I frequently am amazed at the contortions Java programmers go through
>to solve problems within the restrictive OO model.  IMO, "Design
>Patterns" was an admission that too many programmers couldn't use Java
>to solve routine programming problems.

     I bounced off "Design Patterns" myself.  It seemed that the
authors would rather do anything but simply instantiate an object.

     I had a uni assignment that I tried to solve using OO.  As I
worked my way around it, I realised that OO was not going to happen.
Oh, I could have done it, but the code would have been much longer and
quite difficult to validate/debug.

>[That's as much an indictment of the lack of CS education among
>programmers.  Java - somewhat successfully - tried to pander to less
>educated programmers by making simple things simpler, but in doing so
>it made solving many real problems more complicated.]

     I lost a few hours to this on another assignment, because ints
could not be unsigned.

[snip]

Sincerely,

Gene Wirchenko

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

#1433

"By relieving the mind of all unnecessary work, a good notation sets
it free to concentrate on more advanced problems, and in effect,
increases the mental power of the race." -- Alfrid North Whitehead

Mathematicians have been slowly and painstakingly developing new
and better notations over the centuries. Each new development
has increased the mental power of the race. In effect,
each advance in notation allows human beings to think new thoughts.

Before the invention of algebraic notation, mathematical problems
had to be expressed in long, complex sentences in natural language.
My father was a carpenter and was taught how to compute the radius
of a circle, given the length of a chord and the "rise"
(the perpendicular distance from the middle of the chord
to the edge of the circle) as follows:

"To the square of half the chord, add the square of the rise.
Divide this sum by twice the rise and the quotient is the radius".

This is a reasonable plain English description of the computation:
but I somehow doubt that it would be accepted by the Plain English
compiler! But if you want to take in the whole computation at a glance,
in order to analyse or manipulate it, then the mathematical notation
is far superior:

          2    2
R = (C/2)  + r
     -----------
         2r

When the "Revised Report on the Algorithmic Language Algol 60"
was published, researchers immediately recognised the superiority
of the notation and started using it (in preference to natural language)
as a way to describe algorithms to each other: even before
the first Algol 60 compilers appeared.

Each new programming paradigm: functional, parallel, dataflow,
declarative, object-oriented and so on, has added to the mental
power of the race. *Every* programmer should learn at least
one example of each of the above types of language.
For example: even if you are not writing in a functional programming
language, if your problem has a natural functional programming
solution, then you will write a much better implementation
in your target language if you already know functional programming.
Your mental power has been increased by your knowledge
of functional programming.

On the other hand, if you only program in "mutilated English",
your mental power will hardly increase at all!
As the saying goes:  if the only tool you have is a hammer,
you treat everything as if it were a nail.

On 05/11/14 06:54, Joshua Cranmer wrote:
> Once it has slowed to one or two seconds between pops, take it out of
> the microwave.

Joshua claims that this is an example of event-drive programming,
but Gerry disagrees and claims that the program can be expressed
procedurally, in Plain English, as:

Loop. If it not has slowed to one or two seconds between pops, repeat.

Apart from the rather clumsy construction ("If it not has ..."),
this is an excellent example of the problems caused by ambiguity
in natural language. What does "has slowed to one or two seconds
between pops" mean? Presumably, we wait for a pop, note the time,
then wait for the next pop, compare the times and if the time
is less than one second, then we can assert that it has not yet
"slowed to one or two seconds".

Now suppose that pops come at a rate of less than one per second
and then stop altogether. We will be stuck in the loop,
waiting for the next pop, until our popcorn sets fire to the microwave!
Clearly we need to wait until *either* the next pop *or*
more than one second (or is it two seconds?) have passed.
This is an event-driven process, where one event is a timeout,
and another is a "pop".

But a slightly more complex cookery example will better illustrate
that a procedural description is not always the most natural.
Suppose you want bacon and scrambled eggs for breakfast, and want them
both nice and hot at the same time. The most natural description
is to describe how to scramble eggs, then separately describe how
to grill bacon, then state that the two operations should be carried
out in parallel. The procedural description involves an inner loop
which repeatedly checks the eggs, checks the bacon, terminates when both
have cooked. But it has tp check only the eggs if the bacon
has already cooked, and check only the bacon if the eggs have
already cooked. The two simple processes become intemingled into
a single, much more complex, process.

Bartc says,
 > to create sizeable programs that work reliably, I think you
 > need to use a more stylised and disciplined way of writing
 > instructions.

To which Gerry replies:
 > We offer our prototype system as proof that is not so.

I think by a "sizable program", Bartc means something a *little*
larger than six source files containing a totel of 19,731 lines
of code. To be precise: something too large to be implemented
and maintained by a single programmer. At that point,
you do not want every programmer writing in their own private language:
even if each language is a small, highly stylised subset of English.
Making each private language a subset of English will only
increase the confusion, due to the inherent ambiguity of English.
For example, one programmer decides that "foo is between bar and baz"
means that bar <= foo <= baz. Another decides
that "between" should exclude the end points of the range.
If they need to work on each other's code, they will
get very confused! Similarly in English "or" can mean
"inclusive or" or "exclusive or" depending on the context.

I would argue that each different class of "sizable programs"
(those which require a team of programmers and millions of lines
of code) should actually be implemented in a different language.
A language which is specifically designed for implementing
"that type of program". For example: a program transformation system
should be implemented in a language designed for writing
program transformations. So when I started re-implementing
the FermaT program transformation system from scratch,
I first designed the MetaWSL programming language.
The system currently consists of around 3MB of MetaWSL code,
which compiles into 15MB of highly complex C code.

I wrote what I believe to be the first paper on this approach
to programming large systems back in 1994:

"Language Oriented Programming", Martin Ward,
Software--Concepts and Tools, 15, pp 147-161, 1994, ISSN 0945-8115
http://www.gkc.org.uk/martin/papers/middle-out-t.pdf

Since then, the approach has been taken up by quite a few people
under the terms "Language workbenches" (Fowler), "Intentional
Programming" (Microsoft), "Concept Programming" (XL),
"Dielecting (REBOL), "Model Driven (Software) Development",
and, Domain Specific Languages. For example, Google's map/reduce
language is specifically designed for writing massively parallel
distributed systems.

Designing a new language which is a genuine improvement
on all existing languages (for implementing a particular
class of programs) is hard work: and the task should
not be underestimated. However, the results of a really
good design can be applied to many programs
and the benefits outweigh the effort many times over:
a really good design for a new Domain Specific Language
actually can increase the mental power of the race!

--
			Martin

Dr Martin Ward STRL Principal Lecturer & Reader in Software Engineering
martin@gkc.org.uk  http://www.cse.dmu.ac.uk/~mward/  Erdos number: 4
G.K.Chesterton web site: http://www.cse.dmu.ac.uk/~mward/gkc/
Mirrors:  http://www.gkc.org.uk  and  http://www.gkc.org.uk/gkc

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

#1416

"Gerry Rzeppa" <gerry.rzeppa@pobox.com> wrote in message
> Having worked with a wide variety of traditional languages, and having
> written a number of compilers together, we knew that a practical
> procedural
> programming language could be concocted with just five types of
> statements:
>
> 1. Type definitions;
> 2. Global Variable definitions;
> 3. Routine Headers;
> 4. Conditional Commands; and
> 5. Unconditional Commands.

> And that, I think, is enough for now. Questions? Comments? Anyone? Anyone?
> Bueller?

I have problems with the whole approach.

For a start, anyone considering using such a language probably wouldn't be
concerned with type definitions. If it is meant to make programming simple
and accessible, then dynamic typing is expected (or more likely, someone
won't even think about that aspect; it should just work).

But then, even with a more informal language, there's only so much that can
be done, because to create sizeable programs that work reliably, I think you
need to use a more stylised and disciplined way of writing instructions. Any
free-format English would get in the way of that.

(I assume this syntax would just be a front-end to a conventional language
and conventional compiler, as your list suggests, and is not some
super-advanced AI project that can understand anything.)

Using syntax that looks like written English sounds attractive, and might be
suitable for some kinds of command-line interaction ('kill dwarf with axe'),
but I'm not sure it would be taken seriously for real programming.

Maybe, a tool can be used to translate conventional syntax into the English
style you propose, which would be fun, but I don't know if it warrants
creating a whole new language. Not if it doesn't otherwise do anything new.

--
Bartc
[Back in the 1970s there was a vogue for extensible languages, in
which you could add new syntax on the fly, by adding new BNF to the
underlying grammar.  They all disappeared, because what happened was
that no two programs were written in the same langauge and nobody
could read them.  Now we have OOP, where the syntax doesn't change,
but you can add lots of new types and semantics to go with them.
-John]

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

#1421

"BartC" <bcas@freeuk.com> wrote in message news:14-11-008@comp.compilers...

> (I assume this syntax would just be a front-end to a conventional language
> and conventional compiler, as your list suggests, and is not some
> super-advanced AI project that can understand anything.)
>
> Using syntax that looks like written English sounds attractive, and might be
> suitable for some kinds of command-line interaction ('kill dwarf with axe'),
> but I'm not sure it would be taken seriously for real programming.
>
> Maybe, a tool can be used to translate conventional syntax into the English
> style you propose, which would be fun, but I don't know if it warrants
> creating a whole new language. Not if it doesn't otherwise do anything new.
>

> [Back in the 1970s there was a vogue for extensible languages, in
> which you could add new syntax on the fly, by adding new BNF to the
> underlying grammar.  They all disappeared, because what happened was
> that no two programs were written in the same langauge and nobody
> could read them.  Now we have OOP, where the syntax doesn't change,
> but you can add lots of new types and semantics to go with them.
> -John]

They haven't all disappeared; there is still Seed7 (sometimes appearing in
this group).

Although this language supposedly has a user-extensible syntax, I've
never seen source examples that look like anything other than Seed7,
so perhaps my worry that everyone will invent a different look isn't
justified. (Or maybe I just haven't seen fully customised versions of
it; or haven't recognised them!)

With OOP, I don't really agree with 'language building' features being
used for everyday coding, at least not to the extent they are
available in C++ for example. It makes everything a lot more
complicated (language and compiler), and I think encourages people to
use them unnecessarily.

My point of view is a little unusual however, because I use my own
compilers, so adding a new, fully overloaded type for example, is
easily done by changing something in the compiler; that means the
ability to do that directly in the language is not a priority.

Maybe there is a need to do these things in an easier manner, but
without going so far as allowing a free-for-all as some languages do.

--
Bartc

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

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

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

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.compilers

csiph-web