Lisp in Basic

[Mike Lobanovsky]

So here comes my report on the current state of affairs in the BL project.


0. What I wanted to do and why:

0.1. I wanted to de-interleave the GOTO/GOSUB code into SUB's and/or FUNCTION's to eliminate the necessity to count the current stack depth in every program step. Stack depth counting is required to be able to unwind the stack in case the interpreter hits an exception and needs to be reset in its initial state recovering its program stack from the state of deep recursion and/or deeply nested mutual calls. If the stack is left unwound, its uncontrolled growth may lead to its eventual exhaustion and total program crash.

0.2. The existing strategy of stack depth counting however isn't a panacea. Even if the stack is unwound successfully and the interpreter is reset to its initial state, in very many cases there is no possibility to correct the faulty LISP code already entered for execution. If the faulty code is a simple immediate arithmetical expression, it can be re-entered with all the typos corrected and re-run again. But now let's assume that we entered the definition of a complex lambda successfully, the syntax checker hasn't found any lexicographical errors, and the lambda name has been added as a SYMBOL to the symbol hash table. At run time however the lambda may cause an exception e.g. due to improper math calc hardcoded in it. The interpreter will be reset but the lambda cannot be recoded because its SYMBOLic name cannot be redefined in the hashtable. BL doesn't support redefinition of its SYMBOL's. It can be fully reset only by quitting the current session altogether. It makes the entire headache of counting the stack depth not worthwhile.

0.3. There are over 550 instances of BSD (stack depth counter) incrementation throughout the code corresponding to GOSUB calls, and there will be an exact same amount of decrementations to keep the stack balanced. And all this in just one single cycle without going into any recursion or a nested call whatsoever. Going recursive will increase these numbers many times over. It means we will be executing many thousands of incrementations and decrementations over and over again for a slim chance of unlikely error in a piece of known working code. This will be a speed killer for any interpreter even if it runs compiled to machine code, e.g. like OxyLISP will.


1. What I did:

1.1. I thought that natural early bailout from functions in response to an error will keep the stack balanced equally well without any artificial stack depth counting. So I tried to de-interleave the existing GOTO's and GOSUB's into more structured SUB/FUNCTION code entirely. But I was able to do so without breaking the expected program flow only to some two fifths of the total amount of program code. The entire LispEval refuses splitting into functions no matter what I do because the expected program flow gets broken whenever the error is raised in anything more complex than a simple arithmetical operation.

1.2. I became convinced that adding continuous error flag checks and assigning return values to functions may lead to overhead penalties as severe as those caused by continuous BSD incrementation and decrementation. The interpreter will stay just as slow with functions as it was with the stack depth counter.

1.3. Based on my findings and considerations as per Items 0.2 and 0.3, I reverted the entire code to its initial GOTO/GOSUB state and deleted the BSD counter altogether. In doing so I expect that infrequent typos in the interactive input of simple math one-liners will not eat up the stack to any visible amount while major mishaps like those described in Item 0.2 will require the user's univocal exit from the current session.

1.4. I added a command line option -q (quit session on error) to let the user to either proceed as per Item 1.3 or force the interpreter to quit the current session immediately on the first error encountered. The option works in both interactive and file-load-and-run modes but seems more practical in the latter.


2. What I'm planning to do:

2.1. The initial QB functionality with BSD can be fully re-implemented in Oxygen with Charles' ReturnLabel inline asm trick but OxyLISP will suffer speed penalties as described in Item 0.3. We should seriously reconsider these consequences before we proceed that way.

2.2. The initial QB functionality can be fully re-implemented in SBLisp when it is rewritten in CBASIC. We can use Charles' trick emulated with GCC's inline assembly too but only to suffer the exact same unjustified penalties. GOSUB/RETURN functionality can also be emulated with the aid of GCC's inline assembly.

