Re: never use `eval'

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> Remember when I said the byte compiler should be more
> offensive and offer more elaborate style warnings?
>
> And this is a good example of that!
>
> Even in the Emacs help
>
>     (describe-function 'eval)
>
> it doesn't say anything about the dangers of the
> "nil environment":
>

   (eval FORM &optional LEXICAL)

>     Evaluate FORM and return its value.
>     If LEXICAL is t, evaluate using lexical scoping.
>     LEXICAL can also be an actual lexical environment,
>     in the form of an alist mapping symbols to
>     their value.

Doesn't seem to work:

    (setf lexical-binding t)

    (let ((x 42))
      (eval 'x t))
    Debugger entered--Lisp error: (void-variable x)

    (let ((x 42))
      (eval 'x nil))
    Debugger entered--Lisp error: (void-variable x)


> This book -
>
>     @book{artificial-intelligence-and-the-design,
>       title      = {Artificial Intelligence and the Design of Expert Systems},
>       author     = {George Luger and William Stubblefield},
>       publisher  = {Benjamin-Cummings},
>       year       = 1989,
>       ISBN       = 0805301399
>     }
>
> - has a chapter on LISP. One of the first things
> they mention is `eval', and they mention it in
> connection to the `quote', eval "undoing" quote so you
> get the feeling it is as indispensible. There are
> several examples using it.

Without lexical binding, there's no other environment than the global
environment, so it works better:

    (setf lexical-binding nil)

    (let ((x 42))
      (eval 'x)) 
    --> 42

Old lisp didn't have lexical binding (the famous funarg problem), and
this is why eval could have been more useful then.

But once lexical bindings were introduced in scheme and in Common Lisp,
and now in emacs lisp, you cannot be so lenient with eval.


What this means for the modern (emacs or Common) lisper?  That you
should take old lisp code that uses eval with some precautions, such as,
using (setf lexical-binding nil) or making sure that all the variables
are declared special.

See for example, the definition of the DEFINE macro in:
http://www.informatimago.com/develop/lisp/com/informatimago/small-cl-pgms/wang.html
which declares all the variables with DEFPARAMETER, hence declaiming
them to be special and of the dynamic binding persuasion.


> Their other LISP isn't that good either by the way.
> There are several examples where they do (car l)
> several times in one execution branch instead of
> `let'ing it be a local identifier;

It should not be a problem, at that time, or nowadays.  In the old days,
car and cdr were quite the optimized instructions: they corresponded to
7090 machine instructions, or to lisp machine instructions, so calling
(car x) several times was probably faster than storing the result in a
variable or even a register (because of the possible register spilling)
and calling it up again.

And nowadays, with honest compilers performing some common subexpression
elimination optimization, it should compile to exactly the same.



In the case of ccl, the code is quite similar, but indeed
(car x) (car x) will hit the (cache) memory each time, recomputing
the offset (assumedly in the pipeline so at zero cost) each time, while
using a temporary variable saves it in a register.

cl-user> (disassemble (compile nil (lambda (x) (list (car x) (car x) (car x)))))
L0
    (leaq (@ (:^ L0) (% rip)) (% fn))       ;     [0]
    (pushq (% rbp))                         ;     [7]
    (movq (% rsp) (% rbp))                  ;     [8]
    (pushq (% save0))                       ;    [11]
    (movq (% arg_z) (% save0))              ;    [13]
    (pushq (@ 5 (% save0)))                 ;    [16]
    (pushq (@ 5 (% save0)))                 ;    [20]
    (pushq (@ 5 (% save0)))                 ;    [24]
    (movl ($ 24) (% nargs))                 ;    [28]
    (leaq (@ (:^ L53) (% fn)) (% temp2))    ;    [33]
    (nop)                                   ;    [40]
    (nop)                                   ;    [43]
    (jmpq (@ .SPCONSLIST))                  ;    [46]
L53
    (leaq (@ (:^ L0) (% rip)) (% fn))       ;    [53]
    (popq (% save0))                        ;    [60]
    (leaveq)                                ;    [62]
    (retq)                                  ;    [63]
