ChessLisp for everyone!

[Tord Romstad]

ChessLisp, unlike just about all older Lisps, is case specific throughout.

Pedantic remark:

Common Lisp is case-sensitive, too. It just happens that the reader with the default readtable settings converts all symbols read to uppercase. If you just do

Code: Select all

(setf (readtable-case *readtable*) :preserve)

you get case-sensitivity.

You already knew this, of course, but perhaps some other readers didn't.

[Tord Romstad]

Also, I haven't found any Lisp that has support for native 64 bit integers.

I know that SBCL has, and I think many others have, too. In order to get native 64-bit arithmetic, just wrap all arithmetic expressions in a LOGAND with #xFFFFFFFFFFFFFFFF. A sufficiently smart compiler will realize that all the computations inside the LOGAND form can be optimized to native 64-bit arithmetic.

Having to type "(logand <whatever> #xFFFFFFFFFFFFFFFF)" everywhere quickly becomes tedious, but with a little work you should be able to write a WITH-64BIT-ARITHMETIC macro that walks through the code and inserts logand where required.

[sje]

ChessLisp design notes: monadic predicates

A Lisp monadic predicate is a function that takes a single operand and deterministically returns either the symbol t (predicate satisfied) or the symbol nil (predicate not satisfied).

Due to historical kludge accumulation, the monadic predicate names in Common Lisp are not entirely consistent; the names in Scheme are better. In ChessLisp, the Common Lisp functionality is retained, but with Scheme-like names.

Monadic predicates coded and tested (so far; this is actual dispatch source):

Code: Select all

    /* atom?         */ case sysfuncAtomQ:        EvalSysFuncAtomQ();        break;
    /* character?    */ case sysfuncCharacterQ:   EvalSysFuncCharacterQ();   break;
    /* cons?         */ case sysfuncConsQ:        EvalSysFuncConsQ();        break;
    /* eof?          */ case sysfuncEofQ:         EvalSysFuncEofQ();         break;
    /* eq?           */ case sysfuncEqQ:          EvalSysFuncEqQ();          break;
    /* eql?          */ case sysfuncEqlQ:         EvalSysFuncEqlQ();         break;
    /* even?         */ case sysfuncEvenQ:        EvalSysFuncEvenQ();        break;
    /* float?        */ case sysfuncFloatQ:       EvalSysFuncFloatQ();       break;
    /* integer?      */ case sysfuncIntegerQ:     EvalSysFuncIntegerQ();     break;
    /* list?         */ case sysfuncListQ:        EvalSysFuncListQ();        break;
    /* literal?      */ case sysfuncLiteralQ:     EvalSysFuncLiteralQ();     break;
    /* nonnegative?  */ case sysfuncNonnegativeQ: EvalSysFuncNonnegativeQ(); break;
    /* nonpositive?  */ case sysfuncNonpositiveQ: EvalSysFuncNonpositiveQ(); break;
    /* nonzero?      */ case sysfuncNonzeroQ:     EvalSysFuncNonzeroQ();     break;
    /* null?         */ case sysfuncNullQ:        EvalSysFuncNullQ();        break;
    /* number?       */ case sysfuncNumberQ:      EvalSysFuncNumberQ();      break;
    /* odd?          */ case sysfuncOddQ:         EvalSysFuncOddQ();         break;
    /* one?          */ case sysfuncOneQ:         EvalSysFuncOneQ();         break;
    /* positive?     */ case sysfuncPositiveQ:    EvalSysFuncPositiveQ();    break;
    /* string?       */ case sysfuncStringQ:      EvalSysFuncStringQ();      break;
    /* symbol?       */ case sysfuncSymbolQ:      EvalSysFuncSymbolQ();      break;
    /* vector?       */ case sysfuncVectorQ:      EvalSysFuncVectorQ();      break;
    /* zero?         */ case sysfuncZeroQ:        EvalSysFuncZeroQ();        break;

Note: Not all run time error checking has been implemented -- yet.

[sje]

ChessLisp design notes: old style basic list accessors

A Lisp old style basic list accessor is a function that takes a single operand (a list) and returns the indicated component of the list. There are thirty of these defined in Common Lisp, and ChessLisp implements the whole set for compatibility purposes.

The car (contents of address register) and cdr (contents of data register) functions are from the first version of Lisp (i.e., Lisp 1.0 or Year Zero Lisp or Lisp 1958). Better are the more recent, Common Lisp equivalents first and rest.

Likewise, cadr == second, caddr = third, cadddr = fourth.

ChessLisp observes the Common Lisp semantics of the basement cases (car nil) == nil and (cdr nil) == nil.

Old style basic list accessors coded and tested (this is actual dispatch source):

