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

Re: Introduction to BBC BASIC

Wed May 29, 2019 8:06 pm

jahboater,

Edit: I notice you have rewritten your question as I wrote this. I believe it still answers your question though:

Why? You only have to turn optimization on to end up with code using far less resources than Scheme can ever dream of.
With the same numeric result of course, except that the optimized C version wont eventually crash.
Let's forget about Scheme and other languages for a moment.

Let's read what the C standard says. For example : INTERNATIONAL STANDARD ©ISO/IEC ISO/IEC 9899:2017 Programming languages — C here: http://www.open-std.org/jtc1/sc22/wg14/ ... /n2310.pdf

Talk of recursion in there is sparse but it starts out well:
6.5.2.2 Function calls

11 Recursive function calls shall be permitted, both directly and indirectly through any chain of other functions.
But here is the killer for using tail calls in C:
6.2.4 Storage Duration of Objects

6 ... If the block is entered recursively, a new instance of the object is created each time...

7. For such an object that does have a variable length array type, its lifetime extends from the declaration of the object until execution of the program leaves the scope of the declaration.35) If the scope is entered recursively, a new instance of the object is created each time.
Right there it says, twice in the same section, that new object instances are created every time the scope that they are declared in is entered.

I take that to mean function parameters, and local variables etc.

It basically spells it out that a recursive function will eat resources and an infinite recursion, or just deep recursion, will eventually consume all available space with new object instances and your program will crash.

Ergo, it's as well to assume C does not guarantee tail call optimization.

Personally I find it bizarre to argue that creating code that only works properly with optimization turned on, provided you have the right compiler, provided it actually decides to use tail call optimization in your case, provided the moon is in the correct phase, is a good idea.

If nothing else it's not standards compliant, it's behavior is UB, it makes the code less portable, it makes it hard to run under a debugger.

Having said all that, it's great that GCC/LLVM and such optimize tail calls, if only for the performance benefits. If the issues with it I mention don't bother you then by all means abuse it.

jahboater
Posts: 4604
Joined: Wed Feb 04, 2015 6:38 pm

Re: Introduction to BBC BASIC

Wed May 29, 2019 8:19 pm

Heater wrote:
Wed May 29, 2019 8:06 pm
It basically spells it out that a recursive function will eat resources and an infinite recursion, or just deep recursion, will eventually consume all available space with new object instances and your program will crash.
I think you are saying here that the correct operation of the program is to crash?

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

Re: Introduction to BBC BASIC

Wed May 29, 2019 8:40 pm

Heater wrote:
Wed May 29, 2019 8:06 pm
Having said all that, it's great that GCC/LLVM and such optimize tail calls, if only for the performance benefits.
The reason, as far as I can tell, that neither C nor Basic mandate tail calls be removed by the optimizer is because both languages support an advanced flow-control statement known as goto.

Now, has anyone implemented a big-number division routine in BBC Basic yet?

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

Re: Introduction to BBC BASIC

Wed May 29, 2019 8:43 pm

jahboater,
You need to look up the "as if" rule ...
I don't believe there is one. Certainly "as if" appears in the spec a lot.
Why is anyone ever interested in the exact mechanism of how the recursion (or better worded: solution) is implemented?
It is of academic interest only. Few people examine the assembler output of a compiler.
Mostly I'm not interested. As long as it speeds things up, and/or makes them smaller, whilst still behaving as the spec says and I expect.
What is of interest is that the answer is correct, portable, safe, and efficiently calculated.
Exactly. I agree.

Depending on tail call optimization fails your criteria there:

a) It's not correct or safe. It's UB.

b) It's not portable. It will likely fail with a different compiler that does not support tail call optimization or makes decisions about using it differently.
Please please take a look at the output of a recent GCC.
You will find tail call optimization in frequent use within your own code. And you are quite happy with that.
I have done so, many times over the years, for a variety of target architectures. And yes I'm quite happy with that.

So what? Those optimizations I'm happy with perform logically the same as the un-optimized code. They don't break things.

Optimizations are allowed to break things if those things are relying on UB. Which writing tail call dependent code is.

Ergo, don't rely on tail call optimization for the correct functioning of your code.
...but most of the time it will
That is to say, sometimes it won't. If you are happy with that by all means go ahead.

To be clear, I'm not saying compilers should not use tail call optimization, that is a great thing like all the other optimizations they may do. It saves execution time, it saves stack space. It's just not safe to rely on it in general. That is not what it is for.

