;;; This is the saved buffer *scratch* where typing a LISP expression and then
;;;  pressing Ctrl+j evaluates this expression and prints the result right after it.
;;;  In Emacs terms, the result is "insert"-ed into the "buffer" at "the point", i.e.,
;;;  pasted in at the cursor's position. 

;; Simple arithmetic in Lisp syntax
(+ 1 2)
3

;; 5+3*2-6
(- (+ (* 3 2)
      5)
   6)
5

;; "read" parses the string syntax representing a list into an actual list
(read "(+ 3 5)")
(+ 3 5)

;; eval then evaluates the result, recursively if needed
(eval (read "(+ 3 5)"))
8

;; strings can span multiple lines
(eval (read "(- (+ (* 3 2)
      5)
   6)"))
5

;; In classic Lisp, symbols have separate values and function-values. The latter is
;;  accessed as #'

+
;; Debugger entered--Lisp error: (void-variable +) --- SB: press C-x k to kill the buffer with the error backtrace

#'+
+

;; This is the same as #'  . Function is a _special form_, that is, does not evaluate its argument(s)
(function +)
+

;; eq is true when two expressions reference the same object in Lisp's world 
(eq #'+ (function +))
t

(funcall + 1 2)
;; Debugger entered--Lisp error: (void-variable +). + is evaluated but has no value bound to it

;; funcall knows to use the function-value, not the symbol-value
(funcall '+ 1 2)
3

;; same thing
(funcall #'+ 1 2)
3

;; same thing
(funcall (function +) 1 2)
3

;; apply needs the arguments as a list
(apply #'+ '(1 2 2 4))
9

;;; Now for some elementary list operations
(car (cdr '(+ 1 2)))
1

(caddr '(+ 1 2))
2

(cons 1 (cons 2 nil))
(1 2)

(eval (cons #'+ (cons 1 (cons 2 nil))))
3

;; the above is the same as 
(eval '(+ 1 2))
3

;; we can set the values of symbols
(set (quote x) 100)
100

;; this is the idiomatic way of doing it
(setq x 200)
200

x
200

(+ x 1)
201

;; 1+ is a pure function of one argument: 
(1+ x)
201

;; Note that the value ("binding") of x is still unchanged 
x
200

;; BTW, + can take many arguments. We'll see how this is implemented later.
(+ 1 1 2 3 4 6 7)
24

;; How many cdd{}r are pre-defined?

(cdddr '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18))
(4 5 6 7 8 9 10 11 12 13 14 15 ...)

(cddddr '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18))
(5 6 7 8 9 10 11 12 13 14 15 16 ...)

(cdddddr '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18))
;; Debugger entered--Lisp error: (void-function cdddddr)

;;; OK then :)

;; From draw-tree.el is from https://github.com/pietroiusti/draw-tree
(load "~/cs59/draw-tree.el")
t

(draw-tree '(1 2 3))
"
[o|o]---[o|o]---[o|/]
 |       |       |      
 1       2       3      
"

(draw-tree (cdr '(1 2 3)))
"
[o|o]---[o|/]
 |       |      
 2       3      
"

;;; I created a buffer with a file called buff3.txt and pasted the results there:
(with-current-buffer "buff3.txt"
  (insert (draw-tree (cdr '(1 2 3)))))
nil

(with-current-buffer "buff3.txt"
  (point))
50

(with-current-buffer "buff3.txt"
  (insert "foo"))
nil

(setq b (get-buffer "buff3.txt"))
#<buffer buff3.txt>

(type-of b)
buffer
(list-buffers)
#<window 24 on *Buffer List*>

(buffer-list)
(#<buffer *scratch*> #<buffer  *Minibuf-1*> #<buffer buff3.txt> #<buffer *GNU Emacs*> #<buffer  *Minibuf-0*> #<buffer *Messages*> #<buffer  *code-conversion-work*> #<buffer  *Echo Area 0*> #<buffer  *Echo Area 1*> #<buffer  *eldoc*> #<buffer *Backtrace*> #<buffer *Completions*>)

(with-current-buffer b
  (insert (draw-tree '(+ (* 2 3 foo) bar (baz quux)))))
nil

;;; IF in Lisp _always_ has a value! It is a special form, in that only either its "then" or "else" part is evaluated, but the value of IF is that of either the "then" or the "else" expression.
(if (< 1 2) "foo" "bar")
"foo"

(if (> 1 2) "foo" "bar")
"bar"

;; Now we can define some recursive functions that destructure the argument (a list) into
;;  its natural subtypes: either an empty list or a cons cell 
(defun mysum (xs)
  "Sum a list of numbers, recursively"
  (if (null xs) 0
    (+ (car xs) (mysum (cdr xs)))))
mysum

(mysum '(2 3 10))
15

;; another way that is even more explicit about the expected structure of xs
(defun mysum-cond (xs)
  (cond ((null xs) 0)
	((consp xs) (+ (car xs) (mysum-cond (cdr xs))))
	(t (error "Can't sum that"))))
mysum-cond


(mysum-cond '(1 2 3))
6

(mysum 2)
;; results in my custom error

;;; An interlude on equality: EQ vs EQL vs EQUAL
x
200

(eq x x)
t

;; this might not be the same for larger integers, because they need not resolve
;;  to the same object when their representation is constructed by (read)
(eq x 200)
t

;; ok then...
(eq 30000000 30000000)
t

;; aha!
(eq 3000000000000000000 3000000000000000000)
nil

;; but these bignums are eql  
(eql 3000000000000000000 3000000000000000000)
t

;; and of course also equal
(equal 3000000000000000000 3000000000000000000)
t


;; two strings are not eq 
(eq "foo" "foo")
nil

;; and not even eql 
(eql "foo" "foo")
nil

;; but they are equal (recursively compared by value)
(equal "foo" "foo")
t

;; two lists separately constructed by (read) are not eq
(eq '(1 2) '(1 2))
nil

;; nor eql
(eql '(1 2) '(1 2)) 
nil

;; but they are (recursively) equal
(equal '(1 2 (3)) '(1 2 (3)))
t

;;; Let's do some recursion/destructuring driven programming with lists 
(defun mylen (xs)
  "Length of a list. Argument must be a cons cell or nil"
  (cond ((null xs) 0)
	((consp xs) (+ 1 (mylen (cdr xs))))
	((atom xs) -1)
	(t (error "I have no idea what this is, no length for you")))) ; never reached!
mylen

(mylen nil)
0

(mylen '(1 2 3))
3

(mylen 2)
-1

(mylen "foo")
-1

(mylen '(1 2 goo (bar baz)))
4

;; here is why:
(draw-tree '(1 2 goo (bar baz)))
"
[o|o]---[o|o]---[o|o]---[o|/]
 |       |       |       |      
 1       2      goo     [o|o]---[o|/]
                         |       |      
                        bar     baz     
"

;;; Challenge: change the definition above to count all atoms in a tree!
;;;   This new function should return 5 for the above nested list.


;;; More recursion
(defun fact (n)
  "Factorial of an integer"
  (if (= n 0) 1
    (* n (fact (- n 1)))))
fact

(fact 5)
120

(fact 50)
30414093201713378043612608166064768844377641568960512000000000000

;; BTW, notice that
(eq (fact 50) (fact 50))
nil

;; but 
(eql (fact 50) (fact 50))
t

(fact 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

;; sadly, we run out of stack space 
(fact 300)
;; Debugger entered--Lisp error: (error "Lisp nesting exceeds ‘max-lisp-eval-depth’")

;; in my 28.2 emacs-version on Darwin:
max-lisp-eval-depth
800

emacs-version
"28.2"

;; let's try a tail-recursive form:
(defun fact-tc (n acc)
  (if (= n 0) acc
    (fact-tc (- n 1) (* n acc))))
fact-tc

(fact-tc 50 1)
30414093201713378043612608166064768844377641568960512000000000000

(fact-tc 100 1)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

;; we are doing slightly better, it seems:
(fact-tc 300 1)
306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000

(fact-tc 350 1)
123587405826548875014395199766546457224532073946919515879429330230093035357491314216934583295011178445941552109432761532449767761892237043444942213964090091669490545661255111334533069825455607852789836451585122902099649977304226794874840601811017764137584868137504975397325925882541777117706619490238363409254589994079334626893194608016888986949684994333459029365214555784862353939102567266745712846824819004146064184543888123533464975621179287075018586481357643313075153359002713294611632614208134036650116689052585573350955360246170451786972351365370405722036294385680478287278827977511411909071460914807681131728232182991517416470483157998067487290163200000000000000000000000000000000000000000000000000000000000000000000000000000000000000

(fact-tc 370 1)
169421378414976771498034360300750575179884985266562028567190838573975834146304427128457690991055645734383896369207629597362053852992498591517253291160455060524925127533064839291553043072544244101700962213277095890111021672662083764086326801595776937938311694908543218548484973438746436323305295793302852331239633714259307208890737973024528315339036736361090940548961962687255631783569154283321417968564192387176237187658618608592976500594894177965909301444702879346280086938422662659774404705763188389217541828664080114234627262227891895206367030545494542034919038529634589604054050498204398329354269723590042264395124560855397992123903145458287039830638826374147370187610640764055365686990037107867648000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

(fact-tc 390 1)
684012177738220662390618964870204947631481327477028535066111792028247435901614563025958158135576400709575062412230994806211614786597153958894469691326122968990881163020490597055741282940811292445113769074225186148119022832226763895940834095381671684736901441665712949473091917448139320339710262195667705135341665365330557523282747762705692163108946405024495340645264173808101919962489292317247975376876732609007609292526172700863082875594851952005449289132928666836795313937443764581554465013445730069513994819165809962058282554513632941272804458503088656160795473749388280230454827595664272625262002943943736441240202129520450864478439562773478090378204531072762906839469398662200875524557573631555379026704581269487018770453911393439431446757376000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

;; but alas it doesn't last long
(fact-tc 400 1)
;; Debugger entered--Lisp error: (error "Lisp nesting exceeds ‘max-lisp-eval-depth’")

(fact-tc 500 1)
;; Debugger entered--Lisp error: (error "Lisp nesting exceeds ‘max-lisp-eval-depth’")

;;; Emacs does not fully support tail-call optimization, but other LISPs do!
;;   We saw SBCL chew through (fact-tc 30000) without a problem. More on this later.


;; Lambdas are super-important, though now we are just looking at their syntax:

(defun square (x) (* x x))
square

(mapcar #'square '(1 2 3 4 5))
(1 4 9 16 25)

(mapcar (lambda (x) (* x x)) '(1 2 3 4 5))
(1 4 9 16 25)

(mapcar (lambda (x) (* x 2)) '(1 2 3 4 5))
(2 4 6 8 10)

;; lambda behaves the same as any named function under apply and funcall
(apply (lambda (x) (+ 1 x)) '(100))
101

(funcall (lambda (x) (+ 1 x)) 100)
101

;; To be continued