From: Kragen Sitaker (kragen@pobox.com)
Date: Wed Sep 27 2000 - 18:25:07 PDT
Koen Holtman writes:
> On Wed, 27 Sep 2000, Tony Finch wrote:
> > a dogs dinner, compilers for those languages have a fairly limited
> > understanding of the code they are compiling . . .
>
> Um.. I have to disagree here. [aliasing sucks]
> . . . the compiler will first
> have to prove by some analysis that all pointers point to different stuff.
> But that is usually impossible, especially if some of the pointers were
> function arguments.
It is usually not impossible; if the programmer didn't have some kind
of informal proof in mind when they were writing the code, it's
probably wrong anyway.
> What is really needed to improve compilation and bug finding, if you don't
> want to thow away pointers, object handles, or those pesky recursive
> datastructures, is language constructs which allow the programmer to
> express `these two pointers/handles/etc that were passed into this
> function are guaranteed to point to different storage', and also `this
> object is owned by that object and the ownership relation is nowhere
> cyclic'.
"owned by"? To optimize garbage collection, you mean?
Clean has a type system that includes uniqueness annotations, which
indicate that a particular reference is the only reference to its
referent, which is similar to what you're describing. The latest draft
C standard has a type annotation that is exactly what you're
describing.
Elimination of mutation keeps aliasing from being a correctness
problem; Clean's uniqueness annotations are a way to help the compiler
optimize formally non-mutating operations into real mutating operations
which are more efficient.
> > State-of-the-art compile time analysis and bug
> > spotting relies on languages with precise definitions and
> > sophisticated type systems, which tend to discourage less
> > mathematically-inclined programmers.
>
> I'd say Java has about as precise a definition as you can get, possibly
> also a sophisticated type system. Don't see too many people discouraged
> by that...
Java's definition is purely informal and very long, running to several
hundreds of pages of English, which means that it almost certainly
contains numerous errors. Similarly, Java's type system is fairly
primitive and simultaneously quite arcane.
I'm not aware of any languages in common use with precise definitions,
but Haskell and ML have sophisticated type systems. There is what I
think might be a precise definition of a prehistoric version of Haskell
at http://www.haskell.org/definition/long-semantics.ps.gz.
The ICFP'00 programming contest task included implementing a language
precisely defined on pages 2 through 4 of
http://www.cs.cornell.edu/icfp/task.pdf.
> Bugs are more fundamental than objects.
:)
Other things that are more fundamental: closures, routines, basic
blocks, lambdas, words, bytes, machine instructions, register
transfers, combinators in general, S and K combinators specifically,
and bits. It all depends on which way you slice it. :)
> On Mon, 25 Sep 2000, Jim Whitehead wrote:
> > Yes, software development has far to go. On the other hand, I can think of
> > few examples where it is possible to purchase a product that contains
> > person-centuries of product development for around $100.
>
> Lots and lots of products have person-centuries of development behind
> them. Starting with many agricultural products...
Yes. Looking around me, I see a piece of laser-printed paper, a font
being used to render characters on it, a character set being used to
encode words, a language that encodes meaning in words, a pop-up
safety-button bottle lid stamped from metal by a machine made by Dayton
Reliable Tool or Dayton Systems Group (each of whom invest a
person-century of development into can and bottle lids every year or
two), a White Pages holding up my monitor listing millions of Seattle
residents, a pair of hands on my keyboard evolved over several billion
years (not person-years), a plastic bag made of high-density
polyethylene squished into sheets three thousandths of an inch thick.
And that's just what's on my desk at the moment. None of them cost me
even as much as $100.
More ephemeral things, which more closely correspond to software,
include the geometry used to render the text on the page, the business
culture that supports the publication of the magazine that paid Beth
Kwon to compose the words that appear on the page, the economic system
that makes it possible for DSG or DRT to make the machines that stamped
the bottle lid, the petroleum industry that spends person-centuries
every month lobbying governments and that supplied the raw materials
for the plastic bag, the civic culture that makes it possible for me to
sit here at my computer without being pestered, etc.
> Of course, person-centuries of product development as a monolithic piece
> of intellectual property owned by a single commercial entity is another
> matter. That would have been rare in the middle ages.
It's rare today, although it threatens to become more common.
> Anyway, the question of whether software will turn into a science is about
> as relevant as the question of whether architecture will turn into a
> science.
Excellent point. Some bits of software design could become more
scientific, and they have. The interesting thing is that they
disappear into the computer when they are systematized; all that is
left for the humans to do is the artistic part. That's why it took me
fifteen minutes to write diff.cgi last night --- a program that fetches
two documents from anywhere in the world (by URL) over a worldwide
computer network and displays on the screen of a user anywhere in the
world a report on exactly where they differ.
The original post, from somebody's web page:
> 1. Software engineering keeps discovering "deeper" abstractions,
> that once understood, advance the field. Is there a "deepest"
> layer we cannot go beyond? What is it?
Perhaps this question would seem less confused if the author described
two abstractions discovered at different times and explained how they
thought the more recent one was "deeper". As it stands, I disagree
with the premise. Software engineering doesn't discover abstractions;
it writes software and formalizes processes for doing so. Computer
science discovers abstractions, and some of them are deeper than
others, in that they unify more things. But the oldest abstractions
--- e.g. lambda --- are generally the deepest ones.
> 2. Software has continually lagged behind hardware in things
> like cost curve, ease of use and standardization. What
> discoveries would it take for software to surpass hardware, or
> what is the reason this is impossible?
Software is already way cheaper, way easier to use, and way more
standardized than hardware; hardware is only cheap and easy to use
because software runs on it so the hard parts can be done in software.
The difference is that hardware is getting better, and fairly fast,
while software is arguably getting worse. (Although the better
software is becoming more widespread as the hardware it needs to run
gets cheaper. E.g. Unix is better than DOS, GUIs are arguably better
than CLUIs, garbage collection is better than explicit memory
management.)
> 3. Software is still an art, not engineering. It's so
> intractable we are essentially living in the dark ages, like
> before Copernican Theory (the planets revolve around the sun),
> before Einstein's theories of relativity and before Euclidean
> Geometry. Is there a collection of software theory that will
> suddenly turn art into science?
Questions that confuse engineering with science are too confused to be
worth answering.
I think I answered this earlier; when software problems become
tractable, we encode the solutions in software so we don't have to do
them anymore.
> 4. Will software/hardware be able to eventually pass the Turing
> Test, or will this require a biotech approach?
Software has already passed the Turing Test; bots on IRC and MUDs have
frequently fooled people into thinking the bots were human, often for
hours.
Biotech is just more hardware.
> 5. Will software itself disappear, replaced or absorbed by other
> fields that we know not yet of?
Software --- that is, algorithms --- are as ancient as thought; we only
recognized them as distinct from other kinds of thought early this
century, due to the work of Hilbert, Post, Kleene, Church, Turing,
Rosser, Curry, Goedel, Turing and others, and, of course, due to the
slightly later invention of the programmable computer.
> 6. Why is software development so hard to learn?
Thinking is hard. Thinking about thinking is even harder. Perfection
is hard. Successful software development consists of perfect thoughts
about thinking.
> Is there some catalyst or approach that would fundamentally change this?
Amphetamines help, I've heard. Caffeine definitely helps. Lack of
distractions helps. Sleep helps. Immediate and reliable feedback that
your software, and therefore your thoughts, is wrong, helps a lot.
Developing habits that will tell you when your software is wrong ---
like writing automated tests --- helps a lot.
> For example there might be 5 new words to add to the English
> language. These would be taught at a young age. Programming
> languages and tools would use these words/concepts, making the
> transistion to thinking about programming nearly no transition
> at all. The entire population could program....
Nearly the entire population who uses computers does, in fact, program;
spreadsheets help a lot.
I doubt that the problem is that programming concepts are harder to
learn when you're old, although systematizations of programming
concepts help a lot; SICP, for example.
> 7. No software language has survived indefinitely, other than
> 1's and 0's. Will there eventually be one that does, much like
> English seems to be doing?
"1's and 0's" is a character set, not a language; a language consists
of a character set, a syntax, and a semantics.
English's indefinite survival is an illusion. English in any
recognizable form is only a thousand years old. English that is
transparently comprehensible to a modern speaker is perhaps only a
century old. English in its current form didn't exist yesterday.
The lambda calculus is older than the programmable computer, and it
survives unchanged today.
FORTRAN dates from 1956. Lisp dates from 1958. Algol dates from
1960. COBOL dates from before 1960, too. C dates from 1973 or so.
> 8. Are there software particles more fundamental than objects?
See above.
> 9. Is it possible to create a language and IDE which rejects any
> attempts to insert defects, and is productive?
No, as another poster has noted, that's solving the Entscheidungsproblem.
> 10. Will it become possible to prove any system has no defects?
Do you mean, "will it become possible to prove that at least one system
has no defects"? If so, the answer is trivially yes. Do you mean,
"Will it become possible to prove that all systems have no defects?" If
so, the answer is trivially no, except in useless formal systems that
prove bugs correct, because some systems have defects. Do you mean,
"Will it become possible to prove all correct systems correct, but not
any incorrect systems?" If so, that's the Entscheidungsproblem, and
Goedel and Turing answered this question in 1931 and 1936: NO.
There's also the more practical consideration that systems can be
perfectly formally correct and still useless.
> 11. Currently computerdom can be physically partitioned into
> hardware and data. Will any additional top level partition(s) be
> added? For example, what if some self-evolving programs need to
> never be turned off. Would this be a new partition?
Hardware will disappear, leaving only data, encoded as physical states
of molecules.
> 12. Are 1's and 0's the optimum base digital data standard? For
> example, why not four values, like DNA?
Optimality is meaningless in a vacuum. Which is better, red or blue?
> 13. Will something like "graylean" augment boolean? A graylean
> can have three values - true, false and somewhere in the middle
> (black, white and gray). This is not the same as true, false or
> null, because null means the boolean itself is undefined.
"ternary". It's been done; at the moment, I think binary is better for
most things.
"graylean" will make people think of Gray code, which is not what
you're talking about at all.
> Mature societies, such as China, have long approached issues as
> black, white or gray, unlike the West which sees issues mostly
> in black and white.
The child does not know what is right and what is wrong. The youth can
distinguish between right and wrong. The aged understand when a right
act in another context can become wrong and which right acts are more
right than others. This is true of the American aged and the Chinese
youth both.
This is fairly unrelated to encoding information in strings of symbols
from a finite alphabet.
> 14. Will the three rules of solid (what's the proper term?)
> programming - sequence, decision and loop - be replaced by a
> whole new approach, perhaps allowing a whole new language
> generation? What is it?
The proper term is "structured".
Sequence, alternation, and Kleene closure go back to the theory of
finite automata. The elevation of this trinity to the status of dogma
was merely a historical reaction against historical forces, and was
never universal. Today, we commonly use control-flow structures like
exit-in-the-middle loops, nonlocal exits (throwing exceptions, for
example), alternation with null (if (x) { y(); } with no else), and
recursion.
There are other good ways to structure code; for example,
combinator-graph reduction and higher-order functions. They are wrong
choices when the most important aspect of the code's behavior is its
control flow.
> 15. Two or more engineers will never arrive at the same
> identical solution to anything but a trivial software problem.
> Why? Will we discover ways to make software problem solving 100%
> convergent? What are they?
As I answered to the 'art vs. scenginienceering' question, when the
process of solving a problem becomes this systematic, we encode the
knowledge of how to solve the problem into software and move on to
other things.
--
<kragen@pobox.com> Kragen Sitaker <http://www.pobox.com/~kragen/>
Perilous to all of us are the devices of an art deeper than we ourselves
possess.
-- Gandalf the Grey [J.R.R. Tolkien, "Lord of the Rings"]
This archive was generated by hypermail 2b29 : Wed Sep 27 2000 - 18:28:07 PDT