Better then loop/iterate?

Discussion of Common Lisp
Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Better then loop/iterate?

Post by Jasper » Tue Mar 17, 2009 4:35 am

It might be crappy but this is currently pretty much the sequence. My attitude is a little like 'just do it damit'
  • dolist, dotimes.
  • loop (which is pretty bad..)
  • do (ok, but not too readable.)
  • If i need a stack, recursively. (Unless a stack happens to fall in my lap, like the code in OP)
The ones based on functions seemed a little weirdly named. Also, when you collect stuff in some way, like summing, consing, appending, working with a stream, etcetera, it would seem better to let the callback do the work, because otherwise the function with function as argument has to gather all the stuff internally, and every different way would need it's own implementation. Unless you provide functions to specify how it, but that would make it a bit more complicated to use.

If you use callbacks to gather, you only need to have different functions for different ways of iterating. This is btw another advantage of this way over loop and iter, you can do: (Should've called :single-round \:once..) (all untested)

Code: Select all

(defun add-1 (list)
  (umac ((:list) (:single-round)) (map nil (lambda (x) (collecting (+ x 1))))))
Hmm, i don't think that is best, maybe instead of the multitude of map* functions, use reduce?

Code: Select all

(defun consa (list add) '(,@list ,add))
(defun add-1 (list)
  (reduce (lambda (out el) (consa out (+ el 1)) list))
Here i find myself wishing i could make the lambda with a stack language: '1 + consa' would produce that. I guess that wouldn't be readable enough either though. Or do the lambda cheaper ($ (consa $1 (+ $2 1)), but also a little bit dense..

I have thought about higher functions, like when i thought about having (not function) be equivalent to (lambda (&rest rest) (not (function @rest))), or if there is spillover: (f-a f-b) eqv to (lambda ([stuff of f-b] [stuff of f-a]) (f-a (f-b [stuff of f-b]) [stuff-of-f-a])). Maybe i should make a little macro, maybe instead (ho () f-a f-b) can do that, or even (ho (f-d) f-a f-b f-c), that would make reduce look a lot more attractive.(f-d being arguments before f-a f-b f-c, etc. Ah shit i don't really see how to do the lambda in the defun right now. I need to think about this more.
With this stuff using functions taking functions as arguments would be much more attractive, not having to have (lambda (arguments) ..) floating around everywhere.

The umac macro i made here makes me doubt. Lets ask the question how we would make a lisp that does this with regular macros. I'd do it with scope; defvars, defun, defmacro, defsymbol-macro limited to the bodies of progn, lambda, etc. You could do pretty the thing i did with umac by having a scope-transparent-progn, and making the macro output a scope-transparent-progn have the defvars etc. in it. But then i ask of myself why still have a let, flet, macrolet?

Somewhat relatedly, i am also doubting whether s-expressions are really the way we should write everything. Sure, what we write should trivially be converted to s-expressions, but there is a lot that does that. not~expr -> (not expr) for single-argumented functions and numerically, a + b -> (+ a b), same for *, etc. would need to work out precidence.
The thing here that is related that we could write (def symbol expr) for a variable and (def (fun-name arguments) (progn body)) for functions, now we can think about scoping and call {...} (progn ...) and a := b (def a b), and we would get functions written more like ocaml or something.

Code: Select all

(defmacro for-list (el list &optional (iter (gensym))
  (post-body `(progn ,iter = (cdr ,iter) /*Add to post-body*/
                                (when (null iter) (finish)))) /*Stop at end of list.*/
  `(transparent-progn
      ,iter := ,list
      (def-symbol-macro ,el (car ,iter))))

(defmacro equip-listing (&optional (out-var 'ret)) /*Ret being default return.*/
  `(transparent-progn
      (collecting &rest args) := { (append ,out-var (list args)) }
      (appending &rest args) := { (append ,out-var args) }))

(add-list list &optional (add 1)) := 
  { (for-list el list) (equip-listing)   /*Make this scope one that iterates a list, and get stuff to collect with.*/
    (collecting (+ el add))
  }
That might not look very lispy, but the layer of veneer on the s-expressions is very thin. (Note that definining functions with := only has an expression, not a body; you need to either use {} to get a body.) It kills a tonne of hooks, even more could be removed with this idea but i decided not to overload it with too many ideas.

Harleqin
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Better then loop/iterate?

Post by Harleqin » Tue Mar 17, 2009 5:31 am

Code: Select all

(defun add-1 (list)
  (mapcar (lambda (x) (+ x 1)) list))
"Just throw more hardware at it" is the root of all evil.
Svante

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Better then loop/iterate?

Post by gugamilare » Tue Mar 17, 2009 9:20 am

I hate loop and love iterate. One problem (which is mostly not a big deal) is that iterate sometimes does not respect order of the computation (I do not have examples of this right now), but it works quite well. The only big problem with iterate is that the symbols you have to use are the ones exported from iterate package. You cannot, for instance,

Code: Select all

(iter:iter (:for i from 0 to 10) (print i))
You can't even

Code: Select all

(iter:iter (for i from 0 to 10) (print i))
unless the package :iter is being used (i.e. with (use-package :iter)). I would prefer to be able to use keywords instead.

The thing I most like about iterate is that it macroexpands into very readable code (except that it macroexpands every macro being used in the body of the loop) - SBCL's loop macroexpansion, for instance, is a nightmare. Iter also has the advantage of not doing function calls whenever they are not needed (of flets) - it creates just lexical bindings.

By the way, one performance hint. Collecting elements into a list does not need to walk into the list until the last position. You can explicitly create a collector this way:

Code: Select all

(let ((list nil)
      (last nil))
  (flet ((collect (elt)
           (if list
               (setf list (list elt) last list)
               (setf (cdr last) (list elt)))))
    (dotimes (i 100)
      (collect i)))
  list)

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Better then loop/iterate?

Post by Jasper » Tue Mar 17, 2009 3:20 pm

@Harleqin: I get it, keep it simple, stupid :) I went a little crazy with alternative syntax. Might be a good way to attract people that are crazy with syntax, or hate parentheses to lisp though..

I agree just by comparing loop with the docs of iterate that the latter is superior. It also looks like i underestimated iterate, according to that, iterate actually can read normal macros, actually expanding them to look inside. I had thought of that, but wanted to take an easy route after all that mucking about.

Unless there are some other snags, iterate is probably much better then what i made. I think i will just finish what i have. (I already removed that silly assoc list.) Even the problem of having to use the package doesn't seem very important. They're probably not keywords because some of them are regular macros, and they didn't want to be inconsistent.

Thanks for the hint, I don't get it though. List starts nil, whenever collect is called, the second clause is called, only affecting last, so list stays nil.. Also what i already got seems straightforward enough.

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Better then loop/iterate?

Post by gugamilare » Tue Mar 17, 2009 5:05 pm

Hum, I had fixed that, but copied the wrong version. Basically, it works with 2 variables, the "list" itself and "last", which is analogous to (last list) (i.e. if you call (last list) you obtain the same value which last is bound to)..

Code: Select all

(let ((list nil)
      (last nil))
  (flet ((collect (elt)
           (if (null list)
               (setf list (list elt) last list)
               (setf (cdr last) (list elt) last (cdr last)))))
    (dotimes (i 100)
      (collect i)))
  list)

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Better then loop/iterate?

Post by Jasper » Wed Mar 18, 2009 5:43 pm

Implemented. I tried to get it to work for a list directly, but somehow (setf last (last last)) doesn't get it to work properly. I just did it by adding them one by one. I have (collecting &rest collected), instead of a single argument; i wouldn't know what to do with the rest of the arguments anyway. The specification that we are listing already also specifies a variable to list into. Hmm, maybe next to a :list i need a :list-into extension..

Spotted a disadvantage with the optimization, other extensions which do not play well with the 'last variable, break it. And currently they can't work well with it; 'last is a gensym. Added a function fix-list that sets last correctly.
gugamilare wrote:The thing I most like about iterate is that it macroexpands into very readable code
I can't make umac do this, not if i don't look into the body to see if the flets/macrolets etc. are actually used. At least excess unused variables/flets shouldn't make.

I think i will put it online somewhere under the public domain, as a small 'you see what you do with this, please try iterate first' thing.

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Better then loop/iterate?

Post by gugamilare » Wed Mar 18, 2009 7:20 pm

Jasper wrote:Implemented. I tried to get it to work for a list directly, but somehow (setf last (last last)) doesn't get it to work properly. I just did it by adding them one by one. I have (collecting &rest collected), instead of a single argument; i wouldn't know what to do with the rest of the arguments anyway.

Code: Select all

(let ((list nil)
      (last nil))
  (flet ((collect (&rest elts)
           (if (null list)
               (setf list elts last list)
               (setf (cdr last) elts last (last elts)))))
    (dotimes (i 100)
      (collect i)))
  list)
This should do for multiple arguments.

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

Re: Better then loop/iterate?

Post by findinglisp » Wed Mar 18, 2009 11:12 pm

Call me old-fashioned... I just use LOOP. :shock: Like everybody else, I reach for DOLIST and DOTIMES for the simple stuff, as well as MAPCAR and friends for that type of work, but then it's pretty much straight to LOOP for everything else.

That said, I'm interested in ITERATE. That seems close to LOOP but helpful for curing some of the general LOOP annoyances, as well as being extensible.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Better then loop/iterate?

Post by Jasper » Thu Mar 19, 2009 5:42 am

@gugamilare: Imbarrassed i didn't find that myself, but at least you forgot to check (collect i i)

I guess loop is alright, but it is so damn ugly. It is a stranger in s-expression land. That, in itself is fine by me, but it is also unclear how to convert the thing into s-expressions.

The only thing that minorly annoys about iterate at this point that it uses stuff like (for k from 0 to 100), not many macros do that afaik. However this is easily fixed:

Code: Select all

(require :iterate)
(in-package #:iterate)

(defmacro for-range (var from to)
  `(for ,var from ,from to ,to))

(iter (for-range k 0 10)
      (collect k))
...Excellent

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

Re: Better then loop/iterate?

Post by findinglisp » Thu Mar 19, 2009 9:08 am

Jasper wrote:I guess loop is alright, but it is so damn ugly. It is a stranger in s-expression land. That, in itself is fine by me, but it is also unclear how to convert the thing into s-expressions.
Well, LOOP is just one big sexpr. That is, people have always said that LOOP is annoying because it doesn't use more parentheses, but it's never been a big problem for me. I'm not sure that more parentheses would buy me much. Sure, there are definitely advantages of sexpr movement in the editor, etc., but everything in a DO subexpression is a sexpr anyway, and that's where I spend most of my time. I use LOOP in macros all the time and don't really have problems because of lack of sexprs; everything expands as it should. You might have to use PROGN forms a bit to make sure things group, but that's all doable. In other words, the complaint seems to be more of an aesthetic, but less of a practical matter. I have no doubt that somebody could show a situation where LOOP didn't do well in another large macro, but in practice, for me at least, that seems more of a theoretical argument.

IMO, the biggest pains with LOOP are remembering how multiple termination clauses interact with other clauses and such. In other words, it's that it's a whole big complex macro, whatever it's syntax. And I'm assuming ITERATE has some of the same issues since it's basically LOOP with more sexprs. That said, I'm not an ITERATE guru at this point; I have just skimmed the top-level documentation and never used it in practice.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

Post Reply