Functional - The Concepts and Confusions of Prefix, Infix, Postfix and Fully Functional Notations

Author

The Concepts and Confusions of Prefix, Infix, Postfix and Fully Functional Notations

Xah Lee

2007-05-09, 7:07 pm

The Concepts and Confusions of Prefix, Infix, postfix and Fully
Functional Notations

Xah Lee, 2006-03-15

In LISP languages, they use a notation like =E2=80=9C(+ 1 2)=E2=80=9D to me=
an =E2=80=9C1+2=E2=80=9D.
Likewise, they write =E2=80=9C(if test this that)=E2=80=9D to mean =E2=80=
=9Cif (test) {this}
else {that}=E2=80=9D. LISP codes are all of the form =E2=80=9C(a b c ...)=
=E2=80=9D, where the
a b c themselves may also be of that form. There is a wide
misunderstanding that this notation being =E2=80=9Cprefix notation=E2=80=9D=
.. In this
article, i'll give some general overview of the meanings of Algebraic
Notation and prefix, infix, postfix notations, and explain how LISP
notation is a Functional Notation and is not a so-called prefix
notation or algebraic notation.

The math notation we encounter in school, such as =E2=80=9C1+2=E2=80=9D, is=
called
Infix Algebraic Notation. Algebraic notations have the concept of
operators, meaning, symbols placed around arguments. In algebraic
infix notation, different symbols have different stickiness levels
defined for them. e.g. =E2=80=9C3+2*5>7=E2=80=9D means =E2=80=9C(3+(2*5))>7=
=E2=80=9D. The stickiness
of operator symbols are normally called =E2=80=9COperator Precedence=E2=80=
=9D. It is
done by giving a order specification for the symbols, or equivalently,
give each symbol a integer index, so that for example if we have
=E2=80=9Ca=E2=8A=97b=E2=8A=99c=E2=80=9D,
we can unambiguously understand it=
to mean one of =E2=80=9C(a=E2=8A=97b)=E2=8A=99c=E2=80=9
D
or =E2=80=9Ca=E2=8A=97(b=E2=8A=99c)=E2=80=9
D.

In a algebraic postfix notation known as Polish Notation, there needs
not to have the concept of Operator Precedence. For example, the infix
notation =E2=80=9C(3+(2*5))>7=E2=80=9D is written as =E2=80=9C3 2 5 * + 7 >=
=E2=80=9D, where the
operation simply evaluates from left to right. Similarly, for a prefix
notation syntax, the evaluation goes from right to left, as in =E2=80=9C> 7=
+
* 5 2 3=E2=80=9D.

While functional notations, do not employ the concept of Operators,
because there is no operators. Everything is a syntactically a
=E2=80=9Cfunction=E2=80=9D, written as f(a,b,c...). For example, the same e=
xpression
above is written as =E2=80=9C>( +(3, *(2,5)), 7)=E2=80=9D or =E2=80=9Cgreat=
erThan( plus(3,
times(2,5)), 7)=E2=80=9D.

For lisps in particular, their fully functional notation is
historically termed sexp (short for S-Expression, where S stands for
Symbolic). It is sometimes known as Fully Parenthesized Notation. For
example, in lisp it would be (f a b c ...). In the above example it
is: =E2=80=9C(> (+ 3 (* 2 5)) 7)=E2=80=9D.

The common concepts of =E2=80=9Cprefix, postfix, infix=E2=80=9D are notions=
in
algebraic notations only. Because in Full Functional Notation, there
are no operators, therefore no positioning to talk about. A Function's
arguments are simply explicitly written out inside a pair of enclosing
delimiters.

Another way to see that lisp notation are not =E2=80=9Cpre=E2=80=9D anythin=
g, is by
realizing that the =E2=80=9Chead=E2=80=9D f in (f a b c) can be defined to =
be placed
anywhere. e.g. (a b c f) or even (a f b c), and its syntax analysis
remains the same. In the language Mathematica, f(a b c) would be
written as f[a,b,c] where the argument enclosure symbols is the square
bracket instead of parenthesis, and argument separator is comma
instead of space, and the function symbol (or head) is placed in
outside and in front of the argument enclosure symbols.

The reason for the misconception that lisp notations are =E2=80=9Cprefix=E2=
=80=9D is
because the head appears before the enclosed arguments. Such use of
the term =E2=80=9Cprefix=E2=80=9D is a confusion engenderer because the sig=
nificance
of the term lies in algebraic notation systems.

