5
$\begingroup$

in John Backus' 1978 FP paper "Can Programming Be Liberated from the von Neumann Style" he says

To help assemble the overall result from single words [von Neumann ie. conventional mutation-based] languages provide some primitive combining forms in the statement world--the for, while,and if-then-else statements--but the split between the two worlds [ie. between the expression-only and statement-only, as I understand him] prevents the combining forms in either world from attaining the full power they can achieve in an undivided world.

He shows the expressiveness of functional programming, that's what the paper is about, but he implies there's a similar expressiveness that can be got from the statements-only part, per the above quote. However I don't know what he means by this; he gives no examples.

The only language that appears ruthlessly statement-y that I can think of is (pure) prolog (eg. see https://en.wikipedia.org/wiki/Prolog#Quicksort, there's no expressions as such only statements giving relationships) and it's not statements so much as the backtracking that gives it the power.

So what did Backus mean by this? What example languages are there that are statement only (but without backtracking)?

Edit: belated link to orginal paper https://dl.acm.org/doi/10.1145/359576.359579 for interest.

(The question has nothing to do with BNF form. Also, if someone can edit the title to better summarise the long quote, please do Edit: that's much better, thanks!)

$\endgroup$
3
  • 1
    $\begingroup$ Assembly language/machine code is completely composed of statements, telling the computer to move data into and out of registers and perform calculations, etc. In 1978 programming in assembly was much more common than it is today. Perhaps that is what was meant? $\endgroup$
    – Ryan1729
    Mar 8 at 3:14
  • $\begingroup$ That's an interesting idea but expressions in assembler are just high-level expressions broken down, more or less. “y = (a + b) * c” is just “temp = a + b; y = temp * c” but written as “add a, b, temp; mult temp, c, y” I don't know. Backus seemed to be talking about high-level statements (for/while/if-else) and I've been trying to imagine how you can ...well, do anything useful with these, and I can't. The more I think about it the less sense it all makes. Thanks for an ingenious suggestion though. $\endgroup$ Mar 8 at 16:40
  • $\begingroup$ @user3779002, done! $\endgroup$
    – Steve
    Mar 8 at 21:17
4
$\begingroup$

Reading the quote literally without the interpolated interpretation, I think what Backus is saying is that a powerful language is one which makes no distinction between expressions and statements.

That is, where all statements are also expressions, like a functional language.

I don't think Backus was claiming that an "all statement" language - the meaning of which is not entirely clear in this context - would be powerful or even feasible. Rather, he is claiming that the existence of certain statements that cannot be analysed as expressions, is a defect in language design.

$\endgroup$
3
  • $\begingroup$ This is not quite it. Many imperative languages, such as Algol 68, C, and sh, allow statements to be used as expressions. That is a grammatical feature. Backus's idea is not about grammar, it is about immutability. $\endgroup$ Mar 9 at 20:12
  • $\begingroup$ @reinierpost, but do they allow all statements to be used as expressions? Such as the for loop, or the while loop, to which Backus refers? $\endgroup$
    – Steve
    Mar 9 at 20:39
  • $\begingroup$ @reinierpost - C's if/else, for, while, do-while, switch are not expressions IIRC. I don't think immutability was all that special in the paper either (the word doesn't appear at all that I can see) but he does put some weight on 'combining forms' and program steps being large transformations logically, not word-at-a-time VonN. style. Also formal, simple rules that define the language and can be used for program transformation. It's really much more than immutability, though clearly that too. $\endgroup$ Mar 9 at 20:51
0
$\begingroup$

Backus says in that quote that splitting statements from expressions makes the “combining forms” (such as if-then-else) less powerful, because they can only be applied to statements, but not to expressions. He wants to see a language all of whose elements may be combined in the same ways.

That quote does not say that a language consisting only of statements could be more powerful, nor yet that the statement part of a von Neumann language on its own could be. What he actually says is that in an undivided world (without the distinction between expressions and statements) combining forms can be more powerful.

Since he is not talking of declarative languages such as Prolog, your follow-up question about languages without backtracking is not relevant.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.