Lisp in Basic

[Mike Lobanovsky]

Mission accomplished :

No way Rob,

Your exe says it needs some funky libreadline.dll library and quits.

[JRS]

That explains why it didn't run under Wine either. 

[RobbeK]

OOps - 

forgot CLisp needs some DLLs to run ,

-- bundled it into a GCL executable ....


best , Rob

it runs in interpreted mode , if you type (compile 'ackermann) it will compile the function -- (main) runs it in compiled mode then.
...  and then (time (main))   will give the time spent to run ....

also added mandelmemo -- An output from the  STALIN Scheme compiler

.

[Mike Lobanovsky]

Hi Rob,

1. Is this an interpreted Ackermann code?!

It is blazing fast nor does it cause inevitable stack exhaustion at [4,2]. It must be turned transparently into its iterative equivalent else it isn't really possible...

2. Your graphic mandel is beautiful.

3. What are LISP "environments"? Are these what we call variable visibility scopes in plain English? (similar to how "memoization" is nothing but good 'ole cache...)

[RobbeK]

Hi Mike,

1) Yes, interpreted , but comes with a note :  tail-recursive call to ACKERMANN converted to iteration (it also uses caching , of course).
at the command line when the demo ends, you can do   (compile 'ackermann) , you will see same message pops up again....

2) interesting experiment -- the idea is to memoize/cache 2D area's   -- this is how it looks with a (infantile) low table (only 800*800 = the number of pixels used )   -- I may can get reasonable results with a table of 3*3*10000*10000 floats -- this prog is NOT done by caching , it just simulates the result with a small table.  (the problem is, things like fibonacci , x! , Ackermann are exact numbers , the outcome of a Julia iteration is not -- somewhere we have to declare non identical numbers but close numbers equal to make it working .  Nevertheless, imo the result is attractive.   

3)  yes & yes , it's much easier to invent new names than new techniques ;-)
About a decade ago, caching also entered computer chess  ,  prototyped by Налимов   

https://ru.wikipedia.org/wiki/%D0%AD%D0%BD%D0%B4%D1%88%D0%BF%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B_%D0%9D%D0%B0%D0%BB%D0%B8%D0%BC%D0%BE%D0%B2%D0%B0


