Hello,
I have a very urgent question please. Why doesn't the following program
output anything?
(defvar *index* '((a 0)(b 1)(c 2)(d 3)(e 4)(f 5)(g 6)(h 7)))
(defun getindex (el)
(do ((i 0 (+ i 1)))
((= i (length *index*)))
(if (equal (first (nth i *index*)) el) (rest (nth i *index*)) )))
I would like that, for example, (getindex 'f) returns 5.
Any help will be greatly appreciated.
-Francois
In article <··········@news.bluewin.ch>, Francois Aguet wrote:
check out the description of do in the hyperspec. the value of the do (which
in this case also is the function value) is specified in the termination clause
>Hello,
>
>I have a very urgent question please. Why doesn't the following program
>output anything?
>
>
>(defvar *index* '((a 0)(b 1)(c 2)(d 3)(e 4)(f 5)(g 6)(h 7)))
>
>(defun getindex (el)
> (do ((i 0 (+ i 1)))
> ((= i (length *index*)))
> (if (equal (first (nth i *index*)) el) (rest (nth i *index*)) )))
>
>
>I would like that, for example, (getindex 'f) returns 5.
>
>Any help will be greatly appreciated.
>
>-Francois
>
>
>
--
hs
----------------------------------------------------------------
"The cheapest pride is national pride. I demonstrates the lack of
characteristics and achievements you can be proud of. The worst loser
can have national pride" - Schopenhauer
>>>>> On Mon, 7 May 2001 00:10:04 +0200, Francois Aguet ("Francois") writes:
Francois> Hello, I have a very urgent question please.
This appears to be an urgent homework problem, and you will find that
people are more likely to help you if you identify it as such, show the
work you have done so far (as you have), and ask a specific question.
Otherwise it just sounds like you are asking us to do your homework for you.
I am curious; would you please tell me what course this is for,
where you are taking it, and what textbook and Lisp reference
books you are using (if any)?
I can't tell from your example what the problem was supposed to be,
but I'll try to walk you through things, based on what I see.
You have correctly figured out that DO is the general-purpose
iteration construct. It can step variables, such as your "I",
and it has an end-test (in this case, using "="), and a body
of statements (such as your "IF") that are executed unless
the end-test has successfully terminated the loop.
Francois> Why doesn't the following program output anything?
Francois> I would like that, for example, (getindex 'f) returns 5.
(defvar *index* '((a 0)(b 1)(c 2)(d 3)(e 4)(f 5)(g 6)(h 7)))
(defun getindex (el)
(do ((i 0 (+ i 1)))
((= i (length *index*)))
(if (equal (first (nth i *index*)) el)
(rest (nth i *index*)))))
The proximal answer to your question is that you have not specified
any value for DO to return. Unless you somehow specify otherwise,
a DO statement will return NIL.
Your program loops across every element in the list *INDEX*
and does not terminate until every element has been examined.
Each time through, the IF statement tests whether the selected
element is the one you are looking for: if so, it returns it;
otherwise IF returns NIL. There is nothing magic that would
cause the IF statement to exit the DO loop. So, you are testing
to see if you found the desired element, ignores the answer,
and your loop continues to process every element, regardless!
The most obvious modification to your program would be to
use a RETURN statement in the "then" clause of your IF statement.
(defun getindex (el)
(do ((x *index* (cdr x))
(i 0 (+ i 1)))
((= i (length *index*)))
(if (equal (first (nth i *index*)) el)
(return (car (rest (nth i *index*)))))))
RETURN will cause an immediate exit from the DO loop,
bypassing the end-test (= I (LENGTH *INDEX*))
and returning the value you have specified.
But there are much better ways of writing this program.
It is unlikely that your assignment is mainly about learning the
syntax of a DO loop, or about how to break out using RETURN.
You're probably supposed to understand something about the
structure of the data representation in Lisp.
The way you are selecting the elements to be processed is not
very Lispy. The key to your program will be that it is using
a list, which you have named *INDEX*. You should draw yourself
a diagram of the list structure that you have created for *INDEX*
with the DEFVAR statement. When you understand what lists are
good for, you will write the program very differently.
In your data, you have a bunch of small lists that look like (C 2).
You could reference the elements of this list by index:
(nth 0 '(c 2)) => C
(nth 1 '(c 2)) => 2
But lists are not arrays, and using indexes is not the
normal way to access their elements.
A list is a "linked list" of cells, and each cell has two parts
(called CAR and CDR). The CAR of the cell contains a piece of
data (such as "C"), and the CDR of the cell points to the next
cell in the list (or to NIL if this is the end of the list).
For example, the list (C 2) is composed of two cells linked together.
The first cell contains the C, and a pointer to the second cell.
The second cell contains a 2 and a NIL:
(car '(c 2)) => C
(cdr '(c 2)) => (2)
(car (cdr '(c 2)) => 2
(cdr (cdr '(c 2)) => NIL
Notice that we can get from the C to the 2 by simply traversing
the list with CDR. If we are interested in looking at the list
elements in order, we do not need to compute and use an index.
We simply ask for the next part of the list, walking forward
through the list structure itself!
In *INDEX*, you have linked a bunch of small lists together.
The CAR of first cell points to the list (A 0), and the
CDR of the first cell points to the list (B 1), etc.
Note well that your data is not layed out in memory as sequential
elements, as an array would be. Rather, it is composed of cells
that each a contain a pointer linking it to the next cell.
Unlike arrays, lists are not indexed. This means that for the NTH
function to reference a list element by index, it must start at the
beginning of the list and visit each cell in the list, counting them
as it goes, until it gets to the one you want.
But as you saw above, if you already have the list (or a piece of it)
in hand, you can simply walk down to each element using the CDR function.
Here's your program again:
(defun getindex (el)
(do ((x *index* (cdr x))
(i 0 (+ i 1)))
((= i (length *index*)))
(if (equal (first (nth i *index*)) el)
(return (car (rest (nth i *index*)))))))
Your program uses NTH to sequentially index the list, but that is
very inefficient compared to just walking the through the data.
Moreover, each time through the loop, your program computes the
maximum index (LENGTH) of the list. As a general rule of thumb,
since that termination value is a constant, you should move it
outside of the loop, rather than re-compute it each time around.
In this case, moving LENGTH to the outside would probably be a very
good idea, because it might be a particularly expensive computation.
Lisp does not specify how lists are stored in memory, but we do know
that they are not really like arrays. It is most likely that lists
do not have internal structure headers that remember their bounds.
That implies that the LENGTH function probably has to compute the
length by walking through the entire list, counting cells as it goes,
until it reaches the final cell.
In your program, each time through your loop: LENGTH starts at the
beginning of the list of data and walks all the way down to count
up the extent, to see if we are done; then NTH has to start at the
beginning of the list of data and walk all the way down to the cell
that you are interested in; and if it turns out to be the right one,
then you repeat the NTH from the beginning to get the answer.
That's ridiculously inefficient!
A better way to write the program is to eliminate the indexed
references to the data. Instead of using NTH and LENGTH, we will
simply start at the beginning of the list, and each time through
the loop we will use CDR to only walk down one cell in order to
get to the next piece of data.
Here's your list of lists of data; I have renamed the variable to
*DATA* because there's nothing in this program (at least in what
we can see) that has anything to do with indexing anything.
(defvar *data* '((a 0) (b 1) (c 2) (d 3) (e 4) (f 5) (g 6) (h 7)))
I'm renaming the variable EL to be ELT, just because I think it's
more descriptive. ELT is also the name of a built-in Lisp function,
but that's okay. There is no confusion between the variable named
ELT and the function named ELT, because they appear in different
positions: ELT is being used here in a function-call position.
Here's the new program:
(defun getindex (elt)
(do ((i 0 (+ i 1))
(list *data* (cdr list)))
((null list))
(if (equal (car (car list)) elt)
(return (car (cdr (car list)))))))
This DO loop contains a new variable called LIST, which will hold the
part of the list that we have not yet processed. Initially, that's
the entire *DATA* list. Each sucessive time through the loop, LIST
gets to be the CDR of itself; that is, each time through we get the
remaining unprocessed data (the front is popped off).
So the first time through, LIST is ((A 0) (B 1) (C 2) ...)
the second time, LIST is ((B 1) (C 2) (D 3)...)
You can take apart the expressions in the IF statement to see what we
are testing. Remember that LIST contains the unprocessed contents of
our *DATA*, so the CAR of that will be things like (B 1).
We test the CAR of (B 1), which is B. If the test succeeds, we RETURN
a piece of LIST: the CAR is (B 1), the CDR of that is (1), and the
CAR of that is just 1.
We don't need to compute the LENGTH of the data -- we don't care how
long it is. We only care about whether there is any more of it left
to process. So our end-test is (NULL LIST), which returns T if
we have exhausted all the data (that is, when LIST is NIL).
We still have the DO loop counting up a variable I from 0, and at the
end of the loop it will be the zero-based index of the desired element.
We are not using that value for anything, and the compiler will probably
even warn about this "unused variable".
At this point, there's a question about what the program was intended to do.
Was it supposed to find the index to the desired element? If so, then
perhaps we should simply do (RETURN I) instead of returning the 1 from
the (B 1) piece of data. That version of the program would look like this:
(defun getindex (elt)
(do ((i 0 (+ i 1))
(list *data* (cdr list)))
((null list))
(if (equal (car (car list)) elt)
(return i))))
The question is: if we changed *DATA* so that it had (B 33), would we
want the answer to be the number 1 or the number 33? I'll assume that
the desired answer was 33, so rather than the above code, we will
eliminate that counter from the program. Let's also rename the
program to something more appropriate.
(defvar *data* '((a 0) (b 33) (c 22) (d 137) (e 42) (f 56) (g 69) (h 77)))
(defun get-number (elt)
(do ((list *data* (cdr list)))
((null list))
(if (equal (caar list) elt)
(return (cadar list)))))
This version also uses shorthand contractions like CAAR to mean (CAR (CAR ...)).
I don't think it's good style to go more than three (C...R) deep, though.
Finally, there is another feature of the DO statement that you should
probably use in this program. After the end-test-form, you can specify
the result-form which will be the return value:
(DO ((var init step))
((end-test-form result-form))
(body...))
If you omit the result-form, DO will return NIL, unless you bypass
the end-test and break out of the loop, by using RETURN in the body.
Note that the result-form doesn't need a RETURN statement itself.
So we will eliminate the RETURN in the body, and move the form that
computes the return value, putting it right into the DO statement.
This means we must also move the termination condition from the
IF statement into the DO form. This makes sense, because there
is already one termination condition (NULL LIST) there already.
It's easier to see all the termination conditions in one place,
at the front of the DO statement, rather than sprinkling them
around in RETURN statements in the body.
(defun get-number (elt)
(do ((list *data* (cdr list)))
((or (null list)
(equal (caar list) elt))
(cadar list))))
Note that in this version of the program, the DO statement doesn't
have any body at all - just iteration statements!
If I were using DO for this, that's how I would write the program.
Now, here is another way to write same program, using DOLIST:
(defun get-number (elt)
(dolist (x *data*)
(if (equal elt (car x))
(return (cadr x)))))
And here are a couple of ways to write it using the LOOP macro:
(defun get-number (elt)
(loop for x in *data*
when (equal (car x) elt)
return (cadr x)))
(defun get-number (elt)
(loop for (x y) in *data*
when (equal x elt)
return y))
You might actually be interested in computing the index of a symbol,
rather than finding the number associated with it in *DATA*.
In that case, you could use an earlier version of GETINDEX that
stepped the counter variable I and returned it. Or, you could
do the same thing by using Lisp's built-in function POSITION:
(defun getindex (elt)
(position elt *data* :key #'car))
(getindex 'b) => 1
On a final note, you might want to learn about "association lists".
These are lists that have the same shape as your *DATA* does.
Maybe this problem was supposed to be about such "a-lists".
An a-list is a list of cells, where the CAR of each cell
is a key value and the CDR contains the associated data.
(defvar *data* '((a 0)
(z . 42)
(r 33 yellow)
(b 22 blue (saturation 99))
(g 137 green)))
(cadr (assoc 'a *data*)) => 0
(cadr (assoc 'g *data*)) => 137
(cdr (assoc 'b *data*)) => (22 BLUE (SATURATION 99))
(cdr (assoc 'z *data*)) => 42
You might want to further study lists, and the Lisp forms CONS,
LIST and QUOTE. Hope this helped!
Chris
PS. If you or your organization is interested in Lisp training,
please feel free to contact me for consulting at:
<·············@spacy.Boston.MA.US>
>>>>> On Mon, 7 May 2001 00:10:04 +0200, Francois Aguet ("Francois") writes:
Francois> Hello, I have a very urgent question please.
This appears to be an urgent homework problem, and you will find that
people are more likely to help you if you identify it as such, show the
work you have done so far (as you have), and ask a specific question.
Otherwise it just sounds like you are asking us to do your homework for you.
I am curious; would you please tell me what course this is for,
where you are taking it, and what textbook and Lisp reference
books you are using (if any)?
I can't tell from your example what the problem was supposed to be,
but I'll try to walk you through things, based on what I see.
You have correctly figured out that DO is the general-purpose
iteration construct. It can step variables, such as your "I",
and it has an end-test (in this case, using "="), and a body
of statements (such as your "IF") that are executed unless
the end-test has successfully terminated the loop.
Francois> Why doesn't the following program output anything?
Francois> I would like that, for example, (getindex 'f) returns 5.
(defvar *index* '((a 0)(b 1)(c 2)(d 3)(e 4)(f 5)(g 6)(h 7)))
(defun getindex (el)
(do ((i 0 (+ i 1)))
((= i (length *index*)))
(if (equal (first (nth i *index*)) el)
(rest (nth i *index*)))))
The proximal answer to your question is that you have not specified
any value for DO to return. Unless you somehow specify otherwise,
a DO statement will return NIL.
Your program loops across every element in the list *INDEX*
and does not terminate until every element has been examined.
Each time through, the IF statement tests whether the selected
element is the one you are looking for: if so, it returns it;
otherwise IF returns NIL. There is nothing magic that would
cause the IF statement to exit the DO loop. So, you are testing
to see if you found the desired element, ignores the answer,
and your loop continues to process every element, regardless!
The most obvious modification to your program would be to
use a RETURN statement in the "then" clause of your IF statement.
(defun getindex (el)
(do ((x *index* (cdr x))
(i 0 (+ i 1)))
((= i (length *index*)))
(if (equal (first (nth i *index*)) el)
(return (car (rest (nth i *index*)))))))
RETURN will cause an immediate exit from the DO loop,
bypassing the end-test (= I (LENGTH *INDEX*))
and returning the value you have specified.
But there are much better ways of writing this program.
It is unlikely that your assignment is mainly about learning the
syntax of a DO loop, or about how to break out using RETURN.
You're probably supposed to understand something about the
structure of the data representation in Lisp.
The way you are selecting the elements to be processed is not
very Lispy. The key to your program will be that it is using
a list, which you have named *INDEX*. You should draw yourself
a diagram of the list structure that you have created for *INDEX*
with the DEFVAR statement. When you understand what lists are
good for, you will write the program very differently.
In your data, you have a bunch of small lists that look like (C 2).
You could reference the elements of this list by index:
(nth 0 '(c 2)) => C
(nth 1 '(c 2)) => 2
But lists are not arrays, and using indexes is not the
normal way to access their elements.
A list is a "linked list" of cells, and each cell has two parts
(called CAR and CDR). The CAR of the cell contains a piece of
data (such as "C"), and the CDR of the cell points to the next
cell in the list (or to NIL if this is the end of the list).
For example, the list (C 2) is composed of two cells linked together.
The first cell contains the C, and a pointer to the second cell.
The second cell contains a 2 and a NIL:
(car '(c 2)) => C
(cdr '(c 2)) => (2)
(car (cdr '(c 2)) => 2
(cdr (cdr '(c 2)) => NIL
Notice that we can get from the C to the 2 by simply traversing
the list with CDR. If we are interested in looking at the list
elements in order, we do not need to compute and use an index.
We simply ask for the next part of the list, walking forward
through the list structure itself!
In *INDEX*, you have linked a bunch of small lists together.
The CAR of first cell points to the list (A 0), and the
CDR of the first cell points to the list (B 1), etc.
Note well that your data is not layed out in memory as sequential
elements, as an array would be. Rather, it is composed of cells
that each a contain a pointer linking it to the next cell.
Unlike arrays, lists are not indexed. This means that for the NTH
function to reference a list element by index, it must start at the
beginning of the list and visit each cell in the list, counting them
as it goes, until it gets to the one you want.
But as you saw above, if you already have the list (or a piece of it)
in hand, you can simply walk down to each element using the CDR function.
Here's your program again:
(defun getindex (el)
(do ((x *index* (cdr x))
(i 0 (+ i 1)))
((= i (length *index*)))
(if (equal (first (nth i *index*)) el)
(return (car (rest (nth i *index*)))))))
Your program uses NTH to sequentially index the list, but that is
very inefficient compared to just walking the through the data.
Moreover, each time through the loop, your program computes the
maximum index (LENGTH) of the list. As a general rule of thumb,
since that termination value is a constant, you should move it
outside of the loop, rather than re-compute it each time around.
In this case, moving LENGTH to the outside would probably be a very
good idea, because it might be a particularly expensive computation.
Lisp does not specify how lists are stored in memory, but we do know
that they are not really like arrays. It is most likely that lists
do not have internal structure headers that remember their bounds.
That implies that the LENGTH function probably has to compute the
length by walking through the entire list, counting cells as it goes,
until it reaches the final cell.
In your program, each time through your loop: LENGTH starts at the
beginning of the list of data and walks all the way down to count
up the extent, to see if we are done; then NTH has to start at the
beginning of the list of data and walk all the way down to the cell
that you are interested in; and if it turns out to be the right one,
then you repeat the NTH from the beginning to get the answer.
That's ridiculously inefficient!
A better way to write the program is to eliminate the indexed
references to the data. Instead of using NTH and LENGTH, we will
simply start at the beginning of the list, and each time through
the loop we will use CDR to only walk down one cell in order to
get to the next piece of data.
Here's your list of lists of data; I have renamed the variable to
*DATA* because there's nothing in this program (at least in what
we can see) that has anything to do with indexing anything.
(defvar *data* '((a 0) (b 1) (c 2) (d 3) (e 4) (f 5) (g 6) (h 7)))
I'm renaming the variable EL to be ELT, just because I think it's
more descriptive. ELT is also the name of a built-in Lisp function,
but that's okay. There is no confusion between the variable named
ELT and the function named ELT, because they appear in different
positions: ELT is not being used here in a function-call position.
Here's the new program:
(defun getindex (elt)
(do ((i 0 (+ i 1))
(list *data* (cdr list)))
((null list))
(if (equal (car (car list)) elt)
(return (car (cdr (car list)))))))
This DO loop contains a new variable called LIST, which will hold the
part of the list that we have not yet processed. Initially, that's
the entire *DATA* list. Each sucessive time through the loop, LIST
gets to be the CDR of itself; that is, each time through we get the
remaining unprocessed data (the front is popped off).
So the first time through, LIST is ((A 0) (B 1) (C 2) ...)
the second time, LIST is ((B 1) (C 2) (D 3)...)
You can take apart the expressions in the IF statement to see what we
are testing. Remember that LIST contains the unprocessed contents of
our *DATA*, so the CAR of that will be things like (B 1).
We test the CAR of (B 1), which is B. If the test succeeds, we RETURN
a piece of LIST: the CAR is (B 1), the CDR of that is (1), and the
CAR of that is just 1.
We don't need to compute the LENGTH of the data -- we don't care how
long it is. We only care about whether there is any more of it left
to process. So our end-test is (NULL LIST), which returns T if
we have exhausted all the data (that is, when LIST is NIL).
We still have the DO loop counting up a variable I from 0, and at the
end of the loop it will be the zero-based index of the desired element.
We are not using that value for anything, and the compiler will probably
even warn about this "unused variable".
At this point, there's a question about what the program was intended to do.
Was it supposed to find the index to the desired element? If so, then
perhaps we should simply do (RETURN I) instead of returning the 1 from
the (B 1) piece of data. That version of the program would look like this:
(defun getindex (elt)
(do ((i 0 (+ i 1))
(list *data* (cdr list)))
((null list))
(if (equal (car (car list)) elt)
(return i))))
The question is: if we changed *DATA* so that it had (B 33), would we
want the answer to be the number 1 or the number 33? I'll assume that
the desired answer was 33, so rather than the above code, we will
eliminate that counter from the program. Let's also rename the
program to something more appropriate.
(defvar *data* '((a 0) (b 33) (c 22) (d 137) (e 42) (f 56) (g 69) (h 77)))
(defun get-number (elt)
(do ((list *data* (cdr list)))
((null list))
(if (equal (caar list) elt)
(return (cadar list)))))
This version also uses shorthand contractions like CAAR to mean (CAR (CAR ...)).
I don't think it's good style to go more than three (C...R) deep, though.
Finally, there is another feature of the DO statement that you should
probably use in this program. After the end-test-form, you can specify
the result-form which will be the return value:
(DO ((var init step))
((end-test-form result-form))
(body...))
If you omit the result-form, DO will return NIL, unless you bypass
the end-test and break out of the loop, by using RETURN in the body.
Note that the result-form doesn't need a RETURN statement itself.
So we will eliminate the RETURN in the body, and move the form that
computes the return value, putting it right into the DO statement.
This means we must also move the termination condition from the
IF statement into the DO form. This makes sense, because there
is already one termination condition (NULL LIST) there already.
It's easier to see all the termination conditions in one place,
at the front of the DO statement, rather than sprinkling them
around in RETURN statements in the body.
(defun get-number (elt)
(do ((list *data* (cdr list)))
((or (null list)
(equal (caar list) elt))
(cadar list))))
Note that in this version of the program, the DO statement doesn't
have any body at all - just iteration statements!
If I were using DO for this, that's how I would write the program.
Now, here is another way to write same program, using DOLIST:
(defun get-number (elt)
(dolist (x *data*)
(if (equal elt (car x))
(return (cadr x)))))
And here are a couple of ways to write it using the LOOP macro:
(defun get-number (elt)
(loop for x in *data*
when (equal (car x) elt)
return (cadr x)))
(defun get-number (elt)
(loop for (x y) in *data*
when (equal x elt)
return y))
You might actually be interested in computing the index of a symbol,
rather than finding the number associated with it in *DATA*.
In that case, you could use an earlier version of GETINDEX that
stepped the counter variable I and returned it. Or, you could
do the same thing by using Lisp's built-in function POSITION:
(defun getindex (elt)
(position elt *data* :key #'car))
(getindex 'b) => 1
On a final note, you might want to learn about "association lists".
These are lists that have the same shape as your *DATA* does.
Maybe this problem was supposed to be about such "a-lists".
An a-list is a list of cells, where the CAR of each cell
is a key value and the CDR contains the associated data.
(defvar *data* '((a 0)
(z . 42)
(r 33 yellow)
(b 22 blue (saturation 99))
(g 137 green)))
(cadr (assoc 'a *data*)) => 0
(cadr (assoc 'g *data*)) => 137
(cdr (assoc 'b *data*)) => (22 BLUE (SATURATION 99))
(cdr (assoc 'z *data*)) => 42
You might want to further study lists, and the Lisp forms CONS,
LIST and QUOTE. Hope this helped!
Chris
PS. If you or your organization is interested in Lisp training,
please feel free to contact me for consulting at:
<·············@spacy.Boston.MA.US>
>>>>> "CS" == Christopher Stacy <······@spacy.Boston.MA.US> writes:
CS> You have correctly figured out that DO is the general-purpose
CS> iteration construct. It can step variables, such as your "I",
CS> and it has an end-test (in this case, using "="), and a body
CS> of statements (such as your "IF") that are executed unless the
CS> end-test has successfully terminated the loop.
CS> [...]
Excuse me, but you're kind of long-winded. Could you please just tell
me which paragraph to cut-and-paste to send to my TA? B-)
~ESP
P.S. Joke!
--
Evan Prodromou
····@prodromou.san-francisco.ca.us