## Liberation through Computer Literacy

Heater
Posts: 16869
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

ScriptBasic,
I ran the Fibonacci Scheme code you posted running with Elk in TinyScheme and it produced the correct answer. What are your thoughts?
I'm not sure what you are asking exactly. But here goes:

Tiny Scheme is useless for the fibo challenge as it can't produce exact results bigger than fibo(70)

Even as an inexact result that is pretty poor as we should get to fibo(78) with 64 bit floats.

Using the complexity of the fast fibo algorithms for such small values of n makes no sense.

Elk Scheme is better, it gets us the correct fibo(4784969) in three and a half minutes on my PC.

I don't get the point of having an extension module for ScriptBasic to run Scheme (or any similar program), why not just use a generic "system" function to run a Scheme engine passing it the string to run?

Actually using Scheme from inside ScriptBasic like that must be hard, how do you develop/debug it?
Memory in C++ is a leaky abstraction .

ejolson
Posts: 6039
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

Heater wrote:
Sat May 25, 2019 8:01 pm
Odd that, I have been rounding up Scheme engines. Got Racket and Chibi, today it was Chez Scheme and Guile.
I've been scheming with

Code: Select all

``````(define (fibo n)
(cond ((= n 0) 0) ((= n 1) 1) (else
(let* ((k (quotient n 2)) (a (fibo k)) (b (fibo (- k 1))))
(if (even? n) (* a (+ (* 2 b) a))
(let ((c (* (+ (* 2 a) b) (- (* 2 a) b))))
(if (= (modulo n 4) 1) (+ c 2) (- c 2))))))))

(define (fiborun n)
(if (= n 0) (exit) (fibo n)))

(define (fiboloop)
(display "? ")
(display "\n")
(fiboloop))

(fiboloop)``````
which is working fine under the fibench timing framework with Racket and Guile, except Racket gets the answer for fibo(61403) wrong.

Unfortunately, I can't find Chez or Chibi in the Raspbian repository. Did you compile these from source?

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

Heater wrote: I don't get the point of having an extension module for ScriptBasic to run Scheme (or any similar program), why not just use a generic "system" function to run a Scheme engine passing it the string to run?

Actually using Scheme from inside ScriptBasic like that must be hard, how do you develop/debug it?
The TinyScheme extension allows me to load Scheme functions and call them from ScriptBasic. It also allows me to learn Scheme without the all or nothing approach. It's really easy to add C functions to TinyScheme. Checkout the MySQL extension for TinyScheme. It's designed to be embedded. (like ScriptBasic)

TinyScheme is the scripting engine in GIMP.

I'm curious. How often do you need to exceed the hardware's precision limitation and emulate large integers?
Last edited by John_Spikowski on Tue May 28, 2019 5:35 am, edited 8 times in total.

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

@ejolson,

Your code works fine in TinyScheme.

Code: Select all

``````IMPORT ts.inc

sc = TS_New()
ts_src = """
(define (fibo n)
(cond ((= n 0) 0) ((= n 1) 1) (else
(let* ((k (quotient n 2)) (a (fibo k)) (b (fibo (- k 1))))
(if (even? n) (* a (+ (* 2 b) a))
(let ((c (* (+ (* 2 a) b) (- (* 2 a) b))))
(if (= (modulo n 4) 1) (+ c 2) (- c 2))))))))

(display (fibo 78))
(newline)

"""
PRINT FORMAT("%.0f",TS_Cmd(sc, ts_src)),"\n"
TS_Close sc

jrs@jrs-laptop:~/sb/examples/test\$ time scriba fibo_eots.sb
8944394323791464

real	0m0.017s
user	0m0.013s
sys	0m0.004s
jrs@jrs-laptop:~/sb/examples/test\$
``````

Heater
Posts: 16869
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

ejolson,

That racket fibo above works fine with my Racket on my PC:

Code: Select all

``````\$ racket -v
Welcome to Racket v6.7.
\$ racket fibo.racket.scm | head -c 32
13139815501987632955443253884681
... Snipped meessage about broken pipe here.
\$ racket fibo.racket.scm | tail  -c 32
5447320687563816790578645433977
\$
``````
I did a diff off the full output against the Python fibo. No problem.

All the language systems I used come from apt-get or are built from source.

The odd ball was GNU Smalltalk which gave incorrect results from apt-get but correct from my source build.

