Support on design of a simulator: multiple contexts with same variables

Questions & Answers
1

Hi,

in the process of learning Racket I‘ve started designing a small system simulator. Now I am stuck searching for an elegant way to solve the following issue.

The simulator has an environment and multiple actors. The environment is shared among the actors, ie, they can mutate the environment variables. Each actor can have private variables not accessible by other actors. Actors take interleaved steps. Let me give an example of the user input, which is a series of lists with s-expressions like this:

; initialize environment
(init-env (list ‘(define x 1) ‘(define y 100)))

; initialize actor 1
; (init-actor actor-id action-list)
(init-actor 1 (list ‘(define local y)) ‘(set! x y)))

; initialize actor 2
(init-actor 2 (list ‘(define local x) ‘(set! y 0)))

(run-simulations)

The environment steps are immediately taken, the steps of the actors are taken in interleaved fashion with (run-simulations). The output is the multiple possible behaviors (sequences of all bindings).

What I am struggling with is how to maintain the private state of the actors while sharing the variables of the environment. I don’t want to require unique variable names nor use hashes to store the state.

My first try was to use one namespace for the environment and one for each actor. Before taking an action of an actor, I copy the values of the environment variables (let the identifiers be the set E) into the actor namespace, and once the step is finished I copy the values of E from the actor namespace into the environment. I ignore variables not in E, ie, the private variables of the actor. That works but it is quite ugly. All the copying feels just wrong.

I am trying now to use a single namespace ns and continuations/coroutines, but I do not manage to create a local evaluation context for the actors. When I run (eval ‘(define local y) ns), the variable local is defined globally.

Would you have a suggestion how to proceed? Perhaps a completely different approach?

2

Hi, @db7.

I cannot confidently expound upon your question, but have you considered using parameters, perhaps?

Parameters, taken verbatim from here, are "thread-local variables" which do not obey the usual scoping we associate with variables.

Then, maybe you might be able to communicate between the different "environments" in this manner.

I may have misunderstood the intent, though.

Edit: To clarify a bit, I mention parameters because I have been having fun with them lately. As an example, I have a "unification" procedure skeleton below which uses parameterization (parameter scoping) to allow for "automatic" backtracking behaviour:

(define ≡forks (make-parameter (hash))
(define ≡atoms (make-parameter (hash))
...
(define (≡nodes from-node into-node)
  ... changes `≡forks` and/or `≡atoms` ...)
...
; assume the nodes in `from` and `into` are sorted by node-length
; for each node in `into`
; for each node in `from` with a greater or equal node-length to it
; - attempt to unify the nodes
;   - if unified, continue along the current unification path (via parameter chaining)
;   - or assume the next unification path
; if no unification is obtained, signal false
(define unification
  (let into-loop ([into-nodes ...]
                  [from-nodes ...])
    (cond [(empty? into-nodes)
           (cons {≡forks} {≡atoms})]
          [(< (length from-nodes) (length into-nodes))
           #false]
          [else
           (define into-node (car into-nodes))
           (let from-loop ([from-nodes* from-nodes])
             (cond [(empty? from-nodes*) #false]
                   [else
                    (or (parameterize ([≡forks {≡forks}]
                                       [≡atoms {≡atoms}])
                          (define from-node (car from-nodes*))
                          (match (≡nodes from-node into-node)
                            [#false #false]
                            [#true
                             (into-loop (cdr into-nodes) (cdr from-nodes*))]))
                        (from-loop (cdr from-nodes*)))]))])))

Note how the parameters are "shared" between the different scopes of from-loop and into-loop but that their value is either extended or rolled back depending on the success of the parameterization.

3

Would something as simple as

(define-values (actor-1 actor-2)
  (let ()
   (define x 1)
   (define y 2)
     (values
      (lambda () code for actor-1)
      (lambda () code for actor-2))))

(launch actor-1 actor-2)

arrange the code in the correct sharing/private-state way?

— Matthias

4

Yes, I'd love to find a simple approach like that. But I have to have control over the evaluation order performed by the actors. For example, imagine these actors:

(define x 1)
(define y 2)
(values
  (lambda ()  ; code for actor-1
    (define a x)
    (set! y (* 10 a))
  (lambda () ; code for actor-2
    (set! x y)))

I want to generate the executions:

(define a x) ; actor-1
(set! y (* 10 a)) ; actor-1
(set! x y) ; actor-2
; outcome: x = 10  and  y = 10

and

(set! x y) ; actor-2
(define a x) ; actor-1
(set! y (* 10 a)) ; actor-1
; outcome: x = 2  and  y = 20

and

(define a x) ; actor-1
(set! x y) ; actor-2
(set! y (* 10 a)) ; actor-1
; outcome: x = 2  and  y = 10

To achieve the simulation of these interleavings I was encoding the code of the actors as a list of expressions which are evaluated in coroutines like this:

(values
  (lambda ()  ; code for actor-1
    (for ([action (list '(define a x)
                        '(set! y (* 10 a))])
      (yield)
      (eval action))
  (lambda () ; code for actor-2
    (for ([action (list '(set! x y))])
      (yield)
      (eval action))))

And in yield I can decide which actor should perform the next action. Is there another way how to control the "scheduling" of the actors without relying on eval?

6

This is an entirely separate question. It seems you want something like a probabilistic programming language where programs compute all possible outcomes. My guess would be that implementation techniques like those for probabilistic DSLs might work. Gamble is such a language, and Cameron Moy is working on another one with Steve Holtzen's team.

7

@EmEf I guess that is correct. I could reformulate my problem in terms of probabilistic DSLs, but I have no knowledge about this topic.

For now, I'm trying to model a system as a typical state machine (transition system) where state (the global and private variables) changes by actions of the actors in an interleaved fashion. The goal is to generate all possible sequence of actions from the initial state (and the final state binding). In case of loops, we can set a bound on the maximum number of actions.

After the discussion here, I came with this preliminary design:

  • The global state is a module with "getters" and "setters". At the moment, only three are available:
    • (INIT loc value)
    • (WRITE loc value)
    • (READ loc)
  • Each actor has its own namespace with the global state module attached. In this way, it seems that actor definitions to not collide.
  • Actions are the lists of expressions as before.
  • Actors take one action and yield.
  • The yield procedure selects the next actor to take an action.

The input of the user looks like this at the moment:

#lang racket/base
(require "simulator.rkt")

; initialize locations
(INIT 'x 1)
(INIT 'y 2)

; spawn tasks
(spawn-task '((define a (READ 'x)) ;
              (WRITE 'x (* 10 a))))
(spawn-task '((WRITE 'x (READ 'y))))

; pick task at random after each action. 
(start-tasks)

Currently, the simulator performs one single execution with a random schedule. Next, I'll adapt it to perform all possible schedules.

Here is the outcome when running this program 3 times:

$ racket example.rkt 
[0] INIT
    -> y=2 x=1 
[1] (WRITE (quote x) (READ (quote y)))
    -> y=2 x=2 
[2] (define a (READ (quote x)))
    -> y=2 x=2 
[2] (WRITE (quote x) (* 10 a))
    -> y=2 x=20 
$
$ racket example.rkt 
[0] INIT
    -> y=2 x=1 
[1] (define a (READ (quote x)))
    -> y=2 x=1 
[1] (WRITE (quote x) (* 10 a))
    -> y=2 x=10 
[2] (WRITE (quote x) (READ (quote y)))
    -> y=2 x=2 
$
$ racket example.rkt 
[0] INIT
    -> y=2 x=1 
[1] (define a (READ (quote x)))
    -> y=2 x=1 
[2] (WRITE (quote x) (READ (quote y)))
    -> y=2 x=2 
[1] (WRITE (quote x) (* 10 a))
    -> y=2 x=10

So far, this mini project has been a really nice exercise to learn Racket (and Scheme in general). I plan to try to create a DSL in the future so that the input of the user is less cumbersome.

Thanks for the discussion. (I don't know how to close the question, though)

@bakgatviooldoos I glimpsed at your answer before you retracted it, and I was about to reply that it looked like what I wanted, but I was not able to understand the macros and advanced features you have used. For now, I think I will go with this simpler and less elegant approach above. Thank you.

1 Like
8

For posterity's sake; and because I deleted the reply in a moment of embarrassment, I'll link a gist here to capture the lost content. I learnt new things about namespaces and others might too.

actor-sequence.rkt

1 Like