The Future of Lisp

Discussion of Common Lisp
cperkins
Posts: 3
Joined: Wed Jul 23, 2008 5:43 pm

Re: The Future of Lisp

Post by cperkins » Mon Sep 29, 2008 4:58 pm

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

Exolon
Posts: 49
Joined: Sat Jun 28, 2008 12:53 pm
Location: Ireland
Contact:

Re: The Future of Lisp

Post by Exolon » Mon Sep 29, 2008 5:37 pm

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).

death
Posts: 17
Joined: Sat Jun 28, 2008 1:44 am

Re: The Future of Lisp

Post by death » Mon Sep 29, 2008 5:38 pm

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.

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: The Future of Lisp

Post by findinglisp » Mon Sep 29, 2008 5:41 pm

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.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

cperkins
Posts: 3
Joined: Wed Jul 23, 2008 5:43 pm

Re: The Future of Lisp

Post by cperkins » Mon Sep 29, 2008 9:21 pm

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.

Wodin
Posts: 56
Joined: Sun Jun 29, 2008 8:16 am

Re: The Future of Lisp

Post by Wodin » Tue Sep 30, 2008 12:39 pm

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

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: The Future of Lisp

Post by findinglisp » Thu Oct 09, 2008 9:23 am

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/
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

dmitry_vk
Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan
Contact:

Re: The Future of Lisp

Post by dmitry_vk » Thu Oct 09, 2008 9:37 am

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)

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: The Future of Lisp

Post by findinglisp » Thu Oct 09, 2008 9:43 am

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.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: The Future of Lisp

Post by findinglisp » Thu Oct 09, 2008 6:57 pm

Here's Anders Hejlsberg's keynote from the same conference. Very interesting.
http://jaoo.blip.tv/#1324214
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

Post Reply