What is it about some programmers, they have the desperate urge to stuff everything into as few lines as possible thus obfuscating the codes operation and confusing the socks of the likes of me?
Memory in C++ is a leaky abstraction .

ejolson
Posts: 6039
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

Heater wrote:
Tue May 28, 2019 6:25 am
ejolson,

That racket fibo above works fine with my Racket on my PC:

Code: Select all

``````\$ racket -v
Welcome to Racket v6.7.
\$ racket fibo.racket.scm | head -c 32
13139815501987632955443253884681
... Snipped meessage about broken pipe here.
\$ racket fibo.racket.scm | tail  -c 32
5447320687563816790578645433977
\$
``````
I did a diff off the full output against the Python fibo. No problem.

All the language systems I used come from apt-get or are built from source.

The odd ball was GNU Smalltalk which gave incorrect results from apt-get but correct from my source build.

What is it about some programmers, they have the desperate urge to stuff everything into as few lines as possible thus obfuscating the codes operation and confusing the socks of the likes of me?
Sorry for confusing your socks, I reformatted the Scheme code so the parenthesis looked more appetising, at least to me. Brutally making it more compact also provided room on my screen for the interactive input and output routines needed for fibench.

The error I found could be a problem with the ARM version of Racket in Raspbian. The million-digit Fibonacci is fine, but not the one I mentioned. I'll rerun the test on an x86 machine to see what happens.

Update: Indeed Racket works fine on x86 but unfortunately not on Raspberry Pi with Raspbian. Do you know if the 64-bit ARM Racket executable works?

Heater
Posts: 16869
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

Racket Scheme calculates fibo (61403) perfectly on my Pi 3 running 64 bit Debian.

Code: Select all

``````\$ uname -a
Linux pi64-aalto 4.11.12-pi64+ #1 SMP PREEMPT Sun Jul 30 20:18:20 CEST 2017 aarch64 GNU/Linux
pi@pi64-aalto:~\$ ^C

pi@pi64-aalto:~\$ time racket fibo.racket.scm | head -c 32 ; time racket fibo.racket.scm | tail -c 32
13139815501987632955443253884681
real    0m1.846s
user    0m1.660s
sys     0m0.189s
65447320687563816790578645433977
real    0m1.824s
user    0m1.625s
sys     0m0.202s
pi@pi64-aalto:~\$
``````
fibo(4784969) is pretty speedy on the Pi 3:

Code: Select all

``````pi@pi64-aalto:~\$ time racket fibo.scm | head -c 32 ; time racket fibo.scm | tail -c 32
10727395641800477229364813596225
error writing to stream port
system error: Broken pipe; errno=32

real    0m16.169s
user    0m15.920s
sys     0m0.249s
74856539211500699706378405156269
real    0m16.257s
user    0m16.011s
sys     0m0.233s
pi@pi64-aalto:~\$
``````
Memory in C++ is a leaky abstraction .

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

There wasn't much interest in Elk on the AllBasic.info forum so I'm going to complete the TinyScheme API interface to allow C function use.

ejolson
Posts: 6039
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

Heater wrote:
Tue May 28, 2019 10:14 am
Racket Scheme calculates fibo (61403) perfectly on my Pi 3 running 64 bit Debian.

Code: Select all

``````\$ uname -a
Linux pi64-aalto 4.11.12-pi64+ #1 SMP PREEMPT Sun Jul 30 20:18:20 CEST 2017 aarch64 GNU/Linux
pi@pi64-aalto:~\$ ^C

pi@pi64-aalto:~\$ time racket fibo.racket.scm | head -c 32 ; time racket fibo.racket.scm | tail -c 32
13139815501987632955443253884681
real    0m1.846s
user    0m1.660s
sys     0m0.189s
65447320687563816790578645433977
real    0m1.824s
user    0m1.625s
sys     0m0.202s
pi@pi64-aalto:~\$
``````
fibo(4784969) is pretty speedy on the Pi 3:

Code: Select all

``````pi@pi64-aalto:~\$ time racket fibo.scm | head -c 32 ; time racket fibo.scm | tail -c 32
10727395641800477229364813596225
error writing to stream port
system error: Broken pipe; errno=32

real    0m16.169s
user    0m15.920s
sys     0m0.249s
74856539211500699706378405156269
real    0m16.257s
user    0m16.011s
sys     0m0.233s
pi@pi64-aalto:~\$
``````
I'm currently a little disappointed with how Racket works on that \$5 computer that came with a magazine subscription. Running the code

