Swap Without Temporary Variable.
; Short one, inspired by blog post posted by Cormullion on Newlisp forum:
; Swap values of two variables without using temporary variable.
(set 'a 1 'b 2)
(println a "," b); 1, 2
(set 'a (+ a b))
(set 'b (- a b))
(set 'a (- a b))
(println a "," b); 2, 1
(exit)
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.
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)
Subscribe to:
Posts (Atom)