Xah's Edu Corner: The Concepts and Confusions of Pre-fix, In-fix, Post-fix and Fully Functional Nota

X

Xah Lee

The Concepts and Confusions of Pre-fix, In-fix, Post-fix and Fully
Functional Notations

Xah Lee, 2006-03-15

Let me summarize: The LISP notation, is a functional notation, and is
not a so-called pre-fix notation or algebraic notation.

Algebraic notations have the concept of operators, meaning, symbols
placed around arguments. In algebraic in-fix notation, different
symbols have different stickiness levels defined for them. e.g.
“3+2*5>7†means “(3+(2*5))>7â€. The stickiness of operator
symbols are normally called “Operator Precedenceâ€. 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
“a⊗b⊙câ€, we can unambiguously understand itto mean one of
“(a⊗b)⊙c†or “a⊗(b⊙c)â€.

In a algebraic post-fix notation known as Polish Notation, there needs
not to have the concept of Operator Precedence. For example, the in-fix
notation “(3+(2*5))>7†is written as “3 2 5 * + 7 >â€, where the
operation simply evaluates from left to right. Similarly, for a pre-fix
notation syntax, the evaluation goes from right to left, as in “> 7+
* 5 2 3â€.

While functional notations, do not employ the concept of Operators,
because there is no operators. Everything is a syntactically a
“functionâ€, written as f(a,b,c...). For example, the same
expression above is written as “>( +(3, *(2,5)), 7)†or
“greaterThan( plus(3, times(2,5)), 7)â€.

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:
“(> (+ 3 (* 2 5)) 7)â€.

The common concepts of “pre-fix, post-fix, in-fix†are notions in
algebraic notations only. Because in Full Functional Notation, there is
no concept of where one places the “operator†or function. There is
always just a single position given with explicitly enclosed arguments.

Another way to see that lisp notation are not “pre†anything, is by
realizing that the “head†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 it's still not
pre- or in- or post- anything. For example, 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 “pre-fixâ€
is because the head appears before the enclosed arguments. Such
“pre-fix†has no signifance in Full Functional Notation systems and
can only engender confusion in the Algebraic Pre-fix Notation systems
where the term has significance.

2000-02-21

The common name for the lisp way is Fully Parenthesized Notation. This
syntax is the most straightforward to represent a tree, but it's not
the only choice. For example, one could have Fully Parenthesized
Notation by simply moving the semantics of the first element to the
last. You write (arg1 arg2 ... f) instead of the usual (f arg1 arg2).

Like wise, you can essentially move f anywhere and still make sense. In
Mathematica, they put the f in front of the paren, and use square
brackets instead. e.g. f[a,b,c], Sin[3], Map[f,list] ... etc. The f in
front of parent makes better conventional sense until f is itself a
list which then we'll see things like f[a,b][c, g[3,h]] etc. It's worse
when there are arbitrary nesting of heads.

A pre-fix notation in Mathematica is represented as “f@argâ€.
Essentially, a pre-fix notation in this context limits it to uses for
function that has only one argument. More example: “f@a@b@c†is
equivalent to “f[a[b[c]]]†or in lispy “(f (a (b c)))â€. A
post-fix notation is similar. In Mathematica it is, e.g.
“c//b//a//fâ€. For example “List[1,2,3]//Sin†is syntactically
equivalent to “Sin[List[1,2,3]]†or “Sin@List[1,2,3]â€. (and
they are semantically equivalent to “Map[Sin, List[1,2,3]]â€in
Mathematica) For in-fix notation, the function symbol is placed between
its arguments. In Mathematica, the generic form for in-fix notation is
by sandwiching the tilde symbol around the function name. e.g.
“Join[List[1,2],List[3,4]]†can be written as “List[1,2] ~Join~
List[3,4]â€.