Code: Select all

``````#!/usr/bin/racket
#lang racket

(define (fibo n)
(cond ((= n 0) 0) ((= n 1) 1) (else
(let* ((k (quotient n 2)) (a (fibo k)) (b (fibo (- k 1))))
(if (even? n) (* a (+ (* 2 b) a))
(let ((c (* (+ (* 2 a) b) (- (* 2 a) b))))
(if (= (modulo n 4) 1) (+ c 2) (- c 2))))))))

(display (fibo 61403))``````
results in the following

Code: Select all

``````\$ time ./f61403.sh >f61403.out

real    0m6.010s
user    0m4.290s
sys 0m0.900s
\$ head -c32 f61403.out ; echo
13139815501987631394568978726685
\$ head -c32 classic.out ; echo
13139815501987632955443253884681``````
While most of the 6 seconds is run-time startup and excusable, the wrong answer less so. With wild scheme interpreters, just like wild horses, once adopted a person is forever responsible for their well being. Do you think a different kind of hay would help?

Heater
Posts: 16869
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

I don't know about hay but we have now found two failures in interpreters and big integers on Raspbian: Racket Scheme and GNU Smalltalk, it's time to file some bug reports.

But where to file them? Raspbian maintainers, the Debian maintainers, upstream?
Memory in C++ is a leaky abstraction .

ejolson
Posts: 6039
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

Heater wrote:
Tue May 28, 2019 4:22 pm
I don't know about hay but we have now found two failures in interpreters and big integers on Raspbian: Racket Scheme and GNU Smalltalk, it's time to file some bug reports.

But where to file them? Raspbian maintainers, the Debian maintainers, upstream?
Horses always prefer upstream--I'm not so sure about interpreters. Here is another data point: Racket runs fine on 32-bit Intel architecture.

Heater
Posts: 16869
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

ejolson,
Horses always prefer upstream...
So do I.

However in the case of GNU SmallTalk I found that building from latest upstream sources resulted in a working big integer fibo. Clearly upstream would not be interested in hearing about a problem they don't have. That means somebody down stream needs to be told to stop shipping a buggy build of GNU Smalltalk. Is that the Raspbian folks or the Debian folks?

Perhaps the same applies to Racket.
Racket runs fine on 32-bit Intel architecture.
Ah, that was going to be my next question.

You sure you have the same Racket version on that 32 bit machine?

Curiouser and curiouser.
Memory in C++ is a leaky abstraction .

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

What Fibonacci has done for me.

* Stress test ScriptBasic's dynamic array stucture.

* Renew my interest in an expanded Scheme integration with ScriptBasic.

* An education in BIGINT and the languages that support it. The GMP library is a great resource if the need arises.

* I have wasted a lot of time on this topic / challenge.

Heater
Posts: 16869
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

ScriptBasic,

Fibonacci just keeps giving...

It has stressed at least two language implementations, supplied with Raspbian, to breaking point.

As for wast of time... it's half a year now and I'm still tinkering with the damn thing. With the off hand mention of a challenge I made a rod for my back.

I'm still wondering about this Scheme integration with BASIC idea ... I'm familiar with integrating languages into applications so as to provide the user with a means of customizing/configuring things. Been there, done that. But integrating a language into another language seems like a different thing to me.

It's a neat trick but:

What I have seen so far is not what I would call "integration". Can Scheme use variables and functions from ScriptBasic? Or vice versa?

As a means of learning Scheme it seems clunky. A Scheme string as a comment in BASIC means there is no user interaction with Scheme, like the usual REPL command line they provide. Editors cannot syntax highlight the Scheme or show how brackets match up or not. And so on.

How do Scheme error messages come out? If they do how does one match them up with the lines of Scheme comment in the BASIC?

Addressing all these things seems like a lot of work to me. Who would use it?

Sorry to sound so negative about it. Perhaps I just don't get the idea that you have.
Memory in C++ is a leaky abstraction .

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

What I have done with the TinyScheme integration is just minimal to get it running (3 functions) Take a look at the TinyScheme full API then you will understand the integration of the two languages. Both being embedded solutions makes this task rather easy compared to other languages.

The main theme here is dynamic runtime scripting with a seamless integration.

The V7 Javascript extension module would have been a good example of SB integration with a secondary language but it only runs on 64 bit Linux and the library is deprecated.

