Exploring The References.

;===============================================================
; Programming languages differ in the memory management systems
; they use. The Newlisp has its own, original system named ORO -
; One Reference Only, which is something in between manual
; memory management and garbage collection. In this post I
; explore use of the references inside of ORO.
;
; The "references" are the symbols with special names,
; "reference 1", "reference 2" ... (without quotes). Idea is,
; that sometimes, instead of storing values in the variables,
; the values can be stored in "references". Because references
; take constant space in memory, they can be copied faster than
; large values, and also, many variables can evaluate to same
; reference.
;
;                        NOW IT IS LIKE THIS:
;
;                +---------+             +---------+
;                |         |           \ |         |
;                |    X    |------------>|   317   |
;                |         |           / |         |
;                +---------+             +---------+
;
;
;                +---------+             +---------+
;                |         |           \ |         |
;                |    Y    |------------>| (1 7 2) |
;                |         |           / |         |
;                +---------+             +---------+
;
;
;                +---------+             +---------+
;                |         |           \ |         |
;                |    Z    |------------>| (1 7 2) |
;                |         |           / |         |
;                +---------+             +---------+
;
;                 VARIABLES                VALUES
;
;
;                         I WANT THIS ALSO:

;
;    +---------+                                     +---------+
;    |         |                                   \ |         |
;    |    X    |------------------------------------>|   317   |
;    |         |                                   / |         |
;    +---------+                                     +---------+
;
;
;    +---------+             +---------+             +---------+
;    |         |           \ |         |           \ |         |
;    |    Y    |------------>| ref. 1  |------------>| (1 7 2) |
;    |         |           / |         |           / |         |
;    +---------+             +----A----+             +---------+
;                                /|\
;                                /
;    +---------+               ,'
;    |         |          _,,-'
;    |    Z    |--------''
;    |         |
;    +---------+
;
;    VARIABLES              REFERENCES                  VALUES
;
; Picture above is made with Jave editor, http://www.jave.de/
;
; Let's start with code, the examples will explain the purpose
; if reader is in doubt.
;
;---------------------------------------------------------------
; REFERENCE-COUNTER
;
; Global variable containing number of already defined references.
; Used internally by reference. The largest number is
; 9223372036854775807. Hence, program can reference correctly for
; limited but very long time, i.e. millions of years with current
; computer speed.