User avatar
RichardRussell
Posts: 578
Joined: Thu Jun 21, 2012 10:48 am

Re: Introduction to BBC BASIC

Wed May 29, 2019 8:51 pm

ejolson wrote:
Wed May 29, 2019 8:40 pm
Now, has anyone implemented a big-number division routine in BBC Basic yet?
Not me, since it wasn't needed for the Fibonacci challenge and I lack the motivation to go further! Are there any algorithms which are more efficient than 'long division', in the same way that the Karatsuba algorithm improves on 'long multiplication'?

I should add that my existing bigint library (add, subtract, multiply, increment, decrement) is specific to 'recent' versions of BBC BASIC because it assumes the availability of 64-bit integer variables and arrays, which earlier versions (e.g. those from Acorn) don't support.

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

Re: Introduction to BBC BASIC

Wed May 29, 2019 8:58 pm

jahboater,
I think you are saying here that the correct operation of the program is to crash?
Exactly. Yes. That is what I believe the spec. says.

Of course the size of your memory/stack space is not defined in C, nor the width of you stack pointer, so when it will crash is undefined.

Given that we have no infinitely huge computers we have to assume it means it will crash. Eventually.

As opposed to doing endless, or very large numbers of, iterations with "while", "for", "goto", etc that are guaranteed not to crash. Ever.

I suspect we are have used up enough of Richard's hospitality on his thread for this side discussion.

jahboater
Posts: 4604
Joined: Wed Feb 04, 2015 6:38 pm

Re: Introduction to BBC BASIC

Wed May 29, 2019 8:59 pm

Heater wrote:
Wed May 29, 2019 8:43 pm
I don't believe there is one. Certainly "as if" appears in the spec a lot.
Please see:
https://en.wikipedia.org/wiki/As-if_rule
compiler devs rely on it!

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

Re: Introduction to BBC BASIC

Wed May 29, 2019 9:12 pm

I know what "as if" means.

The key phrases in you link are:
...provided that such optimizations make no change in the "observable behavior" of the program, as specified in the standard;
and
The rule has three main exceptions. The first is that programs exhibiting undefined behavior are exempt; since the observable behavior is not well-defined anyway, any transformation is valid.
Using tail calls for large numbers of iterations is UB, ergo any transform is valid.

Ergo, don't do that.

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

Re: Introduction to BBC BASIC

Wed May 29, 2019 9:18 pm

Hi Richard,

I understand you have GPIO working in BBC BASIC. Have you ever interfaced with the DHT11 Temperature and Humidity sensor?

Would you mind taking a peek at the C code I'm trying to use in the SB thread to access this sensor? The Python code is hit and miss.

User avatar
RichardRussell
Posts: 578
Joined: Thu Jun 21, 2012 10:48 am

Re: Introduction to BBC BASIC

Wed May 29, 2019 9:27 pm

ScriptBasic wrote:
Wed May 29, 2019 9:18 pm
I understand you have GPIO working in BBC BASIC. Have you ever interfaced with the DHT11 Temperature and Humidity sensor?
I have one on order (from an eBay seller) and when it arrives I have every intention of doing so!
Would you mind taking a peek at the C code I'm trying to use in the SB thread to access this sensor? The Python code is hit and miss.
I've already looked at what is needed. I don't anticipate any major problems coding it in BBC BASIC, except that since it relies on very short (a few microseconds) delays it is likely to fail if Raspbian happens to perform a context switch on 'my' core at that instant (this will be an issue with any language running in user mode). So 100% reliability cannot be guaranteed.

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

Re: Introduction to BBC BASIC

Wed May 29, 2019 10:45 pm

So 100% reliability cannot be guaranteed.
I like @hippy's idea of using the GPU.

User avatar
scruss
Posts: 2419
Joined: Sat Jun 09, 2012 12:25 pm
Location: Toronto, ON
Contact: Website

Re: Introduction to BBC BASIC

Wed May 29, 2019 10:48 pm

DHT11s sometimes just refuse to return a reading for no discernible reason. The Python code is likely as good as any other.

They're also really picky about not being read too often.
‘Remember the Golden Rule of Selling: “Do not resort to violence.”’ — McGlashan.

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

Re: Introduction to BBC BASIC

Wed May 29, 2019 10:59 pm

Thanks @scruss for your feedback!

The ScriptBasic version of this will take the first valid reading and be happy. ;)

User avatar
RichardRussell
Posts: 578
Joined: Thu Jun 21, 2012 10:48 am

Re: Introduction to BBC BASIC

Sat Jun 01, 2019 8:48 pm

