From: Jeff Sullivan
Subject: tree-searching function in CL?
Date:
Message-ID: <20849@venera.isi.edu>
Is there a built-in function in Common Lisp that allows you to do a
tree-search? I'm trying (have to, really) to avoid the overhead from
a recurusive search of a tree. I need to either apply a predicate to
each element, or search for a specific symbol. Either one will do.
jas
--
--------------------------------------------------------------------------
Jeffrey A. Sullivan | Senior Systems Apologist, Grade F
···@venera.isi.edu | Information Sciences Institute
···@isi.edu | University of Southern California
In article <·····@venera.isi.edu> ···@ISI.EDU (Jeff Sullivan) writes:
> Is there a built-in function in Common Lisp that allows you to do a
> tree-search? I'm trying (have to, really) to avoid the overhead from
> a recurusive search of a tree. I need to either apply a predicate to
> each element, or search for a specific symbol. Either one will do.
What "overhead of the recursive search" are you trying to avoid?
Stack space? I suppose if you've got very deeply nested lists you
might have to use something which reverses pointers to keep track of
where it is, but for most trees the obvious implementation (following)
should be as fast as anything the implementation could provide.
(defun walk-leaves (function tree)
(cond ((consp tree)
(walk-leaves function (car tree))
(walk-leaves function (cdr tree)))
(t (funcall function tree))))
Note that the recursion on the CDR is in a return context. Most CL
compilers will optimize this into a loop, so that the stack depth will
only grow with the depth of nesting, rather than with that plus the
lengths of the lists nested.
To search for leaves satisfying a predicate:
(defun search-tree (predicate tree)
(walk-leaves
#'(lambda (leaf)
(when (funcall predicate leaf)
(return-from search-tree leaf)))
tree))
In article <····················@skye.parc.xerox.com> ·······@skye.parc.xerox.com (Doug Cutting) writes:
What "overhead of the recursive search" are you trying to avoid?
Stack space? I suppose if you've got very deeply nested lists you
might have to use something which reverses pointers to keep track of
where it is, but for most trees the obvious implementation (following)
should be as fast as anything the implementation could provide.
(defun walk-leaves (function tree)
(cond ((consp tree)
(walk-leaves function (car tree))
(walk-leaves function (cdr tree)))
(t (funcall function tree))))
Note that the recursion on the CDR is in a return context. Most CL
compilers will optimize this into a loop, so that the stack depth will
only grow with the depth of nesting, rather than with that plus the
lengths of the lists nested.
Can a CommonLisp compiler legally optimize this code, or must it take
into account the possibility that the argument FUNCTION could be
something outrageous like the following?
#'(lambda (tree)
(unless (consp tree)
(setf (symbol-function 'walk-leaves) #'(lambda (fn tree) tree))))
To avoid such annoying albeit extremely unlikely possibilities, a
LABELS is perhaps preferable:
(defun walk-leaves (function tree)
(labels ((local-walk (tree)
(cond ((consp tree)
(local-walk (car tree))
(local-walk (cdr tree)))
(t (funcall function tree)))))
(local-walk tree)))
-- Harley Davis
--
------------------------------------------------------------------------------
nom: Harley Davis ILOG S.A.
net: ·····@ilog.fr 2 Avenue Gallie'ni, BP 85
tel: (33 1) 46 63 66 66 94253 Gentilly Cedex, France
In article <··················@passy.ilog.fr> ·····@passy.ilog.fr (Harley Davis) writes:
>Can a CommonLisp compiler legally optimize this code, or must it take
>into account the possibility that the argument FUNCTION could be
>something outrageous like the following?
>
> #'(lambda (tree)
> (unless (consp tree)
> (setf (symbol-function 'walk-leaves) #'(lambda (fn tree) tree))))
See p. 686 of CLtL2: "The compiler may assume that, within a named
function, a recursive call to a function of the same name refers to the
same function, unless that function has been declared NOTINLINE."
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
In article <··················@passy.ilog.fr> ·····@passy.ilog.fr (Harley Davis) writes:
Note that the recursion on the CDR is in a return context. Most CL
compilers will optimize this into a loop...
Can a CommonLisp compiler legally optimize this code, or must it take
into account the possibility that the argument FUNCTION could be
something outrageous like [one which changes the function of walk-leaves]
It shouldn't matter; one can optimize *any* tail call. This
just means that instead of calling a routine, then returning upon its
return, you branch to it. It doesn't have to be the same routine. So
the only issue is a (marginal) one of speed -- do you need to lookup
the function associated with walk-leaves or can you statically* assume
it to be the same function? This assumption isn't surprising --
compilers constantly assume calls to functions in the compiled file
are statically resolvable.
Anyhow, the stack depth won't be altered in either case -- TRO
applies regardless.
Ron
* Your labels approach requires no assumptions because of static
scoping.
In article <·····················@lister.lcs.mit.edu> ········@theory.lcs.mit.edu (Ronald Bodkin) writes:
(Harley Davis) writes:
Note that the recursion on the CDR is in a return context. Most CL
compilers will optimize this into a loop...
Can a CommonLisp compiler legally optimize this code, or must it take
into account the possibility that the argument FUNCTION could be
something outrageous like [one which changes the function of walk-leaves]
It shouldn't matter; one can optimize *any* tail call. This
just means that instead of calling a routine, then returning upon its
return, you branch to it. It doesn't have to be the same routine. So
the only issue is a (marginal) one of speed -- do you need to lookup
the function associated with walk-leaves or can you statically* assume
it to be the same function? This assumption isn't surprising --
compilers constantly assume calls to functions in the compiled file
are statically resolvable.
Anyhow, the stack depth won't be altered in either case -- TRO
applies regardless.
Ron
* Your labels approach requires no assumptions because of static
scoping.
While TCO is certainly important, I don't think the funcall speed
issue is marginal. Calling (or branching to) a known function is
considerably faster than calling (or branching to) an unknown
function. For example, the latter requires indirection through the
symbol, checking number of arguments dynamically, and, in CommonLisp,
dynamically resolving keywords. This can all be elided by the
compiler if the function is known statically. The first order effects
are considerable, and on many machines second order effects, such as
data/instruction caches and register windows, can also make a
substantial difference.
I was happy to learn that CommonLisp has made the smart default choice
on this issue.
-- Harley Davis
--
------------------------------------------------------------------------------
nom: Harley Davis ILOG S.A.
net: ·····@ilog.fr 2 Avenue Gallie'ni, BP 85
tel: (33 1) 46 63 66 66 94253 Gentilly Cedex, France
In article <··················@dauphine.ilog.fr> ·····@dauphine.ilog.fr (Harley Davis) writes:
From: ·····@dauphine.ilog.fr (Harley Davis)
Date: 7 Mar 92 00:54:06 GMT
In article <·····················@lister.lcs.mit.edu> ········@theory.lcs.mit.edu (Ronald Bodkin) writes:
It shouldn't matter; one can optimize *any* tail call. This
just means that instead of calling a routine, then returning upon its
return, you branch to it. It doesn't have to be the same routine. So
the only issue is a (marginal) one of speed -- do you need to lookup
the function associated with walk-leaves or can you statically* assume
it to be the same function? This assumption isn't surprising --
compilers constantly assume calls to functions in the compiled file
are statically resolvable.
Anyhow, the stack depth won't be altered in either case -- TRO
applies regardless.
Ron
* Your labels approach requires no assumptions because of static
scoping.
But dynamic scoping exists. If a function makes a recursive call
inside a dynamic variable binding, or an UNWIND-PROTECT, you cannot
do tail calling.
Similarly for anything else with dynamic extent, for example,
passing functions or lists or what have you declared DYNAMIC-EXTENT.
(Not that this has any impact on the main point of the conversation).