Author Topic: Lisp in Basic  (Read 209186 times)

0 Members and 2 Guests are viewing this topic.

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #360 on: August 11, 2014, 10:18:07 PM »
Thanks John.

So here's one more strategic decision to take.

We should realise that both SB and FBSL are now dealing with an interpreter implemented in an interpretative language. This is interesting and instructive but quite weird and uninspiring, speed-wise.

Let's take another recursive example from the Rosetta Code site that computes Fibonacci numbers up to the 26th number in the topmost Fibonacci sequence here.

The algorithm uses two child recursions in each parent recursion so that the recursive tree grows deeper and deeper as the span of possible numbers to evaluate becomes broader with each next number to find following those already found. This is a very serious stress test to verify the integrity of memory management in a language. Both SB and FBSL LISPs pass it successfully, but!

A static or JIT compiler would do this blazing fast even for a much larger Fibonacci number while the 26th number will be found so fast that the benchmark won't be even registered with the Windows system tick timer.

We can assume that both Oxygen and FBSL's DynC JITs are equally fast and very close to static compilers. So the Fibonacci function written directly in either of them can be taken for reference. Please take a look at the leftmost picture below. It implements this function in C and tries to benchmark it as it runs in JIT-compiled machine code. It will run just a little faster in a true optimizing static C compiler like VC or GCC.

Next we can roughly assume that SB and FBSL have equally fast BASIC interpreters. Have a look at the middle picture below. It implements a verbatim equivalent to the function used in the C benchmark above but rewritten in FBSL BASIC. You can easily translate this code to SB to see the SB results on your machine. Or you can use it for equivalent Oxygen code to verify JIT BASIC speeds compatible to my JIT C above.