2.3. FBSL's DynC does not support inline assembly of its own therefore Charles' trick can't be used in FBSL at all. FBLisp will stay as per Items 1.3 and 1.4 even in its DynC implementation. FBSL can do it all as well in both its BASIC and DynC variants.

2.4. I suggest we consider the current state of BL code as the final prototype before getting down to the actual implementation in each respective language.

2.5. I propose OxyLISP and O2 as the first step of BL implementation in each language. O2 with its "strongly elastic" arrays is easier to work with than pure ANSI C or CBASIC and OxyLISP will immediately show us what we may expect from DynC and moreover, from fully optimized -O3 GCC, later.


3. What I'm currently doing:

3.1. I'm currently working in FBSL with FBLisp.

3.2. I've added a -h option to display a brief usage and option help screen.

3.3. I've changed -d to -v (verbose) to display extended error messages and LISP code as it is being loaded from the disk file. Without that option, BL displays only loaded SYMBOL names (as Rob said) and short error descriptions as it did before. You can see Rob's ASCII Mandelbrot loaded into my FBLisp without the -v switch in my latest screenshot.

3.4. I've added trig and rounding mode functionality. OxyLISP can use msvcrt.dll API's. If something is missing in SB, I'll add #unimplemented stubs for the time being. They will be changed for GCC's intrinsics when ported to CBASIC/GCC for final compilation. This way OxyLISP, SBLisp and FBLisp's LISP scripts will fully compatible until/unless language specific add-ons are developed and added in the future.

3.5. When I'm through with pow and division functions, I will post the FBSL sources here for examination (they are easy to read in the two other languages too), and a precompiled FBLisp binary for testing.

Dixi. 

UPD Charles inspired me to make one last attempt at restoring BL's program stack properly. This time I succeded, therefore the lines that are striken through above no longer apply. BL will handle its stack just as good as Lisp-in-Basic did, but more efficiently and visibly faster.

[JRS]

I will post the FBSL sources here for examination ...

   I thought you were using SB for the prototype of BL. Why the switch to FBSL? Did I waste my time with the SB / Bitbucket effort? I'm not participating in a Windows only project. Sorry!

[Mike Lobanovsky]

Preconception? Jealousy? How fast you are jumping to conclusions!

1. I am able to prototype this particular code in SB almost as fast as in FBSL, but...

2. I had only an early FBSL proto at hand that would contain all the initial GOTO's and GOSUB's in it, reformatted but fully QB-based. So my decision was only too natural under the circumstances. Nothing personal, just business.

3. Actually I was planning to port my FBSL proto to SC to be tried under Linux too while you were still alpha testing the proto under Wine and Win 7. Who told you it will stay Windows only? And Rob doesn't care, in the meantime, if it's SBLisp.exe or FBLisp.exe that he's using for his fine art so long as its functionality is exactly the same. In this manner, you won't be sitting with nothing to do while I'm porting the proto to SB.

So what's all this buzz about? Am I jealous of your adultery with ECL or TinyScheme? No. So why are you jealous of me and my FBSL? Perhaps because that's what you would have done in my place -- trash FBSL and hurry on with your SB? That's not my style, John. I said I care for, and am taking care of, all the three implementations BL in the respective languages with equal concern.

So you have nothing to be sorry about. All sorrow is mine again, not yours.

Shame on you, John. Never thought your reaction would be so inadequate. I'm feeling like someone has just spat in my face despite all the work I've done...

Go ahead with your TinyScheme exercises.



Good night.

[JRS]

I'm just trying to follow along based on your mixed messages and demands. You said to freeze the SB code as your were going through a major revision. While on the bench, I was drafted by the TinyScheme team. The next thing I hear is a FBSL version will be posted shortly with source which you have forbidden to reside anywhere other than the FBSL site. Preconception? Jealousy?  I think you are reading between the lines. BASIC Lisp is interesting and fun project because it gives us an opportunity to see how a Lisp runs under the covers and actually understand what is going on.

