Symbols as Sexprs and Hygienic Fexprs.

; During last year of use of Newlisp I changed my opinion about
; one important thing: encoding information in symbols.

; Initially, I thought it is mistake, or attempt for escape from
; dry, but essential Lisp syntax, known in most of Lisp languages.
; See, for example, apostrophe - or even worse, "loop" in some
; dialects. I criticized my Newlisp coleague Cyril Slobin
; who did it once.

; However, soon I concluded that there is no good alternative for
; encoding of information in symbols. For example, in one of the
; first posts here, I tried to define operators similar to +=,
; -=, *= etc in C. If you didn't used these operators, x+=1 is
; same thing as x=x+1; x*=2 is same as x=x*2.
; What does it mean, encoding information in symbols? Take a look
; on C operators
;                          +=, -=, *=,
; again. The names of these operators are not *just names*, but also
; descriptions of the operators. The programmer who learns C probably
; mentally parse these names while programming for some time, until he
; automatizes use of the operators.
; If these operators are defined in Newlisp program, then the
; names must be defined by program as well. And what should be the
; names of the operators defined with
;          (operator1 x y) <=> (setq x (+ x y))
;          (operator2 x y) <=> (setq x (- x y))
;          ...?
; From my point of view, natural choice of the names could be
; setq+ and setq-.
; Another example of generated symbol names I used is in post
; in which I defined functions for prevention of accidental name
; clashes. If function f is, for example, defined with
;                  (set 'f (lambda(x)(x y)))
; then (protect1 'f '(x y)) replaced definition of f with
;                    (lambda(f.x)(f.x f.y))
; and later, I replaced it with
;                  (lambda([f.x])([f.x] [f.y]))
; How bracket get into combination? Because, I have find that
; I might need to distinguish names like
;                    f.[x.1] and [f.x].1
; At this point, my variable names started to look increasingly
; like s-expression, so I assumed that it might be useful to
; assume that our usual one-word symbols as just special cases
; of symbols in the form of s-expressions.
; Newlisp allow us to use "ilegal" symbol names, so theoretically,
; I can use symbols of the form (f x) - with blanks and parenthesis
; as characters - but such symbols cannot be printed out and readed
; again. So, symbols - sexprs must use different forms of parentheses
; and delimiters.

; Unfortunately, dot is not good choice for delimiter, because dot
; can be part of the number, so [f.1.3] is ambigious - is it (f 1.3),
; or (f 1 3)?
; Also, square and curly brackets have special meanings in Newlisp
; syntax, so more exotic choices are necessary.

; In following part of the code, I'll show how I defined symbols in
; the form of s-expression and how these are used to redefine functions
; protect1 (fast - and protecting from practically all kinds of accidental
; variable clashes) and protect2 (slow - protecting from accidental
; variable name clashes in some rare, in Newlisp practice unknown.
; but still possible cases.)
; Details are described in my previous posts in series
; "Don't fear dynamic scope."
; "Don't fear dynamic scope (2)."

; First, we'll define equivalents in one, centralized place

(set 'left-parenthesis-equivalent ".<.")
(set 'right-parenthesis-equivalent ".>.")
(set 'blank-equivalent "___")
(set 'apostrophe-equivalent "`")
(set 'quotation-mark-equivalent "~")

; Next, we'll define two pairs of functions for conversion from
; s-expression to string and vice versa.

(set 'symbol-to-sexpr
       (setq S (string S))
       (setq S (replace left-parenthesis-equivalent S "("))
       (setq S (replace right-parenthesis-equivalent S ")"))
       (setq S (replace blank-equivalent S " "))
       (setq S (replace apostrophe-equivalent S "'"))
       (setq S (replace quotation-mark-equivalent "\""))
       (eval-string (append "'" S))))

(set 'sexpr-from-symbol symbol-to-sexpr)

(set 'sexpr-to-symbol
       (setq L (string L))
       (setq L (replace "(" L left-parenthesis-equivalent))
       (setq L (replace ")" L right-parenthesis-equivalent))
       (setq L (replace " " L blank-equivalent))
       (setq L (replace "'" L apostrophe-equivalent ))
       (setq L (replace "\"" L quotation-mark-equivalent ))
       (sym L)))
(set 'symbol-from-sexpr sexpr-to-symbol)

; Let us see on example, how these functions work:

(println (symbol-from-sexpr '(* (+ x y) (- x y))))

;           .<.*___.<.+___x___y.>.___.<.-___x___y.>..>.
; Pretty much like normal s-expression, while < and > pretend to be
; parenthesis, and exotic dots pretend to be blank characters.
; Now, I'll define "protected version" of function set:
;   * (set-protected1 function/macro-name original-code variables)

(set 'set-protected1
  (lambda(function/macro-name definition-code variables)
    (set function/macro-name
      (eval (list 'letex
                  (map (lambda(x)
                         (list x
                               (list 'quote
                                        (list function/macro-name

; Example:

(set-protected1 'f (lambda(x y z)(x y z)) '(x z))

(println f) ;=> (lambda (.<.f___x.>. y .<.f___z.>.)
            ;              (.<.f___x.>. y .<.f___z.>.))

; Similarly, the version protect1 that protects the functions
; that already exist:

(set 'protect1 (lambda(function/macro-name variables)
                  (set-protected1 function/macro-name
                                (eval function/macro-name)

; In next step, I'll use set-protected1 and protect1 to define -
; protected versions of set-protected1 and protect1.

((copy set-protected1) 'set-protected1
                        '(function/macro-name definition-code
((copy protect1) 'protect1 '(function/macro-name variables))

; In following step, I'll define set-protect2 and protect2. These
; two functions should be able to protect functions even from the
; most demanding funarg problems. Details are explained in "Don't
; fear dynamic scope." articles, links are above.  
(set 'set-protected2
  (lambda(function/macro-name definition-code variables)
    (set function/macro-name
      (expand (lambda-macro()
                        (symbol-from-sexpr (list 'function/macro-name
                                                 (inc counter)))))
                    (set-protected1 name-and-counter
                    (first (list (eval (cons name-and-counter
                                 (dolist(i 'variables)
                                    (delete (symbol-from-sexpr
                                              (list name-and-counter
                                 (delete name-and-counter)))))
               'function/macro-name 'definition-code 'variables))))
; set-protected2 is the most important function in this post.
; In this version it is more than twice shorter and, I hope,
; simpler than in last version.

; Example of set-protected2

(set-protected2 'f (lambda(x y z)(x y z)) '(x z))
(println f)

; (lambda-macro ()
;  (let ((name-and-counter (symbol-from-sexpr (list 'f (inc counter)))))
;   (set-protected1 name-and-counter (lambda (x y z) (x y z)) '(x z))
;   (first (list (apply name-and-counter $args)
;     (dolist (i '(x z))
;      (delete (symbol-from-sexpr (list name-and-counter i))))
;     (delete name-and-counter)))))

; Similarly, the version protect2 that protects the functions
; and macros that already exist:
(set 'protect2
     (lambda(function/macro-name variables)
        (set-protected2 function/macro-name
                        (eval function/macro-name)

; In next step, I'll use protect1 to define -
; protected versions of set-protected2 and protect2.

(protect1 'set-protected2 '(function/macro-name definition-code
                            variables counter name-and-counter i))
(protect1 'protect2 '(function/macro-name variables))

; Finally, hard example of funarg problem: recursive fexpr hard-example
; call itself, passing the function encapsulating one free variable
; from one instance of the hard-example to another. We'll see whether
; protect2 will protect it.
; If (hard-example (lambda(x)x)) returns 1 2 3 1 2 3 then free variable
; is overshadowed with same variable in other instance.
; If (hard-example (lambda(x)x)) returns 1 1 1 1 2 3 then it is not
; overshadowed.

(define-macro (hard-example f)
      (for(i 1 3)
         (unless done          ; avoiding infinite
             (set 'done true)  ; recursion
             (hard-example (lambda(x)i)))  
                               ; One recursive call with function
                               ; (lambda(x)i)

         (println i " =>" (f i)))) ; which i will be printed?
                                   ; i=1 2 3 means inner is overriden

; First, without protection:

(set 'done nil)
(hard-example (lambda(x)x))
; 1 =>1
; 2 =>2
; 3 =>3
; 1 =>1
; 2 =>2
; 3 =>3

; Overshadowing happened.

; Then, after protection:

(set 'done nil)
(protect2 'hard-example '(f i x))
(hard-example (lambda(x)x))

; 1 =>1
; 2 =>1
; 3 =>1
; 1 =>1
; 2 =>2
; 3 =>3

; Overshadowing prevented.

; Finally, we'll take a look whether all variables intended to
; be temporary, like .<.hard-example___1.>. etc. are deleted.

(dolist(i (symbols))
  (if (starts-with (string i) left-parenthesis-equivalent)
      (println i)))
; .<.*___.<.+___x___y.>.___.<.-___x___y.>..>.
; .<.f___x.>.
; .<.f___z.>.
; .<.protect1___function/macro-name.>.
; .<.protect1___variables.>.
; .<.protect2___function/macro-name.>.
; .<.protect2___variables.>.
; .<.set-protected1___definition-code.>.
; .<.set-protected1___function/macro-name.>.
; .<.set-protected1___variables.>.
; .<.set-protected1___x.>.
; .<.set-protected2___counter.>.
; .<.set-protected2___definition-code.>.
; .<.set-protected2___function/macro-name.>.
; .<.set-protected2___i.>.
; .<.set-protected2___name-and-counter.>.
; .<.set-protected2___variables.>.
; Yes, they are deleted.
; Another test, this one taken from recent John Shutt's disertation
; on Kernel programming language.

(define y 3)
(set 'f (lambda (x) (+ x y)))
(set 'g (lambda (y) (+ 1 (f y))))
(println (g 5))                     ;=> 11

; This code in lexically scoped Lisp evaluates to 9. In dynamically
; scoped Lisp it evaluates to 11. If you are surprised with 11,
; that means you didn't recognized that y from definition of g will
; overshadow top level y during evaluation of (f y). But - it will.
; If you want to use different objects, you have to use different
; names; and, if it is boring to invent new names for bounded variables,
; set-protected (both versions) will do that for you:

(define y 3)
(set-protected2 'f (lambda (x) (+ x y)) '(x))
(set-protected2 'g (lambda (y) (+ 1 (f y))) '(y))
(println (g 5))     ;=> 9


; In further posts, I'll explore that idea of symbols as sexprs
; deeper.



  1. I see what you were asking about brackets for now! amazing stuff...


  2. Thanx cormullion. On the way of development, I also accidentally ruined println.supressed - when I replaced it with [println.supressed].

    But I experimented for some time until I discovered that these characters: ¨ and ˙ are relatively readable and relatively well supported by all kinds of consolas, web browsers, text editors, and they are unlikely to occur accidentally in programs.