nil
cl-user> (disassemble (compile nil (lambda (x) (let ((y (car x))) (list y y 
y)))))
L0
    (leaq (@ (:^ L0) (% rip)) (% fn))       ;     [0]
    (pushq (% rbp))                         ;     [7]
    (movq (% rsp) (% rbp))                  ;     [8]
    (pushq (% arg_z))                       ;    [11]
    (pushq (% save0))                       ;    [12]
    (movq (@ 5 (% arg_z)) (% save0))        ;    [14]
    (pushq (% save0))                       ;    [18]
    (pushq (% save0))                       ;    [20]
    (pushq (% save0))                       ;    [22]
    (movl ($ 24) (% nargs))                 ;    [24]
    (leaq (@ (:^ L45) (% fn)) (% temp2))    ;    [29]
    (nop)                                   ;    [36]
    (jmpq (@ .SPCONSLIST))                  ;    [38]
L45
    (leaq (@ (:^ L0) (% rip)) (% fn))       ;    [45]
    (popq (% save0))                        ;    [52]
    (leaveq)                                ;    [54]
    (retq)                                  ;    [55]
nil
cl-user> (optimization)
(optimize (safety 0) (debug 0) (speed 3) (space 3) (compilation-speed 1))


But in the case of sbcl, it compiles to the exact same instructions
(the only difference being in the procedure entry, probably allocating
some space on the stack that is left unused in the let case).


diff -c /tmp/b /tmp/a
*** /tmp/b      Fri Jul 17 03:29:50 2015
--- /tmp/a      Fri Jul 17 03:29:56 2015
***************
*** 1,10 ****
! * (disassemble (compile nil (lambda (x) (list (car x) (car x) (car x)))))
  
  ; disassembly for (LAMBDA (X))
         488B4AF9         MOV RCX, [RDX-7]           ; no-arg-parsing entry 
point
-        488B7AF9         MOV RDI, [RDX-7]
-        488B72F9         MOV RSI, [RDX-7]
         488BD1           MOV RDX, RCX
         49896C2440       MOV [R12+64], RBP
         4D8B5C2418       MOV R11, [R12+24]
         498D5B30         LEA RBX, [R11+48]
--- 1,10 ----
! * (disassemble (compile nil (lambda (x) (let ((y (car x))) (list y y y)))))
  
  ; disassembly for (LAMBDA (X))
         488B4AF9         MOV RCX, [RDX-7]           ; no-arg-parsing entry 
point
         488BD1           MOV RDX, RCX
+        488BF9           MOV RDI, RCX
+        488BF1           MOV RSI, RCX
         49896C2440       MOV [R12+64], RBP
         4D8B5C2418       MOV R11, [R12+24]
         498D5B30         LEA RBX, [R11+48]
***************
*** 36,38 ****
--- 36,39 ----
         488D5B07         LEA RBX, [RBX+7]
         EBB3             JMP L0
  NIL
+ * 

Diff finished.  Fri Jul 17 03:30:00 2015


* (disassemble (compile nil (lambda (x) (list (car x) (car x) (car x)))))

