;===============================================================
; Predicates =?, >? and friends
(dolist (predicate '(< > = <= >= !=))
(set 'left (sym (append (string predicate) "?")))
(set 'right (expand (lambda(x)
(expand (lambda(y)
(predicate y x))
'x))
'predicate))
(set left right))
(println (filter (<=? 3) '(1 2 3 4 5 1 2 3 4 5)))
(println (map (=? 4) '(1 2 3 4 5 1 2 3 4 5)))
(println (clean (>? 1) '(1 2 3 4 5 1 2 3 4 5)))
(exit)
RESULTS:
(1 2 3 1 2 3)
(nil nil nil true nil nil nil nil true nil)
(1 1)
;---------------------------------------------------------------
;
; In this post, I implement simple support for "two phases" evaluation,
; in the form of function "prepare" that accepts code as an argument,
; and returns "prepared" code. Prepared code consists of original
; expressions, except
;
; [1] expressions of a form
;
; (prepare-time expr1 ... exprn)
; Such expressions are evaluated during prepare-time and replaced
; with their results in prepared code. Again, except
;
; [1a] if result of the evaluation during prepare time is
; symbol !! then expression is omitted from prepared code.
;
; [2] expressions of the form (F expr1 ... exprn) where F evaluates to
; function or macro which contains 'prepare-time symbol, for
; example
;
; (lambda-macro(x)
; 'prepare-time
; (list '* x x))
;
; Such function or macro calls are evaluated duringe prepare-time
; and replaced in prepared code with results of their evaluation.
;
;---------------------------------------------------------------
;
; mapg and cleang are versions of map and clean that respect
; lambda and lambda-macro expressions.
(set 'mapg (lambda(f L)
(append (cond ((lambda? L) (lambda))
((macro? L) (lambda-macro))
(true '()))
(map f L))))
(set 'cleang (lambda(f L)
(append (cond ((lambda? L) (lambda))
((macro? L) (lambda-macro))
(true '()))
(clean f L))))
;---------------------------------------------------------------
(set 'prepare-time begin)
(set '!! '!!)
(set 'prepare-time-fn?
(lambda(expr)(and (symbol? expr)
(or (lambda? (eval expr)) (macro? (eval expr)))
(= (nth 1 (eval expr)) ''prepare-time))))
(set 'prepare
(lambda(expr)
(let ((result
(if (and (list? expr)
(not (empty? expr)))
(if (= (first expr) 'prepare-time)
(eval expr) ; [1]
(begin (set 'expr (mapg prepare expr)); recursion
(if (prepare-time-fn? (first expr))
(eval expr) ; [2]
expr)))
expr))) ; general case
(if (list? result)
(cleang (lambda(x)(= x !!)) result) ; [1a]
result))))
; And that's it. Really simple.
;---------------------------------------------------------------
; Now, I'll test it. I'll first define one macro (in CL Scheme style)
; in normal code, and one "normal" function, bot of them will be
; used in code that should be prepared.
(set 'diff-squares
(lambda-macro(x y)
'prepare-time
(expand '(- (* x x) (* y y))
'x 'y)))
(set 'mirror (lambda(x)
(append x (reverse x))))
; and here is relatively complicated code that uses already
; defined macro, with some prepare-time expressions, and one
; of them even contain definition of new, recursive "prepare-time"
; macro. Prepare-time statements frequently end with !!, but not
; always.
(set 'code
'(begin (println "Eval time: starting.")
(prepare-time (println "Prepare-time: starting.")!!)
(println (diff-squares (+ 3 1) (- 3 1)))
(println (mirror '(1 2 3)))
(prepare-time (println "Prepare-time:"
(mirror '(1 0 4 0 5)))!!)
(prepare-time (set 'fib
(lambda-macro(n)
'prepare-time
(let ((en (eval n)))
(if (< en 2)
'1
(let ((n1 (- en 1))
(n2 (- en 2)))
(list '+
(fib n1)
(fib n2)))))))!!)
(prepare-time (set 'fibi (eval (fib 6)))!!)
(println "Eval time: " (prepare-time fibi) " is prepared.")
(prepare-time (println "Prepare-time: " fibi " is prepared.")!!)
(println (diff-squares (fib 3) (fib 2)))))
; TEST
(println "------------------------------------------------------")
(println "CODE: ")
(println)
(println code)
(println "------------------------------------------------------")
(println "PREPARE TIME:")
(println)
(set 'prepared-code (prepare code))
(println "------------------------------------------------------")
(println "PREPARED CODE:")
(println)
(println prepared-code)
(println "------------------------------------------------------")
(println "EVALUATION OF PREPARED CODE:")
(println)
(eval prepared-code)
(exit)
;======================================================
; RESULTS:
;------------------------------------------------------
; CODE:
;
; (begin
; (println "Eval time: starting.")
; (prepare-time (println "Prepare-time: starting.") !!)
; (println (diff-squares (+ 3 1) (- 3 1)))
; (println (mirror '(1 2 3)))
; (prepare-time (println "Prepare-time:" (mirror '(1 0 4 0 5))) !!)
; (prepare-time (set 'fib (lambda-macro (n) 'prepare-time
; (let ((en (eval n)))
; (if (< en 2)
; '1
; (let ((n1 (- en 1)) (n2 (- en 2)))
; (list '+ (fib n1) (fib n2))))))) !!)
; (prepare-time (set 'fibi (eval (fib 6))) !!)
; (println "Eval time: " (prepare-time fibi) " is prepared.")
; (prepare-time (println "Prepare-time: " fibi " is prepared.") !!)
; (println (diff-squares (fib 3) (fib 2))))
;
; ------------------------------------------------------
; PREPARE TIME:
;
; Prepare-time: starting.
; Prepare-time:(1 0 4 0 5 5 0 4 0 1)
; Prepare-time: 13 is prepared.
; ------------------------------------------------------
; PREPARED CODE:
;
; (begin
; (println "Eval time: starting.")
; (println (- (* (+ 3 1) (+ 3 1)) (* (- 3 1) (- 3 1))))
; (println (mirror '(1 2 3)))
; (println "Eval time: " 13 " is prepared.")
; (println (- (* (+ (+ 1 1) 1) (+ (+ 1 1) 1)) (* (+ 1 1) (+ 1 1)))))
; ------------------------------------------------------
; EVALUATION OF PREPARED CODE:
;
; Eval time: starting.
; 12
; (1 2 3 3 2 1)
; Eval time: 13 is prepared.
; 5
;
;
; It works.
================
launch some
1970's psychedelia and enjoy!
;===============================================================
; I like for loop. It is only one loop I can write automatically,
; for all other loops I always have to think what happens
; inside, and what is really exit condition. It seems that for
; loop somehow fit well into my intuition, and I observed the same
; on my students.
;
; On the other side, I was never quite comfortable with functions
; for random numbers, I always had to think whether upper limit
; is included or not, and what happens if I extend the segment
; or shift it. Not that it is some higher level mathematics,
; but it was never quite smooth for me.
;
; After quite a lot of programming, only yesterday I came to idea
; to use syntax for rnd resembling lovely "for" loop so I do not
; need to care about borderline cases any more. For example:
;
; if (for i 0 10 2) generates 0 2 4 6 8 and 10
; (rnd 0 10 2) should return 0, 2, 4, 6, 8 or 10
;
; if (for 3 4 0.25) generates 3, 3.25, 3.5, 3.75 and 4
; (rnd 3 4 0.25) should return 3, 3.25, 3.5, 3.75 or 4
;
; You got the idea. If "step" is 1, then it can be omitted, like in
; many for loops. But what about real numbers - is special syntax
; still required? No, for these - step is simply 0. It
; has some mathematical sense. "For" loop doesn't move if your
; step is 0, but rnd
; First, one cute set of replacements for sub, add etc.
; Usual sings for mathematically operations, followed by "."
; which should remind me on "point" from "floating point."
; It is also easier to visually parse and switch from floating point
; to integer versions and vice versa.
(set '-. sub '+. add '*. mul '/. div)
; Append for symbols.
(set 'symappend
(lambda()(sym (apply 'append
(map string $args)))))
; As said, generalized floor (and when I'm here, ceil and round
; as well). There is no reason number should be ceiled
; to some multiple of 1 and not to multiple of any other number,
; not necessarily power of 10 either. It comes handy in this
; particular case.
(dolist(j (list 'floor 'ceil 'round))
(set (symappend 'g j)
(expand (lambda(x step)
(if (= step 0)
x
(*. (j (/. x step)) step)))
'j)))
; I'm very happy with the loop above, it demostrate few nice
; features.
(println (gfloor 3.1415926 0.001)) ;3.141
(println (gceil 324.12567 (/. 100 3))) ;333.3333333
(println (ground 4.1888876 0.0125)) ;4.1875
(set 'rnd
(lambda(a b step)
(if (> a b)
(rnd b a step) ; because of specificity of Newlisp for
(begin (when (not step) (set 'step 1))
(if (and (= step 0)
(= (random) (random))) ;[?]
b
(let ((scale (+. (gfloor (- b a) step) ; [??]
step)))
(+. a (gfloor (*. scale (random))
step))))))))
; Maybe only two details deserve explanation: ? and ??.
;
; [?] Why that strange (= (random) (random))?
; It is the result of distribution of the random real numbers,
; provided by majority of programming tools, so I guess that in
; Newlisp random number is also chosen from [0,1>, if adjusted for
; offset and scale, from [a,b>.
;
; That means, in ideal case, probability that a is chosen is 0,
; but it is still possible. On the other hand, not only that
; probability that (random)=b is zero, but it is completely
; impossible.
;
; Since I want that right edge of the segment has equal chances
; as a left border, I gave it one extra chance. If function generates
; two equal random numbers - I'll count it as 1. If it doesn't,
; radnom number is determined in [0, 1>. That is the idea.
;
; [??] Why formula for scale is that complicated?
;
; Because "for i:=0 to 5 step 2" is legal, and managing that case
; complicates things a bit compared to only "for i:=0 to 4 step 2."
; TEST
(seed (date-value))
(dolist(x (list '(rnd 0 5 2)
'(rnd 3 4 0.25)
'(rnd 1 4)
'(rnd -6.666 -5.555 0)
'(rnd +2 -2 0.01)))
(println)
(dotimes(i 6)
(println x " = " (eval x))))
(exit)
After exit, I do not need ";" for comments any more.
RESULTS:
(rnd 0 5 2) = 0
(rnd 0 5 2) = 2
(rnd 0 5 2) = 2
(rnd 0 5 2) = 4
(rnd 0 5 2) = 0
(rnd 0 5 2) = 2
(rnd 3 4 0.25) = 3.25
(rnd 3 4 0.25) = 3.75
(rnd 3 4 0.25) = 3.5
(rnd 3 4 0.25) = 3.5
(rnd 3 4 0.25) = 3.25
(rnd 3 4 0.25) = 4
(rnd 1 4) = 1
(rnd 1 4) = 1
(rnd 1 4) = 4
(rnd 1 4) = 1
(rnd 1 4) = 3
(rnd 1 4) = 1
(rnd -6.666 -5.555 0) = -5.844655354
(rnd -6.666 -5.555 0) = -5.862020386
(rnd -6.666 -5.555 0) = -6.024592486
(rnd -6.666 -5.555 0) = -6.231477462
(rnd -6.666 -5.555 0) = -6.409919187
(rnd -6.666 -5.555 0) = -6.586712912
(rnd 2 -2 0.01) = 1
(rnd 2 -2 0.01) = 1.47
(rnd 2 -2 0.01) = -1.53
(rnd 2 -2 0.01) = -1.63
(rnd 2 -2 0.01) = 1.48
(rnd 2 -2 0.01) = -0.98
;===============================================================
; AVOIDING MULTIPLE COPIES.
;
; Few posts ago I discovered that functions, macros and lot of control
; structures in Newlisp copy the results of evaluation, instead of
; passing it directly. Of course, it was discovery for myself -
; experienced Newlispers knew that, and it is certainly written somewhere
; in manual. But you know how it is, the manual is the last resort,
; powerful magic that shouldn't be used unless absolutely necessary.
;
; Anycase, the fact that copies of the values are so frequent opens
; interesting and important questions about possible inefficiencies
; and techniques for their avoidance.
;
; In this post I summarize four techniques I tried for returning
; of the values from blocks and functions. They are tested on
; two implementations of the very simple function
; that for given n returns the list (1 ... n), and empty list if
; n=0. Also, if n<0 function should generate error, othwerwise
; it increases counter for 1.
;
; First implementation, f is non-recursive and uses built in
; function sequence; second implementation, g is recursive and doesn't
; use the sequence.
;
; Each of these two are tested for correctness, and then for speed of
; evaluation, for different values of n.
;
;---------------------------------------------------------------
; TECHNIQUE I. "STRAIGHT" IMPLEMENTATION
;
; It is the most natural one.
(set 'counter 0)
(set 'f (lambda(n)(if (< n 0)
(error "Negative")
(begin (inc 'counter)
(if (= n 0)
(list)
(sequence 1 n 1))))))
(set 'g (lambda(n)(if (< n 0)
(error "Negative.")
(begin (inc 'counter)
(if (= n 0)
(list)
(append (g (- n 1))
(list n)))))))
(println "======================================================")
(println "I. STRAIGHT IMPLEMENTATION.")
; Test is the function that calls f and g with various parameters,
; measures time and print results. Not really interesting,
; so I suggest you to skip over it.
(set 'test
(lambda(eval-needed)
(println)
(println "Correctness:")
(println)
(println (if eval-needed (eval (f 10)) (f 10)))
(println (if eval-needed (eval (f 10)) (f 10)))
(println)
(set 'maxf 7)
(set 'maxg 3)
(for (j 0 maxf 1)
(letn ((argument (pow 10 j))
(to-repeat (pow 10 (- maxf j)))
(t (if eval-needed
(div (mul (time (eval (f argument)) to-repeat)
1000000)
to-repeat)
(div (mul (time (f argument) to-repeat)
1000000)
to-repeat))))
(println "(f " (format "%10d" argument) ") "
(format "%12d" (div t 10)) "0 ns/list, "
(format "%8d" (div t argument)) " ns/element")))
(println)
(for (j 0 maxg 1)
(letn ((argument (pow 10 j))
(to-repeat (* (pow 10 (- maxg j)) 100))
(expr (if eval-needed '(eval (g argument)) '(g argument)))
(t (if eval-needed
(div (mul (time (eval (g argument)) to-repeat)
1000000)
to-repeat)
(div (mul (time (g argument) to-repeat)
1000000)
to-repeat))))
(println "(g " (format "%10d" argument) ") "
(format "%12d" (div t 10)) "0 ns/list, "
(format "%8d" (div t argument)) " ns/element")))
(println)))
(test nil); nil will be explained later
;---------------------------------------------------------------
; II. RETURNING VARIABLES AND EVALUATING IN CALLER ENVIRONMENT
;
; This technique I discussed on Newlisp Forum already. Idea is
; that instead of, for example, block
;
; [1] (begin ... (list 1 2 3 4))
;
; that returns (1 2 3 4) we can use
;
; [2] (eval ... (begin ... (set 'temp (list 1 2 3 4)) 'temp))
;
; On the same way, instead of
;
; [3] (set 'f (lambda() ... (list 1 2 3 4)))
;
; we should write
;
; [4] (set 'f (lambda(...) .... (set 'temp (list 1 2 3 4)) 'temp))
;
; And so forth. What was achieved? In [1] list (1 2 3 4) which
; is constructed inside begin block is not returned directly, but
; its copy. In [2] symbol temp is returned and later evaluated.
; Symbol temp is also copied, but it is - small. So, we spare
; one copy of the potentially large list. True,
;
; (set 'temp (list 1 2 3 4))
;
; maybe copy the value (1 2 3 4). If it does, then it is still only
; one copy, and typically there is more than one nested block. Second,
; some tests suggests me that Newlisp is already optimized to do
; (set 'temp <value>) without copies if <value> is temporary, i.e.
; it is not assigned to some other variable. Still, I do not know is
; it true, but even if it is not, the first advantage still remains.
(set 'f (lambda(n)(if (< n 0)
(error "Negative")
(begin (inc 'counter)
(if (= n 0)
(begin (set 'temp (list))
'temp)
(begin (set 'temp (sequence 1 n 1))
'temp))))))
(set 'g (lambda(n)(if (< n 0)
(error "Negative.")
(begin (inc 'counter)
(if (= n 0)
(begin (set 'temp (list))
'temp)
(begin (set 'temp
(append (eval (g (- n 1)))
(list n)))
'temp))))))
(println "======================================================")
(println "II. RETURNING VARIABLES AND EVALUATING IN CALLER ENVIRONMENT.")
(test true); true = needs eval in caller environment
;---------------------------------------------------------------
; III. RETURNING EXPRESSIONS AND EVALUATING THEM IN CALLER ENVIRONMENT
;
; But - if we return values in variables, and then we evaluate
; these variables - we can return expressions used for definitions
; of variables as well. It is pretty radical, and very "Lispy" idea,
; if anything is "code=data" that is. However, there is a problem
; as well: Lisp code is - ehm - list; Code that generates lists is
; not necessarily smaller than list itself - although it is almost
; certainly smaller than some large lists.
;
; Function "expand" is useful for elimination of the various local
; variables from code of the function that should be returned.
(set 'f (lambda(n)(if (< n 0)
(error "Negative")
(begin (inc 'counter)
(if (= n 0)
'(list)
(expand '(sequence 1 n 1)
'n))))))
(set 'g (lambda(n)(if (< n 0)
(error "Negative.")
(begin (inc 'counter)
(if (= n 0)
'(list)
(expand '(append (eval (g (- n 1)))
(list n))
'n))))))
(println "======================================================")
(println "III. RETURNING EXPRESSIONS AND EVALUATING IN CALLER ENVIRONMENT")
(test true)
;---------------------------------------------------------------
; IV. USING CONTEXTS
;
; In recent Newlisp versions, context variables are also returned
; by reference. So, they can be used for optimization as well, and
; they could be returned without need for eval in the caller environment.
(set 'f (lambda(n)(if (< n 0)
(error "Negative")
(begin (inc 'counter)
(if (= n 0)
(begin (set 'q:q (list))
q:q)
(begin (set 'q:q (sequence 1 n 1))
q:q))))))
(set 'g (lambda(n)(if (< n 0)
(error "Negative.")
(begin (inc 'counter)
(if (= n 0)
(begin (set 'q:q (list))
q:q)
(begin (set 'q:q
(append (g (- n 1))
(list n)))
q:q))))))
(println "======================================================")
(println "IV. CONTEXTS")
(test nil)
(exit)
;===============================================================
; RESULTS
;
; Comment or cut them out if you want to evaluate the code,
; I cannot resist this beautiful green - blue combination.
; "ns" stands for nanoseconds.
======================================================
I. STRAIGHT IMPLEMENTATION.
Correctness:
(1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)
(f 1) 1220 ns/list, 1225 ns/element
(f 10) 2420 ns/list, 242 ns/element
(f 100) 13580 ns/list, 135 ns/element
(f 1000) 132000 ns/list, 132 ns/element
(f 10000) 1312000 ns/list, 131 ns/element
(f 100000) 14970000 ns/list, 149 ns/element
(f 1000000) 155900000 ns/list, 155 ns/element
(f 10000000) 1954000000 ns/list, 195 ns/element
(g 1) 2180 ns/list, 2180 ns/element
(g 10) 18800 ns/list, 1880 ns/element
(g 100) 705000 ns/list, 7050 ns/element
(g 1000) 80390000 ns/list, 80390 ns/element
======================================================
II. RETURNING VARIABLES AND EVALUATING IN CALLER ENVIRONMENT.
Correctness:
(1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)
(f 1) 1300 ns/list, 1306 ns/element
(f 10) 1990 ns/list, 199 ns/element
(f 100) 9370 ns/list, 93 ns/element
(f 1000) 87700 ns/list, 87 ns/element
(f 10000) 722000 ns/list, 72 ns/element
(f 100000) 7380000 ns/list, 73 ns/element
(f 1000000) 72100000 ns/list, 72 ns/element
(f 10000000) 689000000 ns/list, 68 ns/element
(g 1) 3570 ns/list, 3570 ns/element
(g 10) 20000 ns/list, 2000 ns/element
(g 100) 440000 ns/list, 4400 ns/element
(g 1000) 33960000 ns/list, 33960 ns/element
======================================================
III. RETURNING EXPRESSIONS AND EVALUATING IN CALLER ENVIRONMENT
Correctness:
(1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)
(f 1) 2000 ns/list, 2008 ns/element
(f 10) 2690 ns/list, 269 ns/element
(f 100) 9580 ns/list, 95 ns/element
(f 1000) 89200 ns/list, 89 ns/element
(f 10000) 702000 ns/list, 70 ns/element
(f 100000) 7610000 ns/list, 76 ns/element
(f 1000000) 74100000 ns/list, 74 ns/element
(f 10000000) 755000000 ns/list, 75 ns/element
(g 1) 4940 ns/list, 4940 ns/element
(g 10) 41500 ns/list, 4150 ns/element
(g 100) 653000 ns/list, 6530 ns/element
(g 1000) 38600000 ns/list, 38600 ns/element
======================================================
IV. CONTEXTS
Correctness:
(1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)
(f 1) 1500 ns/list, 1501 ns/element
(f 10) 3370 ns/list, 337 ns/element
(f 100) 25260 ns/list, 252 ns/element
(f 1000) 276600 ns/list, 276 ns/element
(f 10000) 2384000 ns/list, 238 ns/element
(f 100000) 21970000 ns/list, 219 ns/element
(f 1000000) 215000000 ns/list, 215 ns/element
(f 10000000) 2162000000 ns/list, 216 ns/element
(g 1) 3900 ns/list, 3900 ns/element
(g 10) 25600 ns/list, 2560 ns/element
(g 100) 1068000 ns/list, 10680 ns/element
(g 1000) 118160000 ns/list, 118160 ns/element
; Comment.
; Look at third column, it is most important. I our example,
; straight technique I. is the best only if lists are very small.
; If lists have some 8-15 elements, then technique II. is the
; best, and technique III. is slightly worse, but if lists
; have some 12-80 elements it is also better than technique I.
; As lists grow, both techniques are 2-3 times better than I.
; Technique IV. is worse than I. in all cases.
;
; Note that factor 2-3 is not universal - it depends on the depth
; of the nested control structures. The advantage is so significant
; that in any time critical program, technique II. could be
; unavoidable.
; Both technique II. and III. are pretty safe for use, i.e.
; incidence of errors probably doesn't increase significantly.
; Technique II. uses global variable, hence, it might cause the
; problems in some cases of multiprocessing, but it is safe for
; all uniprocessing situations. Technique III. doesn't use global
; variables, so it should be always safe.
;
; One problem is evaluation in the caller environment - it requires
; lot of eval's in the source code. As it has no alternative if one
; want to maximize the speed of his code, it gives the weight to my
; proposal for new forms of lambda/eval and lambda-macro/eval expressions
; evaluating in the caller environment without need for explicit
; call of eval.
