Jump to content

Check out our Community Blogs

- - - - -

Prefix vs. infix vs. postfix notation

Posted by DarkLordCthulhu, 03 September 2011 · 154499 views

In my last blog post, I said that I taught myself dc, the Unix RPN calculator. I am also teaching myself Lisp, specifically Common Lisp. Both represent promising alternatives to the imperative, procedural, object-oriented languages that many programmers seem intent on sticking to while remaining ignorant of everything else. These people (at least in my opinion) are unimaginative and do not possess the programmer mindset, and probably are not genuinely interested in computer programming in the first place.

But that's beside the point. What I really want to talk about is alternative paradigms and syntaxes. Lisp and dc are alternative-paradigm languages, the first being functional and the second being stack-based. They also use a rather interesting syntax for arithmetic and other expressions.

There are three possible ways of formatting a dyadic expression: prefix, postfix, and infix. The majority of languages you are probably familiar with use infix. Here is a trivial example of the three, using a simple addition operation:

+ a b

a + b

a b +

One who is not familiar with prefix and postfix might ask what they are good for. Doesn't infix make more sense, since it's the way people normally write equations? Sure, and that's why most programming languages use it. But sometimes it's more useful to use the other two. Lisp and dc are examples of this.

Lisp is a functional language. The essential difference between functional and imperative programming is that, whereas functions in an imperative language are treated as subroutines that alter the flow of the program, functions in a functional language are simply evaluated. They can still do things like display output and manipulate memory (a language is hardly useful if it does nothing other than evaluate), but there's no transfer of control to speak of. One has to experience the functional programming paradigm oneself in order to appreciate this.

Lisp programs consist entirely of functions, which are in the form of lists, the first item being the function and the rest of the items being parameters or operands. In Lisp, the difference between a function and an operator is inconsequential; there really is none to speak of. Arithmetic operations like +, -, *, and / are functions. It is therefore logical for the operand to come first, as in:

( * ( + a b ) ( - a b ) )

It makes little sense to break the uniform format of a Lisp function simply to make arithmetic operations more intuitive. Furthermore, this format has an advantage in that, because the compiler or interpreter knows that the operand is always the first list item, the programmer is allowed to name the items with slashes, asterisks, or any other characters he/she sees fit, without leading to errors.

In a stack-based language like dc, operations are performed by pushing operands onto the stack, popping them to perform an operation, and pushing the result. Thus
la lb + la lb - *
does the same thing as the Lisp function mentioned previously. la and lb are register values that are pushed onto the stack, first added, then subtracted, after which the results are popped and multiplied. Again, the overhead incurred from modifying the syntax to make it more easily readable to someone enslaved by their cognitive bias is not worth it. We all have cognitive biases that make it harder to learn a new discipline (this is why children are seen as being more imaginative and flexible learners; they have not yet developed cognitive bias), but they can be overcome with some effort and an open mind.

Both functional and stack-based programming have tremendous advantages in terms of efficiency and reducing overhead, functional because it eliminates the need for branching between parts of a program, and stack-based because a stack is dynamic and can be used to conveniently create and discard data without allocating or freeing memory.

So here, then, is a table I've made to sum up the three notations:

Notation:      Format:         Construct:           Advantage:
Prefix         op val1 val2    Function or list     Flexibility
Infix          val1 op val2    Parse tree           Readability
Postfix        val1 val2 op    Stack                Resource efficiency

If there's a lesson to be learned from this, it's to always be open to new ideas. Don't fear things that are unknown or unfamiliar; embrace them. Not only will it make you more intelligent; you might find that they are better than what you knew.

  • 0

I would certainly like to have seen calculators in today's age being Łukasiewicz's notation, it would have been a neat to see if children would become more interested in mathematics.
    • 0
Infix notation is the ONLY one that requires order of operations. The other two impose order of operations by the nature of the expression.
    • 0
I've always held a special place in my heart for the functional paradigm. :) Even though I code in Java for a living.
    • 0
Whoo! Had learnt about what prefix, postfix, infix expressions were..but did not know that they were used in some languages too... Got to know about two new languages lisp n dc... :)
    • 0
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download