Another newLISP-like language :)

[cormullion]

I think 'dynamic scoping' must be the number one most-cited reason for people not trying or using newLISP. You can't help wondering whether more people might use newLISP were this apparently 'major obstacle' to be changed in the future.



Although, judging from the statements of some of the people who've been actively disliking newLISP recently (don't they have anything better to do?), it might be a good thing to deter a few of them from the very start...



Me - I don't worry about scoping at all. :)

[newBert]

Thank you all for your answers, I can use them as arguments in discussions about this topic (scoping, etc.) without appearing too ignorant ... ;)



In fact, although it does not use static scoping by default,NewLisp can still implement (functional) object-oriented programming which is easier to use and clearer than the classic OOP. Generally, some purists are surprised at -and even disturbed by- that.



I take advantage of the occasion to greet and thank Pavel for having done Elica and for his replies to my (sometimes "simpleminded") questions on other forums.



:)

Regards,

NewBert, aka Taobert, aka Bertrand ...

[xytroxon]

If you use Lisp... Then the name "newLISP" implies that you are using the old and possibly flawed Lisp... And you become defensive, denying that anything is old or flawed about Lisp...



If you use Scheme... You agree something is flawed with old Lisp... But you become defensive because Scheme fixed Lisp...



If you use newLISP... You are so excited that you can finally write your "Lisp" programs so that they work and do something more useful than boring textbook exercises, that it's hard to hold back your joy of wanting to tell everyone you meet!!!



Needless to say, that kind of EUREKA! feeling using "newLISP" irritates Lisp and Scheme programmers to no end...

[newBert]

I have also tried other things :

Code Select Expand

;; NewLISP
(define x 1)

(define (f) x)

(f) ; => 1

(define (g x) (f))

(g 0) ; => 0

;; SCHEME
(define x 1)

(define (f) x)

(f) ; => 1

(define (g x) (f))

(g 0) ; => 1

I can't get equivalent results in Scheme and in NewLisp, due to different scoping, and 'letex' is of no use to me here.

Finally, I found two solutions :

Code Select Expand