Code: Select all

    /* caaaar        */ case sysfuncCaaaar:       EvalSysFuncCaaaar();       break;
    /* caaadr        */ case sysfuncCaaadr:       EvalSysFuncCaaadr();       break;
    /* caaar         */ case sysfuncCaaar:        EvalSysFuncCaaar();        break;
    /* caadar        */ case sysfuncCaadar:       EvalSysFuncCaadar();       break;
    /* caaddr        */ case sysfuncCaaddr:       EvalSysFuncCaaddr();       break;
    /* caadr         */ case sysfuncCaadr:        EvalSysFuncCaadr();        break;
    /* caar          */ case sysfuncCaar:         EvalSysFuncCaar();         break;
    /* cadaar        */ case sysfuncCadaar:       EvalSysFuncCadaar();       break;
    /* cadadr        */ case sysfuncCadadr:       EvalSysFuncCadadr();       break;
    /* cadar         */ case sysfuncCadar:        EvalSysFuncCadar();        break;
    /* caddar        */ case sysfuncCaddar:       EvalSysFuncCaddar();       break;
    /* cadddr        */ case sysfuncCadddr:       EvalSysFuncCadddr();       break;
    /* caddr         */ case sysfuncCaddr:        EvalSysFuncCaddr();        break;
    /* cadr          */ case sysfuncCadr:         EvalSysFuncCadr();         break;
    /* car           */ case sysfuncCar:          EvalSysFuncCar();          break;
    /* cdaaar        */ case sysfuncCdaaar:       EvalSysFuncCdaaar();       break;
    /* cdaadr        */ case sysfuncCdaadr:       EvalSysFuncCdaadr();       break;
    /* cdaar         */ case sysfuncCdaar:        EvalSysFuncCdaar();        break;
    /* cdadar        */ case sysfuncCdadar:       EvalSysFuncCdadar();       break;
    /* cdaddr        */ case sysfuncCdaddr:       EvalSysFuncCdaddr();       break;
    /* cdadr         */ case sysfuncCdadr:        EvalSysFuncCdadr();        break;
    /* cdar          */ case sysfuncCdar:         EvalSysFuncCdar();         break;
    /* cddaar        */ case sysfuncCddaar:       EvalSysFuncCddaar();       break;
    /* cddadr        */ case sysfuncCddadr:       EvalSysFuncCddadr();       break;
    /* cddar         */ case sysfuncCddar:        EvalSysFuncCddar();        break;
    /* cdddar        */ case sysfuncCdddar:       EvalSysFuncCdddar();       break;
    /* cddddr        */ case sysfuncCddddr:       EvalSysFuncCddddr();       break;
    /* cdddr         */ case sysfuncCdddr:        EvalSysFuncCdddr();        break;
    /* cddr          */ case sysfuncCddr:         EvalSysFuncCddr();         break;
    /* cdr           */ case sysfuncCdr:          EvalSysFuncCdr();          break;

Note: Not all run time error checking has been implemented -- yet.

[Dan Andersson]

Not considering Scheme a Lisp? I guess it would certainly be possible if one purposefully ignored mostly everything about the languages

MvH Dan Andersson

[sje]

A Lisp relational function returns t (or nil) if the specified relation is satisfied (or not) for its operands.

ChessLisp includes a full set of relational functions:

Relationals coded and tested (this is actual dispatch source):

Code: Select all

    // System function evaluation routines (file: ChessLispSysFunc02.cpp)

    /* /=            */ case sysfuncRelNE:        EvalSysFuncRelNE();        break;
    /* <             */ case sysfuncRelLT&#58;        EvalSysFuncRelLT&#40;);        break;
    /* <=            */ case sysfuncRelLE&#58;        EvalSysFuncRelLE&#40;);        break;
    /* =             */ case sysfuncRelEQ&#58;        EvalSysFuncRelEQ&#40;);        break;
    /* >             */ case sysfuncRelGT&#58;        EvalSysFuncRelGT&#40;);        break;
    /* >=            */ case sysfuncRelGE&#58;        EvalSysFuncRelGE&#40;);        break;

    // System function evaluation routines &#40;file&#58; ChessLispSysFunc04.cpp&#41;

    /* char/=         */ case sysfuncCharRelNE&#58;   EvalSysFuncCharRelNE&#40;);    break;
    /* char<          */ case sysfuncCharRelLT&#58;   EvalSysFuncCharRelLT&#40;);    break;
    /* char<=         */ case sysfuncCharRelLE&#58;   EvalSysFuncCharRelLE&#40;);    break;
    /* char=          */ case sysfuncCharRelEQ&#58;   EvalSysFuncCharRelEQ&#40;);    break;
    /* char>          */ case sysfuncCharRelGT&#58;   EvalSysFuncCharRelGT&#40;);    break;
    /* char>=         */ case sysfuncCharRelGE&#58;   EvalSysFuncCharRelGE&#40;);    break;

    // System function evaluation routines &#40;file&#58; ChessLispSysFunc05.cpp&#41;

    /* str/=          */ case sysfuncStrRelNE&#58;    EvalSysFuncStrRelNE&#40;);     break;
    /* str<           */ case sysfuncStrRelLT&#58;    EvalSysFuncStrRelLT&#40;);     break;
    /* str<=          */ case sysfuncStrRelLE&#58;    EvalSysFuncStrRelLE&#40;);     break;
    /* str=           */ case sysfuncStrRelEQ&#58;    EvalSysFuncStrRelEQ&#40;);     break;
    /* str>           */ case sysfuncStrRelGT&#58;    EvalSysFuncStrRelGT&#40;);     break;
    /* str>=          */ case sysfuncStrRelGE&#58;    EvalSysFuncStrRelGE&#40;);     break;

