Wow, I should really learn more about the scoping rules in Lisp. Any
suggested readings?
Anyhow, here's my current scope question:
Suppose I have a recursive function that is searching for elements in
a tree. How can I store a list such that it is not reset on each
recursive call to the search function?
In general, how can I initialize a variable within a function that
will not be reset on each recursive call to that function? I hope my
question is clear. If not, please let me know. Thanks.
dstein64 wrote:
> Suppose I have a recursive function that is searching for elements in
> a tree. How can I store a list such that it is not reset on each
> recursive call to the search function?
>
> In general, how can I initialize a variable within a function that
> will not be reset on each recursive call to that function? I hope my
> question is clear. If not, please let me know. Thanks.
This counter function should give you an idea:
(let ((count 0))
(defun counter ()
(incf count)))
(that is, make it a closure)
If your recursive function was in a LABELS, you would bind your
variable outside of the LABELS form. Implementing the function with a
locally defined function would probably be best because it means you
might need to do less setup/cleanup.
> This counter function should give you an idea:
> (let ((count 0))
> (defun counter ()
> (incf count)))
>
> (that is, make it a closure)
> If your recursive function was in a LABELS, you would bind your
> variable outside of the LABELS form. Implementing the function with a
> locally defined function would probably be best because it means you
> might need to do less setup/cleanup.
I forgot to mention that I would like the variable to reset itself on
each call to the function (but not on the recursive calls. So in your
example, I would like count to be reset to 0 each time counter is
called from the program. Although there is no recursion in that
example, I would not like count to be reset each time counter is
called recursively by counter.
dstein64 wrote:
> > This counter function should give you an idea:
> > (let ((count 0))
> > � (defun counter ()
> > � � (incf count)))
> >
> > (that is, make it a closure)
> > If your recursive function was in a LABELS, you would bind your
> > variable outside of the LABELS form. �Implementing the function with a
> > locally defined function would probably be best because it means you
> > might need to do less setup/cleanup.
>
> I forgot to mention that I would like the variable to reset itself on
> each call to the function (but not on the recursive calls. So in your
> example, I would like count to be reset to 0 each time counter is
> called from the program. Although there is no recursion in that
> example, I would not like count to be reset each time counter is
> called recursively by counter.
The problem is how do you tell a recursive call from a normal call?
Perhaps you could do something like this: (although it isn't the best
example)
(defun my-length (list)
(let ((length 0))
(labels ((helper (list)
(when list
(incf length)
(helper (cdr list)))))
(helper list)
length)))
dstein64 <········@gmail.com> writes:
> I forgot to mention that I would like the variable to reset itself on
> each call to the function (but not on the recursive calls. So in your
> example, I would like count to be reset to 0 each time counter is
> called from the program. Although there is no recursion in that
> example, I would not like count to be reset each time counter is
> called recursively by counter.
Is there a problem with passing count back as an argument? If you
don't want to expose count you can just wrap up the recursive part in
labels:
(defun print-10-times (str)
(labels ((recursive-part (times-left)
(when (> times-left 0)
(print str)
(recursive-part (- times-left 1)))))
(recursive-part 10)))
-Nat
On Apr 29, 3:26 pm, Brian <··············@gmail.com> wrote:
> dstein64 wrote:
> > Suppose I have a recursive function that is searching for elements in
> > a tree. How can I store a list such that it is not reset on each
> > recursive call to the search function?
>
> > In general, how can I initialize a variable within a function that
> > will not be reset on each recursive call to that function? I hope my
> > question is clear. If not, please let me know. Thanks.
>
> This counter function should give you an idea:
> (let ((count 0))
> (defun counter ()
> (incf count)))
This might lead to a bad idea. Here, count is a de facto global
variable.
If you use a global variable for recursion context, then you will have
to use a lock to defend against any concurrency, or at the very least,
save and restore the variable to guard against any nested recursion
sessions (which can happen in non-concurrent programs).
This latter situation can rise, for instance, if you have a function
which recursively walks some data structure and (by means of the
recursion context) invokes a callback specified by the caller. The
callback may want to run a nested search using that same function.
dstein64 <········@gmail.com> writes:
> Wow, I should really learn more about the scoping rules in Lisp. Any
> suggested readings?
>
> Anyhow, here's my current scope question:
>
> Suppose I have a recursive function that is searching for elements in
> a tree. How can I store a list such that it is not reset on each
> recursive call to the search function?
>
> In general, how can I initialize a variable within a function that
> will not be reset on each recursive call to that function? I hope my
> question is clear. If not, please let me know. Thanks.
If I understand the question, you want to pass it along as another
argument to the function, like so (the ACCUM argument).
(defun myfind (test sequence &optional (accum '()))
"Finds all items in SEQUENCE for which TEST is T."
(cond ((null sequence) accum)
((funcall test (car sequence))
(myfind test (cdr sequence) (cons (car sequence) accum)))
(t (myfind test (cdr sequence) accum))))
If you don't have/don't like optional arguments, something like
(defun myfind (test sequence)
"Finds all items in SEQUENCE for which TEST is T."
(myfind0 test sequence '()))
(defun myfind0 (test sequence accum)
"Helper function for MYFIND."
(cond ((null sequence) accum)
((funcall test (car sequence))
(myfind test (cdr sequence) (cons (car sequence) accum)))
(t (myfind test (cdr sequence) accum))))
Is the usual solution.
On Apr 29, 3:14 pm, dstein64 <········@gmail.com> wrote:
> Wow, I should really learn more about the scoping rules in Lisp. Any
> suggested readings?
>
> Anyhow, here's my current scope question:
>
> Suppose I have a recursive function that is searching for elements in
> a tree. How can I store a list such that it is not reset on each
> recursive call to the search function?
The number one solution is to split the recursion into a non-recursive
interface and a recursive implementation, and nest these inside each
other so that the recursive implementation can see lexical variables
established by the interface:
(defun nonrecursive-interface (input)
(let ((context (make-recursive-context input)))
(labels ((recursive-implementation (input)
;; can freely refer to context
... ))
(recursive-implementation input))))
The second best way is to use extra parameters. This can be done
without splitting the function into two, thanks to optional parameters
(defun recursive-function (input
&optional (context nil context-passed-p))
(if context-passed-p
(... this is a recursive call ...)
(... not passed, this is the top-level call ...)))
If the context is not passed, you must create one and then start the
recursion.
These are the ways to do it if the whole thing is under your control,
and there isn't a whole lot of code involved in the recursion loop.
If the recursion is complicated---for instance, involves lots of
functions, many of which are external to the module, and for various
reasons cannot be made to cooperate by passing through your extra
arguments and at the same time make lexical scoping impractical---then
you can use a dynamically scoped variable. You bind this dynamically
scoped variable around the recursion chain. In keeping with lisp
coding conventions, you should introduce the variable with DEFVAR or
DEFPARAMETER at file scope and give it a descriptive name which begins
and ends with an asterisk character. The most straightforward way to
set up the binding is to split the function into the interface wrapper
and a recursive implementation. The wrapper will encapsulate the call
to the implementation inside a LET which establishes the local binding
for the special variable. The recursive function can then make free
references to that variable; the variable is private.
;; The following creates top-level variable, and also
;; specially marks the *FOO-CONTEXT* symbol so that
;; whenever it is subject to a variable binding,
;; the binding will be dynamic rather than lexical.
(defvar *foo-context*)
(defun foo-recursion-helper (input)
;; free recursion
)
(defun foo-recursion (input)
(let ((*foo-context* (make-context input)))
(foo-recursion-helper input)))
Now FOO-RECURSION-HELPER can call some arbitrary chain of functions,
which ends up calling back into FOO-RECURSION-HELPER. That call will
still be able to use its *FOO-CONTEXT*.