My BBC BASIC interface to the DHT11 (or DHT12, DHT22) works, but it's far from perfect:

Code: Select all

      Sat. 1 Jun 2019,21:31:58  Humidity = 15.0%, temperature = 34.8C
      Sat. 1 Jun 2019,21:32:00  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:02  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:04  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:06  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:09  DHT11/12/22 read failed: wrong number of transitions
      Sat. 1 Jun 2019,21:32:11  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:13  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:15  DHT11/12/22 read failed: checksum error
      Sat. 1 Jun 2019,21:32:17  Humidity = 15.0%, temperature = 34.8C
      Sat. 1 Jun 2019,21:32:19  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:21  DHT11/12/22 read failed: checksum error
      Sat. 1 Jun 2019,21:32:23  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:25  Humidity = 15.0%, temperature = 34.8C
      Sat. 1 Jun 2019,21:32:27  DHT11/12/22 read failed: checksum error
      Sat. 1 Jun 2019,21:32:29  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:31  DHT11/12/22 read failed: checksum error
      Sat. 1 Jun 2019,21:32:33  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:35  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:37  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:39  Humidity = 15.0%, temperature = 34.9C
      Sat. 1 Jun 2019,21:32:41  Humidity = 15.0%, temperature = 34.8C
      Sat. 1 Jun 2019,21:32:44  DHT11/12/22 read failed: wrong number of transitions
      Sat. 1 Jun 2019,21:32:46  Humidity = 15.0%, temperature = 34.8C
As far as I can ascertain, although I am sampling the data at /dev/gpiomem at regular intervals (about every 2μs), the sampling of the actual GPIO pin carrying the DHT11 data seems not to be so regular, and there's a lot of jitter as a result. Quite often, that makes the data unreadable. In a practical application that may not matter too much - failed readings can simply be ignored - but it's annoying.

Here's the code I am using, note that the 'gpiolib' library is also entirely BBC BASIC code:

Code: Select all

      REM DHT11/12/22 sensor interface for Raspberry Pi 3/3+ (Raspbian)
      REM (c) Richard Russell, http://www.rtrussell.co.uk/, 01-Jun-2019

      INSTALL @lib$ + "gpiolib"
      GPIO% = FN_gpio_setup
      PIN% = 2 : REM BCM pin no.

      @% = &2010A
      REPEAT
        CASE FN_dht11_read(GPIO%, PIN%, humidity, temperature) OF
          WHEN 0: PRINT TIME$ "  Humidity = "; humidity "%, temperature = "; temperature "C"
          WHEN 1: PRINT TIME$ "  DHT11/12/22 read failed: wrong number of transitions"
          WHEN 2: PRINT TIME$ "  DHT11/12/22 read failed: checksum error"
        ENDCASE
        WAIT 200
      UNTIL FALSE
      END

      DEF FN_dht11_read(G%, P%, RETURN humidity, RETURN temperature)
      LOCAL B%, C%, I%, J%, M%, N%, O%, T%, d&(), t%() : N% = 6000 : REM Adjust for CPU
      PRIVATE initialised
      IF NOT initialised THEN
        PROC_gpio_inp(G%, P%) : PROC_gpio_pull(G%, 2) : REM pull-up
        PROC_gpio_pullclk0(G%, 1 << P%) : PROC_gpio_pullclk0(G%, 0)
        initialised = TRUE
        WAIT 10
      ENDIF
      DIM d&(4), t%(90), C% LOCAL N%*4
      B% = G% + &34 : M% = 1 << P%
      PROC_gpio_out(G%,P%) : G%!&28 = M%
      WAIT 2
      G%!&1C = M% : PROC_gpio_inp(G%,P%)
      FOR I% = C% TO C% + N%*4 STEP 4 !I%=!B% NEXT
      FOR I% = C% + 32 TO C% + N%*4 STEP 4
        IF !I% AND M% EOR O% t%(J%) = I% : O% EOR= M% : J% += 1 : IF J% > DIM(t%(),1) EXIT FOR
      NEXT
      IF J% <> 83 THEN = 1 : REM Wrong number of transitions
      FOR I% = 0 TO 39 : T% += t%(I%*2+2) - t%(I%*2+1) : NEXT : T% DIV= 40 : REM 0 vs 1 threshold
      FOR I% = 0 TO 39 : d&(I% DIV 8) = d&(I% DIV 8) * 2 - ((t%(I%*2+3) - t%(I%*2+2) > T%)) : NEXT
      IF d&(4) <> (SUM(d&()) - d&(4) AND &FF) THEN = 2 : REM Checksum error
      humidity = d&(0) + d&(1) / 10 : temperature = d&(2) + d&(3) / 10 : REM DHT11 / DHT12
      REM humidity = (d&(0) * 256 + d&(1)) / 10 : REM DHT22
      REM temperature = ((d&(2) AND &7F) * 256 + d&(3)) / 10 : IF d&(2) >= &80 temperature *= -1 :  REM DHT22
      = 0
