[Tutor] A little math and Python: Horner's rule

[Danny Yoo]

On Wed, 21 Aug 2002 alan.gauld@bt.com wrote:

> > the constructs that I used to create in high school to feed my HP 15C
> > calculator that uses an entry format called "reverse Polish notation"
>
> Sharing the nostalhgia - I couldn't afford an HP so used a 'Novus'
> calculator that was also RPN based. I agree that once you got
> used to it it was much faster and very powerful - parens
> were hardly ever needed.
>
> Sadly my Novus did not last as long as your HP....
>
> FWIW ISTR that the X windows calculator xcalc can accept a flag that
> makes it into an HP clone complete with RPN. Or am I hallucinating again?
>
> Finally you might find it fun to play with Lisp/Scheme which
> use a system similar to RPN called prefix notation:
>
> (* 3 4) => 12
> (+ 5 6 8) => 19
> (- 3 (+ 4 8)) => 9
>
> Of course being Lisp(*) parens are everywhere.
>
> (*) LISP = Lots of Irrelevant Silly Parentheses...


The parentheses are necessary because the operators in Lisp can take in
more than two arguments as values.  Your second example shows that, in
Lisp, the addition function can take in multiple values --- not just two!



If we force our language to only use binary operations, then the
parentheses are superfluous, and we can say:

    * 3 4 ==> (* 3 4)

+ + 5 6 8 ==> (+ (+ 5 6) 8)

- 3 + 4 8 ==> (- 3 (+ 4 8))

and with this restriction, LISP notation turns out to be exactly reversed
reverse polish notation.  *grin*



I think this was called M-Expression syntax.  We don't actually have to
force every function to have binary arguments, but in order to
disambiguate the parentheses, we need to put explicit restrictions on how
many arguments a particular function takes in.  See:

    http://www.not-compatible.org/LISP/QA/mexpr.html

for more information.  Gregory Chaitin uses a variation of this in his
version of Lisp:

    http://www.cs.auckland.ac.nz/CDMTCS/chaitin/lm.html



It might make an interesting project to write an RPN calculator in Python.