Re: Next Generation of Language

From: wv9...@xxxxxxxxx
I don't think there is anything more anti parallelism like Lisp. Lisp
is recursive, a function has to basically wait for another instance of
itself to finish before continuing. Where is the parallelism?

OK, consider the most trivial recursive-definition example, factorial:
I you use non-branching recursion merely to emulate iteration,
that's stupid, requiring tail-recursion optimization to avoid stack
overflow. But if you divide-and-conquer, the parallelism is obvious:

(defun lo+hi-product (lo hi)
"Computes product lo * (lo+1) * (lo+2) ... up to but not including hi"
(if (>= (+ 1 lo) hi)
lo
(let ((mid (ceiling (+ lo hi) 2)))
(* (lo+hi-product lo mid)
(lo+hi-product mid hi)))))
;(lo+hi-product 2 3) ==> 2
;(lo+hi-product 1 6) ==> 120
;Caveat: The above code works correctly only when lo is an integer.
;A slight change in the logic would be needed to handle products such
; as 1.3 * 2.3 * 3.3 * 4.3 etc., left as exercise to newbies/students.

(defun factorial (n)
(lo+hi-product 1 (+ 1 n)))
;(factorial 5) ==> 120

In general, recursive algorithms are more divide-and-conquer rather
than emulation of iteration. IMO It's unfortunate that the
really-iterative definition of factorial is usually given as the
first example of "recursion" in schools.

<mathCliche>In general, it helps to solve a more general problem
than the one given. The more general problem is often actually
easier to understand than the given special case.</mathCliche>
In this case, generalizing 1*2*3*... to LO*(LO+1)*(LO+2)*...
make it more obvious how to divide-and-conquer.
.

Relevant Pages

  • Re: Making Lisp popular - can it be done?
    ... “hack” for recursion. ... We already have to think about how to do tail ... (recur (dec n) ... experience with implementing Lisp, ...
    (comp.lang.lisp)
  • Re: kernel stack challenge
    ... > infinite loop, and eventually ... Separate logical copy of LISP program is for each ... subsystem we protect. ... > recursion is at all interesting or useful.... ...
    (Linux-Kernel)
  • Re: How to make mod_lisp faster than php?
    ... In the Lisp group, the first fellow will answer, "I know my opinion, ... There seem to be various levels of acceptance of deep recursion ... It's possible that Scheme is here because a standard implementation of call/cc which puts stack frames on the heap yields this property. ... I think that implies tail recursion, ...
    (comp.lang.lisp)
  • Re: Beginners Question on an exercise from Grahams ACL
    ... > just been taught and to exercise my brain on them - not with some other ... Recursion might be more worthwhile as a separate item to learn, ... than binding up lisp and recursion into a single package of pain. ... Alternate places than lisp materials might teach it better, ...
    (comp.lang.lisp)
  • Re: Brevity vs. Lispicity
    ... Recursion is a natural fit for some problems, ... maybe Common Lisp isn't the language for you. ... posters, both with a question regarding Ex3Chapter3AnsiCL. ... (incf (cdr (assoc x result))) ...
    (comp.lang.lisp)