I've written a macro for myself called RCOND which has the same
structure as an ordinary COND block, but instead of testing each
clause in order, it selects a clause randomly and applies it's test.
If the test matches, the corresponding code is evaluated, and is
returned as the value of RCOND.
For example,
(rcond
((eq 1 1) 1)
((
Mike G. wrote:
> I've written a macro for myself called RCOND which has the same
> structure as an ordinary COND block, but instead of testing each
> clause in order, it selects a clause randomly and applies it's test.
> If the test matches, the corresponding code is evaluated, and is
> returned as the value of RCOND.
>
> For example,
>
> (rcond
> ((eq 1 1) 1)
> ((
On Aug 7, 2:56 pm, "Mike G." <···············@gmail.com> wrote:
> I've written a macro for myself called RCOND which has the same
> structure as an ordinary COND block, but instead of testing each
> clause in order, it selects a clause randomly and applies it's test.
> If the test matches, the corresponding code is evaluated, and is
> returned as the value of RCOND.
>
> For example,
>
> (rcond
> ((eq 1 1) 1)
> ((
Bleh. Google. Let me start that block over again:
(rcond
((eq 1 1) 1)
((eq 2 2) 2)
((eq 3 3) 3)
((eq 4 4) 4))
This is an obtuse way of returning a random integer between 1 and 4.
(defmacro rcond (&rest clauses)
(let ((foo (gensym))
(num -1))
(append
`(let ((,foo (random ,(length clauses)))))
(list
(cons 'cond
(map 'list #'(lambda (clause)
(incf num)
(cons `(and (equal ,num ,foo)
,(first clause))
(rest clause)))
clauses))))))
This works OK. But for large lists of clauses, I end up testing the
number for EQ many, many times. I'd like to just jump to the random
clause, test (optionally perform code) and exit. I have a macro which
does this using EVAL, but that isn't optimal either.
How can I jump to the Nth expression in my code?
-M
On Aug 7, 1:09 pm, "Mike G." <···············@gmail.com> wrote:
> Mike G. wrote:
> > I've written a macro for myself called RCOND which has the same
> > structure as an ordinary COND block, but instead of testing each
> > clause in order, it selects a clause randomly and applies it's test.
> > If the test matches, the corresponding code is evaluated, and is
> > returned as the value of RCOND.
>
> > For example,
>
> > (rcond
> > ((eq 1 1) 1)
> > ((
>
> On Aug 7, 2:56 pm, "Mike G." <···············@gmail.com> wrote:
>
> > I've written a macro for myself called RCOND which has the same
> > structure as an ordinary COND block, but instead of testing each
> > clause in order, it selects a clause randomly and applies it's test.
> > If the test matches, the corresponding code is evaluated, and is
> > returned as the value of RCOND.
>
> > For example,
>
> > (rcond
> > ((eq 1 1) 1)
> > ((
>
> Bleh. Google. Let me start that block over again:
>
> (rcond
> ((eq 1 1) 1)
> ((eq 2 2) 2)
> ((eq 3 3) 3)
> ((eq 4 4) 4))
>
> This is an obtuse way of returning a random integer between 1 and 4.
>
> (defmacro rcond (&rest clauses)
> (let ((foo (gensym))
> (num -1))
> (append
> `(let ((,foo (random ,(length clauses)))))
> (list
> (cons 'cond
> (map 'list #'(lambda (clause)
> (incf num)
> (cons `(and (equal ,num ,foo)
> ,(first clause))
> (rest clause)))
> clauses))))))
>
> This works OK. But for large lists of clauses, I end up testing the
> number for EQ many, many times. I'd like to just jump to the random
> clause, test (optionally perform code) and exit. I have a macro which
> does this using EVAL, but that isn't optimal either.
>
> How can I jump to the Nth expression in my code?
>
> -M
This looks fun, but have you tried (random 4) ?
-Jason
On Aug 7, 4:28 pm, Jason <·······@gmail.com> wrote:
> On Aug 7, 1:09 pm, "Mike G." <···············@gmail.com> wrote:
>
>
>
> > Mike G. wrote:
> > > I've written a macro for myself called RCOND which has the same
> > > structure as an ordinary COND block, but instead of testing each
> > > clause in order, it selects a clause randomly and applies it's test.
> > > If the test matches, the corresponding code is evaluated, and is
> > > returned as the value of RCOND.
>
> > > For example,
>
> > > (rcond
> > > ((eq 1 1) 1)
> > > ((
>
> > On Aug 7, 2:56 pm, "Mike G." <···············@gmail.com> wrote:
>
> > > I've written a macro for myself called RCOND which has the same
> > > structure as an ordinary COND block, but instead of testing each
> > > clause in order, it selects a clause randomly and applies it's test.
> > > If the test matches, the corresponding code is evaluated, and is
> > > returned as the value of RCOND.
>
> > > For example,
>
> > > (rcond
> > > ((eq 1 1) 1)
> > > ((
>
> > Bleh. Google. Let me start that block over again:
>
> > (rcond
> > ((eq 1 1) 1)
> > ((eq 2 2) 2)
> > ((eq 3 3) 3)
> > ((eq 4 4) 4))
>
> > This is an obtuse way of returning a random integer between 1 and 4.
>
> > (defmacro rcond (&rest clauses)
> > (let ((foo (gensym))
> > (num -1))
> > (append
> > `(let ((,foo (random ,(length clauses)))))
> > (list
> > (cons 'cond
> > (map 'list #'(lambda (clause)
> > (incf num)
> > (cons `(and (equal ,num ,foo)
> > ,(first clause))
> > (rest clause)))
> > clauses))))))
>
> > This works OK. But for large lists of clauses, I end up testing the
> > number for EQ many, many times. I'd like to just jump to the random
> > clause, test (optionally perform code) and exit. I have a macro which
> > does this using EVAL, but that isn't optimal either.
>
> > How can I jump to the Nth expression in my code?
>
> > -M
>
> This looks fun, but have you tried (random 4) ?
>
> -Jason
:) Of course, I use RANDOM in my macro to decide which clause to try.
The example given that generates a random integer between 1 and 4 is
just a toy to demonstrate the functionality of RCOND.
Its real purpose is that I have a whole slew of conditions in some
game logic, many of which will eval to T, but I don't want to always
fire on the first one (else the computer will play the same way every
time). With RCOND, the machine will use a random tactic.
On Aug 7, 1:49 pm, "Mike G." <···············@gmail.com> wrote:
> On Aug 7, 4:28 pm, Jason <·······@gmail.com> wrote:
>
>
>
>
>
> > On Aug 7, 1:09 pm, "Mike G." <···············@gmail.com> wrote:
>
> > > Mike G. wrote:
> > > > I've written a macro for myself called RCOND which has the same
> > > > structure as an ordinary COND block, but instead of testing each
> > > > clause in order, it selects a clause randomly and applies it's test.
> > > > If the test matches, the corresponding code is evaluated, and is
> > > > returned as the value of RCOND.
>
> > > > For example,
>
> > > > (rcond
> > > > ((eq 1 1) 1)
> > > > ((
>
> > > On Aug 7, 2:56 pm, "Mike G." <···············@gmail.com> wrote:
>
> > > > I've written a macro for myself called RCOND which has the same
> > > > structure as an ordinary COND block, but instead of testing each
> > > > clause in order, it selects a clause randomly and applies it's test.
> > > > If the test matches, the corresponding code is evaluated, and is
> > > > returned as the value of RCOND.
>
> > > > For example,
>
> > > > (rcond
> > > > ((eq 1 1) 1)
> > > > ((
>
> > > Bleh. Google. Let me start that block over again:
>
> > > (rcond
> > > ((eq 1 1) 1)
> > > ((eq 2 2) 2)
> > > ((eq 3 3) 3)
> > > ((eq 4 4) 4))
>
> > > This is an obtuse way of returning a random integer between 1 and 4.
>
> > > (defmacro rcond (&rest clauses)
> > > (let ((foo (gensym))
> > > (num -1))
> > > (append
> > > `(let ((,foo (random ,(length clauses)))))
> > > (list
> > > (cons 'cond
> > > (map 'list #'(lambda (clause)
> > > (incf num)
> > > (cons `(and (equal ,num ,foo)
> > > ,(first clause))
> > > (rest clause)))
> > > clauses))))))
>
> > > This works OK. But for large lists of clauses, I end up testing the
> > > number for EQ many, many times. I'd like to just jump to the random
> > > clause, test (optionally perform code) and exit. I have a macro which
> > > does this using EVAL, but that isn't optimal either.
>
> > > How can I jump to the Nth expression in my code?
>
> > > -M
>
> > This looks fun, but have you tried (random 4) ?
>
> > -Jason
>
> :) Of course, I use RANDOM in my macro to decide which clause to try.
> The example given that generates a random integer between 1 and 4 is
> just a toy to demonstrate the functionality of RCOND.
>
> Its real purpose is that I have a whole slew of conditions in some
> game logic, many of which will eval to T, but I don't want to always
> fire on the first one (else the computer will play the same way every
> time). With RCOND, the machine will use a random tactic.- Hide quoted text -
>
> - Show quoted text -
I see... That's a pretty cool idea! I played around with what you
propose, and have a simple solution. It's not in macro form, but I am
sure that you could convert it to one if you like.
Check this out.
(set 'ls '(
((eq 1 1) 11) ; true
((eq 1 2) 12)
((eq 2 2) 22) ; true
((eq 2 3) 23)
((eq 3 2) 32)
((eq 3 3) 33) ; true
((eq 3 4) 34)
((eq 4 4) 44) ; true
))
(defun rcond-trues (ls)
(if (null ls) '()
(let ((n (car ls)))
(if (and (car n) (eval (car n)))
(cons (cdr n) (rcond-trues (cdr ls)))
(rcond-trues (cdr ls))))))
(defun rcond-worker (ls)
(let ((n (length ls)))
(car (elt ls (random n)))))
(defun rcond (ls)
(rcond-worker (rcond-trues ls)))
(rcond ls)
I have not tested this thoroughly, so I can't say what side effects
might present. Being a relative noob to lisp, I am sure there is a
better way to do this.
-Jason
Jason <·······@gmail.com> writes:
> Check this out.
>
> (set 'ls '(
[snip]
I don't think I've ever seen anyone use SET in real life. Why'd you
pick it over, say, defvar, defparameter, setf, and setq?
> (defun rcond-trues (ls)
> (if (null ls) '()
> (let ((n (car ls)))
> (if (and (car n) (eval (car n)))
> (cons (cdr n) (rcond-trues (cdr ls)))
> (rcond-trues (cdr ls))))))
The use of EVAL means that no lexical variables can be used in the
COND-like code, and that's a pretty big restriction that would make
this approach not all that useful.
> I have not tested this thoroughly, so I can't say what side effects
> might present. Being a relative noob to lisp, I am sure there is a
> better way to do this.
It's simple, but not very typical of normal lisp, and not something to
really learn from. Unless the lesson is "don't do it that way".
Zach
On 2007-08-07, Mike G. <···············@gmail.com> wrote:
>> On Aug 7, 1:09 pm, "Mike G." <···············@gmail.com> wrote:
>> > > I've written a macro for myself called RCOND which has the same
>> > > structure as an ordinary COND block, but instead of testing
>> > > each clause in order, it selects a clause randomly and applies
>> > > it's test. If the test matches, the corresponding code is
>> > > evaluated, and is returned as the value of RCOND.
>>
>> > (rcond
>> > ((eq 1 1) 1)
>> > ((eq 2 2) 2)
>> > ((eq 3 3) 3)
>> > ((eq 4 4) 4))
>>
>> > This is an obtuse way of returning a random integer between 1 and
>> > 4.
Indeed. :)
>> > (defmacro rcond (&rest clauses)
>> > (let ((foo (gensym))
>> > (num -1))
>> > (append
>> > `(let ((,foo (random ,(length clauses)))))
>> > (list
>> > (cons 'cond
>> > (map 'list #'(lambda (clause)
>> > (incf num)
>> > (cons `(and (equal ,num ,foo)
>> > ,(first clause))
>> > (rest clause)))
>> > clauses))))))
>>
>> > This works OK. But for large lists of clauses, I end up testing
>> > the number for EQ many, many times. I'd like to just jump to the
>> > random clause, test (optionally perform code) and exit. I have a
>> > macro which does this using EVAL, but that isn't optimal either.
>>
>> > How can I jump to the Nth expression in my code?
>>
[snip]
> The example given that generates a random integer between 1 and 4 is
> just a toy to demonstrate the functionality of RCOND.
>
> Its real purpose is that I have a whole slew of conditions in some
> game logic, many of which will eval to T, but I don't want to always
> fire on the first one (else the computer will play the same way
> every time). With RCOND, the machine will use a random tactic.
So
(rcond
(t 1)
(t 2)
(t 3)
(t 4))
more-or-less expands into
(let ((g (random 4)))
(cond
((and (equal g 0) t) 1)
((and (equal g 1) t) 2)
((and (equal g 2) t) 3)
((and (equal g 3) t) 4)))
yes?
Try instead expanding into an ecase (untested):
(ecase (random 4)
(0 (when t 1))
(1 (when t 2))
(2 (when t 3))
(3 (when t 4)))
-- L
"Mike G." <···············@gmail.com> writes:
> (defmacro rcond (&rest clauses)
> (let ((foo (gensym))
> (num -1))
> (append
> `(let ((,foo (random ,(length clauses)))))
> (list
> (cons 'cond
> (map 'list #'(lambda (clause)
> (incf num)
> (cons `(and (equal ,num ,foo)
> ,(first clause))
> (rest clause)))
> clauses))))))
>
>
> This works OK. But for large lists of clauses, I end up testing the
> number for EQ many, many times. I'd like to just jump to the random
> clause, test (optionally perform code) and exit. I have a macro which
> does this using EVAL, but that isn't optimal either.
>
> How can I jump to the Nth expression in my code?
The simplest would seem to be Larry's ECASE solution.
It does have the same drawback as your example in that if the test on
the randomly chosen clause DOESN'T evaluate to true, then you don't do
anything. That is different from COND in that COND will keep trying
clauses until they are all exhausted.
Unfortunately, a simple loop that keeps trying RCOND with other random
elements will also not work, since then you could end up in a infinite
loop if there really are no applicable clauses.
Another alternative would be to create a vector of functions, one for
each clause. You could then select individual values out of this vector
for testing. It would also let you construct new, reduced vectors to
try this again until the choices are exhausted. That would require a
fair bit of consing, though.
A different approach would use the vector, but first permute the order
of clauses, and then run down them in order. Or else just permute a
vector of indices and use them in a loop to evaluate either the
vector-based or the ECASE-based solutions.
--
Thomas A. Russ, USC/Information Sciences Institute
···@sevak.isi.edu (Thomas A. Russ) writes:
> The simplest would seem to be Larry's ECASE solution.
>
> It does have the same drawback as your example in that if the test on
> the randomly chosen clause DOESN'T evaluate to true, then you don't do
> anything. That is different from COND in that COND will keep trying
> clauses until they are all exhausted.
>
> Unfortunately, a simple loop that keeps trying RCOND with other random
> elements will also not work, since then you could end up in a infinite
> loop if there really are no applicable clauses.
Something vaguely like this might work. It's vaguely O(n^2) though the
n is unlikely to be large, so that probably doesn't matter. And it could
cons, for that matter, if you had a lot of clauses. But since most COND
clauses don't, maybe that doesn't matter. I didn't do a thorough check
that I avoided the infinite loop thing, but it worked in a few trials.
Anyway, I think something of this form would kinda work.
(defmacro rcond (&rest clauses) ;not heavily tested. caveat emptor
(let ((done (gensym "DONE"))
(count (gensym "COUNT"))
(case (gensym "CASE"))
(mask (gensym "MASK"))
(n (gensym "N"))
(c (gensym "C"))
(k (gensym "K")))
`(loop named ,done
with ,mask = 0
for ,count downfrom ,(length clauses) above 0
for ,n = (1+ (random ,count))
do (let ((case (let ((,k 0))
(loop for ,c below ,(length clauses)
when (not (logbitp ,c ,mask))
do (incf ,k)
when (= ,k ,n)
do (setq ,mask (setf (ldb (byte 1 ,c) ,mask) 1))
(return ,c)
finally ; I wonder if static typing would catch this case
(error "whoops: internal error")))))
(ecase case
,@(loop for clause in clauses
for c from 0
collect `((,c) (when ,(car clause)
(return-from ,done
(progn ,@(cdr clause)))))))))))
(pprint (macroexpand-1 '(rcond (t 3) (t 4) (t 5))))
(LOOP NAMED #:DONE3027
WITH #:MASK3030 = 0
FOR #:COUNT3028 DOWNFROM 3 ABOVE 0
FOR #:N3031 = (1+ (RANDOM #:COUNT3028))
DO (LET ((CASE
(LET ((#:K3033 0))
(LOOP FOR #:C3032 BELOW 3
WHEN (NOT (LOGBITP #:C3032 #:MASK3030)) DO (INCF #:K3033)
WHEN (= #:K3033 #:N3031)
DO (SETQ #:MASK3030 (SETF (LDB (BYTE 1 #:C3032) #:MASK3030) 1))
(RETURN #:C3032)
FINALLY (ERROR "whoops: internal error")))))
(ECASE CASE
((0) (WHEN T (RETURN-FROM #:DONE3027 (PROGN 3))))
((1) (WHEN T (RETURN-FROM #:DONE3027 (PROGN 4))))
((2) (WHEN T (RETURN-FROM #:DONE3027 (PROGN 5)))))))
Of course, in my experience, random number generators rarely "feel good"
when called on very small integers... but that's another question.
Kent M Pitman <······@nhplace.com> writes:
> do (setq ,mask (setf (ldb (byte 1 ,c) ,mask) 1))
Actually, that setq is probably at least spurious and I suspect
actively wrong. Someone can debug that for me since it's late and
I can't be bothered. I put it there when debugging the code because
of paranoia when something wasn't working because of some older version
of SETF (I think in Maclisp) where SETF of LDB didn't actually assign
a place [we hadn't evolved the place notion back then] and only returned
the integer. CL, by contrast, returns the value [arg 2], so this does
the wrong thing for CL.
But I didn't say this all worked for sure. Just that I imagined
something like it would work. And I still do. ;)
On Aug 8, 8:48 am, Kent M Pitman <······@nhplace.com> wrote:
> ····@sevak.isi.edu (Thomas A. Russ) writes:
>
> > The simplest would seem to be Larry's ECASE solution.
>
> > It does have the same drawback as your example in that if the test on
> > the randomly chosen clause DOESN'T evaluate to true, then you don't do
> > anything. That is different from COND in that COND will keep trying
> > clauses until they are all exhausted.
>
> > Unfortunately, a simple loop that keeps trying RCOND with other random
> > elements will also not work, since then you could end up in a infinite
> > loop if there really are no applicable clauses.
>
> Something vaguely like this might work. It's vaguely O(n^2) though the
> n is unlikely to be large, so that probably doesn't matter. And it could
If RCOND is at all like COND it has to continue evaluating clauses
after evaluating and testing other clauses but it should not test the
same clause twice. This suggest that the only difference between COND
and RCOND is the sequence in which the clauses are tested. Some
confusion in this discussion is due to the bad example. A better
example would be:
(rcond
((and (print 1) nil) 1)
((and (print 2) nil) 2)
((and (print 3) nil) 3)
((and (print 4) nil) 4)
(t (print 5) 5))
Notice that out of N clauses only one, the last one, will succeed. The
result should always be N (in the particular case N=5). When executing
the form multiple times one should see the sequence in which the
clauses are tested. Each clause should only be tested once. The code
above will some test some clauses multiple times and will not always
return 5.
Russ (above) hinted at one correct solution of creating a set of n!
vectors capturing all the n! clause permutations and then picking one
(random n!). The permutations could be generated and stored at macro
expand time making the execution quite efficient. Unfortunately this
only works for small n. Storage can be avoided by computing
deterministically the (random n!)th permutation of <1, 2, 3, ... n> at
runtime.
I am sure there are some tricks unexplored but algorithms based on
permutations are not scalable. In other words RCOND is probably
intrinsically unimplementable for large Ns.
··············@gmail.com writes:
> If RCOND is at all like COND it has to continue evaluating clauses
> after evaluating and testing other clauses but it should not test the
> same clause twice.
Unless I made an error in middle-of-the-night coding (which I'm
leaving others to find), that's what my code does. It has a bitmask
of clauses it has tried so it doesn't try them again as it loops retrying.
> I am sure there are some tricks unexplored but algorithms based on
> permutations are not scalable. In other words RCOND is probably
> intrinsically unimplementable for large Ns.
I think the implementation I suggested will work for large N, just slowly.
On Aug 8, 4:19 pm, Kent M Pitman <······@nhplace.com> wrote:
> ··············@gmail.com writes:
> > If RCOND is at all like COND it has to continue evaluating clauses
> > after evaluating and testing other clauses but it should not test the
> > same clause twice.
>
> Unless I made an error in middle-of-the-night coding (which I'm
> leaving others to find), that's what my code does. It has a bitmask
> of clauses it has tried so it doesn't try them again as it loops retrying.
>
> > I am sure there are some tricks unexplored but algorithms based on
> > permutations are not scalable. In other words RCOND is probably
> > intrinsically unimplementable for large Ns.
>
> I think the implementation I suggested will work for large N, just slowly.
evaluating ...
(rcond
((and (print 1) nil) 1)
((and (print 2) nil) 2)
((and (print 3) nil) 3)
((and (print 4) nil) 4)
(t (print 5) 5))
a couple of times (MCL 5) the code in its current form seems to
neither prevent duplicates nor guarantee to evaluate all the clauses
necessary. Because there is a clause with a true condition, #5, it
would have to return 5 no matter in which order the clauses get
tested.
4
4
4
2
2
NIL
?
2
5
5
?
5
5
?
1
3
2
3
2
NIL
ps: when I said cannot be implemented I need to qualify by adding as
efficiently as COND. For small n the precomputed permutations could be
executed about as fast as the regular COND. It would take a single
call to random to pick a permutation.
To deal with larger n one could use a O(n^2) non deterministic
permutation approach based on random functions. Perhaps this is what
your function is trying to do? I am not sure, however, why your code
would have the potential to go into an infinite loop as there is no
need for a try and repeat strategy.
··············@gmail.com writes:
> evaluating ...
>
> (rcond
> ((and (print 1) nil) 1)
> ((and (print 2) nil) 2)
> ((and (print 3) nil) 3)
> ((and (print 4) nil) 4)
> (t (print 5) 5))
>
> a couple of times (MCL 5) the code in its current form seems to
> neither prevent duplicates nor guarantee to evaluate all the clauses
> necessary. Because there is a clause with a true condition, #5, it
> would have to return 5 no matter in which order the clauses get
> tested.
Not if you make the change I suggested. You seem to have ignored the
post I sent with the information about the bug I'd seen and not fixed,
and just gone ahead and tested the buggy version.
> ps: when I said cannot be implemented I need to qualify by adding as
> efficiently as COND.
COND is efficient in code space, consing space, and speed. It's hard
to hold RCOND to all three of these efficiencies at the same time. If
you trade off any one of these, you can probably achieve the other two.
> For small n the precomputed permutations could be
> executed about as fast as the regular COND. It would take a single
> call to random to pick a permutation.
Using pre-cached permutations is an interesting trick though it means
pre-allocating some potentially large structures. I was trying to avoid
consing. If I get time later, I'll try your suggested technique, but maybe
you could implement it and offer it for display yourself...?
> To deal with larger n one could use a O(n^2) non deterministic
> permutation approach based on random functions.
> Perhaps this is what your function is trying to do?
(I provided the source code. Did you not look at it? I sort of expected
a query like "what does this line do?" or "where does it do <x>?"
if you had...)
Mine keeps a mask of bits for each clause and seeks a randomly chosen
clause, setting its bit. It has to search the bit mask for the nth
open slot each time.
Incidentally, I'm not suggesting my approach as "obviously right". I was
just trying to use it to illustrate the fact that there are trade-offs
in the algorithms one could use, and to pick a solution that others were
not suggesting. (It's also one that uses arbitrary precision arithmetic
to interesting advantage because it starts with fixnums and gracefully
overflows to bignums in unlikely cases...)
> I am not sure, however, why your code would have the potential to go
> into an infinite loop as there is no need for a try and repeat strategy.
With the fix applied [removing the unwanted setq I'd mentioned before],
I don't THINK it will. I can't say for sure whether it would have otherwise.
It wasn't doing its bookkeeping right.
(defmacro rcond (&rest clauses) ;still not heavily tested. caveat emptor
(let ((done (gensym "DONE"))
(count (gensym "COUNT"))
(case (gensym "CASE"))
(mask (gensym "MASK"))
(n (gensym "N"))
(c (gensym "C"))
(k (gensym "K")))
`(loop named ,done
with ,mask = 0
for ,count downfrom ,(length clauses) above 0
for ,n = (1+ (random ,count))
do (let ((case (let ((,k 0))
(loop for ,c below ,(length clauses)
when (not (logbitp ,c ,mask))
do (incf ,k)
when (= ,k ,n)
do (setf (ldb (byte 1 ,c) ,mask) 1)
(return ,c)
finally ; I wonder if static typing would catch this case
(error "whoops: internal error")))))
(ecase case
,@(loop for clause in clauses
for c from 0
collect `((,c) (when ,(car clause)
(return-from ,done
(progn ,@(cdr clause)))))))))))
(dotimes (I 10)
(print `(result ,(rcond ((and (print 1) nil) 1)
((and (print 2) nil) 2)
((and (print 3) nil) 3)
((and (print 4) nil) 4)
(t (print 5) 5)))))
1
4
3
5
(RESULT 5)
4
2
3
1
5
(RESULT 5)
1
5
(RESULT 5)
5
(RESULT 5)
1
2
3
5
(RESULT 5)
5
(RESULT 5)
5
(RESULT 5)
3
4
2
1
5
(RESULT 5)
1
5
(RESULT 5)
4
2
3
1
5
(RESULT 5)
NIL
(defun foo (printp)
(dotimes (I 10)
(let ((result
(rcond (t 1)
(t 2)
(t 3)
(t 4)
(t 5))))
(if printp (print result) result))))
(compile 'foo)
FOO, NIL, NIL
(foo t)
1
2
4
4
1
5
3
1
1
4
NIL
(time (foo nil))
Timing the evaluation of (FOO NIL)
user time = 0.000
system time = 0.000
Elapsed time = 0:00:00
Allocation = 0 bytes standard / 0 bytes conses
0 Page faults
NIL
On Aug 7, 6:23 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> "Mike G." <···············@gmail.com> writes:
> > (defmacro rcond (&rest clauses)
> > (let ((foo (gensym))
> > (num -1))
> > (append
> > `(let ((,foo (random ,(length clauses)))))
> > (list
> > (cons 'cond
> > (map 'list #'(lambda (clause)
> > (incf num)
> > (cons `(and (equal ,num ,foo)
> > ,(first clause))
> > (rest clause)))
> > clauses))))))
>
> > This works OK. But for large lists of clauses, I end up testing the
> > number for EQ many, many times. I'd like to just jump to the random
> > clause, test (optionally perform code) and exit. I have a macro which
> > does this using EVAL, but that isn't optimal either.
>
> > How can I jump to the Nth expression in my code?
>
> The simplest would seem to be Larry's ECASE solution.
>
> It does have the same drawback as your example in that if the test on
> the randomly chosen clause DOESN'T evaluate to true, then you don't do
> anything. That is different from COND in that COND will keep trying
> clauses until they are all exhausted.
>
> Unfortunately, a simple loop that keeps trying RCOND with other random
> elements will also not work, since then you could end up in a infinite
> loop if there really are no applicable clauses.
>
> Another alternative would be to create a vector of functions, one for
> each clause. You could then select individual values out of this vector
> for testing. It would also let you construct new, reduced vectors to
> try this again until the choices are exhausted. That would require a
> fair bit of consing, though.
>
> A different approach would use the vector, but first permute the order
> of clauses, and then run down them in order. Or else just permute a
> vector of indices and use them in a loop to evaluate either the
> vector-based or the ECASE-based solutions.
>
> --
> Thomas A. Russ, USC/Information Sciences Institute
Indeed. In my application, I'm not worried about falling through the
RCOND without doing anything - if this happens, the computer simply
forfeited that opportunity. It will loop and get another. My game
isn't turn-based, so this doesn't give the human an implicit
advantage. The computer's reaction time even with forfeiture, will
still be faster than mine :)
OTOH, I agree that a general-purpose RCOND should try to match the
functionality of COND (keep trying clauses until they are exhausted,
or one of them works).
"Mike G." <···············@gmail.com> writes:
> Indeed. In my application, I'm not worried about falling through the
> RCOND without doing anything - if this happens, the computer simply
> forfeited that opportunity. It will loop and get another. My game
> isn't turn-based, so this doesn't give the human an implicit
> advantage. The computer's reaction time even with forfeiture, will
> still be faster than mine :)
Have you considered representing your RCOND clauses as explicit rules?
Maintaining lexical context becomes more complicated, but you may gain
some flexibility. For example, having the system choose some RCOND
clause with a higher probability than the others would mean adding
numbers to the form (e.g., you might not want a system to choose
between obvious-winning-move and really-dumb-losing-move with equal
probability). If the system's performance changes over time
(learning, adapting to a specific user, or having past choices affect
future ones), it would require more complexities in RCOND. Pulling
that level of control out of the procedural code can sometimes be
worthwhile.
Mike G. <···············@gmail.com> wrote:
> This works OK. But for large lists of clauses, I end up testing the
> number for EQ many, many times. I'd like to just jump to the random
> clause, test (optionally perform code) and exit. I have a macro which
> does this using EVAL, but that isn't optimal either.
>
> How can I jump to the Nth expression in my code?
One option is to construct a tree of comparisons, rather than linearly
testing all of the options. There's a one implementation of this idea
by Michael Weber at:
<http://www.foldr.org/~michaelw/log/programming/lisp/icfp-contest-2006-vm>
Using ECASE/TREE from that page, you could write:
(defmacro rcond (&rest clauses)
`(ecase/tree (random ,(length clauses))
,@(loop for clause in clauses
for i from 0
collect (,i (when ,(car clause)
,@(cdr clause))))))
Another option is to create create a function for each of the rcond
clauses, put those functions into an array, and then (funcall (aref
array (random (length array)))).
--
Juho Snellman
Mike G. wrote:
> On Aug 7, 2:56 pm, "Mike G." <···············@gmail.com> wrote:
>> I've written a macro for myself called RCOND which has the same
>> structure as an ordinary COND block, but instead of testing each
>> clause in order, it selects a clause randomly and applies it's test.
>> If the test matches, the corresponding code is evaluated, and is
>> returned as the value of RCOND.
>>
>> For example,
>>
>> (rcond
>> ((eq 1 1) 1)
>> ((
>
> Bleh. Google. Let me start that block over again:
>
> (rcond
> ((eq 1 1) 1)
> ((eq 2 2) 2)
> ((eq 3 3) 3)
> ((eq 4 4) 4))
>
> This is an obtuse way of returning a random integer between 1 and 4.
>
> (defmacro rcond (&rest clauses)
> (let ((foo (gensym))
> (num -1))
> (append
> `(let ((,foo (random ,(length clauses)))))
> (list
> (cons 'cond
> (map 'list #'(lambda (clause)
> (incf num)
> (cons `(and (equal ,num ,foo)
> ,(first clause))
> (rest clause)))
> clauses))))))
>
>
> This works OK. But for large lists of clauses, I end up testing the
> number for EQ many, many times. I'd like to just jump to the random
> clause, test (optionally perform code) and exit. I have a macro which
> does this using EVAL, but that isn't optimal either.
>
> How can I jump to the Nth expression in my code?
If goto is considered harmful, does that extend to go as well?
I'm sure a macro could easily write one of these (and generalize it
for N clauses):
(defun rcond (x)
(tagbody
(case (random 3) ; don't bother catching errors
(0 (go r1))
(1 (go r2))
(2 (go r3))) ; -- just fall through...
r1
(return-from rcond
(when (< x 4) "hi"))
r2
(return-from rcond
(when (< x 7) "there"))
r3
(return-from rcond
(when (< x 10) 42))))
(defun ercond (x)
(let ((count 0))
(flet ((check ()
(incf count)
(when (>= count 3)
(error "no matching case"))))
(tagbody
(case (random 3) ; don't bother catching errors
(0 (go r1))
(1 (go r2))
(2 (go r3))) ; -- just fall through...
r1
(when (< x 4)
(return-from ercond "hi"))
(check)
r2
(when (< x 7)
(return-from ercond "there"))
(check)
r3
(when (< x 10)
(return-from ercond 42))
(check)
(go r1)))))
(rcond 3) will randomly match any of the clauses; (ercond 30) will
quickly throw an error.
- Daniel
On Aug 7, 11:56 am, "Mike G." <···············@gmail.com> wrote:
> I've written a macro for myself called RCOND which has the same
> structure as an ordinary COND block, but instead of testing each
> clause in order, it selects a clause randomly and applies it's test.
> If the test matches, the corresponding code is evaluated, and is
> returned as the value of RCOND.
Just out of curiosity, what would be an example application for RCOND?
I was thinking something like a rule-based system with a "pick a
random rule to test" component.
mfh
On Aug 9, 5:33 pm, "Mark H." <············@gmail.com> wrote:
> On Aug 7, 11:56 am, "Mike G." <···············@gmail.com> wrote:
>
> > I've written a macro for myself called RCOND which has the same
> > structure as an ordinary COND block, but instead of testing each
> > clause in order, it selects a clause randomly and applies it's test.
> > If the test matches, the corresponding code is evaluated, and is
> > returned as the value of RCOND.
>
> Just out of curiosity, what would be an example application for RCOND?
>
> I was thinking something like a rule-based system with a "pick a
> random rule to test" component.
>
> mfh
I'm using it in a game. The computer's tactics are determined by
RCOND. The clauses of my RCOND block check for basic applicability of
certain tactics. In most cases, many tactics apply to a given
situation. Instead of always executing the top-most tactic (which
would happen in an ordinary COND) I now have RCOND, which randomly
picks a clause to fire on.
It works pretty well.
I also have a macro that I've posted here called KOND. This macro
keeps track of how many times each clause fires. After some stats are
gathered, a human can flip a switch and recompile the code (to make
the macro fire again) -- this time instead of inserting stat-grabbing
code into the COND, KOND will re-order the COND clauses according to
the previously collected stats.
In the future, my game will keep track of what tactics have been
successful, and use those stats with a KOND-like block (probably with
randomization of the top N best tactics). Then I'll have to figure out
a way to arrange for the program to re-compile itself at certain
intervals :)
On Aug 10, 12:52 pm, "Mike G." <···············@gmail.com> wrote:
> I'm using it in a game. The computer's tactics are determined by
> RCOND. The clauses of my RCOND block check for basic applicability of
> certain tactics. In most cases, many tactics apply to a given
> situation. Instead of always executing the top-most tactic (which
> would happen in an ordinary COND) I now have RCOND, which randomly
> picks a clause to fire on.
Hm, that's pretty neat! I guess I would have thought of this as
"randomly picking a rule from a set of rules," but you could compile a
rule-based system easily into CL code by using a construct like RCOND.
> I also have a macro that I've posted here called KOND. This macro
> keeps track of how many times each clause fires. After some stats are
> gathered, a human can flip a switch and recompile the code (to make
> the macro fire again) -- this time instead of inserting stat-grabbing
> code into the COND, KOND will re-order the COND clauses according to
> the previously collected stats.
Now THIS could be very handy for profiling, even without the RCOND
stuff...
mfh