Feb 3, 2015

Show the Structure of Your GUI in Your Code

I LIKE creating my GUIs programmatically. I suppose I'm a traditionalist (some would say a masochist). But I feel that it gives me more control over the design and keeps together things that should live together.

The downside to this is, lots of objects all declared in the same scope, with no structure to give you a hint as to how they all fit together:

    class View {
      Form frm = new Form();
      FlowLayoutPanel pnl = new FlowLayoutPanel();
      TabControl tbc = new TabControl();
      TabPage tbp1 = new TabPage();
      Label lbl = new Label();
      TextBox txt = new TextBox();
      TabPage tbp2 = new TabPage();
      Button btn = new Button();
      ...
    }
If you think about it though, the controls will all have fixed parent-child relationships with each other. They will effectively form a tree structure during runtime, that will give rise to the final graphical display. In fact, that's what all the XAMLs and JavaFXs and QMLs of the world model. Why not actually show these relationships in the code itself with a little bit of indentation trickery?

    class View {
      Form frm              = new Form();
        FlowLayoutPanel pnl = new FlowLayoutPanel();
          TabControl tbc    = new TabControl();
            TabPage tbp1    = new TabPage();
              Label lbl     = new Label();
              TextBox txt   = new TextBox();
            TabPage tbp2    = new TabPage();
          Button btn        = new Button();
      ...
    }

A-ha! So the Button won't be inside the TabPage; it'll be a sibling of the TabControl itself!

Of course, this is all manual, and won't work with whitespace-sensitive languages, and can get out of date when you change your layout, and all those things. But--when it does work, it's surprising how well it works at organising my thoughts about the layout into a nice 'graphical' overview.

Jan 8, 2015

Expressive Functional Programming with Continuations in Python

In Python, statements and expressions are separate and unequal citizens. For example, statements can contain expressions but expressions can't contain statements. This prevents things like full-powered anonymous functions which can do everything that named functions can, or expression calculations which contain statements like 'import' etc.

I wanted to fix this, to give Python an expressiveness which I thought it was missing. I first thought that we could introduce a new syntax token which could 'wrap' up any number of statements and return the value of the final expression in the block. This turned out to not be feasible, for a couple of reasons, as discussed in the mailing list.

Then I had the idea that we can turn all statements into expressions. In Python, function calls are expressions. So statements can be wrapped up inside functions to turn them into expressions. Since there aren't that many statements in Python, it's feasible to just do this for all of them. Each of these functions can take a continuation to represent 'the rest of the computation'. If all statements become expressions, and so everything is an expression, this lets us define full anonymous functions because now everything inside the anonymous function can be a single expression!

Implementation

To manage the continuations, we first define a data structure: a pair of (continuation, expression) which is passed around among the functions we'll define later, named whatever_. expression in the pair is meant to represent the input to the continuation, if it takes one.

A 'dead' continuation doesn't take an input value.

    def __dead(k): return (k, None)

A 'live' continuation takes an input value.

    def __live(k, x): return (k, x)

Continuations are run using trampolining to prevent stack overflow, allowing us to overcome the restriction of Python not optimising tail calls. The trampoline takes care of running each continuation with input or not depending on whether it's live or dead.

    def run_k_(prog):
      (k, x) = prog

      while k is not None:
        if x is None: (k, x) = k()
        else: (k, x) = k(x)

In short, a trampoline function like the above converts recursion into iteration. If you want to learn more about trampolines, here's a beautifully simple description of the idea and some examples in Python.

Some 'Syntax' Definitions

Below I define some 'syntax' in the form of functions which use continuation-passing style (CPS). So as discussed above, these functions are wrappers for the real syntax, and turn statements into expressions. Note that some of them are fairly simple versions of the real functionality.

A print function which just prints something and then doesn't return a value, it just sets up the rest of the computation to go ahead when it returns. This pattern can be used for all the Python statements.

    def print_(x, k):
      print x
      return __dead(k)

A primitive version of a 'let' binding. This 'returns' a value, i.e. the expr, bound to the parameter name in the continuation lambda. This pattern can be used for all expression-oriented syntax.

    def let_(expr, k): return __live(k, expr)

