Re: Is Lisp a Blub?

Don Geddis <don@xxxxxxxxxx> writes:
OK, so now the question. Common Lisp was formalized quite some time ago;
ANSI CL a bit later, but without many radical changes. Are there tools now
known in the abstract space of programming language design that "ought" to be
part of Common Lisp? That, if there had been an ANSI CL 2 effort, would
surely have been strongly suggested to get added to the language?

Regular expression matching ...

Static typing is another interesting corner case....

And the pattern-matching programming idea got me thinking of unification...

So I'm wondering about language expressions that are so fundamental to
describing computation, that they "ought" to be part of the vocabulary of any
advanced programmer.


The concept of a computer programming language is pretty
much played out. The progression through machine code,
assembly, C, Lisp has traversed a conceptual space all the
way to its boundary. It is time to strike out in a new
direction.

The two issues are

1)Programming is the boundary activity, separating the
manual from the automatic.

2)The conflict between writing clear, simple code and
writing efficient code.

Think of the document flow in an organisation. There are
discussions with customers. Requirements are
analysed. Software products are proposed and discussed. Lots
of documents are written and rewritten.

Think about a change to the requirements. The author of the
software product proposal responds to the the change by
thinking through its implications and manually amending his
proposal.

Constrast the relationship between source code and assembler
listing with the relationship between requirements and
proposal. When the source code changes the programmer
merely reruns the compiler. The production of documents
``below'' the level of the computer programming language has
been automated.

A computer programming language marks a boundary between the
manual and the automatic and the goal of ``improving'' a
computer programming language is to shift this boundary
higher up the business, automating what was previously
manual.

Let me make this more concrete with an admittedly
hypothetical example. A finance company must respond to tax
changes by changing the programs that calculate tax. It
wants to obtain the taxation statutes in machine readable
form and run a program that extracts the new rates and
updates the code. If the tax changes are just adjustments to
numerical parameters this is within the grasp of current
technology, but when for example, Gordon Brown splits the
tax on cars into bands according to fuel efficiency, the
code base much change more radically.

The finance company wants to "program" its computers in a tax
law programming language. Realistically I'm imagining an
extra level of complication. There is a hairy program,
perhaps in Common Lisp, that compiles TLPL (my hypothetical
Tax Law Programming Language) into Common Lisp. This is the
standard idea of a domain specific programming language and
Common Lisp, with its defmacro, is about as good as it gets.

Attempts to think about improving computer programming
languages falter because they conceive of the issue in terms
of writing programs, but the goal is the opposite of
this. The goal is to NOT write programs. Programming in the
conventional sense is to be automated away. To put it in
boring terms, programming's future is to split into three. One
part is writing compilers for languages closer to the
business needs of the customers who pay the bills. Another
part is using those languages. The third part is ``paddling
up waterfalls''. A waterfall model with the compiler writers
presenting the completed language to those who must program
in it is implausible.

So far I articulated my vision in familiar language. Instead
of application programmers writing applications we have
compiler writers writing compilers, application programmers
writing application in application specific languages, and
some guys paddling up waterfalls. My vision is vague.

It is also incoherent as written. The term "compiler writer"
still has its old meaning, writing programs that turn C or
CL into assembler. I should not be reusing it to mean
something else. Much the same problem applies to my use of
the phrase "application programmer". It is only the job
description "waterfall paddler" that is honest in its
novelty and vagueness.

To see the difficulties, think about Ruby on Rails. Is it
created by compiler writers? Not really. What do power users
do with it? I don't think it is being leveraged to build
more elaborate websites. I think that canny programmers are
using it to spend less time coding and more time thinking
about how to make money.

Lets call the three roles

1)Business programmer: he writes in the domain specific
language, but spends more time understanding customers
than he does understanding computers

2)Transformation programmer: Like a compiler writer except
that Common Lisp is the object language not the source
language

3)Waterfall paddler: My lack of explicitness here reveals a
major weakness in my thinking. This is a post to a
newsgroup, you haven't paid $100 for a book :-)