Note: Not all run time error checking has been implemented -- yet.

[sje]

ChessLisp has a full set of bit functions; these work with natively supported 64 bit integers and allow fast bitboard operations. I guarantee that these are much faster than the equivalent Common Lisp hacks (e.g., logand, sbit, etc.).

Bit functions coded and tested (this is actual dispatch source):

Code: Select all

    /* bf-and        */ case sysfuncBfAnd:        EvalSysFuncBfAnd();        break;
    /* bf-andnot     */ case sysfuncBfAndnot:     EvalSysFuncBfAndnot();     break;
    /* bf-contract   */ case sysfuncBfContract:   EvalSysFuncBfContract();   break;
    /* bf-count      */ case sysfuncBfCount:      EvalSysFuncBfCount();      break;
    /* bf-empty?     */ case sysfuncBfEmptyQ:     EvalSysFuncBfEmptyQ();     break;
    /* bf-eql?       */ case sysfuncBfEqlQ:       EvalSysFuncBfEqlQ();       break;
    /* bf-expand     */ case sysfuncBfExpand:     EvalSysFuncBfExpand();     break;
    /* bf-first      */ case sysfuncBfFirst:      EvalSysFuncBfFirst();      break;
    /* bf-last       */ case sysfuncBfLast:       EvalSysFuncBfLast();       break;
    /* bf-not        */ case sysfuncBfNot:        EvalSysFuncBfNot();        break;
    /* bf-notempty?  */ case sysfuncBfNotemptyQ:  EvalSysFuncBfNotemptyQ();  break;
    /* bf-or         */ case sysfuncBfOr:         EvalSysFuncBfOr();         break;
    /* bf-reset      */ case sysfuncBfReset:      EvalSysFuncBfReset();      break;
    /* bf-reset?     */ case sysfuncBfResetQ:     EvalSysFuncBfResetQ();     break;
    /* bf-set        */ case sysfuncBfSet:        EvalSysFuncBfSet();        break;
    /* bf-set?       */ case sysfuncBfSetQ:       EvalSysFuncBfSetQ();       break;
    /* bf-toggle     */ case sysfuncBfToggle:     EvalSysFuncBfToggle();     break;
    /* bf-xor        */ case sysfuncBfXor:        EvalSysFuncBfXor();        break;

Note: Not all run time error checking has been implemented -- yet.

[sje]

On Common Lisp readtables:

If the Common Lisp language specification had been done right in the fist place, there would be no need for user massaging of readtables. Case insensitivity is a dinosaur and should have been retired long ago, about the same time that most ASR-33 Teletypes wound up in the junk heap.

Note the high correlation between case insensitivity and the deadness of a programming language (e.g., Fortran, Pascal, and Ada).

BUT IF SOMEONE WANTS TO CODE AND GET OUTPUT IN UPPERCASE, THAT'S OKAY. Well, as long as I don't have to look at it.


On 64 bit native support:

Unless things have changed, I know that cmucl, gcl, and clisp (among others) have very inefficient handing of 64 bit integer values. They have taken the general approach to handle everything adequately and so handle nothing excellently.


On Scheme:

I consider Scheme to be a Lisp. It is certainly a descendant of Lisp (mostly from MacLisp). But it's not my first choice for just about anything.

[sje]

This is the first ever benchmark. It's ChessLisp vs GNU Common Lisp (a.k.a., gcl).

Platform: 3 GHz P4 Ubuntu Linux

Test function:

(defun fib (n) (cond ((= n 0) 1) ((= n 1) 1) (t (+ (fib (- n 1)) (fib (- n 2))))))

Function call and result:

(fib 40) => 165580141

ChessLisp: 573 sec => 288971 Hz
gcl: 368 sec => 449946 Hz

So ChessLisp is running at about 2/3 the speed of gcl. Not too bad for the very first test; I'm glad just to get the correct answers.

After the chess run time is connected, I expect ChessLisp to beat gcl by at least a factor of ten on domain specific tests.

If you are running Ubuntu, you can use the Synaptic package manager to download and install gcl. On any Debian Linux, the corresponding apt-get call does the same thing. Eventually, ChessLisp will also be available by the same mechanisms.

[sje]

I added a few lines of code to the top level bindings list scanner to have the list reorganize on each successful probe. When a binding is located, it's moved to the front of the list. The superstition is that recently located bindings will be frequently probed bindings.

Old ChessLisp: 573 sec => 288971 Hz
New ChessLisp: 465 sec => 356085 Hz

Yes, it's low hanging fruit.

I'll take a guess and suggest that gcl likely uses a hash table. I might do the same in ChessLisp at a later date.