Don't Fear Dynamic Scope.

;
;
;                         INTRODUCTION.
;
;
; Dilemma between dynamic and static scope is old and frequent
; subject of discussion in the Lisp community, and many Lisp
; dialects tried different approach.  
;
; Dynamic scope, in my opinion, fits better in main Lisp design
; goals than static scope. The main reason I believe that with
; dynamic scope, symbols and expressions passed as arguments
; to the function retain their semantics, while in the case
; of the static scope, semantics is stripped away and called
; function can see only form of the s-expression.
;
;
;                          THE PROBLEM.
;
;
; Dynamic scope allows some interactions that static scope
; does not allow. Because of that, it is more difficult to
; understand behaviour of the functions and it is more probable
; that called functions will show behaviour not intended by
; programmer. Newlisp contexts provide lexical scope, allowing
; programmer to avoid this kind of the problems. In this post,
; we discuss what can be done if programmer doesn't want to
; give up from dynamic scope.
;
; For example, let us write the function sum that, for given function
; f and integer n evaluates
;
;                        f(1)+...+f(n)
   

(set 'sum (lambda(f n)(set 'result 0)
                           (for (i 1 n)
                                (inc result (f i)))
                           result))

(println "-----\nTest of sum for f(x)=x:")

(set 'f (lambda(x)x))
(println (sum f 100))

; Result 1+2+ ... +100=5050 - exactly as young Gauss said!
;
; Next, I'll try to write code that evaluates
;
;           1 + 2 + 3 + ... + 10
;
;            2   2   2          2
;           1 + 2 + 3 + ... + 10
;
;                   ...
;
;            5   5   5          5
;           1 + 2 + 3 + ... + 10
;
; I just want to see these numbers:

(println "-----\nTest (for (j 1 5) ...):")

(for (j 1 5)
     (set 'f (lambda(x)(pow x j)))
     (println j ": " (sum f 10)))

; 1: 55
; 2: 385
; 3: 3025
; 4: 25333
; 5: 220825
;
; Beautiful, isn't it? But, what would happen if I used variable i,
; and not j in my loop?

(println "-----\nTest (for (i 1 5) ...):")

(for (i 1 5)
     (set 'f (lambda(x)(pow x i)))
     (println i ": " (sum f 10)))

; 1: 1.040507132e+010
; 2: 1.040507132e+010
; 3: 1.040507132e+010
; 4: 1.040507132e+010
; 5: 1.040507132e+010
;
; What a mess! Why the result is not the same - numbers from 55 to
; 220825? The problem is, the function sum in its definition also
; uses variable i, and that i - and i from loop (for i 1 5) interacted
; on the unintended way. That code evaluates just like

(println "-----\nTest of nested loops:")

(for (i 1 5)
     (set 'f (lambda(x)(pow x i)))
     (set 'result 0)
     (print i ": ")
     (for (i 1 10)
          (inc result (f i)))
     (println result))

; 1: 1.040507132e+010
; 2: 1.040507132e+010
; 3: 1.040507132e+010
; 4: 1.040507132e+010
; 5: 1.040507132e+010
;
; The function f is defined in outer loop - but, because f contains
; expression (pow x i), it is also redefined in inner loop. An error
; in our original, dynamic scope example is exactly the same, but
; it is harder to detect, because code is distributed on few, possibly
; many functions, and programmer is maybe (or even probably) unaware
; of the internal, local variables in those functions.
;
; If you write libraries, you do not expect that people who use
; your libraries know local variables you used, right?
;
; So, the problem can be serious.
;
;
;                 THE SOLUTION - THE WEAK ONE.
;
;
; Very simple - and surprisingly efficient - technique is to accept
; naming convention for variables. For example, sum can be defined on
; following way:

(set 'sum (lambda(sum.f sum.n)
                 (set 'sum.result 0)
                 (for (sum.i 1 sum.n)
                      (inc sum.result (sum.f sum.i)))
                 sum.result))
               
; Knowing that convention, one has only to avoid variable names
; like sum.i, sum.n, sum.f and similar - and it is easy. I guess
; you never used such names - and you especially wouldn't use
; such names if you are warned.
;
; Prefix "sum" is somehow annoying while developing the function
; but it can be added later, after function is already developed
; and tested.
;
;
;                   THE PROBLEM PERSISTS.
;
;
; However, the problem doesn't disappear completely -  even if
; programmer does not use variables named like sum.f intentionally,
; he can knowingly or unknowingly use same function on few recursive
; way. Look at this expression:

(println "-----\nTest of complex expression (1):")

(println (sum (lambda(n)(sum pow n)) 2))

; The function sum called itself. Am I sure that I understand
; what happens inside and is it what I intended? Impossible to
; say, unless I know what exactly I intended. But I can say it -
; I intended to keep evaluation of "inner sum" and "outer sum"
; separate, i.e. neither one variable used in evaluation of these
; two should be shared. That is what people usually want.

; By other words, this is what I intended to write, just in more
; abstract and more general way:

(println (sum (lambda(n)(cond ((= n 1) (pow 1))
                              ((= n 2) (+ (pow 1) (pow 2))))) 2))
                              
; So, did I succeeded? Unfortunately, I didn't - result of the
; first expression is 10 and result of the second expression is
; 6. Somewhere on the way, Newlisp confused some variables of
; inner sum and outer sum.
;
; Note it is not fair description - I'm the one who caused the
; problem, not Newlisp - I didn't understood how recursive
; call in the dynamic scope works.
;
; Nevertheless - the problem stays, just, the question is - what
; should I (and not Newlisp) do to prevent the confusion.
;
;
;                  THE SOLUTION - THE STRONGER ONE.
;
;
; So, how can I avoid accidental overshadowing and keep advantage
; of dynamic scope? It would be ideal if for EACH CALL of the
; function different variables are used. For example, in third call
; of the function sum instead of "unsafe" version

(lambda(f n)                                     ;
       (set 'result 0)                           ;
       (for (i 1 n)                              ; UNSAFE SUM
            (inc result (f i)))                  ;
       result)                                   ;

; following, "safe" version is called:

(lambda(sum.f.3 sum.n.3)                         ;
     (set 'sum.result.3 0)                       ;
     (for (sum.i.3 1 sum.n.3)                    ; SAFE SUM
          (inc sum.result.3 (sum.f.3 sum.i.3)))  ;
     sum.result.3)                               ;

; if I can organize that, then there is no chance that two
; recursive calls can "confuse" same variables. Each call will
; use its own, independent variables.
;
; But, how to organize it? Let's go gradually.

; "Safe" version of the function sum is result of evaluation of

    (let ((f       'sum.f.3)                   ;
          (n       'sum.n.3)                   ;  SAFE SUM
          (i       'sum.i.3)                   ;  GENERATING
          (result  'sum.result.3))             ;  EXPRESSION
          (expand
                   ; original function
          
                   (lambda(f n)
                      (set 'result 0)
                      (for (i 1 n)
                           (inc result (f i)))
                      result)

                   'f 'n 'i 'result))

; Try it, and you'll see it works. And that expression is,
; in turn result of application of following function:

(set 'safet                                      ; FUNCTION
     (lambda(safe-name unsafe-function vars k)   ; GENERATING
            (list 'let                           ; SAFE VERSION
                     (map (lambda(v)             ; GENERATING
                             (list v             ; EXPRESSION
                                  (list 'quote
                                        (sym (append (string safe-name)
                                                     "."
                                                     (string v)
                                                     "."
                                                     (string k))))))
                           vars)
                     (append (list 'expand)
                             (list unsafe-function)
                             (map (lambda(v)(list 'quote v)) vars)))))
                          
; So, (eval (safet 'sum unsafe-sum '(f n i result) 3)) should
; produce safe version of function sum.

(println "-----\nTest of safet:")

(set 'unsafe-sum (lambda(f n)
                     (set 'result 0)
                     (for (i 1 n)
                          (inc result (f i)))
                          result))

(println (eval (safet 'sum unsafe-sum '(f n i result) 3)))

; The next step is - to define the function that behave like unsafe-sum
; but in fact, it accept the arguments, produces 1st, 2nd, 3rd etc
; version of unsafe-sum, evaluate it and return result. For something
; like that, we'll need to add one global counter, let's denote it
; sum.counter.

(set 'sum.counter 0)
(set 'sum (lambda-macro()
              (inc sum.counter)
              
              ;-------------------------------------------
              ;        This part only for test.
              
              (println "---\nNow I'll evaluate:")
              (println (cons (eval (safet 'sum
                                          unsafe-sum
                                          '(f n i result)
                                          sum.counter))
                             (args)))
                             
              ;        Delete it if you want for real.
              ;--------------------------------------------
 
              (eval (cons (eval (safet 'sum
                                        unsafe-sum
                                        '(f n i result)
                                        sum.counter))
                          (args)))))

; OK, let's test it:

(println "---------\nTest of safe sum:")

(println (sum (lambda(x)x) 1))
(println (sum (lambda(x)x) 10))
(println (sum (lambda(x)x) 100))

; These are results: if you are still with me, you can see, it
; works.
;
; ------------------
; Now I'll evaluate:
; ((lambda (sum.f.1 sum.n.1) (set 'sum.result.1 0)
;   (for (sum.i.1 1 sum.n.1)
;    (inc sum.result.1 (sum.f.1 sum.i.1))) sum.result.1)
;  (lambda (x) x) 1)
; 1
; ------------------
; Now I'll evaluate:
; ((lambda (sum.f.2 sum.n.2) (set 'sum.result.2 0)
;   (for (sum.i.2 1 sum.n.2)
;    (inc sum.result.2 (sum.f.2 sum.i.2))) sum.result.2)
;  (lambda (x) x) 10)
; 55
; ------------------
; Now I'll evaluate:
; ((lambda (sum.f.3 sum.n.3) (set 'sum.result.3 0)
;   (for (sum.i.3 1 sum.n.3)
;    (inc sum.result.3 (sum.f.3 sum.i.3))) sum.result.3)
;  (lambda (x) x) 100)
; 5050
;

; There is only one step left. I want to automatize production
; of safe functions on demand, i.e. to write unsafe-sum, then
; evaluate following function call:
;
;       (protect 'sum 'unsafe-sum '(f n i result))
;
; and that result is equivalent to evaluation of the previous
; two expressions:
;
; (set 'sum.counter 0)
; (set 'sum ...
;

(set 'protect
     (lambda(safe-name unsafe-name vars)
        (let ((counter-name (sym (append (string safe-name)
                                         ".counter"))))
             (set counter-name 0)
             
             (eval  (expand
                      '(set 'safe-name
                            (lambda-macro()
                               (inc counter-name)
                               
                               ;---------------------------
                               ; This part only for test
                               
                               (println "---\nNow I'll evaluate:")
                               (println (cons (eval (safet 'safe-name
                                                         unsafe-name
                                                         'vars
                                                         counter-name))
                                               (args)))
                                      
                               ; Delete it if you want for real
                               ;---------------------------
                               
                               (eval (cons (eval (safet 'safe-name
                                                         unsafe-name
                                                         'vars
                                                         counter-name))
                                           (args)))))
                       'safe-name
                       'unsafe-name
                       'vars
                       'counter-name)))))
;
; Let us see whether it works:
;

(println "--------\nTest function protect")

(delete 'sum)
(protect 'sum 'unsafe-sum '(f n i result))

(println (sum (lambda(x)x) 1))
(println (sum (lambda(x)x) 10))
(println (sum (lambda(x)x) 100))

; It works.

; Another test:

(println "-----\nTest of complex expression (2):")

(println (sum (lambda(n)(sum pow n)) 2))

; The protected version gave result - 6. As it is expected.
;
;
; Two things can be noted.
;
; (1) In this example, I "protected" all of the variables used
; in the function unsafe-sum: by consistently changing  f, n, i and
; result. It is not necessary - some of these variables can be
; intentionally left with the same name in all function calls.
;
; (2) Even such, protected sum contains one variables that does
; not change its names from one call to another: sum.counter. Is
; it possible that the problem isn't solved? No, sum.counter
; is designed to allow communication between different recursive
; calls
;
; OK, enough for now.
;
(exit)

9 comments:

  1. Great article!

    Although I had trouble understanding what you were doing for a while. You're passing an anonymous function as an argument to another function, I think. ? I always define my functions to have 'let' or 'local', and I very rarely pass functions like you mathematicians whizzes do! :)

    ReplyDelete
  2. Thanks, yes, I'm using these anonymous functions here.

    I start with "unsafe function", say f.

    Then I construct safe version Sf, which is some kind of "wrap" around original f. Sf contains f inside, and transfer arguments to that f.

    But - here is the point - not always to same f, but to its copy which differs only in names of the used variables. Each time Sf is called, new and different copy of f is generated and applied. So functionality is same but accidental overshadowing is impossible - even in the case of recursive functions.

    Next step is automatization of such wrapping so f --> Sf doesn't have to be done manually.

    (These "mutated copies" are those anonymous functions you've seen.)

    You are right that let and local are usually more than enough of protection.

    ReplyDelete
  3. This looks more like an argument against dynamic programming to me.

    ReplyDelete
  4. *dynamic scope.

    ReplyDelete
  5. Because it puts complex code and libraries at jeopardy, as you mentioned in your post, and the solution to the problem is more of a hack then a real solution (no offense).

    You're having to jump through hoops just to make functions safe to use in libraries, and your function isn't part of the newLISP standard library. Even if it was, its solution isn't very pretty, nor is it very efficient as it could potentially lead to the creation of many thousands of symbols. This would slow down the overall operation of the interpreter, just to do symbol lookups.

    Of course, I may be mistaken, feel free to correct me if I am.

    ReplyDelete
  6. I'll try to address that in one of the next posts.

    ReplyDelete
  7. The correct solution to safe variable encapsulation in newLISP is using contexts/namespaces. They can be passed as parameters to user-defined functions and are easier to understand.

    Kazimir's functions are very interesting from a theoretical point of view, exploring how dynamic scoping works in newLISP.

    I don't think he meant them to be used as a practical solution for passing around variable environments. That is what lexical namespaces in newLISP are for.

    ReplyDelete
  8. This comment has been removed by the author.

    ReplyDelete