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

Re: A Final Fibonacci Challenge

Sun May 26, 2019 6:58 am

scruss wrote:
Sat May 25, 2019 9:04 pm
ejolson wrote:
Sat May 25, 2019 6:12 pm
I'm wondering whether it is possible to build Richard's interpreter without the SDL libraries. Even if not, can the resulting programs still be tamed to run from an ssh login without a monitor attached?
BBCSDL can't, but Matrix Brandy can. You can build console-only versions with its makefile.text
Thanks! I now have Matrix Brandy Basic running on my Pi Zeros.

For those who have recently joined, the present thread is a continuation of this previous thread entitled "Why Avoid Basic?" that focused on what characteristics a good first programming language should have and whether modern versions of Basic possessed those characteristics. While some might claim the exact programming language doesn't matter and it's better to begin learning the computer science using whatever means are available without further delay, it is also reasonable to write programs using the various languages to determine whether those languages really are equally suitable for the beginner or whether some are more suitable than others.

Rather than making things up for the sake of having an interesting conversation, it is expedient to recall what insights have already been provided by the successful pioneers of the past. As discussed in this forum post, the efforts of Kemeny and Kurtz are notable for creating a revolution in interactive computing at Dartmouth College that led to widespread computer literacy. While poking fun of the Basic programming language itself is tempting, it is perhaps more productive to discuss the design goals set forth in the 1964 preface to the first draft of the Basic instruction manual.
BASIC Instruction Manual wrote: When plans were made for the Dartmouth College time-sharing system, which will enable 20 or more people to use the computer at the same time, the need arose for a language to meet several requirements:

1. It should be very easy to learn. This will enable faculty and students to obtain useful information from the computer without an undue investment in learning machine languages.

2. It should be possible to change programs from this language to the language of the machine ("compile") quickly. This is a necessity when twenty people share the time of the computer.

3. It should be a stepping-stone for students who may later wish to learn one of the standard languages, such as FORTRAN or ALGOL.

4. It should be a general purpose language; that is, every kind of machine computation should be programmable in it.
Having said this, I've now have versions of the classic.bas Fibonacci code that work with four different Basic interpreters: bwBasic, ScriptBasic, Matrix Brandy Basic and gplBasic. A graph depicting the relative performance of these interpreters will appear in an upcoming post. For now note that the changes needed to adapt classic.bas for bwBasic were posted above and the changes needed for ScriptBasic were posted here. The changes for classic.bas to run under the other two Basic interpreters are as follows:

Matrix Brandy Basic

The sbrandy version of the interpreter was used which reads from standard input and writes to standard output. In order to run under Matrix Brandy Basic, the classic.bas program was converted to uppercase. Then, all occurrences of "LOG" were replaced with "LN" and finally line 290 was changed to read

Code: Select all

290 M0=1:INPUT "? " N:IF N=0 THEN STOP
To run the resulting code under the fibench timing framework, the pipe trick was needed to prevent the interpreter from manually echoing the input number n to standard output. Moreover, as the interpreter uses a 640K workspace by default, the workspace size needed to be increased using a command-line option. The resulting run script looked like

Code: Select all

#!/bin/bash
cat | sbrandy -size 48000000 brandy.bas
gplBasic

The gplBasic interpreter appears to be the effort of a single person named Lennart Benschop. It was downloaded from

http://www.xs4all.nl/~lennartb/gplbasic.tar.gz

and patched as follows:
  • In main.c line 8 replace string.h by signal.h
  • In main.c line 78 replace for(;;) by for(;argc>2;)
The only changes needed for classic.bas to run were

Code: Select all

1080 if p1=1 or p1=3 then 1200
7046 if mid$(s$,len(s$),1)=" " then s$=mid$(s$,1,len(s$)-1)

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

Re: A Final Fibonacci Challenge

Sun May 26, 2019 7:57 am

ejolson,

But, wha' wha' what just happened? My whole time-space continuum seems to have been sucked into a singularity. Here on the other end of the worm hole everything looks eerily familiar, even if everything that was inside is now outside, and vice versa, and time is running backwards...

There once was a thread about avoiding BASIC that contained within it a multi-language big Fibonnaci number calculating challenge. Now I find myself in a thread about the Fibonacci challenge has morphed into an avoiding BASIC thread...

Every new version of the fibo challenge solution, tweaked for a different variant of BASIC, is yet another reason to avoid BASIC.

I'm inclined to say the same about Scheme now that I have managed to tweak the solution to run under four or five different Scheme dialects. But at least Scheme has some semblance of a standard. https://small.r7rs.org/attachment/r7rs.pdf

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

Re: A Final Fibonacci Challenge

Sun May 26, 2019 4:32 pm

Heater wrote:
Sun May 26, 2019 7:57 am
But, wha' wha' what just happened?
While you were rounding up Scheme interpreters, I was rounding up Basic interpreters. Since Bywater, Chez, Chibi, Gpl, Guile, Matrix Brandy, Racket and Script each descended after they escaped into the wild from languages designed for teaching, they are all members of the same herd.

Here are the results of the first Fibonacci roundup:

Image

All timings were performed using the Raspberry Pi Zero.

As with wild horses, some run faster, some are stronger, while others have curly manes.

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

Re: A Final Fibonacci Challenge

Sun May 26, 2019 6:36 pm

ejolson,

I pretty sure Scheme was not created as a teaching language. However as I watch Brian Harvey bring his Berkeley CS undergrads up to speed in his "Structure and Interpretation of Computer Programs" course in 2010 it seems to work very well in that role:
https://www.youtube.com/watch?v=4leZ1Ca ... NKG1b-LFY9

I have no idea how well it might work for young kids mind.

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

Re: A Final Fibonacci Challenge

Sun May 26, 2019 8:31 pm

Heater wrote:
Sun May 26, 2019 6:36 pm
I pretty sure Scheme was not created as a teaching language.
This link contains surprisingly useful information on using Scheme in an educational setting.

Though developed at MIT, Scheme was also popular at many other universities for introductory computing courses. I always assumed the irritating simplicity was for pedagogical reasons. After reading a bit, it seems Scheme was actually created as research into lambdas and closures with a bit of lexical scoping on the side.

Relevant to the present discussion is that according to
Wikipedia wrote:the Scheme Steering Committee calls it "the world's most unportable programming language" and "a family of dialects" rather than a single language.
Consequently, it is not surprising modifications had to be made to run the same code under different interpreters. Given the length and complexity of the line-numbered Fibonacci code, the modifications needed for bwBasic, Matrix Brandy Basic and gplBasic were, in my opinion, quite minor.

It would be amusing to see how those wild Scheme interpreters compare in a second Fibonacci roundup. Maybe a third roundup could consist of Python 2, Python 3, Cython and PyPy.

When the are too many compilers and interpreters, they start starving for developers. Although a helicopter may not help when managing the overpopulation of programming languages, maybe a Fibonacci challenge could help control the number of wild horses.

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

Re: A Final Fibonacci Challenge

Sun May 26, 2019 10:30 pm

ejolson,

As far as I can tell Scheme is mostly inspired by Lisp and ALGOL. I haven't decided if that is a match made in heaven or a scary Frankenstein's monster yet.

I'm strangely attracted to it's irritating simplicity. On the other hand that almost total lack of syntax makes it hard for me to follow.

That comment by the Scheme Steering Committee was made 10 years ago. I wonder if the Scheme community has managed to pull things together since then, or did it fragment even more?!

At least there is a standard, and it's latest incarnation seemed to garner quite some support. I think I have discovered that Scheme written to that standard requires only very minimal changes to get quite a few dialects to accept it. But I don't really have a big enough piece of code here to check that out much.

A Scheme interpreters round up would be great. As would a Python round up. To that end, do you have a scripted/automated way to make those graphs? It would be nice for a consistent in presentation.

User avatar
John_Spikowski
Posts: 1310
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sun May 26, 2019 11:36 pm

This link contains surprisingly useful information on using Scheme in an educational setting.
I think the combination of BASIC and Scheme working together as one is a great environment to learn programming. I'm looking forward to Elk Scheme being an extension module soon for ScriptBasic.

User avatar
John_Spikowski
Posts: 1310
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Mon May 27, 2019 2:49 am

@ejolson,

I think it would be worth creating a table of languages for a fibo(78) comparison. ScriptBasic executes fibo(78) in .006 seconds on a RPi 3B. It's probably going to come in last running your classic.bas for 1 mil digits. (thrashing 1.7 million element dynamic variant array)

Is there a way to use a string rather than an array to store the resulting numeric string? What is the max length an element could be?

With SB you can do math functions / expressions using numeric strings.

Code: Select all

s = "987654321"
k = 32 * MID(s,7,2)

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

Re: A Final Fibonacci Challenge

Mon May 27, 2019 4:52 am

ScriptBasic wrote:
Mon May 27, 2019 2:49 am
I think it would be worth creating a table of languages for a fibo(78) comparison. ScriptBasic executes fibo(78) in .006 seconds on a RPi 3B. It's probably going to come in last running your classic.bas for 1 mil digits. (thrashing 1.7 million element dynamic variant array)
If you examine the graph you will notice that the asymptotic regime for the classic.bas Fibonacci calculation doesn't set in until about fibo(1000). Therefore, any numbers smaller than that do not reflect the time complexity of computing the Fibonacci doubling formulas by means of Karatsuba multiplication. It is also clear from that graph that ScriptBasic is not the slowest interpreter in the roundup. That honor goes to bwBasic. This is not so surprising given that
bwbasic.doc wrote:Whenever faced with a choice between conceptual clarity and speed, I have consistently chosen the former.
Contrary to what is taught in school, performance is often the deciding factor that leads to the success of one software product over another. Examples are the Linux kernel and systemd: There would be almost no interest in either if each didn't exhibit best-in-class performance. In particular, the speed of bwBasic itself was likely more important than the speed of the Beaumont to Port Arthur commuter train when explaining why Mrs Verda Spell never managed to undercut Microsoft's entire market and build a new software empire.

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

Re: A Final Fibonacci Challenge

Mon May 27, 2019 5:17 am

ScriptBasic,
I think the combination of BASIC and Scheme working together as one is a great environment to learn programming.
I'd be interested to hear on what basis you think that. I would have thought that a beginner to programming has enough to assimilate with just one language.

ELK Scheme? Hmm... YAFS. Ah well, let's see:
$ sudo apt-get install elk
$ time elk -l fibo.scm | head -c 32 ; time elk -l fibo.scm | tail -c 32
10727395641800477229364813596225
real 3m31.586s
user 3m29.688s
sys 0m0.125s
4856539211500699706378405156269

real 3m30.693s
user 3m29.500s
sys 0m0.141s
On my Intel PC. The good news is that it runs the "vanila" fibo Scheme code unmodified:

Code: Select all

; Fibonacci using fast doubling formulas, good for millions of digits!
(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*
                        (
                            (2a (* 2 a))
                            (c (* (+ 2a b) (- 2a b)))
                        )

                        (if (= (modulo n 4) 1)
                            (+ c 2)
                            (- c 2)
                        )
                    )
                )
            )
        )
    )
)

User avatar
John_Spikowski
Posts: 1310
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Mon May 27, 2019 5:37 am

Should I assume that Elk meets your approval?

How does Elk compare with other Scheme languages you have tried?

What is the time for the Python version on your PC?
Last edited by John_Spikowski on Mon May 27, 2019 5:59 am, edited 2 times in total.

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

Re: A Final Fibonacci Challenge

Mon May 27, 2019 5:39 am

ScriptBasic,
I think it would be worth creating a table of languages for a fibo(78) comparison.
Huh? Adding up a handful of integers sounds like the most useless benchmark I ever heard of. Might have been eye oppening in the days of the ENIAC.
Is there a way to use a string rather than an array to store the resulting numeric string?
Many people have implemented the Karatsuba multiplication algorithm using strings. A million digit number being just a string of a million ASCII digits. It's a common student exercise. Here is a short sweet example: https://codereview.stackexchange.com/qu ... iplication

It's going to be slow of course. Very slow. Maybe it is faster than integer arrays in ScriptBasic though. Be interesting to find out.
What is the max length an element could be?
A million characters per number would do.

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

Re: A Final Fibonacci Challenge

Mon May 27, 2019 6:07 am

ScriptBasic,
Should I assume that Elk meets your approval?

How does Elk compare with other Scheme languages you have tried?
When it comes to Scheme, I know so little about it that I may as well be a rank beginner at programming. I have a very hard time doing even the simplest thing in Scheme. That's before we start thinking about the differences between dialects, their compatibility and performance. That variety has only compounded my problems in getting started.