(set 'x 1)

(define f (fn () x))

(define g:g (fn (g:x) (f)))

(f) ;=> 1
(g 0);=>1

Code Select Expand

(set 'x 1)

(define f
  (letex (x x) (fn () x)))

(define g (fn (x) (f)))

(f) ;=>1
(g 0);=>1

And my (maybe) simplistic conclusions :

- NewLISP gives the choice between dynamic scoping and static scoping (thanks to contexts and/or 'letex')

- although NewLISP is dynamicly scoped by default, it can be explicitly lexically scoped too.



Isn't it an advantage compared to Scheme, which is exclusively lexically scoped ?



Well, I quit there with my obsessions about scoping and I spend it on something else :-D



Regards,

Bertrand

[itistoday]

I don't think you can do memoization with newLISP because of its dynamic scope, as I discovered when http://www.alh.net/newlisp/phpbb/viewtopic.php?t=2162">working on streams.  I'd love it if someone proved me wrong on this, but you can't use contexts to do it, because that would turn out to be way too ugly and inflexible, I think.

[Lutz]

Here are two ways to implement memoization in newLISP. The first without contexts:

Code Select Expand

(define (mysqrt x ())
(or (lookup x (nth (mysqrt 0 1)))
      (last (push (list x (sqrt x)) mysqrt '(0 1 0)))))

> (mysqrt 10)
3.16227766
> (mysqrt 10)
3.16227766
> (mysqrt 20)
4.472135955
> (mysqrt 30)
5.477225575
> mysqrt
(lambda (x ((30 5.477225575) (20 4.472135955) (10 3.16227766))) (or (lookup x (nth
    (mysqrt 0 1)))
  (last (push (list x (sqrt x)) mysqrt '(0 1 0)))))
>


An association list contains the memorized results, stored in the function itself.



The second solution uses contexts. I find it much cleaner, because the context packaging allows me to store other things besides the memoization memory, and it separates the function from the memoization storage

Code Select Expand

(define (my_sqrt:my_sqrt x)
(or (and my_sqrt:mem (lookup x my_sqrt:mem))
(last (push (list x (sqrt x)) my_sqrt:mem))))

> (my_sqrt 10)
3.16227766
> (my_sqrt 10)
3.16227766
> (my_sqrt 12)
3.464101615
> my_sqrt:mem
((12 3.464101615) (10 3.16227766))


Lutz

[newBert]

Fine, we can really play with NewLISP as we would play with Scheme (or Lisp), but with more facilities. Things and concepts become clearer with NewLISP.

;)

[itistoday]

Here are two ways to implement memoization in newLISP. The first without contexts:

If you look at how memoization is used in streams (see the function memo-proc in http://www.alh.net/newlisp/phpbb/viewtopic.php?t=2162">this thread), I think you'll see that lexical scoping would be a better solution, the main point being that with streams, the function that is "memoized" is arbitrary.

Code Select Expand

(define (mysqrt x ())
(or (lookup x (nth (mysqrt 0 1)))
      (last (push (list x (sqrt x)) mysqrt '(0 1 0)))))


An association list contains the memorized results, stored in the function itself.

This is a really cool solution actually, you're redefining the function each time it's called with a new value, but there are two problems that I see with this: first, it's obviously less efficient to have to do a lookup in a list each time the function is called (the function then becomes at *least* O(n)) than to just get the answer from a statically saved variable that goes with the function, and secondly, you can only use this on functions that have this sort of definition, I don't think you can use this method to memoize arbitrary functions.

The second solution uses contexts. I find it much cleaner, because the context packaging allows me to store other things besides the memoization memory, and it separates the function from the memoization storage

Code Select Expand

(define (my_sqrt:my_sqrt x)
(or (and my_sqrt:mem (lookup x my_sqrt:mem))
(last (push (list x (sqrt x)) my_sqrt:mem))))

Again, I believe this falls under similar criticism, here you can only memoize a function that's designed to be memoized.

[m35]

Here are two ways to implement memoization in newLISP. The first without contexts:

Code Select Expand

(define (mysqrt x ())
(or (lookup x (nth (mysqrt 0 1)))
      (last (push (list x (sqrt x)) mysqrt '(0 1 0)))))

> (mysqrt 10)
3.16227766
> (mysqrt 10)
3.16227766
> (mysqrt 20)
4.472135955
> (mysqrt 30)
5.477225575
> mysqrt
(lambda (x ((30 5.477225575) (20 4.472135955) (10 3.16227766))) (or (lookup x (nth
    (mysqrt 0 1)))
  (last (push (list x (sqrt x)) mysqrt '(0 1 0)))))
>


Wow Lutz, that just blew my mind. :D

[Lutz]

here you can only memoize a function that's designed to be memoized

the following creates memoizing functions from any function and arbitrary number of arguments:

Code Select Expand

(define-macro (memoize func mem-func)
  (set (sym mem-func mem-func)
    (letex (f func m (sym "mem" mem-func))
        (lambda ()
          (or (and m (lookup (args) m))
              (last (push (list (args) (apply f (args))) m)))))))

> (memoize add my-add)

> (my-add 3 4)
7
> (my-add 5 6)
11
> (my-add 3 4)
7
> my-add:mem
(((5 6) 11) ((3 4) 7))
>


The fact that the lookup speed is O(n) is only an implementation detail of the lookup. Instead of using an association list, you could use b-tree name-space lookups when many different results have to be cached:

Code Select Expand

(define-macro (memoize func mem-func)
  (set (sym mem-func mem-func)
    (letex (f func  c mem-func)
        (lambda ()
          (or (context c (string (args)))
              (context c (string (args)) (apply f (args))))))))

(memoize add my-add)

> (my-add 3 4)
7
> (my-add 5 6)
11


The cache is now the 'my-add' namespace itself. There is no danger of symbol clash as all start/end with parenthesis.



Note that in both solutions the memoizing cache memory can easily be made persistent by simply saving the context using 'save'.



Lutz



ps: simplified context/hash creation

[Elica]

the following creates memoizing functions from any function and arbitrary number of arguments

Too bad for rand.



http://forum.skycode.com/img/90.gif">

[itistoday]

Fascinating stuff Lutz, though I still think it seems a bit contrived when compared to using lexically scoped functions.  Nonetheless, I set about to re-write the (delay) function for streams using your macro, and I did some basic benchmarks too.



Here is the new delay function (let me know if you see any ways of improving it btw):

Code Select Expand

(define-macro (delay)
(let (memo-func-name (sym (string (args 0 0) "-memo")))
(if (nil? (sym memo-func-name memo-func-name nil))
(letex (a (args 0 0) b memo-func-name) (memoize a b)))

(letex (params (rest (args 0)))
(letex (f (cons memo-func-name 'params))
(fn () f)
)
)
)
)

Here's an example of its use:

Code Select Expand

> (delay (+ 1 1))
(lambda () (+-memo 1 1))

I discovered that it's actually just a tad faster to use the first version of memoize, I'm guessing this is because it doesn't have to create strings out of the parameters.  However, once you start calling the same function with many different parameters, I'm sure the second version will become faster.



Using this new delay function results in a significant reduction in performance on the first-call (to be expected), but in a significant speed-up if the exact same *exact* code is executed again (meaning even the parameters must be the same).  I think that in most situations when an algorithm is run, it's probably only executed once with the same parameters. Therefore I would probably recommend against doing it in newLISP.



Again, on the topic of lexical vs. dynamic scoping, I think that this example clearly demonstrates some of the advantages of lexical scoping, which would most likely result in much faster times on the first run.



Here's an example of what I'm talking about (I'll post more detailed examples in the http://www.alh.net/newlisp/phpbb/viewtopic.php?p=11919#11919">steam thread):

Code Select Expand

> (time (odd-fibs 50))
16
> (time (odd-fibs 30))
11
> (time (odd-fibs 30))
1
> (time (odd-fibs 25))
11

[newBert]

the following creates memoizing functions from any function and arbitrary number of arguments:

Code Select Expand

(define-macro (memoize func mem-func)
  (set (sym mem-func mem-func)
    (letex (f func m (sym "mem" mem-func))
        (lambda ()
          (or (and m (lookup (args) m))
              (last (push (list (args) (apply f (args))) m)))))))




Lutz

Yeees! And it works with the example from Scheme that I found it difficult to adapt in NewLISP.

Code Select Expand

;;; Scheme ;;;
;(define memoize
;  (lambda (proc)
;    (let ((cache '()))
;      (lambda (x)
;        (cond
;          ((assq x cache) => cdr)
;          (else (let ((ans (proc x)))
;                  (set! cache (cons (cons x ans) cache))
;                  ans)))))))
;
;(define fibonacci
;  (memoize
;    (lambda (n)
;      (if (< n 2)
;          1
;          (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))))
;
;(fibonacci 100) ; => 573147844013817084101
;(fibonacci 20)  ; => 10946

(define-macro (memoize func mem-func)
  (set (sym mem-func mem-func)
    (letex (f func m (sym "mem" mem-func))
        (lambda ()
          (or (and m (lookup (args) m))
              (last (push (list (args) (apply f (args))) m)))))))

(memoize
(lambda (n)
(if (< n 2)
1
(add (fibonacci (sub n 1)) (fibonacci (sub n 2)))))
fibonacci)

(fibonacci 100) ; => 5.73147844e+020
(fibonacci 20)  ; => 10946

Thank you very much, Lutz :)



Bertrand

[Lutz]

I added the context based memoize function here:



http://www.newlisp.org/CodePatterns.html">http://www.newlisp.org/CodePatterns.html



and here:



http://www.newlisp.org/index.cgi?page=Code_Snippets">http://www.newlisp.org/index.cgi?page=Code_Snippets



and with swapped order of arguments for easier readable, direct

embedding of recursive lambda functions as in:

Code Select Expand

(memoize fibo
   (lambda (n)
     (if(< n 2) 1
       (+  (fibo (- n 1))
           (fibo (- n 2))))))


This puts the name of the new function better recognizable on top.



Lutz

[itistoday]

That's neat!  Thanks for mentioning my analysis (I've updated it to be more accurate btw... woke up this morning to the stark realization that I'd made a mistake! :-O)



A cool thing about the (delay) function is that if you want control over how things are memoized based on the function arguments (for example if one of the arguments is irrelevant), you can define your own custom version of the memoized function and it will be used instead.  E.g.:

Code Select Expand

(define (my-func-memo:my-func-memo arg1 arg2)
; memoize based on arg1 only
)