Heater
Posts: 16869
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

You might want to look at JerryScript http://jerryscript.net/ for an embedded Javascript implementation.

How would you handle the event loop of Javascript?
Memory in C++ is a leaky abstraction .

ejolson
Posts: 6039
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

Heater wrote:
Tue May 28, 2019 6:25 am
All the language systems I used come from apt-get or are built from source.
After I broke my Racket, I downloaded Chibi Scheme from the site

https://github.com/ashinn/chibi-scheme

typed "make" and then as root "make install" with the result

Code: Select all

``````echo "Generating images"
Generating images
cd / && LD_LIBRARY_PATH="/usr/local/lib:" DYLD_LIBRARY_PATH="/usr/local/lib:" CHIBI_MODULE_PATH="/usr/local/share/chibi:/usr/local/lib/chibi" /usr/local/bin/chibi-scheme -d /usr/local/share/chibi/chibi.img
Segmentation fault
Makefile:413: recipe for target 'install' failed
make: *** [install] Error 139``````
This was on a Raspberry Pi B+ running the latest version of Raspbian. It appears Chibi Scheme has escaped the roundup for now.

As a replacement Elk Scheme is currently computing Fibonacci numbers with neither the speed of a wild horse nor an antelope.

Code: Select all

``````\$ ./configure
no suitable machine type found
try rerunning as ./configure -m=<machine type>
available machine types: a6le, a6nt, a6osx, i3le, i3nt, i3osx, ta6le, ta6nt, ta6osx, ti3le, ti3nt, and ti3osx``````
I found a link online describing how to cross-compile Chez scheme for ARM Android assuming you already have it installed on an Intel architecture machine.

Update: After computing a few numbers successfully Elk Scheme just output

Code: Select all

``Panic: Visit: object not in prev space at 0xb6bc84d0 ('pair') 705 707 (dumping core).``
The core dump appears to be dependent on the order of the Fibonacci numbers computed. The sequence in n which led to the crash was

Code: Select all

``````7499
3023
32
65089
17
15368
321
82985
3
600
10
76
2018
1186
1
195
2149831
0
``````
Note it crashes while trying to compute fibo(2149831); however, if fibo(2149831) is computed first there is no crash. In keeping with the present theme, there is no crash when running on x86 regardless of whether fibo(2149831) is computed first or last.

Out of five Schemes Chibi and Chez failed to compile on the Raspberry Pi, Elk crashed, Racket gave wrong answers and Guile ran fine. That's not much of a roundup so far.
Last edited by ejolson on Wed May 29, 2019 1:09 am, edited 9 times in total.

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

Have you tried to install TinyScheme and run it from the console? No BIGINT support so you might not be interested.

You would think someone would have created a BIGINT library for Scheme written in Scheme.i might take a peek how Elk implemented it.

ejolson
Posts: 6039
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

From what I've read Tiny Scheme is missing essential features. For example here one finds the remark that
kishi wrote:Chibi is about the same size, and unlike TinyScheme is a real Scheme with hygienic macros and a fast VM (TinyScheme is hopelessly slow). It also has features like Huffman compressed immediate symbols to further reduce runtime heap usage - the raw image size isn't the whole story.
Now, getting back to the bugs,
ejolson wrote:
Tue May 28, 2019 11:16 pm
Out of five Schemes Chibi and Chez failed to compile on the Raspberry Pi, Elk crashed, Racket gave wrong answers and Guile ran fine. That's not much of a roundup so far.
For the record Racket also gives wrong answers on a Pi 3B and Elk still crashes in exactly the same way as on the Zero. The version of Racket is 6.7-3 armhf and the version of Elk is 3.99.8-4.1 armhf.

The results of all this scheming has reminded me of this thread.

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

That seems depressing. Linux 32 bit is a dying environment no one wants to invest in anymore.

You may want to add the following to you gcc command line for ARM.

-fsigned-char

Heater
Posts: 16869
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

ScriptBasic,
Have you tried to install TinyScheme and run it from the console? No BIGINT support so you might not be interested.
TinyScheme is said to be "hopelessly slow" see above. Chibi is said to be much faster which may well be true but Chibi is already one of the slowest Schemes available. See Scheme benchmarks here: https://ecraven.github.io/r7rs-benchmarks/
You would think someone would have created a BIGINT library for Scheme written in Scheme.i might take a peek how Elk implemented it.
It crossed my mind to attempt creating Karatsuba in Tiny Scheme so as to get it to complete the Fibo challenge. That would at least be a good exercise in learning Scheme. However it would be so mind bendingly slow that I'm put off the idea.

