Re: Writing A Plain English Compiler

"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

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