Monday, 19 December 2016

Regular expressions and finite automata

I've just finished the bulk of a personal project, a C++ program which stores and manipulates regular expressions and finite automata. Clocking in at over 1000 lines of code in total, it was a bit more work than I thought it'd be, but I'm pretty happy with it overall (modulo a bit more debugging and refactoring). The biggest problem has been finding a way to explain the project to non-computer-scientists.

If you're reading this blog, you've probably heard of Turing Machines, and the idea that they can do any calculation possible in this universe (as far as we know). What about simpler versions of Turing Machines? It turns out that you can define a number of different machines which are strictly less powerful. Near the bottom of this hierarchy are finite automata, which consist only of a finite number of states, with transitions between them. A finite automaton - they come in two varieties, deterministic (DFA) and non-deterministic (NFA) - "accepts" a string of letters if there's a path from the starting state to an end state which consists of the letters in that string. For instance, in the diagram below, S1 is both the start state and end state. Strings accepted include any number of 1s in a row; any string consisting of 1s, then a 0, then more 1s, then another 0; in short, any possible string which contains an even number of 0s. This can be written more succinctly using the regular expression (1*01*01*)*, where * means "repeat any number of times (including possibly 0 times)".



Another regular expression might look like 0* + 1*, which means "any number of 0s or any number of 1s (but no string mixing 0s and 1s)". There's a very cool result which says that any finite automaton is equivalent to a regular expression, and vice versa. Partly because of this, finite automata turn out to be pretty useful in building compilers, amongst other things, and I wanted to brush up on them. So what does my program do? It implements classes for regular expressions and FAs. It takes as input a regular expression, and converts it to an NFA - or else it accepts the NFA as input directly. From there, it can do a bunch of operations on the NFA, including simplifying it, taking the complement, or converting it to a DFA. It can also combine two NFAs in a variety of ways, including via union, intersection and concatenation. These combinations and conversions end up helping to achieve the final goal, which is testing whether two regular expressions or finite automata are equal. If you think of NFAs A and B as representing two sets of strings, then A and B are equal iff the complement of A doesn't overlap with B AND the complement of B doesn't overlap with A. That boils down to constructing the specified NFA and testing whether it's empty.

The theory behind this was based on my Models of Computation course last year, but there may well be more efficient implementations which I haven't learned about. In particular, I'm curious about two things: is there a NFA-DFA conversion algorithm which is sub-exponential on average, and is there an efficient way to test regular expression equality without the conversion to finite automata? I'm predicting negative answers to both of those, but let me know if I'm wrong on that.

Main lesson learned from this project: plan out a broad class structure before starting. I wasted a lot of time messing around with polymorphism when it wasn't strictly necessary. Also, test early and often! If there's one golden rule of programming, that's it.

Sunday, 18 December 2016

Book review: The Female Eunuch

It’s difficult to write an accurate review of The Female Eunuch. It was an enormously influential book, but even immediately after reading it, I remembered the tone and mood Greer created much better than the content. Partly that’s due to her style: her prose is energetic and impassioned, though at times verging on bombastic. Greer's arguments are stories - first a sweeping claim, followed by a more detailed and vitriolic assessment of the psychology of her chosen targets, and swelling to some iconoclastic conclusion, phrased in a deliberately outrĂ© manner. Between these she weaves personal anecdotes, quotations, literary references and enough obscure words to have me continually reaching for a dictionary. The book is far from a modern sociological study, teeming with facts and statistics. Rather, it is equal parts continental-style philosophy and call to arms.

To what purpose, exactly? It’s very easy to tell what Greer stands against - most things, it seems - but more difficult to extract a positive message from the book. Indeed, she reserves the most criticism for women themselves. “The cage door had been opened but the canaries had refused to fly out… the suggestion of an alternative to captivity had only confused and saddened them.” Greer presents an alternative to the conventional lifestyle, but without the promise that it will be better. Rather, she concludes, “the surest guide to the correctness of the path that women take is joy in the struggle.” Breaking societal norms will hurt, but it’s worth it to further the cause. That’s heady stuff for women who want to define their lives through feminism, and have the means to do so - feminism for the committed - but lacks a clear idea of whether it could, or even should, be desirable to all women.

What does this alternative lifestyle look like? Firstly, it’s women breaking the shackles of their own minds. Greer explains the different acculturation of boys and girls, starting from immediately after birth, and resulting in women who think of themselves as passive and self-sacrificing, especially when it comes to sexual interactions (there are some pretty good sex tips here as well). She draws a contrast between absolute purity of idealised romance, and the negative ways women are taught to think about their bodies, vaginas in particular. In typical form, she believes that any woman uncomfortable with the idea of tasting their own menstrual blood is still mentally subjugated. She also explores the heavily biased language used to describe women’s sexuality, going back hundreds of years for some examples.  It’s here that the book shines - particularly when considered in a historic context where these discussions were much more taboo than they are today.

