Lambda the Ultimate

but I prefer the lucid version,

 h
   where
     h = 1 fby merge(merge(2 * h, 3 * h), 5 * h);
     merge(x,y) = if xx <= yy then xx else yy fi
        where 
          xx = x upon xx <= yy;
          yy = y upon yy <= xx;
        end;
   end;

Xref: a previous lengthy discussion of the Hamming problem.

Much as people say "well, can a language do what lisp can do?", I tend to judge procedural languages on whether they can do Duff's device. It's a pretty short list.... :)

Oh, I don't think Duff's Device is an irresistible feature for language designers. But it is an irresistible puzzle to a programmer - at least it was to this programmer back when. How could it possibly mean anything?

The intriguing part to me is that you can generally understand things in an abstraction "black box" way or an implementation "white box" way. Normally the former view is more useful for composing things because you can ignore irrelevant details. But Duff's Device seems like an exception. When you think of switch and do/while as black box control flow operators Duff's device appears to be gibberish. "Case 1 falls through to a 'while' without having gone through a matching 'do'...WTF?" Yet when you think of switch and do/while as syntactic sugar for certain patterns of conditional jmp then it snaps into clear focus.

That might be why Duff said

I feel a combination of pride and revulsion at this discovery.

The quote I like is “Many people (even bwk?) have said that the worst feature of C is that switches don't break automatically before each case label. This code forms some sort of argument in that debate, but I'm not sure whether it's for or against.”

Keeping in mind that I wasn’t asking just for language design examples. And in fact the device surely makes one curious about language semantics.

Conway's Game of Life isn't just irresistible for the opportunities to play golf in APL, but also because it let's you create irresistible "programs" in the game - initial configurations that lead to beautiful long running or infinite executions. Gosper's Glider Gun is particularly irresistible.

I have a soft spot for bit twiddling, especially bit-parallel SIMD-within-a-register implementations of Life.

When it comes to Prolog and examples, I prefer the Sequence Program discussed by Apt here. However, I’d prefer to have examples that come from specific historical context, and that tell something about the relevant era.

N queens certainly admits elegant Prolog realisations, and has a history, but I don't know enough to cite a particular piece of code as classic.

Google search throws up an implementation in Yield Prolog that is certainly concise, but I think can be made more elegant.

Come to think of it: the classic here would be Wirth's version from Program Development by Stepwise Refinement (1971).

Prolog is a challenge. The language as a whole has historical significance and creates a rich vein of intriguing programs for obvious reasons, but since logic programming has lived so far off center stage it's hard to think of Prolog examples that are "classic" (in the sense of well known and archetypal) other than the standard pedagogical intro of father/ancestor/sibling, but that's just not historically interesting.

Maybe there's something in language processing.

True.

Ehud missed the link in the parent post. I think he means the example on p20 of The LP paradigm and Prolog.

There's certainly some appeal to the example, but I think it falls short of being arresting.

True and true.

Your Prolog example really took me back to my days at Uppsala University, where our professor, Sten-Åke Tärnlund, was mainly known among the students as one of the "inventors" of "difference lists" (d-lists). (Apparently, the use of incomplete data structures in Prolog was common, but Clark and Tärnlund were the first to publish this particular example.)

The difference list is a really neat programming trick that uses unification of logic variables in Prolog to achieve a non-recursive, constant-time append:

append(A-B, B-C, A-C).

That's it!

A difference list A-B represents a list A followed by a tail B. For example:

[a, b, c | []]-[]

would represent the list [a, b, c]. If we use a logic variable for the tail part:

[a, b, c | X]-X

we can unify the logic variable X with another list to append the two.

Prolog's logic variables are kind of used to implement pointer manipulation, but with a logical interpretation.

As an example

append([a, b, c | Z1]-Z1, [d, e, | Z2)-Z2, X-Y).

would result in X-Y being [a, b, c, d, e | Y]-Y

Difference lists are no doubt of historic significance for Prolog: It was previously unclear how to implement DCGs efficiently. A very nice use of difference lists is the following meta-circular evaluator ("meta-interpreter") for Prolog:

mi([]).
mi([G|Gs]) :-
        mi_clause(G, Rest, Gs),
        mi(Rest).

Here is a simple example program in the required representation, making use of list differences to efficiently join remaining goals:

mi_clause(natnum(0), Rs, Rs).
mi_clause(natnum(s(X)), [natnum(X)|Rs], Rs).

The interpreter can evaluate this program:

%?- mi([natnum(X)]).
%@ X = 0 ;
%@ X = s(0) ;
%@ etc.

The interpreter's own code can also be represented:

mi_clause(mi([]), Rs, Rs).
mi_clause(mi([G|Gs]), [mi_clause(G,Rest,Gs),mi(Rest)|Rs], Rs).

