[1+1=2]

OneAndOneIs2

Fri, Nov 04, 2016

[Icon][Icon]Thinking in functions

• Post categories: Omni, Technology, My Life, Programming

AKA "When you're been reading so much Lisp that it starts to affect your brain"

A while ago I did a talk on functional programming. As my example, I showed how to impliment linked lists using closures instead of the built-in data structures. Recently, as I was reading some Lispy code, it suddenly dawned on me that there was one step further I could have taken that hadn't occurred to me. So I sat and had a play, and sure enough it worked.

So here's the process, for anyone who wants it :) I've put it in Javascript, since it makes it easy for anyone to try via the browser.

Firstly, the specified task: We want a new data structure, "pair", which can hold two values. From this, we want be able to build linked lists. We want all access to be handled via functions: Create a pair with pair(), get one value with head() and the other with tail().

The quick, easy, obvious approach is to use a built-in data structure under the hood. Such as an array. So:

function pair (head, tail) {return [head, tail] }
function head (pair) { return pair[0] }
function tail (pair) { return pair[1] }

This is a full implementation of the desired "pair" functionality. A quick test will bear this out:

> var test_pair = pair("the_head","the_tail")
undefined
> test_pair
[ 'the_head', 'the_tail' ]
> head(test_pair)
'the_head'
> tail(test_pair)
'the_tail'

All good! Works perfectly. So.. we're done?

Not quite. This obeys the letter of the law, but falls foul of the spirit. Firstly, it's too easy to bypass the abstraction and access the data directly, instead of through our accessor functions. Secondly, it's all too easy for somebody to shunt more data into the array and make our "pair" hold more than the desired two values.

> test_pair[0]
'the_head'
> test_pair[2] = "sneaky misuse of pairs!"
'sneaky misuse of pairs!'
> test_pair
[ 'the_head','the_tail', 'sneaky misuse of pairs!' ]

Not good. We must fix this! Let's switch away from arrays, and go instead to closures:

function pair (head, tail) {
 return function (fn) {
  return fn(head, tail)
 }
}

function head (pair) {
 return pair(
  function (head,tail) { return head }
 )
}

function tail (pair) {
 return pair(
  function (h,t) { return t }
 )
}

If you're not used to closures, this may seem a little abstract. Let's break it down!

pair() now returns a function. That shouldn't be a surprise in this day & age, functions are first-class objects in most languages. Let's call it the p1 function. The p1 function is a very simple function, as all it does accept another function (call it p2) as its argument and call it. Very simple.

The important thing is that p1 still has access to the original arguments pair() was called with, via the magic of closures. So both the head and tail are available to p1, which means when you pass a p2 function into p1, p2 is called with the original head and tail. So now the p2 function can decide what to do with them. In the case of head(), it passes in a function that accepts the head and tail, and returns the head. Tail is identical, except for which value it returns.

Once you get used to closures and functional programming in this style, it all makes perfect sense. I appreciate it can make the eyes glaze a little at first though. Let's test that it works:

> var test_pair = pair("the_head","the_tail")
undefined
> test_pair
[Function]
> head(test_pair)
'the_head'
> tail(test_pair)
'the_tail'

So, we have continued to fulfill the specification as stated, and now we have a data structure that can ONLY be used to hold our head and tail values - no sneaky extras, and no way to view the data directly.

Onwards, then! We want to use pairs to implement a linked list. In this implementation, a list of, say, (1,2,3) could be implemented by pair(1,pair(2,pair(3))). The head of a pair contains a value, the tail contains the rest of the list. Let's see how that works:

> var list = pair(1,pair(2,pair(3)))
undefined
> list
[Function]
> head(list)
1
> head(tail(list))
2
> head(tail(tail(list)))
3

Okay, simple enough. But a long list calls for a lot of nested pair() calls! Let's automate that.. we need a list() function! And whilst we're at it, let's write a few list accessors to cut down on all that head-tail-tail stuff.

function list () {
 var list;

 for (i = arguments.length; i > 0; i--) {
  list = pair(arguments[i-1], list)
 }

 return list
}

function first (l) { return head(l) }
function second (l) { return head(tail(l)) }
function third (l) { return head(tail(tail(l))) }

And make sure it works as expected:

> var lst = list('a','b','c')
undefined
> first(lst)
'a'
> second(lst)
'b'
> third(lst)
'c'

So far, so good. Now, a common desire with lists is an ability to apply a function that expects a single value to a list of values instead: Say we have a triple() function that expects a number, but we want to be able to apply it to the list (1,2,3) to get (3,6,9).

