Re: Translating python to scheme
- From: Aaron W. Hsu <arcfide@xxxxxxxxxxx>
- Date: Sat, 06 Dec 2008 21:51:39 -0600
5lvqbwl02@xxxxxxxxxxxxxx writes:
I'm trying solve the sliding puzzle problem (where you have 9 slots
and 8 tiles arranged in a square) using a*, depth first, and breadth
first search algorithm. I did this ~11 years ago in some AI class in
lisp, but basically at the time I had no idea about lisp, I hated it
with all my heart, and only in retrospect do I realize I was
programming "c" in lisp. The prof didn't help in this matter...
I just did this recently for an AI class. If you are interested in
seeing that code, email me. It is written in a style that is at
least closer to Scheme "standard practice" than what you probably
wrote back in your AI class.
Anywayyyy...I have a python function which can swap two tiles
easily:
def swap(p, (r1, c1), (r2, c2)):
# Swaps *any* two locations and returns new configuration
# Does not concern itself with zero location, etc
# Not sure how to do this functionally
p_p = p[:]
temp = p_p[r1][c1]
p_p[r1][c1] = p_p[r2][c2]
p_p[r2][c2] = temp
return p_p
I'd like to turn this into something you might find in SICP, avoiding
side effects, etc.
Why? Scheme has mutation, and there are reasons to use it. Vectors
can often be employed destructively when they warrant that kind of
behavior. You should make sure to control your mutations, but you don't
need to eliminate them.
(define swap
(lambda (state i j)
(let ([new (vector-copy state)]
[temp (vector-ref state i)])
(vector-set! new i (vector-ref new j))
(vector-set! new j temp)
new)))
All mutation is hidden and controlled inside one little procedure,
and to the outside world, this is essentially a function without any
side-effects, even though side-effects are used internally.
But this brings up a question. Everything I read in SICP is loops via
recursion. I didn't see anything in accessing arrays/vectors/lists in
constant time. I can imagine a loopish/recursive way to read an
element, but I find it harder to imagine a way to create a new list
with a certain element changed, without invoking side-effect producing
things like set!, and without resorting to crazy if/then/else clauses
concerning which element should be changed. This of course gets more
confusing when considering a 2d array. In this case the solution with
python is obvious because of its native support for multidimensional
arrays.
You can treat any one-dimensional array as an n-dimensional array of
an appropriate size. In addition, you need to understand that there
are two different structures in Scheme which are often called lists
in other languages: Lisp Lists and Vectors.
Vectors are fixed length arrays which support fast constant time
element/index level operations such as reference and mutation.
However, extending these vectors with new elements that would change
the size of the vector is not nice, because you have to make a new
vector of the size you want, and then copy the elements.
For operations where the length of the array or number of elements
will be changing, a lisp list is usually better. Lisp Lists are
linked lists, which makes adding to their number easy, but means that
you usually have to search through the list to do certain operations.
So, changing the ith element in a list is expensive, but doing so
with vectors is easy, but adding another element to a vector is
hard, but easy if one uses lists.
In this case, your sliding puzzle has a fixed size or grid which
remains constant throughout the code execution, so you can set
this once at the beginning and then proceed to use Vectors to
do most of your operations.
In C/C++/Python/Matlab/lua/anything else, accessing lists/arrays via
the [i] syntax is easy, and directly translates to a hardware-oriented
pointer lookup somewhere underneath. I don't understand how scheme
does this, given the atomic operations defined in the SICP version of
scheme, which all seem very loop-and-search oriented. How do the
vector and list array access functions work to get constant time
access? (I'm a total scheme newbie here, so I'm not ever sure what
functions I'd be talking about). Is there a c or assembly library
someplace which is secretly being accessed? Are there any inherent
constant-time semantics in scheme which could be used for list/array/
vector access, and which would allow me a guilt-free way of using that
idiom in python for the moment?
As above, you should make sure you understand the difference between
Lisp Lists and Vectors. There is also a SRFI which contains some
kind of library for arrays, which is probably more of what you are
used to. However, the 8-puzzle or similar problems is easily handled
with vectors, which are usually objects with constant time element
level mutation and reference in Schemes. You don't have to do
any kind of trickery to use them, but you should make sure to isolate
your side-effects and only use them when they really make sense.
How would can I rewrite the above function in python using schemish
semantics? How would I rewrite the above function in scheme using an
SICP-ish subset of what's available? I'm using PLT for this.
You don't have to think of the 8-puzzle as a multi-dimensional array,
but if you did want to do this, then you consider an array to be
a vector of 2+N*M elements where N and M are the Number of rows and
colums. Then, you can store the dimensions of the array in the
extra two elements (this can be extended to n dimensions, of course),
and your operations just get the sizes of the array before working
on them in order to compute the right index.
So, in the end, this is one case where side-effects can be justified
if used judiciously, so why not use them?
Again, if you want to see how this can be done, you're welcome to
look at my code, but I warn you that it is "assignment" quality,
which means that I haven't brushed it up to be easy to read.
--
Aaron W. Hsu <arcfide@xxxxxxxxxxx> | <http://www.sacrideo.us>
"Government is the great fiction, through which everybody endeavors to
live at the expense of everybody else." -- Frederic Bastiat
+++++++++++++++ ((lambda (x) (x x)) (lambda (x) (x x))) ++++++++++++++
.
- References:
- Translating python to scheme
- From: 5lvqbwl02
- Translating python to scheme
- Prev by Date: Emacs / Slime questions
- Next by Date: Re: Emacs / Slime questions
- Previous by thread: Translating python to scheme
- Next by thread: Re: Translating python to scheme
- Index(es):
Relevant Pages
|
