Miguel Arpa Perozo

Introduction

In the previous post I developed some tools to work with control blocks diagrams in C as an exercise. It was fun, but I felt that the result was not very pleasant to use and debug. In this post I present a similar tool, but this time using Scheme, a dialect of the Lisp family of programming languages.

In the SICP book, streams are used as the core datastructure to represent block diagrams in a computer program. This is achieved in a modular way such that it becomes easy to compose and reuse different blocks in several programs. In addition, the framework makes it possible to model systems having feedback loops. The ideas and some of the examples presented below are shamelessly taken from the SICP book. I will be using Chicken Scheme. The SRFI-41 is needed to run the examples.

The post is organized as follows. The first section briefly presents the main ideas behind the stream datastructure. Then, a block abstraction is introduced, in addition to some useful tools to work with blocks. The block abstraction is used to build a basic dynamical system simulator. Finally, the simulator is used to model and control a first-order system with a PI controller, the results are compared to the ones obtained using Julia ControlSystems.jl.

Streams

As mentioned above, this section quickly presents the main ideas behind streams and gives some interesting examples. For a more thorough presentation of streams, see Chapter 3, Section 5 of SICP.

Streams are presented in SICP as a way to “model systems that have state without ever using assignment or mutable data”. They are like traditional lists, i.e., the first element of a stream is accessed with stream-car, and the rest of the stream with stream-cdr. The main difference with traditional lists is that the cdr of a stream is evaluated only when it is accessed and not when it is created. This is possible thanks to the functions delay and force. The delay function gives a promise to make a computation, and force forces the execution of that promise. A possible naive implementation of delay and force is:

(define (delay exp) 
	(lambda () exp))

(define (force delayed-object) 
	(delayed-object))

With force and delay it is possible to define the basic functions to create and manipulate stream objects:

(define (stream-cons a b) 
	(cons a (delay b)))
	
(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force (cdr stream)))

With this clever idea and recursion, it is possible to model infinite datastructures in programs. For example, the program below creates a stream that represents all the positive integers:

