From: ············@googlemail.com
Subject: A Question about Concurrency and Pure Lisp
Date: 
Message-ID: <1175529998.625917.175740@n59g2000hsh.googlegroups.com>
Hello everyone,

An interesting question:
Are these two expressions fully equivalent? ( ... e ...)  and ( ... (future
e) ... ), e is a pure lisp expression, so no side effect, no printing.

(future e) means that e is concurrently evaluated, more precisely,
     1. The location l that will contain the value of (future e) is
identified
         (if the value is going to go into   an existing cons cell) or
created if needed.

     2. A process is created to evaluate e.

     3. When the process evaluating e completes, the value of e is
placed in the location. l

     4. The process that invoked (future e) continues in parallel with
the new process.
         If the originating process tries to read the contents of
location l while it is still empty,
         then the process blocks until the location has been filled
with the value of e.

I have tried to find an negative example from myself or google. but I
can not.

Can anybody give me any hint? Thank you in advance.

Xi Laile

From: Lars Rune Nøstdal
Subject: Re: A Question about Concurrency and Pure Lisp
Date: 
Message-ID: <461146e5$0$29070$c83e3ef6@nn1-read.tele2.net>
On Mon, 02 Apr 2007 09:06:38 -0700, xilai.lehaha wrote:

>      4. The process that invoked (future e) continues in parallel with
> the new process.
>          If the originating process tries to read the contents of
> location l while it is still empty,
>          then the process blocks until the location has been filled
> with the value of e.

Playing with the new `sb-thread:join-thread' .. maybe not what you wanted,
but still fun:


(defpackage :FutureTest
  (:use :cl))
(in-package :FutureTest)


(defun newCell ()
  (cons nil   ;; value-slot
        nil)) ;; thread-slot


(defun thread-of (cell)
  (cdr cell))


(defun (setf thread-of) (thread cell)
  (setf (cdr cell) thread))


(defun value-of (cell)
  (if (sb-thread:thread-alive-p (thread-of cell))
      (setf (car cell) (sb-thread:join-thread (thread-of cell)))
      (car cell)))


(defun (setf value-of) (value cell)
  (setf (car cell) value))


(defmacro inBackground (thread-name &body body)
  `(let ((cell (newCell)))
     (setf (thread-of cell)
           (sb-thread:make-thread
            (lambda () ,@body)
            :name (concatenate 'string "cell-" ,thread-name)))
     cell))



(defun wrt (str)
  (format t "#~A: ~A~%"
          (subseq (princ-to-string (get-universal-time)) 8)
          str))
          


(defun test ()
  (let* (;; Will not block:
         (a (inBackground "a"
              (wrt "`a' is being set (in the background).")
              (sleep 2) ;; Do some fancy calculations that takes some time here.
              (prog1 1
                (wrt "`a' has now actually been set."))))
         
         ;; Will not block:
         (b (inBackground "b"
              (wrt "`b' is being set (in the background)")
              (prog1 (+ 1 (value-of a))
                (sleep 2)
                (wrt "`b' has now actually been set."))))
         
         ;; Will block since `inBackground' is not used:
         (c (progn
              (wrt "`c' is being set (blocks until `a' is actually set).")
              (prog1 (+ 2 (value-of a))
                (wrt "`c' has now been set.")))))
    
    (list (value-of a)
          (value-of b)
          c)))
  

#|
FutureTest> (test)
#42: `a' is being set (in the background).
#42: `c' is being set (blocks until `a' is actually set).
#42: `b' is being set (in the background)
#44: `a' has now actually been set.
#44: `c' has now been set.
#46: `b' has now actually been set.
(1 2 3)
|#


-- 
Lars Rune Nøstdal
http://nostdal.org/
From: Alex Mizrahi
Subject: Re: A Question about Concurrency and Pure Lisp
Date: 
Message-ID: <461155ad$0$90272$14726298@news.sunsite.dk>
(message (Hello ·············@googlemail.com)
(you :wrote  :on '(2 Apr 2007 09:06:38 -0700))
(

 xl> (future e) means that e is concurrently evaluated, more precisely,
 xl>      1. The location l that will contain the value of (future e) is
 xl> identified
 xl>          (if the value is going to go into   an existing cons cell) or
 xl> created if needed.

 xl>      2. A process is created to evaluate e.

 xl>      3. When the process evaluating e completes, the value of e is
 xl> placed in the location. l

 xl>      4. The process that invoked (future e) continues in parallel with
 xl> the new process.
 xl>          If the originating process tries to read the contents of
 xl> location l while it is still empty,
 xl>          then the process blocks until the location has been filled
 xl> with the value of e.

how are you going to implement this?

i don't see a way to implement FUTURE transparently (if it's not already 
implemented) without major changes (e.g. writing lisp interpreter in lisp).
however, is quite easy to implement this in non-transparent way, as Lars 
have demonstrated.

but if you'll really do this, it's very easy to prove that they are 
equivalent. given the condition

--
  If the originating process tries to read the contents of location l while 
it is still empty,
  then the process blocks until the location has been filled with the value 
of e.
--

application will not be detect presence of FUTURE.
however, i'm not sure what location is, how is it possible to determine when 
application tries to read..

for example, if HT is hash table, and you do (setf (gethash (future (A)) ht) 
(future (B)))
it's not even possible to define any physical localtion where result of (B) 
will be stored -- because we need first to calculate (A), find it's hash, 
and only then associate result (B) with it. so, gethash should block until 
(future (A)) is calculated, or you need HT to support lazy keys..
all this is very weird :)

)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"?? ???? ??????? ?????") 
From: Pascal Bourguignon
Subject: Re: A Question about Concurrency and Pure Lisp
Date: 
Message-ID: <874pnxucnf.fsf@voyager.informatimago.com>
"Alex Mizrahi" <········@users.sourceforge.net> writes:

> (message (Hello ·············@googlemail.com)
> (you :wrote  :on '(2 Apr 2007 09:06:38 -0700))
> (
>
>  xl> (future e) means that e is concurrently evaluated, more precisely,
> [...]
> how are you going to implement this?
>
> i don't see a way to implement FUTURE transparently (if it's not already 
> implemented) without major changes (e.g. writing lisp interpreter in lisp).
> however, is quite easy to implement this in non-transparent way, as Lars 
> have demonstrated.
> [...]

Obviously, this is a primitive mechanism that needs to be implemented
at the level of the implementation, or using some implementation
specific primitive.  You must have a specific type of values for
futures, and everytime you read an object, you must check if it's a
future (in addition to checking if it's of the type you're exepcting,
so there's not much more work to do than usual).


One difficulty would be  when you have unboxed values:

(defvar a (make-array 10 :element-type '(unsigned-byte 8) :initial-element 0))
(setf (aref a 0) (future (compute-some-byte)))

You'd have to have a flag indicating that the array may contain some futures...

-- 
__Pascal Bourguignon__
http://www.informatimago.com
http://pjb.ogamita.org
From: Joerg Hoehle
Subject: Re: A Question about Concurrency and Pure Lisp
Date: 
Message-ID: <u647nysng.fsf@users.sourceforge.net>
Pascal Bourguignon <···@informatimago.com> writes:
>  You must have a specific type of values for
>futures, and everytime you read an object, you must check if it's a
>future (in addition to checking if it's of the type you're exepcting,
>so there's not much more work to do than usual).
> You'd have to have a flag indicating that the array may contain some futures...
Which remembers me of DELAY & FORCE and implicit forcing of delayed values.

I haven't seen a Lisp which features this automatic forcing of delayed
values for many years now.
Would you expect this to be different with futures?

Regards,
	Jorg Hohle
Telekom/T-Systems Technology Center
From: Tim Bradshaw
Subject: Re: A Question about Concurrency and Pure Lisp
Date: 
Message-ID: <1175590312.149637.73310@n76g2000hsh.googlegroups.com>
On Apr 2, 5:06 pm, ············@googlemail.com wrote:

> An interesting question:
> Are these two expressions fully equivalent? ( ... e ...)  and ( ... (future
> e) ... ), e is a pure lisp expression, so no side effect, no printing.

If E fails to halt but the program does not actually use its value
then they may not be equivalent, since one program halts and the other
does not.
From: Vassil Nikolov
Subject: Re: A Question about Concurrency and Pure Lisp
Date: 
Message-ID: <m3ps6jcdlz.fsf@localhost.localdomain>
On 3 Apr 2007 01:51:52 -0700, "Tim Bradshaw" <··········@tfeb.org> said:

| On Apr 2, 5:06 pm, ············@googlemail.com wrote:
|| An interesting question:
|| Are these two expressions fully equivalent? ( ... e ...)  and ( ... (future
|| e) ... ), e is a pure lisp expression, so no side effect, no printing.

| If E fails to halt but the program does not actually use its value
| then they may not be equivalent, since one program halts and the other
| does not.

  To add to that, we'd need to specify what would happen in the case
  of errors, abnormal termination, etc.  Equivalence also depends on
  the choice(s) we make in this regard.  (Note: this is more of a
  "practical" consideration; it is not a fundamental consideration
  like Tim Bradshaw's post quoted above.)

  ---Vassil.


-- 
The truly good code is the obviously correct code.
From: Tim Bradshaw
Subject: Re: A Question about Concurrency and Pure Lisp
Date: 
Message-ID: <1175773057.442292.13890@e65g2000hsc.googlegroups.com>
On Apr 5, 11:36 am, Vassil Nikolov <···············@pobox.com> wrote:
> On 3 Apr 2007 01:51:52 -0700, "Tim Bradshaw" <··········@tfeb.org> said:
>

>   To add to that, we'd need to specify what would happen in the case
>   of errors, abnormal termination, etc.  Equivalence also depends on
>   the choice(s) we make in this regard.  (Note: this is more of a
>   "practical" consideration; it is not a fundamental consideration
>   like Tim Bradshaw's post quoted above.)

Good point.  There are actually interesting questions about this kind
of thing for implementations even without FUTURE.  For code like:

(let ((e (complicated-computation)))
  ... E is not used ...)

Are you allowed to not call COMPLICATED-COMPUTATION?  What about side-
effects and failure to terminate?  Of course these issues are not
unique to Lisp.

--tim