Secondly, Greer levels similar arguments against the norms of marriage and the nuclear family, claiming that they stifle women and encourage various negative traits in both people involved, which are then taken out on their spouses and children. These children grow up controlled by adults within that family and terrified of those outside it; they see their mother becoming isolated from the outside world, and their father being “screwed in to the commercial machine” by the responsibility of family; they see each blaming the other. This is supported by an interesting discussion on love and marriage as historical constructs built over the last millennium. I was already fairly opposed to the norm of isolated nuclear families, and so I appreciated the way the book highlights these issues. However, not all of it was convincing - in particular, her description of marriages as intrinsically oppositional is rather pessimistic, and something most of us will try hard to avoid. This is where a lack of rigour hurts the argument - it’s difficult to be sure she’s not simply extrapolating from her own unhappy childhood and failed marriage, dressed up in polemic language. And without some arguments for why relationships can be good, too, The Female Eunuch is in danger of implicitly endorsing the state described by its title.

Overall, there were a couple of things which particularly stood out. The major one was Greer’s willingness to condemn anyone whose choices she sees as insipid or misguided. Parts of the book were the most scathing and vitriolic critiques of women, as a group, that I’ve ever seen. In a way, the honesty is refreshing, and it’s a good counterbalance to the modern strands of feminism which emphasise choice above all. But it also means that, for someone not quite as cynical about human nature as Greer is (and I doubt many are), it’s difficult to swallow her conclusions wholesale. That’s especially true since many of her cynical generalisations about gender relations (for example, that husbands and wives think of each other as status symbols; or various Freud-inspired ideas) are even less convincing now than they would have been half a century ago.

The other interesting thing was simply observing what seemed normal fifty years ago: how she needed to dedicate a chapter to explaining why biological differences in strength were not a good argument against women's empowerment - and also how, in the face of that, she saw a general “revolution” against both patriarchy and capitalism as the best way forward. The reminder of the scale of past bigotry is always sobering. Thankfully, though, calls for revolutions have died down since then, in favour of more incrementalist approaches.

Conclusion: The Female Eunuch is a strong challenge to gender stereotypes and societal norms, even if it’s too broad-brush to wholly defeat many. It offers little discussion of what the alternatives actually are, or how to get there, but the general sense of passion it inspires somewhat makes up for that. Read if you’re interested in the history of feminism or in challenges to some implicit gender norms which aren't major focuses of modern feminism.

Ways in which reading this book changed my mind: Marriage and child-raising in nuclear families probably has worse psychological effects than I would have thought.
The indoctrination of women into passive roles is more comprehensive than I had assumed.
The importance of the move from second- to third-wave feminism is greater than I had assumed.

Sunday, 4 December 2016

Hello World

To blog or not to blog, that is the question. And, increasingly, the former has seemed like the better option. Every so often, I get the itch to write, and it seems a waste to ignore it. I try to have interesting conversations with interesting people, and it seems a waste if they're not recorded. I also have fairly disparate interests, and I'm hoping a blog will funnel me into exploring them on a more systematic basis.

To start off with, I've put up a number of projects of mine in the Programming and Learning & Teaching tabs. I'll be making posts with some commentary on these later. They cover quite an eclectic range of subjects. Some were motivated by my own curiosity, essentially me taking notes as I learned about a topic. Some were intended as presents for my siblings, to help them explore areas they were interested in (living overseas, I've started coming around to my dad's view that "the best presents are virtual ones"). The programming projects (more to come up later) were largely inspired by some interesting Oxford courses that I took. If you've got any thoughts/comments/corrections on any of them, do drop me a line.

Lastly, I should probably explain the title of this blog. It definitely doesn't mean that all the thinking has been done already. A better interpretation is that it's describing broad and holistic thinking, which this blog definitely aims to do. But in fact, it's mostly a computer science reference. A "complete" problem is one which is at least as hard as every other problem in its class. For example, a problem is P-complete if any other problem which can be solved in a polynomial number of steps can be reduced to that problem. One of the most well-studied complexity classes is NP-complete problems, which are key to the most important unsolved problem in computer science. So if something is thinking complete, then it is one of the hardest problems in the class of all problems which can be solved by thinking.

Taken literally, there might be two problems in that group: creating general AI, and convincing a lot of very competent people to work for or with you (both interests of mine, in fact). All other problems reduce to these, since if you can do either of them, you can use that to solve any other thinking-related problem. But in a broader sense, it's about a certain mindset. Richard Hamming (inventor of the first perfectly efficient code) used to go around asking his colleagues: "What's the most important problem in your field, and why aren't you working on it?" Perhaps it's not realistic to work on all the best problems out there, but it's certainly realistic to blog about them. So, time to get started.