And finally, we can roughly assume that our LISPs are also equal in their potential at their current internal settings. So now have a look at the rightmost picture. It presents a verbatim equivalent rewritten in BASIC LISP (I'm always using this term to denote its three current implementations in SB, FBSL, and O2 at once). You can try it on your SBLisp on your machine too to the same effect if you're patient enough. And we'll be also able to test it in OxyLISP as soon as its GC is fully functional. OxyLISP will be showing the results very close to what we have for interpreted SB and FBSL in the middle picture below. No wonder: it will be an interpretative LISP with an engine running in true machine code.

We will never be able to achive OxyLISP results in both SB and FBSL LISPs as we know them now. They are no match for the former. Hehe OxyLISP will be a good match for SB and FBSL BASICs instead.

So we should take a strategic decision now what is reasonable to do in the future. My current opinion is as follows:

-- OxyLISP can continue its development based on the code at hand;
-- FBSL LISP should be rewritten in DynC and therefore go fully C compliant; and
-- SBLisp should be rewritten in CBASIC where possible and utilize verbatim C inlines where not, i.e. inherit the best of the two worlds.

What else can we do so as not to be wasting our time for nothing? I do not know.

.

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #361 on: August 11, 2014, 10:31:22 PM »
John,

QB45 swaps the values in the variables that are used to address the two indices (0 and 1) of the second dimension in the two-dimensional heap value and type arrays.

Since the arrays are now split, there are no indices left to swap the arrays with. They have no point of connection any more. The only way out is to swap the pointers that refer to the array heads, i.e. their respective leading elements. In FBSL, these are array references themselves (values stored under their names, if you want) while in SB, these are the values in ref variables that are storing the pointers to these arrays.

We were lucky enough to have SWAP(array,array) or its equivalent in all the three languages. Otherwise I would've given up immediately even before array splitting. That's because one must be completely out of one's mind to even think of anything that would resemble Aurel's "solution" to the problem even remotely.
« Last Edit: August 11, 2014, 10:38:32 PM by Mike Lobanovsky »

JRS

  • Guest
Re: Lisp in Basic
« Reply #362 on: August 11, 2014, 10:35:31 PM »
There are plenty or Lisp interpreters and compilers out there. I'm not looking to compete with them or even FBSL / O2. I'm more interested in merging the strong points of SB with SBLisp. (ext. module support, symbol standardization, and optimization last)

SBLisp = Toy  Lego / Erector Set BASIC tools to build a custom version of Lisp and maybe solve some of its short comings.

Quote
We were lucky enough to have SWAP(array,array) or its equivalent in all the three languages. Otherwise I would've given up immediately even before array splitting. That's because one must be completely out of one's mind to even imagine anything that would resemble Aurel's "solution" to the problem even remotely.

I don't know about that boy. It's gotten to the point I have to leave him in the car when going out in public. I think it's your turn to watch him for awhile.

JRS

  • Guest
Re: Lisp in Basic
« Reply #363 on: August 11, 2014, 10:49:15 PM »
Arthur Nunes-Harwitt



Biography

Arthur Nunes-Harwitt received his bachelor's degree in Computer Science from Brandeis University. He went on to receive masters' degrees in both Mathematics and Computer Science from the University of Pittsburgh, and is ABD in Computer Science at Northeastern University. He has worked as a software engineer at the Learning, Research and Development Center in Pittsburgh and at The Mathworks, and has taught at the Wentworth Institute of Technology and at SUNY Nassau Community College. His interests include the design and implementation of LISP-like languages, artificial intelligence, and computer algebra.

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #364 on: August 11, 2014, 10:52:29 PM »
SBLisp = Toy
?
Quote
Lego
? ?
Quote
Erector Set
? ? ?
Quote
...solve some of its short comings.
Like what for example? What problems can you solve using a tool that is exactly one thousand times slower than the finely tuned mechanism you're so set to repair?! John, SB and FBSL are only some 120 times slower than VC or GCC. SB/FBSL LISPs are yet an order of magnitude slower than this compared to their SB and FBSL hosts!

Quote
I don't know about that boy. It's gotten to the point I have to leave him in the car when going out in public. I think it's your turn to watch him for awhile.
Have a look here. I was literally begging this ... ... ... to stop sh... ...ting in my thread before the addressee even has a chance to respond. All in vain. ... ... ... ...!
« Last Edit: August 11, 2014, 11:12:36 PM by Mike Lobanovsky »

Charles Pegge

  • Guest
Re: Lisp in Basic
« Reply #365 on: August 11, 2014, 10:58:34 PM »
Gosub is implemented in Oxygen. It translates directly to call label.
To terminate a gosub, ret must be used, rather than return.

JRS

  • Guest
Re: Lisp in Basic
« Reply #366 on: August 11, 2014, 11:02:07 PM »
Doesn't seem to work for me.

Code: [Select]
jrs@laptop:~/sb/sb22/sblisp$ scriba lisp.sb
SBLisp - Scheme BASIC Lisp

0](define fibonacci (lambda (n)
2](if (( n 2)
4]n
4](+ (fibonacci (- n 1))
5](fibonacci (- n 2)))))
2])
1])
FIBONACCI
0](fibonacci 26)
ERROR: Bad type in car.
0]

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #367 on: August 11, 2014, 11:02:58 PM »
Gosub is implemented in Oxygen. It translates directly to call label.
To terminate a gosub, ret must be used, rather than return.

Morning Charles! :)

Yes, we know. We have used them in our OxyLISP 48 hours ago. It would've been impossible to survive without that valuable and indispensable feature in OxygenBasic, ScriptBASIC, and FBSL. :)

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #368 on: August 11, 2014, 11:04:37 PM »
John, it is (< n 2), not (( n 2) again.

JRS

  • Guest
Re: Lisp in Basic
« Reply #369 on: August 11, 2014, 11:13:07 PM »
Thanks!



This looks like one of his WIFI antennas. (free hot spot extended access device)   :)  How Aurel stays connected.

JRS

  • Guest
Re: Lisp in Basic
« Reply #370 on: August 12, 2014, 12:02:38 AM »
Code: [Select]
F0  F1  F2  F3  F4  F5  F6  F7  F8  F9  F10  F11 F12  F13  F14  F15  F16  F17   F18   F19   F20
0   1   1   2   3   5   8   13  21  34  55   89  144  233  377  610  987  1597  2584  4181  6765

