The Cost And Benefit Of Mutability

Apr 5th, 2019 - written by Kimserey with .

Mutability is a topic of high interest in the view of developers adventuring themselves in functional programming languages where it is generally unwelcomed and, in some instances, made voluntarily hard to implement. In contrast, object oriented programming has assignment at its core. Objects are represented as entity with a state modifiable over the lifetime of the application. Mutability is such an important, and non-trivial, part of programming that SICP has a whole chapter dedicated to it. Today we will touch some of its aspects, from the cost of assignment brought in a language, to examples demonstrating its necessity. In particular, we will explore the example of a digital circuit discussed in SICP Chapter 3.

Cost and Benefit of Mutability
Queue with Constant Complexity
Digital Circuit

Cost and Benefit of Mutability

In a previous post, we explored the fibonacci example where the recursive implementation was done without mutation.

(define fibonacci
  (λ (n)
    (cond
      [(zero? n) 0]
      [(= n 1) 1]
      [else (+ (fibonacci (- n 1)) (fibonacci (- n 2)))])))

Running through the example of $n = 4$, we were able to substitute the calls and the variables for each calls to compute the result.

> (fibonacci 4)
>> (+ (fib (- 4 1)) (fib (- 4 2)))
>>> (+ (fib 3) (fib 2))
>>>> (+ (+ (fib 2) (fib 1)) (+ (fib 1) (fib 0)))
>>>>> (+ (+ (+ (fib 1) (fib 0)) 1) (+ 1 0))
>>>> (+ (+ (+ 1 0) 1) 1)
>>> (+ (+ 1 1) 1)
>> (+ 2 1)
> 3

Running multiple time (fibonacci 4) will always result in the same result.

> (fibonacci 4)
3

> (fibonacci 4)
3

Subtitution works as long as we do not have free variables, or that we assume that free variables don’t change. If variables are allowed to be mutated, or in other words change over the time, we need to consider time as a factor in the equation.

For example current-seconds returns the current time in seconds since UTC, January 1, 1970. Therefore the result of the execution depends on the time when the procedure is executed. And consequently, any procedure using current-seconds will be dependent on the exact time when it is executed.

(define (add-ten-seconds)
  (+ 10 (current-seconds)))

add-ten-seconds depends on current-seconds which depends on the current time, a global shared variable. Therefore the substitution model does not apply anymore when assignment is put in the system

> (add-ten-seconds)
1554115700

> (add-ten-seconds)
1554115762

and multiple calls to add-ten-seconds do not yield the same result.

On the other hand, what assignments allow us to model is a state. Without assignments, every input and ouput are immutable data structures and each procedure is a function taking data as input, running a computation, and returning a result as output. What we can now model is a data structure evolving over the time, a mutable data structure, providing functions to mutate its own state.

Queue with Constant Complexity

A queue is a data structure providing three functionalities:

Queueing,
Dequeuing,
and optionally Peeking.

The items stored in the queue are queued at one end and dequeued at the other end (first in first out). In this example, we will enqueue at the end of the queue and dequeue from the front of the queue.

The default cons coming with Racket constructs a new tuple composed of two values or constructs a new list composed of the value provided as first position plus the list provided as second argument. The result value is an immutable structure.

For the purpose of showcasing assignment, we can create our own implementation of cons as a mutable construct, with set-car! and set-cdr! to respectively set the first item and the rest.

