How to mapcar or across a list?

How to mapcar or across a list?

[Marcin Borkowski]

Hi there,

so here's my problem: I have a list of Boolean values, and I want to
`mapcar' an `or' across it (IOW, I want to test whether at least one of
them is true).  Of course, (apply #'or my-list) does not work.  Of
course, I can (cl-reduce (lambda (x y) (or x y)) my-list) -- but is
there a better method?

BTW, my-list doesn't really exist: it is a result of `mapcar'ing
a function taking some value and yielding a Boolean value, so bonus
points if the method does not process the whole list.

(Note: I just noticed that my-list is in fact sorted so that all true
values (if any) will occur at the beginning anyway, so I can just test
the first one.  This means that my problem is purely academic, though
still interesting, I guess.)

Best,

-- 
Marcin Borkowski
http://octd.wmi.amu.edu.pl/en/Marcin_Borkowski
Faculty of Mathematics and Computer Science
Adam Mickiewicz University

Re: How to mapcar or across a list?

[Rasmus]

Marcin Borkowski <mbork@mbork.pl> writes:

> Hi there,
>
> so here's my problem: I have a list of Boolean values, and I want to
> `mapcar' an `or' across it (IOW, I want to test whether at least one of
> them is true).  Of course, (apply #'or my-list) does not work.  Of
> course, I can (cl-reduce (lambda (x y) (or x y)) my-list) -- but is
> there a better method?
>
> BTW, my-list doesn't really exist: it is a result of `mapcar'ing
> a function taking some value and yielding a Boolean value, so bonus
> points if the method does not process the whole list.

Does cl-some and cl-every fit the bill?

Rasmus

-- 
Vote for Dick Taid in an election near you!

Re: How to mapcar or across a list?

[Marcin Borkowski]

On 2015-07-15, at 22:42, Rasmus <rasmus@gmx.us> wrote:

> Marcin Borkowski <mbork@mbork.pl> writes:
>
>> Hi there,
>>
>> so here's my problem: I have a list of Boolean values, and I want to
>> `mapcar' an `or' across it (IOW, I want to test whether at least one of
>> them is true).  Of course, (apply #'or my-list) does not work.  Of
>> course, I can (cl-reduce (lambda (x y) (or x y)) my-list) -- but is
>> there a better method?
>>
>> BTW, my-list doesn't really exist: it is a result of `mapcar'ing
>> a function taking some value and yielding a Boolean value, so bonus
>> points if the method does not process the whole list.
>
> Does cl-some and cl-every fit the bill?

Ha.  Their only drawback is that I didn't know about them...

> Rasmus

Thanks!

-- 
Marcin Borkowski
http://octd.wmi.amu.edu.pl/en/Marcin_Borkowski
Faculty of Mathematics and Computer Science
Adam Mickiewicz University

Re: How to mapcar or across a list?

[Emanuel Berg]

Marcin Borkowski <mbork@mbork.pl> writes:

> so here's my problem: I have a list of Boolean
> values, and I want to `mapcar' an `or' across it
> (IOW, I want to test whether at least one of them is
> true). Of course, (apply #'or my-list) does not
> work. Of course, I can (cl-reduce (lambda (x y) (or
> x y)) my-list) -- but is there a better method?

"Better" I don't know, but how about using your
new-found skills with the backquote? (`or' itself
should be used, of course.)

    (setq boolean-list-1 '(t   nil nil nil t   nil nil))
    (setq boolean-list-2 '(nil nil nil nil nil nil nil))

    (eval `(or ,@boolean-list-1)) ; t
    (eval `(or ,@boolean-list-2)) ; nil

> BTW, my-list doesn't really exist: it is a result of
> `mapcar'ing a function taking some value and
> yielding a Boolean value, so bonus points if the
> method does not process the whole list.

Check. It is a consequence of using `or', which is
"short circuited" as it is called in other languages,
perhaps in Lisp too - I've read
"conditional evaluation" as well in AI books, but
perhaps that is something else.

Anyway:

    (or t undefined) ; t
    (or undefined t) ; error: (void-variable undefined) in eval

To verify, append "undefined" to "boolean-list-1"
(no error) - but, there will be an error (the same as
above) if appended to "boolean-list-2"!

... I suppose now would be a good time for you to hand
over them points!

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: How to mapcar or across a list?

[John Mastro]

> so here's my problem: I have a list of Boolean values, and I want to
> `mapcar' an `or' across it (IOW, I want to test whether at least one of
> them is true).  Of course, (apply #'or my-list) does not work.  Of
> course, I can (cl-reduce (lambda (x y) (or x y)) my-list) -- but is
> there a better method?

You've already gotten good answers from others but, for the sake of one
more option, you could also accomplish this with `cl-loop' (which, of
course, some love and some hate).

It would end up looking something like:

(cl-loop for item in list
         thereis (your-predicate item))

If the predicate would be `(not (null item))', you can drop it entirely
(as you would expect):

(cl-loop for item in list thereis item)

-- 
john

Re: How to mapcar or across a list?

[Pascal J. Bourguignon]

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

> Marcin Borkowski <mbork@mbork.pl> writes:
>
>> so here's my problem: I have a list of Boolean
>> values, and I want to `mapcar' an `or' across it
>> (IOW, I want to test whether at least one of them is
>> true). Of course, (apply #'or my-list) does not
>> work. Of course, I can (cl-reduce (lambda (x y) (or
>> x y)) my-list) -- but is there a better method?
>
> "Better" I don't know, but how about using your
> new-found skills with the backquote? (`or' itself
> should be used, of course.)
>
>     (setq boolean-list-1 '(t   nil nil nil t   nil nil))
>     (setq boolean-list-2 '(nil nil nil nil nil nil nil))
>
>     (eval `(or ,@boolean-list-1)) ; t
>     (eval `(or ,@boolean-list-2)) ; nil

Nope.  

It's always a bad idea to use eval, because eval evalutes in the nil
environment, not in the local lexical envrionment.

Your example works because those lists are literal, but then you don't
need or to know the answer.

In pratice, translating:

   (flet ((some-complex-predicate (x) …))
     (let ((some-data (generate-some-data)))
        (some (function some-complex-predicate) some-data)))

to:

   (flet ((some-complex-predicate (x) …))
     (let ((some-data (generate-some-data)))
       (eval `(or ,@(mapcar (lambda (data)
                               `(some-complex-predicate ',data))
                            some-data)))))

fails lamentably.  

It is also very slow, since it makes you build a new list,
and it makes you interpret, or worse, compile, some new code!

-- 
__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

Re: How to mapcar or across a list?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> It's always a bad idea to use eval, because eval
> evalutes in the nil environment, not in the local
> lexical envrionment.
>
> Your example works because those lists are literal,
> but then you don't need or to know the answer.

OK, what about doing `cl-dolist' which we also had in
a recent discussion?

    (cl-dolist (b boolean-list-1) (when b (cl-return t))) ; t
    (cl-dolist (b boolean-list-2) (when b (cl-return t))) ; nil

-- 
underground experts united
http://user.it.uu.se/~embe8573

never use `eval' (was: Re: How to mapcar or across a list?)

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> It's always a bad idea to use eval, because eval
> evalutes in the nil environment, not in the local
> lexical envrionment.

I have used `eval' eight times in my current setup of
75 files.

Tho some of this code I wrote several years ago, I'd
be happy to correct it. Any hints - general or
specific - are appreciated.

;; From: http://user.it.uu.se/~embe8573/conf/emacs-init/faces.el

(defun set-color-face (name front &optional bold back)
  (eval `(defvar ,(make-symbol name)))
  (eval `(setq ,(intern name)
               `((t (:foreground ,front
                     :background ,back
                     :bold       ,bold) )))))

(defvar cf-black)   (set-color-face "cf-black"   "black")
(defvar cf-red)     (set-color-face "cf-red"     "red")
;; ...

;; From: http://user.it.uu.se/~embe8573/conf/emacs-init/ide/lisp.el

(defun do-repeat-complex-command ()
  (interactive)
  (eval (car command-history) ))

;; From: http://user.it.uu.se/~embe8573/conf/emacs-init/isbn.el

(defun book-page-to-bibtex ()
  (interactive)
  (save-excursion
    (goto-char (point-min))
    (let ((title (get-title))
          (data  (mapcar 'key-value
                         '("authors?" "publisher" "published" "isbn-10")) ))
      (eval `(create-book nil ,title ,@data) )))) ; don't INSERT

;; From: http://user.it.uu.se/~embe8573/conf/emacs-init/match-data-format.el

(defun match-data-format (data match format-str)
  (save-match-data
    (string-match match data)
    (eval `(message format-str ,@(make-match-list 1 data) ))))

;; From: http://user.it.uu.se/~embe8573/conf/emacs-init/wrap-search.el

(defun wrap-search-again (prefix)
  "Search again for the most recent search string of `wrap-search'.
Use \\[universal-argument] \(to set the PREFIX\) to toggle case sensitiveness."
  (interactive "p")
  (let ((cmd (cl-dolist (cmd command-history)
               (if (and (eq (car cmd) 'wrap-search)
                        (not (string= (cl-caddr cmd) "")) )
                   (cl-return cmd) ))))
    (if cmd
        (if (eq prefix 4)
            (let*((old-prefix (cadr  cmd))
                  (search-str (cl-caddr cmd))
                  (new-prefix (if (eq old-prefix 4) 1 4))
                  (final-cmd  `(wrap-search ,new-prefix ,search-str)) )
              (setq command-history (cons final-cmd command-history))
              (eval final-cmd) )
          (eval cmd) )
      (message " No previous search.") )))

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: never use `eval' (was: Re: How to mapcar or across a list?)

[John Mastro]

> Tho some of this code I wrote several years ago, I'd
> be happy to correct it. Any hints - general or
> specific - are appreciated.

> (defun set-color-face (name front &optional bold back)
>   (eval `(defvar ,(make-symbol name)))
>   (eval `(setq ,(intern name)
>                `((t (:foreground ,front
>                      :background ,back
>                      :bold       ,bold) )))))
>
> (defvar cf-black)   (set-color-face "cf-black"   "black")
> (defvar cf-red)     (set-color-face "cf-red"     "red")

I would use something like this:

(defmacro define-color-face (name front &optional bold back)
  `(defvar ,name
     (quote ((t (:foreground ,front
                             :background ,back
                             :bold ,bold))))))

(define-color-face cf-black "black")

> (defun book-page-to-bibtex ()
>   (interactive)
>   (save-excursion
>     (goto-char (point-min))
>     (let ((title (get-title))
>           (data  (mapcar 'key-value
>                          '("authors?" "publisher" "published" "isbn-10")) ))
>       (eval `(create-book nil ,title ,@data) )))) ; don't INSERT

For this (and others like it) it looks like you could instead simply
use e.g. (apply #'create-book nil title data)

-- 
john

Re: never use `eval' (was: Re: How to mapcar or across a list?)

[Emanuel Berg]

John Mastro <john.b.mastro@gmail.com> writes:

> I would use something like this:
>
> (defmacro ...

Macros never liked me, and that is mutual. Are they
really preferrable to `eval'?

> For this (and others like it)

... which are? Do you mean the eval + backquote combo?

> it looks like you could instead simply use e.g.
> (apply #'create-book nil title data)

This is what it looks like:

    (eval `(create-book nil ,title ,@data))

With `apply', won't the last "data" be a list, i.e.

    (a b ... n)

instead of

    a b ... n

?

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: never use `eval' (was: Re: How to mapcar or across a list?)

[John Mastro]

>> I would use something like this:
>>
>> (defmacro ...
>
> Macros never liked me, and that is mutual. Are they
> really preferrable to `eval'?

Yes, I think so. I certainly don't see any advantages to `eval' where a
function or macro would work.

> This is what it looks like:
>
>     (eval `(create-book nil ,title ,@data))
>
> With `apply', won't the last "data" be a list, i.e.
>
>     (a b ... n)
>
> instead of
>
>     a b ... n

No, that's `funcall'. For example, these both evaluate to 6:

(apply #'+ '(1 2 3))
(apply #'+ 1 2 '(3))

-- 
john

Re: never use `eval' (was: Re: How to mapcar or across a list?)

[Barry Margolin]

In article <mailman.6984.1437004760.904.help-gnu-emacs@gnu.org>,
 Emanuel Berg <embe8573@student.uu.se> wrote:

> John Mastro <john.b.mastro@gmail.com> writes:
> 
> > I would use something like this:
> >
> > (defmacro ...
> 
> Macros never liked me, and that is mutual. Are they
> really preferrable to `eval'?
> 
> > For this (and others like it)
> 
> ... which are? Do you mean the eval + backquote combo?
> 
> > it looks like you could instead simply use e.g.
> > (apply #'create-book nil title data)
> 
> This is what it looks like:
> 
>     (eval `(create-book nil ,title ,@data))
> 
> With `apply', won't the last "data" be a list, i.e.
> 
>     (a b ... n)
> 
> instead of
> 
>     a b ... n
> 
> ?

No. apply spreads its last argument. You're thinking of funcall.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Re: never use `eval' (was: Re: How to mapcar or across a list?)

[Barry Margolin]

In article <mailman.6982.1437001117.904.help-gnu-emacs@gnu.org>,
 Emanuel Berg <embe8573@student.uu.se> wrote:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
> 
> > It's always a bad idea to use eval, because eval
> > evalutes in the nil environment, not in the local
> > lexical envrionment.
> 
> I have used `eval' eight times in my current setup of
> 75 files.
> 
> Tho some of this code I wrote several years ago, I'd
> be happy to correct it. Any hints - general or
> specific - are appreciated.
> 
> ;; From: http://user.it.uu.se/~embe8573/conf/emacs-init/faces.el
> 
> (defun set-color-face (name front &optional bold back)
>   (eval `(defvar ,(make-symbol name)))
>   (eval `(setq ,(intern name)
>                `((t (:foreground ,front
>                      :background ,back
>                      :bold       ,bold) )))))

(eval `(setq ,<expr> <val>))

can practically always be replaced with:

(setf (symbol-value <expr>) <val>)

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Re: never use `eval' (was: Re: How to mapcar or across a list?)

[Emanuel Berg]

Barry Margolin <barmar@alum.mit.edu> writes:

>> (defun set-color-face (name front &optional bold
>> back) (eval `(defvar ,(make-symbol name))) (eval
>> `(setq ,(intern name) `((t (:foreground ,front
>> :background ,back :bold ,bold) )))))
>
> (eval `(setq ,<expr> <val>))
>
> can practically always be replaced with:
>
> (setf (symbol-value <expr>) <val>)

Aha, that one! Got it. Please ignore previous question
which one is "eval setq".

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: never use `eval' (was: Re: How to mapcar or across a list?)

[Emanuel Berg]

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":

    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.

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.

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; 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.)

-- 
underground experts united
http://user.it.uu.se/~embe8573

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

Re: never use `eval'

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> 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.

Yeah, it is more a question of the code not looking
good and being difficult to work with, say for example
if the data item that once was (car l) changes - you
have to change all them places. You can do
search-and-replace but then you better catch them all
and since it is such a common thing you might catch
some unwanted fish in the bargain/net as well.

I don't really care about speed as such, but of course
I want to write efficient code. Still computers have
always been always fast enough for me, and I have used
old computers (5-10 years) all my "career". What I do
don't require speed it would seem and besides I don't
think I'm that slow just because I don't disassemble
code to compare which is preferable. I'm on the human
side of the equation. I can't even say how many cache
levels my architecture has. OK, 'lscpu' tells me
three, but you know what I'm saying.

> 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.

"ccl" I don't know.

> 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).

Steel Bank Common Lisp!

    (defvar inferior-lisp-program)
    (setq inferior-lisp-program "/usr/bin/sbcl --noinform")

Did the US steel industry have a bank, which had its
own a dialect of LISP? Crazy times... Probably a lot
of job opportunities for real programmers in
those days.

> 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).

I do like some recursion which uses one function
(itself) and do recursion there. This recursion
pattern is cool:

    * empty list - nil
    * not empty list - do something with car
                     - do it again with cdr

The recursion I don't like is recursion which relies
on helper functions and "accumulator" variables and
the like - them arguments should be input data, not
"persistent variables" to carry state
between invocations.

Some recursion can be with an infix operator and then
do recursion divide-and-conquer both ways down
searching a tree, then leading up to the operands of
the function. It looks cool to be sure.

But the coolest search algorithm I've seen is
"candidate elimination" which searches search space
two ways, from the general to the specific, and
simultaneously, form the specific to the general, and
where they meet is the answer (no nodes left to go to
but to stay put).

This reminds me of what happened once in the FOSS
world when there was a non-free component of KDE,
namely Qt (pronounced "cute"?) - to counterpunch this,
two projects were launched: GNOME, to replace KDE -
i.e., the general approach; and, Harmony to replace Qt
(the specific). The end of the story is GNOME was
succesful (still not to my liking, but I don't like
the desktop at all); Harmony was dropped (?); and, Qt
turned free. It is just the way of the street. In
100 years the same thing will happen and people will
be angry and creative about it. Then and now and in
the future, the only thing bigger than the grievance
is the mirth.

> 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. ;-)

Right. When the carpenter applies sandpaper to a piece
of wood, he doesn't think a person will get stuck by
every single chip he removes. But if he didn't do it
at all, and used the plank to lay a floor, the
shoe-less hippies and their dogs would cry out their
spits and angers...

"If everything can start anew, then everything
must continue."

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: never use `eval'

[Barry Margolin]

In article <87d1zrlfz6.fsf@kuiper.lan.informatimago.com>,
 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote:

> 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)

I don't think that could be expected to work. Since eval is a function, 
not a special form, there's no way it can access the lexical environment 
outside it. I assume the LEXICAL parameter means that it implements 
lexical binding in the code being evaluated, e.g. if you do:

(eval '(let ((x 42)) x) t)

it binds x lexically, not dynamically.

But it also says that LEXICAL can be an alist, so you could do:

(eval 'x '((x . 42)))

and it should return 42.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Re: never use `eval'

[Pascal J. Bourguignon]

Barry Margolin <barmar@alum.mit.edu> writes:

> In article <87d1zrlfz6.fsf@kuiper.lan.informatimago.com>,
>  "Pascal J. Bourguignon" <pjb@informatimago.com> wrote:
>> 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)
>
> I don't think that could be expected to work. Since eval is a function, 
> not a special form, there's no way it can access the lexical environment 
> outside it. I assume the LEXICAL parameter means that it implements 
> lexical binding in the code being evaluated, e.g. if you do:
>
> (eval '(let ((x 42)) x) t)
>
> it binds x lexically, not dynamically.
>
> But it also says that LEXICAL can be an alist, so you could do:
>
> (eval 'x '((x . 42)))
>
> and it should return 42.

Oh!  I see…  

This is nice, to be able to pass an environment like this, because we
could write macros that would build a "lexical environment" to be passed
to eval…


-- 
__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

Re: never use `eval'

[Pascal J. Bourguignon]

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

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>> It's always a bad idea to use eval, because eval
>> evalutes in the nil environment, not in the local
>> lexical envrionment.
>
> I have used `eval' eight times in my current setup of
> 75 files.
>
> Tho some of this code I wrote several years ago, I'd
> be happy to correct it. Any hints - general or
> specific - are appreciated.
>
> ;; From: http://user.it.uu.se/~embe8573/conf/emacs-init/faces.el
>
> (defun set-color-face (name front &optional bold back)
>   (eval `(defvar ,(make-symbol name)))
>   (eval `(setq ,(intern name)
>                `((t (:foreground ,front
>                      :background ,back
>                      :bold       ,bold) )))))

As mentionned, eval setq can be replaced by (setf symbol-value) or even
set, if you like archaic forms.

For defvar, and in general for operations like this set-color-face that
_defines_ a symbol to bind it to some kind of object, what you should do
is to write a define macro instead.  

Also, your code is higly suspicious: why do you use make-symbol?  This
will create a _different_ symbol!

     (eq (make-symbol "x") (intern "x")) --> nil

therefore your defvar will be totally useless!

Instead, you can just give a symbol to the macro.

    (defmacro define-color-face (name front &optional bold back)
       `(progn
          (defvar ,name)
          (setq ,name '((t (:foreground ,front
                            :background ,back
                            :bold ,bold))))))

    (define-color-face cf-black "black")
    cf-black --> ((t (:foreground "black" :background nil :bold nil)))



> (defun do-repeat-complex-command ()
>   (interactive)
>   (eval (car command-history) ))

This use is acceptable.


> ;; From: http://user.it.uu.se/~embe8573/conf/emacs-init/isbn.el
>
> (defun book-page-to-bibtex ()
>   (interactive)
>   (save-excursion
>     (goto-char (point-min))
>     (let ((title (get-title))
>           (data  (mapcar 'key-value
>                          '("authors?" "publisher" "published" "isbn-10")) ))
>       (eval `(create-book nil ,title ,@data) )))) ; don't INSERT

Just use apply!  

        (apply (function create-book) nil title data)


> ;; From: http://user.it.uu.se/~embe8573/conf/emacs-init/match-data-format.el
>
> (defun match-data-format (data match format-str)
>   (save-match-data
>     (string-match match data)
>     (eval `(message format-str ,@(make-match-list 1 data) ))))

Use apply.


> ;; From: http://user.it.uu.se/~embe8573/conf/emacs-init/wrap-search.el
>
> (defun wrap-search-again (prefix)
>   "Search again for the most recent search string of `wrap-search'.
> Use \\[universal-argument] \(to set the PREFIX\) to toggle case sensitiveness."
>   (interactive "p")
>   (let ((cmd (cl-dolist (cmd command-history)
>                (if (and (eq (car cmd) 'wrap-search)
>                         (not (string= (cl-caddr cmd) "")) )
>                    (cl-return cmd) ))))
>     (if cmd
>         (if (eq prefix 4)
>             (let*((old-prefix (cadr  cmd))
>                   (search-str (cl-caddr cmd))
>                   (new-prefix (if (eq old-prefix 4) 1 4))
>                   (final-cmd  `(wrap-search ,new-prefix ,search-str)) )
>               (setq command-history (cons final-cmd command-history))
>               (eval final-cmd) )

Use apply.

>           (eval cmd) )

Ok for eval.

>       (message " No previous search.") )))


Notice:

    command-history is a variable defined in `C source code'.
    Its value is shown below.

    Documentation:
    List of recent commands that read arguments from terminal.
    Each command is represented as a form to evaluate.

So clearly, (eval (first command-history)) is vetted.


-- 
__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

Re: never use `eval'

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> As mentioned, eval setq can be replaced by (setf
> symbol-value) or even set, if you like
> archaic forms.

Do I? Or do you? What do you mean?

But: which case is "eval setq"? From reading your
post, there are two OK uses, one that should be
a macro, and the rest `apply'?

> For defvar, and in general for operations like this
> set-color-face that _defines_ a symbol to bind it to
> some kind of object, what you should do is to write
> a define macro instead.

OK, thanks to all of you!

*Define* is exactly what I wanted to do, but I didn't
succeed and that is the reason for all those `defvars'
in the original code. The line you mentioned is
probably a leftover from an attempt to not have to
have those. Ironically, instead the macro is exactly
what I needed to not have to have them.

Now it looks ten times better:

    http://user.it.uu.se/~embe8573/conf/emacs-init/faces.el

> Notice:
>
>     command-history is a variable defined in `C source
>     code'. Its value is shown below.
>
>     Documentation: List of recent commands that read
>     arguments from terminal. Each command is represented
>     as a form to evaluate.
>
> So clearly, (eval (first command-history))
> is vetted.

I see: the other `eval' that is also "vetted" also
stems from `command-history'.

-- 
underground experts united
http://user.it.uu.se/~embe8573