Tuesday, 11 June 2013

Infix and Postfix (and Prefix)

Jargon Alert!  Two (OK, three) more terms from the mysterious worlds of Maths and Computing Science.  Lets go to wikipedia:

Infix Notation

From Wikipedia, the free encyclopedia

Infix-dia.svg

Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on (e.g. 2 + 2). It is not as simple to parse by computers as prefix notation ( e.g. + 2 2 ) or postfix notation ( e.g. 2 2 + ), but many programming languages use it due to its familiarity.

In infix notation, unlike in prefix or postfix notations, parentheses surrounding groups of operands and operators are necessary to indicate the intended order in which operations are to be performed. In the absence of parentheses, certain precedence rules determine the order of operations.

Update (5th September, 2013): The statement above about parentheses doesn’t refer to the use of parentheses to group the arguments passed to a method.  It means that they should be used to indicate evaluation order. (c.f. Atomic Scala pp.54-57).  It is common for Scala to be described as having “infix notation” but by this people generally mean that (as in the case with AtomicTest’s “is” method) a method can be called without a preceding dot (‘.’) and following parentheses for arguments. (c.f. Atomic Scala pp.119 for an example of this).

 

Reverse Polish Notation (aka Postfix Notation)

From Wikipedia, the free encyclopedia

Postfix-dia.svg

Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position. It is also known as postfix notation and is parenthesis-free as long as operator arities are fixed. The description "Polish" refers to the nationality of logician Jan Łukasiewicz, who invented (prefix) Polish notation in the 1920s.

The reverse Polish scheme was proposed in 1954 by Burks, Warren, and Wright[1] and was independently reinvented by F. L. Bauer and E. W. Dijkstra in the early 1960s to reduce computer memory access and utilize the stack to evaluate expressions. The algorithms and notation for this scheme were extended by Australian philosopher and computer scientist Charles Hamblinin the mid-1950s.[2][3]

In computer science, postfix notation is often used in stack-based and concatenative programming languages. It is also common in dataflow and pipeline-based systems, including Unix pipelines.

 

Polish notation (aka Prefix notation)

From Wikipedia, the free encyclopedia

Prefix-dia.svg

Polish notation, also known as Polish prefix notation or simply prefix notation, is a form of notation for logic, arithmetic, and algebra. Its distinguishing feature is that it places operators to the left of their operands. If the arity of the operators is fixed, the result is a syntax lacking parentheses or other brackets that can still be parsed without ambiguity. The Polish logician Jan Łukasiewicz invented this notation in 1924 in order to simplify sentential logic.

The term Polish notation is sometimes taken (as the opposite of infix notation) to also include Polish postfix notation, or Reverse Polish notation, in which the operator is placed after the operands.[1]

When Polish notation is used as a syntax for mathematical expressions by interpreters of programming languages, it is readily parsed into abstract syntax trees and can, in fact, define a one-to-one representation for the same. Because of this, Lisp and related programming languages define their entire syntax in terms of prefix notation (and others use postfix notation).

In Łukasiewicz 1951 book, Aristotle’s Syllogistic from the Standpoint of Modern Formal Logic, he mentions that the principle of his notation was to write the functors before the arguments to avoid brackets and that he had employed his notation in his logical papers since 1929.[4] He then goes on to cite, as an example, a 1930 paper he wrote with Alfred Tarski on the sentential calculus.[5]

While no longer used much in logic,[citation needed] Polish notation has since found a place in computer science.

Simple.  Now when we come across this again in the future, I’ll not look so blank.