Please let me know when you have a working SB version so I can update the repository and unfreeze the code.

[Mike Lobanovsky]

I'm just trying to follow along based on your mixed messages and demands.

From now on, you won't be getting messages from me in order to avoid mixing them with some other LISP's that you're trying to master. Neither will there be any demands or requests or suggestions addressed to you personally. Nor will there be any reports on what I did, or what, why and how I'm planning to do, or actually am doing. None of all that crap any more. Delivery terms on board ship O2 forum, payment at sight. No more fooling around.

Please let me know when you have a working SB version so I can update the repository and unfreeze the code.

You will get to know it automatically having seen it uploaded here just as its FBSL and O2 counterparts.

No need to see me off, John. Have a good day.

[JRS]

Good night and sleep well.

Once again, thanks for all the effort you have put into the BL project.

[Charles Pegge]

Mike,

It seems to me that error bail-outs cause a lot of complication in the Lisp engine, particularly in managing the stack. Have you considered using a run-time error log instead? The standard behaviour would then be to log the error and its position, then exit the current function and continue operations normally. The program would then be able to check its error log at an appropriate point, and respond under full program control.

I also have some further thoughts on tail recursion in functions involving strings. Local garbage collection and local string clearing have to be woven into the algorithm converting tail-recursions into loops.
 

[Charles Pegge]

A model for direct-string-safe tail-recursion:

rather intense for a compiler

Code: [Select]

'ORIGINAL
=========

function fiboR(m,n,c, string s) as string
if c
  return n+" "+fiboR(n,m+n,c-1,s)
end if
end function


'TRANSLATE TO LOOP
==================

function fiboL(sys m,n,c, string _s) as string 'DECORATE DIRECT STRING PARAMS
'
bstring s=_s      'MAKE COPIES OF ALL DIRECT STRING PARAMS
bstring recurn    'RETURN VALUE (now a bstring)
recur:            'LOOP POINT
                  'START OF SOURCE FUNCTION BODY
if c              '
  recurn += n+" " 'ACCUMULATE RETURN VALUE (instead of return ...)
                  '
                  'PARAM SETTING (safe!)
  tc=c-1 : tn=m+n '
  tm=n : ts=s+"X" '
  m=tm : n=tn     '
  c=tc : s=ts     '
  lea edi,[ebp-4] 'LOCAL GARBAGE COLLECTION LIST
  call [ebx+2080] 'DELETE LOCAL STRINGS (RTL:delchain)
  goto recur      'MAKE RECURSIVE LOOP
end if            '
                  'END OF SOURCE FUNCTION BODY
frees s           'RELEASE ALL COPIES OF DIRECT STRING PARAMS
return recurn
end function

'print fiboR  1,1,10,"dummy"
 print fiboL 1,1,10,"dummy"


[Mike Lobanovsky]

Hi Charles,

It stands to reason to try what you suggest. Basically there are three linear steps in each interpreting loop cycle: lispread (keyboard input or file line), lispeval, and lispprint.

Lispread in its file line hypostasis can go down one level into its own lispread, lispeval and lispprint loop where low-level lispread, lispeval and lispprint behave exactly like those in the top-level main loop, i.e. can go down yet further.

Lispeval can go down into yet another lispeval and lispprint.

Lispprint can only go down (recurse) into itself.

Each lispread, lispeval and lispprint can call about five dozen helper subs some of which can also call lower-level lispevals of their own. Each of these subs can log various errors and signal them by setting a global error flag.

My earlier designs tried to respond to the error flag with immediate bailout from whatever sub the code pointer currently was in. It flooded the code with innumerous error flag checks upon exit from almost any sub call in the code. I was getting rid of 550 incrementations of stack counter just to find myself in some 500 checks of global error flag instead. Traded bad for worse, so to speak.

Bailing out immediately was supposed to bring me very quickly back to the top-level (main) loop unwinding the stack all along but doing actually nothing else in the process. Is that correct strategically? I think yes. But actually it didn't work no matter what I did.