mi_clause(mi_clause(G,Rs,Rs0), Ls, Ls) :- mi_clause(G, Rs, Rs0).

And now the interpreter can be applied to itself. Here is an example of the interpreter, interpreting itself as it evaluates the example program:

%?- mi([mi([natnum(X)])]).
%@ X = 0 ;
%@ X = s(0) ;
%@ X = s(s(0)) ;
%@ etc.

Contrast this with the comparatively verbose meta-circular evaluators of other languages.

Difference lists are a very cool trick, no doubt. Can someone supply a historical reference for difference lists? (were they introduced in a paper?)

I haven't found any online source, but this seems to be the reference to the original Clark / Tärnlund paper:

L. Clark and S.-A. Tärnlund. A first order theory of data and programs.
In B. Gilchrist, editor, Proceedings of the IFIP Congress, pages 939–944, Toronto, Canada, 1977. North Holland.

The catch is that you cannot append to the same list twice, right?

The catch is that you cannot append to the same list twice, right?
With this representation, right.

Difference lists are known in FP, using lambda binders, so in scheme we have:

 (lambda (x) `(a b c d e . ,x))

which can be reused.

With higher-order unification, we can do this in LP too. In lambda-Prolog, Dale Miller has talked of "functional difference lists"; cf. section 11 of his Collection Analysis for Horn Clause Programs from 2006.

Other uses of append that we don't want to miss out on...
Is 3 a member of [1,2,3,4,5]?

append(_,[3|_],[1,2,3,4,5]).

Enumerate the members of [1,2,3,4,5]

append(_,[X|_],[1,2,3,4,5]).

...also since lists and unary numbers share the same structure, we can use append to perform arithmetic.

X = 2+3

append([1,1],[1,1,1],X).

X = 5-4

append(X,[1,1,1,1],[1,1,1,1,1]).

Find the pairs of numbers that add up to 4

append(X,Y,[1,1,1,1]).

While append in prolog is magical, it is more the uses of the predicate than the definition that are irresistible. Second, I'd prefer to use code that had significant impact on programming, programming culture etc.

I thought of quines. Heck, I love quines. But historically important?

Maybe I over spoke. It's more accurate to say the general concept of indirect self reference is important (huge) and quines are one example of it.

Or I could just say that computer viruses are historically significant so I'm covered there as well. :-)

If "quine" means "an automaton using its own source code as input", then Gödel used a quine, more or less, to prove his incompleteness theorem, Turing used one to prove that the halting problem was uncomputable, Thompson used one to show that access to the source code of all of your software and compilers is insufficient to find backdoors in it, Steve Russell approximately invented functional programming languages by encoding McCarthy's Lisp quine into (709?) assembly, John von Neumann predicted that the structure of self-reproducing life forms in general would turn out to be quines, and was proved right with the discovery of DNA.

So if quines are responsible for the existence of life, Gödel's incompleteness theorem, the proof of the uncomputability of the halting problem, and the existence of functional programming languages, I nominate them as the most historically important category of programs of all.

If we were to use a standard of rigour for which the possible overflow of (I+J)/2 is considered a bug, then I can hardly think of a paper that isn't buggy. Certainly in the field in which I work (3D graphics) almost every expression computed in almost every single paper I have seen would be considered buggy because it will cause overflow for some input.

In the process of taking an idea in a paper to production code a programmer ought to handle potential overflows. But I don't see that it is the job of the paper author to highlight the potential problems of every particular programming language in this case, especially when it might clutter an otherwise clear idea. As far as I can tell, it is standard procedure to consider an idealised machine when presenting academic work, unless the paper is specifically about non-idealised machines.

Of course my calibration may be off because the standards in graphics publications are considerably different from those in PLT.

The thing is simply that one of the benefits of formal methods is that you catch these "extreme" cases. In this case it could be an unreasonable criticism, but there are definitely cases where it is not. My impression is that most programmers would not even realize that there was this error case without having it pointed out and wouldn't immediately know how to rewrite it (though they could probably figure out a way quickly enough.) Combined with the fact that overflow errors cause real problems, the criticism is probably not unreasonable.

In this case, i + (j-i)/2 is one way to avoid overflow.

I think it can overflow if i and j are oppositive sign and both big.

positions in a list (i and j here) are natural numbers, not integers.
(can't be negative :) )

While (I+J)/2 is reasonable in math/research papers, 'Programming Pearls' is a book which is about teaching programming, so here it's not adequate IMHO: the author should have used the opportunity to introduce I + (J-I)/2 to avoid potential overflow (or use a Middle function to hide it during the main explanation and only at the end of show that Middle's correct implementation in C-like language is not the obvious formula).

Overflow isn't a bug if it gives the right answer, or even a right answer. If you're using saturating arithmetic, pixel value overflow may look just fine. But if you get a negative array index and it crashes your program, or just an incorrect unsigned array index, and it fails to find a key that was present in the array, then it's a bug.

Assembly is a good place to look for irresistible code, but can you point to a specific example worthy of inclusion in our list. Remember that it would be best if it comes from a specific system, and has historical value.

Two of my favorites are KarL/NoooN's 40 byte sinus generator and Pascal's 20 byte starfield. If you followed the demoscene back in the day these 2 guys should ring a bell.

In an assembly language, it is sometimes possible to express a certain computation unconditionally, although doing the same would seem to be impossible in most other languages. Such things are often both impressive and efficient. Here are several examples in the i8086 assembly language, from my personal collection, about 20 years old now. Most if not all are, I believe, well known idioms.

Decrement by 1 the content of ax if positive but keep it 0 if already so (∸, dot minus, monus, or floor subtraction of 1):

    sub  ax,1
    adc  ax,0

In addition, the following is true after the execution of the above:

• CF (the carry flag) is set iff ax was already 0;
• ZF (the zero flag) is set iff ax is 0 after.

Increment ax by 1 iff currently the content of ax is less than that of bx (increment ax preserving ax≤bx):

    cmp  ax,bx
    adc  ax,0

Absolute value of an integer in ax:

    cwd
    xor  ax,dx
    sub  ax,dx

Signum (-1, 0, or 1) of an integer in ax:

    cwd
    add  ax,-1
    mov  ax,dx
    adc  ax,dx

The following is perhaps the most impressive, as it makes use of a BCD-arithmetic command, DAA (Decimal Adjust after Addition), in a rather unanticipated way. Given a number 0÷15 in al, convert it to its ascii hex representation, i.e. {0,1,…,15} –> {'0','1',…,'F'} (note that while 0,1,…,15 is an (integer) sequence, '0','1',…,'F' is not an ascii sequence):

    add al,90h
    daa
    adc al,40h
    daa

I thought about Icon, but felt that the historical significance was probably not high enough. On second thought, perhaps the significance of backtracking and Icon’s role in the development of ideas about backtracking might make this example worthy of inclusion.
A few unique ways to express fib may also be a nice idea.

Indeed, Icon is of the very few languages with constructs for explicit backtracking.

Other genuinely Icon's contributions to programming are its generators and co-expressions. A generator is an expression which – in a suitable context – produces a (possibly infinite) sequence of values rather than just one. A co-expression is (a form of) a lazy expression, and is particularly useful when that expression is a generator.

The Fibonacci generator from above can be turned into a co-expression, and then any number of calls of this co-expression can be made, themselves being generators if necessary. (The following program makes three such calls.)

procedure main()
  fib := create (i:=j:=1) | |((i+:=j):=:j)
  every  write(|@fib) \20
  write()
  write(@fib)
  write()
  every  write(|@fib) \10
end

In the realm of functional programming, I believe Strachey's 1966 Cartesian product function in CPL:

let CProd[L] = Lit[f,List1[NIL],L]
  where f[k,z] = Lit[g,NIL,k]
    where g[x,y] = Lit[h,y,z]
      where h[p,q] = Cons[Cons[x,p],q]

should be considered classic, and is irresistably elegant. Lit is what in ML, Haskell, etc. is called foldr, so in Haskell the same function is:

cprod = foldr f [[]]  where
  f as zss = foldr g [] as  where
    g a yss = foldr h yss zss  where
      h zs xss = (a:zs):xss

Perhaps this is the earliest example of higher-order programming using a ‘fold’. Or am I mistaken?

The standard reference on this sort of thing is an amazing book called Hacker's Delight, by Henry S. Warren Jr. of IBM, who also wrote an important early theoretical paper on this topic (Functions realizable with word-parallel logical and two's-complement addition instructions, Comm. ACM 20(6):439-441, June 1977.)

I totally forgot about this. And how could we fail to mention HAKMEM?!

To get the bonus points for cryptic glyphs, I propose the following program fragment in Oz that implements a contract net protocol in three lines:

PRs={Map Providers fun {$ P} P#{Send P query(price $)} end}
Pb#Rb={FoldL PRs.2 fun {$ Pb#Rb P#R} if Rb>R then P#R else Pb#Rb end end PRs.1}
for P#R in PRs do {Send P if P==Pb then ok else no end} end

The full program is explained here. This program also combines asynchronous communication with dataflow synchronization and uses functional combinators as concurrency patterns.

I was looking for that! Thanks.

I also found the source for an early version of J.

And another couple of Forth possibilities:
Colorforth IDE driver
FSMs in Forth (you essentially 'draw' the table)