Updating OxyScheme

[Mike Lobanovsky]

Hi Roland,

OxyScheme operators don't use direct literals (strings or numbers) for values or expression results. They rather operate on pointers to cell structures that resemble Variants in such languages as VB, VBA, FBSL, SB, etc. Cells can store numbers or strings in their corresponding member fields.

There are also four special cells to denote NIL, T, F, and EOF. Those don't have any specific numeric or string values. Instead, if some OxyScheme value or expression result points to such a cell, the value/result is considered equal to the corresponding special "value".

In fact, only one expression -- (quit) -- is expected to return a valid NIL explicitly, in which case the session Eval_Cycle loop should break and OxyScheme should exit its prompt altogether, which it currently doesn't. There seem to be some more expressions (presumably in nsinit.scm) that return an erroneous NIL that breaks Eval_Cycle prematurely on app start.

So in those equivalence macros, NIL, T, F stand for pointers to the respective special cells, and p stands for the pointer to the value cell being evaluated.

Otherwise, the O2 source code of OxyScheme uses C-style !0 (i.e. not equal to 0) as the value of TRUE throughout the entire script.

[Arnold]

Hi Mike,

thank you. Your source code is full of refinements. I am glad I did not try to understand o2scm.o2bas when you provided it, this would have been far beyond my abilities. In the meantime I reinstalled a distro of 2015 (A41) where I can execute o2scm.o2bas with #autodim off to compare the results. There are only minor changes in the current version of o2scm.o2bas, O2 is a bit stricter now, so I think it should be possible to find out the few differences.

I see that you created a type cell and use pointer arithmetic to store and fetch values to / from the members. Now that Oxygenbasic can handle types as parameters, maybe it makes sense to use this possibility? But right now this aspect is not that important.

Roland

[Mike Lobanovsky]

The OxyScheme code is a spitting image of its C prototype, and is therefore not very common to how it would look were it written in BASIC from scratch. Almost all ANSI C features can be implemented in O2 relatively easily but not vice versa. If we augment the O2 code with Oxygen-specific options, it will deviate from the prototype too far to be back-portable to FBSL's nanoscheme written in ANSI C and won't thus be usable for direct comparison purposes any more.

[Charles Pegge]

Hi Mike,

I wonder if NIL and F could be made identical safely. It would simplify the internal logic.

[Charles Pegge]

Hi Roland,

The definitions for istrue and isfalse require some extra brackets for explicit operator precedence

Code: [Select]

  #define istrue(p)  (((p) != NIL) && ((p) != F))
  #define isfalse(p) (((p) == NIL) || ((p) == F))


[Arnold]

Hi Charles,

I knew you already told me this and I finally found the link:

Macros as Functions: #return
https://www.oxygenbasic.org/forum/index.php?topic=1536.msg18180#msg18180

but then I had to interrupt. With your fix istrue / isfalse should work correctly in newer versions of Oxygen.

Now fib_fast.scm will return the correct results. Unfortunately garbage collection will crash o2scm. The app will crash in sub mark. I tried to follow the code with some print statements:

Code: [Select]

  sub mark(sys a)
  ===============
    sys t, q, p
printl "in sub mark"   
    t = 0
    p = a
E2:
printl "in E2"
    setmark(p)   
    if (isatom(p)) then goto E6
    q = car(p)
    if ((q != 0) && (ismark(q) == 0)) then
      setatom(p)
      car(p) = t
      t = p
      p = q
      goto E2
    end if
E5:
printl "in E5"
print ",t = " t "  --- Enter: " : waitkey
    q = cdr(p)
    if ((q != 0) && (ismark(q) == 0)) then
      cdr(p) = t
      t = p
      p = q
printl "from E5 to E2"     
      goto E2
    end if
E6:
printl "in E6"
print ",t = " t
    if (t == 0) then exit sub
    q = t
    if (isatom(q)) then
      clratom(q)
      t = car(q)
      car(q) = p
      p = q
 printl "from E6 to E5"     
      goto E5
    else
      t = cdr(q)
      cdr(q) = p
      p = q
printl "from E6 to E6" ': waitkey     
      goto E6
    end if
  end sub

Mark() will never exit the sub in E6: and will crash in E5: after some time. The procedure must be checked a bit more. But it is a bit late now and I have to take a little break.

Roland

This is a sample output:

> (load "fib_fast.scm")
loading fib_fast.scm
fibo*
fibonacci
#<EOF>
> (fibonacci 100)
gc start ...
in sub mark
in E2
in E2
in E2
in E6,t = 137595348
from E6 to E6
in E6,t = 5510696
from E6 to E5
in E5,t = 5510696  --- Enter:
in E6,t = 5510696
from E6 to E5
in E5,t = 137595348  --- Enter:
in E6,t = 137595348
from E6 to E6
in E6,t = 137595336
from E6 to E5
in E5,t = 137439027  --- Enter:        ==> crash

[Mike Lobanovsky]

Hi Charles,