So now I have removed the error flag and all the checks altogether. Instead, I suggest complete program exit on an error condition because even if the scheme worked, I wouldn't be able to correct mistakes in the input in most cases because BL does not allow me to fix up and redefine (re-enter) badly defined symbols (mostly lambdas).


Epilog:

I think I can only have one last try. I will reinstate the error flag but I will only bail out in response to it at the first line of just three major subs -- lispread, lispeval, and lispprint -- all other subs ignoring the current error state. It may prevent any deeper recursion in case of an error and cause actual surfacing in the main loop hopefully without running into a seg fault in some helper sub in the process.

I'll report my findings here. But if it doesn't help, I do not see any other way out except just quit on any error.


UPD My last attempt was successful. My words above that have been crossed out no longer apply. And I'm pretty happy with it.

[Mike Lobanovsky]

Charles,

A model for direct-string-safe tail-recursion:

You are posting wonderful things here indeed. But all of them are head- and hand-crafted by your personal human analysis of recursive fibo function. I think it would be a much greater challenge to program an AI routine to automatically recognize recursive patterns by certain criteria and automatically regroup them into iterative sequences. Such a routine would be in fact the Scheme compiler as it was described in that quotation from Scheme description on the net.

By the way, such policy looks like conspiracy and cheating to me. First they mesmerise you into twisting your brain with laborious recursive designs which would in fact be turned automatically into clean, simple, fast and easy to write iterative code. Isn't it what we would call fraud, do you think?

[Charles Pegge]

I suppose it is a misconceived attempt at mathematical purity. Recursion is vital for certain tasks such as expression analysis, but it is perverse to use it for simple iteration.

[Aurel]

Mike ..
this is exellent explanation..

0.3. There are over 550 instances of BSD (stack depth counter) incrementation throughout the code corresponding to GOSUB calls, and there will be an exact same amount of decrementations to keep the stack balanced. And all this in just one single cycle without going into any recursion or a nested call whatsoever. Going recursive will increase these numbers many times over. It means we will be executing many thousands of incrementations and decrementations over and over again for a slim chance of unlikely error in a piece of known working code. This will be a speed killer for any interpreter even if it runs compiled to machine code, e.g. like OxyLISP will.

Hmm..may i ask you something...
i have in plan to add in my small ruby-truby interpreter SUBS/FUNCS
do you can suggest me the best way (i mean speed wise) what i must do?
i see that you talk that stack is not best option ( i was used in AB ordinary array as stuck
which hold SUB positions)
thanks in advance
Aurel

/ps i would like to see FBSL code about that because looks more natural to me than SB/

[Mike Lobanovsky]

Charles,

BASIC Lisp is now working like a Swiss watch. 78 carefully placed IF eflag THEN RETURN commands have just done everything that was formerly done by over 550 bsd += 1 and over 160 bsd -= 1 commands in Arthur's original code. And no need for the ReturnLabel asm hack any more. The entire code will stay built around GOTO/GOSUB/RETURN commands.

Thank you very much indeed for having inspired me to make this very last attempt. It worked.

I have just proudly written your name into the list of credits in the FBLisp info blurb.

[Mike Lobanovsky]

Hi Aurel,

We are talking here about BASIC's process stack, not the "stack" of LISP code interpreter. LISP's "stack" is implemented in BL as a set of arrays similar to what you have in your own interpreter.

The fastest way for a program to work will be to have all its variables defined as globals, and all its program flow implemented with the old-skool GOTO and GOSUB/RETURN commands. They will be resolved by OxygenBasic directly to JMP and CALL/RET instructions, respectively. Genuine SUB/FUNCTION calls would lead to heavier penalties, speed-wise.

I will post the FBSL code and executable here very soon. Please wait a little and you'll have what you're asking for.

[Aurel]

ok Mike i will wait...and thanks!