Polish Contributions to Computing
Jan Lukasiewicz [pron. YAN wu-ka-SHAY-vich] was born on December 21, 1878 in Lwów, Poland (Lemberg, Austro-Hungary), now Lviv, Ukraine, and died on February 13, 1956, in Dublin, Ireland. He obtained his doctorate in philosophy, in 1902, under Kazimierz Twardowski, at Jan Kazimierz University in Lwów, and worked there until World War I. Then, he moved to the Warsaw University, where he became a professor (serving also shortly as a Minister of Education) and worked until World War II. After the war, he accepted a chair at the University College Dublin, where he stayed until his death.

Major Contribution: Invention of the Polish Notation (also known as a parentheses-free notation or prefix notation) in 1924. It must be noticed though, that the main research area of Jan Lukasiewicz was mathematical logic, and his major accomplishments there, such as invention of multi-valued logic, far surpassed everything else.

Basic Questions
What is the Polish Notation? Briefly, the Polish Notation is a principle of writing mathematical expressions in an operator-first manner, while traditional notation involves placing an operator between arguments. That way, due to the properties of the Polish Notation, one can completely avoid using parentheses. There are many websites providing detailed explanations of the principles of Polish Notation, some of them listed under the Resources button on this page. While most people who are active in computing heard about or even learned the Polish Notation, literally no one can accurately answer the basic historical questions:
  • when exactly was the Polish Notation invented, and
  • when was it applied in computing for the first time.
In the best analysis known to us of the historical origins of the Polish Notation, John Kennedy states the following [1]: “A description of his notation was published in two of his works in 1929 […]. This idea must have originated in the year 1928 (or earlier).” Digging into the early works of Lukasiewicz [2,3] reveals the following statement in a footnote to [2]: “I came upon the idea of a parenthesis-free notation in 1924. I used that notation for the first time in my article [3], p. 610, footnote.” However, he also states that the notation was used earlier by Lesniewski [2]: “At the beginning of his German-language treatise on the Foundations of Mathematics, Dr. Lesniewski parenthically mentions (with my approval) a certain ‘simplification’ of Nicod’s axiom made by me in 1925 […]”. The full text of Lukasiewicz’ article on Nicod’s axiom is placed (with permission) on this website under the Resource button.

The date of the first application of the Polish Notation in computing is less clear. Kennedy lists an article by Burks et al. [4], although without explanation, but that suggests that this was the first use of the Polish Notation in computing, in 1953. However, Burks et al. also published an earlier report [5], in which they explicitly used the term Polish Notation in the title. Although they do not quote the source of their information on the Polish Notation, it is likely that it was the publication of the English translation of the Lukasiewicz’ book [6]. On the other hand, Bauer, in multiple articles on his machine Stanislaus [7-9], named such “in honor of the Polish school of logic” [9], explains in detail how he came to learn about this notation, which he initially called the Warsaw notation [7], that brought him to the concept of a stack (Kellerprinzip). He first heard of it in 1948-49, at the seminar by a German inventor Konrad Zuse, who got the idea from the Viennese logician Karl Menger (1943), who in turn learned about it from a Berlin logician Karl Schroter (1935). It all goes back to the German language article, quoted by Bauer, published by Jan Lukasiewicz and Alfred Tarski, in 1930 [10].

Significance
It is remarkable that to Lukasiewicz himself inventing the parenthesis-free notation was a rather minor fact. He barely mentions it in one footnote referring to another. However, his discovery had a tremendous impact on computing. In particular, it prompted invention of the Reverse Polish Notation (RPN) [11], which led directly to the concept of a stack [8,12,13]. This, in turn, had a direct impact on the shape of programming languages, such as Algol [9], and their compilers. It is worth mentioning, what one of the first computing practitioners, Bob Cralle, from Lawrence Livermore National Labs, states on the importance of this notation for a compiler [14]: “the people who did the first FORTRAN were unaware of his [Lukasiewicz] work, which allowed one easily do one pass through an algebraic statement and parse it into instructions with which the computer could compute.” It is also worth noting that Lukasiewicz’ other contributions have a significant impact on disciplines closely related to computing. For example, his 1913 study on probability calculus lays theoretical foundations for fuzzy sets [15], and his invention of three-valued and multivalued propositional calculi [16] established a whole branch of logic and led to his only two papers published in a computer related journal [17,18]. Several volumes of translations of Lukasiewicz’ work have been published in English, of which the two most complete are [19,20].

