Better then loop/iterate?

[nuntius]

I also tried to read the thesis nuntius posted, but i don't think i have the background knowledge to understand properly. Is it [url=http://en.wikipedia.org/wiki/Graph_theory]graph theory that i am missing?

s/posted/linked/

Yeah, Olin's paper isn't an easy read. From watching his talk, I gathered that it also requires a significant codebase to implement. I hope to tackle it someday (unless else someone gets there first), but I really linked it as a way of saying "this might finally be a solved problem". Once the CFG and LTK languages are implemented, making a nice API should be a walk in the park.

The funny notation starting around Figure 11 looks like sequent calculus.

[findinglisp]

Another thing that struck me is this tidbit of the manual. From here.

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? If the functions are constant or based on higher-order functions on constants, you should be able to expand them just as macros, with similar results. What i actually consider to be the use for iterate, is that it is more convenient. Especially in iterating while accumulating/collecting it can be very handy.

Looks fairly true to me. Which part do you think might not be true, the first statement about not being able to open-code user-written functions or the second part about creating intermediate sequences?

[Jasper]

Yeah, Olin's paper isn't an easy read. From watching his talk, I gathered that it also requires a significant codebase to implement.

Significant means a large amount of code? In my (limited) experience shorter is usually better, and longer often means going in the wrong direction. Of course, the short code one is looking for often is not easy to find. (And i might be wrong.)

Which part do you think might not be true, the first statement about not being able to open-code user-written functions or the second part about creating intermediate sequences?