Last edited by RichardRussell on Sun Jun 02, 2019 11:20 am, edited 1 time in total.

User avatar
scruss
Posts: 2419
Joined: Sat Jun 09, 2012 12:25 pm
Location: Toronto, ON
Contact: Website

Re: Introduction to BBC BASIC

Sat Jun 01, 2019 11:29 pm

These sensors are slow to react, can be wildly inaccurate and like all humidity sensors, age out of usefulness after a while.

Read 'em every few seconds and do a rolling average of all the valid readings you got in the last minute. They're not accurate enough to do much more.
‘Remember the Golden Rule of Selling: “Do not resort to violence.”’ — McGlashan.

User avatar
RichardRussell
Posts: 578
Joined: Thu Jun 21, 2012 10:48 am

Re: Introduction to BBC BASIC

Sun Jun 02, 2019 8:59 am

scruss wrote:
Sat Jun 01, 2019 11:29 pm
Read 'em every few seconds and do a rolling average of all the valid readings you got in the last minute. They're not accurate enough to do much more.
Yes, but if one is monitoring a trend, rather than needing an absolute value, there may still be a benefit in polling more often. The DHT11 I have (seemingly manufactured as a DHT12, possibly which failed to meet the accuracy spec) is returning temperatures to a 0.1°C resolution and that last digit is clearly far from random. This is the old 'accuracy versus resolution' question of course, and depending on the application one may be interested in a higher resolution even if it isn't matched by the accuracy.

User avatar
bensimmo
Posts: 4157
Joined: Sun Dec 28, 2014 3:02 pm
Location: East Yorkshire

Re: Introduction to BBC BASIC

Sun Jun 02, 2019 10:08 am

It's a simple cheap device, design for background room reading I think, so not really a fast changeable device by its target.
.

If you take it apart you'll find it a simple thermistor and a layed humidity capturing 'square' that are converted into a digital format to make it easier to get a reliable reading. Both components are quite large.
It probably the ADC whatsits that's limiting the reading rate.
DHT22 may well be sampling differently to give it it more accurate measurement ?

User avatar
RichardRussell
Posts: 578
Joined: Thu Jun 21, 2012 10:48 am

Re: Introduction to BBC BASIC

Sun Jun 02, 2019 11:09 am

bensimmo wrote:
Sun Jun 02, 2019 10:08 am
DHT22 may well be sampling differently to give it it more accurate measurement ?
I don't think the DHT22 comes into this (what I have appears to be a DHT12, not a DHT22). The DHT22 is significantly different from the DHT11/12; it has the same temperature resolution as the DHT12 but is more accurate and has a wider range, but can only be polled up to 0.5 Hz. I don't have one of them.