I guess that nobody has created a BIGINT library in Scheme because most Schemes already handle big integers just fine. As a high level language should.
Memory in C++ is a leaky abstraction .

Heater
Posts: 16869
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

Chibi Scheme builds and runs fine on my Pi 3 with 64 bit Debian:

Code: Select all

``````pi@pi64-aalto:~/fibo_4784969/scheme\$ time chibi-scheme fibo.chibi.scm | head -c 32
10727395641800477229364813596225
real    33m57.496s
user    33m56.368s
sys     0m0.925s
``````
Interestingly that is only half the speed of running on my 64 Intel PC:

Code: Select all

``````\$ time chibi-scheme fibo.chibi.scm | head -c 32
10727395641800477229364813596225
real    16m9.022s
user    16m0.141s
sys     0m0.234s
``````
Usually I expect to see a PC/Pi performance ratio of about 10.
Memory in C++ is a leaky abstraction .

ejolson
Posts: 6039
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

Heater wrote:
Wed May 29, 2019 5:46 am
Chibi Scheme builds and runs fine on my Pi 3 with 64 bit Debian
That's good to know. I'll try on my Pi 3 under Raspbian next. Elk Scheme on 64-bit ARM also crashes here. Details are

Code: Select all

``````\$ cat input.txt | ./elk.sh >output.txt

Panic: Visit: object not in prev space at 0x7fb0fea4d0 ('pair') 705 707 (dumping core).
./elk.sh: line 2: 21987 Aborted                 elk -l elk.sc
\$ cat elk.sh
#!/bin/bash
elk -l elk.sc
\$ cat elk.sc
(define (fibo n)
(cond ((= n 0) 0) ((= n 1) 1) (else
(let* ((k (quotient n 2)) (a (fibo k)) (b (fibo (- k 1))))
(if (even? n) (* a (+ (* 2 b) a))
(let ((c (* (+ (* 2 a) b) (- (* 2 a) b))))
(if (= (modulo n 4) 1) (+ c 2) (- c 2))))))))

(define (fiborun n)
(if (= n 0) (exit) (fibo n)))

(define (fiboloop)
(display "? ")
(display "\n")
(fiboloop))

(fiboloop)
\$ cat input.txt
7499
3023
32
65089
17
15368
321
82985
3
600
10
76
2018
1186
1
195
2149831
0
\$ uname -a
Linux matrix 4.4.49-s5p6818 #1 SMP PREEMPT Fri Mar 23 15:29:14 HKT 2018 aarch64 aarch64 aarch64 GNU/Linux``````
Unsurprisingly, the same does not crash on either 32-bit or 64-bit Intel architectures. If you have the time I'd greatly appreciate it if you tried Elk on your ARM64 Debian distribution to see if you can reproduce the crash.

ejolson
Posts: 6039
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

ejolson wrote:
Wed May 29, 2019 6:59 am
Heater wrote:
Wed May 29, 2019 5:46 am
Chibi Scheme builds and runs fine on my Pi 3 with 64 bit Debian
That's good to know. I'll try on my Pi 3 under Raspbian next.
Trying to build Chibi on the Pi 3 under Raspbian ran into the same install-time crash as with the Zero. Then I built on 64-bit ARM and everything went fine. Finally, I copied over the three .img files from /usr/local/share/chibi on the 64-bit system to the Raspbian system and everything seems to work. Woohoo! Now there are enough Schemes.

Heater
Posts: 16869
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

I get the same error with your code and input data as shown above. Using Elk installed from apt-get on Pi 64 Debian:

Code: Select all

``````pi@pi64-aalto:~/fibo_4784969/scheme\$ elk -l  fibo.elk.sc
? 195
25299086886458645685589389182743678652930
...
... typed all the test numbers manually...
...
? 2149831

Panic: Visit: object not in prev space at 0x7f91b384d0 ('pair') 705 707 (dumping core).
Aborted
pi@pi64-aalto:~/fibo_4784969/scheme\$ elk -l  fibo.elk.sc
? 2149831
...
...7847308053219469
? 0
pi@pi64-aalto:~/fibo_4784969/scheme\$
``````
Memory in C++ is a leaky abstraction .