A major event in the history of programming language design was John McCarthy's invention of conditional expressions in the late 1950s. They made their way into Algol 60 (see  the CACM paper or  this web version) in the form

if p then a else b

which could be cascaded as

if p then a else if q then b else ... if r then c else d

and also into Lisp (see  the 1960 CACM paper or  this LaTeX-formatted version) in the form

(COND (p a) (q b) ... (r c) (T d))

If you are familar with the original Lisp 1.5 Programmer's Manual from 1962, you may remember the "M-expression" notation

[p -> a; q -> b; ... ; r -> c; d]

And today most of us are familiar with the form

p ? a : q ? b : ... r ? c : d

as used in C, Java, JavaScript, C#, Ruby, and many other languages.

None of these was McCarthy's preferred form for the notation, however. If we examine his writings cited above, we find that he tended to use a version with parentheses and commas, rather than brackets and semicolons:

(p -> a, q -> b, ... , r -> c, d)

He used the brackets-and-semicolons version only when mixing this notation with Lisp S-expressions, so that the brackets would stand out from the parentheses.

As for the origin of the "if-then-else" form of conditional expression, McCarthy said this in a footnote to his 1960 CACM paper:

I sent a proposal for conditional expressions to a CACM forum on what should be included in Algol 60. Because the item was short, the editor demoted it to a letter to the editor, for which CACM subsequently apologized. The notation given here was rejected for Algol 60, because it had been decided that no new mathematical notation should be allowed in Algol 60, and everything new had to be English. The if...then...else that Algol 60 adopted was suggested by John Backus.

To see the importance of conditional expressions (which we now largely take for granted), let's look at how Mikhail Botvinnik, an electrical engineer and one of the great Soviet chess grandmasters, used conventional mathematical notation to express his algorithms for programming a computer to play chess. (M. M. Botvinnik, Computers, Chess, and Long-range Planning (translated by Arthur Brown), Springer-Verlag, 1970.) Botvinnik encoded truth values as the numerical values 1 and 0, much as Ken Iverson did in the programming language  APL (and note that this encoding was also eventually used in C, but Java repudiated this trick and adopted a distinct boolean type). Then instead of writing p | q (as we would in C or Java), or p OR q (as we might in Fortress), he wrote

p + q - p·q

In like fashion, whereas nowadays we might write

tau[m] = (m >= -0.1)

Botvinnik found it necessary or desirable to write

tau[m] = 1/2 DOT (1 + (m+0.1)/(|m+0.1|))

which of course is not only harder to understand but also not quite kosher when m is exactly equal to -0.1 (which in practice can be sidestepped either by decreeing that 0/0 = 1 for purposes of such expressions or by making sure that m never has the exact value -0.1). I mention this example not to disparage Botvinnik's pioneering effort, but to point up the deficiencies of the conventional notation available to him: he found it necessary to encode boolean values numerically and to manipulate them arithmetically. What we write as

p ? a : b

he would have written as

p·a + (1-p)·b

Don Knuth, in his 1997 revision of his Art of Computer Programming series, used brackets as an explicit notation for converting boolean results into 1-or-0 values (Donald E. Knuth, The Art of Computer Programming, Volume I: Fundamental Algorithms, updated and revised, Addison-Wesley, 1997, section 1.2.3). This allows him to write, for example, something like

SUM[i <- A] x[i] [1 <= i < n]

whereas in Fortress we would write this as

SUM[i <- A, 1 <= i < n] x[i]

(Two of the reasons that I prefer the Fortress version are that (1) it avoids the run-time cost of multiplication operations, however trivial that might be, and (2) it avoids some unpleasant nit-picky semantic difficulties when IEEE 754 floating-point arithmetic is involved, because adding +0 to something is not always the same as not performing an addition at all).

This use of brackets is now known as the  Iverson bracket, and was originally suggested by Knuth, as an improvement to Iverson's notation, in the lovely and very readable 1992 paper  Two Notes on Notation, which also delves into the history of the problem and admits that difficulties and discrepancies can arise when you multiply a value by zero rather than omitting the value from the calculation altogether. (Knuth, D. E. 1992. Two notes on notation. Am. Math. Monthly 99, 5 (May, 1992), 403-422. DOI=  http://dx.doi.org/10.2307/2325085 )