; disassembly for (LAMBDA (X))
; 02AB631F:       488B4AF9         MOV RCX, [RDX-7]           ; no-arg-parsing 
entry point
;       23:       488B7AF9         MOV RDI, [RDX-7]
;       27:       488B72F9         MOV RSI, [RDX-7]
;       2B:       488BD1           MOV RDX, RCX
;       2E:       49896C2440       MOV [R12+64], RBP
;       33:       4D8B5C2418       MOV R11, [R12+24]
;       38:       498D5B30         LEA RBX, [R11+48]
;       3C:       49395C2420       CMP [R12+32], RBX
;       41:       7642             JBE L2
;       43:       49895C2418       MOV [R12+24], RBX
;       48:       498D5B07         LEA RBX, [R11+7]
;       4C: L0:   488BC3           MOV RAX, RBX
;       4F:       488950F9         MOV [RAX-7], RDX
;       53:       4883C010         ADD RAX, 16
;       57:       488940F1         MOV [RAX-15], RAX
;       5B:       488978F9         MOV [RAX-7], RDI
;       5F:       4883C010         ADD RAX, 16
;       63:       488940F1         MOV [RAX-15], RAX
;       67:       488970F9         MOV [RAX-7], RSI
;       6B:       48C7400117001020 MOV QWORD PTR [RAX+1], 537919511
;       73:       49316C2440       XOR [R12+64], RBP
;       78:       7402             JEQ L1
;       7A:       CC09             BREAK 9                    ; pending 
interrupt trap
;       7C: L1:   488BD3           MOV RDX, RBX
;       7F:       488BE5           MOV RSP, RBP
;       82:       F8               CLC
;       83:       5D               POP RBP
;       84:       C3               RET
;       85: L2:   6A30             PUSH 48
;       87:       4C8D1C2570724200 LEA R11, [#x427270]        ; alloc_tramp
;       8F:       41FFD3           CALL R11
;       92:       5B               POP RBX
;       93:       488D5B07         LEA RBX, [RBX+7]
;       97:       EBB3             JMP L0
NIL
* (disassemble (compile nil (lambda (x) (let ((y (car x))) (list y y y)))))

; disassembly for (LAMBDA (X))
; 02B12EAF:       488B4AF9         MOV RCX, [RDX-7]           ; no-arg-parsing 
entry point
;      EB3:       488BD1           MOV RDX, RCX
;      EB6:       488BF9           MOV RDI, RCX
;      EB9:       488BF1           MOV RSI, RCX
;      EBC:       49896C2440       MOV [R12+64], RBP
;      EC1:       4D8B5C2418       MOV R11, [R12+24]
;      EC6:       498D5B30         LEA RBX, [R11+48]
;      ECA:       49395C2420       CMP [R12+32], RBX
;      ECF:       7642             JBE L2
;      ED1:       49895C2418       MOV [R12+24], RBX
;      ED6:       498D5B07         LEA RBX, [R11+7]
;      EDA: L0:   488BC3           MOV RAX, RBX
;      EDD:       488950F9         MOV [RAX-7], RDX
;      EE1:       4883C010         ADD RAX, 16
;      EE5:       488940F1         MOV [RAX-15], RAX
;      EE9:       488978F9         MOV [RAX-7], RDI
;      EED:       4883C010         ADD RAX, 16
;      EF1:       488940F1         MOV [RAX-15], RAX
;      EF5:       488970F9         MOV [RAX-7], RSI
;      EF9:       48C7400117001020 MOV QWORD PTR [RAX+1], 537919511
;      F01:       49316C2440       XOR [R12+64], RBP
;      F06:       7402             JEQ L1
;      F08:       CC09             BREAK 9                    ; pending 
interrupt trap
;      F0A: L1:   488BD3           MOV RDX, RBX
;      F0D:       488BE5           MOV RSP, RBP
;      F10:       F8               CLC
;      F11:       5D               POP RBP
;      F12:       C3               RET
;      F13: L2:   6A30             PUSH 48
;      F15:       4C8D1C2570724200 LEA R11, [#x427270]        ; alloc_tramp
;      F1D:       41FFD3           CALL R11
;      F20:       5B               POP RBX
;      F21:       488D5B07         LEA RBX, [RBX+7]
;      F25:       EBB3             JMP L0
NIL
* 



In the case of emacs, being an implementation targetting a lisp machine
VM, the multiple (cdr x) version looks definitely more optimized (less
VM instructions), as expected.

(disassemble (byte-compile (lambda (x) (let ((y (car x))) (list y y y)))))
byte code:
  args: (x)
0       varref    x
1       car       
2       dup       
3       varbind   y
4       dup       
5       varref    y
6       list3     
7       unbind    1
8       return    

(disassemble (byte-compile (lambda (x) (list (car x) (car x) (car x)))))
byte code:
  args: (x)
0       varref    x
1       car       
2       varref    x
3       car       
4       varref    x
5       car       
6       list3     
7       return    



> and, they speak
> appreciatively of all the different types of recursion
> (tail etc.) but at least so far hasn't mentioned (and
> will they?) anything of the drawbacks of recursion in
> terms of efficiency. (When I started out with Lisp,
> coming "closest" from SML of the languages I did
> then, I did recursion all the time by the way.)

Again, if you have tail call optimization, then there's no recursion
occuring, and efficiency is equivalent to iteration (because in effect,
the compiler generates an iteration).

Of course, CL implementations and emacs lisp don't necessarily implement
TCO, so recursion could be less efficient.  But as long as response
times are below the 300 ms threshold, it's ok. ;-)

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk