The Future of Lisp

So I was just doing some morning reading with my first cup of coffee and stumbled across this on Reddit:
http://www.heise-online.co.uk/open/Shut ... ews/111534

In the article, Mark Shuttleworth, Ubuntu Big Cheeze, was asking the Python community what they are doing about three big megatrends in computing today: cloud computing, transactional memory, and multicore processors.

I think this is a general question that every programming language, including Lisp, should be asking itself (if a programming language, as such, is capable of asking itself anything ). Anyway, what do you LispForum members think about that question with respect to Lisp?

I'll start by saying that I think Shuttleworth's question, as reported by Heise, is slightly incorrect. I would not say that transactional memory is really a large trend right now, and it may never be. Rather, transactional memory is one technique for dealing with a massively multicore, parallel world. There are other ways to deal with that same fundamental problem, "How do I program a massively multicore system without making a mess of it?" Admittedly, TM is pretty elegant. Clojure takes the STM route to handle parallelism.

So, let me revise the question with what I feel are the big trends:

• Intead of "cloud computing" which seems pretty trendy and buzzword compliant, let's instead use "Internet-wide computing." The thought here is that things are going to be increasingly distributed. Programming languages need to provide abstractions to help programmers deal with that. This includes not just simple distribution of processing power "into the cloud" but also the usage a resources across the Internet (think what are typically called "mashups" now, but on steroids).
• Massively multicore - I think Shuttleworth got that right. I like to use the word "massive" associated with this because I think it helps people internalize that the future here is not 8 or even 16 core, but rather hundreds and eventually thousands of cores on a single die. Intel has already shown 80-core test chips, albeit not with full x86 cores. But I have had personal discussions with Intel architects that say that tens of cores is certainly right around the corner.
• Finally, to replace transactional memory, let me add high availability. In the future, you're going to see lots of application requirements that say things are going to have to work all day, every day, forever. The idea of application maintenance is going to dwindle for some applications to near zero. The ability to develop, debug, and upgrade a running application is going to be more important than ever.

Fortunately, I think that Lisp brings a LOT to the party with respect to many of these issues, though I think there are some fundamental things that Lisp needs to address ASAP in order to let its other fundamental goodness shine clearly. I discuss some of that here in this thread: viewtopic.php?f=2&t=137

Thoughts?

Intel has already shown 80-core test chips, albeit not with full x86 cores. But I have had personal discussions with Intel architects that say that tens of cores is certainly right around the corner.

You don't need personal discussions for that: Larrabee is tentatively expected to have 24 x86-64 cores late next year.

http://en.wikipedia.org/wiki/Larrabee_(GPU)

Its not that I do really know much of what I am about to talk about, but I think that with newer multicore-architectures with thousands of cores, as well as with cloud-computing, functional programming with few side-effects will get modern, because if you define a function f = g (h, i, j) recursively, you can compute h, i and j in different cores or computers, and so distribute the task of computing in a better way. Without side-effects, you can focus on computing the value of an expression without having to do much memory-management between cores or computers. And it is a lot of easier to write a functional expression that to tell the system to fork in a C-Sourcecode.
With "internet-wide-computing", I imagine that some common standard for exchanging structured data, presumably xml-based, will evolve, and thinking of many different systems and architectures, even program code is likely to be represented by these structures rather than by some bytecode - which will make optimizing harder because it will be too low-level - or other programming language - which will require additional parsers.
As I am not a scientist, I may be completely wrong. These are just a few thoughts of me when thinking about it, they are not very profound or detailed.

Looking at Common Lisp, I see a Programming Language that has the capability of easily - compared to other languages - find out the side-effects a function depends on (using a codewalker, etc.), and you can easily - compared to other languages - let any code be transformed into something that resolves these dependencies in a way that concurrent threads or processes will be able to use it (I have to admit I never tried to do so, but it should be possible - at least to some degree). It should be possible to transform code automatically into a "distributed" form. Also, all lisp-code (s-expressions) can easily be mapped into tree-structures, and should therefore be easy to exchange (i.e. without a lot of parsers and transformations in between).
Libraries like cl-perec show how versatile the CLOS is, if you can save CLOS-Objects in a Database, you can also put them into some Data-Structure and send them through the internet to some other Thread waiting for it.
I think Common Lisp would be a good Language to do "Cloud Computing". But I may be wrong (I would be interested if I am.)

In fact, sometimes my impression is, that much of the modern development of the existing programming systems is just reinventing things that common lisp (and other not-so-wide-spreaded systems like Standard ML) already have in a more complicated way, instead of using it to create something really new.

findinglisp wrote:high availability. In the future, you're going to see lots of application requirements that say things are going to have to work all day, every day, forever.

Recall Erran Gat's description of debugging and upgrading the Remote Agent software running aboard the "Deep Space 1" spacecraft 100 million miles from Earth in his Lisping at JPL.

because if you define a function f = g (h, i, j) recursively, you can compute h, i and j in different cores or computers, and so distribute the task of computing in a better way.

As a question, has this ever been done well automatically with today's compiler technology? People always cite functional programming as being beneficial for auto-parallelizing, and in theory they're quite right, but does any current compiler actually do this well today? GHC with Haskell, maybe?

If we can't already do this today, my hunch is that it's pretty hard to get right. If that's true, then the more simple answer may be explicit process-level parallelism, ala Erlang.

findinglisp wrote: As a question, has this ever been done well automatically with today's compiler technology? People always cite functional programming as being beneficial for auto-parallelizing, and in theory they're quite right, but does any current compiler actually do this well today? GHC with Haskell, maybe?

