Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

On Oct 13, 2015, at 11:52 PM, Nguyen Linh Chi  wrote:

> Isnt this the reason we should add 0 at the beginning of the list?
> 
> On 13/ott/2015, at 22:38, Matthias Felleisen  wrote:
> 
>> 
>> Welcome to Racket v6.3.0.1.
>>> (define r .8)
>>> (for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)
>> 'c
>> 
>> Or WORSE: 
>> 
>>> (define r (random))
>>> r
>> 0.011105628290672482
>>> (for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)
>> #f


No, it is bad programming practice to add a sentinel in one function 
that is used by another function. The locations are too far apart, 
because programmers reason about function-sized pieces when they 
approach code. (I did, I refactored, and I got the failure). 

When you code, keep in mind that you write this code for other 
people (possibly your older self in six months from now when you 
revise the program) and it accidentally runs on a computer. 



Here is how I rewrote your function and added a test: 

;; -
;; [Vectorof Automaton] N -> [Listof Automaton]
;; (randomise-over-fitness v n) spawn a list of n fittest automata

;; Nguyen Linh Chi says: 
;; This procedure uses an independent Bernoulli draw. We independently
;; draw a random number (associated with an automaton) for 10 times. How
;; likely an automaton is chosen depends on its own fitness (its interval
;; in the unit scale of the accumulated percentages.)