This is typically done with a recursive function called map(), which creates and returns a new list, which it generates by applying the desired function to the head value of the original list, and pairing it to the result of calling itself on the tail of the original list.

function undef (x) { if (typeof(x) === 'undefined') { return true } }

function map(fn, list) {
 if ( undef(list) ) {
  // If the list is undefined, we've reached the end - stop recursing
  return;
 }
 // We're still going: Call the function on the head, recurse over the tail
 var h = head(list);
 var t = tail(list);
 return pair( fn(h), map(fn, t) )
}

function triple (x) { return 3 * x }

And let's see if it works:

> var small_list = list(1,2,3)
undefined
> var big_list = map(triple, small_list)
undefined
> first(big_list)
3
> second(big_list)
6
> third(big_list)
9

Looks good! We are making linked lists and mapping over them to make new lists. Very Lispy!

Now, this is as far as I ever got just from generic reading about closures, functions, and Church numbers. It does the job, and does it using nothing but functions. All very clever.

But one day as I was reading up on Lisp, I suddenly realised there was another way. Instead of map() navigating the list via head() and tail(), I could skip the overhead of those extra function calls. In the original approach, pair() creates p1, and then head() and tail() both call p1, passing it a function to return either the head or the tail. Map uses head() and tail() and is thus implementation-agnostic - the original array-based approach would still work with map as defined.

But if we throw that agnosticism out and write something directly for the function-based approach, then we can avoid the overhead of calling head() and tail(). Instead, we can pass p1 the recursive function that does the mapping. Because p1 will call this function with both the head and tail arguments as parameters, this means the new function gets the values it needs directly instead of through the accessor functions, thus:

function fmap(fn, list) {
 var rec;
 rec = function (h,t) {
  if (undef(t)) { return pair( fn(h) ); }
  else { return pair( fn(h), t(rec) ); }
 }
 return list(rec);
}

And sure enough:

> var big_list2 = fmap(triple, small_list)
undefined
> first(big_list2)
3
> second(big_list2)
6
> third(big_list2)
9

I know, I know. It's evil. It's over-engineered. It makes far too much use of passing around recursive functions. And I'd probably be very upset to find anything like it in production code.

But.. it was fun to work it all out :)

 

Sat, Jun 25, 2016

[Icon][Icon]The perfect compromise

• Post categories: Omni, In The News

So, the biggest vote of a generation has been and gone. It came after a campaign painfully lacking in useful information on either side, and it departs leaving nobody really looking good.

The Prime Minster, David Cameron, whose best answer to the huge responsibility of deciding how to handle an enormously complicated political decision was to say "Fuck it, you decide, I'm not going to", has made it clear he'll be continuing with his abdication of responsibility by handing in his notice rather than deal with the results himself. Everybody is therefore asking "What happens next?" with a certain amount of trepidation.

Well, there's a lot of uncertainty, of course. But I think I have the answer. It's based on something once said by the great philosopher, Calvin:

A good compromise leaves everybody mad

One of the most notable lacks in the Leave campaign was its answer to "What's the plan for after the vote?" which was famously answered with "lol, dunno!" by the head of UKIP. Slightly more useful answers cited examples of other non-EU countries that we could emulate.

My argument is that the proposal of the Norweigian model is not just good, but the best possible answer, and here is why:

The original referendum back in the 70s was to join the common market. A persistent complaint from Leave was that the EU was "not what we voted for" and it's perfectly true. So we could satisfy both referendums by leaving the EU and staying in the single market.

So far so good. But there's more!

The Norway model gives access to the single market via the EEA - the European Economic Area. The UK could continue to trade with the Europe pretty much as it always has. This would settle the markets and ease the fears of the international corporations that are suddenly finding London a less-attractive base of operations.

Even better, as all informed voters will be aware, the House of Commons indicated long before the vote took place that it would use it's (roughly) 3:1 pro-Europe majority to block any attempt to take us out of the EEA. So it would actually be very difficult for our leader (whoever that turns out to be) NOT to go with the Norway model or something very close to it.

But what makes it the ideal solution is this: Membership of the EEA not only gives unrestricted access to the single market. It also requires that members: abide by EU regulations regarding the market; allow free movement of workers; and pay the EU for membership - to the tune of something like £200 million a week.

The Leave campaign never ceased to talk about reclaiming control of our borders; and the (wrong) amount of money we pay into the EU each week was even emblazoned on the side of Boris Johnson's Leave campaign bus.

