Page 2 of 3

Re: The Future of Lisp

Posted: Mon Sep 29, 2008 4:58 pm
by cperkins
Even if the runtime of each task was known, optimal multi-core scheduling is NPC iirc../SNIP/...the best we can do is simple heuristic algorithms.
Maybe someone should try it without any sort of optimizing algorithm. If massive mult-core is in the future, then I'd be interested to see how even a dumb implementation works. How about a Lisp where every variable clause of a let (not let*, obviously) is evaluated on a different core if the assignment is a function call, and where the body of the let statement runs once they've all returned.

Code: Select all

(let ((a  (calc-something ...))          
      (b (calc-something-else ...))
      (c (calc-another-thing ...)))
 ;; once each of the above calc- calls have returned, then continue
   (+ a b c))
Chris

Re: The Future of Lisp

Posted: Mon Sep 29, 2008 5:37 pm
by Exolon
cperkins wrote:Maybe someone should try it without any sort of optimizing algorithm. If massive mult-core is in the future, then I'd be interested to see how even a dumb implementation works.
Agreed - if we assume optimising algorithms are too needy, some simple heuristics like this might be useful at least.
cperkins wrote:How about a Lisp where every variable clause of a let (not let*, obviously) is evaluated on a different core if the assignment is a function call, and where the body of the let statement runs once they've all returned.
Sounds good, unless the semantics of let guarantee that the variable clauses should be executed in the order they're encountered (do they?) - in which case side-effecting clauses will behave weirdly.
Obviously, having let variable clauses print to standard output or write to files seems kind of dumb, but a more realistic scenario could have lists/objects being manipulated to extract data.
This is one area where the strict classifications of side-effects is useful in Haskell, especially since it seems to be designed with that issue in mind so the default is no-side-effects, and the user only has to get verbose when they introduce monads (and only where necessary).

Re: The Future of Lisp

Posted: Mon Sep 29, 2008 5:38 pm
by death
cperkins wrote:Maybe someone should try it without any sort of optimizing algorithm. If massive mult-core is in the future, then I'd be interested to see how even a dumb implementation works. How about a Lisp where every variable clause of a let (not let*, obviously) is evaluated on a different core if the assignment is a function call, and where the body of the let statement runs once they've all returned.
This violates the specified evaluation order of the init-forms. With let, only the bindings are performed in parallel.

Re: The Future of Lisp

Posted: Mon Sep 29, 2008 5:41 pm
by findinglisp
cperkins wrote:Maybe someone should try it without any sort of optimizing algorithm. If massive mult-core is in the future, then I'd be interested to see how even a dumb implementation works. How about a Lisp where every variable clause of a let (not let*, obviously) is evaluated on a different core if the assignment is a function call, and where the body of the let statement runs once they've all returned.
My hunch is that the overhead of setting things up to run on each of the cores with each function call would kill the performance.

But as you say, it would be an interesting experiment.

Re: The Future of Lisp

Posted: Mon Sep 29, 2008 9:21 pm
by cperkins
Years ago, before I started working in Lisp, there was a project where someone developed a Lisp with auto-memoization (through some hardcore macrology, I believe, nothing more). I don't remember the exact details - I seem to recall there was a notation to denote whether a function was referentially transparent or not. But I do remember that they were memoizing extensively, even in let bindings. And, if I recall, the automated decision to memo-ize or not was all based on profiling performance data that was gathered as the program was run normally. Combine something like that with optional auto parallelization and maybe you have something.

I will try to dig up the paper. I googled but it didn't seem to come up in the top 5. I may be confusing the details with a different project, but I seem to recall that the client was the Air Force or maybe the Navy.



Death: yes, I had forgotten. In Common Lisp the initial statements of let are supposed to evaluate in order and only the bindings are parallel. But this isn't the case in Scheme and some other lisps.

Re: The Future of Lisp

Posted: Tue Sep 30, 2008 12:39 pm
by Wodin
I am sure there are various people working on feeding the results of profiling back into an optimiser/compiler. I have heard of a couple of examples. The ones I can think of off hand are on Geoff Wozniak's blog:

http://exploring-lisp.blogspot.com/search?q=profiling

Re: The Future of Lisp

Posted: Thu Oct 09, 2008 9:23 am
by findinglisp
I found this interview yesterday on Reddit that has some discussion of the issues with concurrency in language design. It's definitely worth watching. Warning: You'll have to be running a Microsoft product with Silverlight installed :roll: .
http://channel9.msdn.com/posts/Charles/ ... ge-Design/

Re: The Future of Lisp

Posted: Thu Oct 09, 2008 9:37 am
by dmitry_vk
findinglisp wrote:I found this interview yesterday on Reddit that has some discussion of the issues with concurrency in language design. It's definitely worth watching. Warning: You'll have to be running a Microsoft product with Silverlight installed :roll: .
http://channel9.msdn.com/posts/Charles/ ... ge-Design/
There is a link to mms:// feed, mplayer on linux can play it, no silverlight needed.
(mms://mschnlnine.wmod.llnwd.net/a1809/d1/ch9/2/4/9/0/3/4/JAOO2008HeljsbergSteeleConcurrency_s_ch9.wmv)

Re: The Future of Lisp

Posted: Thu Oct 09, 2008 9:43 am
by findinglisp
dmitry_vk wrote: There is a link to mms:// feed, mplayer on linux can play it, no silverlight needed.
(mms://mschnlnine.wmod.llnwd.net/a1809/d1/ch9/2/4/9/0/3/4/JAOO2008HeljsbergSteeleConcurrency_s_ch9.wmv)
Perfect! Thanks for the link. I didn't see that. Fortunately, I was running on Windows with Silverlight installed when I viewed the page, so things just worked for me, but I know that would trip up a lot of people on Windows or who haven't installed Silverlight on XP or something.

Re: The Future of Lisp

Posted: Thu Oct 09, 2008 6:57 pm
by findinglisp
Here's Anders Hejlsberg's keynote from the same conference. Very interesting.
http://jaoo.blip.tv/#1324214