In general, when we say C is a in-fix notation language, we don't mean
it's strictly in-fix but the situation is one-size-fits-all for
convenience. Things like “i++â€, “++iâ€, “for(;;)â€, 0x123,
“sprint(...%s...,...)â€, ... are syntax whimsies. (that is, a ad hoc
syntax soup)

In Mathematica for example, there is quite a lot syntax sugars beside
the above mentioned systimatic constructs. For instance, Plus[a,b,c]
can be written in the following ways: “(a+b)+c†or “a+b+c†or
“(a+b)~Plus~câ€

The gist being that certain functions such as Plus is assigned a
special symbol '+' with a particular syntax form to emulate the
irregular and inefficient but nevertheless well-understood conventional
notation. For another example: Times[a,b] can be also written as
“a*b†or just “a bâ€. Mathematica also have C language's
convention of “i++â€, “++iâ€, “i+=1†for examples.

As a side note, the Perl mongers are proud of their slogan of There Are
More Than One Way To Do It in their gazillion ad hoc syntax sugars but
unaware that in functional languages (such as Mathematica, Haskell,
Lisp) that there are consistent and generalized constructs that can
generate far far more syntax variations than the ad hoc prefixed Perl
both in theory AND in practice. (in lisps, their power syntax variation
comes in the guise of macros.) And, more importantly, Perlers clamor
about Perl's “expressiveness†more or less on the useless syntax
level but don't realize that semantic expression is what's really
important.
----
This post is archived at:
http://xahlee.org/UnixResource_dir/writ/notations.html

Xah
(e-mail address removed)
∑ http://xahlee.org/
 
R

Roedy Green

e. For example, the in-fix
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

Not that Mr. Lee has ever shown much interest in feedback, but you
pretty well have stick to vanilla ASCII to get your notation through
unmangled on newsgroups.
 
S

SamFeltus

"""Not that Mr. Lee has ever shown much interest in feedback, but you
pretty well have stick to vanilla ASCII to get your notation through
unmangled on newsgroups."""

It is the 21st century, so having to do that oughta inspire some sort
of well earned anti Unix rant...

:)
 
J

Jeffrey Schwab

SamFeltus said:
"""Not that Mr. Lee has ever shown much interest in feedback, but you
pretty well have stick to vanilla ASCII to get your notation through
unmangled on newsgroups."""

It is the 21st century, so having to do that oughta inspire some sort
of well earned anti Unix rant...

:)

Not anti-Unix.
Anti-failure-to-use-appropriate-datatypes-for-the-task-at-hand.
 
X

Xah Lee

Xah Lee wrote:
« The Concepts and Confusions of Pre-fix, In-fix, Post-fix and Fully
Functional Notations
http://xahlee.org/UnixResource_dir/writ/notations.html »

A side note: the terminology “Algebraic†Notation is a misnomer. 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 “+ × =†written out similar to the way we use them
today. This is before the activities of systimatic 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 “+ × =†became known as
algebraic because that's what people think of when seeing them.

Xah
(e-mail address removed)
∑ http://xahlee.org/
 
D

Dinko Tenev

Roedy said:
Not that Mr. Lee has ever shown much interest in feedback, but you
pretty well have stick to vanilla ASCII to get your notation through
unmangled on newsgroups.

That would be one of my last concerns with Mr. Lee's postings.

If only someone could persuade this guy to stay away from CS...
 
T

Timo Stamm

Fuzzyman said:
Hmmm... it displays fine via google groups. Maybe it's the reader which
is 'non-compliant' ?


Other charsets than US-ASCII are widely accepted in non-english
newsgroups as long as the charset is properly declared.

Xah's posting was properly encoded and will display fine in every decent
newsreader.


Timo
 
A

axel

Other charsets than US-ASCII are widely accepted in non-english
newsgroups as long as the charset is properly declared.
Xah's posting was properly encoded and will display fine in every decent
newsreader.

It is not just the question of the newsreader, it is also a question of whether
the character set/font being used is capable of displaying the characters
concerned.

