Doug Williams' Racket Projects Blog

New Process Synchronization Mechanism in the Simulation Collection

2011-09-24T13:19:00.000-06:00

I have added a new process synchronization / communication mechanism to the simulation collection - similar to the Ada rendezvous mechanism. This adds call and accept syntaxes that allow processes to communicate in a synchronized manner. The call syntax allows the caller process to send a request to the callee process. The call syntax has the form:

  (call callee (id . arguments))

Where callee is the receiving process, id is the request type (which is not evaluated), and arguments are the arguments for the request. With a simple call, the caller is blocked until the callee accepts the request.

The accept syntax allows the callee process to accept a request from a caller process. The accept syntax has the form:

(accept caller (id . parameters) . body)

Where caller is the calling process, id is the request type (which is not evaluated), parameters are the formal parameters for the request, and body is the body of the accept - i.e., the critical section. With a simple accept, the callee is blocked until a caller sends a matching request. When a matching request is accepted, a rendezvous occurs - that is the body is evaluated and its result returned to caller as the result of the matching call.

Each process maintains a queue of requests that have yet to be accepted - where each caller is blocked.

Even with simple call / accept we can implement a simple lock process.

(define-process (lock)
(let loop ()
    (accept caller (lock))
    (accept caller (unlock))
    (loop)))

This process will continuously loop waiting for a process to request a lock and then wait for a process to request an unlock. Here is an example process that uses the lock.

(define-process (p1 i a-lock)
(printf "~a: process p1(~a) started.~n"
          (current-simulation-time) i)
(call a-lock (lock))
(printf "~a: process p1(~a) acquired lock.~n"
          (current-simulation-time) i)
(wait (random-flat 0.0 10.0))
(printf "~a: process p1(~a) releasing lock.~n"
          (current-simulation-time) i)
(call a-lock (unlock)))

This process just requests a lock - blocking until it gets it, waits a random length of time to simulate some protected task, and requests an unlock.

And here is a main procedure to start everything.

