#723 implementation of built-in assoc funtion is wrong

[Alfgaar]

The clisp implementation of the function 'assoc' is wrong. Here is the definition from the paper 'Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I' by John McCarthy,

1. assoc [x;y]. If y is a list of the form ((u1, v1), · · · , (un, vn)) and x is one
   of the u’s, then assoc [x; y] is the corresponding v. We have
   assoc[x; y] = eq[caar[y]; x] ! cadar[y]; T ! assoc[x; cdr[y]]]

An example is

assoc[X; ((W, (A,B)), (X, (C,D)), (Y, (E, F)))] = (C,D).

clisp would produce the result (X, (C, D)), intead of (C, D).

using a more plain list

let lst = ((a 1) (b 2)(c 3))
let e = a
assoc ( a lst) = 1, as defined by McCarthy

assoc (a lst) = (a b), as implemented by clisp.

[Alfgaar]

Oops...sorry, where it reads a in assoc (a lst) replace it by e.
the last line should read assoc (e lst) = (a 1).

[Sam Steingold]

CLISP implements the ANSI CL standard, not the original paper.
Please see http://clhs.lisp.se/Body/f_assocc.htm

[Jörg Höhle]

I can't remember any LISP (even predating Common Lisp) where assoc was implemented as the paper describes. In papers, one often ignores \bottom and that some functions are partial. At the implementation level, one wants to distinguish the case "not found" -> NIL from the case "found key, value NIL". For decades, the obvious solution has been for ASSOC to return the CONS whose CAR is the found key.
Decades later (i.e. in Java times), people would devise the API to signal an error when the key is not found. Nowadays, given the return of functional programming and other considerations, we prefer tagged variants over the burden of error handling; the NIL/CONS dichotomy fits nicely.