Yes, this is the very question I usually ask Haskell fans and I've never gotten a clear answer. I think this is indeed a hard problem since it is hard to decide when a calculation is time-consuming enough to offset the overhead of distributed programming. I would love to see a reference to working implementation of this concept in any functional language, with a critical discussion on the pros and cons.

yena wrote:

findinglisp wrote: As a question, has this ever been done well automatically with today's compiler technology? People always cite functional programming as being beneficial for auto-parallelizing, and in theory they're quite right, but does any current compiler actually do this well today? GHC with Haskell, maybe?

Yes, this is the very question I usually ask Haskell fans and I've never gotten a clear answer. I think this is indeed a hard problem since it is hard to decide when a calculation is time-consuming enough to offset the overhead of distributed programming. I would love to see a reference to working implementation of this concept in any functional language, with a critical discussion on the pros and cons.

Exactly. Isn't deciding the runtime of a given subproblem essentially the same as the halting problem?

The only thing that I can think of would be to go with a Linda-based common database of subproblems from which workers on individual cores take problems and to which they return results. Still, the overhead of that would be difficult to offset without some human direction, I would think.

findinglisp wrote: Exactly. Isn't deciding the runtime of a given subproblem essentially the same as the halting problem?

The only thing that I can think of would be to go with a Linda-based common database of subproblems from which workers on individual cores take problems and to which they return results. Still, the overhead of that would be difficult to offset without some human direction, I would think.

I don't think that equivalence of the problem to the halting problem should stop from implementing auto-parallelism.

There is already implemented technique of profile-driven optimization where information about complexity of different code parts is collected in runtime and is used to optimize the code (AFAIK, some Java VMs do this). Something like this could be applied to parallelize subtasks.

Dan Weinreb has posted an interesting comment related to Lisp's future: The Failure of Lisp?

findinglisp wrote:As a question, has this ever been done well automatically with today's compiler technology? People always cite functional programming as being beneficial for auto-parallelizing, and in theory they're quite right, but does any current compiler actually do this well today? GHC with Haskell, maybe?

I'd like to know as well. Even if the runtime of each task was known, optimal multi-core scheduling is NPC iirc. Since we can't make assumptions about runtime of each task before running them, and we don't have time for running genetic algorithms/simulated annealing-style search, the best we can do is simple heuristic algorithms. They might be good enough, but I don't know about the current real-life implementations.
What I (and probably all of you) have heard about ghc is that Haskell's system of specifying side-effects (and having a hierarchy of them) via monads does allow it to reschedule stuff cleverly on single-core.

A quick google turned up this though:

http://www.haskell.org/ghc/docs/latest/html/users_guide/lang-parallel.html#id431042 wrote:Ordinary single-threaded Haskell programs will not benefit from enabling SMP parallelism alone: you must expose parallelism to the compiler.

Which indicates that there's no automatic multi-core scheduling happening yet, although the syntax and semantics for manually exploiting parallelism seem quite expressive and powerful.

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.

(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

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

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.

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.

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.

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

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 .
http://channel9.msdn.com/posts/Charles/ ... ge-Design/

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

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.

Here's Anders Hejlsberg's keynote from the same conference. Very interesting.
http://jaoo.blip.tv/#1324214

Whilst watching his talk, it seems to me that the LINQ implementation is described in detail in the famous book.

vityok wrote:Whilst watching his talk, it seems to me that the LINQ implementation is described in detail in the famous book.

In general, I kept thinking to myself all the way through the talk, "Yea, Lisp can do that... and that... and that..." Ironically, even during the discussions of metaprogramming and DSLs, Lisp never really comes up. That really surprised me, particularly since Lisp is starting to be mentioned a lot more.

So, in general, from a Lisp-specific perspective, the talk is a bust. What I thought was most interesting, however, was the enumeration of the various programming problems that Anders is wrestling with because I think the problems are universal, whatever the language. Interestingly, I think that Lisp is well-positioned to help deliver solutions, but we need to move past 1990s Common Lisp in order to do so.

Actually he does mention Lisp by name, but what he says is that it was the first "functional programming language". It depends what you mean by "functional", but if you mean no side effects or something like that, well, you could sure do a lot more without side effects than you could in FORTRAN, but clearly modern Lisp isn't "functional" in the sense that Haskell is.

However, I agree that not mentioning Lisp in the contest of "internal domain specific languages" was odd. But, few people acknowledge Lisp as a source of ideas, even when it clearly is. Java is the one that really bothers me; Gosling never acknowledges how much Java owes to Lisp.

Does anyone here know enough about C# and LINQ to know whether the syntactic sugar that they added was something that anyone could add in their own back yard (a la using Lisp macros), or whether the C# designers had to add it as a specific new feature in the C# compiler?

dlweinreb wrote:Does anyone here know enough about C# and LINQ to know whether the syntactic sugar that they added was something that anyone could add in their own back yard (a la using Lisp macros), or whether the C# designers had to add it as a specific new feature in the C# compiler?

LINQ is a compiler feature. In order to add it, both compiler and Base Class Library were modified.

dlweinreb wrote:However, I agree that not mentioning Lisp in the contest of "internal domain specific languages" was odd. But, few people acknowledge Lisp as a source of ideas, even when it clearly is. Java is the one that really bothers me; Gosling never acknowledges how much Java owes to Lisp.

Interestingly, Steele does acknowledge this, however. I always found his statement about "Java dragging all the C programmers halfway to Lisp" (paraphrased) to be quite funny.

About parallelism, the pcall library makes it look(at least) as if it is easy. As others noted, you don't necessarily have to analyze the code to determine when to slip plets/join in, you can just run it and time which bits are worth paralellizing. So it is possible to do it automatically with existing common lisp code.