tail call with memory

[Gerhard]

Hello,

I do not understand how I managed to build in some limited memory into
the following function.

(let ((lst))
(defun search-all-1 (a b &key (test #'equal))
(labels ((f (a b acc)
(let ((x (search a b :test test)))
(if x
(progn
(push (+ x acc) lst)
(incf acc (+ 1 x))
(f a (subseq b (1+ x)) acc))
(nreverse lst)))))
(f a b 0))))

The first call will get what I intended, but every subsequent call will
inherit the last value (and only the last) of the previous results:

CL-USER> (search-all-1 '("a") '("a" "b" "c" "d" "a"))
(0 4)
CL-USER> (search-all-1 '("a") '("a" "b" "c" "d" "a"))
(4 0 4)
CL-USER> (search-all-1 '("a") '("a" "b" "c" "d" "a" "a"))
(4 0 4 5)
CL-USER> (search-all-1 '("a") '("a" "b" "c" "d" "a" "a"))
(5 0 4 5)

Any idea what I did got wrong, and what I could do about that (other
than checking whether the first value is bigger than the second)?

I am stuck...

Thanks in advance,

Gerhard

[Norbert_Paul]

Gerhard wrote:
> Hello,
>
> The first call will get what I intended, but ...
So what do you intend then?

> Any idea what I did got wrong, and what I could do about that (other
> than checking whether the first value is bigger than the second)?

The problem might be that there still is no programming language with
a DWIM (Do What I Mean) feature. They are still all DWISP (Do What I Say. Period.).

Just kidding. You should say, what exactly you expect the function to do.
Two things can go wrong:
1. The language implementation has an error (very unlikely).
2. The program behaves different that it should do according to
some specification (which is missing).

A hint: Try to figure out, what "lexical closures" are. This might help you
to understand.

Norbert

[Rupert Swarbrick]

You want to put the LST binding inside the defun. As it stands,
SEARCH-ALL-1 closes over a variable called LST. After your first line,
LST is whatever (NREVERSE LST) left it as. (This is
implementation-dependent: see the documentation for NREVERSE). When you
call SEARCH-ALL-1 again, it pushes another variable to LST etc. etc.

Rupert

[Gerhard]

Norbert_Paul wrote:

> Gerhard wrote:
>> Hello,
>>
>> The first call will get what I intended, but ...
> So what do you intend then?
>

What I want is a version of "search" that does not only tell me where the
first occurrence of a given sequence is, but that gives me the position of
all occurrences as a list of integers.

So, instead of:

CL-USER> (search '("a") '("a" "b" "c" "d" "a" "a") :test #'string-equal)
0

I would like to have

CL-USER> (search-all '("a") '("a" "b" "c" "d" "a" "a"))
(0 4 5)

> A hint: Try to figure out, what "lexical closures" are. This might help
> you to understand.

Have checked, and the following seems to work:

(defun search-all-1 (a b &key (test #'equal))

(let ((lst))

(labels ((f (a b acc)
(let ((x (search a b :test test)))
(if x
(progn
(push (+ x acc) lst)
(incf acc (+ 1 x))
(f a (subseq b (1+ x)) acc))
(nreverse lst)))))
(f a b 0))))

I think that I understand now why and how the above works. But I still do
not understand the behaviour of the preceding version.

I would have expected that - if the (let ((lst)) had the defun in its scope
- a new call of the function did not affect the content of the variable lst.
Yet a new call seems to purge all but the last element of the preceding call
to it. Where am I wrong?

[kodifik]

On Apr 25, 12:12 pm, Gerhard <felds...@gmx.net> wrote:
> I think that I understand now why and how the above works. But I still do
> not understand the behaviour of the preceding version.

I will try to explain it to you in a different way:

Version 1: first "let" the variable be,
then define the function over it.
The variable "remains" across function calls.

Version 2: First "defun", then "let".
A new variable gets created every time
the function gets called.
That's what you expected.

[Frank DG1SBG]

In addition to what the other posters explained I would like to present
a possible solution:

(defun find-positions (object list &key (test #'eql))
(let ((result ()))
(loop
for elt in list
for n from 0 to (length list)
do
(when (funcall test object elt)
(pushnew n result)))
(nreverse result)))

And I would like to hear/read comments - or, even better, some shorter
solutions...

To Gerhard: Solution understandable?

Cheers
Frank

[Alex Mizrahi]

> I would have expected that - if the (let ((lst)) had the defun in its scope
> - a new call of the function did not affect the content of the variable lst.
> Yet a new call seems to purge all but the last element of the preceding call
> to it. Where am I wrong?

NREVERSE is destructive. It re-uses cons cells of the list variable lst
points to. It doesn't update variable lst, though.

So now lst points to a re-used cons cell. And it just happens that this
cell is now end of list, so it effectively points to the latest element.
But you shouldn't depend on this.
(To understand how it happens think about how to implement a destructive
NREVERSE which doesn't cons and which preserves CAR's of cons cells.)

As a rule of thumb, don't use destructive functions unless you
absolutely want speed and understand code you're working with.
But not that there no non-destructive SORT.

[kodifik]

On Apr 25, 12:54 pm, Frank DG1SBG <dg1...@googlemail.com> wrote:

I think "when" is unnecessary when/if a simple "if" would do.
Same with "pushnew" and "push".

(defun find-positions (object list &key (test #'eql))

(loop with result = '()

for elt in list
for n from 0 to (length list)

do (if (funcall test object elt)
(push n result))
finally (return (nreverse result))))

slightly more clear, also.

But I would go for some mapping function here.

[Alex Mizrahi]

> I do not understand how I managed to build in some limited memory into
> the following function.

> (let ((lst))

> (defun search-all-1 (a b&key (test #'equal))

> (labels ((f (a b acc)
> (let ((x (search a b :test test)))
> (if x
> (progn
> (push (+ x acc) lst)
> (incf acc (+ 1 x))
> (f a (subseq b (1+ x)) acc))
> (nreverse lst)))))
> (f a b 0))))

By the way, you mix two styles here: you use both accumulator and a
mutable variable. This is weird. You can use two accumulators. I.e. an
accumulator for positions and a counter.

Also your use of subseq and search is weird. Recursive function is
supposed to operate on elements of a list.

[Gerhard]

OK, I see; thanks for the advice.

[Frank DG1SBG]

kodifik <kod...@eurogaran.com> writes:

>
> But I would go for some mapping function here.

Like so?

(defun find-positions (object list &key (test #'eql))

(let ((position -1))
(remove nil (mapcar (lambda (elt)
(if (funcall test object (nth (incf position) list))
position)) list))))

[Tim Bradshaw]

On 2012-04-25 09:36:34 +0000, Norbert_Paul said:

> The problem might be that there still is no programming language with
> a DWIM (Do What I Mean) feature. They are still all DWISP (Do What I
> Say. Period.).

"DWIM, the Do-What-I-Mean error correction facility, was introduced
into the system in 1968 by W. Teitelman"

[Gerhard]

Thank you for your suggestions. But, as I had not specified, I depend on
"search" because I sometimes need to find sequences, and not only individual
elements. My fault.

Your solutions will not work in these cases:

CL-USER> (search-all-1 '(a "b") '("Maradonna" a "b" "c" "d" a a "d" "abo"
"gololo"))
(1)

CL-USER> (find-positions '(a "b") '("Maradonna" a "b" "c" "d" a a "d" "abo"
"gololo"))
NIL

Otherwise, I had come up with the following:

(defun search-all (a b &key (test #'equal))

(let ((x (search a b :test test)))

(when x
(cons x (mapcar #'(lambda (i) (+ 1 x i))
(search-all a (subseq b (1+ x)) :test test))))))

[Tim Bradshaw]

On 2012-04-25 10:54:35 +0000, Frank DG1SBG said:

> And I would like to hear/read comments - or, even better, some shorter
> solutions...

The loop-based one, to be despised by the CS bigots because anyone can
understand what it does

(defun find-positions (object list &key (test #'eql))

(loop for elt in list

for n upfrom 0
when (funcall test object elt)
collect n))


Starting towards the proper obscure CS bigot one (really for full
obscurity you should use Y to do this, and, obviously, not write it in
CL)

(defun find-positions (thing list &key (test #'eql))
(labels ((fp (tail n a)
(if (null tail) (nreverse a)
(destructuring-bind (first . rest) tail
(fp rest (1+ n) (if (funcall test thing first)
(cons n a)
a))))))
(fp list 0 '())))

[Norbert_Paul]

Hehe. Interesting:
http://en.wikipedia.org/wiki/Warren_Teitelman#Interlisp_and_D-Lisp
but it can't correct algorithmic errors :)

[Pascal J. Bourguignon]

Gerhard <feld...@gmx.net> writes:

> Hello,
>
> I do not understand how I managed to build in some limited memory into
> the following function.
>
> (let ((lst))
> (defun search-all-1 (a b &key (test #'equal))
> (labels ((f (a b acc)
> (let ((x (search a b :test test)))
> (if x
> (progn
> (push (+ x acc) lst)
> (incf acc (+ 1 x))
> (f a (subseq b (1+ x)) acc))
> (nreverse lst)))))
> (f a b 0))))

The principal problem with your call to nreverse, is that you don't use
the result. Destructive functions in general don't ensure anything
useful about the state of the destructed object, but return a good
result. You should have kept it:

(setf lst (nreverse lst))


cl-user> (search-all-1 '("a") '("a" "b" "c" "d" "a"))
(0 4)
cl-user> (search-all-1 '("a") '("a" "b" "c" "d" "a"))
(4 0 0 4)
cl-user> (search-all-1 '("a") '("a" "b" "c" "d" "a" "a"))
(4 0 0 4 0 4 5)
cl-user> (search-all-1 '("a") '("a" "b" "c" "d" "a" "a"))
(5 4 0 4 0 0 4 0 4 5)

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

[Kaz Kylheku]

On 2012-04-25, Gerhard <feld...@gmx.net> wrote:
> Hello,
>
> I do not understand how I managed to build in some limited memory into
> the following function.
>
> (let ((lst))

You bound a lexical environment around the defun. There is one instance of this
environment (and thus the variable lst) around this function, shared by all the
function calls.

let around defun is used to create persistent function-private variables, like
"static" in C.

> (defun search-all-1 (a b &key (test #'equal))

Maybe you want (let ((lst)) to be here, inside the function, so that you get a
freshly instantiated lst on each call, initialized to nil.

[WJ]

You're a solving a different problem than the one presented
by the original poster.

Another solution to your problem (in Racket):

(define (all-indices sought lst [test equal?])
(for/list ([(x i) (in-indexed lst)]
#:when (test x sought))
i))

[WJ]

Instead of CL, tCL.

% lsearch -all -exact {a b c d a a} a
0 4 5