An assertion 'statement'.

    def assert_(expr, k):
      assert expr
      return __dead(k)

An if_ 'expression' can 'return' one of two values--so in other words it can pass on either of its input expressions to its continuation.

    def if_(test_expr, then_expr, else_expr, k):
      if test_expr: return __live(k, then_expr())
      else: return __live(k, else_expr())

A cond_ is basically a switch statement, but in the form of an expression that again 'returns' a value. Can be used as a replacement for Python's if ... elif ... else ... syntax.

    def cond_(test_pairs, default_expr, k):
      for (test_expr, then_expr) in test_pairs:
        if test_expr: return __live(k, then_expr())
      else: return __live(k, default_expr())

We can import a module and pass it along to a continuation, which will then use it and pass it along implicitly to its children continuations through the magic of closures. This is almost like a 'let' binding but it binds the name to the imported module instead of to an expression.

    def import_(mod_name, k):
      m = __import__(mod_name)
      return __live(k, m)

The try_ function is different from the others because it actually runs the 'try' continuation and (if needed) the 'except' continuation. This is because it can't just set up two different continuations to be run. It has to run one first to actually find out if there's an exception or not. It returns the 'finally' continuation because the 'finally' block should always be run whether or not an exception occurred, so it's a natural fit for being a continuation.

    def try_(expr_k, except_k, finally_k):
      try: run_k_(__dead(expr_k))
      except: run_k_(__dead(except_k))
      finally: return __dead(finally_k)

The for_ function also needs to run its act continuation on all the items in its seq (sequence), because there may be a lot of items and just queuing them up for running might build up a huge data structure. It's more efficient to flatten the structure at this point and then just set up the ending continuation after all that.

    def for_(seq, act, k):
      for x in seq: run_k_(__live(act, x))
      return __dead(k)

Usage

The end result is that we build and run a large expression that looks kind of like normal code on the left, but ends with a bunch of lambdas on the right of each line. Because Python doesn't have macros or autoclosures, we can't hide the fact that we're passing around lots of functions.

Note that we stop the 'program' at any point by passing in None as the next continuation. You can see this in the functions stored inside the dict below. Also note how we're storing code that looks pretty imperative inside the functions. If you squint a little bit you can kind of ignore the extra clutter and think of each line as a separate 'imperative' statement. Indentation becomes arguably more important here than in normal Python for readability.

Finally, remember that run_k_ ('run continuation') runs the whole thing. As long as we compose our program using only functions specially designed to work with the trampolining mechanism, like the ones above, it should all run fine.

    if __name__ == "__main__":
      run_k_(
        let_(
          { "foo":
              λ:
                print_("I pity the foo!", λ:
                for_(range(5), λ x:
                  print_(x, None), None)),
            "bar":
              λ:
                import_("math", λ m:
                let_(5, λ r:
    
                print_("The area of the circle is:", λ:
                print_(m.pi * r * r, None)))),
            "baz":
              λ:
                print_("None of your bazness!", None) },
          λ dispatch_dict:

        # Call to the function inside the dispatch dict is also handled by
        # the trampolining mechanism.
        dispatch_dict["bar"]()))

For the sake of readability, I've replaced all occurrences of the keyword 'lambda' above with the Greek symbol 'λ'. Of course in real Python code we'll use the keyword (search and replace should do it).

Obviously, you won't want to program like this in normal Python. It would drive people up the wall with crazy. But for specialised use cases like storing a lot of functions inside other data structures, callback-based event handling when you want to do something more complex than just call a function, or building DSLs in Python (hey, worse things have happened), this expressive method could come in very handy.

Update: this article describes a simpler, more primitive version of what I currently have. You can follow the latest developments at the GitHub repository.

Dec 21, 2014

Exodus: Gods and Kings

THIS movie should really be called Exodus: Moses’ Struggle with God.

Early on in the movie, Moses (at the time an Egyptian general), travels to the city of Pithom to investigate complaints about the Hebrew slaves from the Viceroy assigned to the city. They have a conversation in which the Viceroy mocks the Israelites, saying the very name itself means ‘one who fights with God’. Moses corrects him and says it means ‘one who wrestles with God’. Personally I would use the word ‘struggles’ instead of ‘wrestles’, but the point is that that exchange foreshadows Moses’ relationship with God.

