; This is a bytecode-by-bytecode analysis of a simple function ; byte-compiled under lexical bindings. See elisp-bytecode-dynamic-binding-log.txt ; for its dynamic counterpart. ; On emacs bytecode: http://nullprogram.com/blog/2014/01/04/ ; On changes in it for lexical binding in emacs24: ; https://prog-elisp.blogspot.com/2012/05/lexical-scope.html ; The Emacs bytecode compiler (written in Elisp): ; http://cvs.savannah.gnu.org/viewvc/emacs/emacs/lisp/emacs-lisp/bytecomp.el?view=markup ; Emacs docs: ; On byte compilation: https://www.gnu.org/software/emacs/manual/html_node/elisp/Byte-Compilation.html ; On byte-code objects (results of compilation): ; https://www.gnu.org/software/emacs/manual/html_node/elisp/Byte_002dCode-Objects.html ; On how to read disassembly: ; https://www.gnu.org/software/emacs/manual/html_node/elisp/Disassembly.html#Disassembly ; Additional info you might want to look up: ; https://www.emacswiki.org/emacs/ByteCodeEngineering ; Actual C code for the Emacs VM, src/bytecode.c in the Emacs source tree: ; e.g., https://github.com/emacs-mirror/emacs/blob/master/src/bytecode.c or ; https://searchcode.com/codesearch/view/29329403/ (watch the versions!) ; http://www.retro11.de/ouxr/43bsd/usr/src/new/emacs/src/bytecode.c.html (setq lexical-binding t) t (defun len (lst) (cond ((null lst) 0) (t (+ 1 (len (cdr lst)))))) len (len '()) 0 (len '(1 2 3)) 3 (symbol-function 'len) (closure (t) (lst) (cond ((null lst) 0) (t (+ 1 ...)))) (byte-compile #'len) #[257 "\211\204\300\207\301A!T\207" [0 len] 3 " (fn LST)"] ; now len is a byte-compiled function (symbol-function 'len) #[257 "\211\204\300\207\301A!T\207" [0 len] 3 " (fn LST)"] ; Recall that under dynamic binding, the compilation result was ; #[(lst) "^H\204^F^@\301\207\302^HA!T\207" [lst 0 len] 2] ; ---some bytecotes are shared, others new! ; Note: byte-compile works in the context where it's called, but its results ; side-effect the symbol definition, caching the byte-compiled ; version. That is, if you byte-compile #'len in a different buffer ; under dynamic binding, and then switch back here, and call ; byte-compile again, the result will be the cached dynamic variant, ; #[(lst) "\204\301\207\302A!T\207" [lst 0 len] 2] ! ; I managed to do this unwittingly; it got me confused for a few minutes! (disassemble #'len) nil ; pasted from the other buffer: byte code for len: doc: ... args: 257 0 dup 1 goto-if-not-nil 1 4 constant 0 5 return 6:1 constant len 7 stack-ref 1 8 cdr 9 call 1 10 add1 11 return ; Assume l is (a b), so cdr_of_l is (b), cddr_of_l is nil. We call (len l). ; The following is the trace of bytecodes executed by the VM, showing the data stack *after* each: ;; IMPORTANT: unlike many other virtual machines, Elisp does not work with the same stack, ;; but instead creates a new stack for each Bcall, links them up in a stack-like structure. ;; It deallocates the top stack on each return. and pushes the return value onto the ;; previous one, from which the previous "call" was made. As the bytecode program counter ;; is actually a part of the stack structure and is saved in it, returning means jumping ;; to the next bytecode on the caller stack, with the result of the callee pushed on it. ;; Read this in http://cvs.savannah.gnu.org/viewvc/emacs/emacs/src/bytecode.c?view=markup , the ;; "case Breturn" clause of the opcode switch inside the fetch-decode-execute-loop. ;; See reading-elisp-vm-code.txt for more info. ;; Hence argument values left on stacks at return time don't actually accumulate. They would if all calls ;; operated on the same stack, and cleanup would be needed before each return. on entry: [l) ; argument passed on stack under the lexical-binding calling convention after 0 (dup): [l l) ; since goto-if-not-nil test consumes the value, we create a copy of the argument--- ; if it gets popped from the stack, we'd lose it (no lookups by name here!) ;; this dup is important, even thought it seems to leave a refundant copy of the argument on the stack at return time. ;; the problem is that goto-if-not-nil pops the top of the stack no matter which way it goes; and although the ;; argument is no longer needed on the empty-list/nil branch, it *is* needed for cdr on the non-nil branch. ;; But goto-if-not-nil pops it before the decision is made, and so we must treat the branches uniformly. 1: [l) ; goto-if-not-nil consumes the tested value from the top of the stack 6: [l len) 7: [l len l) ; lst stored in slot 1 of the stack (counting down from the top) gets pushed on top, to be consumed by call 8: [l len cdr_of_l) ; cdr pops l and pushed its result, cdr_of_l 9: [l)->[cdr_of_l) ; len and cdr_of_l get popped by call ("call 1" explicitly gives the number of args to pop) ; a new stack is created, linked with the old one and cdr_of_l gets pushed onto it as the argument ; we now jump back to 0, pushing "10" on the control stack, which becomes ["10"> ; (our control stack is really just the C stack, in which of the Fbyte_code's frames live; ; what really happens is that the pc associated with the original stack is now at 10, ; and will stay there until we return. The new stack's pc starts at 0.) 0: [l)->[cdr_of_l cdr_of_l) 1: [l)->[cdr_of_l) 6: [l)->[cdr_of_l len) 7: [l)->[cdr_of_l len cdr_of_l) ; now "slot 1" of the stack (counting from the top) is cdr_of_l, so it gets pushed 8: [l)->[cdr_of_l len nil) ; cdr of cdr_of_l is nil 9: [l)->[cdr_of_l)->[nil) ; args are popped and we go for another recursive call, and create a new stack ; control stack is now ["10" "10"> 0: [l)->[cdr_of_l)->[nil nil) 1: [l)->[cdr_of_l)->[nil) ; now goto-if-not-nil eats nil and falls through to 4 4: [l)->[cdr_of_l)->[nil 0) 5: [l)->[cdr_of_l 0) ; return deallocates the latest stack, and pushes its result onto a previous one! ; our control stack is now ["10">, we are back to previous stack's saved pc of "10" 10: [l)->[cdr_of_l 1) ; add1 pops off 0, pushes its result 0+1==1 11: [l 1) ; return destroys the data stack; we go back to the bottom stack, with the saved pc of "10" ; you can think of it as popping "10" off the control stack, emptying it. 10: [l 2) ; 1 popped, 1+1 pushed 11: bye, result=2 ; we return to whoever called us, destroying this stack and pushing 2 on top of ; our caller's stack as our result. Indeed, it's the length of l! ; You might ask, how come a copy of the argument(s) end(s) up littering the ; stacks, and never gets used? These are destroyed when ; the stack gets destroyed on return, so it's not a problem, but isn't it untidy? ; Perhaps that first dup could be optimized away? ; If we forego the first dup, the argument value will be consumed by ; "goto-if-not-nil", and we'll have nothing left to feed to "cdr" when ; the time comes. But could the bytecode sequence somehow work around it? ; The answer here is likely that, as the beginnging of the len ; function gets compiled, we don't know if the argument will be used ; or not until all of it is byte-compiled. So we'd need to do ; another pass to figure this out, and we don't want to. ; This is a plausible theory. ; ; See how this works when the saved value does get used: (defun sum (lst) (cond ((null lst) 0) (t (+ (car lst) (sum (cdr lst)))))) sum ; The only changes compared to len are the function name and "1" changed to (car lst) (byte-compile #'sum) #[257 "\211\204\300\207\211@\301A!\\\207" [0 sum] 4 " (fn LST)"] (disassemble (byte-compile #'sum)) nil ; Pasted byte code byte code: doc: ... args: 257 0 dup 1 goto-if-not-nil 1 4 constant 0 5 return 6:1 dup 7 car 8 constant sum 9 stack-ref 2 10 cdr 11 call 1 12 plus 13 return ; Observe how the value copied by first dup is consumed, but another dup makes sure the argument stays around, ; just in case more statements that need to use it are coming. Step through this and see! Or, better, ; write an emulator to see it. Note "stack-ref 2": the function takes one extra slot on the stack, due to ; an extra dup. ;;----------------------------------------------------------------------------- ;; Starting from here, I go out on a "what if" exploration. Read only if ;; you too want to mess with bytecodes! ;;----------------------------------------------------------------------------- ;; What would happen if we removed the dup from the len function? It will break, ;; of course, but how exactly? Let's mess with the bytecode and see! ; First, we need to pick apart the result of byte-compile. ; It's a special object, a byte-code function object: ; https://www.gnu.org/software/emacs/manual/html_node/elisp/Byte_002dCode-Objects.html ; Quoting: ; ; Internally, a byte-code function object is much like a vector; ; its elements can be accessed using aref. Its printed ; representation is like that for a vector, with an additional ‘#’ ; before the opening ‘[’. It must have at least four elements; ; there is no maximum number, but only the first six elements have ; any normal use. ; The aref trick seems to work, we get the string: (aref (byte-compile #'len) 1) "\211\204\300\207\301A!T\207" ; But if we try to cut-and-paste that string into the above defalias, it fails, for obscure reasons. ; what does defalias do? look it up! ; this is no good, because I cut-and-pasted the string with non-ascii chars, ; and it's no longer the same string. It's even different length. (defalias 'raw-len #[257 "\211\204^F^@\300\207\301^AA!T\207" [0 raw-len] 3 "(fn LST)"]) raw-len (length "\211\204^F^@\300\207\301^AA!T\207") 15 (length (aref (byte-compile #'len) 1)) 12 ;; So raw-len abjectly fails: (raw-len '(1 2 3)) => Invalid byte opcode: op=0, ptr=18014 ; Argh, the representation of the string is not reusable for READ! ; So we need to manipulate the bytecode strings carefully. Luckily, Emacs 24 ; comes with functions that convert between strings and intereger lists, and back. ; Let's get a readable version of the bytecode string. (aref (byte-compile #'len) 1) "\211\204\300\207\301A!T\207" (string-to-list (aref (byte-compile #'len) 1)) (137 132 6 0 192 135 193 1 65 33 84 135) (unibyte-string 137 132 6 0 192 135 193 1 65 33 84 135) "\211\204\300\207\301A!T\207" (equal (aref (byte-compile #'len) 1) (unibyte-string 137 132 6 0 192 135 193 1 65 33 84 135)) t ; So, we can re-create the right unibyte string. Re-trying defalias: (defalias 'raw-len #[257 (aref (byte-compile #'len) 1) [0 raw-len] 3 "(fn LST)"]) raw-len (raw-len '(x y z)) => Invalid byte code ; What's going on? Well, neither vectors nor byte-code objects evaluate their arguments (somewhat like quote). ; To build one, you need to call the constuctor function; no way around it. (make-byte-code 257 (aref (byte-compile #'len) 1) [0 raw-len] 3 "(fn LST)") #[257 "\211\204\300\207\301A!T\207" [0 raw-len] 3 "(fn LST)"] (defalias 'raw-len (make-byte-code 257 (aref (byte-compile #'len) 1) [0 raw-len] 3 "(fn LST)")) raw-len ; Finally, it works! We can re-create a function from its bytecode. (raw-len '(x y z)) 3 ; So we can try the same with constructed arrays of bytecode: (defalias 'raw-len (make-byte-code 257 (unibyte-string 137 132 6 0 192 135 193 1 65 33 84 135) [0 raw-len] 3 "(fn LST)")) raw-len (raw-len '(x x x x)) 4 (raw-len '(x x x x nil)) 5 ; Now we're cookin'! Let's edit out that DUP bytecode and see what happens (defalias 'len-nodup (make-byte-code 257 (unibyte-string 132 6 0 192 135 193 1 65 33 84 135) [0 len-nodup] 3 "(fn LST)")) len-nodup (len-nodup '()) 0 (len-nodup '(1 2 3)) ; => Wrong type argument: listp, 0 ; WHUT? But, as we look at the byte-code, it becomes clear: the label is in the wrong place! ; the target of "goto-if-not-nil 1" should be 5:1, not 6:1! (disassemble #'len-nodup) nil ; Pasted: byte code for len-nodup: doc: (fn LST) args: 257 0 goto-if-not-nil 1 3 constant 0 4 return 5 constant len-nodup ; <---- this should be the target of the jump, not the next instruction! 6:1 stack-ref 1 7 cdr 8 call 1 9 add1 10 return ;; On a hunch, could that "6" be the target of the jump? Let's try it: (disassemble (make-byte-code 257 (unibyte-string 132 5 0 192 135 193 1 65 33 84 135) [0 len-nodup] 3 "(fn LST)")) nil byte code: doc: (fn LST) args: 257 0 goto-if-not-nil 1 3 constant 0 4 return 5:1 constant len-nodup 6 stack-ref 1 7 cdr 8 call 1 9 add1 10 return ; Retry: (defalias 'len-nodup (make-byte-code 257 (unibyte-string 132 5 0 192 135 193 1 65 33 84 135) [0 len-nodup] 3 "(fn LST)")) len-nodup (len-nodup ()) 0 (len-nodup '(foo)) ; Wrong type argument: listp, 35183699949296 ;; But wait, what does "stack-ref 1" replicate, to take the cdr of? ;; There is nothing we can predict in the stack slot there, since we popped the argument at goto-if-not-nil; ;; so cdr gets garbage for its argument, whatever value was *right next* to the stack! ;; It coudld be a pointer to something, possibly: (format "%x" 35183699949296) "1fffd7eff6f0" ;; Imagine that we tried to derefence that or feed it to some Elisp bytecode as argument! ; No surprise that Emacs can crash if we feed it hand-crafted opcodes. ;;;;------------------------ Another random exploration: ---------------------------- ;;------------------ What do tail-calls look like in bytecode? ----------------------- ;; ;; Answer: not very different. Emacs doesn't do tail call optimization. ;; (defun tlen (lst acc) (cond ((null lst) acc) (t (tlen (cdr lst) (+ 1 acc))))) tlen (tlen nil 0) 0 (tlen '(1 2 3) 0) 3 (disassemble (byte-compile #'tlen)) nil ; pasted: byte code: doc: ... args: 514 0 stack-ref 1 1 goto-if-not-nil 1 4 return 5:1 constant tlen 6 stack-ref 2 7 cdr 8 stack-ref 2 9 add1 10 call 2 11 return ; execution trace [l 0) 0: [l 0 l) if l==nil: 1: [l 0) 4: result==0 else: 5: [l 0 tlen) 6: [l 0 tlen l) 7: [l 0 tlen cdr_of_l) 8: [l 0 tlen cdr_of_l 0) 9: [l 0 tlen cdr_of_l 1) 10: [l 0)->[cdr_of_l 1) 0: ...