Better then loop/iterate?

[dmitry_vk]

One problem with higher-order functions is that they are inefficient, requiring multiple calls on their argument function. While the the built-ins, like map and mapcar, can be open-coded, that cannot be so easily done for user-written functions. Also, using higher-order functions often results in the creation of intermediate sequences that could be avoided if the iteration were written out explicitly.

Isn't that just untrue?

Why do you think that this statement is not true?
Consider the following:

Code: Select all

(reduce '+ (mapcar (lambda (x) (* x 2)) '(1 2 3 4)))

mapcar creates a new, freshly consed list. This list is the passed to reduce. But this fresh list is not neccessary, because it is possible to reduce this list in-place.
In Haskell, this statement about higher-order functions would be completely true: compiler would rearrange code to prevent unnecessary allocation of intermediate lists (this is called «list fusion»).

[gugamilare]

Reducing in place? Ok:

Code: Select all

(reduce (lambda (x y) (+ x (* 2 y))) '(1 2 3 4) :initial-element 0)

what about this, then:

Code: Select all

(let ((list '(1 2 3 4)))
  (reduce '+ (map-into list (lambda (x) (* x 2)) list)))

?

[dmitry_vk]

Reducing in place? Ok:

Code: Select all

(reduce (lambda (x y) (+ x (* 2 y))) '(1 2 3 4) :initial-element 0)

what about this, then:

Code: Select all

(let ((list '(1 2 3 4)))
  (reduce '+ (map-into list (lambda (x) (* x 2)) list)))

?

Your function unnecessarily modifies the list. What I meant is more like this:

Code: Select all

(let ((res 0)
  (map nil (lambda (x) (incf res (* x 2))) '(1 2 3 4)))
  res)


but writing such transformations by hand is tedious.

[Ramarren]

SERIES package does fusion/deforestation for Common Lisp, although no one seems to be actually using it, possibly because it seems very Haskellish way to code. Although as far as I know Haskell doesn't do fusion by default, at least not in stable GHC?

[Jasper]

but writing such transformations by hand is tedious.

This is lisp!

Code: Select all

(define-compiler-macro reduce (&whole whole fun list &key (start 0))
  (cond
    ((listp list)
     (case (car list)
       (mapcar ;Kill redundant list creation.
   (destructuring-bind (fun slist) (cdr list)
     (let ((res (gensym)))
       `(let ((,res 0))
          (map nil (lambda (x)
           (setf ,res (funcall ,fun x)))
          ,slist)
          ,res))))
       (t
   whole)))
    (t
     whole)))

(defmacro reduce-c (fun list &key (start 0))
  (cond
    ((listp list)
     (case (car list)
       (mapcar ;Kill redundant list creation.
   (destructuring-bind (fun slist) (cdr list)
     (let ((res (gensym)))
       `(let ((,res 0))
          (map nil (lambda (x)
           (setf ,res (funcall ,fun x)))
          ,slist)
          ,res))))
       (t
   `(reduce ,fun ,list :start ,start))))
    (t
     `(reduce ,fun ,list :start ,start))))

(reduce '+ (mapcar (lambda (x) (* x 2)) '(1 2 3 4)))

(reduce-c '+ (mapcar (lambda (x) (* x 2)) '(1 2 3 4)))

This needs to incorporate more &key arguments, and more killing of intermediate lists, from other sources, but it can work. I don't think define-compiler-macro is the most powerful optimalization technique that can exist in principle, but it is pretty good. (Do any non-lisp languages even have it?) As for testing, the reduce-c macro-equivalent does seem to work.

BTW lets not forget:

"The Anatomy of a Loop: A Story of Scope and Control" by Olin Shivers
http://www.international-lisp-conferenc ... ivers_olin

The paper can be found at
http://www.ccs.neu.edu/home/shivers/citations.html

[dmitry_vk]

but writing such transformations by hand is tedious.

This is lisp!
...
This needs to incorporate more &key arguments, and more killing of intermediate lists, from other sources, but it can work. I don't think define-compiler-macro is the most powerful optimalization technique that can exist in principle, but it is pretty good. (Do any non-lisp languages even have it?) As for testing, the reduce-c macro-equivalent does seem to work.

I don't think that defining compiler-macros for functions from CL is a good thing, since it might break existing optimizations that rely on compiler-macros. Off-topic: it would be very nice to be able to define multiple compiler-macros for a single function.
As for other languages, Haskell (actually, GHC compiler) has rewrite rules that allow pattern-based rewriting of code.

[gugamilare]

Indeed, defining compiler macros for standard functions is classified by the ANSI as "unportable code". But reduce does accept a key argument, so:

Code: Select all

(reduce #'+ '(1 2 3 4) :key (lambda (x) (* 2 x)))

[Jasper]

Well, the point remains that the optimization is possible with compiler macros, and i think lisp implementations are a little thorough and effective at it relative to what i just thought of in 5 minutes.

Compiler macros can break eachother? Hmm, maybe compiler macros should have priorities, or multiple rounds of them. That way the implementations' optimizations are done first, and others can that go over what remains. (Anyway, if the function producing the intermediate list was a non-cl function, it shouldn't break anything.)

Of course packages should not be exporting stuff that is not the purpose of the package(for compiler macros, or anything else.), for instance PAL exports 'clamp'.. v+, v-, wish those were in separate packages. pal-vect, pal-util, or something. Pal is pretty good so-far though, albeit low on documentation(strings), maybe missing features. (But hey, add it yourself as you go .)

[gugamilare]

Have you seen Lispbuilder-SDL? It is an interesting alternative, at least 4 games were created using it and it is pretty much stable.

Just to mention, you can check lispbuilder at sourceforge, but it is outdated. The first link is better.

[Jasper]

@gugamilare, thanks, i am trying it. (Hrmm haven't gotten opengl to work, but my opengl seems to be bound to sdl, namespace interfering with that of lispbuilder, but i'll try figure it out more myself.)

SERIES package does fusion/deforestation for Common Lisp, although no one seems to be actually using it, possibly because it seems very Haskellish way to code. Although as far as I know Haskell doesn't do fusion by default, at least not in stable GHC?

I read it a little, and i think that it is just because it is harder to learn, partially because it is further away from loop. (I think i encountered it before aswel.)
I also tried to read the thesis nuntius posted, but i don't think i have the background knowledge to understand properly. Is it graph theory that i am missing?

It might very well be that the better ways to loop are harder to learn. Maybe it would be good to make the other loop so that if you learn more, you are lead to the better ways to loop. For instance, by implementing the lesser ways to loop (Which could possibly be iterate-like macros) with the harder ways.