(define (integers-starting-from n)
	(stream-cons n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

Calling (stream-car integers) returns 1, (stream-car (stream-cdr integers)) returns 2, (stream-car (stream-cdr (stream-cdr integers))) 3 and so on… The object integers models all the positive integers without needing to compute them all at once. Or, as presented in the SICP book:

“In general, we can think of delayed evaluation as “demand-driven” programming, whereby each stage in the stream process is activated only enough to satisfy the next stage. What we have done is to decouple the actual order of events in the computation from the apparent structure of our procedures. We write procedures as if the streams existed “all at once” when, in reality, the computation is performed incrementally, as in traditional programming styles”

I personally find it beautiful that with this approach/abstraction we can now reason and work with infinite objects/sets as we do in mathematics: we can write programs to work with the set of all positive integers, or the set of all the multiples of 5… Moreover, the programs will work efficiently because only what is necessary will be computed. Here is another cool example to represent all the positive integers also taken from SICP book:

(define ones (cons-stream 1 ones))
(define (add-streams s1 s2) (stream-map + s1 s2))
(define integers
	(cons-stream 1 (add-streams ones integers)))

Finally, here is a function, used in the following sections, that integrates an input stream using the Euler explicit method of integration:

(define (integral integrand initial-value dt)
  (define int
    (stream-cons initial-value
		  (stream-add (stream-scale dt integrand )
			      int)))
  int)

The Block Abstraction

Considering that the data flowing between blocks are streams, then the blocks are just simply functions that take a stream as an input, and/or generate a stream as an output. That’s it! Blocks become simply functions. More specifically, there are three types of blocks, as presented in the figure below:

1. Source blocks: blocks that take no input and generate an output
2. I/O blocks: blocks that take an input and generate an output
3. Sink blocks: blocks that only accept an input and generate no output

We can define the following constructors:

;; A source block does not take input, and only generate outputs.
(define (mk-blk-source infinite-stream)
  infinite-stream)

;; An input/output block generates its output by applying a function
;; to its input.
(define (mk-blk-io function)
  (lambda (input-stream)
    (stream-map function input-stream)))

;; A sink receives only input, and does not generate any output.
(define (mk-blk-sink function)
  (lambda (input-stream)
    (stream-map function input-stream)))

Common Blocks and Blocks Algebra

Below are given the definition of two common blocks constructors: the constant value and gain blocks.

(define (mk-blk-source-constant val)
  (stream-scale val ones))

(define (mk-blk-io-gain gain)
  (mk-blk-io (lambda (x) (* x gain))))

Here are some useful functions for doing some basic block algebra:

(define (blk-compose blk1 blk2)
  (lambda (input-stream)
    (blk2 (blk1 input-stream))))
	
(define (blk-adder s1 s2)
  (stream-map + s1 s1))

(define (blk-error s1 s2)
  (stream-map - s1 s2))

Please note that by representing blocks as functions, connecting two blocks in series in a diagram translates to composing together two functions.

System Dynamics

The goal of this section is to create a function to simulate systems that have the following form: $$ \begin{equation} \dot{x} = f \left (x(t), u(t) \right ) \end{equation} $$

where \(x(t)\) is the state of the system, \(u(t)\) the control input, and \(f\) a function describing the system dynamics. The block diagram for a “general” simulator has the following form:

As the above figure show, we need an integrator block. The following function implements a simple integrator block using the Euler explicit method of integration:

(define (mk-blk-int-euler initial-value dt)

  ; iteration step
  (define (blk-gen yn dyn-stream)
    (stream-cons yn
		 (blk-gen (+ yn (* dt (stream-car dyn-stream)))
			  (stream-cdr dyn-stream))))

  (define (blk-int-euler input-stream)
    (blk-gen initial-value input-stream))

  blk-int-euler)

Finally, we can now write a function that takes as an argument a function state-dynamics describing the system dynamics, an initial value, and a timestep (for the integrator), and returns a block as the one presented in the figure above.

(define (mk-blk-dyn-sys state-dynamics initial-value dt)

  (lambda (u-stream)
    ;; Applies state-dynamics to the x-stream and u-stream
    (define (state-trans-map xs us)
      (if (or (stream-null? us) (stream-null? xs))
	  stream-null
	  (stream-cons (state-dynamics (stream-car xs) (stream-car us))
		       (state-trans-map (stream-cdr xs) (stream-cdr us)))))

    (define dx-stream
      (stream-cons (state-dynamics initial-value (stream-car u-stream))
		   (state-trans-map x-stream u-stream)))
    
    (define integrator (mk-blk-int-euler initial-value dt))

    (define x-stream (integrator dx-stream))

    x-stream))

Feedback Loops

With the functions defined above, it is possible to create a feedback function à la Matlab to create closed-loop systems:

(define (blk-feedback blk-controller blk-system initial-value)
  (lambda (input-stream)
    (define output-stream (stream-cons initial-value
				       (blk-system control-stream)))
    (define error-stream (blk-error input-stream output-stream))
    (define control-stream (blk-controller error-stream))
    output-stream))

We now have all the necessary elements to simulate a closed-loop system. Let us put it to the test by considering a first-order system \(G(s)\) and a PI controller \(C(s)\):

$$ G(s) = \frac{K}{ 1 + \tau s } $$

$$ C(s) = K_p + \frac{K_i}{ s } $$

We will also compare the results of the simulation using Scheme to the ones obtained using Julia ControlSystems.jl.

Let us start by defining the model parameters and the system dynamics:

(define *tau* 5)
(define *K* 5)

; dynamics of a first order system
(define (state-dyna-first-order x u)
  (/ (- (* *K* u) x) *tau*))

(define *dt* 0.001)
(define *initial-value* 0.0)
(define *kp* 5.0)
(define *ki* 1.0)

We now create the system and controller blocks:

(define blk-first-order (mk-blk-dyn-sys state-dyna-first-order
					*initial-value*
					*dt*))

(define blk-ctrl-pi (mk-blk-ctrl-pi *kp* *ki* *dt*))

where mk-blk-ctrl-pi is defined as:

(define (mk-blk-ctrl-pi kp ki dt)
  (lambda (error-stream)
    (define blk-integrator (mk-blk-int-euler 0.0 dt))
    (stream-add (stream-scale kp error-stream)
		(stream-scale ki (blk-integrator error-stream)))))

Results

Below we create two closed-loop systems, the first where the output corresponds to the output of the controller block \( u(s) \), and the second where the output corresponds to the output of the first order system \( y(s) \).

;; closed loop system where the output is the control output 
(define blk-closed-loop-control (blk-feedback blk-ctrl-pi
					      blk-first-order
					      *initial-value*
					      *initial-value*))

;; closed loop system where the output is the system output 
(define blk-closed-loop-output (blk-feedback (blk-compose blk-ctrl-pi blk-first-order)
					     blk-one
					     *initial-value*
					     *initial-value*))

Finally, we simulate the response of the closed-loop systems to a step for 2000 points and save the results in a file:

(write-n-stream (blk-closed-loop-control ones)
	       2000
	       "lisp_results_control_output.txt")

(write-n-stream (blk-closed-loop-output ones)
	       2000
	       "lisp_results_system_output.txt")

The simulation results for both the Julia and Scheme code are compared in the figures below. The results are difficult to distinguish, which provides a first validation for the proposed simulator.

The source code to generate the figures above can be found in these files: main.scm, blocks.scm, main.jl.

Conclusion

I think that streams are a useful abstraction to model systems with feedback loops in a computer program. With streams, a block is simply a function that takes a stream as an input and generates a stream as an output. Because blocks are just functions, it is easy to compose and reuse them in different contexts.

Compared to the previous project, I believe that this version is easier to use and debug. In the future, I will develop a simulation abstraction: a list of blocks and a global time vector. Also, I will add the possibility of working with streams containing multidimensional data, such as vectors and matrices.