ANSI Common Lisp, Page 30, Exercise 8b

[Steve Graham]

The question is to find the recursive solution for finding the number of times the symbol a occurs in a list (I figured out the iterative code). I calculate the answer to the first test below as 0, but the system disagrees.

I broke it up into 2 functions to allow me to initialize an accumulator variable before calling a function which itself gets called recursively.

Here is what I have so far:

CL-USER> (defun find-a-r-2 (lst)
(if (null lst)
*i*
(progn
(if (eql (car lst) 'a)
(setf *i* (+ *i* 1)))
(find-a-r-2 (cdr lst)))))
STYLE-WARNING: redefining COMMON-LISP-USER::FIND-A-R-2 in DEFUN
FIND-A-R-2

CL-USER> (defun find-a-r (lst)
(defvar *i* 0)
(find-a-r-2 lst))
STYLE-WARNING: redefining COMMON-LISP-USER::FIND-A-R in DEFUN
FIND-A-R

CL-USER> (find-a-r '(1 2 3))
3

CL-USER> (defvar *i* 0)
*I*

CL-USER> (find-a-r-2 '(1 2 3))
3

CL-USER>

What's wrong here?

Thanks, Steve

[Paul Rubin]

Steve Graham <solitary....@gmail.com> writes:
> CL-USER> (defun find-a-r (lst)
> (defvar *i* 0)
> (find-a-r-2 lst))

> What's wrong here?

defvar does a top-level binding. You are expecting something like let
with dynamic scope (I don't remember how to get that in CL). But that
whole approach is ugly: you should pass the accumulation parameter as a
function arg rather than a variable that gets clobbered. This is
untested but shows the idea using 2 functions like in your example:

(defun find-a-r (lst) (find-a-r-2 lst 0))

(defun find-a-r-2 (lst acc)
(cond
((null lst) acc)
((eq (car lst) 'a') (find-a-r-2 (cdr lst) (1+ a)))
(t (find-a-r-2 (cdr lst) a))))

In Common Lisp though, you can use an optional parameter instead of
two separate procedures:

(defun find-a-r (lst &optional (acc 0))
(cond
((null lst) acc)
((eq (car lst) 'a') (find-a-r (cdr lst) (1+ a)))
(t (find-a-r-2 (cdr lst) a))))

So if you call without the extra arg, the runtime supplies it with the
default value of 0.

[Paul Rubin]

Paul Rubin <no.e...@nospam.invalid> writes:
> (defun find-a-r (lst &optional (acc 0))
> (cond
> ((null lst) acc)
> ((eq (car lst) 'a') (find-a-r (cdr lst) (1+ a)))
> (t (find-a-r-2 (cdr lst) a))))

oops, got messed up there, should say 'acc' in the last 2 lines:

> (defun find-a-r-2 (lst acc)
> (cond
> ((null lst) acc)

> ((eq (car lst) 'a') (find-a-r-2 (cdr lst) (1+ acc)))
> (t (find-a-r-2 (cdr lst) acc))))

[Kaz Kylheku]

On 2016-08-03, Steve Graham <solitary....@gmail.com> wrote:
> The question is to find the recursive solution for finding the number
> of times the symbol a occurs in a list (I figured out the iterative
> code). I calculate the answer to the first test below as 0, but the
> system disagrees.
>
> I broke it up into 2 functions to allow me to initialize an accumulator variable before calling a function which itself gets called recursively.
>
> Here is what I have so far:
>
> CL-USER> (defun find-a-r-2 (lst)
> (if (null lst)
> *i*
> (progn
> (if (eql (car lst) 'a)
> (setf *i* (+ *i* 1)))
> (find-a-r-2 (cdr lst)))))

Ouch what, mutating a global variable? Surely you jest.

* Given an empty list, the number of times symbol a occurs in it
is precisely zero.

* If given a non-empty list, there are two cases:
* If the non-empty list begins with symbol a, then the number of
occurences is 1, plus the number of occurrences in the rest of the
list.
* Otherwise, the number of occurrences is the number of occurrences
in the rest of the list.

This English description is verbose and hard to grok; thank goodness
we can write it clearly and concisely in Lisp.

[WJ]

Steve Graham wrote:

> The question is to find the
> recursive solution for finding
> the number of times the symbol
> a occurs in a list (I figured
> out the iterative code). I
> calculate the answer to the
> first test below as 0, but the
> system disagrees.
>
> I broke it up into 2 functions
> to allow me to initialize an
> accumulator variable before
> calling a function which
> itself gets called
> recursively.
>
> Here is what I have so far:
>
> CL-USER> (defun find-a-r-2 (lst)
> (if (null lst)

> i

> (progn
> (if (eql (car lst) 'a)

> (setf i (+ i 1)))

> (find-a-r-2 (cdr lst)))))
> STYLE-WARNING: redefining COMMON-LISP-USER::FIND-A-R-2 in DEFUN
> FIND-A-R-2
>
> CL-USER> (defun find-a-r (lst)

> (defvar i 0)

> (find-a-r-2 lst))
> STYLE-WARNING: redefining COMMON-LISP-USER::FIND-A-R in DEFUN
> FIND-A-R
>
> CL-USER> (find-a-r '(1 2 3))
> 3
>

> CL-USER> (defvar i 0)
> I

>
> CL-USER> (find-a-r-2 '(1 2 3))
> 3
>
> CL-USER>
>
> What's wrong here?

You are an ideal disciple of CL (COBOL-Like).

OCaml:

At the risk of blowing the stack:

let rec count_a = function
[] -> 0
| "a"::rest -> 1 + (count_a rest)
| _::rest -> count_a rest ;;

# count_a ["bb";"c"];;
- : int = 0
# count_a ["a";"bb";"c"];;
- : int = 1
# count_a ["a";"bb";"c";"a"];;
- : int = 2


Without the risk of blowing the stack:

let count_a list =
let rec loop sum = function
[] -> sum
| "a"::rest -> loop (sum + 1) rest
| _::rest -> loop sum rest
in loop 0 list ;;

--
For two years ... he was held in solitary confinement in the Toronto West
Detention Centre, on the pretext that he is a threat to national security....
[A] court in Mannheim sentenced him to five years imprisonment for the crime of
"popular incitement" under Germany's notorious "Holocaust denial" statute.
http://www.revisionists.com/revisionists/zundel.html

[Barry Margolin]

In article <2cc0f1a0-55fe-4c19...@googlegroups.com>,

The second argument to DEFVAR is a default value that's used if the
variable doesn't already have a value. Since *i* is already set to 3,
the second DEFVAR doesn't set it back to 0.

But as others have pointed out, you shouldn't use a global variable at
all for this.

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

[Steve Graham]

Thanks, Paul. This worked:

(defun find-a-r (lst &optional (acc 0))
(cond
((null lst) acc)

((eq (car lst) 'a) (find-a-r (cdr lst) (1+ acc)))
(t (find-a-r (cdr lst) acc))))

I used 2 functions because I did not know how to initialize the accumulator and then use it for updating using only 1 function. I tried a local variable and when it didn't work, I tried the global variable, which of course also didn't work.

Do you think there is a way to accomplish this without the optional parameter? The reason I ask is that Paul Graham had not yet covered it in the material preceding the exercise.

Steve

[Steve Graham]

Answered my own question:

(defun find-a-r (lst acc)
(cond
((null lst) acc)
(t (progn
(if (eq (car lst) 'a)
(setf acc (+ acc 1)))
(find-a-r (cdr lst) acc)))))

STYLE-WARNING: redefining COMMON-LISP-USER::FIND-A-R in DEFUN
FIND-A-R

CL-USER> (find-a-r '(1 2 3) 0)
0

CL-USER> (find-a-r '() 0)
0

CL-USER> (find-a-r '(a) 0)
1

CL-USER> (find-a-r '(a a) 0)
2

CL-USER> (find-a-r '(a 2 a) 0)
2

CL-USER> (find-a-r '(1 2 a) 0)
1

CL-USER>

Here is another version. Which would be more in keeping with CL style?

(defun find-a-r (lst acc)
(cond
((null lst) acc)
(t (find-a-r (cdr lst) (or (and (eq (car lst) 'a) (+ acc 1)) acc)))))

CL-USER> (find-a-r '() 0)
0

CL-USER> (find-a-r '(a) 0)
1

CL-USER> (find-a-r '(1 2 3) 0)
0

CL-USER> (find-a-r '(a 2 3) 0)
1

CL-USER> (find-a-r '(b 2 3) 0)
0

CL-USER> (find-a-r '(1 a 3) 0)
1

CL-USER> (find-a-r '(1 a 3 z y x w a) 0)
2

CL-USER>

[Steve Graham]

On Tuesday, August 2, 2016 at 8:30:58 PM UTC-7, Kaz Kylheku wrote:

I am new to CL. What is wrong with mutating a global variable?

Thanks for the hint on spelling out the problem in English.


Steve

[Steve Graham]

On Wednesday, August 3, 2016 at 8:44:42 AM UTC-7, Barry Margolin wrote:
> In article <xxxx>,

Thanks, Barry.


Steve

[Kaz Kylheku]

On 2016-08-03, Steve Graham <solitary....@gmail.com> wrote:

Mutating a global variable is one of the last resorts we reach
for when we can't solve a problem in any other way, or have good
reasons for not wanting to.

When you have global variables, the behavior of your functions depends
not only on the inputs, but on the current states of those variables.

For instance, the function you're writing which counts the symbol A
will only correctly execute if the global counter is reset to zero,
in addition to all the code being correct. Reasoning about global
variables (are they in the expected state on entry into the code, and
are they left in the correct state on exit) complicates the task of
understanding the code.

When multiple modules of code communicate via changes to global
variables, it becomes difficult to trace their interactions
to convince ourselves that they are correct.

Use of global variables also renders code non-reentrant. Suppose you
made a more flexible function count-matching-items which counts the
number of items in a list which satisfy an arbitrary predicate function.
The function is specified by the caller, passed as an argument. Well,
what if a given instance of that function is so crafted that it *itself*
calls into count-matching-items? If you didn't anticipate that, you
will have a bug. You have a nested counting taking place, yet only
one counter. Oops, now you have to add logic to save and restore the
global counter around calls to the predicate function.

Non-reentrant also means not thread-safe. A function that has
no reason not to be usable by multiple threads at the same
time cannot be, due to its use of globals.

In Lisp, there is a nice way to have "disciplined global variables"
which helps with some of these issues. The code is nevertheless
cumbersome and somewhat error-prone compared to code that avoids
globals.

--
TXR Programming Lanuage: http://nongnu.org/txr
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1

[Steve Graham]

Thanks, Kaz. Makes sense.

[Ben Bacarisse]

Steve Graham <solitary....@gmail.com> writes:
<snip>

> Do you think there is a way to accomplish this without the optional
> parameter? The reason I ask is that Paul Graham had not yet covered
> it in the material preceding the exercise.

Yes, I think you are being expected to find a direct recursive solution.
Have you tried? It's not hard.

You've been steered towards using an accumulating parameter because you
used a global variable, but there is no need for either though an
accumulating parameter may be idiomatic in CL -- I'm not that much of an
expert.

--
Ben.

[Steve Graham]

On Wednesday, August 3, 2016 at 1:28:52 PM UTC-7, Ben Bacarisse wrote:

Came up with 2 solutions without the optional parameter:

(defun find-a-r (lst acc)
(cond
((null lst) acc)

(t (progn
(if (eq (car lst) 'a)
(setf acc (+ acc 1)))
(find-a-r (cdr lst) acc)))))

STYLE-WARNING: redefining COMMON-LISP-USER::FIND-A-R in DEFUN
FIND-A-R

CL-USER> (find-a-r '(1 2 3) 0)
0

CL-USER> (find-a-r '() 0)
0

CL-USER> (find-a-r '(a) 0)
1

CL-USER> (find-a-r '(a a) 0)
2

CL-USER> (find-a-r '(a 2 a) 0)
2

CL-USER> (find-a-r '(1 2 a) 0)
1

CL-USER>

Here is another version.

(defun find-a-r (lst acc)
(cond
((null lst) acc)

[Paul Rubin]

Ben Bacarisse <ben.u...@bsb.me.uk> writes:
> You've been steered towards using an accumulating parameter because you
> used a global variable, but there is no need for either though an
> accumulating parameter may be idiomatic in CL

The reason for using an accumulating parameter is so you get tail
recursion instead of stack buildup.

[WJ]

The CL spec doesn't mandate tail-call optimization.

So you may get stack overflow despite your pains.

As Paul Graham wrote, Common Lisp sucks.

--
Africans gang-rape and clitorectomize Finnish girl; government arrests Finn
whom they accuse of complaining: http://www.wvwnews.net/story.php?id=6746

[Ben Bacarisse]

Steve Graham <solitary....@gmail.com> writes:

> On Wednesday, August 3, 2016 at 1:28:52 PM UTC-7, Ben Bacarisse wrote:
>> Steve Graham <xxxx> writes:
>> <snip>
>> > Do you think there is a way to accomplish this without the optional
>> > parameter? The reason I ask is that Paul Graham had not yet covered
>> > it in the material preceding the exercise.
>>
>> Yes, I think you are being expected to find a direct recursive solution.
>> Have you tried? It's not hard.
>>
>> You've been steered towards using an accumulating parameter because you
>> used a global variable, but there is no need for either though an
>> accumulating parameter may be idiomatic in CL -- I'm not that much of an
>> expert.
>

> Came up with 2 solutions without the optional parameter:

<snip>

Right, but both use an extra parameter. It's likely you are being asked
to write

(defun find-a-r (lst) ...)

directly.

--
Ben.

[tar...@google.com]

On Wednesday, August 3, 2016 at 11:04:06 AM UTC-7, Steve Graham wrote:
>

> (defun find-a-r (lst &optional (acc 0))
> (cond
> ((null lst) acc)
> ((eq (car lst) 'a) (find-a-r (cdr lst) (1+ acc)))
> (t (find-a-r (cdr lst) acc))))
>
> I used 2 functions because I did not know how to initialize the accumulator
> and then use it for updating using only 1 function.

Well, you would need to initialize it in the call if it is not &optional.
The reason for not exposing that variable in the main function is that it is
an implementation detail and not really something the user (caller) of the
function should need to know about.

Especially since you could substitute an iterative solution that doesn't need
the variable in its argument list at all.

This is an important principle of encapsulation, in that you try not to put
internal details of exactly how the function works into the external interface
that other programmers or even your own code uses. That makes it easier to
change the way the function works without affecting anyone who uses it, so long
as it still computes the same answer.

> I tried a local variable and when it didn't work.

Right, because the local variable is local and thus only visible inside the
text of that function, but not in the recursive call.

> I tried the global variable, which of course also didn't work.

Well, you can get it to work, but it complicates things as Kaz so nicely
explained.

> Do you think there is a way to accomplish this without the optional
> parameter? The reason I ask is that Paul Graham had not yet covered
> it in the material preceding the exercise.

Yes, there are a couple of ways.

One is to dispense with the accumulating parameter entirely and just work with
the return values. The accumulating parameter is an optimization and not
necessary for the correctness of the function.*

(defun find-a-r (list)
(cond ((null list) 0)
((eq (car list) 'a)
(1+ (find-a-r (cdr list))))
(t (find-a-r (cdr list)))))

The other is to use a locally-defined internal function, which Paul Graham also
would not have covered yet. But all this does is create the two-argument
version of the function as an internal function and use that.

(defun find-a-r (lst)
(labels ((find-a-r-internal (lst acc)
(cond
((null lst) acc)
((eq (car lst) 'a) (find-a-r-internal (cdr lst) (1+ acc)))
(t (find-a-r-internal (cdr lst) acc)))))
(find-a-r-internal lst 0)))

I would also note that normally you would want the item you are looking for to
also be a parameter rather than being present in your code directly. Perhaps as
an additional exercise you would want to write
(defun count-items (list item)
...)
(count-items lst 'a) <==> (find-a-r lst)


======
* So long as you don't overflow the stack.
And in spite of WG's comment that the Common Lisp standard doesn't mandate
the elimination of tail recursion**, most of the actual implementations will
perform the optimization.
** https://en.wikipedia.org/wiki/Tail_call

[Pascal J. Bourguignon]

Kaz Kylheku <418-83...@kylheku.com> writes:

> On 2016-08-03, Steve Graham <solitary....@gmail.com> wrote:
>
> Non-reentrant also means not thread-safe. A function that has
> no reason not to be usable by multiple threads at the same
> time cannot be, due to its use of globals.

Even without threads, in lisp it is important to avoid mutating global
variable in functions, if they are high order functions:

(defvar *result* nil)

(defun hof1 (fun list)
(if (endp list)
*result*
(progn (push (funcall fun (first list)) *result*)
(hof1 fun (rest list)))))

(hof1 '1+ '(1 2 3))
--> (4 3 2)

(defun fun2 (arg)
(setf *result* (list arg)))

(reverse (mapcar (function fun2) '(1 2 3)))
--> ((3) (2) (1))

(hof1 (function fun2) '(1 2 3))
--> (#1=(3) . #1#) ; oops!

See, even without threads, the global variable has been modified while
hof1 is executing, by fun2, and therefore it breaks hof1.

--
__Pascal Bourguignon__ http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

[WJ]

tar...@google.com wrote:

> * So long as you don't overflow the stack.
> And in spite of WG's comment that the Common Lisp standard doesn't mandate
> the elimination of tail recursion**, most of the actual implementations will
> perform the optimization.

Kent M. Pitman wrote:

> > If you want to iterate through a list, should you use a recursive
> > function or a loop?
>
> In Common Lisp, always prefer a loop where practical unless you know
> with relative certainty that the problem cannot grow very big. A
> recursive function can run out of stack since CL does not guarantee
> tail call elimination. Anyone who tells you otherwise is living in a
> fantasy world or is telling you something implementation-dependent or
> is confusing Lisp with Scheme.

Often the most elegant solution requires tail-call recursion.

Why are people still using the anti-Lisp that was designed in 1984?

--
Europe is not going to be the monolithic societies that they once were in the
last century.... They are now going into a multicultural mode. Jews will be
resented because of our leading role. --- Barbara Spectre
(https://www.youtube.com/watch?v=K0hD7IffTJs)