2022-05-09

Trampolines - fun way to make recursion not stack overflow

(We'll use JavaScript for today, running in the Firefox developer console.)

No doubt when you learned recursion, you learned that each recursive function call uses stack space to do its work.  There's only so much stack space.  So unless your programming language has a special feature (called tail call elimination), a recursive function can eventually exhaust all stack space, leading to the famous stack overflow error (not the web site).

For example, let's write a loop to sum up numbers from 0 up to some N like this:

let sum = 0;
for (let i = 0; i < 10000; ++i) sum += i;
console.log(sum); // prints: 49995000

Now a recursive version might look like this:

const loop = function(i, sum){
  if (i < 10000){
    sum += i;
    return loop(i + 1, sum);
  } else {
    return sum;
  }
};
console.log(loop(0, 0)); // prints: 49995000

As you can see, a loop is just a recursive function call.

The above is a nice, simple demo of converting a loop to recursion.  But if instead of summing up to 10,000, we sum up to 100,000, then the loop prints 4999950000.  But the recursive function prints:

Uncaught InternalError: too much recursion

With a link to: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Errors/Too_much_recursion

Trampolines

No surprise, like the title says, trampolines can fix this!

The key is to not allow the loop function to run loop(i + 1, sum), because that'd consume stack space!  Instead, the loop function will return a function called a thunk.  That thunk function, when run, will run and return loop(i + 1, sum).  This also means a thunk can return a thunk!

The function that runs loop, and any thunk functions, is called a trampoline.  That's because the thunk function the trampoline runs may return a thunk, and if so, that thunk will get run too.  The thunks keep bouncing off of the trampoline function.  Until one day a thunk returns a value instead of a thunk!  Then the trampoline's job is done, and that value is returned.

Because the thunk itself only ever uses a single "frame" of space on the stack, rather than recursively using more and more stack space with recursive function calls, and so the stack overflow error is avoided.

Here's how the code will look:

const loop = function(i, sum){
  if (i < 100000){
    sum += i;
    let thunk = ()=>{return loop(i + 1, sum)};
    return thunk; // rather than returning loop(i + 1, sum)
  } else {
    return sum;
  }
};
 

const trampoline = function(){
  let tv = loop(0, 0);
  while (typeof tv === 'function'){
    tv = tv(); // returns either a thunk function or a value
  }
  return tv;
};
 

console.log(trampoline()); // prints: 4999950000

Trampolines running thunk-returning thunk functions is a generic technique that's applicable in other languages and situations too!


Tail Call Elimination: no need for trampolines

If your programming language has full support for an optimization called Tail Call Elimination, the above trampoline technique is completely unnecessary.

It turns out JavaScript at one point had this optimization planned.  It was to be an "invisible" opportunistic tail call optimization (TCO).  Meaning that if you correctly wrote a proper recursive function call in tail position, then TCO would kick in, and it wouldn't consume stack space (thus no stack overflow).

TCO is currently only available on Apple's Safari browser and on iOS [1].

Google's V8 team apparently came to the conclusion that TCO makes the wrong tradeoff.  Because it's an opportunistic optimization, it's very easy for a programmer to write code they think would get TCO, but actually won't, and it can be very difficult to discover the error during testing.  They advocated for an explicit syntactic way to designate a recursive function call as requiring tail call elimination.  But... well, it all fell by the wayside and was never picked back up [2].

Interestingly, the Clojure programming language's creator, Rich Hickey, basically made the same argument.  In Clojure, recursive function calls requiring TCO must be written explicitly with a recur syntax.  In that case, no trampoline is needed, and the recursive function call won't overflow the stack.

 

[1] https://kangax.github.io/compat-table/es6/

[2] https://stackoverflow.com/a/42788286

2022-05-02

Firefox Focus - weird but good, standalone mobile browser and ad blocker

The best ad blocker around (uBlock Origin [0]) is not available on iPhone iOS.  That's essentially because Firefox and other browsers on iOS do not have the ability to load plugins as sophisticated as uBlock Origin.

A good substitute is Firefox Focus [1].  It's a content blocker on iOS, and can be set up that way so that Focus will block ads from showing when you use Safari!

A weird thing though is that Focus will not block ads on the main Firefox browser.  Again, something to do with iOS restrictions on iPhones.

That's ok, because Firefox has ad blocking built in (though as an obscure feature).

Another weird thing is that Firefox Focus also functions as a weird mobile web browser.  Weird because although Focus is "Firefox" branded, it doesn't have any of the account and password syncing features of the actual Firefox browser.

Oh, and Focus doesn't have tabs.  You literally have to focus on one web page at a time.

 

[0] https://github.com/gorhill/uBlock

[1] https://en.wikipedia.org/wiki/Firefox_Focus


2022-04-25

Ad blocking in Firefox on iPhone iOS

uBlock Origin [0] is a plugin for the best ad blocking available, and it's available for Firefox on Android, Windows, Mac, and Linux.

However, Firefox on iPhone iOS (FF-iOS) does not have any plug-in support, so uBlock Origin is not available for it.

FF-iOS doesn't support plug-ins apparently because it's actually using Safari's rendering engine underneath (a choice forced by Apple, apparently).

What to do about ad blocking in FF-iOS then?

Turns out FF-iOS has ad blocking built-in! You just need to go into "Settings" > "Tracking Protection". Then enable "Enhanced Tracking Protection", and set "Protection Level" to "Strict".

This feature is frustratingly [1][2] not well publicized [3]!

Another very popular plug-in is "dark mode", and that too is built into FF-iOS! It's very prominently publicized in the app's "more" menu though.

[0] https://github.com/gorhill/uBlock
[1] https://www.reddit.com/r/firefox/comments/jwi1r9/firefox_ios_should_integrate_with_ublock_to_make/
[2] https://www.reddit.com/r/firefox/comments/n9jfui/firefox_ios_and_lack_of_content_blockers/
[3] https://github.com/mozilla-mobile/firefox-ios/issues/5198#issuecomment-575617840

2021-04-28

Programming Language Notes 2021 - multiplatform, GUIs

These are incomplete notes and thoughts on programming languages through lens of multiplatform support and coding GUI apps for platforms like Android, iOS, Mac, Windows, Linux, and web (front and back ends).

JavaScript

Lack type safety.

Java, Go, Python, Ruby, C++, C, Elixir

Not great for frontend web dev.

D

Not great for Android or iOS.   Can build web apps via compiling to WASM (pretty sure it's experimental), but lack mature frameworks for frontend web dev.  Not very popularly used, unfortunately.

TypeScript

It's JavaScript but with a brilliant aftermarket type system retrofit. If you must code JS, then TS is a fantastic upgrade.

For backend, there's faster languages (Java, Go).  For device native apps, other languages are maybe better suited (Swift, Kotlin, etc).  Great choice for web frontend.

For frontend web dev, used with React is popular.  There's React Native to build device native apps for Macs, Windows, Linux, Android, and iOS that uses platform native UI widgets (some haven't reached 1.0 yet though, if you're looking for maturity).  You'd still have to build 5 specialized UIs though (6 including web), and there are faster device native languages.

Kotlin

Compiles to JVM, JS, and native.  Kotlin Multiplatform Mobile (alpha) is great for write-once application logic for iOS / Android native apps, but the UI code must be specialized for each platform (could still be written in Kotlin though).

e.g. Use with Google Android's Jetpack Compose (beta) and Apple's Swift UI for native Android and iOS UI.

e.g. Use with Jetbrains' Compose for Desktop to build apps for Windows, Macs, and Linux --- but this  runs on JVM and renders using Skia, so it doesn't use platform native UI widgets (it draws it's own like a game does).  And it's in alpha.

Some say Jetpack Compose is Google Android team's answer to Google Ads team's Dart/Flutter.

Kotlin/JS means you can use with React for frontend web dev too.  Not sure of its maturity.  Kotlin is great for backend using Spring or Ktor.

PHP

Not great for device native apps

C#

Windows centric.  Blazor lets you do frontend web dev by compiling to WASM but it adds C#'s runtime to your web app to run in WASM as well (read: bigger, slower app).

Rust

Lower level, like C or C++.  Can build web apps via compiling to WASM, but without bringing a runtime along for the ride (check out Yew or Seed).  Can build backend stuff (check out Actix-web or Rocket), but frameworks aren't mature the way Django or RoR are.

Coding device native GUI apps is... not there yet.

Rust is getting a lot of traction for systems programming though (unlike D, unfortunately).

Dart

Basically exists for Flutter.  Flutter lets you build apps for Windows, Macs, Linux, iOS, Android, and the web.  On the web, it draws into a canvas.  On devices, it renders using Skia.  So it doesn't use platform native UI widgets anywhere, and draws it's own like a game does.  On the web, it's UI performance is a little janky.

Dart compiles to JS or runs on Dart VM.  Unlike the Kotlin stuff above, Flutter is production ready and being used by Google, notably by their Ads team (apparently some of the Kotlin stuff above are the Android team's answer to Flutter).

It's from Google, so who knows if they'll cancel it in 5 years time.

Other thoughts

Rendering to Skia like Compose for Desktop and Flutter is not great for accessibility, and their accessibility features are currently WIP.

React Native has edge cases for each platform so you'd still need to know each platform carefully.  Plus TypeScript / JavaScript bridging into native can have performance issues.

 Nothing's perfect.

That's all I've got time for today!

Missing: Scala, Clojure, Haskell, F#, Crystal, PureScript, Elm.

2021-03-25

Use ISO 8601 dates in PCManFM on Debian LXQt

I like ISO 8601 or RFC 3339 style dates.  That is, rather than "January 15, 2021", I like "2021-01-15".

This is especially useful in a file manager, having all the year-month-day lined up vertically in a column.

I also prefer 24-hr time format for the same reason.  But how to set this up?

 

macOS Finder

For Mac's file manager, it's really easy to set the date/time format:

Just open System Preferences > Language & Region > Advanced > Dates, then modify the date formats to whatever you want.  At the same time, you could go to the Times tab and set it to use 24-hr format. 

Done!  I offer this as just a point of comparison for what's below...


Debian LXQt PCManFM

On LXQt's PCManFM file manager, running on Debian, the setup was... annoyingly difficult.

PCManFM does not allow custom date/time formatting.  It only respects the system set locale.  So you have to choose the right locale.

Step 1.1: Select Locale

On LXQt, you can easily set the locale (they call it "Region") by running lxqt-config-locale in the terminal, or else click the system Preferences > LXQt settings > Locale.

Step 1.2: Which locale to choose???

You have a number of options.

Do you want:

  • English language
  • dollar denominated
  • metric
  • ISO-8601
  • but 12-hr time?

Use Canadian English (en_CA) locale.

If that's not close enough, and you really want 24-hr time as well, you can enable Detailed Settings and change the Time locale to Sweden - English (en_SE).

Be sure to see Step 2: Installing Locales in Debian, because chances are doing the above will cause system errors later!

Note that en_CA uses Canadian dollars, not USD!  You can change the Currency locale to American English (en_US) if you want real USD dollars.  Although it probably doesn't matter for formatting purposes.

Why Sweden?  It turns out lots of Europeans want something similar, as in a locale that is English language, metric, using ISO-8601 or similar style dates!

Sweden - English is an unofficial locale made up to give us that [1], but it does use Swedish kronor SEK for currency [2].  That's why you only want to set the Time locale to use en_SE, keeping the rest as en_CA (or en_US).

 

Step 2: Installing Locales in Debian

Selecting the "Region" in LXQt's locale preference app is just half the story.

PCManFM will probably work fine as is.  Qt apps are fine because it uses it's own Qt locale definition lookup system, and includes en_CA and en_SE by default.

Debian does not include en_CA by default, so you'll have to install it.  And it does not have en_SE... not at all... you'll have to add the en_SE definition file manually then install it.

You can download a copy of the en_SE locale definition written by Mikael Auno [7].  Then create this directory if it doesn't exist:

/usr/local/share/i18n/locales

Place the en_SE file into the above locales directory.  Create a text file in the above i18n directory containing this text:

en_SE.UTF-8 UTF-8

Then run in terminal:

$ sudo dpkg-reconfigure locales

You should see a list of locales you can install.  Look for and install the ones you selected in LXQt's locale preference app.  For my example above, that means en_CA, en_US, and en_SE.

Lastly, logout and re-login for the changes to take effect.

 

Fully Custom Locales in Debian: don't bother

From above, you see Debian allows you to create totally custom locales, so you can customize all the formats the way Macs can!  After all, that en_SE locale file you downloaded was just made up so to speak, and you can customize it however you want.

...but Qt won't use it.  Qt's locale system runs parallel to Debian Linux's.

So why go through the trouble of installing the en_SE locale if Qt won't use it?  Because if you don't, you'll run into problems with non-Qt apps, problems like:

Run locale in the terminal, and it'll complain:

locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory

Unzip certain archives using file-roller results in a dialog box complaining:

An error occurred while extracting files.
Pathname can't be converted from UTF-8 to current locale.

That occurs because a locale you chose in LXQt was not installed in Debian [8].  Qt is perfectly happy though, as it runs a separate locale system...

 

Firefox locale incompatibility

If you set your locale to Canadian or US English (en_CA or en_US), and enabled Detailed Settings to change the Time locale to Sweden - English (en_SE), Firefox will show numbers in Swedish / European style, like "3,14" instead of "3.14".

This problem happens at least in the downloads window.

Method 1: Fix by setting LC_ALL environment variable

The most reliable way to fix it in Debian is to set the LC_ALL environment variable, but only for Firefox [13].  Don't set LC_ALL globally or it'll undo the locale changes above, plus you just shouldn't as it overrides everything [12]. 

For the terminal :

With that said, all it involves is opening Firefox in the terminal like this:

LC_ALL=en_CA.utf8 firefox

You can save that in a script that's in your PATH so running Firefox always uses the LC_ALL locale.

For the Firefox icon:

The Firefox icon in Debian requires a different fix though.  That icon in the applications menu is controlled by a  firefox.desktop file located at:

/usr/share/applications/firefox.desktop  

You can modify it directly or, safer, copy it to your user's applications folder:

~/.local/share/applications

Once copied, open it in a plaintext editor and change the Exec line to this:

Exec=sh -c "LC_ALL=en_CA.utf8 /usr/bin/firefox"

 

Method 2: Fix by setting Firefox locale internally

The "official" way to set the Firefox user interface locale is via Firefox's preferences [14]:  open preferences, then go to the Language section of the General panel.

I've tried it on Debian and it doesn't work.

You could also try finding in about:config the intl.locale.requested key and set it to the desired locale [15].  I didn't test this method though because setting the LC_ALL environment variable worked perfectly for me.


Other locale options

Sweden - English (en_SE) is an unofficial locale made up to give us English language, metric, ISO-8601 date format [1].  But it uses Swedish kronor SEK for currency [2].

Denmark - English (en_DK) is another unofficial locale made up with similar English and metric formats [3].  But the date is backwards (in dd/MM/y format), and uses Danish kroner DKK currency [4].

Ireland - English (en_IE) is an official locale that, like Denmark - English, gives us English and metric units [5], and like en_DK, the date is backwards (in dd/MM/y format).  It uses Euro for currency [6] though.

So by mixing and matching Ireland, Denmark, and Sweden, you should be able to get a reasonable ISO 8601/English/Euro(pean) locale.

And mixing Canada, US, and Sweden will get you a reasonable ISO 8601/English/Dollar locale.


References

[1]: https://unix.stackexchange.com/a/62318

[2]: https://icu4c-demos.unicode.org/icu-bin/locexp?d_=en&_=en_SE

[3]: https://unix.stackexchange.com/a/272665 and https://superuser.com/a/1269909

[4]: https://icu4c-demos.unicode.org/icu-bin/locexp?d_=en&_=en_DK

[5]: https://unix.stackexchange.com/a/62317

[6]: https://icu4c-demos.unicode.org/icu-bin/locexp?d_=en&_=en_IE

[7]: https://bugs.launchpad.net/ubuntu/+source/langpack-locales/+bug/208548/comments/11

[8]: https://unix.stackexchange.com/a/269293

[12]: https://wiki.debian.org/Locale#Configuration 

[13]: https://unix.stackexchange.com/questions/34965/how-to-change-firefox-language#comment47453_34967

[14]: https://support.mozilla.org/en-US/kb/use-firefox-another-language?redirectslug=use-firefox-interface-other-languages-language-pack&redirectlocale=en-US#w_how-to-change-the-language-of-the-user-interface

[15]: https://support.mozilla.org/en-US/questions/1223719#answer-1127761


Bibliography

[9]: https://github.com/lxqt/pcmanfm-qt/issues/656

[10]: https://github.com/lxqt/lxqt-config/issues/507

[11]: https://wiki.debian.org/Locale