(set 'reference-counter 0)

;---------------------------------------------------------------
; REFERENCE
;
; (reference <expr>) =
;    previously unused symbol of the form "reference 1", "reference 2"
;    etc is created; its value is initalized to result of the evaluation
;    of <expr>. The reference is returned as the result of the function
;    call (reference <expr>).

(set 'reference
      (lambda(reference-value)
          (inc 'reference-counter)
          (set 'new-reference
               (sym (append "reference " (string reference-counter))))
          (set new-reference reference-value)
               new-reference))

; EXAMPLES

(println "\nREFERENCE EXAMPLES ---------------------------------")

(println (reference nil))         ;reference 1
(println (eval (reference nil)))  ;nil
(set 'z (reference (list 1 2 3)))
(println z)                       ;reference 3


;---------------------------------------------------------------
; REFERENCE?
;
; (reference? <expr>) = true if <expr> EVALUATES to reference
;                       nil otherwise

(set 'reference?
     (lambda(arg)
        (and (symbol? arg))
             (starts-with (string arg) "reference " )))
             
; EXAMPLES:

(println "\nREFERENCE? EXAMPLES --------------------------------")

(println (reference? (list 1 2 3)))             ; nil
(println (reference? (reference (list 1 2 3)))) ; true
(println (reference? z))                        ; true


;---------------------------------------------------------------
; DEREFERENCE
;
; (dereference <expr>) =
;    if <expr> evaluates to reference:         that reference
;    if <expr> doesn't evaluate to reference:  error
;
; Usage note: dereference is frequently used in combination with eval.
; See example bellow. That eval cannot be integrated in DEREFERENCE
; because in that case, COPY of the value stored in the reference
; would be returned, and it ruins main purpose of the references,
; to avoid making copies.

(set 'dereference
     (lambda-macro()
        (if (reference? (eval (first $args)))
            (eval (first $args))
            (throw-error (append "(dereference "
                                 (string (first $args))
                                 ") error: argument doesn't"
                                 " evaluate to reference: "
                                 (string (eval (first $args))))))))

; EXAMPLES

(println "\nDEREFERENCE EXAMPLES -------------------------------")

(set 'Borg (reference (list 1 2 3)))
(set 'Locutus Borg)

(println (eval (dereference Borg)))        ; (1 2 3)
(println (eval (dereference Locutus)))     ; (1 2 3)

(push 40 (eval (dereference Locutus)))
(println (eval (dereference Borg)))        ; (40 1 2 3)
(println (eval (dereference Locutus)))     ; (40 1 2 3)

;---------------------------------------------------------------
; DEREFERENCE-IF-NEEDED

; (dereference-if-needed <expr>) =
;    if <expr> evaluates to reference: that reference
;                                else: quoted result of
;                                      evaluation of <expr>
;
; Purpose: to be able to treat references and other values uniformly,
; i.e (eval (dereference-if-needed x)) can replace x.

(set 'dereference-if-needed
     (lambda-macro()
        (if (reference? (eval (first $args)))
            (eval (first $args))
            (eval (list 'quote (first $args))))))
                 
; EXAMPLES:

(println "\nDEREFERENCE-IF-NEEDED EXAMPLES ---------------------")

(set 'L (list (list 1 2 3)
              (list 4 5 6)
              (list 7 8 9)))
              
; What happens if in some kind of loop we push 40 in all sublists
; of list L?

(dolist(i L)
  (print "i before push=" i)
  (push 40 i)
  (println ", after push= " i))
  
; i before push=(1 2 3), after push= (40 1 2 3)
; i before push=(4 5 6), after push= (40 4 5 6)
; i before push=(7 8 9), after push= (40 7 8 9)
  
; Which one of the changes lasted in L?

(dolist(i L)
   (println "i=" (eval (dereference-if-needed i))))
;
; i=(1 2 3)
; i=(4 5 6)
; i=(7 8 9)
;
; Obviously, neither one.
;
; Now, let us try to change L so it contains one reference, and
; use (eval (dereference-if-needed i)) instead of i directly.

(println "---------")

(set 'L (list (list 1 2 3)
              (reference (list 4 5 6))
              (list 7 8 9)))
              
(dolist(i L)
  (print "(eval (deref... i) before push="
         (eval (dereference-if-needed i)))
  (push 40 (eval (dereference-if-needed i)))
  (println ", after push= " (eval (dereference-if-needed i))))

; (eval (deref... i) before push=(1 2 3), after push= (40 1 2 3)
; (eval (deref... i) before push=(4 5 6), after push= (40 4 5 6)
; (eval (deref... i) before push=(7 8 9), after push= (40 7 8 9)

; Which changes lasted?

(dolist(i L)
   (println "(eval (deref... i)=" (eval (dereference-if-needed i))))

; (eval (deref... i)=(1 2 3)
; (eval (deref... i)=(40 4 5 6) <========= :)
; (eval (deref... i)=(7 8 9)

; Another example:

(println "---------")

(set 'M (list 1))
(push 70 (eval (dereference-if-needed M)))
(println M); (70 1)

;===============================================================
; FUNCTIONS THAT RECOGNIZE REFERENCES
;
; The problem is, of course, that (eval (dereference-if-needed M))
; is large and unpractical. Of course, in practice, it would be
; useful to rename dereference-if-needed to something shorter, like &&&.
; Unfortunately we cannot get rid of eval.
;
; However, in we use our own functions, we can delegate the care about
; references to the functions. And it is not really complicated. For example,
; if I want to define function push/r which does exactly the same
; thing as push, but it also accept references, only thing I have
; to do in (push/r <expr1> <expr2>) is to construct expression
;
;       (push (eval(dereference-if-needed <expr1>))
;             (eval(dereference-if-needed <expr2>))
;
; and then, to evaluate it. It can be easily achieved in Newlisp.


(set 'push/r
   (lambda-macro(my-pusharg1 my-pusharg2)
       (eval (expand '(push (eval (dereference-if-needed my-pusharg1))
                            (eval (dereference-if-needed my-pusharg2)))
                     'my-pusharg1
                     'my-pusharg2))))

; The function println/r is bit more complicated. It accepts
; undefined number of arguments; (println/r <expr1> .... <exprn>
; should construct
;
;     (println (eval(dereference-if-needed <expr1>))
;              ...
;              (eval(dereference-if-needed <exprn>)))
;
; and then evaluate it.

(set 'println/r
     (lambda-macro()
        (eval (append '(println)
                      (map (lambda(maparg)
                             (expand '(eval (dereference-if-needed
                                            maparg))
                                     'maparg))
                           $args)))))
                                         

; EXAMPLES:

(println "\nFUNCTIONS THAT RECOGNIZE REFERENCES ----------------")

(set 'N (list 1))
(set 'O (reference (list 1)))
(push/r (list "N") N)
(push/r (list "O") O)
(println/r N O) ; (("N") 1)(("O") 1)

;===============================================================
; AUTOMATIC GENERATIONS OF THE FUNCTIONS THAT RECOGNIZE REFERENCES

; As we have seen in examples, especially from println - definition of
; push/r and println/r is quite mechanic. Somehow it happened even
; the names of the functions are not innovative. Hence, generation
; of such functions can be automatized.

(set 'reference-enable
     (lambda(normal-function-name)
        (set (sym (append (string normal-function-name) "/r"))
             (expand '(lambda-macro()
                        (eval (append '(normal-function-name)
                                      (map (lambda(maparg)
                                             (expand '(eval (dereference-if-needed
                                                               maparg))
                                                     'maparg))
                                           $args))))
                     'normal-function-name))))
                        
; EXAMPLES:

(reference-enable 'sin)
(println/r (sin/r (reference 50))) ;-0.2623748537

(reference-enable 'slice)
(println/r (slice/r (reference (list 10 9 8 7 6 5 4)) 2 3)); (8 7 6)

(reference-enable 'sort)
(reference-enable '<)
(apply 'println/r (sort/r (reference (list (reference 8)
                                           2
                                           (reference 4)))
                           </r)) ; (2 4 8)

;---------------------------------------------------------------
; Now, we'll do our usual trick; pass through the list of all symbols
; and define "reference-enabled" versions of all primitives,
; functions and macros - just in case.

(dolist(f (symbols))
  (let ((ef (eval f)))
       (when (or (primitive? ef)
                 (lambda? ef)
                 (macro? ef))
             (reference-enable f))))
             
; EXAMPLES
        
(println/r (reverse/r (reference (list 2 7 5 4)))) ;(4 5 7 2)

(println/r (add (mul   (sin 26)  
                       (sin/r (reference 26)))
                (mul/r (reference (cos 26))
                       (cos/r (reference 26))))) ; 1

; Yes, even the last one evaluates correctly.

; Functions defined on this way work just fine.
; However, they do not eliminate the need for explicit dereferencing.
; For example
;
;       (dolist/r (reference (list 'i 'L)) ...)
;
; can be useful sometimes, but it doesn't replace
;
;     (dolist (i (eval (dereference-if-needed L))) ... )

;===============================================================
; WHAT NEXT?
;
; Obviously, the technique is promissing. However, some problems
; are left. One of them is well known - memory management. Each call
; (reference <expr>) defines new symbol, and it is not automatically
; deleted once it is not used any more as other values generated
; during runtime. So, either "manual" or "automatic" memory
; deallocation could be required.

; Conveniently, I'll leave that topic for other occasion.

(exit)