There are two other notations for conditional expressions that deserve our attention. One is the form chosen for Python ( version 2.5, PEP 308):

a if p else b if q else ... c if r else d

which may seem strangely inverted at first; but its symmetry, neatly interleaving the n+1 result values with the n predicate expressions, is worthy of admiration. Then again, this symmetry may seduce the reader into thinking that the notation can be read right-associatively from right to left, rather than left-associatively from left to right as intended. And there is the problem that the subexpression p is, after all, evaluated before the subexpression a, contrary to the left-to-right mandate, which some readers might find counterintuitive. But I cannot throw stones, because in Fortress one can write things like

a[k] := k, k <- 1:10, prime k
i := j, i < j

where governing generators and conditions occur to the right of the expressions they govern. Not everyone likes this, but it is based on solid and long-standing mathematical tradition.

(When the conditional-expression syntax was  voted on for Python, a large number of alternatives were considered:

  A.  x if C else y
  B.  if C then x else y
  C.  (if C: x else: y)
  D.  C ? x : y
  E.  C ? x ! y
  F.  cond(C, x, y)
  G.  C ?? x || y
  H.  C then x else y
  I.  x when C else y
  J.  C ? x else y
  K.  C -> x else y
  L.  C -> (x, y)
  M.  [x if C else y]
  N.  ifelse C: x else y
  O.  <if C then x else y>
  P.  C and x else y

Truly there is no shortage of creative ingenuity in our field.)

As an additional historical footnote, Iverson's original notation had a similar sort of expression /b,p,a/ with the "then" value a on the right and the "else" value b on the left (and the predicate p in the middle). This operation was called "mask" and operated elementwise on vectors or arrays, like many other APL operators. This notation appeared only in his original book as a "paper notation" and was not implemented as part of APL\360 or any subsequent computer implementation, as far as I know. (Kenneth E. Iverson, A Programming Language, John Wiley and Sons, 1962, page 21.)

The other notation that deserves our attention is one frequently used in the mathematical literature, notable for its use of a left brace without a matching right brace. It can be approximated in ASCII in this way:

           /  -x,   if x < 0;
  abs(x) = |   0,   if x = 0;
           \   x,   otherwise.

I show this ASCII form because it was seriously contemplated as one possible ASCII input notation in early versions of Fortress, about five years ago. I mention the notation at all because Knuth used it to define his bracket notation for converting boolean results to 1-or-0 values:

                /  1,   if the statement is true;
  [statement] = |
                \  0,   if the statement is false.

What is even more interesting, however, is that in the "Index to Notations" at the back of the book (page 624), the notation "[B]" is defined simply as the "characteristic function of condition B" and then this formula is given:

(B=>1; 0)

which of course is a variant of McCarthy's notation, using parentheses on the one hand but a semicolon on the other (a combination McCarthy did not use, as far as I know), and using a double-shafted right arrow rather than a single-shafted one. This form of conditional expression is defined by the preceding entry in the Index to Notations, but apparently is not defined in the main text. On the other hand, if we go back to the first edition of the same book from 1968, we find that this same formula, with parentheses and semicolon and double-shafted right arrow, is listed in the Index to Notations as being defined in Section 8.1, which as of this blog post, 40-odd years later, still has not been written (and I do hope that, God willing, Knuth will find the time and energy to complete it!).

In Fortress, we have adopted something close to the Algol 60 notation for conditional expressions, but using an explicit terminator end to avoid the  dangling else problem, as well as other related parsing difficulties:

if p then a elif q then b ... elif r then c else d end

(I would have preferred to use fi as the terminating token rather than end, as in  Algol 68 (see the  revised report as a web page) and to use od rather than end as the terminator for a do block. But I have to admit that this business of spelling keywords backwards is a slippery slope, and I would not have liked to see a keyword esac to terminate a case statement, much less a keyword esacepyt to terminate a typecase statement. My colleagues on the Sun Fortress project outvoted me. Fortress was never "Guy Steele's language" but a team effort, and is much the better for it.)