The Norway model would mean nothing changes on either front. And that's what makes it so perfect!

Everybody who voted Remain - the 48% - gets to feel pissed off because they didn't get what they voted for.

Everybody who voted Leave - the 52% - gets to feel pissed off because they got EXACTLY what they voted for. Just not what they actually wanted.

The entire population thus gets to come together, unhappy but united again in our common hatred of our politicians, who always, ALWAYS get it wrong.

And the politicians? It's ideal for them, too: They get to answer every problem with their tried-and-tested approach of blaming everything on the immigrants they can't stop from coming here; and the lack of cash they have to work with because it all goes to Europe.

Life would quickly settle back to normal. The Europeans already here could stop worrying about being thrown out, the Brits abroad likewise. Trade would continue much as it always did before. The UK stops having to worry about EU policymaking because it no longer has a say in it. The entire population settles down and resigns itself to not having got what it wanted, as usual, and the whole thing is over.

 

Mon, Dec 14, 2015

[Icon][Icon]Slides for my talk

• Post categories: Omni, FOSS, Technology, My Life, Programming, Helpful

On Saturday, I attended the London Perl Workshop - an annual event that's totally free to attend and has plenty of useful stuff even for people who don't know Perl.

I even did a talk myself - an introduction to Functional Programming for beginners. Nobody fell asleep, so I called it a success. As requested, I'm also making the slides available. I'm using Dropbox because meh, it's convenient.

It's Powerpoint rather than Open/Libre Office because, basically, that's what happens to be installed on my laptop already. If you weren't at the presentation and want to read the slides to get the content, I advise "notes view" because there were a few worthwhile points that didn't get turned into bullet points on the slides.

Download here

If you have any problems getting the file, tweet me or something and I'll see what I can do about it. I'm not turning comments on here because I get spammed to hell if I do that, sadly.

 

Mon, Aug 10, 2015

[Icon][Icon]Tablet keyboards

• Post categories: Omni, FOSS, Technology, Programming, Helpful

So I got sick of some things on my Android tablet. The crappy privacy settings, the unrelenting stream of adverts in youtube, and so on.

So I figured it was time to try out the alternative: Cyanogenmod, an open-source fork of Android.

A lot went well. Things that were broken by latest Android switching away from the Dalvik runtime sprang back into life with a switch to CM and leaving it set to Dalvik. Such as YouTube AdAway (See previous post for more on that)

Also, CM has privacy settings that let me say "Yes, install the Facebook app, but NO, don't let it know where I am, thankyouverymuch" and profiles so I can have it automatically mute when I'm at work and regain sound when I get home. And I lost far fewer files in the transition than I expected, which was good.

There was just one little niggle. And it's to do with keyboards.

For most tasks, I like to use the standard Android keyboard. It's a pretty good kb. But when I use the ConnectBot ssh client, I *need* a full keyboard, with keys like Ctrl, Alt, and Esc. No problem, Hacker's Keyboard to the rescue!

But when I'm in Firefox, I want the LastPass keyboard so it can enter my username & passwords for me.

So depending on what app I'm using, I might be desiring one of three keyboards. And it's a pain to have to switch them manually.

No problem, because Tasker to the rescue! An app that can watch for context changes, like switching to an app, and automatically apply specified actions. Except that the UI isn't the easiest to get your head around, but eventually I was pretty confident that it wasn't me being an idiot: The option to change keyboard just wasn't there.

But it had to be, because I'd used it before...

A bit of Google-fu, and the answer came to light: Keyboard-switching power isn't exposed in the normal course of things. You can only get at it if you install the Secure Settings app.

Which I did. But that didn't work either. A bit more poking around, and I found that it needed me to install the System+ Module to allow it to expose the functionality I wanted. No problem, it has a button that does exactly that.

But I clicked on "Enable" and it failed to grant the permissions.

I checked the SuperSU logs, and was told that I'd need SuperSU *Pro* to access that feature.

Motherfucker!

