(DEFINE (SOS X Y)
  (+ (SQ X) (SQ Y)))
(DEFINE (SQ X)
  (* X X))

;;; SUBSTITUTION RULE 1B:(6m)
; To evaluate an application
;  Evaluate the operator to get procedure
;  Evaluate the operands to get arguments
;  Apply the procedure to the arguments
;    Copy the body of the procedure.
;     substituting the arguments supplied
;     for the formal parameters of the
;     procedure.
;    Evaluate the resulting new body.

(SOS 3 4)
   ;reducing into (reduction-step):
(+ (SQ 3) (SQ 4))
   ;reduction (2):
(+ (SQ 3) (* 4 4))
   ;reduction (3):
(+ (SQ 3) 16)
   ;reduction (4):
(+ (* 3 3) 16)
   ;reduction (5):
(+ 9 16)
; In the end, this helps the reader/listener.
; Order is irrelevant 1B:(10m)
; The magicians spells (PART I) 1B:(12m)
;   => PEANO ARITHMETIC 1B:(13m35s)
(DEFINE (+ X Y)
  (IF (= X 0)
      Y
      (+ (-1+ X) (1+ Y))))
; "Now we have a reasonably mechanical way of understanding how
;  a program made out of procedures and expressions evolves a
;  process. I'd like to develop some intuition..." by Jay Sussman
;  1B:(17m18s)
;
; imagining the results (like in fotography), looking at a Lisp test-strip:
; 1B:(19m)
;   (define (+ x y)
;     (if (= x 0)
;         y
;         (+ (-1+ x) (1+ y))))
; > (+ 4 3)
; 1> (+ 3 4)
; 2> (+ 2 5)
; 3> (+ 1 6)
; 4> (+ 0 7)
; 5> 7
;   (define (+ x y)
;     (if (= x 0)
;         y
;         (1+ (+ (-1+ x) y))))
; > (+ 4 3)
; 1> (1+ (+ 3 3))
; 2> (1+ (1+ (+ 2 3)))
; 3> (1+ (1+ (1+ (+ 1 3))))
; 4> (1+ (1+ (1+ (1+ (+ 0 3)))))
; 5> (1+ (1+ (1+ (1+ 3))))
; 6> (1+ (1+ (1+ 4)))
; 7> (1+ (1+ 5))
; 8> (1+ 6)
; 9> 7
; to the overviewer: "almost" identical, just a bit of character-mangling
; but a different shape for the the process. One is to reduce from one and
; giving to another in an immediate way. Part of my natural form is the second,
; even if more complex. It is to reduce from the left and adding to the right
; the number you reduced from the left afterwards.
;
; Jay says something important after 1B:(20m40s), he talks about the shapes
; of these processes. And what he tells me is, that the second one is
; DEFERRING something. And yes, the addition in my head is deferring one
; operation, expands it so to say... into these successor-statements. If for
; example I add 8 and 8, I take away 2 from one and later add it to another,
; there remains the rest of 6. I simply say 16 because now I map 6 over 0 and
; my "10" mutates into "16".
; 1B:(37m) Now we know two kinds of processes that can be evolved with 
; recursive definitions. One kind was an iteration (probably linear) and
; another was recursive. Before the end, Jay Sussman talked a little about
; analogies for these processes.
;
; Now comes: "How to not write programs, gaining an intuition on the process
; they evolve." with the Fibonacci number.
(DEFINE (FIB N)
  (IF (< N 2)
      N
      (+ (FIB (- N 1))
         (FIB (- N 2)))))
; > (FIB 4)
; 1> (+ (FIB 3) (FIB 2))
; 2> (+ (+ (FIB 2) (FIB 1)) 2)
; 3> (+ (+ 2 1) 2)
; 4> 5
;
; > (FIB 5)
; 1> (+ (FIB 4) (FIB 3))
; 2> (+ (+ (FIB 3) (FIB 2)) (+ (FIB 2) (FIB 1)))
; 3> (+ (+ (+ (FIB 2) (FIB 1)) 2) (+ 2 1))
; 4> (+ (+ (+ 2 1) 2) (+ 2 1))
; 5> 8
;
; 1B:(43m)
; TIME: O(fib(n))
; SPACE: O(n)
;
; 1B:(47m15s) Towers of Hanoi, moving a tower(N) from one spike to another
; through recursion.
; 1B:(48m) "The way of constructing a recursive definition is by
; wishful thinking." --Jay Sussman
(DEFINE (TMOVE N FROM TO SPARE)
  (COND ((/= N 0)
          (TMOVE (-1+ N) FROM SPARE TO)
          (PRINT-MOVE FROM TO)
          (TMOVE (-1+ N) SPARE TO FROM))))

