Don't Fear Dynamic Scope (2.)

; My last post presented two techniques for safe use of
; dynamic scope. The post was criticized for a few reasons
; and this post is attempt for answer. You can read it if previous
; post was sufficiently interesting to you.
;
; One of the two presented techniques was simple renaming of the
; variables on the way it is unlikely that one will use same
; variable names independently. That technique was, however,
; not enough if two instances of the same function communicate
; between themselves. These two instances necessarily share
; same variable names!

; More sophisticated and interesting technique consisted of
; "protecting" function with one macro wrapped around it.
;
; Let's say that SF is our protected version of the function F.
; When SF is called, it transfers all arguments to F. Not really
; original F, but slightly mutated one. For example, if original
; F used x, y and z then its mutated version uses
;
;      F.x.1, F.y.1, F.z.1 first time SF is called,
;      F.x.2, F.y.2, F.z.2 second time SF is called
;
; and so forth.
;
; On that way, advantages of dynamic scope are kept, while
; there is no danger of unintentional overshadowing of the original
; semantics.
;
; That post attracted criticism, from both technical and lets say,
; philosophical point of view, and some criticals were justified.
;
; From technical point of view, reader noted that my protected
; functions leak - symbols. And really, they do. One thing
; I didn't seen was that Newlisp interpreter keep names
; of variables used in anonymous functions in symbol list.
; For example, look at the following communication copied from :
; Newlisp REPL

;             newLISP v.9.9.93 on Win32 IPv4...
;
;             > (lambda(x))
;             (lambda (x))
;             > (find "x" (map string (symbols)))
;             355
;             > (find "y" (map string (symbols)))
;             nil
;             >

; As you can see, x is not deleted automatically. It has to
; be deleted explicitly. So, I had to take care about deleting
; extra variables. Solution, however, didn't required any
; additional technique, just addition of few "delete" expressions.

; Two useful versions of append. These functions append strings
; and symbols, without need for explicit conversion.

(set 'symappend (lambda()(sym (apply append (map string (args))))))
(set 'stringappend (lambda()(string (apply symappend (args)))))

; Manually defined protected version of "sum":

(set 'sum
     (lambda-macro()
        (inc sum.counter)
        (let ((c (string sum.counter)))
             (first
               (list
                 (eval
                   (let ((f      (symappend "sum" "." "f" "." c))
                         (n      (symappend "sum" "." "n" "." c))
                         (i      (symappend "sum" "." "i" "." c))
                         (result (symappend "sum" "." "result" "." c)))
                        (cons (expand

                                  ; ORIGINAL SUM GOES HERE

                                  (lambda(f n)
                                      
                                      (set 'result 0)
                                      (for (i 1 n)
                                           (inc result (f i)))
                                      result)
                                   
                                   ; THE LIST OF PROTECTED VARS

                                   'f 'n 'i 'result )

                              (args))))
                 (begin (delete (symappend "sum" "." "f" "." c))
                        (delete (symappend "sum" "." "n" "." c))
                        (delete (symappend "sum" "." "i" "." c))
                        (delete (symappend "sum" "." "result" "." c))))))))

; The function protect that takes few arguments, most importantly
; unprotected function; variables that should be protected and
; finally, name of the new function.

(set 'protect
     (lambda(safename unsafename vars)
        (letex ((c1 (symappend safename ".counter"))
                (c2 (map (lambda(x)(list x
                                        (list 'symappend
                                              (string safename)
                                              "."
                                              (string x)
                                              "."
                                              'c)))
                         vars))
                (c3 (append (list 'expand (eval unsafename))
                            (map quote vars)))
                (c4 (append '(begin)
                            (map (lambda(x)(list 'delete
                                                 (list 'symappend
                                                       (string safename)
                                                       "."
                                                       (string x)
                                                       "."
                                                       'c)))
                                 vars))))
               (lambda-macro()
                 (inc c1)
                 (let  ((c (string c1)))
                       (first (list (eval
                                      (let c2
                                           (cons c3 (args))))
                                    c4)))))))

; "Protect" is short, but very complicated function. It is function
; of the third order, i.e. it returns macros that generate functions.
; It is hard to understand what it does by looking at source.
; But it was not really hard to write "protect" because it is
; "linear:" there is no loops or recursions whatsoever and
; it can be easily tested. It can be applied on unsafe
; version of "sum" and result can be compared with manually
; defined safe version.

; Now I'll define function unprotected-sum, and generate
; protected-sum using function protect.
                                        
(set 'unprotected-sum (lambda(f n)
                       (set 'result 0)
                       (for (i 1 n)
                            (inc result (f i)))
                            result))

(set 'protected-sum (protect 'protected-sum
                        'unprotected-sum '(f n i result)))

;===============================================================
; The following code tests correctness and symbol leaking of protected
; function and compares speed of the protected and unprotected sum.


(println "\nCorectness and symbol leaking test.")
(println "\nNumber of symbols before test: " (length (symbols)))

(println "Should be 5050: " (protected-sum (lambda(x)x) 100))
(println "Should be    6: " (protected-sum (lambda(n)
                                               (protected-sum pow n))
                                               2))

(for (i 1 1000)(protected-sum (lambda(x)x) i))
(for (i 1 1000)(protected-sum (lambda(n)(protected-sum pow n)) 2))

(println "Number of symbols after test:  " (length (symbols)))

(println "\nSpeed comparison.")
(println "\nUnprotected sum time: "
         (time (for (i 1 10000)(unprotected-sum (lambda(x)x) i)))
         " ms")

(println "Protected sum time:   "
         (time (for (i 1 10000)(protected-sum (lambda(x)x) i)))
         " ms" )


(exit)

;                              THE RESULTS
;
; Corectness and symbol leaking test.
;
; Number of symbols before test: 382
; Should be 5050: 5050
; Should be    6: 6
; Number of symbols after test:  382
;
; Speed comparison.
;
; Unprotected sum time: 20833 ms
; Protected sum time:   24533 ms
;
;---------------------------------------------------------------
;
; Other, more essential and less technical part of the criticism
; is also interesting. Here is whole critical.
;
;            (Dynamic scope is bad) 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.
;            
;
; The solution, as presented here, doesn't leak variables. Slow
; down caused by substition of new variables linearly depends on  
; length of original function. More exactly, it is
;
;          constant * length(F) * log (number of vars)
;
; From theoretical point of view, it can be considered satisfactory.
;
; Is there a problem that functions like "protect" are not part
; of Newlisp, its core or standard library? In principle, nothing
; prevents introduction of function similar to protect to standard
; libraries or maybe even core language - fact is, however, there
; is little if any demand for that.
;
; Using static scope, called function cannot access to the environment
; of the caller, so there is no such problems at all. It is safer,
; but less expressive choice. The need for dynamic scope is recognized
; in another one Common Lisp and Scheme construct - macros.