A side note: the terminology =E2=80=9CAlgebraic=E2=80=9D Notation is a misn=
omer. It
seems to imply that such notations have something to do with the
branch of math called algebra while other notation systems do not. The
reason the name Algebraic Notation is used because when the science of
algebra was young, around 1700s mathematicians are dealing with
equations using symbols like =E2=80=9C+ =C3=97 =3D=E2=80=9D written out sim=
ilar to the way we
use them today. This is before the activities of systematic
investigation into notation systems as necessitated in the studies of
logic in 1800s or computer languages in 1900s. So, when notation
systems are actually invented, the conventional way of infixing =E2=80=9C+ =
=C3=97
=3D=E2=80=9D became known as algebraic because that's what people think of =
when
seeing them.

----
This post is archived at:
http://xahlee.org/UnixResource_dir/writ/notations.html

Xah
xah@xahlee.org
=E2=88=91 http://xahlee.org/

Malcolm McLean

2007-05-10, 4:17 am

"Dan Bensen" <randomg

@cyberspace.net> wrote in message
news:f1tnlf$m6u$1@wildfire.prairienet.org...
> Xah Lee wrote:
>
> The common concepts of computer programming are defined by computer
> programmers, not by mathematicians. The term "prefix notation" when
> used in the programming world does not indicate "algebraic prefix
> notation" as defined by mathematicians. The word "prefix" is a generic
> English word meaning roughly that the thing being referred to occurs
> before something else. This accurately describes the position of
> the operator in a Lisp s-expression.
>
>
> Is this consistent with the CL spec or any standard Lisp spec?
> I've never heard of such a thing.
>
What he is saying is that it is pure convention that the operator comes
first in the list. It could equally well be last, or second.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Tim Bradshaw

2007-05-10, 8:04 am

On May 10, 7:58 am, "Malcolm McLean" <regniz...@btinternet.com> wrote:

>
> What he is saying is that it is pure convention that the operator comes
> first in the list. It could equally well be last, or second.

And of course what he's conveniently ignoring is that the position of
the operator is actually what matters. Like a lot of novices he's got
massively hung up on the parens and the other little punctuation
characters which programming languages need in order for the parser to
do a fast predictable job, but which experienced humans ignore.

Once you ignore the parens (or the other punctuation if you're reading
Java, say) you see a sequence of words, generally with line breaks and
indentation indicating what they are doing. And the difference
between languages then comes down largely to word order:

Lisp is verb first, or prefix:

do-this-operation thing other-thing ...

so is C. Natural languages like this would be called VSO in general.

Java is, in many cases, verb-second, or SVO:

thing operation other-thing ...

So is English in many cases.

Forth is verb-last, so is PS etc (possibly SOV).

Of course most programming languages have a mass of special cases for
arithmetic and logical operations. Lisp doesn't (but such a syntax
can easily be added of course). Some small number of languages allow
you to extend this special syntax: I think Prolog does this. Some
others do this horrible thing of not allowing that but allowing you to
overload the fixed set of special operators (not in the Lisp sense)
with other meanings: C++ is a notorious example. Java notably has
avoided this.

Obviously if you don't like Lisp being verb-first, you can make it be
anything else, see for instance http://www.tfeb.org/lisp/toys.html#SLIP.

Lots of syntax loonies get absurdly hung up on the maths stuff,
because that's typically one of the first things you learn in any
language, and since they never get beyond that stage they assume that
programs are mostly maths. Even mathematical monographs are not
mostly maths!

--tim

Jon Harrop

2007-05-10, 8:04 am

Tim Bradshaw wrote:
> Some
> others do this horrible thing of not allowing that but allowing you to
> overload the fixed set of special operators (not in the Lisp sense)
> with other meanings: C++ is a notorious example.

F# also lets you do this and I see it as an advantage.

--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/produc...journal/?usenet

Raffael Cavallaro

2007-05-10, 10:04 pm

On 2007-05-10 10:29:22 -0400, Garry Hodgson <garry@sage.att.com> said:

> you'd be
> astonished (i was) at the bizarre notions people come up with for
> overloading "+", for example ( apple + streetcar yields kangaroo,
> while burning a cd as a side effect ).

In my experience, apple + streetcar yields applesauce, so I think
frying a latke rather than burning a CD is the appropriate side effect
- and before you ask, yes, the kangaroo keeps the latkes warm in her
pouch ;^)

This is where I wish my sig were the quote from Harvey that Kenny uses.

John Thingstad

2007-05-10, 10:04 pm

On Thu, 10 May 2007 16:29:22 +0200, Garry Hodgson <garry@sage.att.com>
wrote:

>
> yes, that's a made up example, but not far off the mark.
> overloading would be fine if only sensible people used it,
> but compiler technology is insufficiently advanced to
> enforce that.
>