; 1B:(52m40s) giving the task
; 1B:(53m10s) explaining the task
; => Move tower of height 4 from 1 to spike 2 using spike 3 as a spare.
; Resolving at 1B:(53m14s) and 1B:(55m)
(TMOVE 4 1 2 3)
; 1> (@RUN
;    (TMOVE 3 1 3 2) (PRINT-MOVE 1 2) (TMOVE 3 3 2 1))
; 2> (@RUN
;    (TMOVE 2 1 2 3) (PRINT-MOVE 1 3) (TMOVE 2 2 1 3)
;        (PRINT-MOVE 1 2)
;    (TMOVE 2 3 1 2) (PRINT-MOVE 3 2) (TMOVE 2 1 3 2))
; 3> (@RUN
;    (TMOVE 1 1 3 2) (PRINT-MOVE 1 2) (TMOVE 1 3 2 1)
;        (PRINT-MOVE 1 3)
;    (TMOVE 1 2 3 1) (PRINT-MOVE 2 1) (TMOVE 1 3 1 2)
;        (PRINT-MOVE 1 2)
;    (TMOVE 1 3 2 1) (PRINT-MOVE 3 1) (TMOVE 1 2 1 3)
;        (PRINT-MOVE 3 2)
;    (TMOVE 1 1 2 3) (PRINT-MOVE 1 3) (TMOVE 1 2 3 1))
; 4> (@RUN
;    (TMOVE 0 1 2 3) (PRINT-MOVE 1 3) (TMOVE 0 2 3 1)
;        (PRINT-MOVE 1 2)
;    (TMOVE 0 3 1 2) (PRINT-MOVE 3 2) (TMOVE 0 1 2 3)
;        (PRINT-MOVE 1 3)
;    (TMOVE 0 2 1 3) (PRINT-MOVE 2 3) (TMOVE 0 1 3 2)
;        (PRINT-MOVE 2 1)
;    (TMOVE 0 3 2 1) (PRINT-MOVE 3 1) (TMOVE 0 2 1 3)
;        (PRINT-MOVE 1 2)
;    (TMOVE 0 3 1 2) (PRINT-MOVE 3 2) (TMOVE 0 1 2 3)
;        (PRINT-MOVE 3 1)
;    (TMOVE 0 2 3 1) (PRINT-MOVE 2 1) (TMOVE 0 3 1 2)
;        (PRINT-MOVE 3 2)
;    (TMOVE 0 1 3 2) (PRINT-MOVE 1 2) (TMOVE 0 3 2 1)
;        (PRINT-MOVE 1 3)
;    (TMOVE 0 2 1 3) (PRINT-MOVE 2 3) (TMOVE 0 1 3 2))
; 5> (@RUN
;    (PRINT-MOVE 1 3)
;    (PRINT-MOVE 1 2)
;    (PRINT-MOVE 3 2)
;    (PRINT-MOVE 1 3)
;    (PRINT-MOVE 2 3) >> ERROR in my example (this varies from 1B:(55m))
;                        should be: (PRINT-MOVE 2 1)
;    (PRINT-MOVE 2 1) >> ERROR (2 3)
;    (PRINT-MOVE 3 1) >> ERROR (1 3)
;    (PRINT-MOVE 1 2) >> CORRECT, now it is the same again...
;    (PRINT-MOVE 3 2)
;    (PRINT-MOVE 3 1) >> ERROR (no block on 3)
;    (PRINT-MOVE 2 1)
;    (PRINT-MOVE 3 2)
;    (PRINT-MOVE 1 2) >> ERROR (1 3)
;    (PRINT-MOVE 1 3) >> ERROR (1 2)
;    (PRINT-MOVE 2 3) >> ERROR (3 2)
;
; The correct order would be:
; 5> (@RUN
;    (PRINT-MOVE 1 3)
;    (PRINT-MOVE 1 2)
;    (PRINT-MOVE 3 2)
;    (PRINT-MOVE 1 3)
;    (PRINT-MOVE 2 1)
;    (PRINT-MOVE 2 3)
;    (PRINT-MOVE 1 3)
;    (PRINT-MOVE 1 2)
;    (PRINT-MOVE 3 2)
;    (PRINT-MOVE 3 1)
;    (PRINT-MOVE 2 1)
;    (PRINT-MOVE 3 2)
;    (PRINT-MOVE 1 3)
;    (PRINT-MOVE 1 2)
;    (PRINT-MOVE 3 2)
;
; (END)