Axel
 
T

Timo Stamm

It is not just the question of the newsreader, it is also a question of whether
the character set/font being used is capable of displaying the characters
concerned.

A character set doesn't display characters, it specifies the coupling of
a character (grapheme) and its representation in a data format (number).

Because the specification of internet text messages only allows 7 bit
ASCII, Multipurpose Internet Mail Extensions have been introduced. They
define, for example, the quoted-printable transfer encoding.

Xah's posting properly declared a quoted-printable transfer encoding and
the UTF-8 charset. There were no unspecified characters in the message,
it was absolutely adhering to the recognized standards.


If this message doesn't display properly on your system - because your
newsreader doesn't know how to decode quoted printable or because your
operating system lacks a font to display the characters, this may be a
problem. But it's your newsreader or your OS that is broken or not up to
date.

BTW, the newsreader you are using should handle the posting fine.


Timo
 
R

Roedy Green

Hmmm... it displays fine via google groups. Maybe it's the reader which
is 'non-compliant' ?
I am using Agent. You configure your database with an encoding,
which is by default the platform encoding, not UTF-8. I have just
flipped it over to UTF-8. We'll see if that makes Xah's future UTF-8
messages more readable.
 
P

PofN

Dinko said:
If only someone could persuade this guy to stay away from CS...

I still hope that at some point in time he will manage to tender his
nomination for the darvin award. You can't rationalize with that troll,
because there is nothing between his ears capable of catching a clue.
 
M

Mike Schilling

Roedy Green said:
I am using Agent. You configure your database with an encoding,
which is by default the platform encoding, not UTF-8. I have just
flipped it over to UTF-8. We'll see if that makes Xah's future UTF-8
messages more readable.

Trust me, it won't help a bit.
 
T

Tim Roberts

Roedy Green said:
I am using Agent. You configure your database with an encoding,
which is by default the platform encoding, not UTF-8. I have just
flipped it over to UTF-8. We'll see if that makes Xah's future UTF-8
messages more readable.

Try pressing Ctrl-R when his message is visible. I'm also using Agent, and
that toggles his extended characters from quoted-printable to visible for
me.
 
R

Roedy Green

Try pressing Ctrl-R when his message is visible. I'm also using Agent, and
that toggles his extended characters from quoted-printable to visible for
me.

that swaps fixed and variable pitch fonts. I gather you have one of
your fonts configured without many chars in it.
 
X

Xah Lee

What is Expressiveness in a Computer Language

Xah Lee, 200502, 200603.

In languages human or computer, there's a notion of expressiveness.

English for example, is very expressive in manifestation, witness all
the poetry and implications and allusions and connotations and
dictions. There are a myriad ways to say one thing, fuzzy and warm and
all. But when we look at what things it can say, its power of
expression with respect to meaning, or its efficiency or precision, we
find natural languages incapable.

These can be seen thru several means. A sure way is thru logic,
linguistics, and or what's called Philosophy of Languages. One can also
glean directly the incapacity and inadequacy of natural languages by
studying the artificial language lojban, where one realizes, not only
are natural languages incapable in precision and lacking in efficiency,
but simply a huge number of things are near impossible to express thru
them.

One thing commonly misunderstood in computing industry is the notion of
expressiveness. If a language has a vocabulary of (smile, laugh, grin,
giggle, chuckle, guffaw, cackle), then that language will not be as
expressive, as a language with just (severe, slight, laugh, cry). The
former is “expressive†in terms of nuance, where the latteris
expressive with respect to meaning.

Similarly, in computer languages, expressiveness is significant with
respect to semantics, not syntactical variation.

These two contrasting ideas can be easily seen thru Perl versus Python
languages, and as one specific example of their text pattern matching
capabilities.

Perl is a language of syntactical variegations. Lisp on the other hand,
is a example of austere syntax uniformity, yet its efficiency and power
in expression, with respect to semantics, showcases Perl's poverty in
specification.

