5 ms·

On Iteration and Recursion [pdf]

54 points by alokrai 6y ago

carapace 6y ago
Five hand-written pages and no scratch-outs or corrections. And maybe I'm wrong but I'm pretty sure this wasn't the Nth draft. I don't doubt that he just sat down and wrote it out in one go. (It's so impressive it's almost galling. He makes me feel just a little like Salieri, of Mozart.) https://en.wikipedia.org/wiki/Amadeus_(film) https://en.wikipedia.org/wiki/Amadeus_(film)
- throwaway_pdp09 6y ago
  Dijkstra was well known for having a big thing for handwriting. No reason to believe it was his first draft, not that I know, though.
- JadeNB 6y ago
  If you can hand-write one page with no scratch-outs or corrections, then you can write five, by discarding pages that fail the standard if necessary.
- waynesonfire 6y ago
  it was obviously initially typed in ms word and then handwritten.
- dreamcompiler 6y ago
  EWD almost certainly wrote these on transparent film, because he gave his lectures on overhead projectors. Such film allows easy correction of mistakes because overhead projector markers are water-soluble.
  - carapace 6y ago
    Ah! Now that you mention it I see what you mean. Whew! That must be it. Thanks!
zozbot234 6y ago
(1982), see last page
a1369209993 6y ago
> the syntax for natural numbers, for which there are at least three forms No, this incorrect[0]; consider the number 102, which under the second parse rule yields first the natural number 2, to which a zero is prepended, giving 02, aka... 2; prepending a 1 then produces 12, which is clearly wrong. The third rule has the same problem, nondeterministicly. Only the first rule is correct, producing 1,10,102, by successive multiplication by ten and addition of intermediate digits. This is similar to defining subtraction with: sum ::= term sum ::= term '-' sum it may happen to match the same strings, but parsing "1-2-3" as 1-(2-3) produces 2 rather than -4. It's not clear that chop shares this problem, but personally I would much prefer: chop 0 x = x chop (S n) (p:q) = chop n q 0: or least, you'd need two forms other than the ones provided for "at least three" to be true
- waynesonfire 6y ago
  the string '02' is not the same as '2'. I'm not sure I see a problem with the syntax grammar in parsing the string '102'.
  - a1369209993 6y ago
    And the string "2-3" is not the same as "-1"; that doesn't make `sum ::= term '-' sum` correct.
    - waynesonfire 6y ago
      concatenation is associative while subtraction is left-associative. you're getting yourself in trouble defining subtraction in that way.
      - a1369209993 6y ago
        > concatenation is associative while subtraction is left-associative Yes, exactly my point: `sum ::= term '-' sum` is right-associative, and therefore not a correct syntax for subtraction. Similarly, place-value notation[0] is left-associative, so `nat ::= digit | digit nat`, which is right-associative, is not a valid grammer for a place-value-notation natural number. 0: well, big-endian place-value notation, which is what we're talking about here

54 points by alokrai 6y ago

Five hand-written pages and no scratch-outs or corrections. And maybe I'm wrong but I'm pretty sure this wasn't the Nth draft. I don't doubt that he just sat down and wrote it out in one go. (It's so impressive it's almost galling. He makes me feel just a little like Salieri, of Mozart.) https://en.wikipedia.org/wiki/Amadeus_(film) https://en.wikipedia.org/wiki/Amadeus_(film)

throwaway_pdp09 6y ago
Dijkstra was well known for having a big thing for handwriting. No reason to believe it was his first draft, not that I know, though.
JadeNB 6y ago
If you can hand-write one page with no scratch-outs or corrections, then you can write five, by discarding pages that fail the standard if necessary.
waynesonfire 6y ago
it was obviously initially typed in ms word and then handwritten.
dreamcompiler 6y ago
EWD almost certainly wrote these on transparent film, because he gave his lectures on overhead projectors. Such film allows easy correction of mistakes because overhead projector markers are water-soluble.
- carapace 6y ago
  Ah! Now that you mention it I see what you mean. Whew! That must be it. Thanks!

zozbot234 6y ago

(1982), see last page

a1369209993 6y ago

> the syntax for natural numbers, for which there are at least three forms No, this incorrect[0]; consider the number 102, which under the second parse rule yields first the natural number 2, to which a zero is prepended, giving 02, aka... 2; prepending a 1 then produces 12, which is clearly wrong. The third rule has the same problem, nondeterministicly. Only the first rule is correct, producing 1,10,102, by successive multiplication by ten and addition of intermediate digits. This is similar to defining subtraction with: sum ::= term sum ::= term '-' sum it may happen to match the same strings, but parsing "1-2-3" as 1-(2-3) produces 2 rather than -4. It's not clear that chop shares this problem, but personally I would much prefer: chop 0 x = x chop (S n) (p:q) = chop n q 0: or least, you'd need two forms other than the ones provided for "at least three" to be true

waynesonfire 6y ago
the string '02' is not the same as '2'. I'm not sure I see a problem with the syntax grammar in parsing the string '102'.
- a1369209993 6y ago
  And the string "2-3" is not the same as "-1"; that doesn't make `sum ::= term '-' sum` correct.
  - waynesonfire 6y ago
    concatenation is associative while subtraction is left-associative. you're getting yourself in trouble defining subtraction in that way.
    - a1369209993 6y ago
      > concatenation is associative while subtraction is left-associative Yes, exactly my point: `sum ::= term '-' sum` is right-associative, and therefore not a correct syntax for subtraction. Similarly, place-value notation[0] is left-associative, so `nat ::= digit | digit nat`, which is right-associative, is not a valid grammer for a place-value-notation natural number. 0: well, big-endian place-value notation, which is what we're talking about here