I was just wondering if anyone had any idea on how to address this
problem. I would like to write code for a function in LISP that will
help a car go from point A to point J passing all points with no
backtracking using a depth-first search. Any ideas?
On May 16, 4:21 pm, ·········@yahoo.com wrote:
> I was just wondering if anyone had any idea on how to address this
> problem. I would like to write code for a function in LISP that will
> help a car go from point A to point J passing all points with no
> backtracking using a depth-first search. Any ideas?
Well, it is required that I use LISP. C++ would certainly be easier.
I've been having so much problems just writing condtional statements.
I have the basic pseudocode for the depth-first search but I'm having
trouble converting it into code.
·········@yahoo.com writes:
> On May 16, 4:21�pm, ·········@yahoo.com wrote:
>> I was just wondering if anyone had any idea on how to address this
>> problem. I would like to write code for a function in LISP that will
>> help a car go from point A to point J passing all points with no
>> backtracking using a depth-first search. Any ideas?
>
> Well, it is required that I use LISP. C++ would certainly be easier.
> I've been having so much problems just writing condtional statements.
> I have the basic pseudocode for the depth-first search but I'm having
> trouble converting it into code.
You have the first part right, using a car. . .
·········@yahoo.com wrote:
> On May 16, 4:21 pm, ·········@yahoo.com wrote:
>
>>I was just wondering if anyone had any idea on how to address this
>>problem. I would like to write code for a function in LISP that will
>>help a car go from point A to point J passing all points with no
>>backtracking using a depth-first search. Any ideas?
>
>
> Well, it is required that I use LISP. C++ would certainly be easier.
> I've been having so much problems just writing condtional statements.
> I have the basic pseudocode for the depth-first search but I'm having
> trouble converting it into code.
Fantastic, you have progressed from "any ideas?" to a specific syntax
issue. Now we're talking. Post the pseudocode or the C++ you would write
or try translating to Lisp and ask when you get stuck on a specific
syntax issue. Boil it down to a ten-line case or cond statement and say
what is stumping you. Folks here fall over noobs trying to help the ones
that post disastrous first attempts. I better not say what they do to
folks who just post the homework and say "Any ideas?".
:)
cond and case, btw, are akin to switch but they do not do that braindead
trick of falling through to the next case by default. cond let's you put
any form in on the left side and goes that way on non-nil. Use "t" as
the last left side for the C :default mechanism.
case only works where your left sides are all literals, and use
otherwise to get the :default thing.
Don't forget the parens.
kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
Ken Tilton wrote:
> case only works where your left sides are all literals, and use
> otherwise to get the :default thing.
You speak in a Lisp. The C keyword is "default:".
What Kenny's saying is that
{
int x=3;
switch(x)
{
case 0:
do_a();
break;
case 1:
do_b();
break;
default:
do_c();
break;
}
}
is equivalent to
(let ((x 3))
(case x
(0 (do-a))
(1 (do-b))
(t (do-c))))
is equivalent to
(let ((x 3))
(cond
((= x 0)
(do-a))
((= x 1)
(do-b))
(t
(do-c))))
is equivalent to
{
int x=3;
if(x==0)
do_a();
else if(x==1)
do_b();
else
do_c();
}
CLL loves noobs. First we praise them for trying the language, then
we devour them for not having a couple decades of CL experience.
- Daniel
D Herring wrote:
> (let ((x 3))
> (case x
> (0 (do-a))
> (1 (do-b))
> (t (do-c))))
>
> is equivalent to
>
> (let ((x 3))
> (cond
> ((= x 0)
> (do-a))
> ((= x 1)
> (do-b))
> (t
> (do-c))))
You are right, this is equivalent for x=3, but are you sure this is
equivalent for all x? The CLHS says for CASE:
| These macros allow the conditional execution of a body of forms in a clause
| that is selected by matching the test-key on the basis of its identity.
I think "identity" means, that it uses EQ, where you can find:
| The effect is that Common Lisp makes no guarantee that eq is true even when
| both its arguments are ``the same thing'' if that thing is a character or
| number.
So there might be Lisp implementations, where (eq 1 1) is not t.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> D Herring wrote:
>
>> (let ((x 3))
>> (case x
>> (0 (do-a))
>> (1 (do-b))
>> (t (do-c))))
>>
>> is equivalent to
>>
>> (let ((x 3))
>> (cond
>> ((= x 0)
>> (do-a))
>> ((= x 1)
>> (do-b))
>> (t
>> (do-c))))
>
> You are right, this is equivalent for x=3, but are you sure this is
> equivalent for all x? The CLHS says for CASE:
>
> | These macros allow the conditional execution of a body of forms in a clause
> | that is selected by matching the test-key on the basis of its identity.
>
> I think "identity" means, that it uses EQ, where you can find:
>
> | The effect is that Common Lisp makes no guarantee that eq is true even when
> | both its arguments are ``the same thing'' if that thing is a character or
> | number.
>
> So there might be Lisp implementations, where (eq 1 1) is not t.
Yeah, my examples weren't strictly equivalent. However, SBCL and
CLISP both expand CASE to use COND with EQL, not EQ. A quick look
didn't find any clarification in dpANS, but CLtL2 says "If key is in
the keylist (that is, is eql to any item in the keylist) of a clause" ...
So I'm good with symbols, characters, and fixnums [(eql 1 1.0)=>nil
but (= 1 1.0)=>t; so not all numbers]. Since the C switch statement
is also restricted to int's, I'd call that close enough.
Now the C gurus can point out that == applies to all built-in numeric
types, leading to a similar difference in the two C snippets...
Any implementation where (case 1 (0 0) (1 1) (t :fail)) returns :fail
should not be touched. I mean, ?!? If not characters or integers,
what can CASE be used for? EQ is an odd beast which should rarely be
used. To expose it in the user API of a standard macro would be
highly suspect.
If someone points out such a macro, I guess I'll "pull a Kenny" and
discover a new secret capability. :-P
- Daniel
In article <································@comcast.com>,
D Herring <········@at.tentpost.dot.com> wrote:
> Frank Buss wrote:
> > D Herring wrote:
> >
> >> (let ((x 3))
> >> (case x
> >> (0 (do-a))
> >> (1 (do-b))
> >> (t (do-c))))
> >>
> >> is equivalent to
> >>
> >> (let ((x 3))
> >> (cond
> >> ((= x 0)
> >> (do-a))
> >> ((= x 1)
> >> (do-b))
> >> (t
> >> (do-c))))
> >
> > You are right, this is equivalent for x=3, but are you sure this is
> > equivalent for all x? The CLHS says for CASE:
> >
> > | These macros allow the conditional execution of a body of forms in a
> > clause
> > | that is selected by matching the test-key on the basis of its identity.
> >
> > I think "identity" means, that it uses EQ, where you can find:
> >
> > | The effect is that Common Lisp makes no guarantee that eq is true even
> > when
> > | both its arguments are ``the same thing'' if that thing is a character or
> > | number.
> >
> > So there might be Lisp implementations, where (eq 1 1) is not t.
>
> Yeah, my examples weren't strictly equivalent. However, SBCL and
> CLISP both expand CASE to use COND with EQL, not EQ. A quick look
> didn't find any clarification in dpANS, but CLtL2 says "If key is in
> the keylist (that is, is eql to any item in the keylist) of a clause" ...
The CLHS specification of CASE says "If the test-key is the same as any
key for that clause". The glossary entry for "same" says that if no
predicate is specified, EQL is used.
In general, comparisons in CL rarely default to EQ, EQL is the usual
default comparison, which is the reason for that default in the
definition of "same".
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry Margolin wrote:
> The CLHS specification of CASE says "If the test-key is the same as any
> key for that clause". The glossary entry for "same" says that if no
> predicate is specified, EQL is used.
Sometimes I think the CLHS is difficult to read. Why not just writing "If
the test-key is eql to any key for that clause", instead of linking to the
glossary entry "same", which describes with only 131 words, that "eql" is
meant? An why using the word "identity", which is misleading, because the
glossary says: "identical: the same under eq".
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
In article <································@40tude.net>,
Frank Buss <··@frank-buss.de> wrote:
> Barry Margolin wrote:
>
> > The CLHS specification of CASE says "If the test-key is the same as any
> > key for that clause". The glossary entry for "same" says that if no
> > predicate is specified, EQL is used.
>
> Sometimes I think the CLHS is difficult to read. Why not just writing "If
> the test-key is eql to any key for that clause", instead of linking to the
> glossary entry "same", which describes with only 131 words, that "eql" is
> meant? An why using the word "identity", which is misleading, because the
> glossary says: "identical: the same under eq".
Modularity and abstraction. This wording has to be used in many places,
and it's better to use a single term and then link to the meaning.
Had we decided at the last minute during standardization to change the
default comparison, all that would have been necessary would have been
to change the glossary, not find all the places in the document that
specifically mentioned the predicate.
Why should you be surprised that a document written by computer
programmers would be designed like a well-written computer program. The
glossary is a subroutine library, and "same" is a subroutine.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry Margolin wrote:
> Why should you be surprised that a document written by computer
> programmers would be designed like a well-written computer program. The
> glossary is a subroutine library, and "same" is a subroutine.
I'm suprised that the first sentence of the description is misleading,
because it uses the word "identity", which of course is not linked to the
glossary and is not the same word as "identical", but you have to read the
full description to understand it, and for lazy people like me, who skips
through the documenation until it looks like I have understood it, this is
fatal :-)
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
thus spoke D Herring <········@at.tentpost.dot.com>:
> Any implementation where (case 1 (0 0) (1 1) (t :fail)) returns :fail
> should not be touched.
CASE uses EQL comparison which is guaranteed to work on numbers and
characters.
> If not characters or integers, what can CASE be used for?
A symbol is fine, too.
> EQ is an odd beast which should rarely be used.
EQ shows intent. And i've found myself using EQUAL much more for generic
comparisons.
--
The great peril of our existence lies in the fact that our diet consists
entirely of souls. -- Inuit saying
P� Sat, 17 May 2008 06:08:06 +0200, skrev Frank Buss <··@frank-buss.de>:
> D Herring wrote:
>
>> (let ((x 3))
>> (case x
>> (0 (do-a))
>> (1 (do-b))
>> (t (do-c))))
>>
>> is equivalent to
>>
>> (let ((x 3))
>> (cond
>> ((= x 0)
>> (do-a))
>> ((= x 1)
>> (do-b))
>> (t
>> (do-c))))
>
> You are right, this is equivalent for x=3, but are you sure this is
> equivalent for all x? The CLHS says for CASE:
>
> | These macros allow the conditional execution of a body of forms in a
> clause
> | that is selected by matching the test-key on the basis of its identity.
>
> I think "identity" means, that it uses EQ, where you can find:
>
Nop, it means EQL.
CASE uses EQL and thus works for places, char's and integer's. (not
float's)
--------------
John Thingstad
Frank Buss wrote:
> So there might be Lisp implementations, where (eq 1 1) is not t.
I'm currently learning lisp using 'Practical Common Lisp' and there I
find (in chapter 4):
As some of these examples suggest, you can notate the same
number in many ways. But regardless of how you write them, all
rationals--integers and ratios--are represented internally in
"simplified" form. In other words, the objects that represent
-2/8 or 246/2 aren't distinct from the objects that represent
-1/4 and 123. Similarly, 1.0 and 1.0e0 are just different ways
of writing the same number.
Now to me (with a Java background), objects that are not distinct are
the same object (i.e. two names for the same location in memory). Yet,
although
EQ tests for "object identity"--two objects are EQ if they're
identical
Seibel also writes
Implementations have enough leeway that the expression (eq 3 3)
can legally evaluate to either true or false.
(as Frank Buss pointed out, too).
Now I'm a little bit confused as to which "distinctness" Seibel refers
to in the first part I quoted. I guess from the last part it's obvious
that it doesn't need to be object-identity (as in same location in
memory). So what is it then?
Regards,
Florian
Florian Brucker wrote:
> Frank Buss wrote:
>> So there might be Lisp implementations, where (eq 1 1) is not t.
>
> I'm currently learning lisp using 'Practical Common Lisp' and there I
> find (in chapter 4):
>
> As some of these examples suggest, you can notate the same
> number in many ways. But regardless of how you write them, all
> rationals--integers and ratios--are represented internally in
> "simplified" form. In other words, the objects that represent
> -2/8 or 246/2 aren't distinct from the objects that represent
> -1/4 and 123. Similarly, 1.0 and 1.0e0 are just different ways
> of writing the same number.
>
> Now to me (with a Java background), objects that are not distinct are
> the same object (i.e. two names for the same location in memory). Yet,
> although
I think he means that 2/8 and 1/4 are both stored using the same bit
pattern, but these bits may be stored in different places; thus they
are EQL but may not be EQ. What's not allowed is for 2/8 to be stored
as (/ 2 8) or 0.25 while 1/4 is stored as (/ 1 4).
- Daniel
Florian Brucker <····@torfbold.com> writes:
> Frank Buss wrote:
>> So there might be Lisp implementations, where (eq 1 1) is not t.
>
> I'm currently learning lisp using 'Practical Common Lisp' and there I
> find (in chapter 4):
>
> As some of these examples suggest, you can notate the same
> number in many ways. But regardless of how you write them, all
> rationals--integers and ratios--are represented internally in
> "simplified" form. In other words, the objects that represent
> -2/8 or 246/2 aren't distinct from the objects that represent
> -1/4 and 123. Similarly, 1.0 and 1.0e0 are just different ways
> of writing the same number.
>
> Now to me (with a Java background), objects that are not distinct are
> the same object (i.e. two names for the same location in memory). Yet,
> although
>
> EQ tests for "object identity"--two objects are EQ if they're
> identical
>
> Seibel also writes
>
> Implementations have enough leeway that the expression (eq 3 3)
> can legally evaluate to either true or false.
>
> (as Frank Buss pointed out, too).
>
> Now I'm a little bit confused as to which "distinctness" Seibel refers
> to in the first part I quoted. I guess from the last part it's obvious
> that it doesn't need to be object-identity (as in same location in
> memory). So what is it then?
Think about:
class MyInteger;
new MyInteger(3) == new MyInteger(3) ; EQ
(new MyInteger(3)).eql(new MyInteger(3)) ; EQL
But really, EQ is just an implementation specific operator that you
can forget. Always use at least EQL.
Any compiler worth its bits will optimize EQL to EQ for you, so you
don't even have to think about that:
C/USER[1]> (disassemble (lambda (x) (eql x 'abc)))
Disassembly of function :LAMBDA
(CONST 0) = ABC
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
4 byte-code instructions:
0 (LOAD&PUSH 1)
1 (CONST 0) ; ABC
2 (EQ)
3 (SKIP&RET 2)
NIL
--
__Pascal Bourguignon__
·········@yahoo.com wrote:
> I was just wondering if anyone had any idea on how to address this
> problem. I would like to write code for a function in LISP that will
> help a car go from point A to point J passing all points with no
> backtracking using a depth-first search. Any ideas?
Just wondering what Lisp has to do with it. C would be faster.
hth, kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
·········@yahoo.com wrote on Fri, 16 May 2008:
> I would like to write code [...] with no backtracking using a depth-first
> search. Any ideas?
Are you sure you copied down your homework assignment correctly?
Depth-first search is a backtracking algorithm. What would it mean to do
depth-first search with "no backtracking"?
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
For every complex problem, there is a solution that is simple, neat, and wrong.
-- H. L. Mencken
On Tue, 20 May 2008 09:13:27 -0700, Don Geddis <···@geddis.org> wrote:
>·········@yahoo.com wrote on Fri, 16 May 2008:
>> I would like to write code [...] with no backtracking using a depth-first
>> search. Any ideas?
>
>Are you sure you copied down your homework assignment correctly?
>
>Depth-first search is a backtracking algorithm. What would it mean to do
>depth-first search with "no backtracking"?
I can envision a hybrid breadth/depth algorithm based on a deque with
sibling nodes being queued at the end and children of the current node
pushed at the beginning. That would have the effect of driving the
search deeper along the current path before exploring alternate paths.
It wouldn't backtrack in the conventional sense - the algorithm would
always push forward from the current node but the current node could
change abruptly.
I don't know what I would use it for though ... it would likely be
less efficient at depth first. Apart from code reuse - a single
algorithm could be parameterized to perform either type of search - I
see no obvious advantage to it.
George
--
for email reply remove "/" from address