Speed of The Evaluation vs. Length of The Names of The Variables.

; Newlisp is an interpreter; so one question bothered me: does the
; length of the variables influence the speed of the evaluation?
; Is my program any faster if I use, say, x instead of xxx? It
; should be at least bit faster. But how much faster?

; I wrote the program that evaluates essentially same expression,
; but with different variables;

; (for (a 1 10) ...
; (for (aa 1 10) ...
; (for (aaaa 1 10) ...

; and so forth.

; On my surprise, there are no noticeable differences in the
; time required for evaluation. Here are the results:


; length(var)=1, length(expression)=35, time=340
; length(var)=2, length(expression)=38, time=339
; length(var)=4, length(expression)=44, time=336
; length(var)=8, length(expression)=56, time=364
; length(var)=16, length(expression)=80, time=359
; length(var)=32, length(expression)=128, time=350
; length(var)=64, length(expression)=224, time=354
; length(var)=128, length(expression)=416, time=364
; length(var)=256, length(expression)=800, time=352
; length(var)=512, length(expression)=1568, time=337
; length(var)=1024, length(expression)=3104, time=332
; length(var)=2048, length(expression)=6176, time=360
; length(var)=4096, length(expression)=12320, time=342
; length(var)=8192, length(expression)=24608, time=337
; length(var)=16384, length(expression)=49184, time=337
; length(var)=32768, length(expression)=98336, time=351
; length(var)=65536, length(expression)=196640, time=338
; length(var)=131072, length(expression)=393248, time=339
; length(var)=262144, length(expression)=786464, time=341
; length(var)=524288, length(expression)=1572896, time=356
; length(var)=1048576, length(expression)=3145760, time=348
; length(var)=2097152, length(expression)=6291488, time=341
; length(var)=4194304, length(expression)=12582944, time=336
; length(var)=8388608, length(expression)=25165856, time=347

; And i did it for another expression, this time bit more
; complicated, again, there is no visible influence of the
; length of the variable and length of the expression on
; evaluation time.

; length(var)=1, length(expression)=79, time=1565
; length(var)=2, length(expression)=87, time=1562
; length(var)=4, length(expression)=103, time=1574
; length(var)=8, length(expression)=135, time=1559
; length(var)=16, length(expression)=199, time=1568
; length(var)=32, length(expression)=327, time=1557
; length(var)=64, length(expression)=583, time=1555
; length(var)=128, length(expression)=1095, time=1545
; length(var)=256, length(expression)=2119, time=1544
; length(var)=512, length(expression)=4167, time=1554
; length(var)=1024, length(expression)=8263, time=1564
; length(var)=2048, length(expression)=16455, time=1553
; length(var)=4096, length(expression)=32839, time=1560
; length(var)=8192, length(expression)=65607, time=1557
; length(var)=16384, length(expression)=131143, time=1559
; length(var)=32768, length(expression)=262215, time=1557
; length(var)=65536, length(expression)=524359, time=1554
; length(var)=131072, length(expression)=1048647, time=1539
; length(var)=262144, length(expression)=2097223, time=1521
; length(var)=524288, length(expression)=4194375, time=1527
; length(var)=1048576, length(expression)=8388679, time=1550
; length(var)=2097152, length(expression)=16777287, time=1536
; length(var)=4194304, length(expression)=33554503, time=1534
; length(var)=8388608, length(expression)=67108935, time=1535




(setq varname 'a)
(for (i 1 24)
     (set 'expr
          (expand '(for (varname 1 100)
                        (+ (- varname 1) (- varname 2)))
                   'varname))
     (set 'evtime
          (time (eval (eval expr)) 10000))
     
     (print "length(var)=" (length (string varname)))
     (print ", length(expression)=" (length (string expr)))
     (println ", time=" evtime)
     
     (setq varname (sym (dup (string varname) 2))))

(println)

(setq varname1 'a)
(setq varname2 'b)
(for (i 1 24)
     (set 'expr
          (expand '(begin (set 'varname1
                               (lambda(varname2)
                                      (if (< varname2 3)
                                          1
                                          (+ (varname1 (- varname2 1))
                                             (varname1 (- varname2 2))))))
                          (varname1 12))
                  'varname1
                  'varname2))
     (set 'evtime
          (time (eval expr) 10000))
     
     (print "length(var)=" (length (string varname1)))
     (print ", length(expression)=" (length (string expr)))
     (println ", time=" evtime)
     
     (setq varname1 (sym (dup (string varname1) 2)))
     (setq varname2 (sym (dup (string varname2) 2))))

Conversions to Functions and Macros.

;===============================================================
; CONVERSION OF FUNCTIONS TO MACROS AND VICE VERSA
;
;
; If you think on the way I do, then you sometimes have the function,
; and you want macro - to avoid using of one extra quote in the
; function call. Or, you have a macro, and you want function to pass
; it value stored in some variable.

; In this post, I'll define two cute functions for exactly that purpose;
;
; macro-from-function
; function-from-macro

; Lets start with one meaningless function and macro for illustration
; of the idea.

(set 'set-first-to-0-function
      (lambda()
         (set-nth ((first (args)) 0) 0)))

(set 'set-last-to-0-macro
     (lambda-macro()
         (set-nth ((first (args)) -1) 0)))
         
; The definitions are nearly equal, the difference is
; in the way we call these two:

(println (set-first-to-0-function '(1 2 3 4 5))) ; (0 2 3 4 5)
(println (set-last-to-0-macro (1 2 3 4 5)))   ; (1 2 3 4 0)

;---------------------------------------------------------------
; The similarity of these two definitions is striking, but it
; is not completely trivial to convert one to another - because
; lambda and lambda-macro definitions are not simply lists with
; the first elements lambda or lambda-macro. They are more something
; like special kinds of lists, as it can be seen from following
; expressions:

(println (first (lambda(x)(print x)))) ;(x)
(println (rest (lambda(x)(print x)))) ;((print x))

; Cons can surprise you:

(println (cons (lambda-macro) (lambda()(print))))

(lambda (lambda-macro ) () (print))

; But append behaves nice, so, it is maybe the most natural
; way to exchange lambda and lambda-macro:

(println (append (lambda-macro) (lambda(x)(print x))))

; result: (lambda-macro(x)(print x))

(set 'function-from-macro (lambda()
                             (append '(lambda) ; quote can be omitted
                                      (first (args)))))
(set 'macro-from-function (lambda()
                             (append '(lambda-macro)
                                      (first (args)))))
                                         
;---------------------------------------------------------------
; Does it work?

(set 'set-first-to-0-macro
     (macro-from-function set-first-to-0-function))
     
(set 'set-last-to-0-function
     (function-from-macro set-last-to-0-macro))

(println (set-first-to-0-macro (1 2 3 4 5))) ; (0 2 3 4 5)
(println (set-last-to-0-function '(1 2 3 4 5)))   ; (1 2 3 4 0)

;===============================================================
; CONVERSION OF BUILT-INS to LAMBDA AND LAMBDA-MACRO EXPRESSIONS.

; In Newlisp, there is no clear distinction between built in
; functions and built in macros. The program cannot test whether
; built in is function or macro, and in the reference manual,
; all of them are called functions. But some of the built ins
; really behave as functions, while some behave more like
; macros. For example, "reverse" is function. You have to call it
; with argument that evaluate to list, not list itself.

(println (reverse '(1 2 3)))

; Unlike "reverse", "for" behaves like macro:

(for (i 7 9) (println i))

; obviously, the expressions (i 7 9) and (println i) are not evaluated
; prior to the call of the "for."
;
; So, one might want to use macro version of reverse, something like
;
;                 (reverse-macro (1 2 3))
;
; or functional version of for:
;
;                 (for-function '(i 7 9) '(println i))
;
; Unfortunately, our function-from-macro and macro-from-function
; do not work for "reverse" and "for." They need lambda and
; lambda-macro expressions.

; We'll solve this problem by writing two functions that transform
; built in functions in lambda expressions, and built in macros in
; lambda-macro expressions. After that, function-from-macro and
; macro-from-function can be applied.

; How can we define the lambda and lambda-macro expressions
; doing exactly the same thing as reverse and for?

; These are some possibilities:

(lambda()
   (apply 'reverse $args))
   
(lambda-macro()
   (eval (cons 'for $args)))
           
; Let's test it:

(println "======================================================")
(println ((lambda()
           (apply 'reverse $args))
           '(1 2 3)))

; and

((lambda-macro()
      (eval (cons 'for $args)))
 (i 7 9)
 (println i))
 
; RESULT:
; (3 2 1)
; 7
; 8
; 9

; It works.

; It is obviously the trick; but it serves its purpose.
; Now, we can automatize such transformation of built-ins into
; equivalent lambda and lambda-macro expressions:

(println "======================================================")

(set 'lambda-form
     (lambda(built-in-name)
       (expand '(lambda()(apply 'built-in-name $args))
               'built-in-name)))
               
(set 'lambda-macro-form
     (lambda(built-in-name)
        (expand '(lambda-macro()(eval (cons 'built-in-name $args)))
                'built-in-name)))

; Does it work?

(set 'reverse-macro (macro-from-function (lambda-form 'reverse)))
(set 'for-function (function-from-macro (lambda-macro-form 'for)))

(println (reverse-macro (1 2 3)))
(for-function '(i 1 100) '(print i))

; It does.

(exit)

On Calling and Applying Newlisp Functions and Macros.

;---------------------------------------------------------------
; I continue with my researches of the Newlisp basics. It might be
; boring to some of the readers, but there will be plenty of
; time for other topics.
;
; The macros and the functions are, due to dynamic scoping, more
; similar in Newlisp than in other languages from Lisp family. The
; difference is only in the way arguments are passed to these two.

(set 'x 10 'y 20)

((lambda()(println (args)))
     1 2 "a" x y + - (+ x y)
     '1 '2 '"a" 'x 'y '+ '-  '(+ x y))
((lambda-macro()(println (args)))
     1 2 "a" x y + - (+ x y)
     '1 '2 '"a" 'x 'y '+ '-  '(+ x y))

; RESULTS:

;(1 2 "a" 10 20 + <40C365> - <40C380> 30 1 2 "a" x y + - (+ x y))
;(1 2 "a" x y + - (+ x y) '1 '2 '"a" 'x 'y '+ '- '(+ x y))

; (arg) in the CALLED function is list of evaluated arguments
; (arg) in the CALLED macro is list of unevaluated arguments

;---------------------------------------------------------------
; However, APPLYING of functions and macros on list works slightly
; different. Let as suppose that function and macro are APPLIED
; on list L.

(set 'L '(1 2 "a" (lambda()) x y + - (+ x y)
         '1 '2 '"a" 'x 'y '+ '-  '(+ x y)))
         
(apply (lambda()(push 4 (args))(println(args)))
       L)

(apply (lambda-macro()(println(args)))
       L)

; RESULTS:

;(1 2 "a" x y + - (+ x y) '1 '2 '"a" 'x 'y '+ '- '(+ x y))
;(1 2 "a" 'x 'y '+ '- '(+ x y) ''1 ''2 ''"a" ''x ''y ''+ ''- ''(+ x y))

;(args) in APPLIED function is copy of the L.
;       it is not original L; I tested that.

;(args) in APPLIED macro is OPTIMIZED list of the quoted elements of L
;       where OPTIMIZED means that "self-evaluating" elements are COPIED,
;       not quoted.

; That optimization in macro application is not harmful, because it
; holds that, inside APPLIED macro, (map eval (args)) is equal to L.

(apply (lambda-macro()(println (= L (map eval (args))))) L) ; true

Verbose Functions and Macros.

; --------------------------------------------------------------
; Back in 1970's, one of the best programmers in the local
; public computer center started to behave on strange way. During
; one of our conversations he said " The highest level of the
; programming is when you do not need computer any more,
; you simply sit on the sofa, eat chips and think how program
; should work. Strange argument, but nevertheless, not illogical.
; Sure, if you use your mind as a computer, you cannot
; really make million calculations in few seconds, but as I
; already knew - results are not important - programs are important.

; I felt that something was wrong about it, but the best critical
; I was able to formulate was: if you write programs in your mind,
; they ALWAYS work, right?

; Very soon, my young friend left programming for good; I didn't
; and my programs still do not work.

; One of the best method for fixing them is to make them not only
; evaluate, but also to produce verbose output similar
; to one I used in my blog article on macros:

; ==============================================================
; (-> min-used-cells 945)
; (-> max-used-cells 945)
; --------------------------------------------------------------
; |||||Macro (fibom2 4) called.
; |||||||||Macro (fibom2 (- ex 1)) called.
; |||||||||||||Macro (fibom2 (- ex 1)) called.
; ||||||||||||||Macro (fibom2 (- ex 1)) returns 1.
; |||||||||||||Macro (fibom2 (- ex 2)) called.
; ||||||||||||||Macro (fibom2 (- ex 2)) returns 1.
; ||||||||||Macro (fibom2 (- ex 1)) returns 2.
; |||||||||Macro (fibom2 (- ex 2)) called.
; ||||||||||Macro (fibom2 (- ex 2)) returns 1.
; ||||||Macro (fibom2 4) returns 3.
; --------------------------------------------------------------
; (-> (fibom2 32) 2178309)
; (-> (time (fibom2 32)) 9734)
; (-> min-used-cells 945)
; (-> max-used-cells 1269)
; ==============================================================

; Everyone likes such outputs. If there is some error, it is
; easier to find it. To achieve that, I wrote the macro fibom2
; on the complicated way:

'(set 'fibom2 (macro(x)
               (print-ln (evaluation-level-indent)
                         "Macro (fibom2 " x ") called.")
               (letn ((ex (eval x))
                      (result (if (< ex 3)
                                 1
                                 (+ (fibom2 (- ex 1))
                                    (fibom2 (- ex 2))))))
                    (print-ln (evaluation-level-indent)
                              "Macro (fibom2 " x ") returns " result ".")
                    (memory-watch)
                    result)))
                    
; However, the "real" code that evaluates
; Fibonacci numbers is concentrated in the middle, in the part

;               (letn ((ex (eval x))
;                      (result (if (< ex 3)
;                                 1
;                                 (+ (fibom2 (- ex 1))
;                                    (fibom2 (- ex 2))))))

; So, it might be possible to automatize production of such
; verbose functions, writing macros that turn "normal" functions
; into verbose, and vice-versa. And also, turning normal macros
; in verbose macros and vice versa.

; Also, the output I used in article about macros is not optimal.
; It is nice for small programs, but sometimes, output required
; for debugging could be quite large - thousands of lines, dozens
; of nested function calls. One possibility of the output is in
; use of the nested s-expressions.

'(fibo (in 4)
       (caller 4)
       (fibo (in 3)
             (caller (- x 1))
             (fibo (in 2)
                   (caller (- x 1))
                   (time 0)
                   (memory 13 (total 1262))
                   (out 1))
             (fibo (in 1)
                   (caller (- x 2))
                   (time 0)
                   (memory 13 (total 1263))
                   (out 1))
             (time 24)
             (memory 13 (total 1200))
             (out 2))
       (fibo (in 2)
             (caller (- x 2))
             (time 0)
             (memory 13 (total 1201))
             (out 1))
       (time 49)
       (memory 10 (total 1144))
       (out 3))
      
; This is not the code - this is output of the verbose function.
; Now, why such output? Because, if it is very long, and I find
; that some (out x) part is wrong - I can use text editor to
; show me where is appropriate (in ...). For that purpose, editors
; that highlight whole s-expressions, not only parentheses are better.




; This is Dr. Scheme. Such a highlighting is very useful if
; s-expressions are very long.

; the function that produced output above looked like:

(set 'debug-indent 0)
(set 'fibo (lambda-macro ()
            '(original-function-definition
              (lambda-macro (`x)
                   (let ((x (eval `x)))
                        (if (<= x 2)
                         1
                         (+ (fibo (- x 1)) (fibo (- x 2)))))))
          (let ((t)
               (result)
               (used-memory (sys-info 0)))
           (print (dup " " debug-indent) "(fibo (in")
           (doargs (arg)(print " " (eval arg)))
           (println ")")
           (inc 'debug-indent 6)
           (print (dup " " debug-indent) "(caller")
           (doargs (arg)(print " " arg))
           (println ")")
           (set 't (time (set 'result (eval (append (list
           
           ; Here is original macro
           ; ------------------------------------------
           (lambda-macro (`x)
                    (let ((x (eval `x)))
                     (if (<= x 2)
                      1
                      (+ (fibo (- x 1)) (fibo (- x 2))))))
           ;--------------------------------------------
                                                          )(args))))))
           (println (dup " " debug-indent)
                    "(time " t ")\n"
                    (dup " " debug-indent)
                    "(memory " (- (sys-info 0) used-memory)
                    " (total " (sys-info 0) "))\n"
                    (dup " " debug-indent)
                    "(out " result "))")
           (dec 'debug-indent 6) result)))

(fibo 4)
           
; It might look complicated - but it is not, it is
; only relatively large - and macros that transform original version
; in the version above are relatively simple.

; I use storing blocks of data into function body, already described
; in one of the previous blogs, so you can  scroll
; down until last few paragraphs:


(set 'block?
     (lambda()
              (and (list? (first (args)))
                   (not (empty? (first (args)))))))
(set 'get-block-name
     (lambda(some-block)
              (if (not (block? some-block))
                  (throw-error (list "get-block-name applied on non-block"
                                     some-block))
                  (first some-block))))
(set 'quoted-block?
     (lambda(argument)
         (if (or (quote? argument)
                 (and (list? argument)
                      (not (empty? argument))
                      (= (first argument) 'quote)))
             (block? (eval argument)))))
             
(set 'beginize-block
     (lambda(some-block)
              (append '(begin)
                      (rest some-block))))

(set 'get-block-from-list-containing-quoted-blocks
     (lambda(block-name L)
              (catch (dolist (i L)
                        (if (and (quoted-block? i)
                                 (= block-name
                                    (get-block-name (eval i))))
                            (throw (eval i)))))))

(set 'or-function-macro? (lambda(L)
                            (or (lambda? L) (macro? L))))

(set 'set-quoted-block-in-list
     (lambda(b L)
       (catch (begin (dolist(i L)
                       (when (and (quoted-block? i)
                                  (= b (get-block-name (eval i))))
                             (prinln "set-quoted-block: pronadjen.")
                             (throw (nth-set (L $idx) b))))
                      (println "set-quoted-block: nije pronadjen u listi.")
                      (push (list 'quote b)
                            L
                            (if (or-function-macro? L) 1 0))
                      (println "set-quoted-block-returns " L)))))

(set 'evaluate-block-from-list-containing-quoted-blocks
     (lambda (block-name list-containing-quoted-blocks)
               (eval (beginize-block
                         (get-block-from-list-containing-quoted-blocks
                              block-name
                              list-containing-quoted-blocks)))))
                              
;---------------------------------------------------------------
; Finally, here are these two macros. Also, global variable, named
; debug-indent has to be maintained, so indents can be more
; precisely calculated.

;===============================================================
; DEBUG-WRAP & DEBUG-UNWRAP
; usage: (debug-wrap <function-name>)
;        (debug-unwrap <function-name>)

(set 'blank (lambda(x)(dup " " x)))
(set 'debug-indent 0)
(set 'debug-wrap
     (lambda-macro()
      (letn ((`function-name (first (args)))
             (function-name (eval `function-name))
             (debug-indent-step (+ (length (string `function-name))
                                   2))
             (in-line (append "(" (string `function-name) " (in")))
            (set `function-name
                 (expand
                    (lambda-macro()
                      '(original-function-definition function-name)
                      (let ((t)
                            (result)
                            (used-memory-before)
                            (used-memory-after))
                           
                           (print (blank debug-indent) in-line)
                           (doargs(arg/debug-wrap)
                                (print " " (eval arg/debug-wrap)))
                           (println ")")
                           
                           (inc 'debug-indent debug-indent-step)
                           
                           (print (blank debug-indent) "(caller")
                           (doargs(arg/debug-wrap)
                                (print " " arg/debug-wrap))
                           (println ")")
                           
                           (set 'used-memory-before (sys-info 0))
                           (set 't
                                (time (set 'result
                                            (eval (cons function-name
                                                          (args))))))
                           (set 'used-memory-after (sys-info 0))
                                                      
                           (println (blank debug-indent)
                                    "(time " t ")\n"
                                    (blank debug-indent)
                                    "(memory " (- used-memory-after
                                                  used-memory-before)
                                    " (total " (sys-info 0) "))\n"
                                    (blank debug-indent)
                                    "(out " result "))")

                           (dec 'debug-indent debug-indent-step)
                                 result))
                          'function-name
                          'debug-indent-step
                          'in-line)))))
                          
(set 'debug-unwrap
     (lambda-macro()
       (letn ((`function-name (first (args)))
              (function-name (eval `function-name)))
             (set `function-name
                  (evaluate-block-from-list-containing-quoted-blocks
                     'original-function-definition
                      function-name)))))

;===============================================================

(set 'fibo (lambda(x)(if (>= x 3)
                         (+ (fibo (- x 1))
                            (fibo (- x 2)))
                         1)))
                         
(println "debug-wrap test --------------------------------------")
(debug-wrap fibo)
(fibo 4)

;Output is as follows:

; (fibo (in 4)
;       (caller 4)
;       (fibo (in 3)
;             (caller (- x 1))
;             (fibo (in 2)
;                   (caller (- x 1))
;                   (time 0)
;                   (memory 0 (total 1079))
;                   (out 1))
;             (fibo (in 1)
;                   (caller (- x 2))
;                   (time 0)
;                   (memory 0 (total 1080))
;                   (out 1))
;             (time 3)
;             (memory 0 (total 1029))
;             (out 2))
;       (fibo (in 2)
;             (caller (- x 2))
;             (time 0)
;             (memory 0 (total 1030))
;             (out 1))
;       (time 8)
;       (memory 0 (total 983))
;       (out 3))
;

(println "debug-unwrap test ------------------------------------")
(debug-unwrap fibo)
(println (fibo 4)) ; 3

; And it appears it works. I tested these two macros, debug-wrap
; and debug-unwrap not only on functions, but on macros also, and
; also on the functions and macros that use arguments from (args)
; and it also worked.





; Dr Scheme "program counture" shows 550 lines output of "verbose" (fibo 10).
; It should be pretty because the ratio between (fibo n) and (fibo (- n 1)), always
; called in pairs converges toward golden ratio. Is it pretty?


; One possible improvement could be writing in the file instead on the screen.

; The debug-wrap and debug-unwrap demonstrate one advantage of the Newlisp.
; The macros can be switched from "normal" to "verbose" versions and back automatically
; because they are the first class citizens, so they can be arguments
; of debug-wrap and debug-unwrap.