Steel Bank Common Lisp

Jeff Cunningham <jeffrey@...> writes:

> According to the Hyperspec:
>
>     "let and let* create new variable bindings and execute a series of
>     forms that use these bindings. let performs the bindings in
>     parallel and let* does them sequentially. "
> I thought I knew what that meant until I tried to demonstrate it to
> myself. I wrote a simple function that eats cpu cycles for a visible
> period of time. Then I set up a let expression which I thought would
> evaluate these forms in parallel:
Parallel here is not related in any way to concurrency. Parallel means
that when one binding is established, the other isn't yet. And
sequential means that they are assigned one by one, so that just
established binding will be visible to all the following binding forms.

Compare
(let ((a 20))
  (let* ((a 10)
         (b a))
    b))

and

(let ((a 20))
  (let ((a 10)
        (b a))
    b))
-- 
With best regards, Stas.

Hi Jeff,

The hyperspec doesn't intend to mean "execute in parallel".  It just means
that the values for the bindings in a let are computed independently of one
another, but that the bindings for the let* are computed sequentially.

Take the following example, which I have not submitted to Lisp and will
give you warnings about unused variables.

(defun foo-let (x)
  (let ((x 3)
        (x (* x x)))
  x)

(foo 2) --> 4

(defun foo-let-star (x)
  (let* ((x 4)
         (x (* x x)))
  x)

(foo-let-star 12313212) --> 16

There are various Lisp libraries that provide the functionality you're
looking for.  For example, Vladamir Sedach provides an eager futures
library [ http://common-lisp.net/project/eager-future/ ].  Also, I provide
a "plet" primitive (and others, like "spec-mv-let") for ACL2, which is
built on top of CL [
http://www.cs.utexas.edu/users/moore/acl2/current/PLET.html ].  If you'd
like more information about the latter, feel free to inquire (probably off
the list-serve).

David

On Tue, Nov 27, 2012 at 11:50 AM, Jeff Cunningham <jeffrey@...>
wrote:
> According to the Hyperspec:
>
> "let and let* create new variable bindings and execute a series of forms
> that use these bindings. let performs the bindings in parallel and let*
does
> them sequentially. "
>
> I thought I knew what that meant until I tried to demonstrate it to
myself.
> I wrote a simple function that eats cpu cycles for a visible period of
time.
> Then I set up a let expression which I thought would evaluate these forms
in
> parallel:
>
> (defun waste-time (n)
>   (let ((a 0))
>     (dotimes (i n a)
>       (incf a (- (random 1.0) 0.5)))))
>
> (let ((n 100000000))
>   (let ((n1 (waste-time n))
>         (n2 (waste-time n)))
>     (print n1)
>     (print n2)))
>
> I have a quad-core i7 running Linux  3.2.0-33-generic #52-Ubuntu SMP Thu
Oct
> 18 16:29:15 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux.
>
> I built a fresh copy of SBCL with --fancy (which includes threading I
> believe) which I cloned via git this morning.
>
> What I expected to see was two cpu cores busy for a few seconds when I run
> this. But what I in fact see is a single thread running. This indicates it
> is evaluating the let bindings serially, not in parallel.
>
> If I wrap the code with (time ) I get this for the parallel let:
>
> 362.691
> 1979.4808
> Evaluation took:
>   3.815 seconds of real time
>   3.816238 seconds of total run time (3.816238 user, 0.000000 system)
>   100.03% CPU
>   8,753,527,227 processor cycles
>   30,000 bytes consed
>
> And I get this for the serial let*:
>
> -2341.4565
> 436.2103
> Evaluation took:
>   3.783 seconds of real time
>   3.780236 seconds of total run time (3.780236 user, 0.000000 system)
>   99.92% CPU
>   8,680,021,725 processor cycles
>   33,168 bytes consed
>
>
>
> So I don't understand what the difference is, other than the compiler not
> being willing to recognize sequential bindings in the case of let vs let*.
>
> Regards,
> Jeff
>
>
------------------------------------------------------------------------------
> Monitor your physical, virtual and cloud infrastructure from a single
> web console. Get in-depth insight into apps, servers, databases, vmware,
> SAP, cloud infrastructure, etc. Download 30-day Free Trial.
> Pricing starts from $795 for 25 servers or applications!
> http://p.sf.net/sfu/zoho_dev2dev_nov
> _______________________________________________
> Sbcl-help mailing list
> Sbcl-help@...
> https://lists.sourceforge.net/lists/listinfo/sbcl-help
>

>According to the Hyperspec:
>
>    "let  and let* create new variable bindings  and
>    execute a series of forms that use these bindings
>    . let performs the bindings in parallel and let* 
>    does them sequentially. "
>
>I thought I knew what that meant until I tried to demonstrate it to 
>myself. I wrote a simple function that eats cpu cycles for a visible 
>period of time. Then I set up a let expression which I thought would 
>evaluate these forms in parallel:
>
>(defun waste-time (n)
>   (let ((a 0))
>     (dotimes (i n a)
>       (incf a (- (random 1.0) 0.5)))))
>
>(let ((n 100000000))
>   (let ((n1 (waste-time n))
>         (n2 (waste-time n)))
>     (print n1)
>     (print n2)))
>
>I have a quad-core i7 running Linux  3.2.0-33-generic #52-Ubuntu SMP Thu 
>Oct 18 16:29:15 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux.
>
>I built a fresh copy of SBCL with --fancy (which includes threading I 
>believe) which I cloned via git this morning.
>
>What I expected to see was two cpu cores busy for a few seconds when I 
>run this. But what I in fact see is a single thread running. This 
>indicates it is evaluating the let bindings serially, not in parallel.
>
> <..>
>
>So I don't understand what the difference is, other than the compiler 
>not being willing to recognize sequential bindings in the case of let vs 
>let*.

The spec is less rigid here.

For let, compiler may (has the right without breaking the specs) decide
to spawn a thread (hard to do well because of overhead) or reorder
evaluation order for whatever reason. It could do it, but it opts not to
do all this. 

But where it must behave differently is where not only the process of 
carrying out work but side effects or return values is different:

(defun test* (a b)
  (let* ((a b) (b a))
    (format t "~s ~s~%" a b)))

(defun test (a b)
  (let ((a b) (b a))
    (format t "~s ~s~%" a b)))

Jeff Cunningham <jeffrey@...> writes:

> According to the Hyperspec:
>
>     "let and let* create new variable bindings and execute a series of
>     forms that use these bindings. let performs the bindings in
>     parallel and let* does them sequentially. "

The other responses you've been given tell part of the story, but I
think are failing to be clear on something that is important: performing
the bindings in parallel or sequentially is orthogonal to the evaluation
order of the initialization forms.

In both
  (let ((a (form-a))
        (b (form-b)))
    ...)
and
  (let* ((a (form-a))
         (b (form-b)))
    ...)
the evaluation of (form-b) is specified to happen after the evaluation
of (form-a) has completed:

  "[...] first evaluates the expressions init-form-1, init-form-2, and so on,
  *in that order*, saving the resulting values"

(note *in that order*, emphasis mine).

So it is not possible to spawn threads to evaluate the initialization
forms of a LET form in parallel: the evaluations must happen
sequentially, so that side-effects happen in the right order.

Cheers,

Christophe

Hi,

On 11/27/12 18:50, Jeff Cunningham wrote:
> According to the Hyperspec:
> 
> "let and let* create new variable /bindings/ and execute a series of
> /forms/ that use these /bindings/. let performs the /bindings/ in
> parallel and let* does them sequentially."
>

Maybe the following could help to understand those *sequentially* and
*parallel*, using the sbcl prompt:

* (let ((a 1)(b a)) b)
; in: LET ((A 1) (B A))
;     (LET ((A 1) (B A))
;       B)
[...]
;
; caught WARNING:
;   undefined variable: A
;
; compilation unit finished
;   Undefined variable:
;     A
;   caught 1 WARNING condition
;   caught 1 STYLE-WARNING condition

debugger invoked on a UNBOUND-VARIABLE: The variable A is unbound.
[...]

* (let* ((a 1)(b a)) b)

1
*

:Nicolas

Hello,

I'm just cureous now: Is there a version of LET that at least does not 
guarantee the order of the evaluation and, ideally, would actually spawn 
different threads to compute the values of the bindings of the LET form?

I'm asking because I was talking with an old-time Lisper at our last ABQ 
Lisp/Scheme group meeting who had written a system that would break down 
the code you gave it to determine which parts could be reordered e.g. the 
FOO, BAR, and BAZ calls in the (artifically simple) expression (+ (foo a) 
(bar b) (baz c)) and then randomly reorder them so as to help them find 
bugs when they *thought* that the order should be unimportant.

I often write LET statements that don't (I dont' think) depend on 
side-effects to do their jobs, but I can see how something like what my 
friend brought up at our last meeting could be usefil.

Just cureous,
Jim

On Tue, 27 Nov 2012, Christophe Rhodes wrote:

> Jeff Cunningham <jeffrey@...> writes:
>
>> According to the Hyperspec:
>>
>>     "let and let* create new variable bindings and execute a series of
>>     forms that use these bindings. let performs the bindings in
>>     parallel and let* does them sequentially. "
>
> The other responses you've been given tell part of the story, but I
> think are failing to be clear on something that is important: performing
> the bindings in parallel or sequentially is orthogonal to the evaluation
> order of the initialization forms.
>
> In both
>  (let ((a (form-a))
>        (b (form-b)))
>    ...)
> and
>  (let* ((a (form-a))
>         (b (form-b)))
>    ...)
> the evaluation of (form-b) is specified to happen after the evaluation
> of (form-a) has completed:
>
>  "[...] first evaluates the expressions init-form-1, init-form-2, and so on,
>  *in that order*, saving the resulting values"
>
> (note *in that order*, emphasis mine).
>
> So it is not possible to spawn threads to evaluate the initialization
> forms of a LET form in parallel: the evaluations must happen
> sequentially, so that side-effects happen in the right order.
>
> Cheers,
>
> Christophe
>
> ------------------------------------------------------------------------------
> Keep yourself connected to Go Parallel:
> DESIGN Expert tips on starting your parallel project right.
> http://goparallel.sourceforge.net
> _______________________________________________
> Sbcl-help mailing list
> Sbcl-help@...
> https://lists.sourceforge.net/lists/listinfo/sbcl-help
>

James E. Prewett                    Jim@... download@... 
Systems Team Leader           LoGS: http://www.hpc.unm.edu/~download/LoGS/ 
Designated Security Officer         OpenPGP key: pub 1024D/31816D93 
HPC Systems Engineer III   UNM HPC  505.277.8210

On 11/27/2012 11:22 AM, Christophe Rhodes wrote:
>
>
> the evaluation of (form-b) is specified to happen after the evaluation
> of (form-a) has completed:
>
>    "[...] first evaluates the expressions init-form-1, init-form-2, and so on,
>    *in that order*, saving the resulting values"
>
> (note *in that order*, emphasis mine).
>
> So it is not possible to spawn threads to evaluate the initialization
> forms of a LET form in parallel: the evaluations must happen
> sequentially, so that side-effects happen in the right order.
>

Yes - I can see that now. That is key to what I was missing.

Thanks.
Jeff