[Q] More beginner help
Dirt
I am trying to "unravel" a list, but with little luck. I wish to
take a list such as:
( a ( b c ( d e ) ) f )
and create a new list that looks like one top level list:
( a b c d e f )
I am trying to do this recursively but I am guessing I am way off
because I get a stack overflow. What I am trying to say in my code
below is:
If the expression is a list, call the function again with the
cdr of the list, otherwise it is an atom so cons it to a list.
( defun f ( expr )
( cond
( ( listp expr ) ( f ( cdr expr ) )
( t ( cons expr nil ) ) )
)
)
Thanks,
Dirt
Marius Vollmer
> I am trying to do this recursively but I am guessing I am way off
> because I get a stack overflow. What I am trying to say in my code
> below is:
>
> If the expression is a list, call the function again with the
> cdr of the list, otherwise it is an atom so cons it to a list.
>
> ( defun f ( expr )
> ( cond
> ( ( listp expr ) ( f ( cdr expr ) )
> ( t ( cons expr nil ) ) )
> )
> )
Look at this:
USER(1): (listp nil)
T
USER(2): (cdr nil)
NIL
USER(3): (consp nil)
NIL
USER(4):
Now try to imagine what your function does with an ordinary list, and
where it gets stuck. Understanding this will not give you a solution
to your original problem, but you will understand why you get a stack
overflow.
- Marius
Erik Naggum
code. parentheses are _not_ visually significant, although they are very
syntactically significant, in Lisp source code. don't make them stand
out -- please -- you're code is so ugly it's hard to help you with it. ]
* Dirt <pi...@inam3.com>
| I am trying to "unravel" a list, but with little luck. I wish to take a
| list such as:
|
| (a (b c (d e)) f)
|
| and create a new list that looks like one top level list:
|
| (a b c d e f)
this is normally called "flattening" a list.
| I am trying to do this recursively but I am guessing I am way off because
| I get a stack overflow. What I am trying to say in my code below is:
|
| If the expression is a list, call the function again with the cdr of the
| list, otherwise it is an atom so cons it to a list.
what you wish to do is to move each element of each list you encounter
onto a new list. I'll try to show you with slightly more modern Common
Lisp that you're using:
(defun flatten (list)
(loop for element in list
if (listp element) nconc (flatten element)
else collect element))
if you actually _need_ recursion, which will only waste space and time,
you should be able to unravel this iterative solution easily. in my not
so humble opinion, being able to think recursively is very valuable, the
second most valuable ability you can have, beaten only by knowing _when_
to use recursion.
incidentally, this function considers an empty list a list of no elements
while you might want NIL to be a separate element in the resulting list.
#:Erik
Constantine Vetoshev
> (defun flatten (list)
> (loop for element in list
> if (listp element) nconc (flatten element)
> else collect element))
>
> if you actually _need_ recursion, which will only waste space and time,
> you should be able to unravel this iterative solution easily. in my not
> so humble opinion, being able to think recursively is very valuable, the
> second most valuable ability you can have, beaten only by knowing _when_
> to use recursion.
Learning Lisp in an academic environment (as I did) tends to breed
distrust of looping constructs. (Especially considering that Common
Lisp is not the Lisp dialect of choice for teaching purposes.) I agree
that your solution above is simple and efficient, but I think the
original poster's wish was to have a solution that utilizes as few
``advanced'' features of CL as possible. (I seriously doubt that his
class covered loop at this point :) That said, here is a purely
recursive Scheme-like solution:
(defun flatten (l)
(cond ((endp l) ())
((listp (car l)) (append (flatten (car l))
(flatten (cdr l))))
(t (cons (car l) (flatten (cdr l))))))
Pierre De Pascale
> what you wish to do is to move each element of each list you encounter
> onto a new list. I'll try to show you with slightly more modern Common
> Lisp that you're using:
>
> (defun flatten (list)
> (loop for element in list
> if (listp element) nconc (flatten element)
> else collect element))
>
> if you actually _need_ recursion, which will only waste space and time,
> you should be able to unravel this iterative solution easily. in my not
> so humble opinion, being able to think recursively is very valuable, the
> second most valuable ability you can have, beaten only by knowing _when_
> to use recursion.
>
> incidentally, this function considers an empty list a list of no elements
> while you might want NIL to be a separate element in the resulting list.
>
> #:Erik
Actually your solution is recursive. Look that in your loop construct
you call (recursively) FLATTEN depending on the type of ELEMENT. This
is clearly a case of recursion.
The use of a loop construct if not sufficient to say that the
algorithm is iterative. I guess I should clearly define the concept of
iteration/recursion. Seeing a function calling itself in its body is
sometime a good hint for recognizing recursion.
Flattening a list cannot be done without some kind of recursion, be it
explicit (a function calling itself) or implicit (building some
intermediate stack to simulate recursion).
Has someone a truly iterative solution for this ? I know you could CPS
the program and end up with a tail recursive solution. But this does
not count as you are implicitly building a call stack.
- Pierre.
Erik Naggum
| Actually your solution is recursive. Look that in your loop construct you
| call (recursively) FLATTEN depending on the type of ELEMENT. This is
| clearly a case of recursion.
you're right, of course. the recursion that I find silly, and therefore
reacted to, is using recursion to traverse lists, or recursing on the
CDR. for the sake of argument, I ignored the recursion on the CAR. I
think you made a good point for why that shouldn't be done.
#:Erik
Marius Vollmer
> (defun flatten (list)
> (loop for element in list
> if (listp element) nconc (flatten element)
> else collect element))
>
> if you actually _need_ recursion, which will only waste space and time,
> you should be able to unravel this iterative solution easily.
Hmm, isn't your code above already recursive? Actually, it is both
recursive and iterative: it iterates over the elements of a list and
recurses when it encounters a nested list.
Robert Monfera
Constantine Vetoshev wrote:
> I think the
> original poster's wish was to have a solution that utilizes as few
> ``advanced'' features of CL as possible. (I seriously doubt that his
> class covered loop at this point :) That said, here is a purely
> recursive Scheme-like solution:
Maybe Erik's intention was to make Dirt think about a solution rather
than to help him cheat.
Robert
Bernhard Pfahringer
Pierre De Pascale <d...@siemens.ch> wrote:
>
>Flattening a list cannot be done without some kind of recursion, be it
>explicit (a function calling itself) or implicit (building some
>intermediate stack to simulate recursion).
>
>Has someone a truly iterative solution for this ? I know you could CPS
>the program and end up with a tail recursive solution. But this does
>not count as you are implicitly building a call stack.
>
for destroying the input-tree in-place:
(defun nflatten (list)
"Flattens LIST and all its sublists. Destructive!"
(loop with point = list
for item = (first point)
while point
do
(if (consp item)
;;; lift car, splice in cdr
(setf (car point) (car item)
(cdr point) (nconc (cdr item) (cdr point)))
;;; else move on
(setf point (rest point))))
list)
--
--------------------------------------------------------------------------
Bernhard Pfahringer, OeFAI http://www.ai.univie.ac.at/~bernhard/
--------------------------------------------------------------------------
iSteve: i is iCeo in iApple. You'll be iified. iResistance is inVain.
Dirt
<snip>
>
>Maybe Erik's intention was to make Dirt think about a solution rather
>than to help him cheat.
How is asking for help cheating? I attempted to construct a solution,
then posted that, asking for guidance. I did not once ask for anyone
here to do my work.
I find it quite discouraging to see comments such as yours. Is this
not a learning enviroment? Don't ask!! Don't learn!! Your Bad!!!
Your comments are unwarranted and unappreciated.
Dirt
Thomas A. Russ
>
> Hello,
> I am trying to "unravel" a list, but with little luck. I wish to
> take a list such as:
>
> I am trying to do this recursively but I am guessing I am way off
> because I get a stack overflow. What I am trying to say in my code
> below is:
>
> If the expression is a list, call the function again with the
> cdr of the list, otherwise it is an atom so cons it to a list.
>
> ( defun f ( expr )
> ( cond
> ( ( listp expr ) ( f ( cdr expr ) )
> ( t ( cons expr nil ) ) )
> )
> )
There are two separate issues with your code. The first one explains
why you get a stack overflow. Stack overflows usually result when your
code goes into an infinite recursion.
(listp NIL) => T
(cdr NIL) => NIL
NIL is the empty list and the first clause of your cond will recursively
call itself on successive CDRs of the input list until it reaches the
end of the list (NIL), and then it will repeatedly call itself on NIL
until you run out of stack space.
The second problem is that there is no assembly of the parts of the
solution from the recursive call to the function. I should also point
out that there is also no processing of the CAR of the input argument
when it is a list.
One way to understand what is happening with your code is to step
through a simple example of the input by hand (or using a combination of
doing it by hand and typing things in) and seeing what happens.
For example, start with '((a) b) as input.
(listp '((a) b)) => T
(cdr '((a) b)) => (B) ;; recurse now
(listp '(b)) => T
(cdr '(b)) => NIL ;; recurse now
(listp NIL) => NIL
(cdr NIL) => NIL ;; recurse now
etc.
This will both help you understand what is happening as well as give you
some clues as to how to change your function to get the results that you
want.
--
Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu
Robert Monfera
Hi Dirt
Please interpret more carefully what was said.
Robert
(Private mail was returned)
Erik Naggum
| I find it quite discouraging to see comments such as yours. Is this
| not a learning enviroment? Don't ask!! Don't learn!! Your Bad!!!
attempting to use USENET for homework has long traditions and only
marginally shorter traditions of rebuke, hostile reactions, and general
ill feelings in return. when you ask for help in solving really simple
problems that any good textbook alredy explains well, you're putting
yourself in the homework category, whether you are doing homework on the
Net or not. defensive reactions _reinforce_ that impression strongly.
if you want to learn something from the net, be prepared to listen to
_all_ the answers you get. criticism is always well intended at first,
but the stupid, destructive people who insist on defending themselves
whenever something they do is criticized and on attacking people "back"
who never actually attacked them, make this a very strenous medium for
such people. you see, people who are attacked this way are _not_ going
to give you any benefit of the doubt: you are clearly guilty of hostile
activities towards others, and if you respond strongly to such attacks,
so will everybody else. if you feel unfairly attacked, consider the fact
that you attack others unfairly on purpose when you attack them for
having behaved badly towards you. in short, stupid people escalate a
normal process of mild correction and attitude readjustment into flames
and out-and-out hostilities. the solution is obvioulsy to get rid of the
stupid people, but until we can do that, all we can do is ask people to
stop behaving stupidly.
instead of getting worked up over criticism you don't understand, strive
to understand what made it arise in the first place. most of the time,
it has simple, straightforward reasons that you can easily change, and
which it would be incredibly stupid of you not to change, because that
means you don't listen and really _are_ stupid, like one particular dude
here who never listens to anything he doesn't already agree to, and who
accuses those who try to readjust his attitude of being psychopaths and
maniacs, which only proves that he's just as retarded as they think he is.
incidentally, this is not really a learning environment. it's really an
environment for sharing ideas and experiences with others. the helping
and _learning_ part is the result of motivating those who have something
that you need to share it. you don't do that by looking like you're
doing homework on the Net. you can't change that by accusing people of
holding stupid attitudes like "Don't ask!! Don't learn!! Your Bad!!".
so wise up, and behave like you're asking and learning and taking part in
this environment, not just exploiting it and wasting people's time by not
doing your homework _between_ articles you post to this forum. note the
"behave like" -- nobody cares what you actually _do_ or _think_, as they
can't see that in your articles and can't react to it unless they make
the grave error of pretending to see people's thoughts across the net.
(do notice how you make this mistake.)
#:Erik
Jon K Hellan
> attempting to use USENET for homework has long traditions and only
> marginally shorter traditions of rebuke, hostile reactions, and general
> ill feelings in return. when you ask for help in solving really simple
> problems that any good textbook alredy explains well, you're putting
> yourself in the homework category, whether you are doing homework on the
> Net or not. defensive reactions _reinforce_ that impression strongly.
etc.
This would have been an appropriate response if Dirt had asked a
typical
"How do I <insert easily recognizable textbook problem> ?"
But that's not what he did.
He proposed a solution, asked for comments, got some, and responded
intelligently to those. He never tried to hide the fact that he was
doing homework, in fact it was obvious that he was working very hard
at it.
I think Dirt should be welcome on the net.
Jon
Erik Naggum
| This would have been an appropriate response if Dirt had asked a
| typical
sigh.
Dirt's reaction would have been appropriate if anyone had actually
accused him of any wrong-doing. I'm trying to tell him (and now you),
that you have to _listen_ to what people are saying, not just react to
what _you_ feel. please heed my advice, or heed my secondary advice:
shut up if you have nothing to contribute.
| I think Dirt should be welcome on the net.
your implication that somebody thinks he is not is insulting. quit it.
#:Erik
Bulent Murtezaoglu
I would have agreed with Erik a few years ago. I still think a good
amout of learning results from frustration and [re-]reading not-so-well
presented material in solitude, but "Dirt" did use the resources available
to him appropriately. Whether he would have learned more had he let himself
be frustrated and figure it out by himself seems to be a moot point in this
day and age. He had the right approach to get people's time and attention,
which in itself might be an equally valuable skill as extracting crucial
insights from lectures and books. As a bonus he also got filled in on
eq vs. = issues for number comparison which apparently his teacher failed
to clarify.
The interaction was not inaproppriate, it was just good fruitful use of
modern resources. His next step is learning to complement his skill
in tapping into this knowledge with the acquisition of thicker skin for
on-line disapproval. I think this newsgroup is up to helping him with
that also!
cheers,
BM
Frank A. Adrian
Bernhard Pfahringer <bern...@hummel.ai.univie.ac.at> wrote in message
news:86ig06$3rb8$1...@www.univie.ac.at...
> Well, the following is pretty close to iterative, if you allow
> for destroying the input-tree in-place:
>
> (defun nflatten (list)
> "Flattens LIST and all its sublists. Destructive!"
> (loop with point = list
> for item = (first point)
> while point
> do
> (if (consp item)
> ;;; lift car, splice in cdr
> (setf (car point) (car item)
> (cdr point) (nconc (cdr item) (cdr point)))
> ;;; else move on
> (setf point (rest point))))
> list)
OUCH! This is one of those places where the cure is worse than the disease!
This IS code that illustrates that you can do anything iteratively that you
can do recursively, as long as you are willing to ignore style, clarity, and
cleanliness. Very interesting, but it makes my brain hurt just looking at
it. I guess Lisp is better for allowing you to do these things, but
sheesh... If I saw this code in a student's assignment, I'd probably (a)
barf and (b) wonder if I'd been teaching them anything.
faa
Robert Monfera
Jon K Hellan wrote:
[...]
> This would have been an appropriate response if Dirt had asked a
> typical
>
> "How do I <insert easily recognizable textbook problem> ?"
>
> But that's not what he did.
No, he posted this:
( defun f ( expr )
( cond
( ( listp expr ) ( f ( cdr expr ) )
( t ( cons expr nil ) ) )
)
)
It's not eq to the 'How do I?' question, but it is much closer to this
than to an almost-finished, hard-fought solution on which substantial
_thinking_ time was spent and which needs a small 'gotcha' type of
correction.
> He never tried to hide the fact that he was doing homework [...]
More accurately, he didn't say it was not homework.
Erik had a valid point about Dirt utilizing other people's time instead
of opening a textbook or just doing a simple search on what's available
on the web. It does not matter what we think about it though, because
there will always be people doing it, and it's everyone's own business
to help them. Also, there is a blurred line between helping and solving
homework (strictly speaking, the very point of homework is to make
people think hard, sweat and struggle solitarily in an effort to pump
the way of thinking into students' brains).
In response to postings from people offering subtle help, someone posted
the final, recursive solution off the bat. There is no way of _making_
someone adept at attacking problems with recursive code or divide et
impera methods just by solving their homework. Dirt may or may not have
skipped the solution, but it definitely let him shortcut the gist of the
homework assignment (for which there is a word invented).
Robert
Bulent Murtezaoglu
[no common lisp content whatsoever!]
>>>>> "RM" == Robert Monfera <mon...@fisec.com> writes:
[...]
RM> Right, depending on the meaning of fruitful. In an
RM> educational setting the distinguished meaning may be different
RM> from what you have in mind.
Hmm. I kind of follow this, but not completely. I was using 'fruitful'
in the sense that he _did_ learn something and possibly more than he
would have had he not posted.
RM> Studying and 'easy' are
RM> oxymorons. If they weren't, someone would be able to redefine
RM> the meaning of studying simply by adding hard work to the
RM> recipe.
In my personal experience with my brief and not-so-successful attepts
at both academic teaching and 'training' I have concluded that unless
one has a semi-gifted teacher, learning of novel concepts happen _by
accident_. Happily I was better at learning, but I could certainly
sense when I was being succesfully taught, and when I was stumbling
upon enlightenment. As far as I can see this happy accident of
'getting it' usually happens after long hours of dead-ends and
frustration. I tend to infer a vague causal connection between the
two and thus do value the hard work part of learning. Accepting and
understanding the hard part of learning as a necessary evil is
valuable in itself and ought to be learned. Having said that, I also
think one should not discount the value of a nudge here, a hint there
also as practical means of getting people to the light. Maybe the ng
did go a bit further than I first thought in that last regard though.
RM> 'Assisted homework solving' wasn't made possible by the advent
RM> of Internet; in the past, students mainly interested in the
RM> deliverable could easily ask around and/or copy it among their
RM> classmates (practicing their interpersonal skills :-),[...]
Of course, but presumably getting help from a set of skilled people
spread all over the world is in an altogether different league than
simple collective homework attempts among peers. People could always
ask others in physical proximity, but it is only recently that they
could ask questions to a concentrated collection of experts in the
field of their problem without leaving their desks. _That_ is what
is new and I think being able to tap into that is a very worthwhile
skill.
RM> ... Learning and other
RM> cognitive processes of the brain remained the same, never mind
RM> the new channels. Even Gutenberg did not manage to do away
RM> with the sweat on students' forehead!
I think we are in agreement in general but disagreeing on our
perception of how much of the learning process he went though before
posting. I am willing to concede that maybe I was quick to assume
enough energy was expended before posting. I do not agree with the
(possibly tongue-in-cheek) Gutenberg analogy, unless Gutenberg also
managed to press the authors and their peers into the books.
RM> ... If someone thinks he can just
RM> turn to the web for a quick solution during school and work,
RM> then what's the point of attending the course in the first
RM> place?
Actually this question is not rhetorical! What indeed? Unless, of
course, one has a good teacher which I am not convinced can be replaced.
RM> By approving his way of problem solving, you may give
RM> Dirt a false sense of security about its essence.
I intended no such thing! I hope Dirt understands that. What should
be understood is that Usenet, without the wherewithall to filter it,
is useless and might be harmful. You may break your car by reading
rec.auto newsgroups, you may damage your file system if you believe
the linux newsgroups, and we just may make sure you end up igorant and
out of your tuition money at c.l.l.!
[...]
RM> This skin thickening thing may work even if he just thinks he
RM> was nailed down! (Dirt with thick skin?!?!)
If you're gonna go there: Dirt?!
cheers,
BM
Robert Monfera
Hi Bulent,
You wrote:
[Various thoughts elided]
> The interaction was not inaproppriate, it was just good fruitful use of
> modern resources.
Right, depending on the meaning of fruitful. In an educational setting
the distinguished meaning may be different from what you have in mind.
Studying and 'easy' are oxymorons. If they weren't, someone would be
able to redefine the meaning of studying simply by adding hard work to
the recipe.
'Assisted homework solving' wasn't made possible by the advent of
Internet; in the past, students mainly interested in the deliverable
could easily ask around and/or copy it among their classmates
(practicing their interpersonal skills :-), while keeping the risk of
getting caught lower. Learning and other cognitive processes of the
brain remained the same, never mind the new channels. Even Gutenberg
did not manage to do away with the sweat on students' forehead!
The importance of learning has always been a distinguished part of our
value system (except dark ages), and it is especially true in the
information society, which has a lower need for dock workers etc.. If
someone thinks he can just turn to the web for a quick solution during
school and work, then what's the point of attending the course in the
first place? By approving his way of problem solving, you may give Dirt
a false sense of security about its essence.
> His next step is learning to complement his skill
> in tapping into this knowledge with the acquisition of thicker skin for
> on-line disapproval. I think this newsgroup is up to helping him with
> that also!
This skin thickening thing may work even if he just thinks he was nailed
down! (Dirt with thick skin?!?!)
Regards
Robert
Robert Monfera
Hi Bulent,
I appreciate your thoughts and just like to hang around for a little
more.
Bulent Murtezaoglu wrote:
> In my personal experience with my brief and not-so-successful attepts
> at both academic teaching and 'training' I have concluded that unless
> one has a semi-gifted teacher, learning of novel concepts happen _by
> accident_.
I was often thinking of learning as a way to _force_ the brain to
compress facts and information on a subject. The better the
compression, the higher the chance that the essence of the subject is
captured. What is difficult for me to see is how this compression can
happen without pressure. This pressure may come from various sources.
Going to school or doing certain types of jobs is an acceptance of
subjecting oneself to pressure. Another source is internal motivation.
Accidents only happen if there is velocity, weight and drag. If a piece
of molten plastic drops into a mint form, it may accidentally fill all
the fine details of the mint, but it is standard practice to make it
happen with pressure. Also, accidental great discoveries were usually
preceded by years or tens of years of hard and possibly fruitless work.
> Happily I was better at learning, but I could certainly
> sense when I was being succesfully taught, and when I was stumbling
> upon enlightenment. As far as I can see this happy accident of
> 'getting it' usually happens after long hours of dead-ends and
> frustration. I tend to infer a vague causal connection between the
> two and thus do value the hard work part of learning.
We say the same here, except maybe the strength of correlation.
> [...] getting help from a set of skilled people
> spread all over the world is in an altogether different league than
> simple collective homework attempts among peers.
[...]
> _That_ is what
> is new and I think being able to tap into that is a very worthwhile
> skill.
Yes, it is definitely more efficient, not only because of the global
pool of possible responders but also their often deep knowledge. c.l.l.
is not a moderated learning channel though, and the solution is usually
given away quickly before seeing working code from the OP. As for the
skills required to post a question to a newsgroup, and its relative
weight compared to the skill of systematic thinking or brainstorming in
a team, our opinion seemingly differs :-)
> I do not agree with the
> (possibly tongue-in-cheek) Gutenberg analogy, unless Gutenberg also
> managed to press the authors and their peers into the books.
In fact some thinkers of the time were worried that people will lose
their memory, because the mass availability of books eliminates the need
to remember. It was partially justified, as these days parents have the
option to tell tales from books rather than from memory, amongst more
beneficial examples. Even though printing books was a revolution quite
comparable with the current Internet revolution, the need to use our
brains has only increased since then as well as the time spent in the
classroom.
And _your_ suspicion is not rhetorical either; in a sense (or 'in
essence'?) Gutenberg did press the authors into the book, while peers
could share thoughts via side notes!
Robert
Marc Cavazza
> incidentally, this is not really a learning environment. it's really an
> environment for sharing ideas and experiences with others. the helping
> and _learning_ part is the result of motivating those who have something
> that you need to share it.
Actually, I quite agree with Erik. But it is always interesting to examine the
diversity of programming styles of those who provide solutions even to simple
"homework-like" problems, because they raise style issues.
If I have not missed anything, no one suggested (yet) the textbook-based
"flatten" function using an accumulator:
(defun flatten (tree & optional accumulator)
(cond ((null tree) accumulator)
((atom tree) (cons tree accumulator))
(T (flatten (first tree) (flatten (rest tree) accumulator)))))
Incidentally, I found no detectable improvement in performance (on a real-world
program) when using it instead of the "standard" tree-recursive version (this
was some time ago, but I justed checked again with Allegro 5.0).
Marc
Pierre R. Mai
> If I have not missed anything, no one suggested (yet) the textbook-based
> "flatten" function using an accumulator:
>
> (defun flatten (tree & optional accumulator)
> (cond ((null tree) accumulator)
> ((atom tree) (cons tree accumulator))
> (T (flatten (first tree) (flatten (rest tree) accumulator)))))
A couple of possible reasons why no-one has proposed this:
- Exposing your internal accumulator via the external interface of
your function is not only very ugly, it's also error prone and
invites mis-use, which will later make it nearly impossible to
change the implementation of flatten!
A better implementation would IMHO use an internal helper function:
(defun flatten (tree)
"Docstring here <g>"
(labels ((flatten-internal (item accumulator)
(typecase item
(null accumulator)
(cons
(flatten-internal
(car item)
(flatten-internal (cdr item) accumulator)))
(t (cons item accumulator)))))
(flatten-internal tree nil)))
This has the additional benefit that many compilers can make more
agressive optimizations on flatten-internal (no optional args, and
especially, not globally visible, i.e. you don't have to go through
the value cell of the symbol, and it can't be redefined):
On CMUCL with (optimize (speed 3)) the two versions differ markedly:
10000 times flatten-bad of '((a b (c d) e) f (g (h (i))))
Evaluation took:
1.27 seconds of real time
0.93 seconds of user run time
0.08 seconds of system run time
[Run times include 0.3 seconds GC run time]
0 page faults and
9975800 bytes consed.
vs.
10000 times flatten of '((a b (c d) e) f (g (h (i))))
Evaluation took:
0.09 seconds of real time
0.05 seconds of user run time
0.03 seconds of system run time
0 page faults and
1043568 bytes consed.
> Incidentally, I found no detectable improvement in performance
> (on a real-world program) when using it instead of the "standard"
> tree-recursive version (this was some time ago, but I justed
> checked again with Allegro 5.0).
- Outside of textbooks, simple flattening is usually a very rare
operation: Either you are traversing a tree or graph structure and
collecting the results of applying some operation to certain nodes
(in which case you'll try to combine the "flattening" operation with
the calculation), and/or you care about the order of traversal,
and/or you don't want to visit/process every node, and/or you are
using a different internal representation instead of lists, etc.
So few people spend time on writing flatten, and the few that do
(outside academic exercises) won't try to optimize their
implementation, because it won't matter. If it does matter, then
you should either think about using other representations, caching,
or any other more advanced technique to speed up your program.
Optimizing flatten (even algorithmically) is IMHO a case of
premature and wrong optimization...
Regs, Pierre.
--
Pierre Mai <pm...@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
Espen Vestre
> - Exposing your internal accumulator via the external interface of
> your function is not only very ugly, it's also error prone and
> invites mis-use, which will later make it nearly impossible to
> change the implementation of flatten!
In general, I find such use of 'labels' ugly.
My personal taste of style tells me that in simple cases where
the 'real' parameters are few and fixed, using optional parameters
for accumulating values is a good solution.
'labels' clutters the code and I don't like to use it just to 'hide'
functions, but would like to reserve it to functions which need the
lexical environment of the enclosing function.
Often, using a globally defined auxiliary function (with a package-
internal symbol as a name, of course) makes code easier to read
than defining too voluminous functions with 'labels'-functions.
So my personal style guide is:
- Use labels and flet for local functions which need the lexical environment
of the enclosing function.
- In some cases, you may use optional parameters for accumulating values
(but only in really simple cases - I don't want to argue whether
the case at hand is a good example)
- Otherwise, use auxiliary functions. In general, don't be afraid
to have a lot of top-level functions. It makes your code better
suited for small dynamic updates.
I'd like to hear other peoples opinion on this!
--
(espen)
Marc Cavazza
"Pierre R. Mai" wrote:
> Marc Cavazza <M.Ca...@bradford.ac.uk> writes:
>
> > If I have not missed anything, no one suggested (yet) the textbook-based
> > "flatten" function using an accumulator:
> >
> A couple of possible reasons why no-one has proposed this:
>
> - Exposing your internal accumulator via the external interface of
> your function is not only very ugly, it's also error prone and
> invites mis-use, which will later make it nearly impossible to
> change the implementation of flatten!
That's an interesting comment (BTW, I have diplomatically omitted the name of the
- quite famous - Textbook :-)
and the optimisations figures you sent are indeed convincing ...
> - Outside of textbooks, simple flattening is usually a very rare
> operation
I agree with the general comments. However in some (non-textbook) AI code, my view
is that you sometimes have to split up processing tasks when they start getting
too complex.
> Optimizing flatten (even algorithmically) is IMHO a case of
> premature and wrong optimization...
I think you're right. For different reasons, though. After profiling (on ACL) and
successfully optimising, I was trying to scavenge whatever remaining functions
could be optimised
Best,
Marc
Tim Bradshaw
> My personal taste of style tells me that in simple cases where
> the 'real' parameters are few and fixed, using optional parameters
> for accumulating values is a good solution.
I'd only ever do this if either the function was only called *very*
locally to its definition or I could rely on some (non-standard)
declaration to hide the spurious extra arguments from any `what args
does this function take' tool, because I don't ever want to spend time
thinking `what does that extra undocumented arg do?' In practice this
means I'd never do that.
> 'labels' clutters the code and I don't like to use it just to 'hide'
> functions, but would like to reserve it to functions which need the
> lexical environment of the enclosing function.
> Often, using a globally defined auxiliary function (with a package-
> internal symbol as a name, of course) makes code easier to read
> than defining too voluminous functions with 'labels'-functions.
I quite often use LABELS/FLET for some function which has complex
behaviour but where the aux functions are only ever called by the
outer function, and may have idiosyncratic calling conventions & so
on. In general if I have a function defined in a package I don't want
to have be worrying about documenting that it should only ever be
called from this other function and so on.
> - Otherwise, use auxiliary functions. In general, don't be afraid
> to have a lot of top-level functions. It makes your code better
> suited for small dynamic updates.
I disagree with this (small dynamic updates). If the aux functions
are only ever called from the global function then the only issue must
be compilation time, and I don't find that is a serious problem -- Any
modern Lisp system seems to be able to compile even quite large
functions in less time than it takes to type the `compile this'
command to the editor basically.
Of course if the aux functions are called from several *different*
top-level functions that's a whole other issue.
--tim
Robert Monfera
Hi Espen,
I usually opt for LABELS for cases similar to what was discussed. The
primary reason is not efficiency (that's a bonus), but the perceived
better structure of the program.
Even though you don't export the "real" function, only the interface,
it's not immediately apparent to readers (including yourselves) when
browsing through the code. I keep one function, and if it mostly
consists of a FLET or a LABELS, and maybe the last line is a call to it,
I immediately recognize the "pattern".
This way I don't have to worry about locating the real function, nor
about moving or changing both.
I perceive creating a global function as a mini, intra-package EXPORT,
and having one function stops me from having to think about the inner
function as a separate unit. If it becomes necessary, it will take very
little to turn it into a global function, so I don't feel I loose
anything. OTOH I don't have to worry as much about naming a FLET than
naming a global function.
Another way I reduce clutter on the "workspace" is the use of generic
functions, often even for built-in classes - there are fewer names to
worry about. I think there should be no more names than what you can
justify at the conceptual level.
Other arguments for two global functions is a little easier
debuggability and tracing, but I can cope without them. As an example,
the LWW debugger can highlight the source of FLET or show its innards if
I click on the frame (I could't figure it out with ACL yet) just as it
can functions.
To my taste, CL code written by others sometimes contain too many global
variables and functions, representing a wider, flatter and relatively
low-cohesion style. It does not stop me from figuring them out, and it
fades away as I get better and better in building the dependency
structures in my mind when reading the source. In particular, though, I
am against lots of top-level fuctions and consider it a sub-optimal
representation of the program structure (mainly for us, also for the
compiler), and it is a barrier to entry for all users of the code.
For specific reasons above and in Pierre's mail, my style guide is to
use FLET, LABELS if the use of a function is limited to only one
function, except when I _know_ I will need it soon for additional ones.
This is in line with my desire to modularize code. Of course, I'm not
dogmatic about it - it just felt more productive this way. I'm
interested in specific reasons that challenge this view.
Regards
Robert
Espen Vestre wrote:
>
> pm...@acm.org (Pierre R. Mai) writes:
>
> > - Exposing your internal accumulator via the external interface of
> > your function is not only very ugly, it's also error prone and
> > invites mis-use, which will later make it nearly impossible to
> > change the implementation of flatten!
>
> In general, I find such use of 'labels' ugly.
>
> My personal taste of style tells me that in simple cases where
> the 'real' parameters are few and fixed, using optional parameters
> for accumulating values is a good solution.
>
> 'labels' clutters the code and I don't like to use it just to 'hide'
> functions, but would like to reserve it to functions which need the
> lexical environment of the enclosing function.
>
> Often, using a globally defined auxiliary function (with a package-
> internal symbol as a name, of course) makes code easier to read
> than defining too voluminous functions with 'labels'-functions.
>
> So my personal style guide is:
>
> - Use labels and flet for local functions which need the lexical environment
> of the enclosing function.
>
> - In some cases, you may use optional parameters for accumulating values
> (but only in really simple cases - I don't want to argue whether
> the case at hand is a good example)
>
> - Otherwise, use auxiliary functions. In general, don't be afraid
> to have a lot of top-level functions. It makes your code better
> suited for small dynamic updates.
>
Pierre R. Mai
> pm...@acm.org (Pierre R. Mai) writes:
>
> > - Exposing your internal accumulator via the external interface of
> > your function is not only very ugly, it's also error prone and
> > invites mis-use, which will later make it nearly impossible to
> > change the implementation of flatten!
>
> In general, I find such use of 'labels' ugly.
Personally, I don't often write functions that way either, because I
prefer writing iterations using the apropriate looping constructs,
instead of writing them as tail-recursive functions, unless the
recursive approach is the more intuitive one for the particular
problem at hand.
If I write them, I often do use labels instead of an external defun,
when it is clear that the helper will only be intelligible as part of
the whole function and/or will only be used in this context.
Your preferences may of course differ in this regard, and I'd be
perfectly happy to see it written like this:
(defun flatten (tree)
(flatten-internal tree nil))
(defun flatten-internal (tree accumulator)
...)
> My personal taste of style tells me that in simple cases where
> the 'real' parameters are few and fixed, using optional parameters
> for accumulating values is a good solution.
I still disagree with this, though: Exposing an internal variable via
the public interface of a function _will_ inevitably lead to it
being misused -- in my humble experience. And once this happens,
there is no way you will be able to change the implementation
of flatten in a way that eliminates this optional parameter, without
causing distant code to fail. So you'll have to carry around this
optional parameter (and treat it correctly) in future versions. I
don't think that saving an extra defun or labels is worth that risk
and/or hassle.
Or to put it differently:
The lambda list of a public, exported function is part of the
interface of that function, which is set in stone. Any incompatible
change to that interface will cause problems, and should therefore be
avoided if humanly possible. Inviting future problems by including
unneeded stuff in this lambda list is therefore something I
discourage.
> Often, using a globally defined auxiliary function (with a package-
> internal symbol as a name, of course) makes code easier to read
> than defining too voluminous functions with 'labels'-functions.
I agree with this, actually. Putting large (> 10-15 lines) function
bodies inside a labels/flat form makes things very hard to read, and
should be avoided. In the example code I posted, I felt that this
threshhold had not been exceeded, though.
Pierre R. Mai
> > - Outside of textbooks, simple flattening is usually a very rare
> > operation
>
> I agree with the general comments. However in some (non-textbook) AI
> code, my view is that you sometimes have to split up processing
> tasks when they start getting too complex.
This might indeed be the case (I don't do much AI work nowadays), but
even then you'd probably fold some of the work into the flattening
operation -- which maybe you have abstracted out into a macro,
e.g. (define-flattening-operation foobar (node) (mumble node))) or
even
(define-traversal-operation foobar
(:reduce (node accumulator) (unify (mumble node) accumulator)
(:flatten-in-order)))
Johan Kullstam
> pm...@acm.org (Pierre R. Mai) writes:
>
> > - Exposing your internal accumulator via the external interface of
> > your function is not only very ugly, it's also error prone and
> > invites mis-use, which will later make it nearly impossible to
> > change the implementation of flatten!
>
> In general, I find such use of 'labels' ugly.
i don't. i rather like labels. unless i really want to expose and
exploit the &optional argument from outside the function, i use labels
in preference to &optional. it makes my intent more clear.
i am still very much a lisp neophyte so please correct me if i am
going down a bad path. i do concede that you may later change your
mind and that having optional around in the first place makes it
easier to do so. do we have any other opinions?
the way i see it, lisp can be used as a functional language. i figure
this means that functions should be as easy to use and manipulate as
regular variables. hence, if you'd use let to make more variables,
why not flet or labels when you want a local function?
--
J o h a n K u l l s t a m
[kull...@ne.mediaone.net]
Don't Fear the Penguin!
Pierre R. Mai
> i don't. i rather like labels. unless i really want to expose and
> exploit the &optional argument from outside the function, i use labels
> in preference to &optional. it makes my intent more clear.
Exactly.
> i am still very much a lisp neophyte so please correct me if i am
> going down a bad path. i do concede that you may later change your
> mind and that having optional around in the first place makes it
> easier to do so. do we have any other opinions?
Do you mean with the above that having optional arguments around _in
the language_ is a good thing, and makes changing your mind easier
later on? Yes.
If you meant that having the optional argument around in your function
definition, then that definitely makes changing your mind later on
more difficult, I'd say.
> the way i see it, lisp can be used as a functional language. i figure
> this means that functions should be as easy to use and manipulate as
> regular variables. hence, if you'd use let to make more variables,
> why not flet or labels when you want a local function?
There is an obvious _practical_ difference between variables and
functions: The initialisation forms for variables are usually quite a
bit shorter than the "initialisation forms" (i.e. function
definitions) of functions. Therefore having a couple of local
variables in a function is usually much shorter than having a couple
of local functions in a function. I agree with the sentiment that
including a number of lengthy local functions can make the top-level
function form difficult to navigate, read, understand and maintain.
Moderation and personal judgement seem to be called for...
Robert Monfera
"Pierre R. Mai" wrote:
> > Often, using a globally defined auxiliary function (with a package-
> > internal symbol as a name, of course) makes code easier to read
> > than defining too voluminous functions with 'labels'-functions.
>
> I agree with this, actually. Putting large (> 10-15 lines) function
> bodies inside a labels/flat form makes things very hard to read, and
> should be avoided. In the example code I posted, I felt that this
> threshhold had not been exceeded, though.
Long functions should usually be avoided, be they created by DEFUN or
LABELS. Ripping off a longish LABEL and making it a global function
makes little difference.
The unit of understanding is the same, no matter where a fuction is
defined (i.e., inside or before). I don't perceive a function with a
longish LABELS more difficult to read than two separately defined
functions. As you and others pointed it out earlier that with LABELS,
the intention becomes clearer about where the function is used -
regardless of length IMO. (I'd prefer 2-3 smaller LABELS instead of one
huge one in general.)
Robert
Johan Kullstam
> Johan Kullstam <kull...@ne.mediaone.net> writes:
>
> > i don't. i rather like labels. unless i really want to expose and
> > exploit the &optional argument from outside the function, i use labels
> > in preference to &optional. it makes my intent more clear.
>
> Exactly.
>
> > i am still very much a lisp neophyte so please correct me if i am
> > going down a bad path. i do concede that you may later change your
> > mind and that having optional around in the first place makes it
> > easier to do so. do we have any other opinions?
>
> Do you mean with the above that having optional arguments around _in
> the language_ is a good thing, and makes changing your mind easier
> later on? Yes.
>
> If you meant that having the optional argument around in your function
> definition, then that definitely makes changing your mind later on
> more difficult, I'd say.
this is not what i was trying to say. consider the commonplace case
of have wanting recursive function with accumulator. you can either
make a lables or use &optional. if you use &optional from the start,
you have the choice of sending an accumulator at even the initial
call. this can let you start processing half-way down the recursion.
think of a case where the initial part is either done already or
somehow tricky and done explicitly but the rest of the processing
would fit the standard model.
Espen Vestre
> I still disagree with this, though: Exposing an internal variable via
> the public interface of a function _will_ inevitably lead to it
> being misused -- in my humble experience.
Well, when I think of it, I agree ;-) I was overreacting to provoke a
discussion on alternatives to such uses of labels. In some cases,
when people fill up a function with labels, it will not fit into an
80x24 emacs buffer anymore, which makes it violate my CL readability
standards (btw, grepping through my old code, I actually discovered
that I had almost never really implemented accumulation with optional
parameters).
> And once this happens,
> there is no way you will be able to change the implementation
> of flatten in a way that eliminates this optional parameter, without
> causing distant code to fail. So you'll have to carry around this
> optional parameter (and treat it correctly) in future versions. I
> don't think that saving an extra defun or labels is worth that risk
> and/or hassle.
I agree, although the backwards-compatibility argument is most striking
as an argument for the use of keyword parameters. In fact, keyword
parameters are one of the most useful features of lisp when it comes
to writing extendible and maintainable software (if C++ and CORBA had
used it, they wouldn't have had those IDL version upgrade nightmares
that one hears of).
--
(espen)
Robert Monfera
Johan Kullstam wrote:
> this is not what i was trying to say. consider the commonplace case
> of have wanting recursive function with accumulator. you can either
> make a lables or use &optional. if you use &optional from the start,
> you have the choice of sending an accumulator at even the initial
> call. this can let you start processing half-way down the recursion.
> think of a case where the initial part is either done already or
> somehow tricky and done explicitly but the rest of the processing
> would fit the standard model.
I think you refer to memoization. If so, the caveat is that tight
recursions would generate an enormous number of values to put in the
hash table, so it's usually not worth the space. Memoizing would be
expensive anyway, because you would need to use the equal specializer
(for tree operations) in the hashing table (exception:
computationally-intensive calculations returning small values on short
recursions).
Memoization can sometimes be an argument _in favor of_ LABELS - when you
typically call the function on a value from a small set of values. In
this case, to memoize the factorial of 500, you do _not_ have to store
the factorial values of 499, 498, ...
Also, the use of LABELS does not rule out the use of an optional
argument in the function definition - you still end up with code that's
better optimized, because you let the compiler know that the inner
function has always got two arguments.
Robert
Robert Monfera
Espen Vestre wrote:
[...]
> In some cases,
> when people fill up a function with labels, it will not fit into an
> 80x24 emacs buffer anymore [...]
What's the practical difference if you have two functions, each (say) 20
lines long? Is it that you can easily jump onto the source of the
invoked function? How do you recurse if you made multiple consecutive
jumps? (I don't know how to do "backtracking" in emacs, and I cannot do
it in either the ACL or LispWorks IDE).
Robert
Jeff Dalton
> Of course if the aux functions are called from several *different*
> top-level functions that's a whole other issue.
Then you can write it like this:
(let (...things the local fns might need ...)
(labels (... aux functions ...)
(defun ...)
(defun ...)
...))
That sort of style is unusual in Common Lisp but fairly popular in
Scheme, though you have to do it differently because inner define
in Scheme defines a local fn.
-- jeff
Tim Bradshaw
> I think you refer to memoization. If so, the caveat is that tight
> recursions would generate an enormous number of values to put in the
> hash table, so it's usually not worth the space. Memoizing would be
> expensive anyway, because you would need to use the equal
> specializer (for tree operations) in the hashing table (exception:
> computationally-intensive calculations returning small values on
> short recursions).
And you can memoize labels too, if you want. I have a thing called
MEMOIZED-LABELS which does this, which I could clean up & post if
anyone is interested.
--tim
Christopher R. Barry
Tim Bradshaw
> Tim Bradshaw <t...@tfeb.org> writes:
>> And you can memoize labels too, if you want. I have a thing called
>> MEMOIZED-LABELS which does this, which I could clean up & post if
>> anyone is interested.
> I'll bite, since no one else did.
For what it's worth, here it is. This may still have nasties in it
related to file-compiling MEMOIZED-LABELS: it definitely used to. If
anyone uses it in anger I'd be interested to hear if it works (I never have).
--tim
--cut--
;;; -*- Mode: LISP; Base: 10; Syntax: ANSI-COMMON-LISP; Package: (MEMOIZE) -*-
;; File - memoize.lisp
;; Description - memoization
;; Author - Tim Bradshaw (tfb at lostwithiel)
;; Created On - 1995?
;; Last Modified On - Sun Feb 6 23:26:54 2000
;; Last Modified By - Tim Bradshaw (tfb at lostwithiel)
;; Update Count - 4
;; Status - Unknown
;;
;; $Id$
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; * Memoization
;;; Norvig p269-275
;;; Copyright Tim Bradshaw 1995-2000. Do with this what you will.
(cl:defpackage "MEMOIZE"
(:use "CL")
(:export "MEMOIZE-FUNCTION"
"UNMEMOIZE-FUNCTION" "UNMEMOIZE-FUNCTIONS"
"CLEAR-MEMOIZED-FUNCTION" "CLEAR-MEMOIZED-FUNCTIONS"
"FUNCTION-MEMOIZED-P"
"DEF-MEMOIZED-FUNCTION"
"MEMOIZED-LABELS"))
(cl:in-package "MEMOIZE")
(cl:provide "MEMOIZE")
(defvar *memoized-functions* '()
;; stores an alist of (name table old-def)
)
(defun make-memo (fn key test)
;; Return wrapper & table
(declare (type function fn key test))
(let ((table (make-hash-table :test test)))
(values
#'(lambda (&rest args)
(declare (dynamic-extent args))
(let ((k (funcall key args)))
(multiple-value-bind (val found-p) (gethash k table)
(if found-p
val
(setf (gethash k table)
(apply fn args))))))
table)))
;;; semi user-interface fns
(defun memoize-function (fn-name &key (key #'first) (test #'eql))
"Memoize FN-NAME, a symbol, causing its results to be stashed.
KEY is a function which is given the arglist of FN-NAME, and should return
a key to hash on for memoizing. TEST is a function which the test for the
ashtable.
See Norvig P269-275.
Note this function may not work on self-recursive functions because the
compiler can optimize away self-calls in various ways.
DEF-MEMOIZED-FUNCTION should work for those cases as it is careful to ensure
the function can not be inlined like this."
(declare (type symbol fn-name)
(type function kwy test))
(when (not (fboundp fn-name))
(error "~A is not FBOUNDP" fn-name))
(when (assoc fn-name *memoized-functions*)
(error "~A is already memoized" fn-name))
(multiple-value-bind (wrapper table)
(make-memo (symbol-function fn-name) key test)
(push (list fn-name table (symbol-function fn-name)) *memoized-functions*)
(setf (symbol-function fn-name) wrapper)
fn-name))
(defun unmemoize-function (fn-name)
"Remove memoization for FN-NAME"
(declare (type symbol fn-name))
(let ((hit (assoc fn-name *memoized-functions*)))
(when (not hit)
(error "~A is not memoized" fn-name))
(setf (symbol-function fn-name) (third hit))
(setf *memoized-functions* (delete hit *memoized-functions*))
fn-name))
(defun unmemoize-functions ()
;; complain about all the double-lookup & consing & I'll laugh at
;; you.
"Unmemoize all functions"
(mapcar #'unmemoize-function
(mapcar #'car *memoized-functions*)))
(defun clear-memoized-function (fn-name)
"Clear memoized results for FN-NAME"
(declare (type symbol fn-name))
(let ((hit (assoc fn-name *memoized-functions*)))
(when (not hit)
(error "~A is not memoized" fn-name))
(clrhash (second hit))
fn-name))
(defun clear-memoized-functions ()
"Clear memoized results for all functions"
(mapcar #'clear-memoized-function
(mapcar #'car *memoized-functions*)))
(defun function-memoized-p (fn-name)
"Is FN-NAME memoized?"
(declare (type symbol fn-name))
(if (assoc fn-name *memoized-functions*) t nil))
(defmacro def-memoized-function (fnspec args &body bod)
"Define a memoized function.
FNSPEC is either the name of the function, or a list suitable as an arglist
for MEMOIZE-FUNCTION. ARGS & BOD are passed off to DEFUN.
This will declare FNSPEC NOTINLINE, which may be necessary to prevent good
compilers optimizing away self calls & stuff like that."
;; the sorts of fns that are usefully inlineable and those that are
;; usefully memoizable are probably disjoint...
(let ((name (etypecase fnspec
(symbol fnspec)
(list (car fnspec)))))
(when (function-memoized-p name)
(unmemoize-function name))
`(progn
;; ??? is this right? I want to ensure that the function is
;; really called, and avoid bright compilers doing TRO or not
;; calling through the SYMBOL-FUNCTION (kind of a strange thing
;; to want in general). I think that a NOTINLINE declaration
;; does this.
(declaim (notinline ,name))
(defun ,name ,args
;; ??? can we need NOTINLINE here as well?
,@bod)
(apply #'memoize-function ',(typecase fnspec
(symbol (list fnspec))
(list fnspec)))
',name)))
#||
(def-memoized-function fib (n)
(if (<= n 1)
1
(+ (fib (- n 1)) (fib (- n 2)))))
||#
(defmacro memoized-labels ((&rest labdefs) &body bod)
"A version of LABELS that memoizes the local functions. See
MEMOIZE-FUNCTION and DEF-MEMOIZED-FUNCTION. If code that uses this is
compiled (either by COMPILE or COMPILE-FILE, then the table of memoized
results will be unique, if interpreted then a new table may be generated for
each use. The function `names' are generalised in the same way as for
DEF-MEMOIZED-FUNCTION."
;; this is a pretty hairy macro, perhaps unnecessarily so. It uses
;; an interestingly-large amount of the features of CL. The use of
;; LOAD-TIME-VALUE is an attempt to get literal hashtables into the
;; compiled code, which seems to be non-portable the obvious way
;; (binding them in the macro & then splicing the literal in to the
;; expansion). Can MAKE-LOAD-FORM do this better?
`(labels ,(loop for (fspec fargs . fbod) in labdefs
collect
(destructuring-bind (fname &key (key '(function first))
(test '(function eql)))
(if (listp fspec)
;; FSPEC is of the form (NAME :key
;; .. :test ..), where we use the keywords
;; to get the key from the arglist and
;; decide what test to use for the
;; hashtable.
fspec
(list fspec :key '(function first)
:test '(function eql)))
(let ((htn (make-symbol "HT")) ;hashtable name
(kn (make-symbol "K")) ;key from arglist name
(vn (make-symbol "V")) ;value found name
(fpn (make-symbol "FP")) ;foundp name
(argsn (make-symbol "ARGS"))) ;args name
;; here's the definition clause in the LABELS:
;; note we have to generalise rthe args to an
;; &REST, but hopefully the DYNAMIC-EXTENT
;; avoids too much lossage.
`(,fname (&rest ,argsn)
(declare (dynamic-extent ,argsn) ;stop consing
(notinline ,fname)) ;stop TRO (?)
;; this use of LOAD-TIME-VALUE should ensure
;; that the hashtable is unique in compiled
;; code. This has kind of interesting
;; effects, as it's shared amongst seperate
;; closures that you might return, so use of
;; one can speed up another!
(let ((,htn (load-time-value (make-hash-table
:test ,test)))
(,kn (funcall ,key ,argsn)))
(multiple-value-bind (,vn ,fpn)
(gethash ,kn ,htn)
(if ,fpn
,vn ;found in table: return value
;; didn't find it: compute value
(setf (gethash ,kn ,htn)
(apply #'(lambda ,fargs
,@fbod)
,argsn)))))))))
,@bod))
;;; indentation for zmacs
#+Genera
(pushnew 'memoized-labels zwei:*definition-list-functions*)
Fernando D. Mato Mira
;; Created On - 1995?I hope not. In '94 (93?) I was using this:
http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/ext/memoize/0.html
Would be cool to get some of your work merged in (eg: labels).
[Isn't Erik the new archiver?]
-- Fernando D. Mato Mira Real-Time SW Eng & Networking Advanced Systems Engineering Division CSEM Jaquet-Droz 1 email: matomira AT acm DOT org CH-2007 Neuchatel tel: +41 (32) 720-5157 Switzerland FAX: +41 (32) 720-5720 www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html
Tim Bradshaw
> Tim Bradshaw wrote:
>> ;; Created On - 1995?
> I hope not. In '94 (93?) I was using this:
> http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/ext/memoize/0.html
That code has no common ancestry with mine.
--tim
Fernando D. Mato Mira
Except for Norvig, according to your comment ;)
I meant I hope you wrote it before that code showed up at CMU; or decided you didn't like
it, eventually. I'm a reuse freak ;)
Regards,
Tim Bradshaw
> I meant I hope you wrote it before that code showed up at CMU; or
> decided you didn't like it, eventually. I'm a reuse freak ;)
I'm not, which might explain why I wrote it, but actually I wrote it
just for fun.
--tim