As such my approval or otherwise is worth nothing :)

Just now I'm happy if a Scheme adheres to recent standards versions, 6 or 7: https://small.r7rs.org/attachment/r7rs.pdf

For what it's worth, ELK has not been updated for 10 years or more. Does not support standard hash-tables. It is however 5 or 6 times faster tan Chibi Scheme.

I'll try and find time to summarize the Scheme results at some point.

User avatar
John_Spikowski
Posts: 1310
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Mon May 27, 2019 6:22 am

The best feature I like about Elk is its embeddable by design and C centric.

If you can still apt install, it must mean it's not abandoned.

Hard call for me to make if a SB extension is worth the time. I got burnt on the V7 JavaScript ext. module when they abandoned the project for different direction. I spent a lot of time building that module. :cry:

ScriptBasic has only had a one line change to scriba since I picked up the project in 2006. Same boat as Elk.i would say both languages are production stable and mature. If it had bugs there would be info on the web about it. I couldn't find anything negative. How important is hash table support?
Last edited by John_Spikowski on Mon May 27, 2019 6:48 am, edited 4 times in total.

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

Re: A Final Fibonacci Challenge

Mon May 27, 2019 6:37 am

ScriptBasic,
The best feature I like about Elk it's embeddable by design and C centric.
Ha! The best feature I like about Chibi Scheme is that is embeddable by design and C centric.
See here: http://synthcode.com/scheme/chibi/#h3_QuickStart

That and it's adherence to modern Scheme standards.

Oddly, despite my tinkering with JS in embedded systems, Espruino, JerryScript, I don't think I had ever heard of v7 or it's new incarnation mjs. Thanks for the heads up on those.

User avatar
John_Spikowski
Posts: 1310
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Mon May 27, 2019 6:54 am

The Elk API is much more extensive.

The 6X faster and Scheme compatibility is positive news. Adding C functions to Elk syntax seems intuitive.

The Ubuntu repo shows Elk updated as of 9/2018 so I don't think the language is dead.

https://launchpad.net/ubuntu/+source/elk/3.99.8-4.2

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

Re: A Final Fibonacci Challenge

Mon May 27, 2019 5:03 pm

Heater wrote:
Mon May 27, 2019 5:17 am
I would have thought that a beginner to programming has enough to assimilate with just one language.
From my point of view, one of the main reasons why the choice of a first programming language is important is that many beginners will not go on to become software engineers who know many languages and enjoy the luxury of choosing the best one for the task at hand. In fact, many engineers don't have that luxury either, because management may take the lowest common denominator approach and decide because nobody can't program in Visual Basic then everybody should.

Just like Satya Nadella sought to alleviate people's natural fear of emergent behaviour in deep-learning neural networks by paraphrasing Isaac Asimov's impractical rules of robotics, so shall we alleviate a fear of teletypes and timesharing by rephrasing the four requirements stated by Kemeny and Kurz for a beginner's programming language:

1. It should be very easy to learn. This will enable people of every race, creed, gender and political persuasion the opportunity to obtain useful information from the computer without an undue investment in time.

2. It should be possible to quickly interpret or compile programs written in the language. This is a necessity when a Raspberry Pi is used as a software development environment for teaching and learning.

3. It should be a stepping-stone for students who may later wish to learn one of the standard languages, such as FORTRAN or C.

4. It should be a general purpose language; that is, every kind of machine computation should be programmable in it.
Last edited by ejolson on Mon May 27, 2019 9:12 pm, edited 1 time in total.

User avatar
John_Spikowski
Posts: 1310
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Mon May 27, 2019 5:33 pm

Has ScriptBasic fallen off your list of ideal attributes for a learning language?

User avatar
John_Spikowski
Posts: 1310
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Mon May 27, 2019 10:43 pm

@Heater,

With Elk, I could call ScriptBasic functions / subs which would become part of Elk Scheme syntax. 8-)

If any two languages were ment to merge, SB and Elk is it.

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

Re: A Final Fibonacci Challenge

Tue May 28, 2019 12:51 am

ScriptBasic,
With Elk, I could call ScriptBasic functions / subs which would become part of Elk Scheme syntax. 8-) ...
If any two languages were meant to merge, SB and Elk is it.
Can you show an example of what this unholy alliance would look like?

