Gensym and Genlet.

; Gensym is one of the important tools in the Lisp languages. It is
; function that returns variable. The point is - each time it is called
; it returns different variable. Gensym is typically used if one
; wants to avoid accidental name clashes while defining macros, but
; it is not its sole use.


; Newlisp has not gensym yet, but it is easy to make one. One example
; can be seen in Jeff Ober's article In defense of Newlisp, and it
; is also included in his Util library. His implementation supports
; contexts, and since I do not need contexts in this article, I'll
; define another gensym, slightly simpler, but not without some charm.


(set 'gensym-counter 0)

(set 'gensym
     (lambda(i)
       (inc gensym-counter)
       (sym (append (string i)
                    " ("
                    (string gensym-counter)
                    ". generated symbol)"))))
       

; Let us see how variables generated by our gensym look like:


(for(j 1 5)
  (println (gensym 'i)))


; Output:
;
;                     i (1. generated symbol)
;                     i (2. generated symbol)
;                     i (3. generated symbol)
;                     i (4. generated symbol)
;                     i (5. generated symbol)
;
;
; The blanks and parentheses - all that is the part of the generated
; symbol. I defined such symbol name intentionally, because it is
; impossible to accidentally use such name in programs; it must be
; generated during runtime. Also, these names are pretty descriptive,
; so they can be useful in debugging.
;
;
; I'll say that, for example, i (1. generated symbol) - is generated
; symbol that used symbol i as its base. It might have sense.
;
;
; Once generated, symbols are elements of the symbols-table until
; explicitly deleted. It is an implementation detail. Although not
; important for normal symbols, there might be millions of generated
; symbols, and it might be good to delete generated symbols immidietely
; when theye are not needed any more.


                    (for (j 1 3)
                         (set 'v (gensym 'j))
                         (println v)
                         (delete v))
  

; Topic I'd try to adress here is how to define "generated" versions
; of let and local, so programmer can write:
;
;    (genlet ((i 1)
;             (j 2))
;            (println 'i "= " i ", " 'j "= " j))
        
; While in fact, not ordinary symbols i and j are used inside
; of the genlet expression, but their gensymed versions. It is
; relatively easy to accomplish it by using powerful letex
; expression:


        (letex ((i (gensym 'i))
                (j (gensym 'j)))
                (let ((i 1)
                      (j 2))
                     (println 'i "= " i ", " 'j "= " j)))


; letex will literally replace i and j with "generated versions"
; in the inner let expression and then evaluate such, mutated inner
; expression.
;
; Output is:
;
; i (9. generated symbol)= 1, j (10. generated symbol)= 2
;
; As it can be seen, really, not i and j, but their "gensymed"
; versions are actually used. Each time this block is evaluated,
; different version is used.
;
;
; However, it becomes more complicated if I want to delete
; generated symbols. And I must do that, because if gensym is
; in some large loop, it could easily generate millions of symbols,
; and finally exhaust memory.


(letex ((i (gensym 'i))
        (j (gensym 'j)))
       (first (list (let ((i 1)
                          (j 2))
                         (begin
                            (println 'i "= " i ", " 'j "= " j)))
                   
                    (begin (delete 'i)
                           (delete 'j)))))


; With this construction I ensure that inner let expression is
; evaluated, after that gensymed variables are deleted, and finally,
; the result of the inner let expression is returned as result.
;
;
; This is how macro that "expands" into expression above looks
; like. I'll use wherex, which is inverse letex I defined few
; posts earlier, so I'll load my library from Internet. The
; definition of genlet is technical and not very interesting,
; so you can skip it.

(load "http://www.instprog.com/Instprog.default-library.lsp")

(set 'genlet
  (lambda-macro(head)
    (let ((body (args)))
         (wherex
         
                 (letex H1          
                     (first (list (let H2   
                                       H3)
                                  H4)))
                            
         ; where
                 
                 ((H1 (map (lambda(x)
                             (list (nth 0 x)
                                   (list 'gensym
                                         (list 'quote (nth 0 x)))))
                           head))
                           
                  (H2 head)
                  
                  (H3 (cons 'begin body))
                  
                  (H4 (cons 'begin (map (lambda(x)
                                          (list 'delete
                                                (list 'quote
                                                       (nth 0 x))))
                                         head))))))))

; Does it work?


         (genlet ((i 1)
                  (j 2))
                 (println 'i "= " i ", " 'j "= " j))

; Output:
;
;      (13. generated symbol)= 1, j (14. generated symbol)= 2
;
; It works.
;
; And what happens if I do something like


              (genlet ((i 1))
                      (genlet ((i 2))
                          (println 'i "= " i))
                      (println 'i "= " i))
       
; Output:
;
; i (15. generated symbol) (16. generated symbol)= 2
; i (15. generated symbol)= 1    
;
;
; What is
;
;    i (15. generated symbol) (16. generated symbol)?
;
; It is generated symbol, that uses for its basis generated symbol
; i (15. generated symbol), that uses i for its basis symbol i.
;
; Another test:


               (println= (genlet ((i 7))
                            (genlet ((j 8))
                               (* i j))))
               
; Output:

;      (genlet ((i 7)) (genlet ((j 8)) (* i j)))=56;
;
; Again, everything works.
;
; If you do have problems with understanding this code, don't
; let this discourage you. It is really complicated, and it is
; enough to remember that some genlet is defined here - and come
; back if you find you might need it.

; Next time - genlocal!



                          (exit)

No comments:

Post a Comment