Is heavy use of lambdas considered bad style or not? I found myself
writing lambdas quite often, but the code looks absolutely hair-raising.
(However, practically every piece of Lisp code looks hair-raising to me
at the moment, so it's not very useful indicator ;). For instance, is it
ok to use nested lambdas?
Should I convert such code into (labels...) forms or even into normal
functions?
V.Ch. wrote:
> Is heavy use of lambdas considered bad style or not?
this depends how you formulate your problem. If you use a functional
programming style, this is normal, as in my functional geometry example or
texture generation:
http://www.frank-buss.de/lisp/functional.html
http://www.frank-buss.de/lisp/texture.html
> For instance, is it ok to use nested lambdas?
do you have an example?
> Should I convert such code into (labels...) forms or even into normal
> functions?
it doesn't hurt to convert it to functions, if possible. Sometimes you can
even re-use it from within other functions, which is an advantage of
functions :-)
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> do you have an example?
Yes, the code below is supposed to sort things according to their
dependencies. For instance, if we need to find out the correct order of
declaration of the following classes (C++):
class A: B, C {}
class B: D {}
we must call (topo-sort '((a b c) (b d))).
Nested lambdas are at the very bottom.
Would be greatful to hear all comments and suggestions:
<code>
; Dependency information is represented as a list of lists, where
; the first element depends on every element in the tail.
; Externally callable function.
(defun topo-sort (decls)
(let ((decl-hash (make-hash-table)))
(mapcar (lambda (s) (setf (gethash s decl-hash) nil)) (reduce
#'append decls))
(mapcar (lambda (d) (setf (gethash (car d) decl-hash) (cdr d))) decls)
(topo-sort-hash decl-hash)))
; Dependency information is represented as a hash table, where
; the key depends on every element in the value (list).
; This function is to be called by topo-sort only - it assumes that
; hash table entries exist for all elements.
(defun topo-sort-hash (decls)
(do ((ret nil)
(removed nil nil))
((zerop (hash-table-count decls)) (nreverse ret))
(maphash (lambda (k v)
(when (null v)
(push k ret)
(setf removed t)
(remhash k decls)))
decls)
(unless removed
(return 'cycle))
(maphash (lambda (k v)
(setf (gethash k decls) (remove-if-not (lambda (e)
(gethash e
decls)) v))) decls)))
</code>
+ "V.Ch." <····@not.real>:
| Nested lambdas are at the very bottom.
| [...]
| (maphash (lambda (k v)
| (setf (gethash k decls) (remove-if-not (lambda (e)
| (gethash e
| decls)) v)))
| decls)))
Those aren't nested hashes, there's both a setf and a remove-if-not in
between them. To answer your question, I wouldn't consider this
excessive use of lambda.
But you /do/ abuse indenting! It may look very neat that the two
occurences of decls are just below each other and all that, but I
immediately thought your code must be wrong because you're calling
maphash with only one argument (the outer lambda). A quick C-M-q
later the answer is revealed, and the code is more reasonably
indented:
(maphash (lambda (k v)
(setf (gethash k decls) (remove-if-not (lambda (e)
(gethash e
decls)) v)))
decls)
After moving a few newlines about it even gets downright readable:
(maphash (lambda (k v)
(setf (gethash k decls)
(remove-if-not (lambda (e) (gethash e decls))
v)))
decls)
To me, this conveys the structure of your code much better. Having a
line break between the arguments to setf makes it much clearer what
those two arguments are, and it saves a lot of indenting below. And
the newline before that lone v brings it out clearly as the second
argument of remove-if-not, rather than as some part of the first
argument.
With a little practice you should find that such simple rearrangements
of your code becomes second nature, and the improved readability lets
you focus on what the code does rather than what it looks like.
(Sorry, I didn't inspect your code further. It's past bedtime here.)
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
+ "V.Ch." <····@not.real>:
| Nested lambdas are at the very bottom.
| [...]
| (maphash (lambda (k v)
| (setf (gethash k decls) (remove-if-not (lambda (e)
| (gethash e
| decls)) v)))
| decls)))
Those aren't nested lambdas, there's both a setf and a remove-if-not
in between them. 8-) To answer your question, I wouldn't consider
this excessive use of lambda.
But you /do/ abuse indenting! It may look very neat that the two
occurences of decls are just below each other and all that, but I
immediately thought your code must be wrong because you're calling
maphash with only one argument (the outer lambda). A quick C-M-q
later the answer is revealed, and the code is more reasonably
indented:
(maphash (lambda (k v)
(setf (gethash k decls) (remove-if-not (lambda (e)
(gethash e
decls)) v)))
decls)
After moving a few newlines about it even gets downright readable:
(maphash (lambda (k v)
(setf (gethash k decls)
(remove-if-not (lambda (e) (gethash e decls))
v)))
decls)
To me, this conveys the structure of your code much better. Having a
line break between the arguments to setf makes it much clearer what
those two arguments are, and it saves a lot of indenting below. And
the newline before that lone v brings it out clearly as the second
argument of remove-if-not, rather than as some part of the first
argument.
With a little practice you should find that such simple rearrangements
of your code becomes second nature, and the improved readability lets
you focus on what the code does rather than what it looks like.
(Sorry, I didn't inspect your code further. It's past bedtime here.)
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
Harald Hanche-Olsen wrote:
> But you /do/ abuse indenting! ...
> With a little practice you should find that such simple rearrangements
> of your code becomes second nature, and the improved readability lets
> you focus on what the code does rather than what it looks like.
Thank you for the suggestion.
I relied entirely on emacs to do formatting for me, but with Lisp it's a
bit different - lines tend to get longer than in any other language, and
you need to think how to break them.
V.Ch. wrote:
> Frank Buss wrote:
>
>> do you have an example?
>
>
> Yes, the code below is supposed to sort things according to their
> dependencies. For instance, if we need to find out the correct order of
> declaration of the following classes (C++):
>
> class A: B, C {}
> class B: D {}
>
> we must call (topo-sort '((a b c) (b d))).
>
> Nested lambdas are at the very bottom.
> Would be greatful to hear all comments and suggestions:
>
> <code>
>
> ; Dependency information is represented as a list of lists, where
> ; the first element depends on every element in the tail.
> ; Externally callable function.
> (defun topo-sort (decls)
> (let ((decl-hash (make-hash-table)))
> (mapcar (lambda (s) (setf (gethash s decl-hash) nil)) (reduce
> #'append decls))
1. why are you creating entries in the hash table with values of nil?
does the very existence of a key have special meaning? if not (guessing
at your purpose) gethash will just return nil if you ask for a
non-existent key.
2. (apply 'append decls) will suffice. but...
3. ...why cons up a new list?
(dolist (decl decls)
(dolist (el decl)
(setf (gethash el decl-hash) nil)))
> (mapcar (lambda (d) (setf (gethash (car d) decl-hash) (cdr d))) decls)
> (topo-sort-hash decl-hash)))
>
> ; Dependency information is represented as a hash table, where
> ; the key depends on every element in the value (list).
> ; This function is to be called by topo-sort only - it assumes that
> ; hash table entries exist for all elements.
> (defun topo-sort-hash (decls)
> (do ((ret nil)
> (removed nil nil))
> ((zerop (hash-table-count decls)) (nreverse ret))
> (maphash (lambda (k v)
> (when (null v)
> (push k ret)
> (setf removed t)
> (remhash k decls)))
> decls)
> (unless removed
> (return 'cycle))
> (maphash (lambda (k v)
> (setf (gethash k decls) (remove-if-not (lambda (e)
> (gethash e
> decls)) v))) decls)))
>
> </code>
Will this do as well?:
(let ((data '((a b c) (b d) (d c))))
(flet ((independent-of (x y)
(not (find y (cdr (find x data :key 'car))))))
(sort (reduce 'union data) #'independent-of)))
=> (c d b a)
--
Kenny
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film
"If you plan to enter text which our system might consider to be
obscene, check here to certify that you are old enough to hear the
resulting output." -- Bell Labs text-to-speech interactive Web page
Kenny Tilton wrote:
>
>
> V.Ch. wrote:
>
>> Frank Buss wrote:
>>
>>> do you have an example?
>>
>>
>>
>> Yes, the code below is supposed to sort things according to their
>> dependencies. For instance, if we need to find out the correct order
>> of declaration of the following classes (C++):
>>
>> class A: B, C {}
>> class B: D {}
>>
>> we must call (topo-sort '((a b c) (b d))).
>>
>> Nested lambdas are at the very bottom.
>> Would be greatful to hear all comments and suggestions:
>>
>> <code>
>>
>> ; Dependency information is represented as a list of lists, where
>> ; the first element depends on every element in the tail.
>> ; Externally callable function.
>> (defun topo-sort (decls)
>> (let ((decl-hash (make-hash-table)))
>> (mapcar (lambda (s) (setf (gethash s decl-hash) nil)) (reduce
>> #'append decls))
>
>
> 1. why are you creating entries in the hash table with values of nil?
> does the very existence of a key have special meaning? if not (guessing
> at your purpose) gethash will just return nil if you ask for a
> non-existent key.
sorry, I did figure this out after staring at your algorithm a little
more, but neglected to delete this.
--
Kenny
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film
"If you plan to enter text which our system might consider to be
obscene, check here to certify that you are old enough to hear the
resulting output." -- Bell Labs text-to-speech interactive Web page
Kenny Tilton wrote:
> Will this do as well?:
>
> (let ((data '((a b c) (b d) (d c))))
> (flet ((independent-of (x y)
> (not (find y (cdr (find x data :key 'car))))))
> (sort (reduce 'union data) #'independent-of)))
>
> => (c d b a)
Oops. Cycles. Hang on. :)
--
Kenny
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film
"If you plan to enter text which our system might consider to be
obscene, check here to certify that you are old enough to hear the
resulting output." -- Bell Labs text-to-speech interactive Web page
Kenny Tilton wrote:
>
>
> Kenny Tilton wrote:
>
>> Will this do as well?:
>>
>> (let ((data '((a b c) (b d) (d c))))
>> (flet ((independent-of (x y)
>> (not (find y (cdr (find x data :key 'car))))))
>> (sort (reduce 'union data) #'independent-of)))
>>
>> => (c d b a)
>
>
> Oops. Cycles. Hang on. :)
>
(defun topo-sort (data)
(flet ((independent-of (x y)
(not (find y (assoc x data)))))
(let ((s (sort (reduce 'union (mapcar 'copy-list data))
#'independent-of)))
(loop for (i . deps) on s
unless (every (lambda (d)
(independent-of i d)) deps)
do (return-from topo-sort `(cycle ,i))
finally (return s)))))
(topo-sort '((a b c) (b d)(d c)(c b)))
=> (cycle b)
(topo-sort '((a b c) (b d)(d c)))
=> (c d b a)
Probably better to look for cycles first. anyway, break time.
--
Kenny
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film
"If you plan to enter text which our system might consider to be
obscene, check here to certify that you are old enough to hear the
resulting output." -- Bell Labs text-to-speech interactive Web page
Kenny Tilton wrote:
> 2. (apply 'append decls) will suffice. but...
According to Paul Graham reduce can be more efficient because apply uses
&rest parameters when called like this.
> 3. ...why cons up a new list?
>
> (dolist (decl decls)
> (dolist (el decl)
> (setf (gethash el decl-hash) nil)))
Thanks!
I just didn't get this habit yet to look for excessive consing.
V.Ch. wrote:
> Kenny Tilton wrote:
>
>> 2. (apply 'append decls) will suffice. but...
>
>
> According to Paul Graham reduce can be more efficient because apply uses
> &rest parameters when called like this.
Ahem. :) In this case, infinitessimally.
>
>> 3. ...why cons up a new list?
>>
>> (dolist (decl decls)
>> (dolist (el decl)
>> (setf (gethash el decl-hash) nil)))
>
>
> Thanks!
> I just didn't get this habit yet to look for excessive consing.
I reworked things a little (and fixed a bug):
(defun topo-sort (data &aux (cycle (find-cycle data)))
(if cycle
(values nil cycle)
(flet ((independent-of (x y)
(not (find y (assoc x data)))))
(sort (reduce 'union (mapcar 'copy-list data))
#'independent-of))))
(defun find-cycle (data)
(labels ((dependencies (element)
(cdr (assoc element data)))
(depends-on (i d)
(unless (eql i d)
(or (when (find d (dependencies i))
(list i d))
(some (lambda (d2)
(depends-on i d2))
(dependencies d))))))
(loop for (element . dependencies) in data
when (some (lambda (d)
(depends-on d element)) dependencies)
return it)))
(topo-sort '((a b c) (b d)(d c)(c b)))
=> nil (c b)
(topo-sort '((a b c) (b d)(d c)))
=> (c b d a)
--
Kenny
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film
"If you plan to enter text which our system might consider to be
obscene, check here to certify that you are old enough to hear the
resulting output." -- Bell Labs text-to-speech interactive Web page
Kenny Tilton wrote:
>
>
> V.Ch. wrote:
>
>> Kenny Tilton wrote:
>>
>>> 2. (apply 'append decls) will suffice. but...
>>
>>
>>
>> According to Paul Graham reduce can be more efficient because apply
>> uses &rest parameters when called like this.
>
>
> Ahem. :) In this case, infinitessimally.
>
>>
>>> 3. ...why cons up a new list?
>>>
>>> (dolist (decl decls)
>>> (dolist (el decl)
>>> (setf (gethash el decl-hash) nil)))
>>
>>
>>
>> Thanks!
>> I just didn't get this habit yet to look for excessive consing.
>
>
> I reworked things a little (and fixed a bug):
>
> (defun topo-sort (data &aux (cycle (find-cycle data)))
> (if cycle
> (values nil cycle)
> (flet ((independent-of (x y)
> (not (find y (assoc x data)))))
Sorry, should be (cdr (assoc x data))
kt
--
Kenny
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film
"If you plan to enter text which our system might consider to be
obscene, check here to certify that you are old enough to hear the
resulting output." -- Bell Labs text-to-speech interactive Web page
Kenny Tilton wrote:
> I reworked things a little (and fixed a bug):
Thanks, I'll look at the code tomorrow. The only thing that worries me
now is that you use loop, and I decided to stay away from this form for
now for it's not for a newbie.
V.Ch. wrote:
> Kenny Tilton wrote:
>
>> I reworked things a little (and fixed a bug):
>
>
> Thanks, I'll look at the code tomorrow. The only thing that worries me
> now is that you use loop, and I decided to stay away from this form for
> now for it's not for a newbie.
Oh, you read that thread? :)
Hmmm, the latest version does not use loop, but I would not call it
newby-ese, either.
--
Kenny
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film
"If you plan to enter text which our system might consider to be
obscene, check here to certify that you are old enough to hear the
resulting output." -- Bell Labs text-to-speech interactive Web page
+ "V.Ch." <····@not.real>:
| The only thing that worries me now is that you use loop, and I
| decided to stay away from this form for now for it's not for a
| newbie.
Nah. The simpler uses of loop are perfectly newbie-friendly. Just
learn loop a little at a time, taking care that you understand what
each feature does as you're learning it, and work hard to avoid
pushing the boundaries of your understanding. (Those boundaries /are/
to be pushed, not be experimenting while you code, but by
understanding how the loop macro is /supposed/ to work.
Implementations often allow constructs that the standard frowns upon,
so there are indeed dangers lurking, but nothing serious as long as
you swim near the shore.)
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
>>> 2. (apply 'append decls) will suffice. but...
>> According to Paul Graham reduce can be more efficient because apply
>> uses &rest parameters when called like this.
> Ahem. :) In this case, infinitessimally.
I haven't reviewed the OP's code, but I would expect #'append to be a
special case in which (reduce #'append arg) to be worse than (apply
#'append arg), for the following-two reasons.
1. When using a many-arg append, the append can keep a tail pointer
throughout the operation, instead of having to traverse its
argument lists each time.
2. When using reduce, append conses up a new list for the accumulator
each time it's called. In the following example, I'm going to use
the #n= notation to follow some cons cells around.
(reduce #'append '('#1=(1 2 3) '#2=(4 5 6) '#3=(7 8 9)))
effectively reduces as:
(append (append '#1# '#2#) '#3#)
(append '#4=(1 2 3 . #2#) '#3#) ;; new (1 2 3 ..) consed.
'#5=(1 2 3 4 5 6 . #3#) ;; new (1 2 3 4 5 6 ..) consed.
Note that #4# is an intermediate list, and is consed only to be
gc'd. We really could have reused its conses in #5#, but didn't.
Calling (apply #'append ...) could, given a reasonably useful
implementation of append, reuse these.
It could be argued that the above two reasons are really the same
reason wearing a different hat. Somebody who wants to bring that up
should note that using nconc would have the first problem, but not the
second. (It would, of course, have all the usual problems with
nconc.)
We can possibly get the best of both worlds by using reduce's
:from-end parameter. This avoids the inefficiency of &rest, the
problems I stated above, and also doesn't run into troubles with
call-arguments-limit.
I suppose the moral here is that we can't blindly make sweeping
assertions about efficiency; some knowledge of what we're working with
is required. This would mean that since I didn't actually look at the
original code and don't know the circumstances of how append is being
called, I should really sit down and shut up.
Cheers,
joelh
Joel Ray Holveck <·····@juniper.net> writes:
> It could be argued that the above two reasons are really the same
> reason wearing a different hat. Somebody who wants to bring that up
> should note that using nconc would have the first problem, but not the
> second. (It would, of course, have all the usual problems with
> nconc.)
Some of the usual problems could be avoided with :KEY #'COPY-LIST.
The tail-pointer problem would still remain.
(reduce #'nconc sequence-of-lists :key #'copy-list :from-end t)
(reduce #'append sequence-of-lists :from-end t :initial-value '())
The difference between these two forms seems to be that NCONC
happily ignores the final atom of dotted lists.
> Some of the usual problems could be avoided with :KEY #'COPY-LIST.
True, although that does copy one list that it doesn't have to (the
last one).
joelh
"V.Ch." <····@not.real> writes:
> Is heavy use of lambdas considered bad style or not?
It's old-fashioned. Long ago, it was essential to program that way
since there was no serious alternative. Ever since LET was
introduced, though, it was preferred over LAMBDA combinations
by most people, mostly because it makes programs execute forward
instead of backward, which was thought to be a good thing.
That is, in the olden days, we used to write:
((lambda (...) (this is done last))
((lambda (...) (this is done next to last))
((lambda (...) (this is done second from last))
(this is done first))))
It was a lot clearer to write
(let* ((... (this is done first))
(... (this is done second from last))
(... (this is done next to last)))
(this is done last))
And as to passing things as parameters, that's done a lot in Scheme,
less in CL. In CL, it's more common to use keywords. That is,
instead of
(sort x (lambda (x y) (< (frob x) (frob y))))
as you might say in Scheme, Lispers often write
(sort x #'< :key #'frob)
> I found myself
> writing lambdas quite often, but the code looks absolutely
> hair-raising. (However, practically every piece of Lisp code looks
> hair-raising to me at the moment, so it's not very useful indicator
> ;). For instance, is it ok to use nested lambdas?
This is an ambiguous question. Do you mean lambda EXPRESSIONS, as in:
(funcall (funcall (lambda (y) (lambda (x) (+ x y))) 3) 4)
or do you mean nesting lambda COMBINATIONS, as in the example at the top
of this message?
The answer is that it depends on your goal. Sometimes a function is
quite clear. e.g.,
(mapc (lambda (x) (print (car x) *foo-stream*)) z)
is clearer than most alternatives.
> Should I convert such code into (labels...) forms or even into normal
> functions?
I wouldn't necessarily do this unless circumstance demands it.