Perhaps better demonstrated on the ScriptBasic thread.

User avatar
John_Spikowski
Posts: 1310
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue May 28, 2019 1:46 am

I decided to kick off the project on the AllBasic.info forum. A member there and I have a long history of Scheme / Lisp and Basic. Join us if you like.

User avatar
John_Spikowski
Posts: 1310
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue May 28, 2019 1:59 am

@ejolson,

Can you tell me array element size range for your fibo classic.bas submission?

With 1.7 million elements one would think they are a single digit or small integer.

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

Re: A Final Fibonacci Challenge

Tue May 28, 2019 2:35 am

ScriptBasic wrote:
Tue May 28, 2019 1:59 am
@ejolson,

Can you tell me array element size range for your fibo classic.bas submission?

With 1.7 million elements one would think they are a single digit or small integer.
The classic Basic program uses arrays of the default floating point type. The subroutine at the end of the program automatically detects how much precision those variables have and adjusts the base and number of limbs needed to store each number. Look at the comments of that routine for more information.

A typical size is 5 or 6 digits per array entry.
Last edited by ejolson on Tue May 28, 2019 2:48 am, edited 1 time in total.

User avatar
John_Spikowski
Posts: 1310
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue May 28, 2019 2:38 am

@Heater,

I ran the Fibonacci Scheme code you posted running with Elk in TinyScheme and it produced the correct answer. What are your thoughts? A missing parenthesis? The good news is that TinyScheme doesn't seem broken after all. Tiny so no Big integers.

Code: Select all

IMPORT ts.inc

sc = TS_New()
TS_Cmd sc, "(load \"init.scm\")"
ts_src = """
; Fibonacci using fast doubling formulas, good for millions of digits!
(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*
                        (
                            (2a (* 2 a))
                            (c (* (+ 2a b) (- 2a b)))
                        )

                        (if (= (modulo n 4) 1)
                            (+ c 2)
                            (- c 2)
                        )
                    )
                )
            )
        )
    )
)
(display (fibo 70))

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

Code: Select all

[email protected]:~/sb/examples/test$ time scriba fibo_ts.sb
190392490709135

real	0m0.049s
user	0m0.020s
sys	0m0.004s
[email protected]:~/sb/examples/test$ 
Here is fibo(78) in TinyScheme, ScriptBasic and Elk.

Code: Select all

[email protected]:~/sb/examples/test$ time scriba fibo_.sb
8944394323791464

real	0m0.006s
user	0m0.006s
sys	0m0.000s
[email protected]:~/sb/examples/test$ time scriba fibo_ts.sb
8944394323791464

real	0m0.020s
user	0m0.016s
sys	0m0.004s
[email protected]:~/sb/examples/test$ time elk -l elkfibo78.scm
8944394323791464
real	0m0.005s
user	0m0.001s
sys	0m0.004s
[email protected]:~/sb/examples/test$ 


FUNCTION fibonacci(num)
  a = 1
  b = 0
  FOR i = 1 TO num
    temp = a
    a += b
    b = temp
  NEXT
  fibonacci = b
END FUNCTION

PRINT FORMAT("%.0f\n",fibonacci(78))
Last edited by John_Spikowski on Tue May 28, 2019 4:59 am, edited 8 times in total.

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

Re: A Final Fibonacci Challenge

Tue May 28, 2019 2:53 am

ScriptBasic,
Can you tell me array element size range for your fibo classic.bas submission?
If you look at the beginning of the classic BASIC solution you will find:

Code: Select all

270 d9=int(n*log((1+sqr(5))/2)/log(b8)+7):m9=14
280 dim m(d9*m9):m0=1
That is to say the required size of the array for the n given is dynamically calculated at run time.

With 1.7 million elements one would think they are a single digit or small integer.
If you look at the end of the code you see:

Code: Select all

 
8500 rem Get dynamic range
8510 rem    outputs: f0 the largest integer
8511 rem    outputs: b7 carry threshold
8512 rem    outputs: b8 radix of limbs
8513 rem    outputs: b9 exponent to b8=10^b9

b8 is the number base of each element ("limb").
Again calculated dynamically at run time to cater for the number size of your BASIC.

If I understand correctly.

Return to “General programming discussion”