Probaly best just to stick with the ones in STDLIB for streams.
Quite a chore to implement to.
It would have been much simpler with methods.
C++ classes needs to many friends ;)

--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Neelakantan Krishnaswami

2007-05-10, 10:04 pm

In article <1178791343.150674.174040@l77g2000hsb.googlegroups.com>, Tim
Bradshaw wrote:
>
> Some others do this horrible thing of not allowing that but allowing
> you to overload the fixed set of special operators (not in the Lisp
> sense) with other meanings: C++ is a notorious example. Java
> notably has avoided this.

What? Java has dynamic method dispatch for method calls. That's
overloading, pure and simple. It can't matter whether your overloaded
call is written "x.add(y)" or "(+ x y)" or "x + y" -- the same thing
will happen.

I can certainly believe that the culture of the C++ community
encouraged people to do horrible things, but I don't see how it could
possibly be a property of the language itself.

If you think I'm wrong, I'd /genuinely/ like an explanation why,
because I've heard a lot of people I respect say similar things and I
just don't get it.

--
Neel R. Krishnaswami
neelk@cs.cmu.edu

Tim Bradshaw

2007-05-10, 10:04 pm

On 2007-05-10 18:29:53 +0100, Neelakantan Krishnaswami <neelk@cs.cmu.edu> said:

> What? Java has dynamic method dispatch for method calls. That's
> overloading, pure and simple. It can't matter whether your overloaded
> call is written "x.add(y)" or "(+ x y)" or "x + y" -- the same thing
> will happen.

Can you, in Java, make 'x + y' mean, for instance 'add the row y to the
database table x'? I don't think you can. That expression, in Java,
is not a method call. You could however make 'x.add(y)' mean this, and
that would probably be a reasonable thing to do.

>
> I can certainly believe that the culture of the C++ community
> encouraged people to do horrible things, but I don't see how it could
> possibly be a property of the language itself.

It's a property of the language because it a small fixed number of
operators with fixed precedence and very well-known meanings (such as
<< ). Either do the job properly (allow new operators with new
precedence rules etc) or don't do it at all.

--tim

Malcolm McLean

2007-05-10, 10:04 pm

"Andrew Reilly" <andrew-newspost@areilly.bpc-users.org> wrote in message
news:5ag2hrF2omhc5U1@mid.individual.net...
> On Thu, 10 May 2007 07:58:36 +0100, Malcolm McLean wrote:
>
>
> Well sure, but how was the dialog helped by saying it?
>
I've condensed Xah Lee's post into two sentences. I think that is worth
something.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Paul Rubin

2007-05-11, 4:13 am

Tim Bradshaw <tfb@tfeb.org> writes:
> Can you, in Java, make 'x + y' mean, for instance 'add the row y to
> the database table x'? I don't think you can. That expression, in
> Java, is not a method call. You could however make 'x.add(y)' mean
> this, and that would probably be a reasonable thing to do.

Python can certainly make 'x+y' act as you describe, and I don't hear
anyone complaining.

Gian Uberto Lauri

2007-05-11, 4:13 am

>>>>> Long count = 12.19.14.5.9; tzolkin = 7 Muluc; haab = 17 Uo.[color=darkred]

GH> my experience during many years of c++ is that operator
GH> overloading is a Really Bad Idea.

Once upon a long ago I was fascinated by operators overloading.

"Geee, i can sum my RationalNumbers like i sum integers and floats,
wonderful".

Then I began to use a language that doesn't offer operator
overloading, and lived happily with it.

One nice day, I moved my cursor over the + in (+ 1 1) and typed C-h
C-f.

Emacs nicely responded "+ is a built-in function...". And I realized
that operators does not "exist", they are a formalism. What exists,
IMHO (my I.Q. tends to 0 from below), is something that takes one or
more "input parameters" and yelds a result.

And therefore I feel that operator overloading is not really useful,
not much more than doing

#define begin {
#define end ;}

--
/\ ___
/___/\_|_|\_|__|___Gian Uberto Lauri_____
//--\| | \| | Integralista GNUslamico
\/ e coltivatore diretto di Software

to Caesar I woulda have said "mail me to fnvag@rat.vg"

P.S.

And no. I feel that Emacs doesn't need to be modernized. It should be
the user that should get smarter... :)

Xah Lee

2007-05-11, 10:04 pm

The Merits of the Head of Expression Inside vs Outside the Parenthesis

Xah Lee. 2007-05

Lisp's nested parenthesis syntax is a Functional Notation. It has the
general form of =E2=80=9C(f a b ...)=E2=80=9D where any of the symbols insi=
de the
matching parenthesis may again be that form. For example, here's a
typical code from Emacs Lisp.

