;===============================================================
; 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)
