Arc Forum | Symbol tables

Arc Forum

2 points by shader 5435 days ago | 7 comments

Is there a way to get a table containing the current symbol mappings from the surrounding lexical scopes, in a way such that they could be modified or replaced?

I was thinking about writing a macro with an "undo" option that could restore the previous local and/or global state before the body was executed. Obviously, if it restored global state, it would require work to make it thread safe.

Anyway, I was wondering if anyone had a solution to this thought experiment?

3 points by conanite 5433 days ago | link

Here's a macro-based approach that doesn't involve hacking ac.scm. First, an undo function that knows how to restore state for a set of variables:

  (def undo-fn (syms)
    (let backup-syms (map [sym (string "_" _)] syms)
      `(let ,backup-syms (list ,@syms)
         (fn ()
           (= ,@(mappend (fn args args) syms backup-syms))))))

This gives:

  arc>(undo-fn '(a b c))
  (let (_a _b _c) (list a b c) (fn () (= a _a b _b c _c)))

Now, a macro for defining functions that unhygienically inserts a function called "undo":

  (mac ufn (args . body)
    `(fn ,args
      (let undo ,(undo-fn args)
        ,@body)))

A quick test:

  arc>(= undo-test (ufn (x) (= x 999) (prn x) (undo) x))
  arc>(undo-test "original")
  999
  "original"

You could use 'undo-fn directly if you wanted to specify which variables need to be undoable.

-----

1 point by fallintothis 5433 days ago | link

Cool solution! Of course, handling arbitrarily-long history and globals would be more complicated. Maybe you could modify = to push old values onto a stack?

One advantage to an ac.scm approach is that you don't need to use the special ufn. If it worked on fn itself, then any local variables -- in a def, let, with, mac, etc. -- would be undoable. In an attempt to do this, I added a bit to your macro-based approach:

  (def undo-fn (symbols)
    (let backups (map1 [uniq] symbols)
      `(let ,backups (list ,@symbols)
         (fn () (= ,@(mappend list symbols backups))))))

  (mac w/undoable (parms . body)
    `(let undo ,(undo-fn parms)
       ,@body))

  (mac w/undo (expr)
    ((afn (tree)
       (let tree (macex tree)
         (if (caris tree 'fn)
              (let (lambda args . body) tree
                `(fn ,args (w/undoable ,args ,@(self body))))
             (atom tree)
              tree
             (cons (self (car tree))
                   (self (cdr tree))))))
     expr))

Certainly a hack, but it gives us:

  arc> (w/undo (let x 5
                 (prn "original: " x)
                 (++ x)
                 (prn "new: " x)
                 (undo)
                 (prn "undone: " x)
                 nil))
  original: 5
  new: 6
  undone: 5
  nil

  arc> (w/undo
         (def f (x)
           (prn "original: " x)
           (++ x)
           (prn "new: " x)
           (undo)
           (prn "undone: " x)
           nil))
  #<procedure: f>
  arc> (f 5)
  original: 5
  new: 6
  undone: 5
  nil
  arc> (f 10)
  original: 10
  new: 11
  undone: 10
  nil

  arc> (w/undo
         (def f (x)
           (prn "=== OUTSIDE LET ===")
           (prn "original: " x)
           (= x (let x (+ x 1)
                  (prn "=== INSIDE LET ===")
                  (prn "    original: " x)
                  (++ x)
                  (prn "    new: " x)
                  (undo)
                  (prn "    undone: " x)
                  x))
           (prn "new: " x)
           (undo)
           (prn "undone: " x)
           nil))
  *** redefining f
  #<procedure: f>
  arc> (f 5)
  === OUTSIDE LET ===
  original: 5
  === INSIDE LET ===
      original: 6
      new: 7
      undone: 6
  new: 6
  undone: 5
  nil

-----

1 point by shader 5416 days ago | link

All of the solutions so far have been interesting, but I was thinking more of being able to undo any change to any variable, instead of just the few variables declared as parameters.

The idea would be something like this:

  (with x 5 y 4
    (w/undo
      (++ x)           -> x=6
      (undo x)         -> x returns to 5
      (= y (++ x))     -> x = y = 6
      (side-efn x y)   -> x and y are modified
      (undo)           -> x = y = 6 again
      (reset)))         -> x = 5, y = 4

It seems like being able to undo side effects caused by function calls to arbitrary variables would require overloading = (or more likely sref).

Maybe if you did that you could replace variables that are modified with objects that when evaluated return their current value, but which can undo and maybe even redo by changing the return value to an earlier or later value on the stack. They should also be added to a list of modified variables owned by the w/undo macro, so that it can reset all of their values, and also commit their final value when the block is completed.

Would this even be possible? I'm not sure that it would be, since I think arc uses lexical scoping, which means that an arbitrary function call would use its own context's definition of sref, and thus wouldn't pay attention if we redefined it. Maybe since sref is a global variable, it could be replaced and then reset by w/undo? Meta w/undo!

Anyway, this concept of making variables able to remember their past and return previous values reminds me of lazy evaluation and memoization. Maybe their's some sort of connection that could be used to unify them simply, and add them to arc as a unit?

-----

2 points by rocketnia 5415 days ago | link

What happens if side-efn is this?

  (mac side-efn (x y)
     ; NOTE: This form is only intended to be used in the case where x and y are
     ; raw symbols, as they are in forms like (side-efn foo bar).
     `(= ,x (- ,y ,x)    ; temp = old y - old x
         ,y (- ,y ,x)    ; new y = old x (calculated as old y - temp)
         ,x (+ ,y ,x)))  ; new x = old y (calculated as old x + temp)

Should 'undo reverse just one of these assignments or all three? Should it make any difference if these assignments are three separate = forms within a (do ...) block?

A top-level undo could be nifty, but on the Arc top level even the macro environment gets to change from expression to expression, so it can be a bit different. To allow undo on a finer scale raises the question of just how to measure the previous transaction. How many assignments should be undone, and what if they're hidden away in a call to a function nobody likes to read? What about assignments for scopes whose dynamic extent has ended?

-----

1 point by shader 5412 days ago | link

I'm not entirely sure. Now that I think about it, fine grained undo is really a different concept from global state restoration, and is commonly only done for variables that the programmer a) knows about and b) has in mind the place he would like to restore to.

This means that finer grained undo would be more accurately implemented with save and restore functions, as opposed to just an undo function.

The global undo should work the same was as previously stated, more like a reset, and going all the way back to the start point, which may or may not be the beginning of the w/undo block.

Maybe a better system would be two pairs of save and restore functions, one that works on individual symbols, and the other that redefines '= to store the old value in a table if it didn't already exist, so that reset could restore it.

-----

1 point by conanite 5434 days ago | link

In ac.scm during compilation/macroexpansion there's a variable passed around called 'env which I think is the list of lexically bound symbols for the current scope. Not sure how you'd hook into that for your purposes though.

-----

1 point by fallintothis 5434 days ago | link

Yeah, but env just keeps the variables around, not their values. It's used to distinguish between locals and globals when compiling down to lambda.

  > (ac '(fn (x) (+ x 1)) '())
  (lambda (x) (ar-funcall2 _+ x 1))
  > (ac '(+ x 1) '())
  (ar-funcall2 _+ _x 1)
  > (ac '(+ x 1) '(x))
  (ar-funcall2 _+ x 1)

So it's not quite what you'd want. Off the top of my head, you could hack ac.scm to treat

  (fn (x) body)

as something like

  (fn (x) (= (locals* 'x) x) body (wipe (locals* 'x)))

Since Arc does all of its local binding with fn (either directly or by macroexpansion), this would work. ac.scm won't heed Arc-side redefinitions of fn, so I can't think of a convenient vanilla Arc implementation. As for efficiency, thread safety, etc., my idea seems gross.

I know Common Lisp has environments (http://www-prod-gif.supelec.fr/docs/cltl/clm/node102.html), but I don't know how they're usually implemented.

  $ clisp -q
  [1]> (let ((x 10)) (let ((y 20)) (the-environment)))
  #(#(Y 20 #(X 10 NIL))
    NIL
    NIL
    NIL
    ((DECLARATION XLIB::CLX-VALUES VALUES OPTIMIZE DECLARATION)))

-----