No, F and NIL cannot be made identical because they denote different entities. One and the same boolean expression may return either F or NIL (e.g. in case a parameter is faulty or missing and the corresponding error isn't intercepted).

F refers to a value that resolves/amounts to 0/FALSE in math and boolean expressions. (T refers to any value except numeric 0 or boolean F)

NIL refers to an object that denotes an empty list, i.e. ().

You may regard NIL as a rough equivalent of ScriptBASIC uninitialized undef.

[Mike Lobanovsky]

Hi Roland,

Fibonacci is a deeply recursive function that exhausts the program stack very quickly. Interpreters (and Scheme is an interpreter) usually have a rather shallow preallocated program stack, which leads to its exhaustion, and hence, crash at large Fibonacci numbers.

A reasonable (and visibly slow to calc) limit to the argument would be (fibonacci 28) or smaller.

Please check if that value would still crash the garbage collector and let us know your results.

[Arnold]

Hi Mike,

with my machine after running o2scm.o2bas with O2 I can calculate (fibonacci 60) after loading fib_fast.scm (load must be the first command). The next input e.g. (fibonacci 5) will lead to gc_start (3 * Enter and crash).

#<EOF>
>  (load "fib_fast.scm")
loading fib_fast.scm
fibo*
fibonacci
#<EOF>
> (fibonacci 60)
2504730781961
> (fibonacci 5)
gc start ...
in sub mark
...

With o2scm in A41 I can calc up to (fibonacci 91). If I add in sub init_globals() like in the version of 0.2.8:
gc_verbose = 1

then I will also see gc_start when garbage collection begins:
> (fibonacci 91)
gc start ... done: 12948 cells recovered.
7540113804746346429

Btw: the values seem not to be correct with bigger numbers? Using two different online calculators I found these results:
fibo 60 =         1.548.008.755.920
fibo 91 = 4.660.046.610.375.530.309

fibo 28: fib_fast.scm in o2scm=514229, fib_fast.scm in in Tinyscheme: also 514229, online calc=317811. But at the moment I do not know the correct answer.

Roland

[Mike Lobanovsky]

Roland,

Re. fib & fib_fast calc: Your online calc seems to be wrong. Both fib and fib_fast display 514229,  2504730781961, and (almost) 7540113804746346429 when run in online Scheme compilers for 28, 60, and 91, respectively. (see below)

Re. large Fibonacci numbers: OxyScheme registers and its display (in fact, print) routine handle only up to 64 bit-long numbers (long long ints and double-precision reals). If any intermediate calc involved in obtaining the final result overflows, then the final result is going to also be wrong. There is currently no error flagging of register and/or value overflow.

[Arnold]

Thank you, Mike. I think this is a helpful info, because I can now assume that most of the routines work similar in o2scm.o2bas of version 0.2.8 compared to o2scm_03_2015.o2bas of version A 41.

I added the same print statements in o2scm.o2bas of A41. A 41 will not crash after the 3rd waitkey. If I comment out the waitkey statement, I can see that garbage collection will succeed after many cycles.

With A41 the flow is: E2,E2,E2,E6, E5,E6, E5,(t=0),E2,E2,E2,E6,E5 etc.
With version 0.2.8   : E2,E2,E2,E6, E6,E5, E6         ,E5,E6,E6,E5    crash

I am a bit confused about the value of t in E6 (t in v0.2.8 is about 10 times bigger than t in A 41). The flow of A41 is also different after E6 compared to v0.2.8. Does clratom or another macro in sub mark() work differently?

Roland

[Mike Lobanovsky]

Scheme's program stack is in fact a linked list of cells that comprise:
-- a flag to denote a used cell's type, or a mark for garbage collection, or a free cell;
-- two unions to store string or numeric values; and
-- two address fields (_car and _cdr) to point to the preceding and next cells, respectively, in the doubly linked list.

What GC does is iterate through the entire linked list following each cell's _car and _cdr pointers to spot cells marked with a flag for garbage collection, clear their values and flags, and possibly rearrange the newly freed cells into contiguous blocks of program free memory by changing their _car and _cdr pointers to the adjacent (closest) free cells.

I'd suggest asking Charles to check if the garbage collection routines (all of them) that use pointer access, for compliance with modern O2 pointer notation.

The difference in t values should not bother you much because it is a temporary pointer value that depends on which program memory cell exactly the garbage collector is currently dealing with. Since different builds of O2 are very likely to allocate program memory in different areas of RAM, the pointer values are going to differ accordingly.

[Arnold]

Somehow I think, that some of the #define macros starting at about line 164 might need extra brackets like the istrue / isfalse macros? But if this should be the case, I have no idea at the moment how to proceed to verify this.

[Charles Pegge]

The problem occurs with macros used inside an expression, and I did not see any others requiring extra brackets. I should be able to fix this in o2  by passing all the macro sources through the 'precedenter ' before storing.

But istrue and isfalse can be implemented more efficiently by using asm calls:

Code: [Select]

  '#define istrue(p)  (((p) != NIL) && ((p) != F))
  '#define isfalse(p) (((p) == NIL) || ((p) == F))
  #define istrue(p) call istrue_asm(p)
  #define isfalse(p) call isfalse_asm(p)

 ... 'append to o2 asm helper functions

.istrue_asm
  mov eax,0
  mov ecx,[esp+4]
  (
    cmp ecx,NIL
    jnz exit
    ret 4
  )
  (
    cmp ecx,F
    jnz exit
    ret 4
  )
  mov eax,-1
ret 4

.isfalse_asm
  mov eax,-1
  mov ecx,[esp+4]
  (
    cmp ecx,NIL
    jnz exit
    ret 4
  )
  (
    cmp ecx,F
    jnz exit
    ret 4
  )
  mov eax,0
ret 4


[Charles Pegge]

Comparing Scheme code with Basic code:

Code: [Select]

'12:44 09/11/2019
'sheme and basic compare
'(define fibo*
'   (lambda (a b x)
'     (if (= x 0) a
'        (fibo* b (+ a b) (- x 1)))))
'
function fibo(int a,b,x) as int
  if x=0 then return a else return fibo(b,a+b,x-1)
end function