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)