Eval and Anti-eval.

;---------------------------------------------------------------
; I again need some functions and macros I already defined.
; For the rest of the text see bellow.

(set 'macro
    (lambda-macro()
        (eval (append '(lambda-macro) (args)))))
        
(set 'expression-and-value
    (macro(expression-and-value-arg)
        (list '->
              expression-and-value-arg
              (eval expression-and-value-arg))))

(set '§ (macro()
         (doargs(§arg)
           (println (eval (list 'expression-and-value §arg))))))



;---------------------------------------------------------------
;
;                  Eval and Anti-eval.
;
; Quote and eval can be seen as inverse functions;
; But, they are not exactly that:

(set 'x "I am the value of x")

         (println (= x (quote (eval x))))  ; -> nil! UGLY! UGLY!
         (println (= x (eval (quote x))))  ; -> true

; What really happens?

(§ (quote (eval x)))  ;(-> (quote (eval x)) (eval x))
(§ (eval (quote x)))  ;(-> (eval (quote x)) "I am the value of x")



; Say we want real inverse of eval, i.e. function anti-eval
; such that everything works as expected.


                 (set 'anti-eval
                      (macro(argument)
                            (if (and (list? argument)
                                     (not (empty? argument))
                                     (= (first argument) 'eval))
                                (eval (first (rest argument)))
                                argument)))
                      

;Tests:

                     (§ (anti-eval (eval x)))
                     (§ (eval (anti-eval x)))

                     (§ (anti-eval (eval (quote (+ 2 3)))))
                     (§ (eval (anti-eval (quote (+ 2 3)))))

                     (§ (eval (anti-eval (eval (anti-eval x)))))
                     (§ (anti-eval (eval (anti-eval (eval x)))))

;Results:

  ;(-> (anti-eval (eval x)) "I am the value of x")
  ;(-> (eval (anti-eval x)) "I am the value of x")

  ;(-> (anti-eval (eval (quote (+ 2 3)))) (+ 2 3))
  ;(-> (eval (anti-eval (quote (+ 2 3)))) (+ 2 3))

  ;(-> (eval (anti-eval (eval (anti-eval x)))) "I am the value of x")
  ;(-> (anti-eval (eval (anti-eval (eval x)))) "I am the value of x")

;So far, so good.

;And even this one:

                     (§ (eval (anti-eval (anti-eval (eval x)))))
                     (§ (anti-eval (eval (eval (anti-eval x)))))

;(-> (eval (anti-eval (anti-eval (eval x)))) "I am the value of x")
;(-> (anti-eval (eval (eval (anti-eval x)))) "I am the value of x")



; But I wouldn't be surprised it is broken for more complicated
; expression. I'll keep an eye on it. But this is only blog.

; Is there any practical use of anti-eval? I don't know,
; but it would be strange that there is no use whatsoever.

Evaluation of Large Expressions in Newlisp.

; This time I'll try different eval benchmark; instead of
; evaluating simple expressions many time, I'll write the program
; that construct large s-expression and measures the time of its
; evaluation

(setq large-s-expression 1)


(setq counter 1)
(do-while (< counter 1000000)
    (setq counter (+ counter 1))
    (setq large-s-expression
          (list 'eval
                (list 'quote
                      (list '+ counter large-s-expression))))
    (when (= (% counter 100) 0)
          (println counter
                   " > "
                   (time (eval large-s-expression)))))

; This is how those z that are evaluated
; look like for counter=2,3,...

;(eval (quote (+ 2 1)))
;(eval (quote (+ 3 (eval (quote (+ 2 1))))))
;(eval (quote (+ 4 (eval (quote (+ 3 (eval (quote (+ 2 1)))))))))

; 100 > 0
; 200 > 15
; 300 > 15
; 400 > 31
; 500 > 46
; 600 > 78
; 700 > 109
; 800 > 140
; 900 > 234
; 1000 > 281
; 1100 >

; ERR: call stack overflow in function eval : quote
;
; Newlisp returns to REPL after that stack overflow. The speed
; is satisfactory, although it seems it is not stable, in some
; executions I got numbers like 900 ms for evaluation of the
; expression with 1000 evals.  

; Also, stack overflow happens earlier than in other Scheme
; or Lisp implementations. Clisp and PLT stack overflow
; happens for counter = about 4000, Lispworks and Allegro (free
; editons somewhere near 50 000, while Petit Chez Scheme works
; happily for counter > 10 000 000 and more. Stack overflow
; results in crash of PLT IDE and Chez Scheme interpreter
; respectively.

; However, that stack overflow in Newlisp is not the result of
; eval and quote, because it happens even earlier if eval and
; quote are replaced with sin and cos.

; Conclusion: for evaluation of very large expressions, Newlisp
; is satisfactory, but there is a lot of room for improvement.

Embedding Blocks into Functions.

; I'm trying to "embed" blocks into functions or macros, they
; can be useful for calls similar to
;
; (help function)
; (test f)
;
; etc. There are lot of ways it can be done, for example, using
; contexts. Or closures where available. Or hash tables containing
; functions for tests and help. But i tried this one.

;---------------------------------------------------------------
; I want to use "function" and "macro" as keywords
; instead of "lambda" and "lambda-macro"

(set 'function
    (lambda-macro()
        (eval (append '(lambda) (args)))))
        
(set 'macro
    (lambda-macro()
        (eval (append '(lambda-macro) (args)))))

; Tests: later

;---------------------------------------------------------------
; One macro useful for printing. I learnt that I almost always
; use output in this form. In the same time, test for "macro"

(set 'expression-and-value
    (macro(x)
        (list '-> x (eval x))))
        
; Tests:

                    (println expression-and-value)
                    (println (expression-and-value (+ 3 3)))

; Results:

;(lambda-macro (x) (list '-> x (eval x)))
;(-> (+ 3 3) 6)

;---------------------------------------------------------------
; As expression-and-value is used almost exclusively in print
; and it is frequently used, it justifies definition of one
; special print functions, with a very short name.
; I'll use this name: §

(set '§ (macro()
         (doargs(x)
           (println (eval (list 'expression-and-value x))))))


; Test (it is enough to test §)

                                (set 'z 1)
                                (§ z (sin z) (+ z 4))

; Result:

;(-> z 1)
;(-> (sin z) 0.8414709848);
;(-> (+ z 4) 5)

;---------------------------------------------------------------
; I define block as non-empty list. Intention is to make
; generalization of begin-block. Following functions are very
; simple and they do not require any comments.

(set 'block?
     (function(candidate)
              (if (list? candidate)
                  (not (empty? candidate)))))

; Tests:

        (§ (block? '(hello-world (println "hello, world"))))
        (§ (block? '()))
        (§ (block? 3))
        (§ (block? '(nil print)))

; Results:

;(-> (block? '(hello-world (println "hello, world"))) true)
;(-> (block? '()) nil)
;(-> (block? 3) nil)
;(-> (block? '(nil print)) true)

;---------------------------------------------------------------
(set 'get-block-name
     (function(some-block)
              (if (not (block? some-block))
                  (throw-error (list "get-block-name applied on non-block"
                                     some-block))
                  (first some-block))))

;Tests

          (§ (get-block-name '(hello (println "hello"))))

;(§ (get-block-name '()))
;(§ (get-block-name 3))

; Results:

;(-> (get-block-name '(hello (println "hello"))) hello)
; other two really return excpected error

;---------------------------------------------------------------
(set 'quoted-block?
     (function(candidate)
         (if (quote? candidate)
             (block? (eval candidate)))))
             
; Tests:

                (§ (quoted-block? ''(hello (println "hello!"))))
                (§ (quoted-block? ''()))
                (§ (quoted-block? '3))
                (§ (quoted-block? ''(nil print)))

; Results:

;(-> (quoted-block? ''(hello (println "hello!"))) true)
;(-> (quoted-block? ''()) nil)
;(-> (quoted-block? '3) nil)
;(-> (quoted-block? ''(nil print)) true)

;---------------------------------------------------------------

(set 'begin-block-from-any-block
     (function(some-block)
              (append '(begin)
                      (rest some-block))))

; Test:

                    (§ (begin-block-from-any-block
                                  '(hello (println "Hello!"))))

; Result: works OK

;---------------------------------------------------------------

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

; Tests:

          (§ (get-block-from-list-containing-quoted-blocks
                  'test
                  (list ''(wrong) '(test) 0 ''(test) '(false))))
          (§ (get-block-from-list-containing-quoted-blocks
                  'test
                  (list '(wrong) '(right) 0 '(false))))
          (§ (get-block-from-list-containing-quoted-blocks
                  'test
                  (list)))
          (§ (get-block-from-list-containing-quoted-blocks
                  'test
                  '()))

; Results: everything works OK

;---------------------------------------------------------------

(set 'evaluate-block-from-list-containing-quoted-blocks
     (function (block-name list-containing-quoted-blocks)
               (eval (begin-block-from-any-block
                         (get-block-from-list-containing-quoted-blocks
                              block-name
                              list-containing-quoted-blocks)))))

;---------------------------------------------------------------
; OK, everything is ready for a final test.
; I'll define one cute function, "integer-quote" with two cute
; blocks, "help" and "test," and see what happens.

(set 'integer-quote
    (macro(i expr)
    '(help
        (println "\nInteger-guote help:")
        (println "  Syntax: (integer-quote <integer> <expression>)")
        (println "  Example: " (expression-and-value (integer-quote 2 x)))
        (println "  Example: " (expression-and-value (integer-quote -3 x)))
        (println "  Example: " (expression-and-value (integer-quote 0 x)))
        (println "End of integer-quote help.\n"))
    '(test
        (println "\nInteger-quote test:")
        (if (= (integer-quote 2 x) '(quote (quote x)))
            (println "  First test passed.")
            (println "  First test failed."))
        (if (= (integer-quote -3 x) '(eval (eval (eval x))))
            (println "  Second test passed.")
            (println "  Second test failed."))
        (if (= (integer-quote 0 x) 'x)
            (println "  Third test passed.")
            (println "  Third test failed."))
        (println "End of quote-eval test.\n"))
    (cond
        ((= i 0) expr)
        ((> i 0) (eval (list 'integer-quote
                                (- i 1)
                                (list 'quote expr))))
        ((< i 0) (eval (list 'integer-quote
                                (+ i 1)
                                (list 'eval expr)))))))
                                
;---------------------------------------------------------------
; Tests

(println "\n\n\nOK, let me see how it works.")

(evaluate-block-from-list-containing-quoted-blocks 'help integer-quote)
(evaluate-block-from-list-containing-quoted-blocks 'test integer-quote)
(§ (integer-quote -7 (i-o-lets-go!)))

;Results

;Integer-guote help:
;  Syntax: (integer-quote <integer> <expression>)
;  Example: (-> (integer-quote 2 x) (quote (quote x)))
;  Example: (-> (integer-quote -3 x) (eval (eval (eval x))))
;  Example: (-> (integer-quote 0 x) x)
;End of integer-quote help.

;Integer-quote test:
;  First test passed.
;  Second test passed.
;  Third test passed.
;End of quote-eval test.

;(-> (integer-quote -7 (i-o-lets-go!))
;(eval (eval (eval (eval (eval (eval (eval (i-o-lets-go!)))))))))

;Everything works fine.
;Sure, i can use shorter names.

Starting with Newlisp.

Starting with Newlisp
I decided that in the next few months, and possibly longer I'll use Newlisp programming language. The main reason is that I recognized some important features consistent to the main design goals of Lisp, and they are, I believe, to provide powerful and abstract features which make hard algorithmic problems, especially AI problems easier to solve. In last few decades, it appears that Lisp dialects neglected development of the core language, instead, the efforts seem to be invested mostly in producing implementations more suitable for the practical use.

Unrestricted Eval.

The "eval" function is the cornerstone of the "code=data" paradigm Lisp is known for; if code is treated as data, it means it can be processed and evaluated during runtime. Evaluation of the code is provided through application of the function "eval" on the peace of code. Somehow surprisingly, both Common Lisp and Scheme implement somehow restricted version of eval, i.e. one that does not see "local variables". Newlisp's eval is not restricted on that way.

(let ((a 1)
      (b 2))
     (println (eval '(+ a b))))
This code evaluates to 3 in Newlisp, while in other Lisp dialects this code produces error "undefined/ unbound variable." Some Lisp users claim that unrestricted eval prevents some optimizations during compiling of the code. Maybe - but claim that some abstract feature should be dismissed because it is slow is strangely radical and unjustified: one can simply use it when time is not critical, and avoid it if it is. I do not think it should be accepted as normal that languages like Python have more powerful "eval" than Common Lisp or Scheme.

First Class Macros.

Also, Newlisp has simple, yet powerful macros. In Newlisp, macros are just like functions, except that they accept unevaluated arguments. They are "first class citizens", the values that can be used in expressions and be result of the evaluation of expressions; they can be passed as arguments and returned as results of the functions - or other macros. Newlisp macros are easier to write because they can directly perform given tasks, instead of generating code that will perform that task. As you can see in following example, there is no need for backquotes and commas.

(set 'my-print (lambda-macro(x)
                 (print "(-> " x " " (eval x )")")))
(my-print (+ 3 7))

; (-> (+ 3 7) 10)
Old Lisps, in 1970's had that feature. It was named fexpr but it was dropped in the favor of macros as we know them these days.

Pitman's Criticism of Fexpr's.

According to Wikipedia,
At the 1980 Conference on Lisp and Functional Programming, Kent Pitman presented a paper "Special Forms in Lisp" in which he discussed the advantages and disadvantages of macros and fexprs, and ultimately condemned fexprs. His central objection was that, in a Lisp dialect that allows fexprs, static analysis cannot determine generally whether an operator represents an ordinary function or a fexpr — therefore, static analysis cannot determine whether or not the operands will be evaluated. In particular, the compiler cannot tell whether a subexpression can be safely optimized, since the subexpression might be treated as unevaluated data at run-time."
This is similar argument as one for restriction of "eval." Not only that dismissing powerful feature because it cannot be optimized is unjustified decision but in this particular case, it is not even true that fexpr's cannot be optimized. If Lisp fexpr's (Newlisp macros) are written in the same style as equivalent Lisp macro's and fexpr calls are inlined, then they provide exactly the same opportunity for optimization as Lisp macro calls do. Common Lisp macro call evaluation is separated in two phases - macroexpansion, and evaluation of the macroexpanded code. Usually, although not always, macroexpansion does not depend on any value known only in runtime, hence macroexpansion can be performed during compile time. But in such cases, parts of the equivalent and inlined fexpr call can be evaluated and optimized during compiling phase on the same way. Newlisp implementation doesn't do it, it is an interpreter - no problem for me, I tend not to care for anything compile time - but such optimizations are, however, possible.

Another reason Pitman prefers Lisp macros over Lisp fexprs is that he wants some kind of automatic analysis of the code. For example, let's say that one wants to define Lisp macro (USED-ON-PARTICULAR-WAY [variable] [expression]) which returns 1 if, well, if [variable] is used on the particular way in [expression], and 0 if it is not. If [expression] contains macros - these macros can be expanded in USED-ON-PARTICULAR-WAY (using Common Lisp's MACROEXPAND) and analyzed so USED-ON-PARTICULAR-WAY can find the answer it needs. It cannot be done if [expression] contains fexprs instead of macros; fexprs are like black boxes, and USED-ON-PARTICULAR-WAY cannot see what happens inside them. Pitman is partially right. Partially, because it is not excluded that [variable] is, however, used on particular way during macroexpansion phase, and it is not visible in macroexpanded code! Macroexpanded code does not necessarily contain all relevant information. But if we suppose that automatic analysis of macroexpansion phase is not needed, whatever the reason, yes, he is right. However, Newlisp macros solve even that problem, and turn to be even more "transparent" and suitable for the kind of analysis he advocates. Here is why:

Functions and Macros are Their Definitions.

In Common Lisp and Scheme, the functions are special type of values resulting from evaluations of their definitions. They can be used as values and applied, but their definitions are not accessible, and they cannot be analysed and mutated during runtime. In Newlisp, functions are not results of evaluation of the definitions, they are exactly same thing as their definitions. Hence, they can be analyzed (and mutated) during runtime. And exactly the same is true for Newlisp macros. The following example demonstrates that feature.

(set 'my-print (lambda-macro(x)
                 (print "(->" x " " (eval x ) ")" )))

(set 'replace-print-with-println
      (lambda-macro(f)
         (set-nth 1
                 (eval f)
                 (append '(println) (rest (nth 1 (eval f)))))))

(println my-print)
(replace-print-with-println my-print)
(println my-print)

; Output:                                                      
;(lambda-macro (x) (print "(->" x " " (eval x) ")"))           
;(lambda-macro (x) (println "(->" x " " (eval x) ")"))         
So, yes, Newlisp macros and even Newlisp functions can be analyzed by other functions and macros, and that is substantial improvement in the spirit of the "code=data" paradigm.

Real World Problems.

Newlisp is a new language, developed by one man, American psychologist and computer scientist Lutz Mueller and it has small users and contributors community so it has less features than some mature Common Lisp and Scheme implementations. However, neither one of the missing features seems to be essential for my programs, and hopefully, if the language itself will be successful, Newlisp libraries and native features will grow. Although we have seen that Newlisp surpasses other Lisp dialects in expressive power of the core language, author says that the language is developed primarily "to be useful for solving real world problems" and that "things like regular expressions, network functions and support for popular protocols like XML or HTTP are all built in to Newlisp without the need of external libraries." Some users of Newlisp say that they switched on Newlisp exactly because of that, not because of abstract features I listed.

Memory Management.

My only concern is that Newlisp does not allow that data structures share common parts in memory. Other Lisp users frequently mention that as a weakness, and it seems so on the first sight. However, at this moment, I'm not able to estimate all consequences of that policy, so I rely on expectation that Mueller who was able to single-handedly improve basics of Lisp didn't made significant mistake in this part of the language. I hope that I'll learn how to compensate for that limitation. One possibility might be in exploitation of the facts that data structures can, however, contain same symbols, and symbols can be used as references of data structures.

(set 'x (list 1))
(set 'a 'x)
(set 'b 'x)
(set-nth 0 (eval a) 2)
(print-expr-and-value-lns a b (eval a) (eval b))

;Results in:

;(-> a x)
;(-> b x)
;(-> (eval a) (2))
;(-> (eval b) (2))
I'll certainly come back to that topic in following months.