; 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))))
;===============================================================
; 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)
;---------------------------------------------------------------
; 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
; --------------------------------------------------------------
; 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.
