Re: succinctness = power

[Matthias Felleisen <address@hidden>]

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:
> 
> http://www.paulgraham.com/power.html
> 
> 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.
> 
> --pg

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. 
  Examples: 
	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. 
  Examples: 
	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. 

-- Matthias