I am arguing that since the DHT11/12 can be polled at up to once per second, and seems to return meaningful data at that rate, the interface code should support it. At the moment the rate of mis-reads, seemingly due to GPIO timing uncertainty, is higher than I would like. I have improved the performance a little, by trying to infer what the correct data was even when corrupted (there's a fair bit of redundancy in the format), but it's only a partial fix.

User avatar
bensimmo
Posts: 4157
Joined: Sun Dec 28, 2014 3:02 pm
Location: East Yorkshire

Re: Introduction to BBC BASIC

Sun Jun 02, 2019 11:21 am

Sorry, I got the wrong end of the stick, I thought you were trying to poll faster than it would allow, and/or worry about the heating effect at 1second polling.

The DHT22 needs to be supported in the code though as it's the newer device. I was just thinking the 2second interval might be extra calculations and not actually different components as such.

(I'm also assuming it is pretty similar code, but without one who knows).
I'll get back to following the topic :-)

User avatar
RichardRussell
Posts: 578
Joined: Thu Jun 21, 2012 10:48 am

Re: Introduction to BBC BASIC

Sun Jun 02, 2019 11:47 am

bensimmo wrote:
Sun Jun 02, 2019 11:21 am
The DHT22 needs to be supported in the code
Indeed, and it is! I've REMmed out the lines for the DHT22 in the code I posted; in principle it should simply be a case of disabling the DHT11 line and enabling those two lines, and reducing the polling rate, but I don't have one to try.
I was just thinking the 2second interval might be extra calculations and not actually different components as such.
The resolution of the DHT12 and DHT22 are the same (0.1°C) so I'm not sure that follows. The DHT22's accuracy is better, and so is the range (notably it can output negative temperatures, hence the different data format from the DHT11/12), but which has the greater impact on the maximum polling rate I don't know.

User avatar
RichardRussell
Posts: 578
Joined: Thu Jun 21, 2012 10:48 am

Re: Introduction to BBC BASIC

Mon Jun 03, 2019 8:45 am

The best I've managed to achieve is an approximate halving of the mis-read rate. I've done that by combining two strategies:

  1. When the transition count is wrong (typically 81 rather than the expected 83) infer the position of the 'missing' pulse from the data pattern. This restores the data to a readable state on perhaps half the occasions.
  2. Take advantage of the redundancy in the DHT11 data format by decoding the data both from only the one-to-zero transitions and from only the zero-to-one transitions. If one gives a checksum error, the other may not. Again this probably fixes the error about half the time.
Of course the 'random' nature of the errors means that it is still possible to get two or more successive mis-reads, if you are unlucky, so there is no guarantee of timely delivery of humidity and temperature data. Elsewhere on this forum it is stated that there may be up to an approximately 40 μs latency from the signal on the GPIO pin to what a user-mode program sees at /dev/gpiomem! Whilst a constant delay of this sort wouldn't of itself corrupt the data, a variable one would and that is almost certainly what is happening.

I won't list the code here since it's quite 'ugly' and I don't want to give more ammunition to those whose sole objective is to criticise BBC BASIC.

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

Re: Introduction to BBC BASIC

Mon Jun 03, 2019 5:26 pm

Thanks for the post on the RaspberryBASIC.org forum about your current DHT11 effort. That code looks attractive to me.

Let me know if getting syntax highlighting working for BBC BASIC is of any interest.

User avatar
RichardRussell
Posts: 578
Joined: Thu Jun 21, 2012 10:48 am

Re: Introduction to BBC BASIC

Mon Jun 03, 2019 5:57 pm

ScriptBasic wrote:
Mon Jun 03, 2019 5:26 pm
Let me know if getting syntax highlighting working for BBC BASIC is of any interest.
At your forum, you mean? There's a GeSHi highlighter for BBC BASIC, if that's what it uses.

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

Re: Introduction to BBC BASIC

Mon Jun 03, 2019 6:05 pm

Thanks!

I'll get your syntax highlighting file installed on the RaspberryBASIC.org forum.
Attachments
Pretty_BBC_BASIC.png
Pretty_BBC_BASIC.png (42.69 KiB) Viewed 1330 times

User avatar
RichardRussell
Posts: 578
Joined: Thu Jun 21, 2012 10:48 am

Re: Introduction to BBC BASIC

Mon Jun 24, 2019 4:14 pm

I have released version 1.04a of BBC BASIC for SDL 2.0, the cross-platform programming language for Windows, MacOS, Linux, Raspbian, Android and iOS. The changes in this version are as follows:

  • BASIC Interpreter / Run Time Engine

    The VDU 23,24,n| command updates the 'character spacing adjustment' when a proportional-spaced font is used (negative values cause the characters to close up, positive values cause them to spread apart).

    The @tmp$ system variable has been changed on Linux (including Raspbian) and MacOS so that it points to a user-specific directory. Previously, problems could arise if BBC BASIC was run as 'root' (causing files with root ownership to be stored in @tmp$) and then subsequently as a user without privileges to delete them. On other platforms @tmp$ has always been user-specific.
  • Example Programs

    hangman.bbc: David Williams' nice hangman program, ported to BBCSDL whilst preserving its original look-and-feel as closely as possible.

    figleaf.bbc: A rendition of Scott Joplin's 'Fig Leaf Rag' (transcribed by Ron Stickley for my Z80 Music program in 1984) accompanied by an animated 3D piano keyboard.
This new version may be downloaded, for all the supported platforms, from the usual location. The GitHub repository has been updated (used to build the MacOS, Raspbian, iOS and 64-bit Linux editions, currently) although doubts have been expressed over whether GitHub is the right solution going forwards.

Please remember that if you use the Android Application Generator you should download a new APK template to ensure that any updates to the run-time engine are incorporated in your own apps.

Return to “Other programming languages”