So I threw a few quid their way, and got SuperSU Pro installed & running. (You have no idea how many reboots I'm leaving out of the story here, by the way :(

Tried again, saw a failure in the logs but needed to enable expanded logging for a more useful answer. Enabled it, tried again, finally got a useful error: <stdin>[1]: pm: not found</stdin>

But *why* isn't pm found? It's in the /system/bin/ directory, with correct 755 permissions. Fscking hell. Maybe I'm missing something?

Switch away from my Linux VM and back into OS X because that's where all the Android SDK stuff is installed. Open up an iTerm, and fire up adb. Which fails to find my tablet because (a) it's not plugged in at the moment, and (b) I turned off USB debugging.

Fix those two problems, and *now* I can get a shell. One quick confirm on SuperSU Pro later, and I have a root shell. Can I run the pm binary? Yes.

Okay, clearly there's a problem in the installer preventing it from using the correct $PATH to find the binary that's right where it fucking should be. It *can't* be that many commands to run to install this fecking module, right..? And I already know the first one from the error logs. It's pm grant com.intangibleobject.securesettings.plugin something something something

So, let's dump that command into google and see if anyone has been helpful enough to list the *other* commands that are needed..?

Yes!

pm grant com.intangibleobject.securesettings.plugin android.permission.WRITE_SECURE_SETTINGS
pm grant com.intangibleobject.securesettings.plugin android.permission.CHANGE_CONFIGURATION

That's all it needs! Just those two commands!

So I run those from adb where pm is actually working, and the module is *still* not enabled. So I reboot just for good measure.

AND IT WORKS!!!

System+ Module is enabled, and Secure Settings is now allowing me to open the System+ Actions in Options and activate the "Input Method" entry.

Finally! I have reached the point where Tasker should be able to change my keyboard settings.

So now it's just the Tasker UI to worry about...

This time, I remember the lessons from last time: Do *not* start with the profile. First define the tasks you want. That means Tasks -> New -> Name it -> Add Action -> Select Plugin -> Secure Settings -> Edit configuration -> System+ Actions -> Input method -> Select desired keyboard from dropdown -> Save -> Leave all other conditions in the Tasker screen alone and hit the top-left button to say "I'm done here"

Repeat this for every keyboard I'll be wanting - in my case, LastPass, Hacker's, and stock.

Now that I *have* the tasks, create a profile to use them. Profiles -> New -> Application -> Select desired app(s) -> Top-left button -> From drop-down select desired keyboard task

Halfway there, I will now get the keyboard I want when I switch to a target app. But it won't go away when I leave. How do I add an "exit" task? I see nothing obvious.

A bit more poking around, and I get it: Long-press the green arrow, and it'll pop up a dropdown that allows you to add an exit task. Select that option, choose the stock keyboard task, and finally, after all that work, you're done.

Yes, I'm aware, it's an insane amount of work to have to go to just to establish a link between apps and keyboards. I only stuck with it so long because at every step of the way, it seemed like I was just *one* step away from success.

If somebody else is stuck with trying to get their CM tablet/phone to change keyboards based on app, I hope something in here helps you to save your sanity. Mine is, clearly, gone already :)


 

Tue, Dec 09, 2014

[Icon][Icon]Blocking

• Post categories: Omni, FOSS, Rant, Technology, My Life, Helpful

That old chestnut, internet advertising. Still causing problems after all these years...

The problem is clicks. When advertisers came to the Web, they realized they could make their adverts clickable. Unfortunately, this single fact caused their brains to melt.

You see, no form of advertising ever has relied on "See ad, buy product". That is an approach that has never worked. It's well known that advertising works on a subtle, slow-and-steady approach: The first half-dozen times you see an advert, you don't even register it. Then the next half-dozen, you vaguely remember having seen it before. Then the next few times, you wonder briefly about the product. Then a few more exposures and you start to think about buying the product. A few more, and you resolve that you WILL buy the product. A few more still, and you finally take action and actually buy the product.

And that's the best-case scenario. Sure, sometimes you'll see an ad that reminds you you already meant to buy a product and you might seem to do "See ad, buy" but those are exceptional edge-cases, not brilliant advertising.

So the whole industry was based around ensuring you saw a product advertised many times, because it was repeated exposure that did the magic. And everybody knew that. A never-ending stream of subtle nudges that ultimately resulted in a purchase.

Nobody ever said "We put up a billboard by the road that says 'Buy cola!' and the drivers didn't immediately pull over and dive into a shop for a cola. Clearly, the advert has failed." That would be nonsense. Advertising doesn't work like that.

Internet advertising should have been just another form of exposure: A reminder of a product, which was linked to a site where you could buy it solely to make your life easier if this happened to be that one-in-a-hundred exposure that caused you to buy the product.

Instead, the entire industry threw out everything they knew about how adverts work, and began a years-long scream of "CLICK ON OUR FUCKING ADVERTS YOU BASTARDS!!!"