As much as the movie is about the suffering and deliverance of the Hebrew people in Egypt, and about how Moses finally finds some measure of happiness in exile with his wife and son, it is more about Moses’ relationship with God–a very personal relationship, almost an equal partnership at times.

Moses is very clearly an unbeliever–he has grown up surrounded by the Egyptian religion with its pantheon of gods (not to mention Pharaohs), and has remained unconverted by any of them. He finally decides to follow God (their relationship, as I mentioned, doesn’t even look like any kind of deity worship we have today) because that’s the only way he sees to save his people.

Moses sets out to save his people from Pharaoh, but his attempts don’t have much impact, while Rameses’ retaliation seems expressly designed to dispirit and demoralise, frighten and terrorise, the Hebrew slaves. Like any clever slaveowner, Rameses avoids doing much real damage to his property, while still punishing them enough to (in his eyes) frighten them into submission.

That it doesn’t work is evident whenever we see the faces of the Hebrews as they observe the injustice. That they persevere in the face of it all seems like the real miracle to me, not the plagues and the cataclysms. Early on in the movie, Moses tells the Viceroy that you can tell a lot about a man by looking into his eyes. When you look at the faces of the Hebrews, it seems as if God is behind their eyes looking out at you.

God in the movie is a wrathful God. A God of vengeance. There are no two ways about it. He cannot coerce men nor preempt their minds, having given them free will. But He can and does preempt the natural order and the natures of the beasts and insects, and causes them to rain down upon Egypt in plague after plague. The punishment is intense, the suffering severe. Moses grows frustrated with it. ‘Who are we punishing?’ he asks. When God acts upon the face of the Earth, his action is like a giant hammer that smashes down upon all, without discrimination.

The final plague is what finally threatens to break Moses’ resolve: ‘No! I cannot be a part of this!’ In a final act of wrath, God reveals that He has heard Rameses’ threat to kill every Hebrew infant, and He will take the life of every first-born child of Egypt, unless they are in a house whose door is marked with the sacrificial blood of a lamb. Of this escape only the Hebrews are warned. Finally, God plans a way to discriminate between His people and their oppressors.

Knowing that there will be a massacre of innocent children is a hard thing to take. Yet the God of the Old Testament has many times been wrathful. He has taken perhaps millions of lives as punishment for evil. The Passover is the first time that He has actually planned out such a massacre with a human general and has chosen who will live and who will die in such a targeted way (well, perhaps since Noah, but then the Ark was also a much cruder means of selecting survivors than what they did for the Passover).

The way that God reveals Himself to Moses is interesting. Before I watched the movie, I heard somewhere that God took the form of a British public schoolboy. This intrigued me because it meant that Ridley Scott subscribed to the idea that God, being eternal, experienced all moments of time (past, present, and future) simultaneously and could thus introduce anachronisms by appearing in one time period as something from a completely different time period.

But ... I probably took that too literally. It didn’t actually happen. Instead I saw something just as interesting, but in another way. God asks Moses who he is, and Moses replies ‘A shepherd’. God says, ‘I thought you were a general? I need someone who can fight.’ As if He is a wartime leader recruiting a general to lead an army on a front. Which of course He is, and which of course is what He needs Moses to do. The portrayal is very, very interesting when you think about how Yahweh, the Hebrew God, started out in the oldest stories as a legendary warrior hero and leader of his people. In some stories, He had once been in the same position that He now wanted to recruit Moses to.

Many times throughout the film, Moses struggles with God, perhaps even chastises Him as being too cruel and vengeful. After four hundred years of watching His people suffer, apparently God has some pent-up wrath. Ultimately though they agree on one thing: the people of Israel need protection and guidance to find their way home.

Jul 7, 2014

Easily Authenticate when Pushing to a Git Remote