Look how much is needed for 7 "figures"  ---  (the English version doesn't give these numbers, it seems - from there the link above)   -- it will not kill the game of chess ,   possible combinations at the start of a game may be something of (the reward of the King) !         (faculty of the number of grains at field 64 )

best Rob

[Mike Lobanovsky]

Guys, you won't believe it but what you're seeing in the appended snapshots is the birth of FBSL's brand new JIT compiling DynLisp layer. It's at its proto stage yet and it can do just a few Lisp operations only but it can already resolve a recursive lambda.

See how it beats Tiny Scheme in calculating (fibonacci 35) -- it's exactly 90 times faster. I wouldn't post this message in the TS thread for fear lest henceforth John redard me his personal archenemy for sabotaging his own SB extension.

I'm feeling very excited and I just wanted to share my feelings with you.

.

[RobbeK]

Congrats, Mike ...   

It would be interesting to see the benchmark with a helper (single) recursive function :

(defun fibo*  ( a b x)
    (if (= x 0) a
        (fibo* b (+ a b) (1- x))))

(defun fibo (x)
   (fibo* 1 1 x))

;; needs to be converted into Scheme syntax

-------------------------------------------output from the REPL , CLisp in interpreted mode :


[4]> (time (fibo 35))

Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 12 Bytes
14930352
[5]> (time (fibo 350))

Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 8496 Bytes
10119911756749018713965376799211044556615579094364594923736162239653346274
[6]>
[6]> (time (fibo 3500))

Real time: 0.046875 sec.
Run time: 0.046875 sec.
Space: 566808 Bytes
GC: 1, GC time: 0.03125 sec.
2071302422030262753416199537299341464207691967344600973326088247223853841292493160797697343340451944
4976593116933291600999770493153188194487391358228695151342468224877086896425368422810438268966043143
5922397519756497357499967505758679688646649075302803539077528386858224498222588856280163988716395494
3851743918399601630391772093506274643901267107805198009064692093234224193403702061606850299426651476
9908089454731212877225205687361987022780519210425124250789022062818138048190207921943410932369612123
1264625722768733484440412902313033879037929246974105582008193813127877888969955929338924710176760096
4317826621273936149422080698086653588915837724060010304084595878920010121852066682093621607829876763
92635512259975382189797347146626

[9]> (compile 'fibo) (compile 'fibo*)  ;; switched to compiled code

 
NIL ;
NIL
[10]> (time (fibo 3500))

Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 566808 Bytes
2071302422030262753416199537299341464207691967344600973326088247223853841292493160797697343340451944
4976593116933291600999770493153188194487391358228695151342468224877086896425368422810438268966043143
5922397519756497357499967505758679688646649075302803539077528386858224498222588856280163988716395494
3851743918399601630391772093506274643901267107805198009064692093234224193403702061606850299426651476
9908089454731212877225205687361987022780519210425124250789022062818138048190207921943410932369612123
1264625722768733484440412902313033879037929246974105582008193813127877888969955929338924710176760096
4317826621273936149422080698086653588915837724060010304084595878920010121852066682093621607829876763
92635512259975382189797347146626
[11]>

-------------------------------------------------------------------------------------------

best Rob

[Mike Lobanovsky]

Rob,

CLisp unwinds recursion to iteration, interpreted or otherwise. Or it may use a cache transparently. Or both. And noone knows what else.

DynLisp is in fact a rudimentary Scheme and it can't optimise recursion to iteration. I haven't seen a generalized algorithm to recognize and perform such an optimization from either you or Charles yet and I don't know where to look for it on the net. At any rate, it is too early for DynLisp to compete with mature LISP compilers but I'm seeing great potential in it to compete with rank-and-file LISP interpreters. And it also is my own one and it is hosted within the same Fbsl.exe that already incorporates three other no-nonsense languages -- BASIC, C, and Asm.

[RobbeK]

Hi Mike,

You probably used a double recursive mechanism for your benchmark,  from there I was interested to see how single rec. compares to double rec.

in Scheme that's

(define fibo*
   (lambda (a b x)
     (if (= x 0) a
        (fibo* b (+ a b) (- x 1)))))

(define fibo
   (lambda (x)
     (fibo* 1 1 x)))

;; can be speeded up one cycle     by (if (= x 1) b    ;;;

recursion / iteration

http://cs.saddleback.edu/rwatkins/CS2B/Lab%20Exercises/Stacks%20and%20Recursion%20Lab.pdf      (??)

best Rob

[Mike Lobanovsky]

Thanks for the pdf Rob,

I'll look through it, perhaps it can give me ideas.

I'll post the benchmark results a little later (need to have some rest). I am already able to translate myself such simple pieces of LISP code from one dialect to another.

See you in the evening.


P.S. Hehe, FiboRob appeared to be incongruously faster in both implementations. It is in fact so fast that the results are actually app load/unload timings. (Fbsl.exe is a much heavier app and its three engines (actualy three and a half ) do take time to initialize)

Can you make every LISP program that fast? 

.

[RobbeK]

Hi Mike,

"Can you make every LISP program that fast?  "  -- it worked with the Ackermann too 

Well, it works with accumulators , in this case a and b

From a mathematical viewpoint this form has enormous advantages :

- you can restart from any value a and b from the series (i.o. starting over from 1 again)
- it gives possibities analyzing things p.e. returning also the factor between two sequential elements of the series :

(defun fibo*  ( a b x)
    (if (= x 0)  (list a (/ b a))      ;;;;;  extra info returned
        (fibo* b (+ a b) (1- x))))

here the cadr gives the value nth+1 term / nth term :   if x is high enough, you will see it becomes the value of the golden ratio !!!! -- going further, you can completely and exactly make the fibonacci analytic for every real and complex number.

This may be the unspoken disadvantage of Lisp -- every piece of code may reveal your capabilities (or lack of same).  (Lisp is limited to the brain of the hacker/coder    )

The only thing remaining is to understand the lambda-macro , a lot of coders fail to do so.

If you understand next , you know everything about Lisp there's to know about :

(define not-if
  (lambda-macro (condition a b)
    (if (eval (not condition)) (eval a) (eval b))))

or

(define not-if
  (lambda-macro (condition a b)
    (if (eval condition) (eval b) (eval a) )))

It's easy --  the lambda-macro does not evaluate things , it copies and has to be forced by eval to evaluate its arguments, that's all  -- it is an extremely powerful tool   (it's somewhat more complicated with compilers , but only a little step -- it uses (eval-when    ) and some other tricks

best Rob

[Mike Lobanovsky]

Yes Rob,

I'm seeing the benefits of lambda-macro very clearly. It introduces lazy evaluation of the lambda's intrinsic components and in this way it effectively halves the costs (overhead) of overall evaluation and consequently doubles its speed if the both components are equally computationally heavy.

[Mike Lobanovsky]

Thanks for the pdf Rob,

I'll look through it, perhaps it can give me ideas.

That's it, Rob!

The following strategy can be used to the remove the recursion from a recursive routine, although not elegantly. There might be a far more pleasing method for a particular routine, but this technique is very instructional. It allows you simulate the system stack by declaring your own stack structure and manage the recursion. It is accomplished as follows:

i) Each time a recursive call is made in the algorithm, push the necessary information onto your stack.
ii) When you complete processing at this deeper level, pop the simulated stack frame and continue processing in the higher level at the point dictated by the return address popped from the stack.
iii) Use an iterative control structure that loops until there are no return addresses left to pop from the stack.

Thanks for sending me to my first school grade again!

[RobbeK]

Great 

An addendum about the lambda-maco's  -- this is NewLisp , infact it uses the ancient (fexpr    )  , it was buried in the 70s when the UNIX systems started to compile Lisp code. 
Strangely the NewLisp is very close to the original McCarthy Lisp of the end 1950s (and in fact so is PicoLisp ).
All these 3 (Mr McCarthy (the inventor) , Mr Lutz Mueller (NewLisp) and Alexander Burger (PicoLisp) are somewhat convinced their languages can not be compiled ).
So the "desecration" of the fexpr "corpus" is very logical -- it works in an interpreter , and maybe OldLisp is a better name for NewLisp 

I think recursion->iteration can be simulated @ Lisp level too --

the definitions of push and pop are easy :

;;  Scheme flavor ;;;


(define push
  (lambda (data stack)
   (set! stack (cons data stack))))

(define pop
  (lambda (stack)
    (let (( result (car stack)))
      (set! stack (cdr stack))
    result )))

with the usual advantage that here the stack is a typeless and variadic container 

best Rob

[Mike Lobanovsky]

Strangely the NewLisp is very close to the original McCarthy Lisp of the end 1950s

Are you really that ancient, Rob?

I think recursion->iteration can be simulated @ Lisp level too --

Did you know that almost all existing LISP-to-C and LISP-to-Asm translators are actually written in LISP? Their source code is thus an order of magnitude shorter than its respective C or assembly analog.