# Is McCarthy Formalism first ever formalism for defining functions recursively in computer science?

McCarthy formalism is a formalism for defining functions recursively, first introduced in classic paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (1960).

From Wikipedia:

In his 1967 Computation: Finite and Infinite Machines, Marvin Minsky in his § 10.6 Conditional Expressions: The McCarthy Formalism describes the "formalism" as follows:

"Practical computer languages do not lend themselves to formal mathematical treatment--they are not designed to make it easy to prove theorems about the procedures they describe. In a paper by McCarthy  we find a formalism that enhances the practical aspect of the recursive-function concept, while preserving and improving its mathematical clarity.

McCarthy introduces "conditional expressions" of the form f = (if p1 then e1 else e2) where the ei are expressions and p1 is a statement (or equation) that may be true or false. This expression means: See if p1 is true; if so the value of f is given by e1. IF p1 is false, the value of f is given by e2. [...]

The McCarthy formalism is like the general recursive (Kleene) system, in being based on some basic functions, composition, and equality, but with the conditional expression alone replacing both the primitive-recursive scheme and the minimization operator." (Minsky 1967:192-193)

I'm interested in chronology. Was there any other formalism regarding recursive function before McCarthy Formalism (in computer science)?

• Such as Gödel's formalism for general recursive functins which predates McCarthy by at least 25 years? – Andrej Bauer Mar 8 '19 at 18:23
• Sure, but that's mathematics. I'm asking specifically about computer science. – Siegmeyer Mar 9 '19 at 10:24
• @Siegmeyer In TCS, there is no meaningful difference. $\mu$-recursion and $\lambda$-calculus are mathematical models we use in computer science. See also this question. – Raphael Mar 9 '19 at 11:45
• FWIW, formal semantics seem to have emerged later. Is that the field you are referring to, as opposed to computability/recursion theory? – Raphael Mar 9 '19 at 11:47
• @Siegmeyer: Wehre do you think people like McCarthy got their ideas from? They were very knowledgable, also about mathematics. – Andrej Bauer Mar 10 '19 at 0:00