[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: various recent ll1 threads

   From: kragen@pobox.com (Kragen Sitaker)
   To: ll1-discuss@ai.mit.edu
   > That presumes that infix notation is merely a whimsical preference that
   > could change soon whereas I think that it probably evolved over millenia
   > as the best solution to keeping operators close to their operands.
   That's what I thought, too, but then I examined some expressions.
   In ((2 - 3) * (4 + 1)) / (11 + 3), the / is separated from its child
   operators (* and the second +) by six and two tokens respectively, for
   a sum of eight.  * is separated from its child operators by two and
   two tokens, for a total of four.  The other three operators are
   adjacent to their operands, so we have a total of only twelve
   intervening tokens.
   In the prefix notation / * - 2 3 + 4 1 + 11 3, / is separated from its
   children by zero and seven tokens; * from its by zero and three; and
   each of the +s and the - by zero and one, for a total of thirteen,
   slightly more than in parenthesized infix notation.  If the order of
   /'s children were swapped, prefix would keep the operators closer to
   their operands than infix.

Interesting points, but contemplate

  / * - 2 3
      + 4 1
    + 11 3

or, with Lisp's parentheses,

  (/ (* (- 2 3)
        (+ 4 1))
     (+ 11 3))

In this case each operator tends to be quite close to its children.
If all you care about is "separation", then each operator is
separated from its first child by zero tokens and from its
second child by one token (because you scan horizontally
over to the first child, then vertically to the second child,
which may be some distance down but there will be no tokens
in the way!).

This two-dimensional effect is difficult to achoeve with infix.

Yes, infix may win for small expressions.  Years of experience
have convinced me what prefix wins for large expressions.

--Guy Steele