(define (cons x y)
  (define (set-x! v) (set! x v))
  (define (set-y! v) (set! y v))
  (define (dispatch m)
    (cond [(eq? m 'car) x]
          [(eq? m 'cdr) y]
          [(eq? m 'set-car!) set-x!]
          [(eq? m 'set-cdr!) set-y!]
          [else (error "Undefined operation: CONS" m)]))
  dispatch)

We use the dispatch procedure to encapsulate local state, here x and y together with functions modifying the local state. We then create car, cdr by dispatching the message targeting the function we need on our object z representing an object constructed by cons.

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

(define (set-car! z v) ((z 'set-car!) v) z)
(define (set-cdr! z v) ((z 'set-cdr!) v) z)

'car, 'cdr, 'set-car!, and set-cdr! are messages passed to z which represents the dispatch function of the created cons. When we execute (z 'car), we are actually executing (dispatch 'car) which will match to the (eq? m 'car) condition and therefore return x.

Using cons, we can create a representation of the queue by a cons of two pointers, one pointing to the front of the queue and the other to the rear of the queue, effectively enqueuing at the end.

(define ptrs (cons '() '()))

(define (front-ptr) (car ptrs))
(define (rear-ptr) (cdr ptrs))

(define (set-front-ptr! item) (set-car! ptrs item))
(define (set-rear-ptr! item) (set-cdr! ptrs item))

The front pointer, front-ptr, will point to the actual queue, while the rear pointer, rear-ptr, will point to the rear of the queue. Using these pointers allows us to enqueue and dequeue elements without having to iterate over the whole queue content. The complexity is therefore reduced from linear to constant.

We can then define enqueue! which enqueues an item by settings the pointers to the new item if the queue was previously empty, or setting the cdr of the rear pointer and then setting the rear pointer to the new item if the queue is not empty.

(define (enqueue! item)
  (let ([new-pair (cons item '())])
    (cond
      [(null? (front-ptr))
        (set-front-ptr! new-pair)
        (set-rear-ptr!  new-pair)
        #t]
      [else
        (set-cdr! (rear-ptr) new-pair)
        (set-rear-ptr! new-pair)
        #t])))

And we can define dequeue! which dequeues the first item added by setting the front pointer cdr as the the front pointer and returning that item.

(define (dequeue!)
  (cond
    [(null? (front-ptr)) #f]
    [else
      (let ([front (front-ptr)])
        (set-front-ptr! (cdr front))
        (car front))]))

We define peek by getting the car of the front pointer.

(define (peek) (car (front-ptr)))

Lastly we add a procedure indicating when the queue is empty by looking at the front pointer.

(define (empty-queue?) (null? (front-ptr)))

We can then use the same message passing method used with cons to encapsulate the ptrs state and the functions mutating the state while providing a dispatch procedure to invoke those.

(define (make-queue)
  (define ptrs (cons '() '()))

  (define (front-ptr) (car ptrs))
  (define (rear-ptr) (cdr ptrs))

  (define (set-front-ptr! item) (set-car! ptrs item))
  (define (set-rear-ptr! item) (set-cdr! ptrs item))

  (define (empty-queue?) (null? (front-ptr)))
  
  (define (enqueue! item)
    (let ([new-pair (cons item '())])
      (cond
        [(empty-queue?)
         (set-front-ptr! new-pair)
         (set-rear-ptr!  new-pair)
         #t]
        [else
         (set-cdr! (rear-ptr) new-pair)
         (set-rear-ptr! new-pair)
         #t])))

  (define (dequeue!)
    (cond
      [(empty-queue?) #f]
      [else
       (let ([front (front-ptr)])
         (set-front-ptr! (cdr front))
         (car front))]))
  
  (define (peek)
    (if (empty-queue?)
        #f
        (car (front-ptr))))

  (define (dispatch m)
    (cond [(eq? m 'enqueue!) enqueue!]
          [(eq? m 'dequeue!) dequeue!]
          [(eq? m 'peek) peek]
          [(eq? m 'empty-queue?) empty-queue?]))
  dispatch)

And we can create global procedures easing the usage of the dispatch mechanism.

(define (enqueue! q item) ((q 'enqueue!) item))
(define (dequeue! q) ((q 'dequeue!)))
(define (peek q) ((q 'peek)))
(define (empty-queue? q) ((q 'empty-queue?)))

We can then create a queue, enqueue and dequeue items out of it.

> (define my-queue (make-queue))

> (enqueue! my-queue 10)
#t
> (enqueue! my-queue 20)
#t
> (dequeue! my-queue)
10
> (dequeue! my-queue)
20
> (dequeue! my-queue)
#f

We now endup with a mutable data structure representing a queu, referenced by my-queue, containing a state changing over the time as we enqueue or dequeue items. my-queue can also be passed as argument to other procedures where it can be used.

My-queue is now deemed to have a lifecycle where depending on when queueing or dequeuing occurs, results are most likely to differ.

Digital Circuit

Extending on the queue example, we can build up a representation of digital circuit, an example from SICP.

Before defining circuit components, we start by defining the logical binary operators not, and and or.

(define (logical-not s)
  (cond
    [(= s 0) 1]
    [(= s 1) 0]
    [else (error "Invalid signal" s)]))
    
(define (logical-and a1 a2)
  (cond
    [(and (= a1 1) (= a2 1)) 1]
    [else 0]))

(define (logical-or a1 a2)
  (cond
    [(or (= a1 1) (= a2 1)) 1]
    [else 0]))

Once the logical binary operators defined, we can build our gates starting from inverter which uses loginal-not to compute the result value.

(define (inverter input output agenda)
  (define (logical-not s)
    (cond
      [(= s 0) 1]
      [(= s 1) 0]
      [else (error "Invalid signal" s)]))
  
  (define (invert-input)
    (let ([new-value (logical-not (get-signal input))])
      (after-delay agenda inverter-delay (λ () (set-signal! output new-value)))))
  (add-action! input invert-input)
  'ok)

We assumed the existence of two important pieces:

wires providing get-signal, set-signal! for the input and ouput, and add-action! which set the procedure which the input wire triggers,
an agenda scheduling actions to run after a certain delay with after-delay.

The inverter gate is simply creating a procedure, invert-input, and setting it to be triggered when its input changes.

We do the same for and-gate

(define (and-gate a1 a2 output agenda)
  (define (logical-and a1 a2)
    (cond
      [(and (= a1 1) (= a2 1)) 1]
      [else 0]))

  (define (and-action-procedure)
    (let ([new-value (logical-and
                      (get-signal a1)
                      (get-signal a2))])
      (after-delay agenda and-gate-delay (λ () (set-signal! output new-value)))))
  (add-action! a1 and-action-procedure)
  (add-action! a2 and-action-procedure)
  'ok)

where we set the value after and-gate-delay and trigger when a1 or a2 changes.

And we do the same for or-gate

(define (or-gate a1 a2 output agenda)
  (define (logical-or a1 a2)
    (cond
      [(or (= a1 1) (= a2 1)) 1]
      [else 0]))
  
  (define (or-action-procedure)
    (let ([new-value (logical-or
                      (get-signal a1)
                      (get-signal a2))])
      (after-delay agenda or-gate-delay (λ () (set-signal! output new-value)))))
  (add-action! a1 or-action-procedure)
  (add-action! a2 or-action-procedure)
  'ok)

where we set the value after or-gate-delay and trigger when a1 or a2 changes.

We can now define a wire, in the same way we defined the queue, as a mutable data structure with an internal state containing:

the actions that the wire would trigger for any signal change,
the current signal of the wire.

(define signal-value 0)
(define action-procedures '())

We define set-signal which changes the signal-value when the new value is different, and when changed triggers all action-procedures.

(define (set-my-signal! new-value)
  (if (not (= signal-value new-value))
      (begin
        (set! signal-value new-value)
        (call-each action-procedures))
      #f)
  'done)

Call-each recursively goes through the list of procedures and executes them one by one.

(define (call-each procedures)
  (if (null? procedures)
      'done
      (begin ((car procedures))
             (call-each (cdr procedures)))))

And we define an accept-action-procedure! procedure which accepts an action to be triggered by the wire when its signal changes. This procedure allows us to construct the gate logic by appending actions to the wires, where an action on an input wire will set the signal on an output wire.

(define (accept-action-procedure! proc)
  (set! action-procedures (cons proc action-procedures))
  (proc))

After the new action is added to the list of actions, it is executed once to propagate the current wire signal value. Lastly we encapsulate all the state within a make-wire procedure which construct a wire.

(define (make-wire)
  (define signal-value 0)
  (define action-procedures '())

  (define (call-each procedures)
    (if (null? procedures)
        'done
        (begin ((car procedures))
              (call-each (cdr procedures)))))

  (define (set-my-signal! new-value)
    (if (not (= signal-value new-value))
        (begin
          (set! signal-value new-value)
          (call-each action-procedures))
        #f)
    'done)

  (define (accept-action-procedure! proc)
    (set! action-procedures (cons proc action-procedures))
    (proc))

  (define (dispatch m)
    (cond
      [(eq? m 'get-signal) signal-value]
      [(eq? m 'set-signal!) set-my-signal!]
      [(eq? m 'accept-action-procedure!) accept-action-procedure!]
      [else (error "Unknown operation: WIRE" m)]))
  dispatch)

Similarly as the queue, we use the dispatch messaging mechanism to encapsulate functionalities and state and provide a dispatch procedure routing the the appropriate function. We can then create global procedures operating on wires for get-signal, set-signal!, and add-action!.

(define (get-signal wire) (wire 'get-signal))
(define (set-signal! wire new-value) ((wire 'set-signal!) new-value))
(define (add-action! wire proc) ((wire 'accept-action-procedure!) proc))

The last remaining part is the after-delay. After-delay is used to simulate the propagation time within the logic gate. As we discussed earlier, time is a factor in the whole system, and as represented in this example, depending on the current time, different actions will take place.

This representation of the time will be implemented with an agenda. Delaying an action will result in queuing an action in the agenda at a specific point in time.

Therefore we start first by creating an agenda by defining its data structure which would be a list of tuple containing an integer representing an exact time together with a queue representing the actions to perform at that exact time. We will also store the current time with the agenda.

'(
  0,
  '(
    '(0 '())
    '(1 actions-at-1)
    '(2 actions-at-2)
    '(3 actions-at-3)
    ...etc
  )
)

We start first by defining the agenda state.

(define agenda (cons 0 '()))

We then define procedures to retrieve and set the time

(define (current-time) (car agenda))
(define (set-current-time! time) (set-car! agenda time))

and procedures to retrieve and append actions at specific time segments.

(define (segments) (cdr agenda))
(define (set-segments! segments) (set-cdr! agenda segments))

(define (first-segment) (car (segments agenda)))
(define (rest-segments) (cdr (segments agenda)))

The agenda is empty when it does not contain any time segments.

(define (empty-agenda?) (null? (segments)))

We can then define the after-delay procedure taking a delay and the action to execute.

(define (after-delay delay action)
  (add-to-agenda! (+ delay (current-time)) action))

The delays are arbitrary numbers meant to represent the delay an electrical signal would take to traverse the logic gate.

(define inverter-delay 2)
(define and-gate-delay 3)
(define or-gate-delay 5)

Next we define add-to-agenda! which adds an action to the agenda at an exact time.

Assuming the existence of:

belongs-before? predicate indicating whether the new action belongs before the segments currently registered in the agenda,
make-time-segment creating a new time segment given a time and initial action,
add-to-segments! iterating over the segments to find where to place the action, either in an existing segment or creating a new one,

we can define the logic of add-to-agenda! by verifying if the new action belongs before any existing timeline, if it does, we create a new time segment and cons it to the existing segments, if it doesn’t belong before, we iterate over the existing segments to figure out where to place it.

(define (add-to-agenda! time action)
  (let ([segments (segments)])
    (if (belongs-before? segments)
        (set-segments! (cons (make-time-segment time action) segments))
        (add-to-segments! segments))))

Defining the procedures one by one, we start first by belong-before? which checks if the new action belongs before the current time segments by looking at the first time segment.

(define (belongs-before? segments)
  (if (null? segments)
      #t
      (< time (car (car segments)))))

(car (car segments)) selects the first element of the first segments representing the time of the first time segment.

Next we define make-time-segment which creates a new segment by cons’ing the time and a queue of one element containing the action.

(define (make-time-segment)
  (let ([q (make-queue)])
    (enqueue! q action)
    (cons time q)))

Lastly we create add-to-segments! which iterates over the segments list, adds the action to an existing segment if the time matches, else adds a new segment in between segments or at the end of the segments list.

(define (add-to-segments! segments)
  (if (= time (car (car segments)))
      (enqueue! (cdr (car segments)) action)
      (let ([rest (cdr segments)])
        (if (belongs-before? rest)
            (let ([new-seg (make-time-segment)])
              (set-cdr! segments (cons new-seg rest)))
            (add-to-segments! rest)))))

We can then encapsulate the state and procedures within an agenda object as we did for the wire and the queue.

(define (make-agenda)
  (define agenda (cons 0 '()))
  (define (set-current-time! time) (set-car! agenda time))
  (define (segments) (cdr agenda))
  (define (set-segments! segments) (set-cdr! agenda segments))
  (define (first-segment) (car (segments)))
  (define (rest-segments) (cdr (segments)))
  (define (empty-agenda?) (null? (segments)))
  
  (define (current-time) (car agenda))
  
  (define (after-delay delay action)
    (add-to-agenda! (+ delay (current-time)) action))

  (define (add-to-agenda! time action)
    (define (belongs-before? segments)
      (if (null? segments) #t (< time (car (car segments)))))

    (define (make-time-segment)
      (let ([q (make-queue)])
        (enqueue! q action)
        (cons time q)))

    (define (add-to-segments! segments)
      (if (= time (car (car segments)))
          (enqueue! (cdr (car segments)) action)
          (let ([rest (cdr segments)])
            (if (belongs-before? rest)
                (let ([new-seg (make-time-segment)])
                  (set-cdr! segments (cons new-seg rest)))
                (add-to-segments! rest)))))
              
    (let ([segments (segments)])
      (if (belongs-before? segments)
          (set-segments! (cons (make-time-segment) segments))
          (add-to-segments! segments))))
  
  (define (dispatch m)
    (cond
      [(eq? m 'current-time) current-time]
      [(eq? m 'after-delay) after-delay]
      [(eq? m 'empty-agenda? empty-agenda?)
      [else (error "Unknown operation: AGENDA" m)]))
  dispatch)

At this point, we are now able to construct a circuit with an agenda. Next we create propagate, a procedure simulating the propagation of electrical signals.

Propagate will take each segment, and execute action by action, recursively going through each time segment present in the agenda.

Assuming the existence of:

First-agenda-item procedure returning the first action in the agenda,
Remove-first-item! procedure removing the first action of the agenda,

We define the propagate procedure as a recursive function executing the first item, then removing the first item, and recursively doing so until the agenda is empty.

(define (propagate)
  (if (empty-agenda?)
      'done
      (let ([first-item (first-agenda-item)])
        (first-item)
        (remove-first-agenda-item!)
        (propagate))))

First-agenda-item sets the current time of the agenda to the time segment it is currently returning the action from, and return the first action it finds from that time segment by using peek.

(define (first-agenda-item)
  (if (empty-agenda?)
      (error "Agenda is empty: FIRST-AGENDA-ITEM")
      (let ([first-seg (first-segment)])
        (set-current-time! (car first-seg))
        (peek (cdr first-seg)))))

Remove-first-agenda-item! dequeues from the first time segment, and if the item is the last action of the time segment, updates the agenda segments using set-segments!.

(define (remove-first-agenda-item!)
  (let ([q (cdr (first-segment))])
    (dequeue! q)
    (if (empty-queue? q)
        (set-segments! (rest-segments))
        #f)))

We then include propagate, first-agenda-time, and remove-first-agenda-item! in the agenda, and expose the propagate procedure. The following snippet contains the whole agenda structure.

(define (make-agenda)
  (define agenda (cons 0 '()))
  (define (set-current-time! time) (set-car! agenda time))
  (define (segments) (cdr agenda))
  (define (set-segments! segments) (set-cdr! agenda segments))
  (define (first-segment) (car (segments)))
  (define (rest-segments) (cdr (segments)))
  (define (empty-agenda?) (null? (segments)))
  
  (define (current-time) (car agenda))
  
  (define (after-delay delay action)
    (add-to-agenda! (+ delay (current-time)) action))

  (define (add-to-agenda! time action)
    (define (belongs-before? segments)
      (if (null? segments) #t (< time (car (car segments)))))

    (define (make-time-segment)
      (let ([q (make-queue)])
        (enqueue! q action)
        (cons time q)))

    (define (add-to-segments! segments)
      (if (= time (car (car segments)))
          (enqueue! (cdr (car segments)) action)
          (let ([rest (cdr segments)])
            (if (belongs-before? rest)
                (let ([new-seg (make-time-segment)])
                  (set-cdr! segments (cons new-seg rest)))
                (add-to-segments! rest)))))
              
    (let ([segments (segments)])
      (if (belongs-before? segments)
          (set-segments! (cons (make-time-segment) segments))
          (add-to-segments! segments))))

  (define (propagate)
    (if (empty-agenda?)
        'done
        (let ([first-item (first-agenda-item)])
          (first-item)
          (remove-first-agenda-item!)
          (propagate))))
  
  (define (first-agenda-item)
    (if (empty-agenda?)
        (error "Agenda is empty: FIRST-AGENDA-ITEM")
        (let ([first-seg (first-segment)])
          (set-current-time! (car first-seg))
          (peek (cdr first-seg)))))

  (define (remove-first-agenda-item!)
    (let ([q (cdr (first-segment))])
      (dequeue! q)
      (if (empty-queue? q)
          (set-segments! (rest-segments))
          #f)))
  
  (define (dispatch m)
    (cond
      [(eq? m 'current-time) current-time]
      [(eq? m 'after-delay) after-delay]
      [(eq? m 'propagate) propagate]
      [else (error "Unknown operation: AGENDA" m)]))
  dispatch)

Similarly to the queue and wire, we expose global procedures to interact with the agenda.

(define (after-delay delay action agenda) ((agenda 'after-delay) delay action))
(define (current-time agenda) ((agenda 'current-time)))
(define (propagate agenda) ((agenda 'propagate)))

We now have a complete implementation of digital circuits which we can use to implement a half-adder:

(define (half-adder a b sum carry)
  (let ([d (make-wire)]
        [e (make-wire)])
    (or-gate a b d)
    (and-gate a b carry)
    (inverter carry e)
    (and-gate d e sum)
    'ok))

To observe the progress of our circuit, we complete this example by defining a probe, which appends an action displaying the current state of the wire at each value change.

(define (probe name wire)
  (add-action!
   wire
   (λ ()
     (display name) (display " ") (display (current-time)) (display " New-value = ") (display (get-signal wire))
     (newline))))

Lastly we can execute our circuit:

> (define agenda (make-agenda))
> (define input-1 (make-wire))
> (define input-2 (make-wire))
> (define sum (make-wire))
> (define carry (make-wire))
> (probe "sum" sum agenda)
sum 0 New-value = 0

> (probe "carry" carry agenda)
carry 0 New-value = 0

> (half-adder input-1 input-2 sum carry agenda)
'ok

> (set-signal! input-1 1)
'done

>  (propagate agenda)
sum 8 New-value = 1
'done

> (set-signal! input-2 1)
'done

> (propagate agenda)
carry 11 New-value = 1
sum 16 New-value = 0
'done

The propagation of the signal will bring the time to 8 to compute sum, due to the or and and gates delays. Then the next iteration brings the computation of carry at 11, due to the initial time being at 8 plus the time of the and gate, and brings sum at 16, due to the initial time plus the and and inverter gates delays.

Conclusion

Today we looked into mutability, starting by looking into the cost and benefit that mutability introduces, specifically pointing out that time becomes a problem when mutability is involved. We then moved on to define a queue structure using assignment to hold an inner state and encapsulating functionalities in the queue structure.

We completed the post by creating a digital circuit representing a half-adder using a wire structure and an agenda structure simulating the time delay that signals take to propagate in different logic gates.

Mutability, in our example, solves the problem of representing each data structure as a living entity, modifiable over the time, making the design simpler as wire structures were bound together in the logic gates and had their own lifecycles. Without assignements, we would have had to carry all information about the current state and the resulting program would have been much more complex as it currently is.

I hope you liked this post and I see you on the next one!

The Cost And Benefit Of Mutability

Cost and Benefit of Mutability

Queue with Constant Complexity

Digital Circuit

Conclusion

External Sources