SOMETIMES when you’re working with git repositories, the remote doesn’t support pushing and pulling over SSH. It only supports HTTPS. Or you don’t have an SSH key properly set up, or you do but it’s not working for some reason. Whatever the cause, the upshot is that whenever you push, you’re forced to type in your username and password. This sucks, understandably. But do you use a password manager, like KeePass, on Windows by any chance? Because if you do, you can authenticate absolutely painlessly. Here’s how.

Set up a KeePass entry for the git server you’re pushing to. Let’s use GitHub as an example. Create a GitHub entry with your username and password, then make sure the entry has these two properties:

Auto-Type: {USERNAME}{ENTER}{PASSWORD}{ENTER}

Auto-Type-Window: Git Bash

If you’re using git on Windows, most likely you’re using Git Bash. Of course, if you’re using Posh Git, then just change the window name to whatever is appropriate.

Now, when you do a ‘git push’ and the git remote asks you to authenticate, simply press your global autotype combo (by default it’s Ctrl-Alt-K) and KeePass will log you in immediately. No SSH necessary.

That’s convenience.

May 13, 2014

Stack Overflow and its Discontents

LIKE many others, I’ve come to rely on Stack Overflow (SO) as an amazing repository of technical knowledge. How did it become so comprehensive? My guess is it was the ‘many eyes make bugs shallow’ principle. I.e., many contributors building something together, a lot like Wikipedia. SO is nearly always great when you’re searching for an answer, but not that great when you’re trying to contribute and build a profile for yourself among the other members. I’ll explain why but first let me clarify something as I see it: SO may look like a simple Q&A site, but it’s really a permanent knowledge base with the knowledge organised in the form of questions and answers. That’s important: the Q&A format is just that, a knowledge delivery mechanism. So with that in mind, we can examine how that affects peoples’ actions on the site.

Lots of people have discussed why SO punishes or rewards contributors the way it does, but one widely-held belief is that there is a subset of users (usually the moderators and other high-reputation users) that is intent on seeing SO’s core mission carried out: that the site becomes a repository of useful and generally applicable questions and answers. To keep it that way, this subset performs triage on the questions that are asked: they apply judgment calls on whether or not the questions are good ones. When you’re a beginner, there are no bad questions. But when you’re building a long-lasting repository, there are bad questions.

Generally speaking, bad questions on SO could be any of:

  • Duplicate of an already-answered question
  • Not phrased as a question
  • Not clear what the asker wants to find out
  • Asker shows no signs of having done any research or made any attempt to solve the problem
  • Question is about a specific corner case which can be easily solved if asker understood a more general principle
  • Code examples are incomplete and can’t be compiled, error messages are not quoted verbatim but only vaguely described
  • And the other end of the spectrum: many screenfuls of code or log output pasted verbatim, in entirety, without any attempt to zoom in on the source of the issue.

Any of these questions will annoy the mods because they’ll invariably get answered (because people are incentivised to answer no matter how bad the question), and then those bad questions and their answers will raise the noise level and make it difficult for people trying to find answers to the genuinely good questions. (Good search features, and even Google, can only take you so far.)

So with this in mind, we can start to understand the mods’ behaviour of seemingly penalising usually newer users of the site, those who haven’t absorbed the culture yet and are treating SO as a source of answers to one-off questions. It’s not–the questions are meant to become part of a knowledge base on the subject and potentially live forever. Under these conditions, it’s very difficult to justify questions with the above bad qualities, especially if we can guide the new users towards improving their question quality (and lots of people are trying to do this).

So, remember, the mods’ goal is to build a generally-useful knowledge base. With this as a given, the questions (subjects of knowledge) that are of a low quality will tend to get weeded out: either by being downvoted, or closed. The people who’re doing the downvoting and closing don’t have the end goal of punishing the askers; their goal is to weed out the bad questions. That the askers lose rep points is a side effect of the voting and rep system. Which is fair: if my peers judge me as not contributing good material, then I should have less cred. But the primary goal on everyone’s mind is having good material on the site, not punishing me.