The same form can be used as either a statement or an expression. It is permitted but not necessary to break it across several lines, which is not uncommon when the construction (and the subexpressions a, b, ..., c, d) are statements:

if p then a
elif q then b
...
elif r then c
else d
end

Moreover, as a convenience, if the statement is followed by a right parenthesis or other right encloser, then the end token may be omitted:

x = (if p then a elif q then b ... elif r then c else d) + 3

However, for some purposes this can still seem verbose compared with, say,

x = (p => a; q => b; ... ; r => c; d) + 3

Which brings me to my question of the week: should Fortress adopt some more concise version of McCarthy's notation? Or let me put it another way: I would hope that we could do it through the syntactic extension mechanism. If someone were to write a library to provide concise McCarthy notation, would people use it? What version would you like to see? Or are we better off without it?

I happen to favor Knuth's version, for four reasons:

1. Brackets are already heavily overloaded in Fortress.
2. If we use semicolons instead of commas, then they can be omitted if a line break follows.
3. The double-shafted right arrow better matches the syntax of case statements.
4. He's Knuth.

One counterargument is that it might be confused with keyword-tuple notation, so brackets might be the better choice after all. But I'd like to hear your opinions as well.

One of the problematic features of the Java programming language is that fact that every reference type includes null as a possible value. For many purposes this is very convenient, but it has the drawback that in principle every field reference and every method call might possibly fail, throwing a "null pointer" exception. This behavior is of course more desirable than the Unix segmentation faults often observed by C programmers, but there is much to be said for a type system that, when you claim that a variable is of type String, ensures that the value actually always is a String instance and not a null reference.

Another oddity of the Java programming language is that the instanceof operator always produces false when the value being tested is null. Therefore, even if variable x is declared to have type String, x instanceof String might be false, which can look a little strange at first sight, and might mislead a maintenance programmer who is focusing on other issues.

The early design of the C# programming language was quite similar, the most visible difference being syntactic: the operator analogous to instanceof was, and is, called "is". (See the C# Language Specification, Standard ECMA-334, December 2001.)

A "late-breaking feature" in C# version 2.0 was nullable types (see  Eric Gunnerson's 2004 blog entry on this topic, as well as the  Wikipedia article). Looking at the  fourth edition of the ECMA C# standard (July 2006), page 62, we find a very readable introductino to this feature, from which I quote the first two paragraphs:

Support for nullability across all types, including value types, is essential when interacting with databases; yet, historically, general-purpose programming languages have provided little or no support in this area. Many approaches exist for handling nulls and value types without direct language support, but all have shortcomings. For example, one approach is to use a "special" value (such as -1 for integers) to indicate null, but this only works when an unused value can be identified. Another approach is to maintain Boolean null indicators in separate fields or variables, but this doesn't work well for parameters and return values. A third approach is to use a set of user-defined nullable types, but this only works for a closed set of types. C#'s nullable types solve this long-standing problem by providing complete and integrated support for nullable forms of all value types.

Nullable types are constructed using the ? type modifier. For example, int? is the nullable form of the predefined type int. A nullable type's underlying type must be a non-nullable value type.

The last sentence notes two limitations of C#'s nullable types: (a) they apply only to value types, not to reference types (every reference type in C# still allows null as a value), and (b) they cannot be nested.

It is worth comparing the design of C# with that of the  Cyclone programming language, designed to be a "safer" dialect of C (see also the  Wikipedia article. Among other features, it has "non-null pointer types", written with a @ character rather than the usual * character. Here are the first two sentences of the abstract from a  2002 ACM PLDI paper about Cyclone:

Cyclone is a type-safe programming language derived from C. The primary design goal of Cyclone is to let programmers control data representation and memory management without sacrificing type-safety.

(Grossman, Morrisett, Jim, Hicks, Wang, and Cheney. Region-based memory management in Cyclone. Proc. ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, 282-293.  Also available from Citeseer.)

In contrast, the language Haskell supports the Maybe type, which is a form of  option type. Values of type Maybe Int, for example, are of the form Just n (where n is any value of type Int) or the alternate value Nothing. A key difference between an option type and a nullable type is that option types may be nested; the type Maybe (Maybe Int) is different from the type Maybe Int, and in effect can encode any Int value plus two distinct alternate values; an integer value such as 3 is encoded as Just (Just 3), and the two alternate values are Nothing and Just Nothing. For those who care about category theory, Maybe is a  monad. A slightly more pragmatic way to think about a value of type Maybe T is that it is a set (with elements of type T) whose size (cardinality) is either 0 or 1.

