I read once that haskell programs can be automatically multi-threaded,
parallelled for mutli-processor loading by complier, without any
explicit usage of MP libraries or language constructions.
Is it possible with lisp code ?
Vagif Verdi wrote:
> I read once that haskell programs can be automatically multi-threaded,
> parallelled for mutli-processor loading by complier, without any
> explicit usage of MP libraries or language constructions.
>
> Is it possible with lisp code ?
Sure it is possible -- in the ideal world of purely functional
programming one can evaluate all arguments to a function in parallel,
same for (non-starred) things like LET. On the other hand, Common Lisp
standard explicitly specifies that even for parallel things like LET
and PSETF arguiments are evaluated left-to-right, so any implementation
which would try to use this parallelization opportunity will not be a
Common Lisp.
Paul B.
·······@gmail.com" <······@gmail.com> writes:
> Vagif Verdi wrote:
>> I read once that haskell programs can be automatically multi-threaded,
>> parallelled for mutli-processor loading by complier, without any
>> explicit usage of MP libraries or language constructions.
>>
>> Is it possible with lisp code ?
>
> Sure it is possible -- in the ideal world of purely functional
> programming one can evaluate all arguments to a function in parallel,
> same for (non-starred) things like LET. On the other hand, Common Lisp
> standard explicitly specifies that even for parallel things like LET
> and PSETF arguiments are evaluated left-to-right, so any implementation
> which would try to use this parallelization opportunity will not be a
> Common Lisp.
Left-to-right evaluation doesn't prevent parallelism.
(let ((a 1)
(b (+ c 2))
(c (- c 2)))
(print (list a b c)))
can be generated as:
(let ((k c))
(let (a b c)
(vector-setf (c b a) (vector-eval (- k 2) (+ k 2) 1))
(let (x y z)
(vector-setf (y x z) (vector-eval (cons nil nil)
(cons nil nil) (cons nil nil)))
(vector-setf ((car z) (car x) (car y)) (c b a))
(vector-setf ((cdr x) (cdr y) (cdr z)) (vector-eval (y z nil)))
(print x))))
Contrarily to what you may think, this code still evaluates the forms
from left to right. Even the following sequential code still
evaluates from left to right:
(let ((k c))
(let (a b c)
(setf c (- k 2))
(setf a 1)
(setf b (+ k 2)))
(let ((x nil))
(setf x (cons c x))
(setf x (cons b x))
(setf x (cons a x))
(print x)))
Of course, if you had something like:
(let ((a 1)
(b (incf c 2))
(c (incf c 2)))
(print (list (decf a) (+ b (decf a)) (+ c a))))
left-to-right would suddenly take a stronger meaning. But it would
still allow for a good degree of parallelism.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"I have challenged the entire quality assurance team to a Bat-Leth
contest. They will not concern us again."
······@gmail.com wrote:
> Vagif Verdi wrote:
>> I read once that haskell programs can be automatically multi-threaded,
>> parallelled for mutli-processor loading by complier, without any
>> explicit usage of MP libraries or language constructions.
>>
>> Is it possible with lisp code ?
>
> Sure it is possible -- in the ideal world of purely functional
> programming one can evaluate all arguments to a function in parallel,
> same for (non-starred) things like LET. On the other hand, Common Lisp
> standard explicitly specifies that even for parallel things like LET
> and PSETF arguiments are evaluated left-to-right, so any implementation
> which would try to use this parallelization opportunity will not be a
> Common Lisp.
Even without these left-to-right specifications, you could force serial
evaluation by using the following pattern:
(let ((x ...))
(let ((y ...))
(let ((z ...))
...)))
This what a LET* expands to, at least conceptually.
The reason is that Common Lisp has strict evaluation of arguments. That
is, in a binding (let ((var some-expression)) ...), some-expression is
evaluated immediately, and it is guaranteed in the example above that
the expression for x is evaluated before the expression for y, and that
again before the expression for z. Haskell has lazy evaluation. Lazy
evaluation means that some-expression would only be evaluated as soon as
var is read for the first time - potentially never - and it is not
guaranteed in the example above that x is evaluated before y or before z
- they can (and are) evaluated in some arbitrary order, as dictated by
the enclosed code. (Lazy evaluation is sometimes nice because with it,
you can implement potentially infinite data structure in a very
straightforward way.)
However, sometimes you really need serial evaluation instead, for
example when you do IO (which is essentially a side effect). In that
case, lazy evaluation doesn't work well. For example, the following
example might not do what you actually expect, for the reasons given above:
(let ((x (print 1))
(y (print 2)))
...)
In order to handle these situations, monads were "invented" that force
serial evaluation of programs in a lazily evaluated language.
Apparently, monads are used a lot in "real" Haskell programs, so the
opportunities for parallelization are probably also considerably reduced.
Pascal
--
3rd European Lisp Workshop
July 3 - Nantes, France - co-located with ECOOP 2006
http://lisp-ecoop06.bknr.net/
Pascal Costanza schrieb:
> ······@gmail.com wrote:
> > Vagif Verdi wrote:
> >> Is it possible with lisp code ?
> > Sure it is possible -- ...
The Idea goes like this:
Take a dual-core-CPU and write
(CAR CAR CDR CDR)
for evaluate in one step instead of
(CAR CDR) (CAR CDR)
Its more parallel and more cpus will go to a chip in future...
What do you think?
stefan
(lambda apply my-list new-list)
There usually are opportunities for parallelism when using declarative
programming. CL is not declarative, but allows one to embed the
construct. Some examples:
. embedded Prolog in Lisp (see Norvig, PAIP), a declarative language
. Cells; spreadsheet-like interfaces are declarative
. SQL interface, an example of a declarative DSL
I don't know of anyone who has actually gone to the trouble of
inserting a parallel engine into any of these, but in theory it is
tractable, even when embedded in non-declarative languages such as CL.
Lou Vanek
Vagif Verdi wrote:
> I read once that haskell programs can be automatically multi-threaded,
> parallelled for mutli-processor loading by complier, without any
> explicit usage of MP libraries or language constructions.
>
> Is it possible with lisp code ?
Vagif Verdi schrieb:
> I read once that ...
> Is it possible with lisp code ?
There was:
Qlisp, Ron Goldman, Richard Gabriel, Carol Sexton, a scheme-like
Multilisp, Robert Halstead, an extended Scheme-version
PaiLisp, paper by Takayasu Ito and Manabu Matsui, a kernel-language
gc-algorithms, James Miller, Barbera Epstein
Concurrent Scheme, Robert Kessler, Mark Swanson, concurrent threads in
seperat domains
the Boyer benchmark, W.Ludwell Harrison, (compiler-notes)
ABCL, An Object-Oriented Concurrent System, Akinori Yonezawa (workshop),
Etsuya Shibanyama and Yonezawa (book)
TAO, Ikuo Takeuchi, practical expirience, runs on ELIS Lisp machine,
(namespace problems - symbol packages)
MacELIS, Ken-ichiro Murakami
Mul-T, David Kranz, Robert Halstead, Eric Mohr (optimizing compiler
generating code for Encore Multimax)
Utilisp, (University of Tokyo Interactive Lisp), Hideya Iwasaki,
(mUtilisp, implementation, simulat parallelism by time-slicing)
PM!, PMLisp, Taiichi Yuasa, Takafumi Kawana, (8-bit Z80, first prototype
of "P-machine"), Scheme-like
EVLIS, Hiroshi Yasui, Tashikazu Sakaguchi, Kohichi Kudo, Nobuyuki
Hironishi, (multiport mem-sys)
TOP-1, Norihisa Suzuki, ongoing project of parallel Common Lisp
GHC (guarded-Horn-clause), Kazunori Ueda (comments: Akikazu Takeuchi),
(variables in p-languages)
OPS-5, Hiroshi Okuno, (parallelizing 2 large AI systems)
...
Yes, there are many many more papers, articles, running systems,
experiments, ... out there. A small list is sent to you, taken from
Parallel Lisp: Languages and Systems, US/Japan Workshop on Parallel
Lisp, Sendai, Japan, June 1989 (1989! <-- thats Lisp).
stefan
-a step to an other world inside your computer-