What is open-coding exactly(sorry :p ) whatever it is, inlining achieves it.(Right?) Most of the time when you use functions taking functions as arguments, you enter in constant functions, or functions from constant functions' output, or functions that depend on non-function variables.(Both can be expanded.) They can be replaced by their result, just like (+ (* 2 2) x) can be replaced with (+ 4 x). The only point where you can't expand functions is where they depend on non-constant functions(For which macros don't have a counterpart.) I am assuming that lisp actually does this. I could probably write code that does this. (If the functions are created with defun*, so i can store the functions and read their code.) However, if you ask me, it is the CL implementations responsibility, maybe i should look what optimizations implementations like SBCL say they do at this aspect. (Or *cringe* even look into their code.)
That said, the worry if the resulting code from expansion would become too large is different in macros relative to functions taking functions. In macros you already imagined what is going to happen, in functions you did not. However, it should be possible to estimate how much space expansion relative to function call costs, this is both an advantage and a disadvantage. The advantage is that it allows a little more choice whether you want to preserve space or speed, the disadvantage is that estimating this might not be that easy.

Maybe i should be more specific: The sequence to expand functions as function of functions:

• Look for funcalls, where did the argument for the funcall come from?
• A variable: See where variable came from, do one of below for what you find. (Might not be possible if turns out depending on non-constant functions, or if someone is iterating by changing a function or something like that, then again you can't compare with macros at that point; macros have no analogy except going through eval.) If used more then once, might want to expand into a local flet to let lisp decide whether to inline.
• (funcall (lambda(,@args) ,@body) ,@got-> expand to (let (,@(combine args got)) ,@body), and then repeat the looking for funcalls.
• (funcall (some-fun ,@args) ,@got) -> expand some-fun until you either find you can't, or find the final lambda. When latter do above.
• (funcall #',fun-name ,@got) and (funcall ',fun-name ,@got) Easy, (,fun-name ,@got)

Edit: I forgot mentioning functions taking arguments inside the function to be inlined, you can inline those aswel, using the same method.
I guess i have not covered apply yet.


As for user-written intermediate sequences, i don't know of anything that can be done about that, besides define-compiler-macros specific to the functions. To be honest, functions taking functions as arguments and having as their way of output what they return strikes me as the wrong way to do it, except for very simple stuff like lists. If your program is a little more complicated, you have to think about how to collect the data to return together. It is like connecting each of the houses to the powerplant individually. You wouldn't have to do that if you just let the function return nothing(or maybe some information it stumbles upon and would be wasteful to waste.), letting the callbacks do the work like collection.

[findinglisp]

What is open-coding exactly(sorry :p ) whatever it is, inlining achieves it.(Right?)

Open-coding is like a very primitive form of inlining. The main difference is that it's performed directly by the compiler and thus can be even more efficient for certain operations. Essentially, the compiler is programmed to understand certain primitive functions (cons, car, cdr, length, etc.) and it just spits out the exact right machine code for those at the call site. Like inlining, it eliminates the function call, but unlike inlining, it doesn't rely on a bunch of compiler analysis to optimize things further. Because the compiler author knows exactly how standard primitives like car or length work, he can optimize them by hand when the compiler is written.

Maybe i should be more specific: The sequence to expand functions as function of functions:

• Look for funcalls, where did the argument for the funcall come from?
• A variable: See where variable came from, do one of below for what you find. (Might not be possible if turns out depending on non-constant functions, or if someone is iterating by changing a function or something like that, then again you can't compare with macros at that point; macros have no analogy except going through eval.) If used more then once, might want to expand into a local flet to let lisp decide whether to inline.
• (funcall (lambda(,@args) ,@body) ,@got-> expand to (let (,@(combine args got)) ,@body), and then repeat the looking for funcalls.
• (funcall (some-fun ,@args) ,@got) -> expand some-fun until you either find you can't, or find the final lambda. When latter do above.
• (funcall #',fun-name ,@got) and (funcall ',fun-name ,@got) Easy, (,fun-name ,@got)

Edit: I forgot mentioning functions taking arguments inside the function to be inlined, you can inline those aswel, using the same method.
I guess i have not covered apply yet.

Most compilers already perform various transformations like this. Basic constant expressions are typically evaluated during compilation (e.g., things like (+ 2 2) is simply replaced with 4). This is not, however, what Olin was talking about. There are many cases when the call site cannot be optimized because you don't know what to inline within it. For instance, if I write (mapcar #'xyzzy '(1 2 3)), and xyzzy is defined in another compilation unit, the compiler, even a very smart compiler, has no chance to optimize anything. While a good compiler can open-code the instructions for mapcar (essentially doing the equivalent of (loop for temp in '(1 2 3) collect (funcall #'xyzzy temp)) ), it still must call xyzzy each time. If xyzzy is in the same compilation unit and it is declared to be inline, then perhaps a smart compiler will inline it in this instance, but realize that inline directives are hints, not orders. A compiler is not required to inline anything, no matter how many inline and speed directives you give it.

As for user-written intermediate sequences, i don't know of anything that can be done about that, besides define-compiler-macros specific to the functions. To be honest, functions taking functions as arguments and having as their way of output what they return strikes me as the wrong way to do it, except for very simple stuff like lists. If your program is a little more complicated, you have to think about how to collect the data to return together. It is like connecting each of the houses to the powerplant individually. You wouldn't have to do that if you just let the function return nothing(or maybe some information it stumbles upon and would be wasteful to waste.), letting the callbacks do the work like collection.

This is the kind of thing that Shivers was talking about, I think. There are many cases where the simple, obvious, static analysis falls short. Among these cases are many interesting ones (not strange, theoretical corner cases, for instance, but real practical problems). Devices like Common Lisp compiler macros were created, I think, to allow application writers to provide application-specific smarts to a standard compiler to help it along through some of the optimizations. While we can always theorize that a compiler should be able to do such and such, some of the analysis can get very complex very quickly and may be very error prone to handle the general cases. Many compilers fall well short of what might be theoretically possible.

[Jasper]

I have been a little annoyed by this: Having flets, lets, macrolets and symbol-macrolets separate all the time has disadvantages.

1) More nested then need be, implying more parenthesis, more depth of indentation.

2) Sometimes need lets or flets in some specific order, causing more nesting.

So it might be better to use macros that create all these macros at the same time, and it seems to be the only disadvantage of that is that it punishes the user a little less when he doesn't create sub functions fast enough. I don't think that is worth it; programmers need to recognize that themselves anyway.

There are a bunch of ways to do this:

• With a macro with a specific variable(of any *let) creation area. The umac this thread was begun with somewhat does that.(Looking at the source code, i see i didn't write it so it can fix (2) currently, easily fixed, and then it'll do it.) Advantages is clear distinction between variables and body, and separate namespace for 'macros to create variables'.(def-umac) You could make a with-slots for the umac, for instance. (maybe not so inferior to iterate after all.)
• An iterate-like approach, working in a scope-like manner. here the advantage is that regular macros can make variables. It likely needs a 'scope-transparant'
• Loop like approach, much like the iterate approach, but just with symbols(which also need to indicate regular body elements). Don't really like it. Nor do i know how to make it properly flexible. WITH somewhat does this.

I feel i am missing something.. Maybe a 'denesting' function..

Code: Select all

(defmacro denest ((&rest args) &body body)
  (if (null args)
    `(progn ,@body)
    `(,@(car args)
      (denest (,@(cdr args)) ,@body))))

Edit: maybe nestedness really is the problem loop, iterate and such are trying to solve, i think this thing will perform at least just as well as umac in looping. At least accumulators are made easily enough:

Code: Select all

(defmacro summing ((&optional (initial 0) (onto (gensym))) &body body)
  `(let ((,onto ,initial))
     (macrolet ((sum (&rest summed)
		 (list 'setf ',onto (append (list '+ ',onto) summed)))) ;Too lazy to figure out how to backquote here.
       ,@body)
     ,onto))

(denest ((summing ())
	      (dolist (el (list 1 2 3 4))))
  (sum el))

[dmitry_vk]

I have been a little annoyed by this: Having flets, lets, macrolets and symbol-macrolets separate all the time has disadvantages.

1) More nested then need be, implying more parenthesis, more depth of indentation.

2) Sometimes need lets or flets in some specific order, causing more nesting.

So it might be better to use macros that create all these macros at the same time, and it seems to be the only disadvantage of that is that it punishes the user a little less when he doesn't create sub functions fast enough. I don't think that is worth it; programmers need to recognize that themselves anyway.

There are a bunch of ways to do this:

• With a macro with a specific variable(of any *let) creation area. The umac this thread was begun with somewhat does that.(Looking at the source code, i see i didn't write it so it can fix (2) currently, easily fixed, and then it'll do it.) Advantages is clear distinction between variables and body, and separate namespace for 'macros to create variables'.(def-umac) You could make a with-slots for the umac, for instance. (maybe not so inferior to iterate after all.)
• An iterate-like approach, working in a scope-like manner. here the advantage is that regular macros can make variables. It likely needs a 'scope-transparant'

There is a metabang-bind project. It does what you describe and is extensible.

[Jasper]

Looking at metabang bind, not exactly. I don't really see the extension mechanism in the docs. I suppose you can add different keywords, just like :values was added. If it works that way, it's somewhat similar to umac i guess. Likely with a better implementation of it too. So you are probably right, but the docs i linked to would be a little out of date in that case..

Weird that i didn't think of something as simple as denest, it's five lines.. I am stumped... I suspect it can do pretty much everything loop(edit or iterate) can(at least everything i regularly use, which is admittedly, not that much), using macros that do the various things, and which can be used stand-alone too. It would use only a few parenthesis(and no nesting) more then macros like iterate. Further, it feeds from about every macro it encounters. It's not a project.. it's just there.. wtf.

Plus, a minor adjustment removes those few more parenthesis.

Code: Select all

(defmacro denest* ((&rest args) &body body)
  (if (null args)
    `(progn ,@body)
    `(,(caar args) (,@(cdar args)) ;Edit, made a silly mistake, forgot to change this to denest* too.
      (denest*(,@(cdr args)) ,@body))))

Do mind though that now it can't use with-slots, multiple-value-bind anymore.

Edit: did i edit on the denest macro? or did you just happen to not quote it. I remember not editing it on, but just submitting it. Memory might not serve me right.

[gugamilare]

If you look at metabang-bind's code, you'll see it is extensible, and also support for much more keywords than specified in the docs.

[Harleqin]

2) Sometimes need lets or flets in some specific order, causing more nesting.

Why don't you use LET* and LABELS then?

[Jasper]

LABELS somehow didn't get on my radar.. Why isn't it called FLET* -_-. Either way, LET* and LABELS don't solve the mixing of functions and variables. Nor for WITH-SLOTS, DOLIST, really pretty much anything. Actually Neither does DENEST, but DENEST fixes the accompanying nesting+indentation needed.

METABANG-BIND might be able to work it with DEFBINDING-FORM. However, look at how it does :slots, for instance, compared with this macro you just plug the existing macro in. The core part also is more then 5 lines.

I am not saying this macro is something to get exited over, it can't do wonders. But it seems a little surprising that there is such a simple yet powerful method that nobody seems to have been using. I have made a little modified method, to add denest-specific 'keyword macros', that work exactly the same as macros, they're just there to use less namespace. And i added two block types to return from 'denest' to drop out completely, and 'denest-prev-ret', the latter is to return whatever the accumulators/value returning macros have been picking up. totally ~60 lines of code with all that.(With doc strings and all, and including DENEST*) Totalling 183 lines, with various accumulators, iterators and returning thingies. With this, code like this works.

Code: Select all

(denest ((collecting (nil list))
  	      (summing (0 a))
 	       (:return (values a list)) ;Override return of summing. (summing overrided that of collecting) does (return-from denest value)
	       (dolist (el (list 1 2 3 4))))
  (summing el)
  (collecting a))

(denest ((collecting ())
	       (:integer-block ((i 0 10) (j 0 10)) ()))
  (when (and (= i 5) (= j 5))
    (finish)) ;finish does (return-from denest-prev-ret), which then returns whatever that macro intended to return. (Unfortunately requires a block for that.)
  (collecting (list i j)))

As i said, it won't suddenly make things easy, and god knows you've never seen me output anything useful(yet), but it does seem to me like an improvement. Unlike umac, i think i'll opine it better then iterate. I can hardly believe no-one else has come up with this, probably it hasn't.. But why are we using stuff like LOOP, ITERATE then?