(defun fold (f x li)
"Recursively apply (f x i), where i is the ith element in the list
li.\n
For example, (fold f x '(1 2)) computes (f (f x 1) 2)"
(let ((li2 li) (ele) (x2 x))
(while (setq ele (pop li2))
(setq x2 (funcall f x2 ele))
)
x2
)
)

Vast majority of computer languages, interpret source code in a one-
dimensional, linear nature. Namely, from left to right, line by line,
as in written text. (Examples of computer languages's source code that
are not linear in nature, are spread sheets, cellular automata,
graphical programing languages) For languages that interprets source
code linearly, the logics of their syntax necessarily have a
hierarchical structure (i.e. a tree). The lisp's notation, is the most
effective in visually showing the logics of the syntax. This is
because, a function and its arguments, are simply laid out inside a
parenthesis. The level of nesting corresponds to the =E2=80=9Cprecedence=E2=
=80=9D in
evaluating the expression.

The first element inside the matching parenthesis, is called the
=E2=80=9Chead=E2=80=9D of the expression. For example, in =E2=80=9C(f a b)=
=E2=80=9D, the =E2=80=9Cf=E2=80=9D is the
head. The head is a function, and the rest of the symbols inside the
matching parenthesis are its arguments.

The head of lisp's notation needs not to be defined as the first
element inside the parenthesis. For example, we can define the =E2=80=9Chea=
d=E2=80=9D
to be the last element inside the parenthesis. So, we write =E2=80=9C(arg1
arg2 ... f)=E2=80=9D instead of the usual =E2=80=9C(f arg1 arg2 ...)=E2=80=
=9D and its
syntactical analysis remains unchanged. Like wise, you can move the
head outside of the parenthesis.

In Mathematica, the head is placed in front of the parenthesis, and
square brackets are used instead of parenthesis for the enclosing
delimiter. For example, lisp's =E2=80=9C(f a b c)=E2=80=9D is syntactically=
equivalent
to Mathematica's =E2=80=9Cf[a,b,c]=E2=80=9D. Other examples: =E2=80=9C(sin =
=CE=B8)=E2=80=9D vs =E2=80=9CSin[=CE=B8]=E2=80=9D,
=E2=80=9C(map f list)=E2=80=9D vs =E2=80=9CMap[f,list]=E2=80=9D. Placing th=
e head in front of the
matching bracket makes the notation more familiar, because it is a
conventional math notation.

However, there is a di

vantage in moving the head of a expression
from inside the matching bracket to outside. Namely: The nesting of
the matching delimiters, no longer corresponds to the logics of the
syntax, when the head is itself a compound expression.

For example, suppose Reflection(vectorV,pointP) is function that
returns a function f, such that f(graphicsData) will reflect the
graphicsData along a line passing pointP and parallel to vectorV. In
lisp, we would write =E2=80=9C((Reflection vectorV pointP) graphicsData)=E2=
=80=9D. In
Mathematica, we would write =E2=80=9CReflection[vectorV,pointP]
[graphicsData]=E2=80=9D. In lisp's version, the nesting corresponds to the
logics of the evaluation. In the Mathematica's form, that is no longer
so.

For another example, suppose Deriv is a function that takes a function
f and returns a function g, and we want to apply g to a variable x. In
lisp, we would write =E2=80=9C((Deriv f) x)=E2=80=9D. In Mathematica, we wo=
uld write
=E2=80=9CDeriv[f][x]=E2=80=9D. In lisp's version, the nesting corresponds t=
o the
logics of the evaluation. In the Mathematica's form, the logics of the
evaluation no longer corresponds to the nesting level, because now the
head is outside of the enclosing delimiters, so the head of
expressions no longer nests. The merit of lisp's =E2=80=9C(f x)=E2=80=9D fo=
rm versus
Mathematica's =E2=80=9Cf(x)=E2=80=9D form.

------------
This post is excerpted from
=E2=80=9CThe Concepts and Confusions of Prefix, Infix, postfix and Fully
Functional Notations=E2=80=9D, archived at
http://xahlee.org/UnixResource_dir/writ/notations.html

Xah
xah@xahlee.org
=E2=88=91 http://xahlee.org/

Tim Bradshaw

2007-05-11, 10:04 pm

On 2007-05-11 04:16:11 +0100, Paul Rubin <http://phr.cx@NOSPAM.invalid> said:

> Python can certainly make 'x+y' act as you describe, and I don't hear
> anyone complaining.

You'd hear me if I wrote Python any more. Fortunately I don't, so I
won't (also I suspect but am not sure that you can create entirely new
operators in Python which, as I said, I'm fine with). I seem to
remember the article to which you responded was about Java however.

Sponsored Links