CODEWITHSUNDEEP
common-lisptail-call-optimization
Gustav Bertram
Gustav Bertram

Reputation: 14905

How can I tell if my function has been tail call optimized?

I'm reading section 2.8 (Tail Recursion) in On Lisp. It has an example of a tail recursive function:

(defun our-length-tr (lst)
  "tail recursive version with accumulator"
  (labels ((rec (lst acc)
             (if (null lst)
                 acc        
                 (rec (cdr lst) (1+ acc)))))
    (rec lst 0)))

It says that many Common Lisp compilers do TCO, but you may need (proclaim '(optimize speed)) at the top of your file.

How can I tell for certain that my compiler supports TCO, and that it will compile my function to a loop version rather than a recursive version?

Upvotes: 0

Views: 613

Answers (1)

Renzo
Renzo

Reputation: 27424

There are a couple of simple ways of checking if a function is compiled with tail recursion or not.

If you can read assembly language then the primitive function disassemble (see the documentation) can be used, for instance:

* (disassemble 'our-length-tr)

; disassembly for OUR-LENGTH-TR
; Size: 89 bytes. Origin: #x10034F8434
; 34:       498B4C2460       MOV RCX, [R12+96]                ; no-arg-parsing entry point
                                                              ; thread.binding-stack-pointer
; 39:       48894DF8         MOV [RBP-8], RCX
; 3D:       488B4DF0         MOV RCX, [RBP-16]
; 41:       31D2             XOR EDX, EDX
; 43:       EB3E             JMP L2
; 45:       660F1F840000000000 NOP
; 4E:       6690             NOP
; 50: L0:   4881F917001020   CMP RCX, #x20100017              ; NIL
; 57:       7506             JNE L1
; 59:       488BE5           MOV RSP, RBP
; 5C:       F8               CLC
; 5D:       5D               POP RBP
; 5E:       C3               RET
; 5F: L1:   8D41F9           LEA EAX, [RCX-7]
; 62:       A80F             TEST AL, 15
; 64:       751F             JNE L3
; 66:       488B5901         MOV RBX, [RCX+1]
; 6A:       48895DE8         MOV [RBP-24], RBX
; 6E:       BF02000000       MOV EDI, 2
; 73:       41BBF004B021     MOV R11D, #x21B004F0             ; GENERIC-+
; 79:       41FFD3           CALL R11
; 7C:       488B5DE8         MOV RBX, [RBP-24]
; 80:       488BCB           MOV RCX, RBX
; 83: L2:   EBCB             JMP L0
; 85: L3:   0F0B0A           BREAK 10                         ; error trap
; 88:       2F               BYTE #X2F                        ; OBJECT-NOT-LIST-ERROR
; 89:       08               BYTE #X08                        ; RCX
; 8A:       0F0B10           BREAK 16                         ; Invalid argument count trap
NIL

(SBCL 1.4.1 on Mac OS X 10.13.3)

Otherwise you can call the function with a very long list and see if the result is a Stack Overflow error (recursion compiled as recursion), or the length of the list (recursion compiled with iteration, tail recursion).

Even better, you can provide an infinite length list, like in:

(our-length-tr '#1=(1 2 3 . #1#)))

and see if a Stack Overflow error is produced (usually almost immediately), or no output at all is produced because of the infinite loop of the iteration.

Upvotes: 5

Related Questions