[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: succinctness = power
At Fri, 24 May 2002 12:05:21 -0700 (PDT), Paul Graham wrote:
> At any rate, it seemed like it might be a good idea to
> take the question of succinctness head on. To avoid
> spamming this whole list with a long piece on the topic
> (and because I want to build a collection of related
> links) I put this on a web page:
> Comments (either here on ll1 or to me directly) are
> appreciated. Let me know especially if you know of any
> links to stuff about this question.
Paul, as someone who has tasted academic research on PL, you
may wish to think about the abstract question as well.
We all know and have even studied the Goedel/Church/Turing notion
of power in programming languages. That's not the notion that you
have in mind.
Then there is Landin's informal idea, which I formalized in the
early 90's as an alternative to Turing's notion of expressiveness.
Roughly speaking, a construct is superfluous if you can write
structurally regular translations that eliminate all uses.
let-blocks over 1st-class closures,
for-loops over while-loops,
closures over objects,
Conversely, a construct adds power if it allows programs to observe
an aspect of an expression's behavior that wasn't visible before.
set! over a pure functional or OO language
call/cc over a pure function or OO language:
you can now observe certain aspects of procedures
abort over a pure language with call/cc
You can then draw the informal corollary that adding an "expressive"
construct to a language removes patterns from programs (cps, store-passing)
and thus makes the program more "conceptually" more succinct.
My papers appeared at ESOP and in Sci of Programming, if anyone is
interested. A number of people followed up on the idea but I wouldn't
say that it caught on. A word of caution: It is a syntactic notion of
expressiveness and is thus brittle. But I claim that one should expect
this from a notion based on a programmer's perspective. A programmer
sees syntax first.