speed of let vs. let*

[Mike]

I understand that the order of variables set in let is implementation
dependent and the order of variables in let* proceeds from the first
varable to the last. It seems that for my (simple) projects that I can
get a lot of the defun's work done in the let* initialization part if
I use let*.

Is let faster than let* since let does not have to be concerned with
initialization order?

Mike

[Barry Margolin]

Evaluation order is left to right in LET. From
http://www.lispworks.com/documentation/HyperSpec/Body/s_let_l.htm#let

"evaluates the expressions init-form-1, init-form-2, and so on, in that
order, saving the resulting values"

The only difference between them is the environment in which each form
is evaluated: LET evaluates each form in the original environment, LET*
evaluates each form in an environment containing the preceding bindings.
With any decent compiler, there should be little or no performance
difference.

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

[Pascal J. Bourguignon]

Theorically, LET initialization expressions could be evaluated in
parallel, but they can still have dependencies if they have side
effects, that would prevent parallelizing them. In any case, it's very
fine grained parallelism (at the level of simple expressions, (all
right, you might also call big functions, but with big functions come
big side effects and therefore less possibility of parallelizing
evaluation).


So in practice,

(shadow 'let)
(defmacro let (bindings &body body)
`((lambda ,(mapcar (lambda (binding)
(if (atom binding) binding (first binding)))
bindings)
,@body)
,@(mapcar (lambda (binding)
(if (atom binding) 'nil (second binding)))
bindings)))


(macroexpand '(let ((a (incf i)) (b (incf i)) (c (incf i))) (list a b c))
--> ((lambda (a b c) (list a b c)) (incf i) (incf i) (incf i))


Now, for let*:

(shadown 'let*)
(defmacro let* (bindings &body body)
(if (null bindings)
`(progn ,@body)
`((lambda (,(if (atom (car bindings)) (car bindings) (caar bindings)))
(let* ,(cdr bindings) ,@body))
,(if (atom (car bindings)) 'nil (cadar bindings)))))

(ext:expand-form '(let* ((a 0) (b (1+ a)) (c (1+ b))) (list a b c)))
--> ((LAMBDA (A) ((LAMBDA (B) ((LAMBDA (C) (LIST A B C)) (1+ B))) (1+ A))) 0)



As for which one is faster, see for yourself, try to write forms
evaluating the same things, differing only in let vs. let*:


C/USER[12]> (disassemble (compile nil (lambda (a b) (let ((a 0) (b (1+ a)) (c (1+ b))) (list a b c)))))

Disassembly of function NIL
(CONST 0) = 0
2 required arguments
0 optional arguments
No rest parameter
No keyword parameters
7 byte-code instructions:
0 (LOAD&INC&PUSH 2)
2 (LOAD&INC&PUSH 2)
4 (CONST&PUSH 0) ; 0
5 (LOAD&PUSH 2)
6 (LOAD&PUSH 2)
7 (LIST 3)
9 (SKIP&RET 5)
NIL
C/USER[13]> (disassemble (compile nil (lambda () (let* ((a 0) (b (1+ a)) (c (1+ b))) (list a b c)))))

Disassembly of function NIL
(CONST 0) = 0
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
8 byte-code instructions:
0 (CONST&PUSH 0) ; 0
1 (CALLS2&PUSH 177) ; 1+
3 (LOAD&INC&PUSH 0)
5 (CONST&PUSH 0) ; 0
6 (LOAD&PUSH 2)
7 (LOAD&PUSH 2)
8 (LIST 3)
10 (SKIP&RET 3)
NIL
C/USER[14]>


--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

[Mike]

Thank you both. I'll look at the disassembly of my routines. I was thinking something like:

(defun parse (key line)
(let ((pattern (concatenate 'string "<start>" key "<end>"))
(match (regexp:match pattern line))
(val (subseq match (regexp:match-start match) (regexp:match-end match))))
val))

I thought the order is implementation dependent for let and therefore not something I should trust.

Mike

[Jussi Piitulainen]

Mike writes:

> [...] I was thinking something like:

>
> (defun parse (key line)
> (let ((pattern (concatenate 'string "<start>" key "<end>"))
> (match (regexp:match pattern line))
> (val (subseq match (regexp:match-start match)
(regexp:match-end match))))
> val))
>
> I thought the order is implementation dependent for let and
> therefore not something I should trust.

The occurrence of _pattern_ in the initializer of _match_ and the
three occurrences of _match_ in _val_ are not bound by that _let_.

[Kaz Kylheku]

If the code is being evaluated using abstract-syntax-tree interpretation,
and is not optimized in any way, let* may be conceivably slower, since
it has to construct multiple environments interleaved with the evaluation
of the forms. That also depends on how environments are implemented.
If the environment is just an assoc list, it hardly matters whether
it is consed up upfront or interleaved.

In compiled code, this should not matter. If the let* is used unnecessarily,
(the initialization forms do not refer to any of the bindings being set up),
it should ideally generate the same code as let.

--
If you ever need any coding done, I'm your goto man!

[WJ]

Jussi Piitulainen wrote:

> Mike writes:
>
> > [...] I was thinking something like:
> >
> > (defun parse (key line)
> > (let ((pattern (concatenate 'string "<start>" key "<end>"))
> > (match (regexp:match pattern line))
> > (val (subseq match (regexp:match-start match)
> (regexp:match-end match))))
> > val))
> >
> > I thought the order is implementation dependent for let and
> > therefore not something I should trust.
>

> The occurrence of pattern in the initializer of match and the
> three occurrences of match in val are not bound by that let.

Yes, Mike. Before you worry and fret about whether let is
faster than let*, you ought to learn what let does and what
let* does. You may be able to dredge up some text somewhere
that explains that. It may not be a closely guarded secret.
In fact, one would imagine that since let is a basic and
fundamental operator, it should be understood before an
attempt is made to employ things such as regexp:match.

Racket:

(define (parse key line)
(car (regexp-match (string-append "<start>" key "<end>") line)))

(parse "foo[a-z]+" "<start>fooing<end> we will go")
=> "<start>fooing<end>"

[Mike]

Thank you for your eloquent sarcasm.

Mike

[Norbert_Paul]

Mike might be talking about Scheme:

http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_idx_124

Norbert

Barry Margolin wrote:
> In article<jp0rhk$hui$1...@dont-email.me>, Mike<mi...@mac.com> wrote:
>
>> I understand that the order of variables set in let is implementation
>> dependent and the order of variables in let* proceeds from the first
>> varable to the last. It seems that for my (simple) projects that I can

...

>
> Evaluation order is left to right in LET. From
> http://www.lispworks.com/documentation/HyperSpec/Body/s_let_l.htm#let

...

[Barry Margolin]

In article <jp2r2j$obo$1...@dont-email.me>,

Norbert_Paul <norbertpau...@yahoo.com> wrote:

> Mike might be talking about Scheme:
>
> http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_idx
> _124

Except that he specifically mentioned "defun" in his OP. So maybe he
was assuming that CL is like Scheme in this regard.

>
> Norbert
>
> Barry Margolin wrote:
> > In article<jp0rhk$hui$1...@dont-email.me>, Mike<mi...@mac.com> wrote:
> >
> >> I understand that the order of variables set in let is implementation
> >> dependent and the order of variables in let* proceeds from the first
> >> varable to the last. It seems that for my (simple) projects that I can
> ...
> >
> > Evaluation order is left to right in LET. From
> > http://www.lispworks.com/documentation/HyperSpec/Body/s_let_l.htm#let
> ...

[Mike]

On 2012-05-17, Barry Margolin <bar...@alum.mit.edu> wrote:
> In article <jp2r2j$obo$1...@dont-email.me>,
> Norbert_Paul <norbertpau...@yahoo.com> wrote:
>
>> Mike might be talking about Scheme:
>>
>> http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_idx
>> _124
>
> Except that he specifically mentioned "defun" in his OP. So maybe he
> was assuming that CL is like Scheme in this regard.
>
>>
>> Norbert
>>
>> Barry Margolin wrote:
>> > In article<jp0rhk$hui$1...@dont-email.me>, Mike<mi...@mac.com> wrote:
>> >
>> >> I understand that the order of variables set in let is implementation
>> >> dependent and the order of variables in let* proceeds from the first
>> >> varable to the last. It seems that for my (simple) projects that I can
>> ...
>> >
>> > Evaluation order is left to right in LET. From
>> > http://www.lispworks.com/documentation/HyperSpec/Body/s_let_l.htm#let
>> ...
>

I am talking about Common Lisp. I'm using clisp. I infer by another
comment that when there are multiple things in a let, that all of the
things are avaiable once the initialization portion is complete and that
none of the things are available while initialization is happening. If
true, then my thought of using let* for sequential initialization is moot.

(defun x (y)
(let ((A 1)
(B (+ A 1)))
(+ A B)))

B will never see A because the initialization is happening and neither
are truely in scope until initialization is complete. Maybe let* is
necessary for side effects (and I'm not asking about side effects).

Again, thanks to everyone for helping me with my understanding of let
and let*.

Mike

[Jussi Piitulainen]

Mike writes:
...
> I am talking about Common Lisp. I'm using clisp. I infer by another
> comment that when there are multiple things in a let, that all of
> the things are avaiable once the initialization portion is complete
> and that none of the things are available while initialization is
> happening. If true, then my thought of using let* for sequential
> initialization is moot.
>
> (defun x (y)
> (let ((A 1)
> (B (+ A 1)))
> (+ A B)))
>
> B will never see A because the initialization is happening and
> neither are truely in scope until initialization is complete. Maybe
> let* is necessary for side effects (and I'm not asking about side
> effects).

Use let* for this. It's precisely what you want.

You can think of let* as nested lets. It optimizes indentation :)

[Kaz Kylheku]

On 2012-05-17, Mike <mi...@mac.com> wrote:
> On 2012-05-17, Barry Margolin <bar...@alum.mit.edu> wrote:
>> In article <jp2r2j$obo$1...@dont-email.me>,
>> Norbert_Paul <norbertpau...@yahoo.com> wrote:
>>
>>> Mike might be talking about Scheme:
>>>
>>> http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_idx
>>> _124
>>
>> Except that he specifically mentioned "defun" in his OP. So maybe he
>> was assuming that CL is like Scheme in this regard.
>>
>>>
>>> Norbert
>>>
>>> Barry Margolin wrote:
>>> > In article<jp0rhk$hui$1...@dont-email.me>, Mike<mi...@mac.com> wrote:
>>> >
>>> >> I understand that the order of variables set in let is implementation
>>> >> dependent and the order of variables in let* proceeds from the first
>>> >> varable to the last. It seems that for my (simple) projects that I can
>>> ...
>>> >
>>> > Evaluation order is left to right in LET. From
>>> > http://www.lispworks.com/documentation/HyperSpec/Body/s_let_l.htm#let
>>> ...
>>
>
> I am talking about Common Lisp. I'm using clisp. I infer by another

Speaking of which CLISP implements the standard function disassemble, like
other Common Lisps, so you can easily see what difference let* makes.

> comment that when there are multiple things in a let, that all of the
> things are avaiable once the initialization portion is complete and that
> none of the things are available while initialization is happening. If
> true, then my thought of using let* for sequential initialization is moot.
>
> (defun x (y)
> (let ((A 1)
> (B (+ A 1)))
> (+ A B)))
>
> B will never see A because the initialization is happening and neither
> are truely in scope until initialization is complete.

This is exactly what let* is for; so that the (A 1) binding is visible to the
the init form (+ A 1)

[Sam Steingold]

> * Mike <zv...@znp.pbz> [2012-05-17 16:51:23 +0000]:

>
> comment that when there are multiple things in a let, that all of the
> things are avaiable once the initialization portion is complete and that
> none of the things are available while initialization is happening. If
> true, then my thought of using let* for sequential initialization is moot.
>
> (defun x (y)
> (let ((A 1)
> (B (+ A 1)))
> (+ A B)))
>
> B will never see A because the initialization is happening and neither
> are truely in scope until initialization is complete. Maybe let* is
> necessary for side effects (and I'm not asking about side effects).

1. it pays to pay attention to compiler warnings:

(disassemble '(let ((a 1) (b (1+ a))) (+ a b)))
WARNING: in :LAMBDA : A is neither declared nor bound,
it will be treated as if it were declared SPECIAL.

Disassembly of function :LAMBDA
(CONST 0) = A
(CONST 1) = 1

0 required arguments
0 optional arguments
No rest parameter
No keyword parameters

reads special variable: A
6 byte-code instructions:
0 (GETVALUE&PUSH 0) ; A
2 (CALLS2&PUSH 177) ; 1+
4 (CONST&PUSH 1) ; 1
5 (LOAD&PUSH 1)
6 (CALLSR 2 55) ; +
9 (SKIP&RET 2)

i.e., the (1+ A) form does not know what A is.
there will be an error when you try to execute the code.

2. think of LET* as many nested LETs (just like in regexp: * means repeat).
exercise: compare
(disassemble '(let* ((a 1) (b (1+ a))) (+ a b)))
with
(disassemble '(let ((a 1)) (let ((b (1+ a))) (+ a b))))
and report any differences as bugs.

3. don't worry about speed yet. when you find that your code works well,
you can take a look at http://clisp.org/impnotes/bytecode.html and
especially at http://clisp.org/impnotes/byte-intro.html:

Execution speed of a program can easily be understood by looking at
the output of the DISASSEMBLE function. A rule of thumb is that every
elementary instruction costs 1 time unit, whereas a function call
costs 3 to 4 time units.



--
Sam Steingold (http://sds.podval.org/) on Ubuntu 12.04 (precise) X 11.0.11103000
http://www.childpsy.net/ http://americancensorship.org http://iris.org.il
http://pmw.org.il http://honestreporting.com http://dhimmi.com
The Truth does not have to look plausible.