(defun partition (array start stop)
(let ((pivot (svref array start))
(i start)
(j stop))
(loop with i = (position-if (lambda (x) (>= x pivot) array :start i :end j)
and j = (position-if (lambda (x) (<= x pivot) array :start i :end j :from-end t)
until (or (< i j) (> i stop) (< j start))
do (prog1 (myswap array i j) (incf i)) ;;; probably something like this..
finally (progn (myswap array start i) ;;;
(return j)))))))
---------
CMUCL tells me som that:
---------
Argument Y is not a REAL: NIL.
Restarts:
0: [ABORT] Return to Top-Level.
Debug (type H for help)
(KERNEL:TWO-ARG-> 1 NIL)
Source: (TWO-ARG-</> TWO-ARG-> > CEILING FLOOR ...)
----------
If I change (lambda (x) (>= x pivot) with (lambda (x) (>= x 5), then
the function runs without giving me any error message. Is it some
trick I can do to make it work?
--
Knut Olav B�hmer
_ _
/ / (_)__ __ ____ __
/ /__/ / _ \/ // /\ \/ / ... The choice of a
/____/_/_//_/\.,_/ /_/\.\ GNU generation
An ideal world is left as an exercise to the reader. (Paul Graham)
Knut Olav B?hmer <·····@linpro.no> wrote:
> If I change (lambda (x) (>= x pivot) with (lambda (x) (>= x 5), then
> the function runs without giving me any error message. Is it some
> trick I can do to make it work?
Are you certain you array really contains no nils? Try with some
debugging output or an assertion like below:
(lambda (x)
(assert (numberp pivot))
(assert (numberp x))
(>= x pivot))
If you can verify that only numbers end up in the comparison, then
you have found a bug in CMUCL.
I would guess likelier that you have some residual junk in your
array... or if MYSWAP is a macro then you better check that it's
not screwing with it's environment.
Cheers,
-- Nikodemus
Just a stupid question, but...
Is that a real code sample? The parens don't match up right
at all on the lambda expressions.
"Knut Olav B�hmer" <·····@linpro.no> wrote in message ····················@emacs.linpro.no...
>
>
> (defun partition (array start stop)
> (let ((pivot (svref array start))
> (i start)
> (j stop))
> (loop with i = (position-if (lambda (x) (>= x pivot) array :start i :end j)
> and j = (position-if (lambda (x) (<= x pivot) array :start i :end j :from-end t)
> until (or (< i j) (> i stop) (< j start))
> do (prog1 (myswap array i j) (incf i)) ;;; probably something like this..
> finally (progn (myswap array start i) ;;;
> (return j)))))))
>
> ---------
> CMUCL tells me som that:
>
> ---------
> Argument Y is not a REAL: NIL.
>
> Restarts:
> 0: [ABORT] Return to Top-Level.
>
> Debug (type H for help)
>
> (KERNEL:TWO-ARG-> 1 NIL)
> Source: (TWO-ARG-</> TWO-ARG-> > CEILING FLOOR ...)
> ----------
>
> If I change (lambda (x) (>= x pivot) with (lambda (x) (>= x 5), then
> the function runs without giving me any error message. Is it some
> trick I can do to make it work?
>
>
> --
> Knut Olav B�hmer
> _ _
> / / (_)__ __ ____ __
> / /__/ / _ \/ // /\ \/ / ... The choice of a
> /____/_/_//_/\.,_/ /_/\.\ GNU generation
>
> An ideal world is left as an exercise to the reader. (Paul Graham)
"Joe Marshall" <·············@attbi.com> wrote in message news:<·······················@sccrnsc01>...
> Just a stupid question, but...
>
> Is that a real code sample? The parens don't match up right
> at all on the lambda expressions.
Indeed.
(position-if (lambda (x) (>= x pivot) array :start i :end j)
->
(position-if (lambda (x) (>= x pivot)) array :start i :end j)
-nick
> "Knut Olav B�hmer" <·····@linpro.no> wrote in message ····················@emacs.linpro.no...
> >
> >
> > (defun partition (array start stop)
> > (let ((pivot (svref array start))
> > (i start)
> > (j stop))
> > (loop with i = (position-if (lambda (x) (>= x pivot) array :start i :end j)
> > and j = (position-if (lambda (x) (<= x pivot) array :start i :end j :from-end t)
> > until (or (< i j) (> i stop) (< j start))
> > do (prog1 (myswap array i j) (incf i)) ;;; probably something like this..
> > finally (progn (myswap array start i) ;;;
> > (return j)))))))
* Nick Levine
> "Joe Marshall" <·············@attbi.com> wrote in message news:<·······················@sccrnsc01>...
> > Just a stupid question, but...
> >
> > Is that a real code sample? The parens don't match up right
> > at all on the lambda expressions.
>
> Indeed.
>
> (position-if (lambda (x) (>= x pivot) array :start i :end j)
>
> ->
>
> (position-if (lambda (x) (>= x pivot)) array :start i :end j)
>
Actualy It was not the code I tested. I changed the code so much that
I just wrote it again in my newsreader. it was suppose to be
(lambda (x) (>= x pivot))
My array contains for sure no nils. If I change it to
(let ((pivot (svref array 0)) I get the same error, but if i write
(let ((pivot (svref array 1)) I get no error. If I write
(svref testarray 0) I get => 1.
testarray is the array i use for testing the function.
I will try upgrading cmucl.
>
> > "Knut Olav B�hmer" <·····@linpro.no> wrote in message ····················@emacs.linpro.no...
> > >
> > >
> > > (defun partition (array start stop)
> > > (let ((pivot (svref array start))
> > > (i start)
> > > (j stop))
> > > (loop with i = (position-if (lambda (x) (>= x pivot) array :start i :end j)
> > > and j = (position-if (lambda (x) (<= x pivot) array :start i :end j :from-end t)
> > > until (or (< i j) (> i stop) (< j start))
> > > do (prog1 (myswap array i j) (incf i)) ;;; probably something like this..
> > > finally (progn (myswap array start i) ;;;
> > > (return j)))))))
--
Knut Olav B�hmer
_ _
/ / (_)__ __ ____ __
/ /__/ / _ \/ // /\ \/ / ... The choice of a
/____/_/_//_/\.,_/ /_/\.\ GNU generation
An ideal world is left as an exercise to the reader. (Paul Graham)
Knut Olav B?hmer <·····@linpro.no> wrote:
> Actualy It was not the code I tested. I changed the code so much that
> I just wrote it again in my newsreader. it was suppose to be
Er. You realize that it's pretty hard to offer comments on code that you
don't present, do you?
Also: is myswap a function or a macro? Did you try with assertion inside
the lambda expression: that's about the easiest way to make sure you are
getting decent input in there.
Cheers,
-- Nikodemus
* Nikodemus Siivola
> Knut Olav B?hmer <·····@linpro.no> wrote:
>
> > Actualy It was not the code I tested. I changed the code so much that
> > I just wrote it again in my newsreader. it was suppose to be
>
> Er. You realize that it's pretty hard to offer comments on code that you
> don't present, do you?
>
> Also: is myswap a function or a macro? Did you try with assertion inside
> the lambda expression: that's about the easiest way to make sure you are
> getting decent input in there.
It is not so important now. If you read the previous mail, I explain
what is wrong.
--
Knut Olav B�hmer
_ _
/ / (_)__ __ ____ __
/ /__/ / _ \/ // /\ \/ / ... The choice of a
/____/_/_//_/\.,_/ /_/\.\ GNU generation
An ideal world is left as an exercise to the reader. (Paul Graham)
"Knut Olav B�hmer" <·····@linpro.no> writes:
> (defun partition (array start stop)
> (let ((pivot (svref array start))
> (i start)
> (j stop))
> (loop with i = (position-if (lambda (x) (>= x pivot) array :start i :end j)
> and j = (position-if (lambda (x) (<= x pivot) array :start i :end j :from-end t)
> until (or (< i j) (> i stop) (< j start))
> do (prog1 (myswap array i j) (incf i)) ;;; probably something like this..
> finally (progn (myswap array start i) ;;;
> (return j)))))))
>
> ---------
> CMUCL tells me som that:
>
> ---------
> Argument Y is not a REAL: NIL.
>
> Restarts:
> 0: [ABORT] Return to Top-Level.
>
> Debug (type H for help)
>
> (KERNEL:TWO-ARG-> 1 NIL)
> Source: (TWO-ARG-</> TWO-ARG-> > CEILING FLOOR ...)
> ----------
It's pretty strange code. First you bind I and J to START and STOP,
and then you rebind them to the results of POSITION-IF. You never
use the outer bindings except to save fewer keystrokes in the
POSITION-IF calls than the outer bindings cost you. Why? :-)
Then, the value of the first POSITION-IF call is always the same
as START. (You're scanning elements START onwards, left to right,
for something >= the pivot, and the pivot is the same thing as
the element at START.)
Then, the value of the second POSITION-IF call is the index
of the rightmost element <= the pivot. So everything to its
right is > the pivot. Well, that makes sense.
But then your termination test stops if (< I J). Well, I is
the same as START and J has to be >= START. So the only way
this test can *not* cause immediate termination is if they're
equal; in other words, if the START element is strictly less
than all the subsequent ones up to STOP.
And then you never update J in the loop, so the test (< J START)
seems a little unnecessary :-).
None of this explains the error message you report. Unfortunately
you haven't really given enough information for a diagnosis. For
instance, we don't know what MYSWAP does, though it seems a fair
bet that it's something like
(defun myswap (a i j)
(rotatef (svref a i) (svref a j)))
and you haven't said how PARTITION gets called (from the
middle of a quicksort routine?). For example: if you call
PARTITION with (>= START STOP) then those calls to
POSITION-IF will return NIL and you'll get the sort of
problem you describe. However, that wouldn't go away on
replacing PIVOT with 5 in the POSITION-IF calls.
But I'll bet that somehow your problem is that I or J
is getting the value NIL, not that any of the values
in the array is NIL. And I'll bet that your problem is
*not* a bug in CMU CL.
Try replacing the UNTIL clause with this:
until (progn
(format t "~&i=~A j=~A~%" i j)
(or (> i j) (> i stop) (< j start)))
Oh, one other thing. You're testing for (> I STOP),
but everything else in the code says you should be
testing for (>= I STOP) instead.
--
Gareth McCaughan
.sig under construc