Example: String Patterns in Regex

In Perl, the facilities for finding and replacing a text pattern is
this construct “$myText =~ s/myPattern/replStr/â€.

In Python, it is “re.sub( myPattern, replStr, myText , myCount)â€,
where the replacement string repStr can be a function, and a max number
of replacement myCount can be specified. If there is a match, and if
replStr is given a function myFunc instead, then a special regex match
object is feed to myFunc and it can return different strings based on
how the pattern is matched.

This is a instance where the language is more expressive. In Python's
regex facilities, there are several other flexibilities not present in
Perl. For example, its regex pattern can be frozen as a compiled object
and moved about. And, when a there is a match, Python returns a special
object that contains all information about the regex, such as the
original pattern, the number of matches, the set of matched strings and
so on, and this object can be passed around, or have information
extracted. These facilities are absent in Perl.

In this case, the flexibilities and facilities of Python's texual
patterns matching's capabilities a instance of superior expressiveness
to Perl's.

For more about Python's Regex machinery, see the Re-written Python
Regex Documentation at:
http://xahlee.org/python_re-write/lib/module-re.html

Example: Range, and Computation with Fractions

In Perl, there's a range construct “(a..b)†that returns a list of
numbers from a to b. However, this construct cannot generate a list
with regular intervals such as (1, 3, 5, 7, 9). Nor would it generate
decreasing lists such as (4, 3, 2, 1) when a > b.

In Python, its range function range(a,b,c) returns a range of numbers
from a to b with steps c. For example, range(3,-5, -2) returns [3, 2,
1, -1, -3]. The arguments can be negative, however, they all must be
integers.

In the Mathematica language, there's also a range function
Range[a,b,c]. Here, the arguments can be either real numbers or exact
fractions. If one of the input argument is a decimal, then the
computation is done as machine precision approximations and the result
list's elements are also in decimals. If all inputs are in fractions
(including integers), returned list's elements will also be exact
fractions.

In Mathematica, the language support fractions wherever a number is
used, and if all numbers are specified as fractions (or integers) in
the code, the result of the computation is also in exact fractions,
with it automatically in a reduced fraction form where common factors
in the numerator and denominator are taken out. (Fractions in
Mathematica is written as a/b with a and b integers.)

This section compares the expressiveness of a particular list
generating facility in 3 languages. But far more importantly, being
able to compute with fractions naturally is a expressibility unheard of
in non-commercial languages.
Example: Rich, Systematic Parameters for Functions

In many languages, there is a function called “mapâ€. Usually it
takes the form map(f, myList) and returns a list where f is applied to
every element in myList. For example, here is a example from Python and
Perl and lisp:

# python
map( lambda x:x**2 , [1,2,3])

# perl
map {$_**2} (1,2,3);

; lisp
(map (lambda (x) (expt x 2)) (list 1 2 3))

In the Mathematica language, its map function takes a optional third
argument, which specifies the level of the list to map to. In the
following example, f is mapped to the leafs of the list {1,2,{3,4}}.