Findings
The contribution of this website is in bringing for the first time to the general audience, information known only to specialists: (1) answer on the actual source of the Polish Notation (originated in 1924), and (2) clarification on the first use of the Polish Notation in computing (early 1950s, both in Germany and the U.S.).

References [hide]

[1] J. Kennedy, RPN Perspective, PPC Calculator Journal, Vol. 9, No. 5, pp. 26-29, August 1982
[2] J. Lukasiewicz, Uwagi o aksjomacie Nicoda i dedukcji uogólniajacej, Ksiega pamiatkowa Polskiego Towarzystwa Filozoficznego, Lwów, 1931, s. 366-382 (Comments on Nicod’s Axiom and on “Generalizing Deduction”, L. Borkowski (Ed.), Jan Lukasiewicz Selected Works, North-Holland, Amsterdam, 1970, pp. 179-196)
[3] J. Lukasiewicz, O znaczeniu i problemach logiki matematycznej (On the Significance and Needs of Mathematical Logic), Nauka Polska, Vol. 10, pp. 604-620, 1929
[4] A. Burks, D. Warren, J. Wright, An Analysis of a Logical Machine Using Parenthesis-Free Notation, Math. Tables and Other Aids to Computation, Vol. 8, No. 46, pp. 53-57, April 1954
[5] A. Burks, D. Warren, J. Wright, “Truth-Function Evaluation Using the Polish Notation”, Project M828, Burroughs Adding Machines Co., Detroit, Michigan, July 8, 1952
[6] J. Lukasiewicz, Aristotle’s Syllogistic from the Standpoint of Modern Formal Logic, Clarendon Press, Oxford, 1951
[7] F.L. Bauer, The Formula-Controlled Logical Computer “Stanislaus”, Math. Tables and Other Aids to Computation, Vol. 14, No. 69, pp. 64-67, 1960
[8] F.L. Bauer,The Cellar Principle of the State Transition and Storage Allocation, IEEE Annals of the History of Computing, Vol. 12, No. 1, pp. 41-49, 1990
[9] F.L. Bauer, From the Stack Principle to Algol, Proc. Conf. Software Pioneers: Contributions to Software Engineering, Bonn, June 28-29, 2001, A. Broy, E. Denert (Eds.), pp. 26-42, Springer-Verlag, New York, 2002
[10] J. Lukasiewicz, A. Tarski, Untersuchungen über den Aussagenkalkül, C.R. Soc. Sci. Lett. Varsovie, Ch. III, Vol. 23, pp. 30-50, 1930
[11] C. L. Hamblin, Translation to and from Polish Notation. The Computer Journal, Vol. 5, pp. 210-213, 1962
[12] C. L. Hamblin, Computer Languages, The Australian Journal of Science, Vol. 20, pp. 135-139, 1957.
[13] F.G. Duncan, Stack Machine Development: Australia, Great Britain, and Europe, Computer, Vol. 10, No. 5, pp. 50-52, May 1977
[14] G. Michael, An Interview with Bob Cralle, Stories of the Development of Large Scale Scientific Computing at Lawrence Livermore National Laboratory, http://www.computer-history.info/
[15] R. Giles, Lukasiewicz logic and fuzzy set theory, International Journal of Man-Machine Studies, Vol. 8, pp. 313-327, 1976.
[16] L. Borkowski, J. Slupecki, The Logical Works of J. Lukasiewicz, Studia Logica, Vol. 8, pp. 7-56, 1958.
[17] J. Lukasiewicz, A System of Modal Logic, The Journal of Computing Systems, Vol. 1, No. 3, pp. 111-149, 1953
[18] J. Lukasiewicz, Arithmetic and Modal Logic, The Journal of Computing Systems, Vol. 1, No. 3, pp. 213-219, 1954
[19] L. Borkowski (Ed.), Jan Lukasiewicz Selected Works, North-Holland, Amsterdam, 1970
[20] J. Srzednicki et al. (Eds.), Collected Works of Jan Lukasiewicz. I: Mathematical Logic. II: History of Logic. III: Methodology of Science and General Philosophy, Ashgate Publishing, 2006

Copyright 2006. All rights reserved. W3C XHTML Compliant Valid XHTML 1.0 Transitional