(define (main n)
(with-new-simulation-environment
    (let ((a-lock (schedule #:now (lock))))
      (for ((i (in-range n)))
        (schedule #:at (random-flat 0.0 10.0) (p1 i a-lock)))
      (start-simulation))))

If you run this with:

(main 10)

You get the following output:

0.13863292728449428: process p1(5) started.
0.13863292728449428: process p1(5) acquired lock.
1.1536616785362432: process p1(7) started.
2.0751959904191937: process p1(8) started.
2.876463473845367: process p1(1) started.
3.344929657351545: process p1(4) started.
7.029086638253653: process p1(5) releasing lock.
7.029086638253653: process p1(7) acquired lock.
7.342236104231587: process p1(2) started.
7.824845469456133: process p1(9) started.
7.921942925957062: process p1(6) started.
8.162050798467028: process p1(3) started.
8.574025375628212: process p1(0) started.
8.624836102585753: process p1(7) releasing lock.
8.624836102585753: process p1(8) acquired lock.
16.152957766273808: process p1(8) releasing lock.
16.152957766273808: process p1(1) acquired lock.
18.243251499858758: process p1(1) releasing lock.
18.243251499858758: process p1(4) acquired lock.
22.293434873464157: process p1(4) releasing lock.
22.293434873464157: process p1(2) acquired lock.
27.693559748646905: process p1(2) releasing lock.
27.693559748646905: process p1(9) acquired lock.
32.4025230155617: process p1(9) releasing lock.
32.4025230155617: process p1(6) acquired lock.
39.54837751017477: process p1(6) releasing lock.
39.54837751017477: process p1(3) acquired lock.
39.86720234676685: process p1(3) releasing lock.
39.86720234676685: process p1(0) acquired lock.
44.316970186291684: process p1(0) releasing lock.

However, this is a (very) fragile implementation of a lock relying on well-behaved callers.

A more robust implementation of a lock requires greater control over the acceptance of requests. The select syntax - in this case for accepts - plus some internal state variables allows us to do this. The select (for accepts) syntax has the following form.

  (select

    accept-alternative

...

    [else-alternative])

  accept-alternative 

    = ((when expr

        (accept caller (id . parameters) . body1)

          . body2)

    | ((accept caller (id . parameters) . body1)

         . body2)

  else-alternative

    = (else timing . body)

  timing

    = #:now

    | #:at time

    | #:in delta

    | #:when event

Which looks a bit daunting, but basically it is a list of possibly guarded accepts with an optional else. The select will evaluate all of the guards - the when exprs - to determine the open accepts. Unguarded accepts are always open. If any request form an open accept are queued, the highest priority request is selected and a rendezvous occurs. The body2 expressions are evaluated after the rendezvous. The else alternative specified a time-out and is evaluated (in lieu of a rendezvous) if no request is accepted before the specified time.

Here is a better implementation of a lock process.

(define-process (lock)
(let ((process #f)
        (locked? #f))
    (let loop ()
      (select
        ((when (not locked?)
           (accept caller (lock)
             (set! process caller)))
         (set! locked? #t))
        ((accept caller (unlock)
           (unless (eq? caller process)
             (error 'unlock
                    "process does not have the lock"
                    caller)))
         (set! process #f)
         (set! locked? #f)))
      (loop))))

This uses two variables, process and locked?, to maintain the internal state of the lock. The lock process continuously loops processing lock or unlock requests. A lock request will only be accepted if the lock is not currently locked. An unlock request will be accepted any time, but will raise an error if the process requesting the unlock is not the process that has the lock.

Running this lock process with the process p1 and main above gives identical results.

In some cases, we don't know if we can fully process a request until we get the request - because it depends on the caller or arguments in the request. What of we wanted to extent the lock to allow nested lock/unlock pairs from a process. In that case, we want to accept lock requests from the process owning the lock at any time, but not from others. There isn't any way to do that with a guard. Instead, we use requeue.

(define-process (lock)
(let ((process #f)
        (count 0))
    (let loop ()
      (select
        ((accept caller (lock)
           (if process
               (if (eq? caller process)
                   (set! count (+ count 1))
                   (requeue))
               (begin
                 (set! process caller)
                 (set! count 1)))))
        ((accept caller (unlock)
           (if (eq? caller process)
               (begin
                 (set! count (- count 1))
                 (when (= count 0)
                   (set! process #f)))
               (error 'unlock
                      "process does not have the lock"
                      caller)))))
      (loop))))

Here we have a count variable instead of a simple Boolean locked? variable. - when count = 0 the lock is open to anyone, but only open open to the process current 'owning' the lock when count > 0. In this case, we remove the guard from the accept for lock and requeue the request if the caller is not the process currently owning the lock.

I believe this is a very robust interprocess synchronization / communications mechanism for the simulation collection. I have a complete knowledge-based simulation example I will be putting up in the near future.

This code (and many examples) are included in the development branch of the simulation collection on the Schematic project at Sourceforge. I will update the PLaneT package when I update the documentation.

Simple Simulation in Racket

2010-08-14T13:26:00.005-06:00

I updated the simple simulation example from the simulation collection to Racket. The simple simulation example shows how a basic discrete-event simulation engine can be written in pure Racket (specifically, the racket/base language). Fully commented it is only about two and a half pages of code and does not contain any references to external packages. If you're curious about the usage of continuations, this might be a good example to look at. [If you're an expert in continuations, any critique would be welcome - particularly on the event loop in the start-simulation procedure.]

The code uses parameters for its global variables, which may be unfamiliar to some people. For example, the simulation clock is maintained by the current-time parameter. This parameter is created by (make-parameter current-time 0.0). A call to (current-time) will return its current value. The call (current-time (event-time (current-event))) in start-simulation sets its value to the time of the next event. Finally, the parameterize call in run-simulation creates new instances of the parameters and (I think) is cleaner than just resetting their values.

And, here is the actual code.


#lang racket/base
;;; Simplified Simulation System

;;; Global simulation control variables

;;; future-event-list : (parameter/c (list? event?))
;;; current-time : (parameter/c real?)
;;; current-event : (parameter/c (or/c false/c event?))
;;; event-loop-exit : (parameter/c (or/c false/c continuation?))
;;; event-loop-next : (parameter/c (or/c false/c continuation?))
(define future-event-list (make-parameter '()))
(define current-time (make-parameter 0.0))
(define current-event (make-parameter #f))
(define event-loop-exit (make-parameter #f))
(define event-loop-next (make-parameter #f))

;;; Event definition and scheduling

;;; (struct event (time function arguments))
;;;   time : (>=/c 0.0)
;;;   function : (or/c false/c procedure?)
;;;   arguments : list?
;;; Each event has a time the event is to be executed, the function to
;;; be executed, and the (evaluated) arguments to the function.
(struct event (time function arguments))

;;; (schedule event) -> any
;;;   event : event?
;;; Add an event to the event list.
(define (schedule event)
 (future-event-list (event-schedule event (future-event-list))))

;;; (event-schedule event event-list) -> (list-of event?)
;;;   event : event?
;;;   event-list : (list-of event?)
;;; Return a new list of events corresponding to the given event added
;;; to the given list of events.
(define (event-schedule event event-list)
 (cond ((null? event-list)
        (list event))
       ((< (event-time event)
           (event-time (car event-list)))
        (cons event event-list))
       (else
        (cons (car event-list)
              (event-schedule event (cdr event-list))))))
;;; Simulation control routines

;;; (wait/work delay) -> any
;;;   delay : (>=/c 0.0)
;;; Simulate the delay while work is being done.  Add an event to
;;; execute the current continuation to the event list.
(define (wait/work delay)
 (let/cc continue
   ;; Add an event to execute the current continuation
   (schedule (event (+ (current-time) delay) continue '()))
   ;; Return to the main loop
   ((event-loop-next))))

;;; (start-simulation) -> any
;;; This is the main simulation loop.  As long as there are events to
;;; be executed (or until the simulation is explicitly stopped), remove
;;; the next event from the event list, advance the clock to the time
;;; of the event, and apply the event's functions to its arguments.
(define (start-simulation)
 (let/ec exit
   ;; Save the event loop exit continuation
   (event-loop-exit exit)
   ;; Event loop
   (let loop ()
     ;; Exit if no more events
     (when (null? (future-event-list))
       ((event-loop-exit)))
     (let/cc next
       ;; Save the event loop next continuation
       (event-loop-next next)
       ;; Execute the next event
       (current-event (car (future-event-list)))
       (future-event-list (cdr (future-event-list)))
       (current-time (event-time (current-event)))
       (apply (event-function (current-event))
              (event-arguments (current-event))))
     (loop))))

;;; (stop-simulation) -> any
;;; Stop the execution of the current simulation (by jumping to its
;;; exit continuation).
(define (stop-simulation)
 ((event-loop-exit)))

;;; Random Distributions (to remove external dependencies)

;;; (random-flat a b) -> inexact-real?
;;;   a : real?
;;;   b : real?
;;; Returns a random real number from a uniform distribution between a
;;; and b.
(define (random-flat a b)
 (+ a (* (random) (- b a))))

;;; (random-exponential mu) -> inexact-real?
;;;   mu : real?
;;; Returns a random real number from an exponential distribution with
;;; mean mu.
(define (random-exponential mu)
 (* (- mu) (log (random))))

;;; Example Simulation Model

;;; (generator n) -> any
;;;   n : exact-positive-integer?
;;; Process to generate n customers arriving into the system.
(define (generator n)
 (do ((i 0 (+ i 1)))
     ((= i n) (void))
   (wait/work (random-exponential 4.0))
   (schedule (event (current-time) customer (list i)))))

;;; (customer i) -> any
;;;   i : exact-nonnegative-integer?
;;; The ith customer into the system.  The customer is in the system
;;; 2 to 10 minutes and then leaves.
(define (customer i)
 (printf "~a: customer ~a enters~n" (current-time) i)
 (wait/work (random-flat 2.0 10.0))
 (printf "~a: customer ~a leaves~n" (current-time) i))

;;; (run-simulation n) -> any
;;;   n : exact-positive-integer?
;;; Run the simulation for n customers (or until explicitly stopped at
;;; some specified time).
(define (run-simulation n)
 ;; Create new global values
 (parameterize ((future-event-list '())
                (current-time 0.0)
                (current-event #f)
                (event-loop-exit #f)
                (event-loop-next #f))
   ;; Schedule the customer generator
   (schedule (event 0.0 generator (list n)))
   ;; Stop the simulation at the specified time (optional)
   ;(schedule (event 50.0 stop-simulation '()))
   ;; Start the simulation main loop
   (start-simulation)))

;;; Run the simulation for 10 customers.
(run-simulation 10)

An example of the output looks like:


2.3985738870908615: customer 0 enters
5.395876334125138: customer 1 enters
7.716207787604494: customer 2 enters
8.062394508850671: customer 1 leaves
9.204092461998275: customer 0 leaves
14.431739507072376: customer 3 enters
15.15611565215575: customer 2 leaves
19.107487138771972: customer 4 enters
19.67563344212178: customer 3 leaves
26.51109574171283: customer 5 enters
27.060305975366514: customer 4 leaves
31.04777263526701: customer 6 enters
32.83444054122948: customer 5 leaves
36.31758748274069: customer 7 enters
39.27687483880874: customer 6 leaves
40.643350655011744: customer 8 enters
41.76876758081738: customer 7 leaves
42.82235216823591: customer 8 leaves
47.63479457664656: customer 9 enters
57.31661407095231: customer 9 leaves

Your output will vary slightly because of the random numbers. That is, this is a stochastic model.

Status Update

2010-08-13T10:39:00.003-06:00

I haven't posted for a while, so I just wanted to provide an update on the status and (hopeful) direction of my various PLaneT packages. This post will cover the science, simulation, and inference collections, which work together to provide a knowledge-based simulation capability.

We at SET Corporation are using the science, simulation, and inference collections as part of our Multi-Agent, Dynamic NEtwork Simulation System (MADNESS). The inference collection is also used in our COntent GENeration from Templates (COGENT) system. These are used on a daily basis in our agent-based simulation work.

Science Collection

The current release of the science collection is version 3.10. I only expect to do bug fixes to the version 3 code. The next release should be version 4.0. For version 4.0 I plan to convert the code to Typed Racket, which has gotten to the point that typed code generally runs as fast or faster than my hand-optimized numeric code.

The only major new functionality planned for version 4.0 are fast Fourier transforms. This code is already written and ready for release, but the documentation has not been updated. Vincent St-Amour at Northeastern University converted the FFT code to Typed Racket to test the optimized code generation for numeric processing. The results were extremely impressive and I need to make a separate post on this.

Simulation Collection

The current version of the simulation collection is version 3.4. I only expect to do bug fixes to the version 3 code. At some point I will release a version 4.0, which may (or may not) be in Typed Racket. The decision to use Typed Racket will be based on my experience in converting the science collection. I will also rewrite the simulation language using syntax-parse to provide better syntax error handling.

Inference Collection

The current version of the inference collection is version 2.7. There was a flurry of releases earlier this year as we really began to use the inference collection in MADNESS and COGENT. Unfortunately, the documentation has not yet caught up with the code changes.

I made earlier posts on the upcoming version 3 rewrite. As with the simulation collection, this may (or may not) be in Typed Scheme. I will definitely use syntax-parse to implement a rule compiler for the rule language.

Getting Ready for Inference Collection V3.0 Update 1

2009-09-26T10:31:00.006-06:00

One of the major changes for version 3.0 of the inference collection is a rule compiler that generates code for (portions of) the match/join process. This will be done at expansion (compile) time by the rule language macros themselves. The rule language macro include define-ruleset, define-facts, and define-rule. The rule compilation itself takes place in the define-rule macro.

So far, I have the rule parsing, rule validation, and rule normalization phases pretty much complete. The rule normalization phase converts Boolean expressions within the pattern clauses on a standard (and <pattern-clause> ...) | (or (and <pattern-clause> ...) ...). The first form is a simple rule while the second is a sequence of simple rules. For example:


(define-rule (some-rule some-ruleset)
    (p1 ?a ?b ?c)
    (p2 ?a ?b ?c)
    (or (and (p3 ?a)
             (p4 ?b))
        (p3 ?c))
  ==>
    (printf "a = ~a, b = ~a, c = ~a~n" ?a ?b ?c))

would expand into the equivalent of the two rules:


(define-rule (some-rule-a some-ruleset)
    (p1 ?a ?b ?c)
    (p2 ?a ?b ?c)
    (p3 ?a)
    (p4 ?b)
  ==>
    (printf "a = ~a, b = ~a, c = ~a~n" ?a ?b ?c))

(define-rule (some-rule-b some-ruleset)
    (p1 ?a ?b ?c)
    (p2 ?a ?b ?c)
    (p3 ?c))
  ==>
    (printf "a = ~a, b = ~a, c = ~a~n" ?a ?b ?c))

This can simplify writing complex rulesets.

I am now coding the actual rule compiler. This will generate procedures for matching pattern elements and joining matches - applying join constraints. For example, the pattern


(p1 ?a 12 ?b : (> ?b 10) (c . ?c))

would compile into:


(p1
 (#:variable #f ?a #f (lambda (?a bindings)
                        (vector-immutable
                         (unsafe-vector-ref bindings 0))))
 (#:literal #f #f 12 (lambda (x bindings)
                       (if (= x 12) bindings #f)))
 (#:variable #f ?b (> ?b 10) (lambda (?b bindings)
                               (let ((?a (unsafe-vector-ref bindings 1)))
                                 (if (> ?b 10)
                                     (vector-immutable
                                      (unsafe-vector-ref bindings 0) ?a ?b)
                                     #f))))
 (#:variable c ?c #f (lambda (?c bindings)
                       (let ((?a (unsafe-vector-ref bindings 1))
                             (?b (unsafe-vector-ref bindings 2)))
                         (vector-immutable
                          (unsafe-vector-ref bindings 0) ?a ?b ?c))))))

where each pattern element is a five element list (<type> <key> <variable> <constraint> <matcher>), where <type> is the pattern element type (e.g., #:variable or #:literal), <key> is the key for association list matching, <variable> is a variable name, <constraint> is a constraint expression, and <matcher> is a procedure to match the pattern element. These are used at execution time to build the rule network.

The structure of the pattern is maintained in the compiled form and is used to structure the match nodes and the data flow between them. The <type>, <key>, <variable>, and <constraint> fields are used to determine when nodes can be shared among rules. Finally, the procedure in the <matcher> field does the actual matching and variable binding.

Data Structures for Matching and Joining

Immutable vectors are used to represent matches. For example, the pattern


(p1 ?a 12 ?b : (> ?b 10) (c . ?c))

matched against the asserted fact


(p1 10 12 14 (c . 16) (d . 18))

would produce a match of


#(<assertion> 10 14 16)

where <assertion> is the assertion object for the specified fact and 10, 14, and 16 are the values matching the variables ?a, ?b, and ?c, respectively.

Immutable vectors are also used to represent joined matches. For example, the patterns


(p1 ?a ?b ?c)
?p2 <- (p2 ?a ?b ?c)
(no (p3 ?a))

matched against the asserted facts


(p1 1 2 3)
(p2 1 2 3)

with no asserted (p3 1)) fact, would produce a match of


#(#(<assertion> 1 2 3)
  #(<assertion> 1 2 3)
  #(#t))

A major bottleneck in the current inference engine is the amount of work done in propagating (or unpropagating) assertions and deletions through the join (and rule) nodes of the rule network. For version 3.0, I'm planning on two (eq?) hash tables for each join node to index left and right matches and a double doubly-linked list of joined matches. This will allow efficient insertion and deletion of both left and right matches during join processing (for propagating and unpropagating).

More to come.

Science Collection Updated

2009-09-20T09:49:00.006-06:00

I released a new version of the Science Collection with reimplemented statistics and Chebyshev approximation routines.

Statistics

The statistics routines have been rewritten to take sequences (for example, lists and vectors) as arguments instead of just vectors - except for the median and quantile routines that require sorted vectors. Unfortunately, the sequence versions, which are generally implemented using for/fold, were more than twice as slow as the previous vector versions. So, I wrote dispatching for and for/fold macros (see below) that take a general sequence and generate a cond expression with special cases for vectors and lists that the complier can better optimize. These perform about the same as the old code for vectors and lists perform about the same (as vectors). And, we still get the benefit of general sequences.

I also added the correlation function that I had somehow missed in the original implementation. [Unfortunately, the first version had a bug (#203) in it - actually, there were two since the contract was also wrong. It has since been fixed.]

I also added running statistics to the statistics routines. If you only need simple statistics (e.g., n, min, max, mean, variance, and standard deviation), you don't need to maintain a list (or vector) of the values. Instead, you create a statistics object and tally successive values. The statistics object can be queried at any time for the values of its statistics at that point.

I also implemented a mean-variance function that computes both the mean and variance for a sequence in a single pass through the data. [The previous functions requires two passes - one to compute the mean and one to compute the variance.] This also reduces the number of passes required for computing skew and kurtosis when the mean and standard deviation aren't given.

I also implemented contracts for sequence-of-real? and nonempty-sequence-of-real? that are used in the contracts for the statistics routines. As usual in the Science Collection, there are unchecked versions of the statistics routines that bypass the contract check.

Chebyshev Approximations

The Chebyshev approximation routines were reimplemented for clarity and efficiency. I changed the make-chebyshev-series function to be more general. It replaces the functionality of make-chebyshev-series-order and chebyshev-series-init, which are still available as legacy routines. I also added make-chebyshev-series-derivative and make-chebyshev-series-integral that generate new series to compute the derivative and integral, respectively, of a given Chebyshev series.

Dispatching for and for/fold

In reimplementing the statistics routines to allow general sequences as arguments, I also implemented dispatch-for and dispatch-for/fold macros, as described above. These macro are not exported from the statistics collection and are implemented using syntax-rules - so error messages are pretty much limited to 'bad-syntax'. With that caveat, they do produce code that outperforms (due to compiler optimizations) a straight for or for/fold for vectors and lists.

The implementation of the macros and examples their usage can be seen in the statistics.ss file in the Science Collection.

Getting Ready for Inference Collection 3.0

2009-08-08T20:37:00.002-06:00

I've been working on improvements to the inference collection now that we are actually using it (and the simulation collection) on a regular basis for agent-based simulation work. There will be in Version 3.0 of the inference collection. This is just to put forward some of the changes I'm planning on including.
The major change affecting user code is that Version 3.0 is that only (immutable) lists will be used to represent facts. This includes association lists for named slots. [Previously, vectors and structures could also be used.] Immutability simplifies many things associates with truth maintenance and explanation.
An ontology capability will be added that allows the user to define a set of taxonomies for the facts in the knowledge base. [Actually, this capability is already in Version 2.2 of the inference collection, but isn't released to PLaneT yet.] Taxonomic relations are asserted (much the same as facts) and these relations are used in matching rule preconditions. For example, (assert '(#:class hunter ())) and (assert '(#:class duck-hunter (hunter))) specifies that facts about hunters also apply to duck hunters. Classes may be generalizations of multiple parent classes. Basically, when a fact is asserted, it matched precondition clauses for its own class and (recursively) its parent classes. So, (duck-hunter clyde) would match both (duck-hunter ?x) and (hunter ?x) patterns as preconditions in rules.
Backward chaining is better integrated with forward chaining. When propogating assertions (or retractions) through the rule network, backward chaining will be automatically invoked. [Currently, backward chaining is only invoked when explicitly requested - via (query fact).]
Rulesets have a run-time instantiation now. [They were just collections of rules before.] When a ruleset is activated, a ruleset instance is created. The ruleset instance contains the agenda (for rule instances from the ruleset). This allows different conflict resolution strategies to be applied to rulesets within a single inference environment. [It will also allow us to experiment with conflict resolution among rulesets in the future.]
Certainty values for facts are implemented. A certainty may be specified when a fact is asserted and these are maintained as facts are inferred via rule firings.
Boolean connectives are allowed among rule preconditions. This simplifies writing complex rules.
This is a fairly substantial rewrite of the inference collection and should result in a better package all around. Our agent-based simulation work is leading us to look at less monolithic knowledge bases and more distributed ones. Although Version 3.0 is not truly distributed, it should help us along those lines as PLT Scheme continues to mature.
I'm not aware of any regular users outside of our small cadre of agent-based simulation folks. But, if there are, I'd like to solicit your inputs on any changes you might like and also make you aware of specific changes to the collection.

Simulation Collection Update

2008-12-01T07:47:00.003-07:00

I have updated the PLTScheme Simulation Collection to Version 3.2. This was primarily to release the Scribble documentation. The Scribble documentation is about 90% complete, which is a bit more than the previous HTML documentation.

I have begun adding new graphics capabilities to the simulation collection. So far I have added variable-slider%, variable-gauge%, and variable-message% classes. These are subclasses of the MrEd slider%, gauge%, and message% classes that are automatically synchronized with a specified simulation variable.

The variable-slider% class sets its associated variable to the value of the slider. That is, whenever the user moves the slider, the associated variable value is changed. This is input only.

The variable-gauge% class updates the gauge whenever the value of its associated variable is changed. The range of a variable-gauge% object may also be associated with a simulation variable. This is output only (for both the value variable and the range variable, if any).

The variable-message% class displays its associated variable's value and is updated whenever the value of that variable is changed. This is output only.

The graphical open and closed loop examples have been updated to show the use of these classes.

As usual, these are available on the Schematics project at SourceForge. I will update the PLaneT package when everything is stable and documented.

There are several other variable controls I plan on implemented in the next few weeks. The variable-text-field% class will provide both input and output for its associated variable's value. The variable-plot% class will provide a plot capability for variables. Initially, plots will just be time-value plots, but it will support multiple variables on each plot.

Currently, for my agent-based simulations I am using the animated-canvas% class to display the cell grid (or whatever 2D or 3D representation is appropriate). I need to generalize that as part of generalizing the agent-based capability. [Although simulation processes aren't very heavy-weight, continually adding and removing many thousands of them from the event list each generation is quite time-consuming.] That is next on my to do list.

PLT Scheme Science Collection Version 4.1 Released

2008-09-26T09:28:00.004-06:00

I released Version 4.1 of the PLT Scheme Science Collection to PLaneT earlier this week. There were no functionality changes, but the documentation has been converted to the Scribble format.

As usual, it is available from the PLaneT repository using the form:

(require (planet williams/science/science))

or

(require (planet williams/science/science-with-graphics))

depending on whether or not the graphics routines are needed.

The source code is maintained on the Schematics project subversion repository on SourceForge.

Animated Canvas Released to PLaneT

2008-09-26T08:47:00.003-06:00

I've released the animated canvas that I use for animated graphics in PLT Scheme. An animated canvas uses two bitmaps to provide a double-buffered animation capability. This is implemented by a new class animated-canvas% that specializes the canvas% class. At any specific time, one bitmap, the background bitmap, is being used for all drawing operations and the other bitmap, the foreground bitmap, is being used to paint the canvas.

The swap-bitmaps method is used to swap the background and foreground bitmaps. When the bitmaps are swapped, the contents of the new foreground bitmap – the old background bitmap – is displayed on the canvas. The new background bitmap – the old foreground bitmap – is automatically cleared, unless specifically prevented by the 'no-autoclear style option.

The device context returned by the animated canvases’s get-dc method is the device context of the background bitmap. This value is not valid across calls to swap-bitmaps. Therefore, it is important to re-retrieve, via get-dc, the device context across bitmap swaps.

The animated canvas also supports resizing on the canvas, which automatically resizes the background buffer after the bitmaps are swapped.

A simple example using the animated canvas is also provided.

As usual, the package is available from PLaneT using the form:

(require (planet williams/animated-canvas/animated-canvas))

The source code is maintained on the Schematics subversion repository at SourceForce.

Packed Binary Routines for PLT Scheme

2008-09-01T10:41:00.013-06:00

I have implemented an equivalent of the Python pack/unpack functions in PLT Scheme. I needed it primarily to be able to (more easily) read binary data from other applications for analysis in PLT Scheme.

The documentation for the Python capability can be found in the Python Library Reference: 4.3 struct -- Interpret strings as packed data. I have implemented the entire capability except for the "p" and "P" formats that encode a "Pascal string". [I don't have pack_into or unpack_from implemented yet - they are new in Pyton 2.5 - but I will implement them before posting the package to PLaneT. The following description is modified from the above reference.

packed-binary.ss

This module performs conversions between PLT Scheme values and C structs represented as PLT Scheme byte strings. It uses format strings (explained below) as compact descriptions of the layout of the C structs and the intended conversion to/from PLT Scheme values. This can be used in handling binary data stored in files or from network connections, among other sources.

The module defines the following functions:

(pack format v1 v2 ...)

Returns a byte string containing the values v1, v2, ... packed according to the given format. The arguments must match the values required by the format exactly.

(pack-into format buffer offset v1 v2 ...)

Pack the values v1, v2, ... according to the given format into the (mutable) byte string buffer starting at offset. Note that the offset is not an optional argument.

(write-packed format port v1 v2 ...)

Pack the values v1, v2, ... according to the given format and write them to the specified output port. Note that port is not an optional argument. [Note that write-packed is not part of the Python module, but was added because of its utility.]

(unpack format bytes)

Unpack the bytes according to the given format. The result is a list, even if it contains exactly one item. The bytes must contain exactly the amount of data required by the format [(bytes-length bytes) must equal (calculate-size format)].

(unpack-from format buffer (offset 0))

Unpack the byte string buffer according to the given format. The result is a list, even if it contains exactly one element. The buffer must contain at least the amount of data required by the format [(- (bytes-length buffer) offset) must be at least (calculate-size format)].

(read-packed format port)

Read (calculate-size format) bytes from the input port and unpack them according to the given format. The result is a list, even if it contains exactly one element. [Note that read-packed is not part of the Python module, but was added because of its utility.]

(calculate-size format)

Return the size of the byte string corresponding to the given format.

Format characters have the following meaning; the conversion between C and PLT Scheme values should be obvious given their types:

Format	C Type	PLT Scheme
x	pad byte	no value
c	char	char
b	signed char	integer
B	unsigned char	integer
h	short	integer
H	unsigned short	integer
i	int	integer
I	unsigned int	integer
l	long	integer
L	unsigned long	integer
q	long long	integer
Q	unsigned long long	integer
f	float	real
d	double	real
s	char[]	string

A format character may be preceded by an integral repeat count. For example, the format string "4h" means exactly the same thing as "hhhh".

Whitespace characters between formats are ignored; a count and its format must not contain whitespace though.

For the "s" format character, the count is interpreted as the size of the string, not a repeat count like for the other format characters. For example, "10s" means a 10-byte string while "10c" means 10 characters. For packing, the string is truncated or padded with null bytes as appropriate to make it fit. For unpacking, the resulting string always has exactly the specified number of bytes. As a special case, "0s" means a single, empty string (while "0c" means 0 characters).

By default, C numbers are represented in the machine's native format and byte order, and properly aligned by skipping pad bytes if necessary.

Alternatively, the first character of the format string can be used to indicate the byte order, size, and alignment of the packed data according to the following table:

Character	Byte order	Size and alignment
@	native	native
=	native	standard
<	little endian	standard
>	big endian	standard
!	network (= big endian)	standard

If the first character is not one of these, "@" is assumed.

Native byte order is big endian or little endian. For example, Motorola and Sun processors are big endian; Intel and DEC processors are little endian.

Standard size and alignment are as follows: no alignment is required for any type (so you have to use pad bytes); short is 2 bytes; int and long are 4 bytes; long long is 8 bytes; float and double are 32-bit and 64-but IEEE floating point numbers, respectively.

Note the difference between "@" and "=": both use native byte order, but the size and alignment of the latter is standardized.

The form "!" is available for those who can't remember whether network byte order is big endian or little endian - it is big endian.

There is no way to indicate non-native byte order (force byte swapping); use the appropriate choice of "<" or ">".

Hint, to align the end of a structure to the alignment requirement of a particular type, end the format with the code for that type with a repeat count of zero. For example, the format "llh0l" specified two pad bytes at the end, assuming longs are aligned on 4-byte boundaries. This only works when native size and alignment are in effect; standard size and alignment does not enforce any alignment.

The current implementation may not properly handle native alignment in all cases. For the current implementation, the native alignment is assumed to be the same as the size. This may result in excess pad bytes, particularly for 8-byte objects.

I will be putting the code up on the Schematics project on source forge (probably tomorrow) and it will be available on PLaneT soon thereafter.

PLT Scheme on Vista

2008-07-01T07:37:00.006-06:00

First off, I'd like to thank Eli Barzilay from the PLT team for helping track down these Vista 'features' that, together with a PLaneT 'feature', are causing my PLT Scheme problems on Vista. We also found the reason for long PLaneT download times on PLT Scheme V4.0 in the process.

This particular problem started when I tried to upgrade to PLT Scheme V4.0.1. After uninstalling PLT Scheme V4.0 (and making sure the uninstall completely removed the C:\Program Files\PLT directory) and installing V4.0.1, I would get the error "collects\srfi\compiled\provider_ss.zo::0: read (compiled): code compiled for version 4.0, not 4.0.1". I reported this on the bug tracker (http://bugs.plt-scheme.org/query/?cmd=view&pr=9554) where you can read the e-mail thread on the problem.

The Vista 'feature' that is biting us is called "UAC virtualization services" and is described in this article on the National Instruments Developer Site. (I'm sure there are many other such explainations that could be referenced.) It's a good read and goes into details that I will only summarize here. In short, if a user application attempts to modify protected portions of the file system (like C:\Program Files), the UAC virtualization service silently redirects the access to an unprotected, site-specific area (like C:\Users\doug\AppData\Local\VirtualStore\Program Files). Subsequent reads of affected files will use the copy in the virtual store. The problem is that install and uninstall (and probably some other application specific programs) don't know about the virtual store and files stay persistant across uninstall/install boundaries.

This was coupled with the current PLaneT 'feature' (http://bugs.plt-scheme.org/query/gnatsweb.pl?debug=&database=default&cmd=view+audit-trail&cmd=view&pr=9555) that compiles PLaneT packages with errortrace (i.e., debugging) when the initial require is from within DrScheme - it doesn't seem to happen from within MzScheme. In my case, when I would require the science collection (for example) from within DrScheme, it would download the collection and compile it and all referenced collections with errortrace turned on. This would recompile the referenced PLT Scheme collections (in C:\Program Files\PLT\collects) and the compiled files were put in the virtual store. This works okay until the uninstall of V4.0 and install of V4.0.1 where the compiled files in the virtual store (from V4.0) were seen instead of the newly installed files (from V4.0.1).

In any case, you can read the e-mail thread in the bug list for the details of how we finally tracked the problem down.

There are some work arounds that can be used until the PLT Scheme team figures out the best way to 'play nice' with Vista - although it would be nice if Vista played nice with legacy applications, but don't hold your breath for that.

When you do an uninstall, check to see if C:\Users\<user>\AppData\Local\VirtualStore\PLT exists. If it does, delete it also. This will remove the user modified files that might exist - even if they didn't realize they had modified any. [Note that the location of the virtual store may be different, so you might want to do a search for 'PLT' and include system and hidden files in the search. Also, if there are multiple users, they may be multiple virtual stores.]
For the initial load of PLaneT collections where you don't want errortrace turned on, do the initial require from MzScheme. For example, start up MzScheme from the command prompt and type "(require (planet "science.ss" ("williams" "science.plt")))" to load the science collection. This should work for any collection.

I will be 'upgrading' by laptop from Vista to XP and at least the first problem will go away. I would still recommend doing the initial require for PLaneT packages from MzScheme. I still have my Vista machine at home and will be dealing with some of these issues in an on-going basis.

Progress Updating to PLT Scheme V4.0

2008-06-26T14:22:00.002-06:00

Now that PLT Scheme is official released, I am updating the science, simulation, and inference collections to be compatible with the new version. These changes are incompatible with pre-V4.0 versions of PLT Scheme and will be stored in the PLaneT 4.x repository. Anyone using pre-V4.0 code should continue to use the versions in the PLaneT 3xx repository. V4.0 compatible versions of the science collection (Version 3.0) and simulation collection (Version 3.0) have been released already. I am now working on the V4.0 version of the inference collection (Version 2.0) and expect to release it this weekend.

There were several rather simple global changes that occurred in all of the code. For example, using the new #lang construct for all modules, using modules for all examples, hash table name changes, changes to require constructs, some contract changes (in particular union/c becomes or/c), and define-struct syntactic changes.

Some other changes were more difficult. The changes to keywords and keyword parameters required individual attention to each specific usage. Fortunately, much of my usage of keyword parameters is in macros and those still work the same in V4.0. I often use keywords as special values (e.g. #:now). These used to self evaluate, but now require quoting. Fortunately, these don't occur in user code. The other major problem is with mutable lists. These also have to be looked at on an individual bases. In some cases, I reverted to immutable lists (e.g. when using reverse! to reorder a constructed list being returned from a function) and in other cases I converted them to explicit mutable lists. It can be a chore to track down all of the references in a large body of code.

One big remaining issue is converting the documentation over to use Scribble. Unfortunately, the existing HTML documentation for PLaneT packages is not made available in the new Help Desk. [I honestly think that they should retain the ability for developers to distribute HTML documentation for PLaneT packages.]

PLT Scheme Science Collection: The science collection was rather straightforward to convert since I had kept the older versions compatible with both 372 and 399 (the V4.0 pre-release). Version 2.9 is the last pre-V4.0 compatible version and Version 3.0 is the new V4.0 compatible version.

PLT Scheme Simulation Collection: The simulation collection was more complicated to convert since it mutates lists in the implementation of the event list and variable histories (and probably a few others that I don't remember). I also had some problems with keywords since I had implemented my own keyword parameter scheme before it was added into PLT Scheme. Version 2.2 is the last pre-V4.0 compatible version and Version 3.0 is the new V4.0 compatible version.

PLT Scheme Inference Collection: The inference collection makes extensive use of list mutation and I am still tracking down and fixing them on an individual basis. I expect to have the V4.0 compatible version out this weekend.

If anybody runs into any problems with any of these packages, please let me know.

Homogeneous, N-Dimensional Arrays (ndarrays)

2008-03-27T09:25:00.005-06:00

The basic representational element for PLT Scheme Schemelab is a homogeneous, n-dimensional array - or ndarray. This post will discuss the initial design for ndarrays and discuss some of the operations on them.

Internally, an ndarray is represented by a structure with the following elements:

ordering - (symbols 'row 'column), specifies the order in which dimensions are stored ('row for row major and 'column for column major). Generally, this isn't that useful except for (eventually) interfacing with foreign code (C uses row major and FORTRAN uses column major). Also, the transpose operation converts from one to the other (although that is more a side effect that its real functionality). [read only]
shape - (listof natural-number/c), specifies the shape of the array. The length of the shape list is the number of dimensions for the array and each element is the cardinality of the corresponding dimension. This may be set to reshape the array.
ndim - natural-number/c, the number of dimensions for the array. This is equal to (length shape). [read only]
size - natural-number/c, the total number of elements in the array. [read only]
disp - natural-number/c, the displacement (in elements) of this subarray is the data vector. This will be zero for any ndarray that owns its own data. [read only]
strides - (listof natural-number/c), a list of the number of elements to skip to move to the next element in the corresponding dimension. [read only]
offset - natural-number/c, the offset (in elements) for each addressed element. This will be zero for any ndarray that owns its own data. [read only]
data - typed-vector?, the typed vector containing the data for the array. [A typed vector encapsulates an SRFI 4 vector (for u8, u16, u32, u64, s8, s16, s32, s64, f32, or f64 arrays), a complex vector (for c64 or c128 arrays), or a Scheme vector (for Scheme object arrays).] [read only]
base - (or/c array? false/c), the base array for this (sub)array or #f if the array owns its own data (i.e. it is a base array). Note that the referenced array may itself base a non-#f base entry. [read only]

Note that I may not need both the displacement (disp) and offset fields. But, the general idea for array iteration is to add the displacement once when the iterator is initialized and to add the offset for each element. It might be possible to collapse those into one offset without loss of generality.

The most general array constructor is make-array, which has the following contract:

(->* ((listof natural-number/c))
(#:vtype (or/c vtype? symbol?)
#:ordering (symbols 'row 'column)
#:fill any/c)
array?)

The required argument is the shape of the array. The optional keyword arguments are #:vtype, which specifies the type of the array (default object), #:ordering, which defaults to 'row, and #:fill. If #fill is not specified, the array elements are not initialized.

Example:

(define a1 (make-array '(3 2) #:vtype f32 #:fill 0.0))

Creates an array whose shape is '(3 2) (i.e. three rows and two columns) and whose elements are 32-bit floating-point numbers that are initially 0.0.

A fully qualified reference for the array returns the corresponding (scalar) element. For example, (array-ref a1 '(1 1) returns the value of the element at '(1 1).

A partially qualified reference for the array returns a reference to the corresponding subarray. For example, (array-ref a1 '(: 1) ) returns the subarray of shape '(3) that corresponds to the second column of a1. [Note that this is a reference to the second column of a1 and not a copy of it. Array referencing never copies anything.] Likewise, (array-ref a1 '(1 :)) [or equivalently, (array-ref a1 '(1))] returns a reference to the second row of a1.

Array mutation also allows partially qualified references. In that case, the value specified must be broadcastable (described in a future post) to the shape of the reference. For example, (array-set! a1 '(: 1) 1.0) sets the elements of the second column of a1 to 1,0 (yes, the scalar 1.0 is broadcastable to shape '(3)). Likewise, (array-set! a1 '(1) '(4.0 8.0)) sets the elements of the second row of a1 to 4.0 and 8.0.

A complete set of array manipulation functions will be provided. This will include: build-array, array-map, array-map!, array-for-each (i.e., similar to what SRFI 43 provides for vectors).

I haven't though about the semantics for things like array-fold and array-unfold. They may be well-defined someplace - I really haven't looked. If anyone knows where or has any ideas, please let me know.

Note that it is not my intention to define functions like add, subtract, multiply, divide, ... (as numpy does for Python). Rather, we will rely on the array mapping functions to extend scalar operations to arrays.

Schemelab Concept

2008-03-27T07:59:00.002-06:00

My PLT Scheme project for this year is to create a Schemelab collection to provide better analysis capabilities in PLT Scheme. It will be something of a mini-Matlab with capabilities similar to what numpy, scipy, and matplotlib provide in Python. I plan on making a new numeric collection to provide homogeneous, n-dimensional arrays (and, as a subset, matrices) as the primary underlying representation. Next, the science collection will be updated to use the new numeric package. Finally, a new plot collection will be developed to provide better visualization functionality. [After these are done I'll also update the simulation and inference collections to use the new Schemelab packages.]

I've already started work on the numeric collection. The basic representational element is a homogeneous, n-dimensional array (ndarray). An ndarray's type and shape are specified when it is created. The type may be any of the element types allowed for SRFI 4 vector types (u8, u16, u32, u64, s8, s16, s32, s64, f32, or f64), a complex type (c64 or c128), or may hold any Scheme object (object). The shape is a list of natural numbers where the length of the shape is the number of dimensions for the ndarray and each element is the cardinality of the corresponding dimension. References to array elements will support array slicing (in any dimension) for both array accessing (array-ref) and mutation (array-set!). Slicing operations create new views of the referenced array as opposed to copying portions of the array. I will start posting entries on different aspects of the numeric collection in the next few days.

The updates to the science collection to support (or to make use of internally) the new numeric collection should be relatively straightforward. The main issue will be to retain compatibility with the existing data types (i.e. vectors). Most of the really numerically complex code (e.g. special functions and random number distributions) will not be affected since they don't generally provide vector or array operations. The main changes will be to the statistics and histogram modules, which will be modified to work with ndarrays as well as vectors. Finally, some of the modules (e.g. histograms and ordinary differential equations) will benefit from being reimplemented using ndarrays internally.

I've also prototyped some code for the new plot package that provides much more functionality than the current PLoT package. The initial capability will be very much patterned after the functionality provided by Matlab (or more precisely, matplotlib for Python, which is also based on Matlab). It provides precise control over the elements of a graph (or multiple subgraphs). It also provides interactive graphics functionality for more dynamic analysis capabilities.

Note that all of these new (or updated) collections require PLT Scheme Version 4 (currently 3.99) and are not compatible with earlier versions. As such, I am not releasing them to PLaneT until either PLT Scheme Version 4 is officially released or there is a separate PLaneT repository for PLT Scheme Version 4 code. I will be putting the code on the Schematics web site at some point.

PLT Scheme Science Collection Version 2.8

2007-11-19T13:11:00.000-07:00

Version 2.8 of the PLT Scheme Science Collection has been released via PLaneT. There are two major changes from Version 2.7:

The random-sources.ss file has been reverted back to its previous implementation. This is because the interface for SRFI 27 was changed to be compatible with the pre PLT Scheme V371.1 version. That is, Version 2.7 is only required for PLT Scheme V371.1 (which probably isn't being used by anyone). Version 2.8 will work with V371 (and before) as well as with V371.2 and later.

Unchecked versions of many of the functions are now provided that bypass the contract check. These are called internally where it is known that the contract would be met. Obviously, they may also be called from user code in similar circumstances or where the contract check is not desired for some reason.

The unchecked version of a function is provided by renaming the function in a provide statement. The standard version is provided in a provide/contract statement. A trivial example is:

(module test-unchecked mzscheme

(require (lib "contract.ss"))

(provide
(rename double unchecked-double))

(provide/contract
(double
(-> real? real?)))

(define (double x)
(+ x x)))

This works fine. But, I'm not sure there is any guarantee that it will work in the future.

This will probably be the last revision before the release of PLT Scheme v4.0. I have branched the source code (at the Schematics project on SourceForge) for the PLT Scheme Science Collection Version 3.0 to be released with PLT Scheme Version 4.0. These changes will be tested using the PLT Scheme v3.99.x releases.

Science, Simulation, and Inference Collections Source Code Moved to SourceForge

2007-11-06T10:31:00.000-07:00

I finally got around to moving the source code for the science, simulation, and inference collections to the schematics project at SourceForge. This will help me manage the collections better and allow others to contribute more easily, if they wish. Unfortunately, I've been rather busy with work and haven't had much opportunity to work with the collections.
I have been playing around with Scribble for the documentation - it's currently in TeX. I'm not sure Scribble is ready for prime time in terms of graphics and mathematics typesetting yet.
Here is the status and high-level to-do list for the collections.

PLT Scheme Science Collection
The science collection is stable. The only things I might add in the near-term are additional random distributions and ordinary differential equation solvers. Also, if there are any capabilities that anyone would like added, drop me an e-mail.

PLT Scheme Simulation Collection
The simulation collection is where I have the most near-term activities. I have pretty much finished the design of the process interactions capability, based on the Ada rendezvous mechanism. Coding this up, with examples, and testing it are the next things to do. I will then reimplement the current resource mechanism using interprocess interactions.
Another thing I would like to do is to add vector valued variables. This is pretty straightforward, but also requires implementing vector values histories and statistics. It won't be hard, just a fair amount of coding. I may also add complex (and maybe quaternian) valued variables also.
The final thing for the simulation collection is to add components and a graphical construction method. I'm still working this through. Any ideas would be appreciated.

PLT Scheme Inference Collection
The inference collection is the one that still needs the most work. I still haven't written the reference manual. I will quit waiting for Scribble to shape up and just use TeX or OpenOffice.
To improve performance, I need to add more indexing to the various internal data structures - e.g., use hash tables instead of association lists. I have implemented indexing for existential pattern handling, but still need to add indexing for binding patterns and the agenda (at a minimum).

PLT Scheme Simulation Collection Version 2.2 Released

2007-05-13T08:49:00.000-06:00

Yesterday I released PLT Scheme Simulation Collection Version 2.2 via PLaneT. Version 2.2 includes some additional graphical examples. See the examples directory (in the PLaneT cache). All of the graphical examples can be run under either DrScheme or MrEd (mred -r ...).
The interactions.ss example is still my favorite. It shows the use of a simulation monitor to produce a visualization of a simulation, in this case, the interaction of particles with both attractive and repulsive forces. It is a hybrid simulation with both discrete-event (creating and deletion of particles) and continuous (modeling the forces) simulation elements. The animation works very well when its window is on the top, but doesn't repaint when it has been hidden. I have played a little with using a bitmap for the animation and transferring the bitmap to the canvas each update. This fixes the repaint when it's hidden, but I haven't been able to get a decent looking animation without flicker or other artifacts. A good animation example (or just plain help) would be appreciated. The only other thing I'd like to add to this simulation is a was to stop the simulation.
The other graphical examples aren't animations, they just provide a GUI for the simulation. For each of these there was already a simulation with graphical elements (i.e., a histogram or other plot of simulation data). The graphical example adds a GUI that allows simulation parameters to be modified.
The best GUI example is open-closed-loop-graphical.ss. This provides an example GUI for performing analysis on a (very simple) system. From the Edit > Options ... menu, you can select either open-loop (infinite resources) or closed-loop (with a specified number of resources) processing and other simulation parameters. The number of runs and number of customers per run are specified via sliders on the main window. The results are displayed in a pane in the main window.
As both a user of graphical tools (i.e., PLoT) and a provider of graphical tools, I am still annoyed at the differences between the various ways of providing graphical output in the PLT Scheme suite of tools (e.g., DrScheme, MrEd, and open-output-text-editor). I thought I had a nice mental model of DrScheme as an IDE for graphical PLT Scheme programs and MrEd as a run-time for the same programs. To the PLT Scheme developers the model seems to be that MrEd is (just) a tool to develop DrScheme and other graphical applications. My mental model of a graphical PLT Scheme program is just an illusion. Unfortunately, to people with my mental model, it seems that MrEd is just brain damaged with respect to executing what to me seems to be valid PLT Scheme graphical programs.

Simulation Collection Version 2.1 Available

2007-04-06T15:25:00.000-06:00

I just released Version 2.1 of the Simulation Collection to PLaneT. This fixes a bug in the variable monitors and updates the interacting particles example (interactions.ss) to illustrate their use in graphical simulations. If anyone with more experience with graphics programming with MrED would look it over and make suggestions on improving it, I would appreciate it.
Variables are used for automatic data collection in the Simulation Collection. [Note that these variables are not Scheme identifiers with values associates with them, but a separate data type and associated semantics.] Variable monitors allow arbitrary code to be attached to getting or setting a variable's value. This is especially useful in adding graphics to a simulation. In the particle interactions example, one is used to update the progress bar.
The particle interactions example also uses a simulation monitor that is executed each time the simulation clock is advanced. This provides the main simulation visualization.
This weekend I plan on adding process monitors that are executed whenever a process event is executed. This will be useful for updating graphics based on the (change in) state of a process. I will also update the reference manual with a section on Monitors.

Inference Collection - Fact Modification Semantics

2006-09-24T13:35:00.000-06:00

I need to specify the semantics for the various ways to change a fact in the inference engine. There are three ways to reassert a fact. The first is to explicitly retract the existing assertion and then to assert its replacement. The second is to replace an assertion using the replace function. The third is to modify (the fact within) an assertion using the modify function. Each of these has a different set of semantics - largely associated with the level of reuse.
Retract and Assert
By explicitly retracting an assertion, all reference to it should be removed. This is true in terms of the rule network, but currently references to the assertion may still exist in rule instances retained as the reasons for other assertions. I need to think of a better mechanism to retain the relevant information from the rule instance or give up on consistency when reusing assertions or facts.
One approach would be to sanitize the rule instance before using it as a reason. This would involve removing the assertion list (easy) and any assertion variables from the bindings. [These would not be reliable as reasons following any replace or modify of tge assertion.]
An alternative is to try to determine which assertion references are still valid following a replace or modity. We could remove any such references (in reason fields) or we could maintain a generation field and have an explicit assertion reference type with generation checking.
For now, I will document the inconsistence problem and live with it. It only affect debugging at the moment anyway.] I will revisit this when I implement truth maintenance in the future.
In any case, a separate retract and assert does not provide any reuse of assertions and the above problems will not occur.
Replace
Currently, replace literally implements an assert preceded by a retract as above. I will change this to reuse the assertion object for the next release. This will have the inconsistenct problem noted above.
Modify
The new modify functionality will reuse the underlying fact object within the assertion object being modified. Only the fields that are specified will be changed.

PLT Scheme Inference Collection

2006-09-21T07:02:00.000-06:00

The PLT Scheme Inference Collection has been released. Version 1.3 is the current released version.
All of the basic functionality has been implemented. There are several examples coded: ancestors, Towers of Hanoi, and Sudoku. The Sudoku example is the most complex requiring a search (using hierarchical inference environments).
I am not satisfied with the current implementation of 'modify'. I am going to rename the current functionality to be 'replace'. The semantics match that new term better.
I need to implement a real modify functionality that does modify the underlying fact object. This will be useful with fact objects with names fields: association lists, structures, and class instances. The primary additional work is how to map field names to their location in the fact object. Association lists aren't a problem since the field names are stored in the association list. I haven't found any way to get the names of structure fields - and I'm not sure there is any way to do so. Class instances are still a future implementation feature - but it does seem to be possible to get the field names for classes.
The initial implementation for modify will just support association lists. This will not require any additional syntax beyond modify itself.
Next, I will implement the modify functionality for structures. This will likely involve a new syntax - define-template - to supply the field names. It will have essentially the same syntax as define-struct. I will also implement define-struct/template that does the structure definition and template definition in one call.
This will also make it easier to implement the rule-based system benchmarks. I would like to code and bechmark the performance of the system before I begin adding more efficient algorithms (i.e. hashing for node matches).

Inference Collection Prototype

2006-07-13T16:13:00.000-06:00

I have been working on the prototype of the Inference Collection. It is now working for data-driven (forward chaining) rules. This includes existential (i,e, no, any, not all, all) joins, binding joins, and constraints.
To keep the code simpler, the prototype does not include the syntax elements (e.g. define-rule). Instead, the rule instances are created directly. I have protptyped the syntax elements separately and need to merge them in at some point. I will likely wait until after I get goal-driven (backward chaining) rules working.
The rule network consists of three basic type of nodes:

Match nodes
Join nodes
Rule nodes

The simple data-driven rule set I have been using is for finding ancestors. It only uses binding joins. The rule set, using the define-rule format is:


(define-ruleset ancestors)

(define-rule (initialize ancestors)
  ?start <- (start)  
 -->
  (retract ?start)
  (printf "Please enter the first name of a~n")
  (printf "person whose ancestors you would~n")
  (printf "like to find:~n")
  (assert `(request ,(read))))

(define-rule (print-ancestor ancestors)
  ?request <- (request ?name)  
  (parents ?name ?mother ?father)  
 -->
  (retract ?request)
  (when ?mother
      (printf "~a is an ancestor via ~a~n" ?mother ?name)
      (assert `(request ,?mother)))
  (when ?father
      (printf "~a is an ancestor via ~a~n" ?father ?name)
      (assert `(request ,?father))))

(define-rule (remove-request ancestors)
  ?request <- (request ?) 
 -->
  (remove ?request))

When this rule set is activated, it results in a rule network with 4 match nodes (1 for each precondition clause), 5 join nodes (1 initial join and 1 for each precondition clause), and 3 rule nodes (1 for each rule).

A more complex ruleset that includes existential joins is one that solves the Towers of Hanoi problem.


(define-ruleset towers)

(define-rule (rule-1 towers)
    - (ring ? on left)
    - (ring ? on middle)
  -->
    (printf "Problem solved!~n"))

(define-rule (rule-2 towers)
    - (move)
      (ring ?ring on (?peg (not (eq? ?peg 'right))))
    - (ring (?ring-1 (> ?ring-1 ?ring))
            on (?peg-1 (not (eq? ?peg-1 'right))))
  -->
    (assert `(move ?ring from ?peg to right)))

(define-rule (rule-3 towers)
      ?move-assertion <- (move ?ring from ?from to ?to)
      ?ring-assertion <- (ring ?ring on ?from)
    - (ring (?ring-1 (< ?ring-1 ?ring)) on ?from)
    - (ring (?ring-2 (< ?ring-2 ?ring)) on ?to)
  -->
    (printf "Move ring ~a from ~a to ~a.~n" ?ring ?from ?to)
    (modify ?ring-assertion `(ring ,?ring on ,?to))
    (retract ?move-assertion))

(define (rule-4 towers)
      ?move-assertion <- (move ?ring from ?from to ?to)
      (peg (?other (not (memq ?other (list ?from ?to)))))
      (ring (?ring-1 (< ?ring-1 ?ring))
            on (?peg-1 (not (eq? ?peg-1 ?other))))
    - (ring (?ring-2 (< ?ring-1 ?ring-2 ?ring))
            on (?peg-2 (not (eq? ?peg-2 ?other))))
  -->
    (modify ?move-assertion `(move ,?ring-1 from ,?peg-1 to ,?other)))))

I will post a separate entry explaining this ruleset.

Links to Presentations on the Science and Simulation Collections

2006-06-01T09:08:00.000-06:00

I have given a couple of talks at local Lisp users groups in Denver and Vancouver on Knowledge-Based Simulation. To date these have covered the Science Collection and the Simulation Collection. Thanks to Bill Clementson who taped each of the presentations and provided links to them and the presentation materials in his blog.

The first presentation is from the September 2004 Denver Area Lisp Users Group (DALUG) meeting and primarily covers the science collection. This includes links to a video of the presentation and to the presentation slides. An update to the post includes a link to an audio only version of the presentation.

The second presentation is from the February 2006 Vancouver Lisp Users Group (lispvan) meeting on the PLT Scheme Simulation Collection. This also includes links to a video of the presentation, the presentation slides, and to the documentation for both the science and simulation collections.

Syntax for Interprocess Communication in the Simulation Collection

2006-05-31T17:01:00.000-06:00

I am planning on extending the simulation collection to include interprocess communications (and synchronization) functionality based of Ada task interactions. Note that this is between processes in the simulation collection, not OS processes.

This will allow the model developer to more easily specify process interactions. For examples, resources could be implemented using this functionality.

Entry Definition
Each process entry must be declared in the define-process macro call that defines the process.

(entry (name . arguments))

Entry Acceptance
The simplest use of an entry is the accept statement.

(accept (name . arguments)
body...)

This is an executable statement that will either accept the first (i.e. highest priority) call to name or wait until such a call occurs.
The select statement allows more control over the selection of entry calls.

(select
accept-clause
...)

Each select clause has one of the following forms:

((accept (name . arguments)
    body ...)
 body ...)

((expr)
(accept (name . arguments)
    body ...)
 body ...)

((delay n)
 body ...)

(else
 body ...)

The first clause specifies an unguarded accept statement. That is, there are no conditions on its acceptance. The second clause specified a guarded clause. The accept is only active if the guard expression evaluates to true. The third clause is a timeout. The body will be evaluated if none of the alternatives have been accept before the specified (simulated) time has elapsed. The last is an else clause. Its body will be evaluated of no other clause is active.

[We could also allow a simple accept statement as an alternative when no code is specified other than the entry code itself. That is, allow the following:

(select (name . arguments)
 body ...)

Simple examples:

(define-process (test)
   (entry (abc a b c))
   ...
   (accept (abc a b c)
      (printf "a=~s b=~s c=~s~n" a b c))
   ...)

(define-process (test)
   (entry (abc a b c))
   ...
   (select
      (accept (abc a b c)
         (printf "a=~s b=~s c=~s~n" a b c))
      (else
         (printf "No entry waiting~n")))
   ...)

(define-process (test)
   (entry (abc a b c))
   ...
   (select
      (accept (abc a b c)
         (printf "a=~s b=~s c=~s~n" a b c))
      ((delay 10.0)
       (printf "No entry after waiting 10.0 units~n")))
   ...)

Entry Calls
For now, I will implement an enter statement with a syntax similar to the send statement for classes:

(enter process-instance name . arguments)

A more advanced use is to also allow the select statement with wither a delay or an else clause.

(define my-test (make-process test))

(select
  (enter my-test x y z)
  ((delay 10.0)
   (printf "Entry no accepted after 10.0 units~n")))

(select
  (enter my-test x y z)
  (else
   (printf "Entry not open~n")))

I need to decide if it makes any sense to allow other code after the entry call but withn the select.

Since the delay and else clauses don't make sense together (because a delay will always be open), I could combine them:

(else
 [(delay n)]
 body ...)

I will cover possible implementation strategies in a later post.

PLT Scheme Simulation Collection

2006-05-31T16:16:00.000-06:00

The PLT Scheme Simulation Collection implements a combined discrete event and continuous event simulation engine for developing simulation models in PLT Scheme. The simulation engine:

Provides a process-based, discrete event simulation engine
Supports combined discrete and continuous simulation models
Provides automatic data collection
Is designed to facilitate construction of component-based simulation models

The source code is distributed with the simulation collection and licensed under the GNU Lesser General Public License (LGPL).

The PLT Scheme Simulation Collection provides the following functionality for building and executing simulation models:

Simulation Environments (Basic)
Simulation Control (Basic)
Events
Processes
Resources
Data Collection
Sets
Continuous Simulation Models
Monitors
Simulation Classes
Simulation Control (Advanced)
Simulation Environments (Hierarchical)
Components

The PLT Scheme Simulation Collection is available via the PLaneT repository using the following form:

(require (planet "simulation.ss" ("williams" "simulation.plt")))

This will download and install the latest version of the simulation collection. The reference manual is available on the PLT Scheme Help Desk once the collection is installed.

I am still actively developing the PLT Scheme Simulation Collection. The Simulation Classes needs to be enhanced. The Hierarchical Simulation Environments and Components functionality needs to be completed, Also, I plan on added a process interaction capability using a rendezvous mechanism (similar to Ada task interactions).

Verson 2.0
Version 2.0 of the PLT Scheme Simulation Collection features a full Reference Manual that is compatible with the PLT Scheme Help Desk. The reference manual was written in TEX and converted to HTML using tex2page. A pdf version of the reference manual is also available.

Version 2.0 also provides priority ordering for events and resource allocation; reneging for resources; and linking event execution.

Finally, Version 2.0 adds a monitor capability for simulation timing and for variables.

Bug Fixes
The schedule macro was changed to generate code that is compatible with its use within a module. Previously, it generated code that worked only at the top level.

PLT Scheme Science Collection

2006-05-30T18:55:00.000-06:00

The PLT Scheme Science Collection is a collection of modules that provide functions for numerical computing. The structure of the science collection and many of the underlying algorithms were inspired by the GNU Scientific Library (GSL). The functions are written entirely in PLT Scheme and present a true Scheme look-and-feel throughout. The source code is distributed with the science collection and licensed under the GNU Lesser General Public License (LGPL).
The PLT Scheme Science Collection covers a range of topics in numerical computing. Functions are available for the following areas:

Mathematical Constants and Functions
Special Functions
Random Numbers
Random Distributions
Statistics
Histograms
Orginary Differential Equations
Chebyshev Approximations

The PLT Scheme Science Collection is available via the PLaneT repository using the following form:

(require (planet "science.ss" ("williams" "science.plt")))

This will download and install the latest version of the science collection. The reference manual is available on the PLT Scheme Help Desk once the collection is installed.
I don't have any updates scheduled for the PLT Scheme Science Collection. Bugs reports or requests for enhancements are welcome, however.

Version 2.2.1
Version 2.2.1 is a point release of Version 2.2 where the discrete random routines were reimplemented using Walker's O(1) algorithm.

Version 2.2
Version 2.2 of the PLT Scheme Science Collection features a reformatted Reference Manual that is compatible with the PLT Scheme Help Desk. The reference manual was written in TeX and converted to HTML using tex2page. A pdf version of the reference manual is also available.

Bug Fixes
The gamma-inc-Q function has been added. It was accidentally stubbed out in Version 2.1

Version 2.1
Version 2.1 of the PLT Scheme Science Collection added cummulative density functions for the rest of the 1-dimensional, continuous distributions (except the Gaussian tail distribution). The corresponding graphics routines were also updated to plot the cummulative density functions. Also, beta, incomplete gamma, and exponential integral special functions were implemented.

Bug Fixes
The lngamma function returned incorrect values for positive values less than 0.5.

Downloading the science collection from PLaneT on a computer with less than(approximately) 1GB of memory failed. This is caused in a bug in the PLT Scheme setup collection that fails on large files. The pdf file for the reference manual -- the large file that caused the problem -- was removed from the distributed science collection.

2-dimensional histogram plots failed. This was an error in the PLoT package distributed with PLT Scheme. It is fixed in V301.5 and later.

Version 2.0
Version 2.0 of the PLT Scheme Science Collection added ordinary differential equations. These were needed for the PLT Scheme Simulation Collection.

PLT Scheme Projects

2006-05-27T19:39:00.001-06:00

This blog is about my various open source PLT Scheme projects. There are three major Scheme projects I am currently working on. Two of these - PLT Scheme Science Collection and PLT Scheme Simulation Collection - have already been released. The third - PLT Scheme Inference Collection - is currently under development.
I had developed a knowledge-based simulation capability in Symbolics Common Lisp back in the late 1980s. I moved on to more traditional simulation technologies in my professional career and the work was largely forgotten. In the 1990s as PCs made their way into the classroom, I began using Scheme for teaching AI. However, at the time I didn't consider Scheme to be suitable for production quality software.
A few years ago, I came across PLT Scheme that seemed to meet my needs: it had an integrated development environment, it supported modern programming paradigms (e.g. object oriented programming, graphical user interfaces, exception handling, and modules), it was reasonably efficient, and it was portable across Windows and Linux, which are my two main platforms. Eventually I decided to resurrect my knowledge-based simulation work in PLT Scheme.
It was obvious that a simple port of the original Common Lisp code was not the best approach to the problem. I decomposed the problem into three basic components: the underlying mathematical and analysis capability, the simulation engine, and the inference engine. These became the science collection, simulation collection, and inference collection.
As I began developing the science collection, I noticed that much of what I needed was in the GNU Scientific Library (GSL). So, I decided that I would use the structure, and algorithms to the extent practical, of the GSL for the science collection. Version 1.0 of the PLT Scheme Science Collection was released via PLaneT in October 2004.
The simulation collection is a complete rewrite from the Common Lisp code. One of the advantages of Scheme is the availability of continuations, which are ideally suited for the implementation of a process-based simulation engine. I also decided to add a continuous simulation capability to the simulation engine. Version 1.0 of the PLT Scheme Simulation Collection was released in August 2005.
With my background in Artificial Intelligence, I was somewhat surprised at myself for leaving the inference collection as the last of the three to be implemented; particularly since I already have a Scheme version of a naive inference engine written. But, it made sense that way. It also turns out that the inference collection is a complete rewrite of the Common Lisp (and earlier Scheme) code. I plan on releasing Version 1.0 of the PLT Scheme Inference Collection during the summer of 2006.
I also have some Scheme programs that I have used in teaching AI classes over the years. Over time, I will convert these to PLT Scheme and make them available. The only one I have converted so far is a collection for defining state space problems and solving them using a graph search algorithm.