The Business Programmer is writing clear, simple code. Perhaps
the naive interpretation of the code is as an inefficient
algorithm that runs too slowly, but the business programmer
has no time to spend rewriting it to run faster. He is out
of the office talking to customers. When he comes back he
will change it to keep up with a fast changing world, not to
fix efficiency problems.

What about the Transformation Programmer? Does he rewrite
the code himself to make it run faster? Absolutely
not. ``Programming'' = ``writing code'' is what we are trying to
eliminate, or more precisely automate. Remember that
tomorrow the Business Programmer will change key Business
Declarations. All the effort put into manual tuning will be
lost. The Transformation Programmer aims to come up with a
transformation that turns today's Business Declarations into
efficient code, but is not so tightly tuned that the
transformation breaks tomorrow. The waterfall paddler tries
to optimise a tricky trade-off. The transformations must be
general enough to survive tomorrows changes, but if this
vision is to be practical them must be done in a way that
keeps well away from attempting to build a general artifical
intelligence. Some-one must distinguish the likely changes
from the unlikely changes in a way that permits a trade-off:
being less prepared for unlikely changes buys being more
prepared for likely changes.

Technology and Implementation
-----------------------------

I've recast the problem. It is no longer about creating
better, fixed languages for writing applications. It is
about better tools for writing optimising
compilers. Especially about having more flexible tools so
that an efficiency problem is not solved by changing the
source, but by adding extra transformations to the compiler
on an as needed basis.

How might this be possible. The work that stikes me as
exciting and mysterious is that of Futamura.

http://www.cubiclemuses.com/cm/blog/archives/000419.html

If the transformation programmer's tool chest includes a
reasonably powerful language (RPL) that comes with a partial
evaluator and a native code compiler, he uses it to write an
interpreter for the business language, then uses the first
futamura projection to get a native code compiler for free,
by partially evaluating the business declarations with the
interpreter to get RPL that can be compiled to native code.

I think that this kind of staged approach covers the issues
of pattern matching and static typing.

It is easy enough to write code that matches data structures
at run time. So you can write an interpreter for a pattern
matching language. You can even write macros that expand to
calls to a pattern matching routine, so you can add pattern
matching to a compiled language and only take the
interpretive performance hit in code that actually uses the
pattern matching. It you write the pattern matcher in a
language for which you have a partial evaluator, you can
partially evaluate the pattern matching code with the
pattern list at macro expansion time and get full
compilation.

I think that something similar happens with static
typing. Much of the type checking overhead is removed by
partial evaluation, because the types are independent of the
actual data. One can even regard the elimination of type
checks as the criteria for whether the code is well typed.

Notice that if the Business Programmer wants a more
expressive type system or more elaborate pattern matching,
the Transformation Programmer is in a position to offer this
because he is hacking an interpreter for which he has a
partial evaluator.

There are interesting issues with regular expressions. My
Perl book gives the example of matching

"aaaaab" against /a*a*a*a*a*[b]/

and warns that leaving of the "b" and just matching against
"aaaaa" will take too long to fail. This is the kind of
conflict between clarity and efficiency that makes
programming an all consuming technical activity. It does
strike me that there is something wrong here. Regular
expressions are a subset of context free languages and the
Earley algorithm parses context free grammars in at worst
cubic time, so I don't understand Larry Wall's hint these
kinds of expression take exponential time.

I've come across this issue before with a computer
programming language called REFAL. It is very attractive,
because the built-in pattern matching subsumes most
looping. Unfortunately it does not live up to its promise
because there are various ways that clear code can be unbearably
inefficient. The manual has to go into some detail of how
certain obvious ways of matching have quadratic performance
and how to write non-obvious code to get linear performance.

In future the Business Programmer will not obfuscate the
Business Declarations to obtain performance, he will get the
Transformation Programmer to fix the regular expression
matching engine (either with a better algorithm or by adding
special case code to handle common troublesome
situations). Transformations from quadratic to linear will
be done by adding transformations to the optimiser, not
obfuscating the source code. (The source code might well
need declarations saying that linear performance is needed in
one parameter of a function but not in another. It might
even need to include a hint about how the transformation is
to be done.)

