===============[ Equality in LISP ]================ Equality in LISP can be tested at the level of references (are these two references pointing to the exact same object?), internals of non-recursive objects like BIGNUMs, and the structure of recursive objects like lists and strings, where the entire pair of objects need to be traversed to get the answer. These are EQ, EQL, and EQUAL functions respectively. There is also EQUALP, which ignores case when comparing strings. Some of this may seem baroque and confusing, but there it answers to two fundamental truths: (1) In a language with references, one must be able to compare references directly. (2) Defining equality of recursively constructed objects is hard. You may find the following summary useful: https://lisp-journey.gitlab.io/blog/common-lisp-equality-predicates/ sergey@snowball lisp % gcl GCL (GNU Common Lisp) 2.6.14 Fri Jan 13 10:47:56 AM EST 2023 ANSI git: Version_2_6_14 ...skipped... Use (help) to get some basic information on how to use GCL. // EQ: are these two arguments bound to the same object? >(eq t t) T >(eq t nil) NIL >(eq (quote x) (quote x)) // both arguments are the "x" symbol T // EQ seems to compare FIXNUM integers, but not BIGNUMs. BIGNUMs are treated as separate objects >(eq 1 1) // <<--- this is not guaranteed, but it seems to work for FIXNUMs T >(eq 100 100) T >(eq 10000000 10000000) T >(eq 100000000000000000000 100000000000000000000) // ...but not BIGNUMs NIL >(TYPE-OF 10000000) FIXNUM >(TYPE-OF 100000000000000000000) BIGNUM >(eq x x) // oops, "x" has no value bound to it Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by EVAL. Condition in EVAL [or a callee]: INTERNAL-SIMPLE-UNBOUND-VARIABLE: Cell error on X: Unbound variable: Broken at EQ. Type :H for Help. 1 Return to top level. >> >(setq x 100000000000000000000) 100000000000000000000 >(type-of x) BIGNUM >x 100000000000000000000 >(eq x x) // both arguments evaluate to the same BIGNUM object T >(eq 100000000000000000000 100000000000000000000) // these BIGNUMs are created by READ // as two different objects. NIL >(setq bn1 100000000000000000000) 100000000000000000000 >(setq bn2 100000000000000000000) 100000000000000000000 >(eq bn1 bn2) NIL >(eq "foo" "foo") // these strings are two different objects, same as BIGNUMs above /// EQL works with numbers but not strings: >(eql 1000 1000) T >(eql 100000000000000000000 100000000000000000000) T >(eql "foo" "foo") NIL >(eql '(1 2) '(1 2)) // ..and not lists either. These lists use different cons cells // even though the CARs of these cons cells may point to the same 1 and 2 NIL // EQUAL compares recursively: >(equal '(1 2) '(1 2)) T >(equal "foo" "foo") T // GCL has handy built-in documentation: >(help 'eq) ----------------------------------------------------------------------------- EQ [Function] From ((EQ . Iteration and Tests) gcl-si.info): -- Function: EQ (x y) Package:LISP Returns T if X and Y are the same identical object; NIL otherwise. ...skipped.. ---- but look at the examples of what is and is not guaranteed ...In particular: (eq 'a 'a) => true (eq 3 3) /// <<--- Note that (eq 3 3) is not guaranteed! => true OR=> false (eq 3.0 3.0) /// floats aren't doing any better => true OR=> false (let ((x 5)) (eq x x)) => true OR=> false // <<<---- I don't fully understand this. As per text below, LISP can // presumably make a copy of the 5 between when the first argument // x and a second argument x are evaluated, so eq will get two // different copies of 5. Or perhaps they simply // mean that nothing at all can be guaranteed about equality // of objects that are numbers or strings or floats, so (eq x x) // in this example is as chancy as (eq 5 5). See Also:: .......... *note eql:: , *note equal:: , *note equalp:: , *note =:: , *note Compilation:: Notes:: ....... Objects that appear the same when printed are not necessarily eq to each other. Symbols that print the same usually are eq to each other because of the use of the intern function. However, numbers with the same value need not be eq, and two similar lists are usually not identical. An implementation is permitted to make "copies" of characters and numbers at any time. The effect is that Common Lisp makes no guarantee that eq is true even when both its arguments are "the same thing" if that thing is a character or number. ----------------------------------------------------------------------------- /////// ---- NOTE that this definition of EQUAL is itself recursive! >(help 'equal) ----------------------------------------------------------------------------- EQUAL [Function] From ((EQUAL . Iteration and Tests) gcl-si.info): -- Function: EQUAL (x y) Package:LISP Returns T if X and Y are EQL or if they are of the same type and corresponding components are EQUAL. Returns NIL otherwise. Strings and bit-vectors are EQUAL if they are the same length and have identical components. Other arrays must be EQ to be EQUAL. ...skipped... Object equality is not a concept for which there is a uniquely // <<<<----- NOTE THIS! determined correct algorithm. The appropriateness of an equality predicate can be judged only in the context of the needs of some particular program. Although these functions take any type of argument and their names sound very generic, equal and equalp are not appropriate for every application. A rough rule of thumb is that two objects are equal if and only if their printed representations are the same. ----------------------------------------------------------------------------- >(equal bn1 bn2) T >(eql bn1 bn2) T >(eq bn1 bn2) NIL >(help 'eql) ----------------------------------------------------------------------------- EQL [Function] ----------------------------------------------------------------------------- EQL [Type] Defined as: (DEFTYPE EQL (PCL::TYPE-OBJECT) (LIST 'MEMBER PCL::TYPE-OBJECT)) See the doc of DEFTYPE. From ((EQL . Numbers) gcl-si.info): -- Function: EQL (x y) Package:LISP Returns T if X and Y are EQ, or if they are numbers of the same type with the same value, or if they are character objects that represent the same character. Returns NIL otherwise. ...skipped... ---- but read the examples!! The value of eql is true of two objects, x and y, in the folowing cases: 1. If x and y are eq. 2. If x and y are both numbers of the same type and the same value. 3. If they are both characters that represent the same character. Otherwise the value of eql is false. ...skipped... ==============[ Let's write recursive functions that use these ]============= // There is a standard function called MEMBER: >(help 'member) ----------------------------------------------------------------------------- MEMBER [Function] From ((MEMBER . Lists) gcl-si.info): -- Function: MEMBER (item list &key (test #'eql) test-not (key #'identity)) Package:LISP Returns the tail of LIST beginning with the first ITEM. ----------------------------------------------------------------------------- >(member 1 '(5 4 3 2 1 0)) (1 0) >(member 10 '(5 4 3 2 1 0)) NIL >(member 1 '(5 4 3 2 1 0)) (1 0) >(member 1 '(5 4 3 2 1 0 1 )) (1 0 1) ////// We'll write our own. We'll call is MEMBR (nothing is bound to this name). >membr Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by EVAL. Condition in EVAL [or a callee]: INTERNAL-SIMPLE-UNBOUND-VARIABLE: Cell error on MEMBR: Unbound variable: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 Top level. >#'membr Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by FUNCTION. Condition in FUNCTION [or a callee]: INTERNAL-SIMPLE-UNDEFINED-FUNCTION: Cell error on MEMBR: Undefined function: Broken at FUNCTION. Type :H for Help. 1 Return to top level. >>1 Top level. >(BOUNDP 'membr) NIL >(fBOUNDP 'membr) /// <--- notice that I accidentally typed "fBOUNDP". It got treated the same. NIL //// Instead of IF we are going to use a different special form, COND: >(help 'cond) ...skipped... //////////// At this point I switched to Emacs in lisp-interaction-mode, because //////////// Emacs automatically counts parentheses and indents S-expressions. (defun membr (x xs) (cond ((null xs) nil) // <--- note that the COND basically writes itself: ((consp xs) (if (equal x (car xs)) // xs is either nil or a cons cell xs // if the CAR matches, return the cons/list (membr x (cdr xs)))) // otherwise proceed down the list (t (error "not a list")))) membr (membr "foo" '(1 2 3 5 "foo")) ("foo") (membr nil '(nil)) ;; stands to reason, nil is a member of a single-cell list that ;; contains a nil in its CAR (nil) (cons nil nil) ;; in case you are wondering what '(nil) is (nil) //// Trees are also recursive data structures, just as lists are. The only difference //// is that the CAR of a list is an atom, whereas CARs in trees can be cons cells. (defun sumtree (xs) ;; assume xs is a tree with integers as leaves (cond ((null xs) 0) ;; base case ((consp xs) (+ (sumtree (car xs)) ;; recursive case: the sum of the tree is the sum (sumtree (cdr xs)))) ;; of the subtrees under its CAR and CDR ((atom xs) xs))) ;; and the leaf (hopefully an integer) is its own sum:) sumtree (sumtree nil) 0 (sumtree '(1 2 3 4)) 10 (sumtree '(((((((((1 (2) (((3 ))))))))))))) 6 (setq t1 '(((((((((1 (2) (((3 ))))))))))))) ((((...)))) (setq t2 '(((((((((1 ("foo") (((3 ))))))))))))) ((((...)))) (sumtree t2) ;; the error reveals the function call stack in Emacs' debugger. Examine it! ///// I use the function draw-tree.el to show the cons cells of trees: ///// https://github.com/pietroiusti/draw-tree/ ///// https://github.com/pietroiusti/draw-tree/blob/main/draw-tree.el (load "~/cs59/draw-tree.el") t (draw-tree '(a b c d)) " [o|o]---[o|o]---[o|o]---[o|/] | | | | a b c d " (draw-tree '((a b) (c d))) " [o|o]---[o|/] | | | [o|o]---[o|/] | | | | c d | [o|o]---[o|/] | | a b " (draw-tree t1) " [o|/] | [o|/] | [o|/] | [o|/] | [o|/] | [o|/] | [o|/] | [o|/] | [o|o]---[o|o]---[o|/] | | | 1 [o|/] [o|/] | | 2 [o|/] | [o|/] | 3 " /// For more examples, see https://cosc59.gitlab.io/lisp/lisp-tree-recusion-log.txt ===================[ Tail Recursion ]=================== // Note that the recursive call to membr is a _tail call_: there is nothing that needs to be saved // from the stack frame of the current invocation, so the stack frame can, in principle, be // eliminated. More on this later. /// There are tricks for making functions tail-recursive and thus less demanding on the memory. /// They are discussed in the OnLisp book, pages 48--49. Read that chapter if you haven't yet! (defun fact (n) (cond ((eql n 0) 1) (t (* n (fact (- n 1)))))) ;; not tail-recursive: after self-call returns, (* n ..) must happen fact /// This works for numbers up to 500. At 550 it fails due to exceeding Emacs' call stack depth: (fact 500) 122013682599111006870123878542304692625357434280319284219241358838584537315388199760\ 54964475022032818.....000000 (fact 550) Debugger entered--Lisp error: (excessive-lisp-nesting 1601) (cond ((eql n 0) 1) (t (* n (fact (- n 1))))) fact(20) (* n (fact (- n 1))) (cond ((eql n 0) 1) (t (* n (fact (- n 1))))) fact(21) ...skipped... /// From the debugger stack trace we can figure out that 529 is the largest that fits: (fact 529) 533526216060012988756025127348557303528841881219005404343449448568436062992673648778\ 23815647824928827692...000000000 //// To avoid the need for storing the "n" we can push the last multiplication by n into //// the second argument of the function: (defun fact1 (n acc) (cond ((eql n 0) acc) (t (fact1 (- n 1) (* n acc))))) fact1 (fact1 750 1) 258080348888515099592332164484462756339873138465439573430307783197416299243027155954\ 177662782377988121786330241704205895696...00000000000 ;;;; However, it fails at 800: (fact1 800 1) Debugger entered--Lisp error: (excessive-lisp-nesting 1601) (cond ((eql n 0) acc) (t (fact1 (- n 1) (* n acc)))) fact1(5 64254417611282167012053283147919030049629700151334186596950916169497570985$ (cond ((eql n 0) acc) (t (fact1 (- n 1) (* n acc)))) fact1(6 10709069601880361168675547191319838341604950025222364432825152694916261830$ (cond ((eql n 0) acc) (t (fact1 (- n 1) (* n acc)))) //// From the debugger stack trace we can figure out the last n for which it succeeds: (fact1 794 1) 29971333221090040829395683....0000 //// So Emacs LISP doesn't do the proper job of stack frame elimination for tail calls. /// However, the Steel Bank Common Lisp (SBCL) does: sergey@snowball lisp % rlwrap sbcl This is SBCL 2.5.3, an implementation of ANSI Common Lisp. More information about SBCL is available at . SBCL is free software, provided as is, with absolutely no warranty. It is mostly in the public domain; some portions are provided under BSD-style licenses. See the CREDITS and COPYING files in the distribution for more information. * (defun fact1 (n acc) (cond ((eql n 0) acc) (t (fact1 (- n 1) (* n acc))))) FACT1 * (fact1 800 1) 7710530113353860041446393977750283605955564018160102391634109940339708518270930693670907697955390330926478... * (fact1 8000 1) 5184181060480876939805819797427726985651100531936841770672361154595429475316606187556643544762678482157216...0000 * (fact1 30000 1) 275953724621938459937994216642546278398076204452933098552963503680007586885036056583297297765120425434165...0000 * (fact1 100000 1) 28242294079603478742934215780245355184774949260912248505789180865429779509010630178725517714138311636107136117373619629514749961831239180227260734090938324220055569688667840380377379444961268380147875111966906386...0000 /// and it just keeps on going :) We'll find out where it stops and why this coming Tuesday