the art of memorization

I read a book about human memory and memory techniques. Quite interesting and as an association of that memory I will in this post try to describe a nifty memory trick you can do in stack based prolog like engines.

The task is to make a kind of variable that behaves just like a variable but at a memorization of the current state these are automatically stored. We should try to not store too much information so we will need to have some mechanism that free memory in gc and selectively store stuff according to some intelligent scheme.

So let's start with a basic building block.

(define-syntax with-guarded-states

  (lambda (x)

    (syntax-case x ()

      ((_ guard ((s v) ...) code ...)

       #'(let ((s v) ... (fr #t) (done #f))

           (letrec ((guard  (mk-guard *current-stack* fr done guard s ...)))

             (dyn

              (lambda ()

                (set! fr   #t)

                (set! done #t)

                (push-setup

                 *current-stack*

                 (lambda ()

                   (set! done #f))))

              (lambda (x) (set! fr #f))

              *current-stack*)

             (let ()  code ...)))))))

with-guarded-states take a name for a guard and associate that with a set of variables s ... with initial values v .... The guard is active in the code section and it is a function that is used to set the variable s ... in the wanted manner. in the code we first initiate the variables with the initial value and initiate to flags fr, and done. we then define a guard function with the helper macro mk-guard which semantic will be described later. Then the function put's a dynwind dyn on the prolog stack. a dynwind has essentially two functions, one that is executed when the stack is reinstated and one where the stack is unwinded. Here at unwinding the fr flag is set to #f and at rewinding e.g. recalling a state, fr is set to #t and done is set to #t and we push a setup hook that set done to #f. The setup hook is called after the winding have been finished. the code is then executed in a let environment meaning that we are allowed to start the code with a set of defines. Anyway done is used to make sure we will update just ones if there is a sequence of guards evaluated and fr will mark that we are in the frame of the guarded variables and done will mark that we are hitting the first guarded set! in a wind/unwind.

the mk-guard is essentially the following

(lambda (ss ...)

   (let ((so s) ...)

      (set! s ss) ...

      (dyn

         rewind-code

         unwind-code)))

So the generated guard will take the new data ss ... and then store the old state in so ..., then set the variables with the new data in (set! s ss) ... and push a dynwind on the stack that represents the memorization of the setting of the variables.
essentially when passing the dynwind in a unwind we will restore the old value, and when passing in a rewind we will restore the new value.

The rewind code and the unwind will be described next, we use,

(begin

  (if (and (gp-wind-ref p) (not done))

      (begin

          (set! done #t)

          (push-setup p

             (let ((ss s) ...)

                (lambda ()

                   (set! done #f)

                   (if fr

                       (guard ss ...)

                       (begin (set! s ss) ...)))))))

  (set! s so) ...))

So here we see the done flag in action, if done is false e.g. it hits the variable for the first time then it will try execute the if, also we need gp-wind-ref to be true, e.g. we are saving the variable values, the if just marks done as #t so we will not do this again if we enters a new guarded set for the same variables. Again we push-setup e.g. put a hook to be executed at the finishing of the wind/unwind. so we store the current variables in ss, the lambda then will undo done and put it to #f, ready to be used at the next wind/unwind, it will then check if we are in the frame of the variable, if so we will make a new guard setting the s to the stored ss. If we have left the frame we will set the s, the net effect is that we have kept the initial value of the guarded variables intact but been able to correctly add, if needed, a guarded to do the correct transformations of the variable if we unwind or rewind over the new guard, in case of leaving the frame of the variables we have still kept the variable value, in case the there are no references to the variables all data will be reclaimed at perhaps the next gc. After the if part is done we simple restore to the old value so.

The code for the wind is very similar, again we will make sure to just execute the first encountered guard. The difference is that fr will always be true here. Also gp-wind-ref will flag if we shall keep the value of the special variable, or if we shall restore the old value. There is a problem with the previous code though one need to make sure not to grow the number of guards as one reinstate the new value, this is an optimization not solved yet, but the wanted semantic should be correct. A solution would be to at re-instation overwrite the last guard/wind refering to the variables to the new one or add a new one. Another optimization is to make sure that we do not add a null guard e.g. one that does not change anything. The deficiencies shown at winding back the stack does not look that good, but in practice the rewind is followed by a unwind what essentially keep the number of guard to say 1 or 2.

So this works pretty well it is not perfected but still a quite cool feature if one does not restore data to the same state to often without backtracking over the guard constructs.

Have fun!