And that brings us to Fortress.  (Remember Fortress? It's a blog about Fortress.) In Fortress, if a variable has type String, then it must always contain a reference to an object of type String; there is no such thing as a "null reference" in Fortress. But Fortress also has a parameterized Maybe trait similar to Haskell's Maybe type. In the standard Fortress libraries, the type Maybe[\T\] is used in situations where one would normally expect to retrieve a value of type T but sometimes no such value is present, and it is more convenient to return an alternate value than to throw an exception. For example, Java indexOf methods typically return an int value that is an index k into a string or collection for a sought item, but return -1 if the item is not found. Fortress indexOf methods instead return either Just k or Nothing. As another example, given a map m and a key k, looking up the key k in the map m is normally expected to return the value v associated with k, but it may be that m contains no key-value pair with a key matching k. The current implementation of maps in the standard Fortress library provides several methods that handle this situation in different ways:

This is perhaps not the best interface; it's a bit strange for member to return values of different types depending on whether it gets one or two arguments. (Yes, Fortress is flexible enough to let you do this, but it may be an unnecessary mental burden for application programmers.)

Fortress goes beyond Haskell in that the type Maybe[\T\] extends type Generator[\T\] so that it can be treated much like a set that will generate either one item or no items at all. One can conveniently use generator syntax to extract the contained item of a Maybe type, bind a variable to that value, and then execute a chunk of code---but only if there is in fact a contained item:

for v <- m.member(k) do
  println("We found a value: " || v)
end

This idiom got us to thinking about collections, and the fact that there are (at least) three cases of interest for the number of items generated: "0", "1", and "2 or more". I believe that when a language designer encounters a small set of categories like this, a useful exercise is to systematically consider the power set, that is, the set of all subsets of the set of categories. This led to three interesting ideas, two of which are now exploited in Fortress:

(a) If the only possibilities are "0" and "1", no parallelism is possible.

(b) If the only possibilities are "0" and "1", it may be useful to execute different blocks of code for case "0" (on the one hand) and case "1" (on the other).

(c) It may be useful to execute different blocks of code for case "0" (on the one hand) and cases "1" and "2 or more" (on the other).

(There are additional possibilities based on other possible subsets of the three cases. but they all seemed less interesting than these.)

Item (b) led to an augmentation of the if-then-else construct to allow generator syntax: instead of

for v <- m.member(k) do 
  println("We found a value: " || v)
end

as shown above, one may instead write

if v <- m.member(k) then
  println("We found a value: " || v)
end

The if form requires that the generator in fact be of type Condition[\T\] for some T; the trait Condition[\T\] extends trait Generator[\T\], and Maybe[\T\] extends Condition[\T\]. The trait Condition guarantees never to generate more than one item. So use of the if construct rather than the for construct gives us two guarantees and a bonus feature:

(i) At most one thing will be generated.

(ii) No parallelism will be involved (see item (a) above), which allows the implementation to avoid certain overheads.

(iii) An else clause can be used to address the case of 0 items being generated:

if v <- m.member(k) then
  println("We found a value: " || v)
else
  println("There was no value for " || k)
end

This makes it much more convenient to deal with values of option types. Remember also that such generator syntax can be used in comprehensions and reductions, in effect serving as a Boolean filter but also providing an item (and a name for it).

The generalization we have not (yet) put into Fortress is allowing an else clause on a for construct, suggested by item (c) above:

(*) An `else` clause like this is **not** currently supported in Fortress.
for v <- myList do
  mySet UNION= { v }
else
  println "The list was empty."
end

You have to draw the line somewhere. If someone produces a compelling use case, then we could consider it. (One issue is that if we allow else clauses on for loops, then for consistency we might have to allow else clauses, or some equivalent, on comprehensions and reductions. Yecch.)

In the meantime, there remain some open questions. Is the syntax Maybe[\T\] sufficiently concise for use in Fortress, or should we consider using a single character, writing that type as "T?" or something like that? And as a matter of style and design philosophy, when should we use option types for return values rather than throwing an exception---or is it worthwhile generally supporting both forms in most libraries? Would users prefer for m[k] to mean m.member(k) rather than m.getVal(k), and if so would they also prefer to write something like

m[k] ?? d

(as in C#) rather than

m.member(k,d)

? Your comments are welcome.

Happy new year! We took a break from blogging over the end-of-year holidays, but we didn't stop working on the ProjectFortress wiki. You may have noticed, in the past, that Fortress code as rendered on this website has looked a little bit fuzzy or "out of focus". We have been trying to find a combination of tools that will produce crisply rendered code when viewed at all magnifications in all browsers.

The best technological solution we have found for producing beautiful, crisp rendering at all magnifications is to use PDF files. Unfortunately, while many browsers support viewing of individual PDF pages, one at a time, most browsers do not support inclusion of multiple PDF images within a single HTML page. Therefore we choose to generate PNG files. This, unfortunately, requires resolution to be chosen ahead of time, and there are trade-offs between adequate resolution and file size (and the latter affects both download time and page regeneration time).

Anyway, Gary Cutbill (who got the entire Trac-based Fortress-rendering process working in the first place), David Chase, and I have been experimenting with alternatives over the last couple of months and have now released a new PNG-based rendering strategy that we hope will provide a better code-reading experience. We will continue to tune it over the next few weeks. Please let us know whether you encounter any difficulties or anomalies.

Just so you have some Fortress code to look at, here is a bit of code I wrote during the summer of 2008 to convert an integer value into an English ordinal adjective:

component Ordinals
import  PureList.{...}
export Executable

numericOrdinalsEnglish = <| "zeroth", "first", "second", "third", "fourth", "fifth",
  "sixth", "seventh",  "eighth", "ninth", "tenth", "eleventh", "twelfth", "thirteenth",
  "fourteenth", "fifteenth", "sixteenth", "seventeenth", "eighteenth", "nineteenth" |>

tensOrdinalRootsEnglish = <| "", "", "twent", "thirt", "fort", "fift", "sixt",
  "sevent", "eight", "ninet" |>

opr (n: ZZ32)TH : String =
  if 0 <= n <= 19 then
    numericOrdinalsEnglish[ n ]
  elif 20 <= n <= 99 then
    if n MOD 10 = 0 then
      tensOrdinalRootsEnglish[ n DIV 10 ] || "ieth"
    else
      tensOrdinalRootsEnglish[ n DIV 10 ] || "y-" || numericOrdinalsEnglish[ n MOD 10 ]
    end
  elif -99 <= n <= -1 then
    "minus-" || (-n)TH
  else
    s = n || (if 11 <= |n REM 100| <= 13 then "th"
              else case |n REM 10| of
                     1 => "st"
                     2 => "nd"
                     3 => "rd"
                     else => "th"
                   end
              end)
    if n < 0 then "minus" || s else s end
  end

run(args: String...): () = do
  println "Hello, world!"
  for k <- seq((-125)#251) do
    println (k)TH
  end
end

end

Note that it is implemented as a postfix operator named TH. The run routine tests it on values from -125 to 125; here are some excerpts of its output:

minus-125th
minus-124th
minus-123rd
minus-122nd
minus-121st
minus-120th
...
minus-102nd
minus-101st
minus-100th
minus-ninety-ninth
minus-ninety-eighth
minus-ninety-seventh
...
minus-seventh
minus-sixth
minus-fifth
minus-fourth
minus-third
minus-second
minus-first
zeroth
first
second
third
fourth
fifth
...
eighteenth
nineteenth
twentieth
twenty-first
twenty-second
twenty-third
twenty-fourth
twenty-fifth
twenty-sixth
twenty-seventh
twenty-eighth
twenty-ninth
thirtieth
thirty-first
thirty-second
...
ninety-seventh
ninety-eighth
ninety-ninth
100th
101st
102nd
103rd
104th
105th
106th
107th
108th
109th
110th
111th
112th
113th
114th
115th
116th
117th
118th
119th
120th
121st
122nd
123rd
124th
125th