(module+ test
  (define p0 (vector (automaton 0 1 't1)  (automaton 0 90 't1)))
  (define p1 (list (automaton 0 90 't1)))
  ;; this test case fails if (random) picks a number < .01
  (check-equal?
   (randomise-over-fitness p0 1) (list (automaton 0 90 't1

(define (randomise-over-fitness population0 speed)
  (define fitness (payoff-percentages population0))
  ;; (= (length fitness) (length population))
  ;; fitness is sorted and the last number is ~1.0
  (define population (vector->list population0))
  (for/list ([n (in-range speed)])
[define r (random)]
(define last (for/last ([p population] [f fitness] #:final (< r f)) p))
(or last (error 'randomise "the unlikely happened: r = ~e is too large" 
r

the for/last combined with #:final brings across this intention. 

The way I have written it, the code also points out that,
at least in principle, the world of floating point numbers 
allows for a failure to find a fit enough automaton in this 
list. (Yes, it is a very small chance.) 

***

QUESTION: why do you accumulate fitness across different automata? 
That is, why does payoff-percentages add the payoff of automata_i
to automata_{i+1}? I understand that this means the last automata 
will have a fitness level of close to 1 (modulo rounding floating
point numbers). 





-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[chi]

Thanks for answering me many times. I really appreciate.
For the question, if we dont accumulate and randomise that way, how can 
we spawn new automata regarding their fitness?


For example,
population: a b c d
payoff: 5 0 8 3 (sum = 16)
relative payoff: 5/16 0/16 8/16 3/16

-> The replacement process is a lottery that gives automaton a 5/16 
probability to be chosen, 0 for automaton b, 1/2 for automaton c, 3/16 
for automaton d.


In practice, option 1: this process is usually been done by drawing a 
unit line, marking intervals with different lengths:


+-++---+---+

then you throw a ball randomly in this line, if we see it landing in the 
interval with length 3/16, automaton a is chosen. Bigger interval means 
better chance of being chosen and it can proliferate over time (counted 
by cycles).


Or option 2: we can mark each point on the line associating with an 
automaton (however the line is continuous, hence it has infinite points) 
at random order. In this marking process, we just need to be sure about 
one thing: the number of points for automaton a has to sum up to 5/16 ~ 
25% length of the whole line, the number of points for automaton c has 
to sum up to 50% the length of the line


-> it's better to put all the points for the same automaton next to each 
other so they form a continuous interval (like in option1).


In coding, it's similar. The (random) function throws a ball, and gives 
a point but the computer doesnt simply see which automaton the point 
belongs to.


So we accumulate the payoff according to the order of the automata in 
the population. It's called a cumulative function.

F(a) = p(a) = 5/16
F(b) = p(a) + p(b) = 5/16
...
F(d) = p(a) + p(b) + p(c) + p(d) = 1

so the actual payoff of b will be F(b) - F(a) and so on..
(We can accumulate from the left or from the right).

And now the computer can compare r = (random) with the end point of each 
interval, then it knows what automaton interval the point belongs to.


(I dont know who do this first, it's like every person who starts to do 
evolution simulation will ask this question, and a person who already 
did this practice will tell them, and so on...)




On 14/10/2015 16:42, Matthias Felleisen wrote:


On Oct 13, 2015, at 11:52 PM, Nguyen Linh Chi  wrote:


Isnt this the reason we should add 0 at the beginning of the list?

On 13/ott/2015, at 22:38, Matthias Felleisen  wrote:


Welcome to Racket v6.3.0.1.

(define r .8)
(for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)

'c

Or WORSE:


(define r (random))
r

0.011105628290672482

(for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)

#f


No, it is bad programming practice to add a sentinel in one function
that is used by another function. The locations are too far apart,
because programmers reason about function-sized pieces when they
approach code. (I did, I refactored, and I got the failure).

When you code, keep in mind that you write this code for other
people (possibly your older self in six months from now when you
revise the program) and it accidentally runs on a computer.



Here is how I rewrote your function and added a test:

;; -
;; [Vectorof Automaton] N -> [Listof Automaton]
;; (randomise-over-fitness v n) spawn a list of n fittest automata

;; Nguyen Linh Chi says:
;; This procedure uses an independent Bernoulli draw. We independently
;; draw a random number (associated with an automaton) for 10 times. How
;; likely an automaton is chosen depends on its own fitness (its interval
;; in the unit scale of the accumulated percentages.)

(module+ test
   (define p0 (vector (automaton 0 1 't1)  (automaton 0 90 't1)))
   (define p1 (list (automaton 0 90 't1)))
   ;; this test case fails if (random) picks a number < .01
   (check-equal?
(randomise-over-fitness p0 1) (list (automaton 0 90 't1

(define (randomise-over-fitness population0 speed)
   (define fitness (payoff-percentages population0))
   ;; (= (length fitness) (length population))
   ;; fitness is sorted and the last number is ~1.0
   (define population (vector->list population0))
   (for/list ([n (in-range speed)])
 [define r (random)]
 (define last (for/last ([p population] [f fitness] #:final (< r f)) p))
 (or last (error 'randomise "the unlikely happened: r = ~e is too large" 
r

the for/last combined with #:final brings across this intention.

The way I have written it, the code also points out that,
at least in principle, the world of floating point numbers
allows for a failure to find a fit enough automaton in this
list. (Yes, it is a very small chance.)

***

QUESTION: why do you accumulate fitness across different automata?
That is, why does payoff-percentages add the payoff of automata_i
to automata_{i+1}? I understand that this means the last automata
will have a fitness level of close to 1 (modulo rounding floating

Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

This is perfectly clear and obvious in hindsight. Thanks -- Matthias



On Oct 14, 2015, at 11:23 AM, chi  wrote:

> Thanks for answering me many times. I really appreciate.
> For the question, if we dont accumulate and randomise that way, how can we 
> spawn new automata regarding their fitness?
> 
> For example,
> population: a b c d
> payoff: 5 0 8 3 (sum = 16)
> relative payoff: 5/16 0/16 8/16 3/16
> 
> -> The replacement process is a lottery that gives automaton a 5/16 
> probability to be chosen, 0 for automaton b, 1/2 for automaton c, 3/16 for 
> automaton d.
> 
> In practice, option 1: this process is usually been done by drawing a unit 
> line, marking intervals with different lengths:
> 
> +-++---+---+
> 
> then you throw a ball randomly in this line, if we see it landing in the 
> interval with length 3/16, automaton a is chosen. Bigger interval means 
> better chance of being chosen and it can proliferate over time (counted by 
> cycles).
> 
> Or option 2: we can mark each point on the line associating with an automaton 
> (however the line is continuous, hence it has infinite points) at random 
> order. In this marking process, we just need to be sure about one thing: the 
> number of points for automaton a has to sum up to 5/16 ~ 25% length of the 
> whole line, the number of points for automaton c has to sum up to 50% the 
> length of the line
> 
> -> it's better to put all the points for the same automaton next to each 
> other so they form a continuous interval (like in option1).
> 
> In coding, it's similar. The (random) function throws a ball, and gives a 
> point but the computer doesnt simply see which automaton the point belongs to.
> 
> So we accumulate the payoff according to the order of the automata in the 
> population. It's called a cumulative function.
> F(a) = p(a) = 5/16
> F(b) = p(a) + p(b) = 5/16
> ...
> F(d) = p(a) + p(b) + p(c) + p(d) = 1
> 
> so the actual payoff of b will be F(b) - F(a) and so on..
> (We can accumulate from the left or from the right).
> 
> And now the computer can compare r = (random) with the end point of each 
> interval, then it knows what automaton interval the point belongs to.
> 
> (I dont know who do this first, it's like every person who starts to do 
> evolution simulation will ask this question, and a person who already did 
> this practice will tell them, and so on...)
> 
> 
> 
> On 14/10/2015 16:42, Matthias Felleisen wrote:
>> 
>> On Oct 13, 2015, at 11:52 PM, Nguyen Linh Chi  
>> wrote:
>> 
>>> Isnt this the reason we should add 0 at the beginning of the list?
>>> 
>>> On 13/ott/2015, at 22:38, Matthias Felleisen  wrote:
>>> 
 Welcome to Racket v6.3.0.1.
> (define r .8)
> (for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)
 'c
 
 Or WORSE:
 
> (define r (random))
> r
 0.011105628290672482
> (for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)
 #f
>> 
>> No, it is bad programming practice to add a sentinel in one function
>> that is used by another function. The locations are too far apart,
>> because programmers reason about function-sized pieces when they
>> approach code. (I did, I refactored, and I got the failure).
>> 
>> When you code, keep in mind that you write this code for other
>> people (possibly your older self in six months from now when you
>> revise the program) and it accidentally runs on a computer.
>> 
>> 
>> 
>> Here is how I rewrote your function and added a test:
>> 
>> ;; 
>> -
>> ;; [Vectorof Automaton] N -> [Listof Automaton]
>> ;; (randomise-over-fitness v n) spawn a list of n fittest automata
>> 
>> ;; Nguyen Linh Chi says:
>> ;; This procedure uses an independent Bernoulli draw. We independently
>> ;; draw a random number (associated with an automaton) for 10 times. How
>> ;; likely an automaton is chosen depends on its own fitness (its interval
>> ;; in the unit scale of the accumulated percentages.)
>> 
>> (module+ test
>>   (define p0 (vector (automaton 0 1 't1)  (automaton 0 90 't1)))
>>   (define p1 (list (automaton 0 90 't1)))
>>   ;; this test case fails if (random) picks a number < .01
>>   (check-equal?
>>(randomise-over-fitness p0 1) (list (automaton 0 90 't1
>> 
>> (define (randomise-over-fitness population0 speed)
>>   (define fitness (payoff-percentages population0))
>>   ;; (= (length fitness) (length population))
>>   ;; fitness is sorted and the last number is ~1.0
>>   (define population (vector->list population0))
>>   (for/list ([n (in-range speed)])
>> [define r (random)]
>> (define last (for/last ([p population] [f fitness] #:final (< r f)) p))
>> (or last (error 'randomise "the unlikely happened: r = ~e is too large" 
>> r
>> 
>> the for/last combined with #:final brings across this intention.
>> 
>> The way I have written it, the code 

Re: [racket-users] help on coding finite state automata

[Linh Chi Nguyen]

Matthias you work like a machine, too fast.

Anyway, I have no idea what is type or not type.

But I have some general remarks:

1. A general automaton can have many states, say, 10 states.

so the action in each state can be either cooperate or defect (this is a 
deterministic automaton, for a probabilistic one, they can even randomise 
between cooperate or defect, but the case of deterministic and probabilistic 
should be separated far).

it means that, even for a 2 state automaton, it can happen that both state use 
the same cooperate action.


other small notices
- the all defect automaton start with defecting and always defecting so its 
code is : defect defect defect... not cooperate defect defect... (same for the 
all cooperates one)

- i'm considering to add a mutation phase at the end of each cycle (ie choose 
some random automaton and mutate their code) but im working very slow.

- why dont you define a (match-pair ...) function separately? you insert it in 
the (match-population ...). doesnt it deserve to be outside?

- why you use [i (in-range 10)] in all for loop? what's the difference with [i 
10]. they both produce stream, right?



On Tuesday, 13 October 2015 01:46:04 UTC+2, Matthias Felleisen  wrote:
> Take a crack at it. 
> 
> I am pretty sure I have introduced the proper level of representation 
> independence (I can hear Ben laugh all the way now — Typed Racket
> doesn’t have types) and the typed documentation is pretty solid. (I’ll
> do types later to validate.) 
> 
>

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

See repo. I special-purposed shuffle for my data rep. 


On Oct 13, 2015, at 12:39 PM, Alex Knauth  wrote:

> I've started on that, but shuffle doesn't exist properly yet for generic 
> collections. I could just use (shuffle (sequence->list )), but, what 
> would be the best way of representing this? Generic collections give you the 
> freedom of creating a new type of data structure just for shuffled sequence, 
> so would it be best to do that, or something else?
> 
>> On Oct 12, 2015, at 7:45 PM, Matthias Felleisen  wrote:
>> 
>> Take a crack at it. 
>> 
>> I am pretty sure I have introduced the proper level of representation 
>> independence (I can hear Ben laugh all the way now — Typed Racket
>> doesn’t have types) and the typed documentation is pretty solid. (I’ll
>> do types later to validate.) 
>> 
>>> On Oct 12, 2015, at 7:37 PM, Alex Knauth  wrote:
>>> 
>>> What about Alexis King's persistent vectors?
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

1. Your code is a good example for something that we could use as a benchmark, 
and working on it has helped me find a couple of problems in drracket and typed 
racket. Thanks for triggering my activity. I'll stop soon. 

2. I figured out that your code was general so you could accommodate more 
situations than the ones you explored. My interest diverges from yours. To me 
it is now just a cute benchmark. You will be able to use my insights to speed 
up your performance: 

-- factor the program into separate modules/files, 
-- make the modules independent of the representations, 
-- change automata and population representations to use vectors instead of 
lists, 
-- avoid mutation, 
-- eliminate all situations where you use (append l (list x)); instead use cons 
and reverse the result at the end. 

That way you can run the program 6 times faster. 

3. Otherwise I think your program needs real testing and I think there are two 
bugs: 

a: I created a pull request for this one: 


(define (accumulated-payoff-percentages payoff-list)
(define payoff-sum (apply + payoff-list))
(define-values (accumulated _)
  (for/fold ([accumulated (list 0)] ;; change to '(); otherwise you get a 
list that's too long; your other for loop accidentally compensates for this bug 
 [init 0])
([y (in-list payoff-list)])
[define next-init (+ init (/ y payoff-sum))]
(values (cons next-init accumulated) next-init)))
(reverse accumulated))

b: I don't know how to fix this one properly: 

(define (randomise-over-fitness population fitness speed)
  (for/list ([n (in-range speed)])
[define r (random)]
(define candidate
  (for/and ([p (in-vector population)]
 [f (in-list fitness)]
 #:break (< r f))
p))
candidate))

replace last line with something like this: 
(or candidate (vector-ref population 0

Otherwise there is a non-0 chance otherwise that you get a boolean value 
eventually. I am not sure which default value you want to throw in. 

4. You're right:

-- I re-created the match-pair function when I looked over my code. 
-- using in-list and in-vector and in-range speeds up for loops. 
-- types are irrelevant to your project. They helped me. 

I have pushed the last changes for now. Can we have your permission to use this 
code for a benchmark in our research world? Thanks. 







On Oct 13, 2015, at 12:00 PM, Linh Chi Nguyen  wrote:

> Matthias you work like a machine, too fast.
> 
> Anyway, I have no idea what is type or not type.
> 
> But I have some general remarks:
> 
> 1. A general automaton can have many states, say, 10 states.
> 
> so the action in each state can be either cooperate or defect (this is a 
> deterministic automaton, for a probabilistic one, they can even randomise 
> between cooperate or defect, but the case of deterministic and probabilistic 
> should be separated far).
> 
> it means that, even for a 2 state automaton, it can happen that both state 
> use the same cooperate action.
> 
> 
> other small notices
> - the all defect automaton start with defecting and always defecting so its 
> code is : defect defect defect... not cooperate defect defect... (same for 
> the all cooperates one)
> 
> - i'm considering to add a mutation phase at the end of each cycle (ie choose 
> some random automaton and mutate their code) but im working very slow.
> 
> - why dont you define a (match-pair ...) function separately? you insert it 
> in the (match-population ...). doesnt it deserve to be outside?
> 
> - why you use [i (in-range 10)] in all for loop? what's the difference with 
> [i 10]. they both produce stream, right?
> 
> 
> 
> On Tuesday, 13 October 2015 01:46:04 UTC+2, Matthias Felleisen  wrote:
>> Take a crack at it. 
>> 
>> I am pretty sure I have introduced the proper level of representation 
>> independence (I can hear Ben laugh all the way now — Typed Racket
>> doesn’t have types) and the typed documentation is pretty solid. (I’ll
>> do types later to validate.) 
>> 
>> 
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Benjamin Greenman]

>
> - why you use [i (in-range 10)] in all for loop? what's the difference
> with [i 10]. they both produce stream, right?


Yes, but `in-range` runs faster because of "types". Here's a little example:

#lang racket/base
(define N (expt 10 7))

(time (for ([n (in-range N)])  (void)))
;; cpu time: 36 real time: 36 gc time: 0

(time (for ([n N])  (void)))
;; cpu time: 635 real time: 635 gc time: 0

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Nguyen Linh Chi]

the list 0 isnt a bug. I add it because #:break will break the fitness vector 
at r < f.

For example, 
Population : a b c d
Cumulative fitness .2 .5 .7 1

If the random r = .8, it means that the lottery points to the interval of 
automaton d. But #:break will breaks at .7, and the associated automaton is 
falsely identified as automaton c.

(Hm, right?)

On 13/ott/2015, at 20:21, Nguyen Linh Chi  wrote:

> Hi Mathias, thank you so much for helping me a lot.
> You can use the code as you want, i still have tons of them on my github. 
> (Just dont use it against me ok :D )
> 
> I'd try to see through your list of suggestions.
> 
> About the automata payoff.
> 
> There are 2 different things that are always mixed up: round and cycle. In 
> each cycle, automata are matched in pair and play a game for r rounds per 
> match. At the end of each cycle, there is a replacement period (respawning 
> the fittest). In what im doing, the payoff after r rounds is transformed into 
> the fitness, and the strongest automata (biggest payoff) survive. In some 
> sense they already carry on their relative payoff with them just because they 
> survive.
> 
> Make the automaton carrying their absolute payoff history over cycles would 
> be intereting to see. I've never thought of that and the coding effort is 
> also a reason i havent tried.
> 
> On 13/ott/2015, at 19:59, Matthias Felleisen  wrote:
> 
>> 
>> p.s. One more question. Why do you 'reset' the payoff for automata after 
>> each round? Shouldn't they carry along their overall, historical payoff? 
>> 
>> 
>> 
>> 
>> On Oct 13, 2015, at 1:40 PM, Matthias Felleisen  wrote:
>> 
>>> 
>>> 1. Your code is a good example for something that we could use as a 
>>> benchmark, and working on it has helped me find a couple of problems in 
>>> drracket and typed racket. Thanks for triggering my activity. I'll stop 
>>> soon. 
>>> 
>>> 2. I figured out that your code was general so you could accommodate more 
>>> situations than the ones you explored. My interest diverges from yours. To 
>>> me it is now just a cute benchmark. You will be able to use my insights to 
>>> speed up your performance: 
>>> 
>>> -- factor the program into separate modules/files, 
>>> -- make the modules independent of the representations, 
>>> -- change automata and population representations to use vectors instead of 
>>> lists, 
>>> -- avoid mutation, 
>>> -- eliminate all situations where you use (append l (list x)); instead use 
>>> cons and reverse the result at the end. 
>>> 
>>> That way you can run the program 6 times faster. 
>>> 
>>> 3. Otherwise I think your program needs real testing and I think there are 
>>> two bugs: 
>>> 
>>> a: I created a pull request for this one: 
>>> 
>>> 
>>> (define (accumulated-payoff-percentages payoff-list)
>>> (define payoff-sum (apply + payoff-list))
>>> (define-values (accumulated _)
>>>   (for/fold ([accumulated (list 0)] ;; change to '(); otherwise you get a 
>>> list that's too long; your other for loop accidentally compensates for this 
>>> bug 
>>>  [init 0])
>>> ([y (in-list payoff-list)])
>>> [define next-init (+ init (/ y payoff-sum))]
>>> (values (cons next-init accumulated) next-init)))
>>> (reverse accumulated))
>>> 
>>> b: I don't know how to fix this one properly: 
>>> 
>>> (define (randomise-over-fitness population fitness speed)
>>> (for/list ([n (in-range speed)])
>>> [define r (random)]
>>> (define candidate
>>>   (for/and ([p (in-vector population)]
>>>  [f (in-list fitness)]
>>>  #:break (< r f))
>>> p))
>>> candidate))
>>> 
>>> replace last line with something like this: 
>>> (or candidate (vector-ref population 0
>>> 
>>> Otherwise there is a non-0 chance otherwise that you get a boolean value 
>>> eventually. I am not sure which default value you want to throw in. 
>>> 
>>> 4. You're right:
>>> 
>>> -- I re-created the match-pair function when I looked over my code. 
>>> -- using in-list and in-vector and in-range speeds up for loops. 
>>> -- types are irrelevant to your project. They helped me. 
>>> 
>>> I have pushed the last changes for now. Can we have your permission to use 
>>> this code for a benchmark in our research world? Thanks. 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> On Oct 13, 2015, at 12:00 PM, Linh Chi Nguyen  
>>> wrote:
>>> 
 Matthias you work like a machine, too fast.
 
 Anyway, I have no idea what is type or not type.
 
 But I have some general remarks:
 
 1. A general automaton can have many states, say, 10 states.
 
 so the action in each state can be either cooperate or defect (this is a 
 deterministic automaton, for a probabilistic one, they can even randomise 
 between cooperate or defect, but the case of deterministic and 
 probabilistic should be separated far).
 
 it means that, even for a 2 

Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

Welcome to Racket v6.3.0.1.
> (define r .8)
> (for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)
'c

Or WORSE: 

> (define r (random))
> r
0.011105628290672482
> (for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)
#f




On Oct 13, 2015, at 3:37 PM, Nguyen Linh Chi  wrote:

> the list 0 isnt a bug. I add it because #:break will break the fitness vector 
> at r < f.
> 
> For example, 
> Population : a b c d
> Cumulative fitness .2 .5 .7 1
> 
> If the random r = .8, it means that the lottery points to the interval of 
> automaton d. But #:break will breaks at .7, and the associated automaton is 
> falsely identified as automaton c.
> 
> (Hm, right?)
> 
> On 13/ott/2015, at 20:21, Nguyen Linh Chi  wrote:
> 
>> Hi Mathias, thank you so much for helping me a lot.
>> You can use the code as you want, i still have tons of them on my github. 
>> (Just dont use it against me ok :D )
>> 
>> I'd try to see through your list of suggestions.
>> 
>> About the automata payoff.
>> 
>> There are 2 different things that are always mixed up: round and cycle. In 
>> each cycle, automata are matched in pair and play a game for r rounds per 
>> match. At the end of each cycle, there is a replacement period (respawning 
>> the fittest). In what im doing, the payoff after r rounds is transformed 
>> into the fitness, and the strongest automata (biggest payoff) survive. In 
>> some sense they already carry on their relative payoff with them just 
>> because they survive.
>> 
>> Make the automaton carrying their absolute payoff history over cycles would 
>> be intereting to see. I've never thought of that and the coding effort is 
>> also a reason i havent tried.
>> 
>> On 13/ott/2015, at 19:59, Matthias Felleisen  wrote:
>> 
>>> 
>>> p.s. One more question. Why do you 'reset' the payoff for automata after 
>>> each round? Shouldn't they carry along their overall, historical payoff? 
>>> 
>>> 
>>> 
>>> 
>>> On Oct 13, 2015, at 1:40 PM, Matthias Felleisen  
>>> wrote:
>>> 
 
 1. Your code is a good example for something that we could use as a 
 benchmark, and working on it has helped me find a couple of problems in 
 drracket and typed racket. Thanks for triggering my activity. I'll stop 
 soon. 
 
 2. I figured out that your code was general so you could accommodate more 
 situations than the ones you explored. My interest diverges from yours. To 
 me it is now just a cute benchmark. You will be able to use my insights to 
 speed up your performance: 
 
 -- factor the program into separate modules/files, 
 -- make the modules independent of the representations, 
 -- change automata and population representations to use vectors instead 
 of lists, 
 -- avoid mutation, 
 -- eliminate all situations where you use (append l (list x)); instead use 
 cons and reverse the result at the end. 
 
 That way you can run the program 6 times faster. 
 
 3. Otherwise I think your program needs real testing and I think there are 
 two bugs: 
 
 a: I created a pull request for this one: 
 
 
 (define (accumulated-payoff-percentages payoff-list)
 (define payoff-sum (apply + payoff-list))
 (define-values (accumulated _)
  (for/fold ([accumulated (list 0)] ;; change to '(); otherwise you get a 
 list that's too long; your other for loop accidentally compensates for 
 this bug 
 [init 0])
([y (in-list payoff-list)])
[define next-init (+ init (/ y payoff-sum))]
(values (cons next-init accumulated) next-init)))
 (reverse accumulated))
 
 b: I don't know how to fix this one properly: 
 
 (define (randomise-over-fitness population fitness speed)
 (for/list ([n (in-range speed)])
 [define r (random)]
 (define candidate
  (for/and ([p (in-vector population)]
 [f (in-list fitness)]
 #:break (< r f))
p))
 candidate))
 
 replace last line with something like this: 
 (or candidate (vector-ref population 0
 
 Otherwise there is a non-0 chance otherwise that you get a boolean value 
 eventually. I am not sure which default value you want to throw in. 
 
 4. You're right:
 
 -- I re-created the match-pair function when I looked over my code. 
 -- using in-list and in-vector and in-range speeds up for loops. 
 -- types are irrelevant to your project. They helped me. 
 
 I have pushed the last changes for now. Can we have your permission to use 
 this code for a benchmark in our research world? Thanks. 
 
 
 
 
 
 
 
 On Oct 13, 2015, at 12:00 PM, Linh Chi Nguyen  
 wrote:
 
> Matthias you work like a machine, too fast.
> 
> Anyway, I have no idea 

Re: [racket-users] help on coding finite state automata

[Alex Knauth]

I've started on that, but shuffle doesn't exist properly yet for generic 
collections. I could just use (shuffle (sequence->list )), but, what would 
be the best way of representing this? Generic collections give you the freedom 
of creating a new type of data structure just for shuffled sequence, so would 
it be best to do that, or something else?

> On Oct 12, 2015, at 7:45 PM, Matthias Felleisen  wrote:
> 
> Take a crack at it. 
> 
> I am pretty sure I have introduced the proper level of representation 
> independence (I can hear Ben laugh all the way now — Typed Racket
> doesn’t have types) and the typed documentation is pretty solid. (I’ll
> do types later to validate.) 
> 
>> On Oct 12, 2015, at 7:37 PM, Alex Knauth  wrote:
>> 
>> What about Alexis King's persistent vectors?

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Nguyen Linh Chi]

Hi Mathias, thank you so much for helping me a lot.
You can use the code as you want, i still have tons of them on my github. (Just 
dont use it against me ok :D )

I'd try to see through your list of suggestions.

About the automata payoff.

There are 2 different things that are always mixed up: round and cycle. In each 
cycle, automata are matched in pair and play a game for r rounds per match. At 
the end of each cycle, there is a replacement period (respawning the fittest). 
In what im doing, the payoff after r rounds is transformed into the fitness, 
and the strongest automata (biggest payoff) survive. In some sense they already 
carry on their relative payoff with them just because they survive.

Make the automaton carrying their absolute payoff history over cycles would be 
intereting to see. I've never thought of that and the coding effort is also a 
reason i havent tried.

On 13/ott/2015, at 19:59, Matthias Felleisen  wrote:

> 
> p.s. One more question. Why do you 'reset' the payoff for automata after each 
> round? Shouldn't they carry along their overall, historical payoff? 
> 
> 
> 
> 
> On Oct 13, 2015, at 1:40 PM, Matthias Felleisen  wrote:
> 
>> 
>> 1. Your code is a good example for something that we could use as a 
>> benchmark, and working on it has helped me find a couple of problems in 
>> drracket and typed racket. Thanks for triggering my activity. I'll stop 
>> soon. 
>> 
>> 2. I figured out that your code was general so you could accommodate more 
>> situations than the ones you explored. My interest diverges from yours. To 
>> me it is now just a cute benchmark. You will be able to use my insights to 
>> speed up your performance: 
>> 
>> -- factor the program into separate modules/files, 
>> -- make the modules independent of the representations, 
>> -- change automata and population representations to use vectors instead of 
>> lists, 
>> -- avoid mutation, 
>> -- eliminate all situations where you use (append l (list x)); instead use 
>> cons and reverse the result at the end. 
>> 
>> That way you can run the program 6 times faster. 
>> 
>> 3. Otherwise I think your program needs real testing and I think there are 
>> two bugs: 
>> 
>> a: I created a pull request for this one: 
>> 
>> 
>> (define (accumulated-payoff-percentages payoff-list)
>>   (define payoff-sum (apply + payoff-list))
>>   (define-values (accumulated _)
>> (for/fold ([accumulated (list 0)] ;; change to '(); otherwise you get a 
>> list that's too long; your other for loop accidentally compensates for this 
>> bug 
>>[init 0])
>>   ([y (in-list payoff-list)])
>>   [define next-init (+ init (/ y payoff-sum))]
>>   (values (cons next-init accumulated) next-init)))
>>   (reverse accumulated))
>> 
>> b: I don't know how to fix this one properly: 
>> 
>> (define (randomise-over-fitness population fitness speed)
>> (for/list ([n (in-range speed)])
>>   [define r (random)]
>>   (define candidate
>> (for/and ([p (in-vector population)]
>>[f (in-list fitness)]
>>#:break (< r f))
>>   p))
>>   candidate))
>> 
>> replace last line with something like this: 
>>   (or candidate (vector-ref population 0
>> 
>> Otherwise there is a non-0 chance otherwise that you get a boolean value 
>> eventually. I am not sure which default value you want to throw in. 
>> 
>> 4. You're right:
>> 
>> -- I re-created the match-pair function when I looked over my code. 
>> -- using in-list and in-vector and in-range speeds up for loops. 
>> -- types are irrelevant to your project. They helped me. 
>> 
>> I have pushed the last changes for now. Can we have your permission to use 
>> this code for a benchmark in our research world? Thanks. 
>> 
>> 
>> 
>> 
>> 
>> 
>> 
>> On Oct 13, 2015, at 12:00 PM, Linh Chi Nguyen  
>> wrote:
>> 
>>> Matthias you work like a machine, too fast.
>>> 
>>> Anyway, I have no idea what is type or not type.
>>> 
>>> But I have some general remarks:
>>> 
>>> 1. A general automaton can have many states, say, 10 states.
>>> 
>>> so the action in each state can be either cooperate or defect (this is a 
>>> deterministic automaton, for a probabilistic one, they can even randomise 
>>> between cooperate or defect, but the case of deterministic and 
>>> probabilistic should be separated far).
>>> 
>>> it means that, even for a 2 state automaton, it can happen that both state 
>>> use the same cooperate action.
>>> 
>>> 
>>> other small notices
>>> - the all defect automaton start with defecting and always defecting so its 
>>> code is : defect defect defect... not cooperate defect defect... (same for 
>>> the all cooperates one)
>>> 
>>> - i'm considering to add a mutation phase at the end of each cycle (ie 
>>> choose some random automaton and mutate their code) but im working very 
>>> slow.
>>> 
>>> - why dont you define a (match-pair ...) function separately? you 

Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

p.s. One more question. Why do you 'reset' the payoff for automata after each 
round? Shouldn't they carry along their overall, historical payoff? 




On Oct 13, 2015, at 1:40 PM, Matthias Felleisen  wrote:

> 
> 1. Your code is a good example for something that we could use as a 
> benchmark, and working on it has helped me find a couple of problems in 
> drracket and typed racket. Thanks for triggering my activity. I'll stop soon. 
> 
> 2. I figured out that your code was general so you could accommodate more 
> situations than the ones you explored. My interest diverges from yours. To me 
> it is now just a cute benchmark. You will be able to use my insights to speed 
> up your performance: 
> 
> -- factor the program into separate modules/files, 
> -- make the modules independent of the representations, 
> -- change automata and population representations to use vectors instead of 
> lists, 
> -- avoid mutation, 
> -- eliminate all situations where you use (append l (list x)); instead use 
> cons and reverse the result at the end. 
> 
> That way you can run the program 6 times faster. 
> 
> 3. Otherwise I think your program needs real testing and I think there are 
> two bugs: 
> 
> a: I created a pull request for this one: 
> 
> 
> (define (accumulated-payoff-percentages payoff-list)
>(define payoff-sum (apply + payoff-list))
>(define-values (accumulated _)
>  (for/fold ([accumulated (list 0)] ;; change to '(); otherwise you get a 
> list that's too long; your other for loop accidentally compensates for this 
> bug 
> [init 0])
>([y (in-list payoff-list)])
>[define next-init (+ init (/ y payoff-sum))]
>(values (cons next-init accumulated) next-init)))
>(reverse accumulated))
> 
> b: I don't know how to fix this one properly: 
> 
> (define (randomise-over-fitness population fitness speed)
>  (for/list ([n (in-range speed)])
>[define r (random)]
>(define candidate
>  (for/and ([p (in-vector population)]
> [f (in-list fitness)]
> #:break (< r f))
>p))
>candidate))
> 
> replace last line with something like this: 
>(or candidate (vector-ref population 0
> 
> Otherwise there is a non-0 chance otherwise that you get a boolean value 
> eventually. I am not sure which default value you want to throw in. 
> 
> 4. You're right:
> 
> -- I re-created the match-pair function when I looked over my code. 
> -- using in-list and in-vector and in-range speeds up for loops. 
> -- types are irrelevant to your project. They helped me. 
> 
> I have pushed the last changes for now. Can we have your permission to use 
> this code for a benchmark in our research world? Thanks. 
> 
> 
> 
> 
> 
> 
> 
> On Oct 13, 2015, at 12:00 PM, Linh Chi Nguyen  
> wrote:
> 
>> Matthias you work like a machine, too fast.
>> 
>> Anyway, I have no idea what is type or not type.
>> 
>> But I have some general remarks:
>> 
>> 1. A general automaton can have many states, say, 10 states.
>> 
>> so the action in each state can be either cooperate or defect (this is a 
>> deterministic automaton, for a probabilistic one, they can even randomise 
>> between cooperate or defect, but the case of deterministic and probabilistic 
>> should be separated far).
>> 
>> it means that, even for a 2 state automaton, it can happen that both state 
>> use the same cooperate action.
>> 
>> 
>> other small notices
>> - the all defect automaton start with defecting and always defecting so its 
>> code is : defect defect defect... not cooperate defect defect... (same for 
>> the all cooperates one)
>> 
>> - i'm considering to add a mutation phase at the end of each cycle (ie 
>> choose some random automaton and mutate their code) but im working very slow.
>> 
>> - why dont you define a (match-pair ...) function separately? you insert it 
>> in the (match-population ...). doesnt it deserve to be outside?
>> 
>> - why you use [i (in-range 10)] in all for loop? what's the difference with 
>> [i 10]. they both produce stream, right?
>> 
>> 
>> 
>> On Tuesday, 13 October 2015 01:46:04 UTC+2, Matthias Felleisen  wrote:
>>> Take a crack at it. 
>>> 
>>> I am pretty sure I have introduced the proper level of representation 
>>> independence (I can hear Ben laugh all the way now — Typed Racket
>>> doesn’t have types) and the typed documentation is pretty solid. (I’ll
>>> do types later to validate.) 
>>> 
>>> 
>> 
>> -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Racket Users" group.
>> To unsubscribe from this group and stop receiving emails from it, send an 
>> email to racket-users+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/d/optout.
> 

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 

Re: [racket-users] help on coding finite state automata

[Gustavo Massaccesi]

:( . I tried few modifications, but I didn't get any improvement. I
think that the recalculation of the population is used very seldom, so
any change there will not affect the speed too much.

Most of the time is used in the matches, but I don't have any
suggestion for it (that doesn't include uglifying the code, and
perhaps are also not useful).

Gustavo

On Mon, Oct 12, 2015 at 7:14 PM, Matthias Felleisen
 wrote:
>
>
> So I couldn't resist and wrote the vector-based, allocation-minimizing
> version of the program. I didn't get that much of a performance gain.
>
> I might still change the fitness representation (into a vector) or
> integrate it into 'population' (where it belongs from an SE perspective).
> I doubt this will do much better in terms of speed. A speed-up of 6x
> will have to do for now.
>
> Code at the same old link:
>
>>https://github.com/mfelleisen/sample-fsm
>
>
>
>
>
>
>
> On Oct 12, 2015, at 11:46 AM, Matthias Felleisen  wrote:
>
>>
>> for/last: good point.
>>
>> Based on my previous experience with replacing imperative automata with 
>> functional ones,
>> I don't think replacing the list-based population container with a vector 
>> per se will
>> speed up things much. But the pairing up of neighbors might be a tad faster. 
>> Then again
>> I would have to rewrite shuffle for imperative vectors.
>>
>> I have pulled out the population for now so that you can play with this:
>>
>> https://github.com/mfelleisen/sample-fsm
>>
>> It's easy to run now from the command line.
>>
>>
>>
>> On Oct 12, 2015, at 11:17 AM, Gustavo Massaccesi  wrote:
>>
>>> Sorry for not testing before posting, but in this code:
>>>
>>> (define (randomise-over-fitness accumulated-payoff-percentage population 
>>> speed)
>>> (for/list ([n (in-range speed)])
>>>   [define r (random)]
>>>   (for/and ([p (in-list population)]
>>> [a (in-list accumulated-payoff-percentage)]
>>> #:break (< r a))
>>> p)))
>>>
>>> It looks like the population is stored in a list, and the changes in
>>> the populations create more lists. I think that changing the
>>> implementation to use vectors instead of list would make the code
>>> faster. (But I haven't tested it.)
>>>
>>> Also, I think that for/and can be changed to for/last. I guess it will
>>> almost no no change the speed, but it would make the intention
>>> clearer.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Linh Chi Nguyen]

I dont know how the email group work. If someone keeps receiving emails out of 
interest, please notice me.

Thanks Bryan for the suggestion, it's nice to know, however Im not able to 
afford upgrading now.

And Matthias, for your notice of the spawning process
```
(define (randomise-over-fitness accumulated-payoff-percentage population speed)
  (for/list ([n (in-range speed)])
[define r (random)] ;; SHOULDN"T THIS LINE BE OUTSIDE OF THE for/list 
COMPREHENSION?
(for/and ([p (in-list population)][a (in-list 
accumulated-payoff-percentage)]
  #:break (< r a))
  p)))
```

The randomly generated r has to be inside the for/list loop. Because if it's 
outside, then there is only one random number generated at the beginning, and 
the newly spawn automata will keep being the same one repeatedly.

For example, when the learning speed is s = 10, it means that, 10 old automata 
should be replaced with 10 new ones. And the replacement should be done in 10 
different places in the population.

This procedure is called an independent bernoulli draw. We independently draw a 
random number (associated with an automaton) for 10 times. How likely an 
automaton is chosen depends on its own fitness (its interval in the unit scale 
of the accumulated percentages.)

On Monday, 12 October 2015 03:46:05 UTC+2, Matthias Felleisen  wrote:
> I have pushed some more cleanups, more speed. 
> I added another question to the “spawning” procedure. 
> 
> 
> 
>

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

for/last: good point. 

Based on my previous experience with replacing imperative automata with 
functional ones, 
I don't think replacing the list-based population container with a vector per 
se will 
speed up things much. But the pairing up of neighbors might be a tad faster. 
Then again
I would have to rewrite shuffle for imperative vectors. 

I have pulled out the population for now so that you can play with this: 

https://github.com/mfelleisen/sample-fsm

It's easy to run now from the command line. 



On Oct 12, 2015, at 11:17 AM, Gustavo Massaccesi  wrote:

> Sorry for not testing before posting, but in this code:
> 
> (define (randomise-over-fitness accumulated-payoff-percentage population 
> speed)
>  (for/list ([n (in-range speed)])
>[define r (random)]
>(for/and ([p (in-list population)]
>  [a (in-list accumulated-payoff-percentage)]
>  #:break (< r a))
>  p)))
> 
> It looks like the population is stored in a list, and the changes in
> the populations create more lists. I think that changing the
> implementation to use vectors instead of list would make the code
> faster. (But I haven't tested it.)
> 
> Also, I think that for/and can be changed to for/last. I guess it will
> almost no no change the speed, but it would make the intention
> clearer.

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

I pushed some more changes. 

-- All automata code is now in the automata modules. 
-- It is now easy to explore different implementations of automata. 

1. Eliminating your last side-effects came for free or possibly a small gain in 
performance. 
2. Replacing your list-based automata with automata that use a transition 
matrix was the real gain, 
but of course this transformation reduces generality. 

Right now, the code uses about 1/6 of the time your original program consumed. 
This measurement is extremely rough and probably wouldn't stand up to 
statistically
rigorous methods. Close enough. 

I may try to add types later today. 

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Gustavo Massaccesi]

Sorry for not testing before posting, but in this code:

 (define (randomise-over-fitness accumulated-payoff-percentage population speed)
  (for/list ([n (in-range speed)])
[define r (random)]
(for/and ([p (in-list population)]
  [a (in-list accumulated-payoff-percentage)]
  #:break (< r a))
  p)))

It looks like the population is stored in a list, and the changes in
the populations create more lists. I think that changing the
implementation to use vectors instead of list would make the code
faster. (But I haven't tested it.)

Also, I think that for/and can be changed to for/last. I guess it will
almost no no change the speed, but it would make the intention
clearer.

Gustavo



On Mon, Oct 12, 2015 at 5:31 AM, Linh Chi Nguyen
 wrote:
> I dont know how the email group work. If someone keeps receiving emails out 
> of interest, please notice me.
>
> Thanks Bryan for the suggestion, it's nice to know, however Im not able to 
> afford upgrading now.
>
> And Matthias, for your notice of the spawning process
> ```
> (define (randomise-over-fitness accumulated-payoff-percentage population 
> speed)
>   (for/list ([n (in-range speed)])
> [define r (random)] ;; SHOULDN"T THIS LINE BE OUTSIDE OF THE for/list 
> COMPREHENSION?
> (for/and ([p (in-list population)][a (in-list 
> accumulated-payoff-percentage)]
>   #:break (< r a))
>   p)))
> ```
>
> The randomly generated r has to be inside the for/list loop. Because if it's 
> outside, then there is only one random number generated at the beginning, and 
> the newly spawn automata will keep being the same one repeatedly.
>
> For example, when the learning speed is s = 10, it means that, 10 old 
> automata should be replaced with 10 new ones. And the replacement should be 
> done in 10 different places in the population.
>
> This procedure is called an independent bernoulli draw. We independently draw 
> a random number (associated with an automaton) for 10 times. How likely an 
> automaton is chosen depends on its own fitness (its interval in the unit 
> scale of the accumulated percentages.)
>
> On Monday, 12 October 2015 03:46:05 UTC+2, Matthias Felleisen  wrote:
>> I have pushed some more cleanups, more speed.
>> I added another question to the “spawning” procedure.
>>
>>
>>
>>
>
> --
> You received this message because you are subscribed to the Google Groups 
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Alex Knauth]

What about Alexis King's persistent vectors?

> On Oct 12, 2015, at 6:14 PM, Matthias Felleisen  wrote:
> 
> 
> 
> So I couldn't resist and wrote the vector-based, allocation-minimizing 
> version of the program. I didn't get that much of a performance gain. 
> 
> I might still change the fitness representation (into a vector) or
> integrate it into 'population' (where it belongs from an SE perspective). 
> I doubt this will do much better in terms of speed. A speed-up of 6x 
> will have to do for now. 
> 
> Code at the same old link: 
> 
>>   https://github.com/mfelleisen/sample-fsm
> 
> 
> 
> 
> 
> 
> 
> On Oct 12, 2015, at 11:46 AM, Matthias Felleisen  wrote:
> 
>> 
>> for/last: good point. 
>> 
>> Based on my previous experience with replacing imperative automata with 
>> functional ones, 
>> I don't think replacing the list-based population container with a vector 
>> per se will 
>> speed up things much. But the pairing up of neighbors might be a tad faster. 
>> Then again
>> I would have to rewrite shuffle for imperative vectors. 
>> 
>> I have pulled out the population for now so that you can play with this: 
>> 
>> https://github.com/mfelleisen/sample-fsm
>> 
>> It's easy to run now from the command line. 
>> 
>> 
>> 
>> On Oct 12, 2015, at 11:17 AM, Gustavo Massaccesi  wrote:
>> 
>>> Sorry for not testing before posting, but in this code:
>>> 
>>> (define (randomise-over-fitness accumulated-payoff-percentage population 
>>> speed)
>>> (for/list ([n (in-range speed)])
>>>  [define r (random)]
>>>  (for/and ([p (in-list population)]
>>>[a (in-list accumulated-payoff-percentage)]
>>>#:break (< r a))
>>>p)))
>>> 
>>> It looks like the population is stored in a list, and the changes in
>>> the populations create more lists. I think that changing the
>>> implementation to use vectors instead of list would make the code
>>> faster. (But I haven't tested it.)
>>> 
>>> Also, I think that for/and can be changed to for/last. I guess it will
>>> almost no no change the speed, but it would make the intention
>>> clearer.
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

So I couldn't resist and wrote the vector-based, allocation-minimizing 
version of the program. I didn't get that much of a performance gain. 

I might still change the fitness representation (into a vector) or
integrate it into 'population' (where it belongs from an SE perspective). 
I doubt this will do much better in terms of speed. A speed-up of 6x 
will have to do for now. 

Code at the same old link: 

>https://github.com/mfelleisen/sample-fsm







On Oct 12, 2015, at 11:46 AM, Matthias Felleisen  wrote:

> 
> for/last: good point. 
> 
> Based on my previous experience with replacing imperative automata with 
> functional ones, 
> I don't think replacing the list-based population container with a vector per 
> se will 
> speed up things much. But the pairing up of neighbors might be a tad faster. 
> Then again
> I would have to rewrite shuffle for imperative vectors. 
> 
> I have pulled out the population for now so that you can play with this: 
> 
> https://github.com/mfelleisen/sample-fsm
> 
> It's easy to run now from the command line. 
> 
> 
> 
> On Oct 12, 2015, at 11:17 AM, Gustavo Massaccesi  wrote:
> 
>> Sorry for not testing before posting, but in this code:
>> 
>> (define (randomise-over-fitness accumulated-payoff-percentage population 
>> speed)
>> (for/list ([n (in-range speed)])
>>   [define r (random)]
>>   (for/and ([p (in-list population)]
>> [a (in-list accumulated-payoff-percentage)]
>> #:break (< r a))
>> p)))
>> 
>> It looks like the population is stored in a list, and the changes in
>> the populations create more lists. I think that changing the
>> implementation to use vectors instead of list would make the code
>> faster. (But I haven't tested it.)
>> 
>> Also, I think that for/and can be changed to for/last. I guess it will
>> almost no no change the speed, but it would make the intention
>> clearer.

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

Take a crack at it. 

I am pretty sure I have introduced the proper level of representation 
independence (I can hear Ben laugh all the way now — Typed Racket
doesn’t have types) and the typed documentation is pretty solid. (I’ll
do types later to validate.) 




> On Oct 12, 2015, at 7:37 PM, Alex Knauth  wrote:
> 
> What about Alexis King's persistent vectors?
> 
>> On Oct 12, 2015, at 6:14 PM, Matthias Felleisen  wrote:
>> 
>> 
>> 
>> So I couldn't resist and wrote the vector-based, allocation-minimizing 
>> version of the program. I didn't get that much of a performance gain. 
>> 
>> I might still change the fitness representation (into a vector) or
>> integrate it into 'population' (where it belongs from an SE perspective). 
>> I doubt this will do much better in terms of speed. A speed-up of 6x 
>> will have to do for now. 
>> 
>> Code at the same old link: 
>> 
>>>  https://github.com/mfelleisen/sample-fsm
>> 
>> 
>> 
>> 
>> 
>> 
>> 
>> On Oct 12, 2015, at 11:46 AM, Matthias Felleisen  
>> wrote:
>> 
>>> 
>>> for/last: good point. 
>>> 
>>> Based on my previous experience with replacing imperative automata with 
>>> functional ones, 
>>> I don't think replacing the list-based population container with a vector 
>>> per se will 
>>> speed up things much. But the pairing up of neighbors might be a tad 
>>> faster. Then again
>>> I would have to rewrite shuffle for imperative vectors. 
>>> 
>>> I have pulled out the population for now so that you can play with this: 
>>> 
>>> https://github.com/mfelleisen/sample-fsm
>>> 
>>> It's easy to run now from the command line. 
>>> 
>>> 
>>> 
>>> On Oct 12, 2015, at 11:17 AM, Gustavo Massaccesi  wrote:
>>> 
 Sorry for not testing before posting, but in this code:
 
 (define (randomise-over-fitness accumulated-payoff-percentage population 
 speed)
 (for/list ([n (in-range speed)])
 [define r (random)]
 (for/and ([p (in-list population)]
   [a (in-list accumulated-payoff-percentage)]
   #:break (< r a))
   p)))
 
 It looks like the population is stored in a list, and the changes in
 the populations create more lists. I think that changing the
 implementation to use vectors instead of list would make the code
 faster. (But I haven't tested it.)
 
 Also, I think that for/and can be changed to for/last. I guess it will
 almost no no change the speed, but it would make the intention
 clearer.
>> 
>> -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Racket Users" group.
>> To unsubscribe from this group and stop receiving emails from it, send an 
>> email to racket-users+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/d/optout.
> 

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Linh Chi Nguyen]

Thank you very much,
Im trying to see it. However Im very unfamiliar with module in racket.

So far I can only answer you this:

about your comment 

> [define survivors (drop population speed)]
> ;; MF: THIS LOOKS LIKE IT MAY "RESURRECT" AUTOM. THAT ARE ALIVE
> [define successors (randomise-over-fitness accum-fitness population speed)]

The point of the simulation is that it "ressurect" already available automata, 
regarding their fitness. Hence who has higher fitness gets more offspring and 
grows in size gradually (at the expense of the poor doers).

What is not right here is the word "ressurect" and it catches your intuition.

I'm not a native English speaker and they are complaining that I should get a 
native English speaker to proofread my paper. Sorry for that :)

On Sunday, 11 October 2015 05:07:02 UTC+2, Matthias Felleisen  wrote:
> I forked, Racket-ized, and gained some speed (~2x). 
> 
> 

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Linh Chi Nguyen]

ok i've been trying to see through the code.

I'm not sure how github works but I pushed the changes in my repo again 
(https://github.com/ayaderaghul/sample-fsm/blob/master/fsm0.rkt). Basically, I 
rewrite the automaton module (description and behavior) because previously I 
made a confusion between the number of the states and the number of actions for 
each state. Now the automaton is less readable but more simple.

I also add some test that can be run with 
```
~laptop$ raco test fsm0.rkt
```

However I dont know to run this code without a repl.
Because the whole file fsm0.rkt is a module and it has many nested modules 
inside, and the command i need is in the nested one. There is a special module 
that has this command:

```
(module* main #f
(run))
```

So if i want to run a trial of the file, i open a repl:

```
~laptop$ racket
> (require (submod "fsm0.rkt" tv))
> (run)
```
and it runs and plot the result.

I dont want to open a repl. How to run the command right in the terminal 
(Because later on i want to run the command with arguments in the terminal)? 
for example, I've tried this but it doesnt work:

```
~laptop$ racket fsm0.rkt '(require (submod "fsm0.rkt" tv))' '(run)'
```

Thank you,
Chi




On Sunday, 11 October 2015 09:24:07 UTC+2, Linh Chi Nguyen  wrote:
> Thank you very much,
> Im trying to see it. However Im very unfamiliar with module in racket.
> 
> So far I can only answer you this:
> 
> about your comment 
> 
> > [define survivors (drop population speed)]
> > ;; MF: THIS LOOKS LIKE IT MAY "RESURRECT" AUTOM. THAT ARE ALIVE
> > [define successors (randomise-over-fitness accum-fitness population speed)]
> 
> The point of the simulation is that it "ressurect" already available 
> automata, regarding their fitness. Hence who has higher fitness gets more 
> offspring and grows in size gradually (at the expense of the poor doers).
> 
> What is not right here is the word "ressurect" and it catches your intuition.
> 
> I'm not a native English speaker and they are complaining that I should get a 
> native English speaker to proofread my paper. Sorry for that :)
> 
> On Sunday, 11 October 2015 05:07:02 UTC+2, Matthias Felleisen  wrote:
> > I forked, Racket-ized, and gained some speed (~2x). 
> > 
> >

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Linh Chi Nguyen]

Sorry for the emails.

But I'd like to post that the question of how to require a module then evaluate 
a command is answered here:

https://groups.google.com/forum/#!topic/racket-users/byL7W1yktas

by Daniel.

Thank you so much for all your help and patience,
chi

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

I have pushed some more cleanups, more speed. 
I added another question to the “spawning” procedure. 




> On Oct 10, 2015, at 11:06 PM, Matthias Felleisen  wrote:
> 
> I forked, Racket-ized, and gained some speed (~2x). 
> 
> 
> 
>> On Sep 6, 2015, at 5:21 AM, Nguyen Linh Chi > > wrote:
>> 
>> Dear All,
>> thanks for all your help, im writing the code to generate a population of 
>> fsm, playing a repeated game and the population evolves over time. (no 
>> mutation yet). here on my github just fyi:
>> 
>> https://github.com/ayaderaghul/sample-fsm 
>> 
>> 
>> Btw, the blogger suggests that because the automaton only needs to know the 
>> current-state, if the population scales big, we just need to separate the 
>> current-state as a single atom outside the machine itself (for better 
>> performance). 
>> 
>> I hope this may helps make the thread more complete.
>> 
>> 
>> On 4 September 2015 at 20:50, > > wrote:
>> On Friday, September 4, 2015 at 9:31:36 AM UTC-4, Michael Myers wrote:
>> > You might want to take a look at https://github.com/mromyers/automata 
>> > 
>> > specifically, 
>> > https://github.com/mromyers/automata/blob/master/examples.rkt 
>> > 
>> > and https://github.com/mromyers/automata/blob/master/machines.rkt 
>> > 
>> >
>> > I more or less just use the definition that was in my textbook: you provide
>> > a transition function, and the DFA or NFA just uses stream-fold to get the
>> > extended transition. I used a bunch of generics stuff to try to generalize
>> > everything past the point of practicality, but it's still reasonably
>> > fast.
>> >
>> > It's not documented, but use (in-machine? M seq) to check for acceptance,
>> > (extended-transition M start seq) for final state(s).
>> >
>> > There's also a minimization function and nfa->dfa conversion in there, but
>> > they're a bit fragile, so use at your own risk.
>> 
>> Sorry for the duplicate, this was sent yesterday, and only arived just now.
>> 
>> --
>> You received this message because you are subscribed to a topic in the 
>> Google Groups "Racket Users" group.
>> To unsubscribe from this topic, visit 
>> https://groups.google.com/d/topic/racket-users/4o1goSwrLHA/unsubscribe 
>> .
>> To unsubscribe from this group and all its topics, send an email to 
>> racket-users+unsubscr...@googlegroups.com 
>> .
>> For more options, visit https://groups.google.com/d/optout 
>> .
>> 
>> 
>> 
>> -- 
>> Nguyen Linh Chi
>> 
>> -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Racket Users" group.
>> To unsubscribe from this group and stop receiving emails from it, send an 
>> email to racket-users+unsubscr...@googlegroups.com 
>> .
>> For more options, visit https://groups.google.com/d/optout 
>> .
> 
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to racket-users+unsubscr...@googlegroups.com 
> .
> For more options, visit https://groups.google.com/d/optout 
> .

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Matthias Felleisen]

I forked, Racket-ized, and gained some speed (~2x). 



> On Sep 6, 2015, at 5:21 AM, Nguyen Linh Chi  wrote:
> 
> Dear All,
> thanks for all your help, im writing the code to generate a population of 
> fsm, playing a repeated game and the population evolves over time. (no 
> mutation yet). here on my github just fyi:
> 
> https://github.com/ayaderaghul/sample-fsm 
> 
> 
> Btw, the blogger suggests that because the automaton only needs to know the 
> current-state, if the population scales big, we just need to separate the 
> current-state as a single atom outside the machine itself (for better 
> performance). 
> 
> I hope this may helps make the thread more complete.
> 
> 
> On 4 September 2015 at 20:50,  > wrote:
> On Friday, September 4, 2015 at 9:31:36 AM UTC-4, Michael Myers wrote:
> > You might want to take a look at https://github.com/mromyers/automata 
> > 
> > specifically, https://github.com/mromyers/automata/blob/master/examples.rkt 
> > 
> > and https://github.com/mromyers/automata/blob/master/machines.rkt 
> > 
> >
> > I more or less just use the definition that was in my textbook: you provide
> > a transition function, and the DFA or NFA just uses stream-fold to get the
> > extended transition. I used a bunch of generics stuff to try to generalize
> > everything past the point of practicality, but it's still reasonably
> > fast.
> >
> > It's not documented, but use (in-machine? M seq) to check for acceptance,
> > (extended-transition M start seq) for final state(s).
> >
> > There's also a minimization function and nfa->dfa conversion in there, but
> > they're a bit fragile, so use at your own risk.
> 
> Sorry for the duplicate, this was sent yesterday, and only arived just now.
> 
> --
> You received this message because you are subscribed to a topic in the Google 
> Groups "Racket Users" group.
> To unsubscribe from this topic, visit 
> https://groups.google.com/d/topic/racket-users/4o1goSwrLHA/unsubscribe 
> .
> To unsubscribe from this group and all its topics, send an email to 
> racket-users+unsubscr...@googlegroups.com 
> .
> For more options, visit https://groups.google.com/d/optout 
> .
> 
> 
> 
> -- 
> Nguyen Linh Chi
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to racket-users+unsubscr...@googlegroups.com 
> .
> For more options, visit https://groups.google.com/d/optout 
> .

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Nguyen Linh Chi]

Dear mrmyers, I cloned your repo however it's true that i complete have no
idea about macro yet. It'd be nice for further reading as i'd work on this
problem for long.

As soegaard suggests on IRC, to avoid the problem of creating new machines
after every interaction, i'd try to make the struct #:mutable. Hope that'd
be good.

Thanks for great advice,
Chi

On 4 September 2015 at 12:00, Jens Axel Søgaard 
wrote:

> Hi Linh,
>
> There are many different representations of finite state machines.
>
> If you "just" need to simulate a single machine, a simple and efficient
> approach is to represent each state as a Racket function (see example
> below).
>
> #lang racket
> (require racket/generator)
>
> ;; The turn-stile example from Wikipedia.
> ;;
> https://en.wikipedia.org/wiki/Finite-state_machine#Example:_coin-operated_turnstile
>
> ;; Current State  Input   Next State   Output
> ;;   LOCKED   coinUNLOCKED unlock turnstile so customer can
> push through
> ;;   LOCKED   push  LOCKED none (custome can't move through)
> ;; UNLOCKED   coinUNLOCKED none
> ;; UNLOCKED   push  LOCKED when customer is through, lock
> turnstile
>
> (define inputs '(coin push push push coin coin push))
> (define get-input (sequence->generator inputs))
>
> (define (LOCKED)
>   (match (get-input)
> ['coin(displayln "turnstile is unlocked")
>   (UNLOCKED)]
> ['push(displayln "you can't move through locked turnstile")
>   (LOCKED)]
> [_(DONE)]))
>
> (define (UNLOCKED)
>   (match (get-input)
> ['coin(displayln "no need to pay when the turnstile is unlocked")
>   (UNLOCKED)]
> ['push(displayln "customer goes through, turnstile is locked")
>   (LOCKED)]
> [_(DONE)]))
>
> (define (DONE)
>   (displayln "no more inputs"))
>
> (LOCKED) ; start turnstile in a locked state
>
>
>
>
> 2015-09-03 16:29 GMT+02:00 Linh Chi Nguyen :
>
>> Dear All,
>> I'm a complete newbie in racket and need help in coding finite state
>> machine/automata. Please pardon any of my ignorance.
>>
>> Thanks to this post of Tim Thornton, I see a very good way to code FSM:
>> http://timthornton.net/blog/id/538fa6f2f09a16ba0674813d
>>
>> I'd summarise it as following:
>> A finite state automaton has a number of states and each state has a name
>> plus many transition rules. He structures it in racket as following:
>>
>> (struct automaton (current-state states))
>> (struct state (name actions))
>> (struct action (event result))
>>
>> A simple automaton can be like this:
>> (define simple-fsm (fsm 'A
>> (list (fstate 'A (list (action 0 'A)
>>(action 1 'B)))
>>   (fstate 'B (list (action 0 'B)
>>(action 1 'A))
>>
>> The automaton is in state A which has 2 transition rules:
>> - if event 1 happens, the automaton jumps to state B,
>> - if event 0 happens, it stays in state A.
>>
>> Then he writes some functions to update the automaton after each event
>> (in the post). Plus this function he omits (I guess):
>> (define fsm-update-state old-fsm new-state)
>>   (struct-copy automaton old-fsm [current-state new-state]))
>>
>> HERE IS THE QUESTION:
>>
>> Using this way, after each event, there'd be a NEW automaton created. So
>> I'm worried about scaling. I'd like to generate 100 automata. In each
>> cycle, I'd pair the automata to interact for 50 times. Which means that
>> there'd be 100 new automata created for every single cycle. And I'd like to
>> run at least 1000 cycles.
>>
>> Would there be any problem with scaling? If yes, is there a way around
>> this?
>>
>> Any kind of comments and suggestions are welcomed and appreciated,
>> Thank you really much,
>> Chi
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Racket Users" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to racket-users+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/d/optout.
>>
>
>
>
> --
> --
> Jens Axel Søgaard
>
>


-- 
*Nguyen Linh Chi*

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Jens Axel Søgaard]

Hi Linh,

There are many different representations of finite state machines.

If you "just" need to simulate a single machine, a simple and efficient
approach is to represent each state as a Racket function (see example
below).

#lang racket
(require racket/generator)

;; The turn-stile example from Wikipedia.
;;
https://en.wikipedia.org/wiki/Finite-state_machine#Example:_coin-operated_turnstile

;; Current State  Input   Next State   Output
;;   LOCKED   coinUNLOCKED unlock turnstile so customer can
push through
;;   LOCKED   push  LOCKED none (custome can't move through)
;; UNLOCKED   coinUNLOCKED none
;; UNLOCKED   push  LOCKED when customer is through, lock
turnstile

(define inputs '(coin push push push coin coin push))
(define get-input (sequence->generator inputs))

(define (LOCKED)
  (match (get-input)
['coin(displayln "turnstile is unlocked")
  (UNLOCKED)]
['push(displayln "you can't move through locked turnstile")
  (LOCKED)]
[_(DONE)]))

(define (UNLOCKED)
  (match (get-input)
['coin(displayln "no need to pay when the turnstile is unlocked")
  (UNLOCKED)]
['push(displayln "customer goes through, turnstile is locked")
  (LOCKED)]
[_(DONE)]))

(define (DONE)
  (displayln "no more inputs"))

(LOCKED) ; start turnstile in a locked state




2015-09-03 16:29 GMT+02:00 Linh Chi Nguyen :

> Dear All,
> I'm a complete newbie in racket and need help in coding finite state
> machine/automata. Please pardon any of my ignorance.
>
> Thanks to this post of Tim Thornton, I see a very good way to code FSM:
> http://timthornton.net/blog/id/538fa6f2f09a16ba0674813d
>
> I'd summarise it as following:
> A finite state automaton has a number of states and each state has a name
> plus many transition rules. He structures it in racket as following:
>
> (struct automaton (current-state states))
> (struct state (name actions))
> (struct action (event result))
>
> A simple automaton can be like this:
> (define simple-fsm (fsm 'A
> (list (fstate 'A (list (action 0 'A)
>(action 1 'B)))
>   (fstate 'B (list (action 0 'B)
>(action 1 'A))
>
> The automaton is in state A which has 2 transition rules:
> - if event 1 happens, the automaton jumps to state B,
> - if event 0 happens, it stays in state A.
>
> Then he writes some functions to update the automaton after each event (in
> the post). Plus this function he omits (I guess):
> (define fsm-update-state old-fsm new-state)
>   (struct-copy automaton old-fsm [current-state new-state]))
>
> HERE IS THE QUESTION:
>
> Using this way, after each event, there'd be a NEW automaton created. So
> I'm worried about scaling. I'd like to generate 100 automata. In each
> cycle, I'd pair the automata to interact for 50 times. Which means that
> there'd be 100 new automata created for every single cycle. And I'd like to
> run at least 1000 cycles.
>
> Would there be any problem with scaling? If yes, is there a way around
> this?
>
> Any kind of comments and suggestions are welcomed and appreciated,
> Thank you really much,
> Chi
>
> --
> You received this message because you are subscribed to the Google Groups
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>



-- 
-- 
Jens Axel Søgaard

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Neil Van Dyke]

If your FSM are defined at compile-time, you can write a macro (in 
`syntax-rules` or `syntax-case`) that transforms FSMs defined in your 
FSM macro language to efficient Racket code.


Even with a macro, there are a few popular ways to do it, but I suggest 
trying to make your state transitions be Racket tail calls.


Neil V.

--
You received this message because you are subscribed to the Google Groups "Racket 
Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[racket-users] help on coding finite state automata

[Linh Chi Nguyen]

Dear All,
I'm a complete newbie in racket and need help in coding finite state 
machine/automata. Please pardon any of my ignorance.

Thanks to this post of Tim Thornton, I see a very good way to code FSM:
http://timthornton.net/blog/id/538fa6f2f09a16ba0674813d

I'd summarise it as following:
A finite state automaton has a number of states and each state has a name plus 
many transition rules. He structures it in racket as following:

(struct automaton (current-state states))
(struct state (name actions))
(struct action (event result))

A simple automaton can be like this:
(define simple-fsm (fsm 'A 
(list (fstate 'A (list (action 0 'A)
   (action 1 'B)))
  (fstate 'B (list (action 0 'B)
   (action 1 'A))

The automaton is in state A which has 2 transition rules: 
- if event 1 happens, the automaton jumps to state B, 
- if event 0 happens, it stays in state A.

Then he writes some functions to update the automaton after each event (in the 
post). Plus this function he omits (I guess):
(define fsm-update-state old-fsm new-state)
  (struct-copy automaton old-fsm [current-state new-state]))
   
HERE IS THE QUESTION:

Using this way, after each event, there'd be a NEW automaton created. So I'm 
worried about scaling. I'd like to generate 100 automata. In each cycle, I'd 
pair the automata to interact for 50 times. Which means that there'd be 100 new 
automata created for every single cycle. And I'd like to run at least 1000 
cycles.

Would there be any problem with scaling? If yes, is there a way around this?

Any kind of comments and suggestions are welcomed and appreciated,
Thank you really much,
Chi

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Michael Titke]

On 03/09/2015 16:29, Linh Chi Nguyen wrote:

Dear All,
I'm a complete newbie in racket and need help in coding finite state 
machine/automata. Please pardon any of my ignorance.

Thanks to this post of Tim Thornton, I see a very good way to code FSM:
http://timthornton.net/blog/id/538fa6f2f09a16ba0674813d


Looks interesting! When I first heard of finite state machines they were 
presented to me as an abstract model
of computers in general. AFAIR finite state automatons are used to teach 
how to realize really fast orthography checks but for me these were more 
connected to the concept of directed cyclic graphs.




HERE IS THE QUESTION:


Using this way, after each event, there'd be a NEW automaton created.


That's because of pure functional programming as the post states.



So I'm worried about scaling. I'd like to generate 100 automata. In each cycle, 
I'd pair the automata to interact for 50 times. Which means that there'd be 100 
new automata created for every single cycle. And I'd like to run at least 1000 
cycles.

Would there be any problem with scaling? If yes, is there a way around this?


With the knowledge of a regular computer already being such an automaton 
(in some way) I have learned
to appreciate the /case/ form for data driven programming. Especially if 
one doesn't care about past states (which will need memory one way or 
the other) it's probably better to describe the automaton "from inside" 
and see the whole program (or some part of it) as an automaton. For 
event driven programs nowadays (at least in Racket) we only need to 
define the actions as regular procedures or callbacks.


--
You received this message because you are subscribed to the Google Groups "Racket 
Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] help on coding finite state automata

[Paulo Matos]

On 03/09/2015 16:34, Neil Van Dyke wrote:

If your FSM are defined at compile-time, you can write a macro (in
`syntax-rules` or `syntax-case`) that transforms FSMs defined in your
FSM macro language to efficient Racket code.

Even with a macro, there are a few popular ways to do it, but I
suggest trying to make your state transitions be Racket tail calls.



Which reminds me of Shriram's awesome paper:
http://cs.brown.edu/~sk/Publications/Papers/Published/sk-automata-macros/

Enjoy!

--
Paulo Matos

--
You received this message because you are subscribed to the Google Groups "Racket 
Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.