sergey@snowball ~ % 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.

>(defun len (l acc) (cond ((null l) acc) ((consp l) (len (cdr l) (1+ acc))) (t (error "boo"))))
 
LEN

;; Explain this mistake in one word. Yell it out!

>(len nil)

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by LEN.

Condition in LEN [or a callee]: INTERNAL-SIMPLE-PROGRAM-ERROR: LEN [or a callee] requires more than one argument.

Broken at LEN.  Type :H for Help.
    1  Return to top level. 
>>1

;;  ARITY! ARITY! ARITY! ARITY! ARITY! ARITY! ARITY! ARITY! 


Top level.
>(len nil 0)

0

;; Arity check is very useful, but it is NOT a proper type check. We meant
;;  LEN to take lists and produce naturals, so how come this happens?

>(len nil '(1 2 3 4 5))

(1 2 3 4 5)

;; Answer: our code on this logical path admits and produces multiple types. How much of
;;  a real problem is this? Some exploits leverage exactly this looseness. Strict
;;  typing of Haskell, OCaml, and Rust won't allow this (sometimes annoyingly).

>(len '(1 2 3 4 5) 0)

5

>(len '(1 2 3 4 x y z) 0)

7

;; So far so good. Let's try to make lists that are too big for LEN to process.

>(defun range (n acc) (if (= n 0) acc (range (1- n) (cons n acc))))

RANGE

>(range 0)

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by RANGE.

Condition in RANGE [or a callee]: INTERNAL-SIMPLE-PROGRAM-ERROR: RANGE [or a callee] requires more than one argument.

Broken at RANGE.  Type :H for Help.
    1  Return to top level. 
>>1

Top level.

;;  ARITY! ARITY! ARITY! ARITY! ARITY! ARITY! ARITY! ARITY!  GCL has our back (on arity).


>(range 0 nil)

NIL   ;; This is actually consistent with the type of RANGE, from Naturals to Lists. Remember
      ;;   that NIL _is_ a list, the base case of a list in Common Lisp.

>(range 1)

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by RANGE.

Condition in RANGE [or a callee]: INTERNAL-SIMPLE-PROGRAM-ERROR: RANGE [or a callee] requires more than one argument.

Broken at RANGE.  Type :H for Help.
    1  Return to top level. 
>>1

;;  ARITY! ARITY! ARITY! ARITY! ARITY! ARITY! ARITY! ARITY!  GCL still has our back.

Top level.
>(range 1 nil)

(1)

>(range 2 nil)

(1 2)

>(range 3 nil)

(1 2 3)

>(range 4 nil)

(1 2 3 4)

;; We tried so hard to get the tail call in place to stop paying the Stack Frame Tax.
;;  But in GCL you only get it once you COMPILE the function, not before.

>(range 300000000 nil)

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by IF.

Condition in IF [or a callee]: INTERNAL-SIMPLE-ERROR: Invocation history stack overflow.

Broken at IF.  Type :H for Help.
    1  Return to top level. 
>>1

;;;; As you reproduce it, type N at the >> prompt. You should be able to see at which
;;;;   value of N this tail-recursive but not tail-call-optimized (TCO) form broke the stack. Do it.

;; Note that so far RANGE is just a list, just like any Lisp program starts as a list:

Top level.
>#'range

(SYSTEM:LAMBDA-BLOCK RANGE (N ACC)
  (IF (= N 0) ACC (RANGE (1- N) (CONS N ACC))))

>(consp #'range)

T

>(compile 'range)

Compiling /var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.lsp.
End of Pass 1.  

;; Note: Tail-recursive call of RANGE was replaced by iteration.   // <--- Now we are seeing TCO
End of Pass 2.  
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
Finished compiling /private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.o.
;; Loading #p"/private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.o"
start address -T 0x10b148ab0 ;; Finished loading #p"/private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.o"
#<compiled-function RANGE>
NIL
NIL

>#'range

#<compiled-function RANGE>

;; And now we are stack-less, no overflows, thanks to the compiler:

>(range 30000000)

(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
[..skipped..]
^C                ;; I hit Ctrl+C here, to prevent printing out the entire buffer

Correctable error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by SYSTEM::GCL-TOP-LEVEL.
If continued: Type :r to resume execution, or :q to quit to top level.26653 526654 526655 526656 526657 526658 526659 526660 526661
 526762 526763 526764 
SIMPLE-ERROR: Console interrupt.

Broken at SYSTEM::GCL-TOP-LEVEL.  Type :H for Help.
    1 (continue) Type :r to resume execution, or :q to quit to top level. 
    2  Return to top level. 
>>2

Top level.

;; So this works. EVAL succeeds, and the PRINT phase of the READ-EVAL-PRINT loop
;;   is now printing the very long list. Yay TCO.


;; Interlude: What is the type of RANGE now, once it's been compiled? In fact, what
;;  if even a type in Lisp? 

>(consp #'range)

NIL

;; TYPE-OF is handy:

>(type-of #'range)

COMPILED-FUNCTION     ;; But what is this COMPILED-FUNCTION a printed form of?

>(type-of (type-of #'range))

SYMBOL                ;;  ..oh, it's just a SYMBOL. All TYPE-OF reported types in GLC are symbols

;; In the meantime, LEN is still a list <=> Lisp program <=> lambda block:

>#'len

(SYSTEM:LAMBDA-BLOCK LEN (L ACC)
  (COND
    ((NULL L) ACC)
    ((CONSP L) (LEN (CDR L) (1+ ACC)))
    (T (ERROR "boo"))))

;; It's truly a list, i.e., a CONS cell:

>(consp #'len)

T

>(type-of #'len)

CONS

>(type-of (type-of #'len))

SYMBOL

;; All types are represented at symbols:

>(eq (type-of (type-of #'len)) (type-of (type-of #'range)))

T

>(compile 'len)

Compiling /var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.lsp.
End of Pass 1.  

;; Note: Tail-recursive call of LEN was replaced by iteration.     ;; <-- Yay TCO!
End of Pass 2.  
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
Finished compiling /private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.o.
;; Loading #p"/private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.o"
start address -T 0x10b591930 ;; Finished loading #p"/private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.o"
#<compiled-function LEN>
NIL
NIL

;; So I accidentally managed to give RANGE three arguments. That triggered an error, but
;;   not the most immediate kind of error we'd think of:

>(len (range 30 000 000))

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by LEN.

SIMPLE-ERROR: boo

Broken at LEN.  Type :H for Help.
    1  Return to top level. 
>>1

;; It turns out that COMPILE-d code does not by default check the arity of functions,
;;   for the presumed sake of performance. 
;;  But we can tell the compilation system to not skip this check while still optimizing
;;   for performance:

Top level.

>(proclaim '(optimize (safety 1) (speed 3)))

NIL

;; Oh, LEN is already compiled. Better redefine it to recompile.

>(compile 'len)

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by COMPILE.

SIMPLE-ERROR: can't compile LEN

Broken at COMPILE.  Type :H for Help.
    1  Return to top level. 
>>1

Top level.

>(defun len (l acc) (cond ((null l) acc) ((consp l) (len (cdr l) (1+ acc))) (t (error "boo"))))
LEN

>(compile 'len)

Compiling /var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.lsp.
End of Pass 1.  

;; Note: Tail-recursive call of LEN was replaced by iteration.
End of Pass 2.  
OPTIMIZE levels: Safety=1 (No runtime error checking), Space=0, Speed=3
Finished compiling /private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.o.
;; Loading #p"/private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.o"
start address -T 0x10b587d30 ;; Finished loading #p"/private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.o"
#<compiled-function LEN>
NIL
NIL

;; Do the same for RANGE:

>(defun range (n acc) (if (= n 0) acc (range (1- n) (cons n acc))))

RANGE

>(COMPILE 'range)

Compiling /var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.lsp.
End of Pass 1.  

;; Note: Tail-recursive call of RANGE was replaced by iteration.
End of Pass 2.  
OPTIMIZE levels: Safety=1 (No runtime error checking), Space=0, Speed=3
Finished compiling /private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.o.
;; Loading #p"/private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_0.o"

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by COMPILE.
Condition in COMPILE [or a callee]: INTERNAL-SIMPLE-ERROR: Caught fatal error [memory may be damaged]

Broken at COMPILE.  Type :H for Help.
    1  Return to top level. 
>>1

Top level.

;; Not sure what happened there. Trying again:

>(defun range (n acc) (if (= n 0) acc (range (1- n) (cons n acc))))

RANGE

>(COMPILE 'range)

Compiling /var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_1.lsp.
End of Pass 1.  

;; Note: Tail-recursive call of RANGE was replaced by iteration.
End of Pass 2.  
OPTIMIZE levels: Safety=1 (No runtime error checking), Space=0, Speed=3
Finished compiling /private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_1.o.
;; Loading #p"/private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_1.o"
start address -T 0x10b2ee070 ;; Finished loading #p"/private/var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/gazonk_4805_1.o"
#<compiled-function RANGE>
NIL
NIL

;; Now we catch the arity errors:

>(len (range 30 000 000))

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by RANGE.

Condition in RANGE [or a callee]: INTERNAL-SIMPLE-PROGRAM-ERROR: RANGE [or a callee] requires less than three arguments.

Broken at RANGE.  Type :H for Help.
    1  Return to top level. 
>>1

Top level.

;; Enough with the arity already :)

>(len (range 30000000 nil) 0)

30000000

>(len (range 3000000000000 nil) 0)
^C^C

;; Too long. Not too long for SBCL, but GCL is unfortunately held back on my M1 by various inefficiencies 

Correctable error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by RANGE.
If continued: Type :r to resume execution, or :q to quit to top level.
SIMPLE-ERROR: Console interrupt.

[..skipped..]

;; Here we go, with both functions being TC optimized once compiled.

>(len (range 300000000 nil) 0)

300000000

;;;; --------- Let's now reverse a list in TC form ---------

;; OK, what's wrong with this:

>(defun rev (l acc) (if (null l) acc (rev (cdr l) (cons (car l) acc))))

REV

>(rev '(a b c d n))

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by REV.

Condition in REV [or a callee]: INTERNAL-SIMPLE-PROGRAM-ERROR: REV [or a callee] requires more than one argument.

Broken at REV.  Type :H for Help.
    1  Return to top level. 
>>1
Top level.

>(rev '(a b c d n) nil)

(N D C B A)

;; We took a look are the C code that gets generated under TCO. Do it, look at "rev.c".
>(COMPILE-FILE "/Users/sergey/cs59/cosc59.gitlab.io/lisp/rev.lsp" :c-file t)

Compiling /Users/sergey/cs59/cosc59.gitlab.io/lisp/rev.lsp.
End of Pass 1.  

;; Note: Tail-recursive call of REV was replaced by iteration.
End of Pass 2.  
OPTIMIZE levels: Safety=1 (No runtime error checking), Space=0, Speed=3
Finished compiling /Users/sergey/cs59/cosc59.gitlab.io/lisp/rev.o.
#p"/Users/sergey/cs59/cosc59.gitlab.io/lisp/rev.o"
NIL
NIL

;; We try the LABELS Common Lisp syntax. It rather heavily depends on the view of
;;  the balanced parentheses:

;; BAD. WHY?

>(defun rev (ll) (labels ((rev1 l acc) (if (null l) acc (rev1 (cdr l) (cons (car l) acc)))) (rev1 ll nil)))

REV

(rev '(1 2 3 4))

;; BAD. WHY?

Top level.
>(defun rev (ll) (labels ((rev1 (l acc) (if (null l) acc (rev1 (cdr l) (cons (car l) acc)))) (rev1 ll nil))))

REV

>(rev '(1 2 3 4))

NIL

;; BAD. WHY?

>(defun rev (ll) (labels (rev1 (l acc) (if (null l) acc (rev1 (cdr l) (cons (car l) acc)))) (rev1 ll nil)))

REV

;; 

>(rev '(1 2 3 4))

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by LABELS.

Condition in LABELS [or a callee]: INTERNAL-SIMPLE-TYPE-ERROR: REV1 is not of type LIST: 

Broken at LABELS.  Type :H for Help.
    1  Return to top level. 
>>1


Top level.
>

;;;;;; At this point I switched to Emacs, and used its editing to align the parens:

>(defun rev (ll)
  (labels
      ((rev1 (l acc)
             (if (null l) acc
               (rev1 (cdr l)
                     (cons (car l) acc)))))
    (rev1 ll nil)))

REV

;; Works now:

>(rev '(1 2 3 4))

(4 3 2 1)

;; Note that REV1 doesn't becomes a symbol, despite being a label in TCO:


>(boundp 'REV1)

NIL

>(fboundp 'REV1)

NIL

;; Whereas we have the expected:

>(fboundp 'REV)

T

>(boundp 'REV)

NIL