Having said all that, I want to address the fact that votes on each question and answer are essentially on an infinite scale going in both directions. So, a given question or answer can potentially be upvoted or downvoted many times over, and every one of those votes affects the poster’s rep. But the effects on rep are all coming from a single posting. That’s skewed, because users on the site are more likely to see higher-voted questions and answers than they are to see lower-voted ones. That’s simply how the search facilities work by default: understandably and helpfully, users get to see highly-regarded content before they see the dregs of the site. But this means that highly-upvoted content will always get more exposure, and therefore continuously be exposed to more upvotes, while downvoted content will get less exposure and less downvotes. This skewness is disproportionately rewarding the experts and inflating their rep.

Let’s ignore the downvoted content for a second and think about the upvoted content: it is continuously getting upvoted, just for being there. Meanwhile, the person who posted that content could very well have not made a single contribution after that (taking this to the logical extreme). That’s an unfair advantage, and thus a bad indicator of that person’s cred in the community.

It’s clear at this point that the SO rep system is not going to be recalibrated yet again (barring some really drastic decision) to fix this bias, so let’s imagine for a second what a rep system would look like that actually did fix it. My idea is that such a rep system would reward (or punish) a user for a single contribution by a single point only, to be determined as the net number of up (or down) votes. So, if a post had +1 and -1, the reward to the contributor is nothing. If the post has +100 and -12, the reward to the contributor is +1. And if the post has +3 and -5, the reward is -1. If there’s a tie, the next person who comes along has the power to break that tie and thus ‘reward’ or ‘punish’ the contributor. Usually, of course, the situation won’t be a tie–usually there’s pretty good consensus about whether a contribution is good or not (to verify this, simply log in to Stack Overflow and click on the score of any question or answer on the question’s page–it’ll show you the upvotes and downvotes separately).

The sum of the net effect on reputation from each of a contributor’s posts shouldn’t become the final measure of their profile rep, though. That doesn’t give the community an easy way to tell apart a person with +100/-99 rep (a polarising figure) from someone with +1/0 (a beginner, an almost-unknown). Instead, users should be able to judge contributions as +1 (helpful), -1 (not helpful), or 0 (undecided). And each net reputation change from a contribution should form a part of a triune measure of rep: percentage helpful, percentage not helpful, and percentage undecided.

The three parts of the measure are equally important here. The vote on the merit of a contribution is nothing but a survey; and any statistician will tell you that in a survey question you must offer the respondent the choice of giving a ‘Don’t know’ answer. In this case that’s the ‘undecided’ option. If we don’t offer this option, we are missing critical information about the response to the contribution–we can’t tell apart people who simply didn’t vote, or those who tried to express their uncertainty in the question/answer by not voting.

This way, everyone immediately sees how often a particular user contributes valuable content, as opposed to unhelpful or dubious content. And the primary measure of rep is therefore not something that can grow in an unbounded way: the most anyone can ever achieve is 100% helpfulness. That too, I think, should be quite rare. The best contributors will naturally tend to have higher helpfulness percentages, but it won’t so much a rat race but rather a level marker within the community, tempered by their levels of ‘unhelpfulness’ or people’s indecision about their contributions.

So much for user profile rep. I do think that the scores on questions and answers should behave in the traditional SO way: all votes should be counted as individual votes, instead of (as with user profile rep) being summed into a net positive/negative/undecided vote. The reason for the difference is that the votes are the measure of each contribution’s merit; and if (for example) you have two similar contributions, their vote scores should be a good way to judge between them. Again, vote score should be presented in the form of a three-fold percentage measure of helpfulness, unhelpfulness, and undecidedness (with vote counts available on, say, mouseover). This keeps conformity with user profile rep and puts an upper bound on the score shown on each question or answer. The reason why this is a good thing is that most of the time, to a site user, unbounded scores are simply extra information they won’t really process. The site itself can easily search and present content in order of most highly-voted; but the reader just needs to judge merit on a fixed scale. Anything extra is just cognitive burden on the reader.

So to recap, if we’re to implement an unbiased user profile rep, we need to count the net helpfulness of each contribution once only. But for content scoring, we can count each vote individually. And to present everything in a uniform way and with low cognitive burden, we should show all scores as a three-fold measure of percentage helpfulness, unhelpfulness, and undecidedness.