Simple text ads not getting clicked? Make them brash colours!

Still not enough clicks? Bright, flashing colours!

Still not enough? Animations! Dancing monkeys!

Still not enough? Full-on movies!

Still not enough? Movies with sound!

And so on....

And so adverts became bigger, brighter, louder, and in every way possible harder to ignore. They even over-shadowed the content people were actually trying to view. And so the ad-blocker was born - a desperation move by people who just wanted to read the content they had clicked on without seizure-inducing movies screaming at them from all sides.

I've used Abdblock Plus in my browser for years. For a while, I tried to maintain my own list of sites to be blocked, but it became harder and harder to stay on top, so ultimately I caved and signed up for the auto-updating filters it offers. And it eliminated the vast majority of obnoxious ads for me, and still allowed harmless ads through: the ones that were just simple text, or static banner.

And that was fine, and indeed still is.

But I also started using a tablet. And ads soon made their unwelcome appearance on that, too. Beyond obnoxious: Simply opening a web page sometimes saw me suddenly finding myself in the Play store being asked to okay the installation of an app. WTF?!?

Not just obnoxious, this was becoming a genuine safety hazard. Something had to be done!

And I discovered my old friend, Adblock Plus, had an Android app. Installed on a tablet you have root on (Which I do), it blocks ads not just in Firefox, but across all applications. Win!

For a while, all was well. But then a couple of problems: Firstly, ABP had a tendency to crash and need a manual restart, which was annoying. Secondly, YouTube started using HTTPS.

This is a problem, because ABP works by being a proxy, diverting all network traffic through it. This works beautifully for filtering out known advertising servers, like doubleclick. However, youtube adverts are videos. They come from youtube.com. And HTTPS obscures all details of a request other than the server: All ABP could see was "Youtube, please send me stuff" - it couldn't distinguish "Video I asked for" from "Advert I don't want"

And youtube, like most other advertising, has been getting slowly more and more intrusive. Un-skippable ads before you can watch a movie, ads that pop up in front of the movie you're watching... all the shit that makes US TV so painful to watch, ported into the web. Lovely.

Youtube was getting steadily worse; ABP couldn't help; Youtube can't realistically be boycotted; Google is only just beginning to consider a "Paid membership" option to remove adverts. What to do?

Well, when you have a technical problem, a useful approach is often to bitch about it on an IRC channel. Which I did, and as hoped, got pointed at something useful. AdAway, and YouTube AdAway.

AdAway, instead of being a proxy, simply updates your hosts file to redirect ad requests. Nice and simple. YouTube AdAway was a plugin for the Xposed framework, a handy little framework that can alter the way the system, and any installed apps, work.

So, there was a certain amount of jumping through hoops - install F-Droid to use it to get AdAway, install the Xposed Installer to get the framework to get the YouTube AdAway module...

But I got it all done, and the end result? So far, no ads in YouTube: No pre-video clips, no pop-ups during the vid. YouTube is no longer annoying.

Browsing, I have more ads than I'm used to - I've not yet done anything to customise AdAway - but less ads than I'd get with no block at all. And so far, none of the dangerous "Hey, install this app!" crap.

So I count it as a win.

A couple of other things I've picked up lately that may be of use to desktop users. Firstly, that old favourite, the video player VLC: It can open YouTube vids from the URL. If you just want to watch a movie without any ads, suggested "What to watch next" vids, etc. then this is a quick & simple way to get it.

Secondly, if you use ABP, there's also an extension that will work with it called AdNauseam - ABP simply blocks everything, AN adds a simple addition: It simulates clicking on everything blocked.

This answers two of the common objections to adblockers: "You should support sites you like by clicking on their ads!" and "I don't want my preferences to be tracked" - clicking on everything makes your preferences unknowable, costs advertisers money, and raises funds for your favoured sites.

Lastly, if you worry about how much Google knows about you, this has some links that will allow you to not only see what Google knows, but also to correct and even delete some of it.

Have fun!


 

:: Next >>

[Links][icon] My links

[Icon][Icon]About Me

[Icon][Icon]About this blog

[Icon][Icon]My /. profile

[Icon][Icon]My Wishlist

[Icon]MyCommerce

[FSF Associate Member]


December 2016
Mon Tue Wed Thu Fri Sat Sun
 << <   > >>
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  

Search

User tools

XML Feeds

eXTReMe Tracker

Valid XHTML 1.0 Transitional

Valid CSS!

[Valid RSS feed]

powered by b2evolution free blog software