Expressive Power

Moved from SyntacticSugar

x+=1 and x=x+1 have different semantics when x is declared volatile - to me this says they are not equivalent, one is not syntactic sugar for the other.

But they don't differ in expressive power.

Would you care to expand on that?

This comes up pretty frequently in comparing languages; often someone says "language A is more powerful than language B", someone else argues "that's stupid, both are Turing Equivalent", and the first says "That's trivial; the point is that A has more expressive power than B". Most people would agree that e.g. Haskell, Smalltalk, and Lisp all have more expressive power than Basic, even though Basic is indeed TuringEquivalent.

Determining such a thing objectively rather than subjectively seems to be somewhat problematic, a phenomenon that PaulGraham has discussed under "The BlubParadox".

I think the heart of it is weak and strong equivalence, though. If two constructs are only weakly equivalent, then the one with the terser representation/derivation is the one with greater "Expressive Power".

Weak Equivalence computes the same output (or strings, in the case of grammars); Strong Equivalence does that, but with the same intermediate steps (same derivation tree). Colin already knows this, but for other readers: these are standard mathematical terms, not ones made up for this discussion.

GreenspunsTenthRuleOfProgramming is definitely about this topic; Greenspun is talking about Lisp constructs that do not tend to have Strong Equivalents in other languages, so they have to be developed laboriously, and once that's been done, one has created a half-assed version of Lisp in that other language.

Some of those Lisp features with high expressive power include: higher order functions, semantic macros, equivalence of representation of data and code (both representable as lists), eval, etc.

-- DougMerritt

(Borrowed from DataAndCodeAreTheSameThing:) The issues have been described and formalized in OnExpressivePower.

All true, but irrelevant to the original point, which was that neither x+=1 nor x=x+1 is SyntacticSugar for the other. See that page for a more detailed argument.

ExampleOfGreenspunsTenthAtWork GreenspunsTenthRuleOfProgramming DataAndCodeAreTheSameThing NonTuringModelOfComputation NthGenerationLanguage DomainSpecificLanguage CriteriaForGoodMathOrCompactNotation BlubParadox