Once we have this system in place, we can start doing interesting things, like automatically closing questions which sink below a threshold of, say, 10% helpfulness (they’ll start out with 100% helpfulness because the original asker’s vote is automatically counted as helpful–otherwise they wouldn’t have asked). And we can do away with reputation loss from downvoting, since a downvote will usually have no effect on the recipient’s profile rep, and only one unit of negative effect on the contribution being downvoted.

Achieving an unbiased measure of rep is tricky. But I think we can do better than SO’s current system by rebalancing the ‘rewards’ and ‘punishments’, and bounding the primary measures between 0 and 100% helpfulness so that we don’t end up with another Jon Skeet on our hands (I kid–Jon Skeet is great :-)

Dec 9, 2013

Man of Steel

IT TOOK me a while to write about Zack Snyder’s Man of Steel (MoS) because I was trying to articulate what it meant to me. And I think I’ve got it: MoS is our generation’s Superman anthem.

Let me explain. The Donner movies* were an anthem of the previous generation: Clark Kent as the Everyman, Superman as the benevolent big Boy Scout. Snyder has reimagined Clark as an outsider trying to find himself, someone who’s a little lost in the world. And a lot of us can relate to that, especially in this post-recession age.

With MoS, Snyder and Zimmer have quite literally given us an anthem for this era: brash, bold, perhaps worlds-spanning. And with it, there’s the wild element of of danger and uncertainty because Clark still doesn’t have full control over his powers, his emotions, and his moral compass yet.

Speaking of moral compass, I honestly don’t have a problem with the way it ended with Zod. There’s precedent for it in the comics, and I felt it was a nod to that. My problem was with the way they used Metropolis as the Kryptonian battleground. And maybe I’m being overly sentimental here, but I would’ve thought that Clark would try his hardest to keep those things happening to densely-populated urban centres, especially Metropolis. But then again, maybe it just goes to show how we’re not in Kansas any more, in terms of who and what this Superman is. It’s a brave new world.

* I count Superman Returns as one of the Donner movies because it explicitly tried to follow that continuity and approach to Superman/CK.

Nov 2, 2013

Notes on The Master and Margarita

‘MANUSCRIPTS don’t burn’.–Woland, The Master and Margarita

Recently I re-read this classic, long my favourite book, and I re-discovered why that is. It always amazes me how Bulgakov changes his tone and phrasing, here switching to an everyday, very Russian dry humour and wit, and there to an almost science-fiction exposition. Some notes:

‘… Let me see it.’ Woland held out his hand, palm up.

‘Unfortunately, I cannot do that,’ replied the master, ‘because I burned it in the stove.’

‘Forgive me, but I don’t believe you,’ Woland replied, ‘that cannot be: manuscripts don’t burn.’

Ideas: the most incredible and indestructible creation of humankind. Once an idea is created, it can never be destroyed.

‘No, because you’ll be afraid of me. It won’t be very easy for you to look me in the face now that you’ve killed him.’

‘Quiet,’ replied Pilate. ‘Take some money.’

Levi shook his head negatively, and the procurator went on:

‘I know you consider yourself a disciple of Yeshua, but I can tell you that you learned nothing of what he taught you. For if you had, you would certainly take something from me. Bear in mind that before he died he said he did not blame anyone.’ Pilate raised a finger significantly, Pilate’s face was twitching. ‘And he himself would surely have taken something. You are cruel, and he was not cruel….’

How incredible it would be to not be cruel and petty in this world.

‘… You uttered your words as if you don’t acknowledge shadows, or evil either. Kindly consider the question: what would your good do if evil did not exist, and what would the earth look like if shadows disappeared from it? Shadows are cast by objects and people. … Do you want to skin the whole earth, tearing all the trees and living things off it, because of your fantasy of enjoying bare light? You’re a fool.’

Ah, how clean-cut good and evil are to the Devil … on a grand scale, you need evil to balance out the good. Of course, this is ignoring the minutiae … maybe the Devil’s not in the details, but rather in the grand scheme of things?

‘… If it is true that cowardice is the most grievous vice, then the dog at least is not guilty of it. Storms were the only thing the brave dog feared. Well, he who loves must share the lot of the one he loves.’

An echo of the master and Margarita?