Code: [Select]
jrs@laptop:~/sb/sb22/sblisp$ time scriba lisp.sb fibonacci.scm
SBLisp - Scheme BASIC Lisp

(define fibonacci (lambda (n)
  (if (< n 2)
      n
      (+ (fibonacci (- n 1))
         (fibonacci (- n 2)))))
)
FIBONACCI
(fibonacci 12)
144
(quit)
Bye!

real 0m0.464s
user 0m0.452s
sys 0m0.008s
jrs@laptop:~/sb/sb22/sblisp$
« Last Edit: August 12, 2014, 12:09:26 AM by John »

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #371 on: August 12, 2014, 12:27:04 AM »
Ah yes, that code would count the second sequence rather than the first one. The actual values are the same in the both of them barring 0 which isn't a strict Fibonacci number.

But the 12th number won't be informative because both SB and FBSL would yield zeros similar to O2 or DynC with such a childish task!

Try to be patient for some 5 minutes to calc the 26th one to and see the results in SB and SBLisp that could somehow compare given the differences in our HW (my PC is faster).


Here's its counterpart for your HW reference:

.

JRS

  • Guest
Re: Lisp in Basic
« Reply #372 on: August 12, 2014, 12:43:39 AM »
You have a faster computer than my Toshiba laptop.

Can you run the same for FBSL and SBLisp (fibonacci 14) on your box? (use SBLisp.exe)

Also can you do a prompt to prompt speed test? This is how SB is reporting it's time. There is something to be said for startup and the time it takes to clean up.


« Last Edit: August 12, 2014, 12:52:33 AM by John »

Mike Lobanovsky

  • Guest
Re: Lisp in Basic
« Reply #373 on: August 12, 2014, 12:56:43 AM »
Hold on for a while. I've got something better to offer.

Back.

Now please goto your sources and change your DoLoad as follows:

Code: [Select]
DoLoad:
  ptype = qtype
  pvalue = qvalue
  bsd += 1
  GOSUB Car
  bsd += 1
  GOSUB RregtoPreg
  IF ptype <> symbol THEN
    PRINT "ERROR: Load needs a symbol.\n"
    GOTO HandleError
  END IF
  lispfilename = symbols[pvalue]
  OPTION COMPARE sbCaseInsensitive
  fnpos = INSTR(ibuf, lispfilename)
  IF fnpos THEN lispfilename = MID(ibuf, fnpos, LEN(lispfilename))
  OPTION COMPARE sbCaseSensitive
  lispfilenum = 1
  bsd += 1
  GOSUB LispOpenInputFile
gtc=now
  WHILE NOT EOF(lispfilenum)
    stkcursor = 0
    curenv = globalenv
    bsd += 1
    GOSUB LispRead
    bsd += 1
    GOSUB RregtoPreg
    bsd += 1
    GOSUB LispEval
    bsd += 1
    GOSUB RregtoPreg
    bsd += 1
    GOSUB LispPrint
    PRINTNL
  WEND
print "Done in ",now-gtc," seconds\n"
  bsd += 1
  GOSUB LispCloseFile
  rtype = booleant
  rvalue = TRUE
  bsd -= 1
  RETURN

This will enable you to time the evaluation loop only. It will work for files only but not for interactive evaluation which cannot be timed that simple.

Your resolution will be rough but passable if evaluation takes longer than 10 seconds.

Save your LISP code as a file with (fibonacci 20). Run it to compare it against my reference picture below.

This effectively eliminates all overhead for initializing your arrays with Splita and all other prolog/epilog code. Pure evaluation and garbage collection timed. This is how my measurements are taken too but with the GetTickCount() timer.

.
« Last Edit: August 12, 2014, 01:14:10 AM by Mike Lobanovsky »

JRS

  • Guest
Re: Lisp in Basic
« Reply #374 on: August 12, 2014, 01:23:21 AM »
Sweet!

When I get the SDL_gfx interface working it has a sub-second timer.

I'm still interested in a prompt to prompt comparison. I want to see how much time the interpreters are taking to do their jobs. Do you have a Windows console process timer like the Linux time utility?