The big obstacle to this vision is that deep within the
partial evaluator lurks a theorem prover, and it is the
strength of this theorem prover that determines whether the
partial evaluation of an interpreter with source is actually
compiling.

I'm intrigued by what I have read of ACL2. It seems that it
is not very smart "out of the box". You ask it to prove a
theorem and it cannot manage it. You ask it to prove a well
chosen lemma and it manages the lemma. Now the lemma is
added to its stock of theorems, and when you return to the
main theorem it is able to prove it automatically. One
feature of this kind of dialogue is that you cannot break it
by accidently teaching it a false lemma. You can only build
its stock of theorems incrementally by getting it prove them
for itself and working up.

What fascinates me is that I'm not looking for artificial
intelligence. I'm only expecting to automate processes that
are currently routinely done manually. I'm not expecting
automated tools to come up with a program transformation
that the Transformation Programmer would not have done
himself in the old days. I'm imagining that the
Transformation Programmer doesn't write transformations in
the style of defmacro function bodies. Instead he comes up
with a series of lemmas that get the ACL2 like theorem
prover inside the partial evaluator up to the point that it
can carry out the transformation. There is then a good
chance that when the Business Declarations change, the
theorem prover will be able to prove the trivial variant
needed to optimise the new code all on its own.

So here is a radical vision for what computer programming
looks like in 2027.

The Business Programmer writes clean, clear code. Probably
declarative code. It might look a lot like Prolog, but
actually it will be very different. Naively written Prolog
often triggers the backtracking search producing
exponentially awful programs. The Business Programmer will
not personally have to worry about this and will never
obfuscate his code for efficiency.

The necessary transformations are never done manually. The
Transformation Programmer engages in a Socratic dialog with
the theorem prover inside the partial evaluator, leading it
to see how to transform the code to make it efficient.

Source control means both the Business Declarations and the
Lemma List. Today creative engineers must consider the
software/hardware trade-off. In future the Waterfall Paddler
must design the domain specific language by trading off the
complexity of the Business Declarations against the length
of the Lemma List and the difficulty of constructing it.

Now I can explain why I am not very interested in improving
Common Lisp. It is not that I think that Common Lisp is the
last word in computer programming languages. Far from it. I
have the opposite concern. I look forward to radical
developments. The tool chain underpining future languages
might well be written first time around in Common Lisp, but
I look forward to those languages being very different
indeed. For example the semantics of partial evaluation
would be part of the specification. If the Lemma List is to
be part of the program source, then the specification of the
language would have to include minimum capabilities for the
theorem prover inside the partial evaluator and say how to
dialogue with it. That is not sounding like anything one can
reach by further development of Common Lisp.

Is Common Lisp a Blub? It will be.

Alan Crowe
Edinburgh
Scotland
.

Relevant Pages

  • Re: Python or PHP?
    ... > every language here and there more ways to do something. ... The best the programmer can do, as you imply, is to ... parse out into proper perl expressions. ... > lists, dictionaries, etc. etc. ...
    (comp.lang.python)
  • Re: Python or PHP?
    ... >> every language here and there more ways to do something. ... The best the programmer can do, as you imply, is to ... I am curious of a list of extraneous methods in Perl (more about the ... I just had a glance on Python, ...
    (comp.lang.python)
  • Re: The War On HLA
    ... Take a look at the HLA compile-time language. ... Macros can be abused just like any other language feature. ... I find it amusing, however, that HLL programmers (e.g., Delphi, ... > feature is left to the programmer to invent his own uses for. ...
    (alt.lang.asm)
  • [LONG] Re: Why code completion and early error checking are needed
    ... > the programmer who wants such features. ... the guiding principles in the evolution of the c++ language should be ... the problem with this is that ide must first be able to assume ... libraries to find the type declaration. ...
    (comp.lang.cpp)
  • Re: Microsoft rebates
    ... competition any time in the global market, ... as far as what business need is Business Analysts. ... >grunt 'programmers', any idiot, even an indian idiot, can ... >programmer; that sort of role died ten years ago. ...
    (microsoft.public.cert.exam.mcsd)