1
$\begingroup$

In Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, i.e. "the LISP paper", John McCarthy introduces a notation for conditional expression as follows:

$(p_{1} \rightarrow e_{1},\dotsc,p_{n} \rightarrow e_{n} )$

Example:

$(1 < 2 \rightarrow 4, 1 > 2 \rightarrow 3) = 4$

Was this notation ever picked up by the computer science or math communities? It's my impression that it wasn't.

If not, was it because the use of the brace notation was already well-established?

$\endgroup$
1
$\begingroup$

I think you are right that the notation has not been widely adopted, but many programming languages do have conditional expressions using a different syntax. some have the comb structure of McCarthy's notation. Others are binary-branching and give McCarthy's conditional through nesting.

A binary variant $t\to a,b$ "if $t$ then $a$ else $b$" of the original notation is used in the denotational semantics of the programming language Scheme (possibly more widely in the semantics community, but I wouldn't know). When nested so that $b$ is another conditional expression, it becomes McCarthy's original (assuming parentheses are optional) up to the last expression which is an "else" branch: $$ p_1\to e_1, p_2\to e_2,\cdots, p_{n-1}\to e_{n-1},e_n $$ With McCarthy's notation, it was usual for the last condition to be always true anyway.

Lisp has always had, and still has, the comb-structured McCarthy conditional, and the binary-branching variant is also standard for decades:

(cond ((p1 e1) (p2 e2) ... (pn en)))
(if t a b)

The C programming language uses the following notation for binary-branching conditional expressions. Many later languages have adopted this notation. The user population has named the pair of characters the ternary operator.

t ? a : b

The Python programming language has a different variant:

a if t else b

Both of the above two can be chained to give the meaning of McCarthy's comb-structured expression. (One should also look into other, so-called functional programming languages for more of these, but the main point is that conditional expressions are well and widely available in programming languages.)

The brace notation of mathematics is different in that the order of the branches is not significant. An "otherwise" branch may be used, but the following is considered wrong because it would specify both values when $x = 2$. $$ \begin{cases} 4 & \text{if $x\le 2$} \\ 3 & \text{if $x\ge 2$} \end{cases} $$

Mathematics has its own device: functions that give $1$ when a condition is satisfied and $0$ otherwise. This allows at least numerical expressions whose value depends on the condition: $$ a\cdot t(x) + b\cdot t(x) $$ The Graham, Knuth, Patashnik book, Concrete Mathematics: A foundation for computer science advocates the use of "Iverson brackets" for turning any statement into a truth value this way: $$ a\cdot[x \ge 2] + b\cdot[x \le 2] $$ There is even a convention to make the brackets so strongly $0$ that they can undo an otherwise undefined expression. (Use with care, I suppose.)

With (the binary-branching variant of) McCarthy conditional, the above would be: $$ (x\ge 2\to a, 0) + (x\le 2\to b, 0) $$ Or the original: $$ (x = 2\to a + b, x\ge 2\to a, x\le 2\to b) $$

$\endgroup$
  • $\begingroup$ Thanks for the information answer. I know that Lisp has adopted a cond form that uses notation similar to McCarthy's; I was wondering about the adoption of the notation in written works, e.g. papers. You're absolutely right that the brace notation is different in that the order of branches is not significant. I had not considered that when I posted the question. $\endgroup$ – Tianxiang Xiong Jan 24 '16 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.