In[1]:=
Map[Function[#^2],{1,2,{3,4}}, {-1}]

Out[2]=
{1,4,{9,16}}

The expressive power of a language does not solely lies with its
functions taking more options. Such is only a small aspect of
expressibility. However, if a language's functions are designed such
that they provide important, useful features in a consistent scheme,
certainly makes the language much more expressive.

In the functional language Mathematica, there is a host of functions
that manipulate lists, with options that work on the list's structural
level or syntactical pattern. In terms of expressiveness, this is a
superior example.

Example: Symbolic Computation

Lisp differs from most imperative programing languages in that it deals
with symbols. What does this mean?

In imperative languages, a value can be assigned a name, and this name
is called a variable. For example, “x=3â€, and whenever this
“name†is encountered, it is evaluated to its value. It does not
make any sense, to have variables without a assigned value. That is,
the “x†is not useful and cannot be used until you assign something
to it.

However, in lisp, there is a concept of Symbols. As a way of
explanation, a “variable†needs not to be something assigned of a
value. Symbols can stand by themselves in the language. And, when a
symbol is assigned a value, the symbol can retain it's symbolic form
without becoming a value.

This means that in lisp, “variables†can be manipulated in its
un-evaluated state. The situation is like the need for the
“evaluate†command in many languages, where the programer can built
code as strings and do “evaluate(myCodeString)†to achieve
meta-programing.

For example, in imperatives languages once you defined “x=3â€, you
cannot manipulate the variable “x†because it gets evaluated to 3
right away. If you want, you have to build a string “"x"†and
manipulate this string, then finally use something like
“evaluate(myCodeString)†to achieve the effect. If the imperative
language does provide a “evaluate()†function, its use breaks down
quickly because the language is not designed for doing it. It's
extremely slow, and impossible to debug, because there lacks facilities
to deal with such meta programing.

In lisp, variable's unevaluated form are always available. One just put
a apostrophe ' in front of it. In “x=3â€, the x is a variable in the
contex of the code logic, x is a name of the variable in the context of
meaning analysis, and x is a symbol in the context of the programing
language. This Symbols concept is foreign to imperative languages. It
is also why lisp are known as symbolic languages. Such makes
meta-programing possible.

The power of symbolic processing comes when, for example, when you take
user input as code, or need to manipulate math formulas, or writing
programs that manipulates the source code, or generate programs on the
fly. These are often needed in advanced programing called Artificial
Intelligence. This is also the reason, why lisp's “macroâ€
facilities is a powerful feature unlike any so-called
“pre-processors†or “templates†in imperative languages that
works by processing strings.

Mathematica for example, is sometimes known as a Computer Algebra
System. It too, works with symbols in the language. They can be
manipulated, transformed, assigned a value, evaluated, hold unevaluated
etc.

One way for a imperative programer to understand symbols, is to think
of computing with strings, such as which Perl and Python are well known
for. With strings, one can join two strings, select sub strings, use
string pattern (regex) to transform strings, split a string into a list
for more powerful manipulation, and use “eval†to make the string
alive. Now imagine all these strings needs not to be strings but as
symbols in the language, where the entire language works in them and
with them, not just string functions. That is symbolic computation.

Here we see, a expressibility unseen in non-lisp family of languages.
Expressiveness in Syntax Variability

See: The Concepts and Confusions of Pre-fix, In-fix, Post-fix and Fully
Functional Notations, at:
http://xahlee.org/UnixResource_dir/writ/notations.html

Example: Classes in OOP (in Java, JavaScript, Python)

Coming soon...

----
This post is archived at:
http://xahlee.org/perl-python/what_is_expresiveness.html

Xah
(e-mail address removed)
∑ http://xahlee.org/
 
J

John Bokma

Dag Sunde said:
<snipped_inane_chatter />
PLONK.

Don't post PLONK messages you idiot. PLONK in silence instead of adding to
a lot of garbage in serveral groups.
 
L

Luc The Perverse

John Bokma said:
Don't post PLONK messages you idiot. PLONK in silence instead of adding to
a lot of garbage in serveral groups.

Sometimes you need to make a statement about a local troll.

Though I agree - a massively cross posted thread with no one familiar
probably doesn't qualify
 
R

Roedy Green

One thing commonly misunderstood in computing industry is the notion of
expressiveness. If a language has a vocabulary of (smile, laugh, grin,
giggle, chuckle, guffaw, cackle),

Expressive for a natural language refers to the language's ability to
generate precisely generate moods, and move people emotionally in a
minimum of words.

Expressiveness in computer languages refers to the language's ability
to persuade the computer to produce some result in a minimum of words.

Another measure might be how smoothly elements of the language map
onto elements of the problem domain.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,832
Latest member
GlennSmall

Latest Threads

Top