Math Circle Session 4: Ciphers

Today saw the fourth session of our math circle. Attendance was down, and there was a sombre mood, due to a tragic event to hit the the school community today.

We went ahead with the three children who came, looking at ciphers. Following the guidance and resources in Rozhkovskaya’s book, we looked at the following activities:

We started with some plaintext words and one ciphertext word, and the kids very quickly spotted, without any help, which plaintext word corresponded to the ciphertext word, on the basis that both had a double letter in a certain place and they had the same number of symbols.
We showed how a coding wheel can be used to produce a Caesar shift cipher, and got them to actually build such a wheel.
We queried how many possible ciphers could be constructed with such a wheel. Interestingly, this was not obvious to the children at first, and a common answer was “infinite”. On questioning, this is because they were considering all integer shifts, i.e. mapping the letter $n$ to the letter $n+k$ for some key $k$ , and forgetting the modulo arithmetic in play, despite having the wheel in front of them.
We got them to produce coded messages to each other using the wheel, which they seemed to enjoy. Our initial plan was to have them pass the message and the key to the next child to decode. However, they immediately attempted to decode without they key by looking for patterns, so we didn’t stop this. One key pattern they spotted included the limited number of two letter words in English, allowing them to enumerate possible keys on two-letter words in the ciphertext. Another was the limited number of letters in the alphabet that can appear twice consecutively in an English word, again allowing for enumeration.

There’s a lot more that can be done with ciphers, and I expect we’ll continue this for another session.

Review: Three Views of Logic: Mathematics, Philosophy, and Computer Science

I read this book largely by accident, because I was attracted by the title. As an academic in (or rather, on the edge of) computer science, I come across logic regularly, both in teaching and research. Mathematics underpins almost everything I do, and I’m certainly interested in whether a mathematician’s view of logic differs significantly from that of a theoretical computer scientist (as a keen reader of mathematics, I’m well aware that standard mathematical practice of proof differs quite strongly from the formal approach studied in computer science, but this isn’t quite the same thing!) I once had a strong interest in philosophy, most significantly in epistemology, which is being rekindled by my involvement in education at the school level, and so combining all these factors, the title was very appealing. What I actually discovered when I started reading wasn’t exactly what I expected. But this book turns out to be an excellent, crystal clear, textbook suitable for undergraduates and those with just a limited level of mathematical maturity. The book is explicitly partitioned into three sections, but in practice I found that the first two sections, proof theory and computability theory (the “maths” and the “computer science”) were very familiar material for any computer scientist, and from my perspective there was no very clear difference in approach taken, just a difference in the range of topics covered.

Part 1, by Loveland, covers propositional and predicate logic, with a particular focus on automated proof by resolution. I found the description of resolution to be very clear, with a particular focus on the difference between resolution for propositional and predicate logic, and with one of the clearest descriptions of completeness results I’ve seen.

Part 2, by Hodel, covers computability theory. Again, the clarity is exemplary. The first chapter discusses concepts informally, the second precisely defines two machine models in a way very accessible to a computer engineer (effectively one supporting general recursion and one supporting only primitive recursion) and discusses their relative computational power. The insistence of an informal discussion first makes these distinctions come to life, and allows Hodel to frame the discussion around the Church-Turing thesis. The focus on compositionality when preserving partial recursiveness, and the emphasis on the ‘minimalisation’ operator (bounded and unbounded) was new to me, and again very clearly presented. Most introductory texts I’ve read only tend to hint at the link between Gödel’s Incompleteness Theorem and Church’s Undecidability Theorem, whereas Hodel makes this link precise and explicit in Section 6.6, Computability and the Incompleteness Theorem.

Part 3, by Sterrett, covers philosophical logic. In particular, Sterrett considers the existence of alternatives to (rather than extensions of) classical logics. She focuses on the logic of entailment aka relevance logic introduced by Anderson and Belnap, into which she goes into depth. This logic comes from rethinking the meaning ascribed to the connective, $\rightarrow$ , logical implication. In classical logic, this is a most confusing connective (or at least was to my students when I taught an introductory undergraduate course in the subject long ago). I would give my students examples of true statements such as “George is the Pope” implies “George is Hindu” to emphasise the difference between the material implication of classical logic and our everyday use of the word. It is exactly this discrepancy addressed by Anderson and Belnap’s logic. I was least familiar with the content of this part of the book, therefore the initial sections came as something of a surprise, as I found them rather drawn out and repetitive for my taste, certainly compared to the crisp presentation in Parts 1 and 2. However, things got exciting and much more fast moving by Chapter 8, Natural Deduction, where there are clear philosophical arguments to be had on both sides. In general, I found the discussion very interesting. Clearly a major issue with the line of reasoning given by my Pope/Hindu example above is that of relevance. Relevance might be a slippery notion to formalise, but it is done so here in a conceptually simple way: “in order to derive an implication, there must be a proof of the consequent in which the antecedent was actually used to prove the consequent.” Actually making this work in practice requires a significant amount of baggage, based on tagging wffs with relevance indices, which get propagated through the rules of deduction, recalling to my mind, my limited reading on the Curry-Howard correspondence. The book finishes with a semantics of Anderson and Belnap’s logic, based on four truth values rather than the two (true/false) of classical logic.

I can’t emphasise enough how easy this book is to read compared to most I’ve read on the subject. For example, I read all of Part 1 on a single plane journey. I will be recommending this book to any of my research students who need a basic grounding in computability or logic.

Math Circle Session 3: Knots

Today saw the third session of the primary school math circle we’ve been running for kids in Year 2 to Year 6. (I was absent for Session 2, where my wife covered mathematical card tricks.)

Today we looked at knots, drawing inspiration from Rozhkovskaya’s book as well as Adams’ introduction to knot theory. In particular, we covered the following points:

(Medial) graph representations of knot projections, moving backward and forward between them (see http://en.wikipedia.org/wiki/Knots_and_graphs)
The importance of assigning an (under/over) decision to crossings
Getting the kids to think of their own ideas for what knot equivalence might mean (shape, size, rotation, deformation – of what type) etc.

The key innovation we used here, which I think really brought the session to life, was to get the kids actually physically making the knots using Wikkistix, wax-coated string which allowed them to make, break, and remake their knots.

The kids really ran with this, and made their own discoveries, in particular:

One child discovered that some knots corresponding to the graph $K_3$ could be manipulated to produce the unknot, some could not.
A child discovered that it is possible to produce two interconnected knots, forming a link. Another child came to the same conclusion from the graph representation.
Consider the graph with vertex set $\{v_1,\ldots,v_n\}$ and edge set $\{\{v_i,v_{i+1}\} | 1 \leq i \leq n-1\}\} \cup \{\{v_n,v_1\}\}$ (is there a name for these graphs?). One child completely independently found that for $n$ even, this corresponds to a link of two knots, whereas for $n$ odd, it corresponds to a single knot.

I certainly had a lot of fun this afternoon – I hope they did too!

Where High Performance Reconfigurable Computing Meets Embedded Systems

I have just returned from attending HiPEAC 2015 in Amsterdam. As part of the proceedings, I was asked by my long-time colleague Juergen Becker to participate in a panel debate on this topic.

Panels are always good fun, as they give one a chance to make fairly provocative statements that would be out of place in a peer review publication, so I took up the opportunity.

In my view, there are really two key areas where reconfigurable computing solutions provide an inherent advantage over most high performance computational alternatives:

In embedded systems, notions of correct or efficient behaviour are often defined at the application level. For example, in my work with my colleagues on control system design for aircraft, the most important notion of incorrect behaviour is would this control system cause the aircraft to fall out of the sky? An important metric of efficient behaviour might be how much fuel does the aircraft consume? These high level specifications, which incorporate the physical world (or models thereof) in its interaction with the computational process, allow a huge scope for novelty in computer architecture, and FPGAs are the ideal playground for this novelty.
In real time embedded systems, it is often important to know exactly how long a computation will take in advance. Designs implemented using FPGA technology often provides such guarantees – down to the cycle – where others fail. There is, however, potentially a tension between some high level design methodologies being proposed and the certainty of the timing of the resulting architecture.

Despite my best attempts to stir up controversy, there seemed to be very few dissenters to this view from other members of the panel, combined with a general feeling that the world is no longer one of “embedded” versus “general purpose” computing. If indeed we can draw such divisions, they are now between “embedded / local” and “datacentre / cloud”, though power and energy concerns dominate the design process in both places.

Starting a Math Circle

I’ve been intrigued for a couple of years by the idea of math circles. Over Christmas I finally plucked up the courage to start one at a local primary school with my wife, a maths teacher. The school was happy, and recruited six pupils from Year 2 to Year 6 to attend.

Armed with a number of publications from the American Mathematical Society’s Mathematical Circles Library, our first task was to find a suitable topic for Session 1. Our primary goal was to find a topic that was clearly not everyday school maths, preferably as far away from the National Curriculum as possible, and ideally including practical activities.

In the end, we decided to look at Möbius strips. In the traditional of journal keeping for Mathematical Circles, I thought I would report the experience here in case anyone else wants to give it a go. In particular, we took the following approach:

Make zero half-turn bands (loops) and colour the outside in one colour. Then colour the inside in a different colour.
Repeat with a one half-turn band. This caused some surprise when it became apparent that one colour coloured the whole band.
Predict what would happen if you cut the zero half-turn band down the centre (prediction was universally that you’d get two zero half-turn bands). Try it.
Now predict for the one half-turn band. Children were less sure about this case, but the most popular prediction was two half-turn bands. More surprise when it turned out to create a single four half-turn band. One child then went off on his own exploring what happened when you cut one of these four half-turn bands (two four half-turn bands).

By this time some of children were already off under their own steam, trying out their own experiments. This was great, but even with only six children and with two adults, I found it hard to pull together the outcomes of these experiments in any systematic way in real time.

Eventually we discovered together that:

If the initial number of half-turns is odd, cutting gives you one larger band with more half turns. (I was hoping we’d be able to quantify this, but it turns out to be very difficult to count the number of half-turns in a strip – even for me, let alone for the younger children!)
If the initial number of half-turns is even, cutting gives you two interlinked bands with the same number of half-turns.

This took up pretty much the whole 50mins we had for Session 1, though I did briefly try to show them an explanation of why this might be the case, following the diagrammatic representation in this document from the University of Surrey. I probably didn’t leave enough time to do this properly, and they were anyway keen on cutting and exploring by that time, so with hindsight I probably should have just left them to it.

What delighted me was the child who wanted to take home his Möbius strip to show his dad. So, not a bad start to the Math Circle. Let’s see how we get on!

Overclocking-Friendly Arithmetic Needn’t Cost the Earth

This week, the FPT conference is being held in Shanghai. My PhD student, Kan Shi, will be presenting our work (joint with David Boland), entitled Efficient FPGA Implementation of Digit Parallel Online Arithmetic Operators.

In a previous paper, we’ve shown how the ideas of Ercegovac‘s “online arithmetic” – an arithmetic where computation proceeds from most significant digit to least significant digit, in contrast to the usual way we think about adding and multiplying – can be applied in the brave new world of clocking circuits faster than they “should” be able to run. The basic idea is simple: although sometimes beneficial, overclocking normal arithmetic – when it hurts – hurts bad, because errors tend to occur in the more significant digits. But if the flow of information were reversed, from more to less significant digits, then the error should hurt less too.

And so it did. But with one problem: to allow most significant digits to be generated first requires a redundant number system – a way of representing numbers where each number has more than one representation, for example, where there are two different ways of writing “10”. This redundancy cost a lot of silicon area.

This new paper shows that, in modern FPGA architectures, with careful design, the cost can be reduced significantly for adders. For multipliers, most significant digit first arithmetic has the important benefit that if you only want the most significant digits of the result, you don’t need to compute the least significant digits. In multiplication this is often the case, often in regular binary arithmetic we compute the 2n-bit result of an n by n-bit multiplication only to throw away the bottom n bits. We show in this paper that by judicious design, the area penalties of the redundant arithmetic can be eliminated in this case.

This work removes one of the last remaining hurdles that stops online arithmetic being industrially viable.

How (not) to Assess Children

Last month, the UK’s Department for Education launched a formal consultation to replace the statutory assessment in primary schools throughout England. The consultation is still running, and can be found at https://www.gov.uk/government/consultations/performance-descriptors-key-stages-1-and-2, and runs until the 18th December. Everyone can respond, and should respond. In my view, this proposal has the potential to seriously damage the education of our children, especially those who are doing well at school.

Currently, English schools report a “level” at the middle of primary school and the end of primary school in reading, writing, maths and spelling, punctuation and grammar. At the end of primary school, typical levels reported range from Level 3 to Level 6, with Level 4 being average. The new proposals effectively do away with reporting a range of attainment, simply indicating whether or not a pupil has met a baseline set of criteria. In my view this is a terrible step backwards: no longer will schools have an external motivation to stretch their most able pupils. In schools with weak leadership and governance, this is bound to have an impact.

I have drafted a response to the consultation document at https://www.scribd.com/doc/246073668/Draft-Response-to-DfE-Consultation.

My response has been “doing the rounds”. Most recently, it was emailed by the Essex Primary Heads Association to all headteachers in Essex. It has also been discussed on the TES Primary Forum and has been tweeted about a number of times.

I am not the only one who has taken issue with this consultation: others include http://thelearningmachine.co.uk/ks1-2-statutory-teacher-assessment-consultation/ and http://michaelt1979.wordpress.com/2014/11/13/primary-teachers-a-call-to-arms/.

Please add your say, and feel free to reuse the text and arguments made in this document.

Review: The Learning Powered School

This book, The Learning Powered School, subtitled Pioneering 21st Century Education, by Claxton, Chambers, Powell and Lucas, is the latest in a series of books to come from the work initiated by Guy Claxton, and described in more detail on the BLP website. I first became aware of BLP through an article in an education magazine, and since found out that one of the teachers at my son’s school has experience with BLP through her own son’s education. This piqued my interest enough to try to find out more.

The key idea of the book is to reorient schools towards being the places where children develop the mental resources to enjoy challenge and cope with uncertainty and complexity. The concepts of BLP are organised around “the 4 Rs”: resilience, resourcefulness, reflectiveness, and reciprocity, which are discussed throughout the book in terms of learning, teaching, leadership, and engaging with parents.

Part I, “Background Conditions”, explains the basis for BLP in schools in terms of both the motivation and the underlying research.

Firstly, motivation for change is discussed. The authors argue that both national economic success and individual mental health is best served by parents and schools helping children to “discover the ‘joy of the struggle’: the happiness that comes from being rapt in the process, and the quiet pride that comes from making progress on something that matters.” This is, indeed, exactly what I want for my own son. They further argue that schools are no longer the primary source of knowledge for children, who can look things up online if they need to, so schools need to reinvent themselves, not (only) as knowledge providers but as developers of learning habits. I liked the suggestion that “if we do not find things to teach children in school that cannot be learned from a machine, we should not be surprised if they come to treat their schooling as a series of irritating interruptions to their education.”

Secondly, the scientific “stable” from which BLP has emerged is discussed. The authors claim that BLP primarily synthesises themes from Dweck‘s research (showing that if people believe that intelligence is fixed then they are less likely to be resilient in their learning), Gardner (the theory of multiple intelligences), Hattie (emphasis on reflective and evaluative practice for both teachers and pupils), Lave and Wenger (communities of practice, schools as an ‘epistemic apprenticeship’), and Perkins (the learnability of intelligence). I have no direct knowledge of any of these thinkers or their theories, except through the book currently under review. Nevertheless, the idea of school (and university!) as epistemic apprenticeship, and an emphasis on reflective practice ring true with my everyday experience of teaching and learning. The seemingly paradoxical claim that emphasising learning rather attainment in the classroom leads to better attainment is backed up with several references, but also agrees with a recent report on the introduction of Level 6 testing in UK primary schools I have read. The suggestion made by the authors that this is due increased pressure on pupils and more “grade focus” leading to shallow learning.

The book then moves on to discuss BLP teaching in practice. There is a huge number of practical suggestions made. Some that particularly resonated with me included:

pupils keeping a journal of their own learning experiences
including focus on learning habits and attitudes in lesson planning as well as traditional focuses on subject matter and assessment
a “See-Think-Wonder” routine: showing children something, encouraging them to think about what they’ve seen and record what they wonder about

Those involved in school improvement will be used to checklists of “good teaching”. The book provides an interesting spin on this, providing a summary of how traditional “good teaching” can be “turbocharged” in the BLP style, e.g. students answer my questions confidently becomes I encourage students to ask curious questions of me and of each other, I mark regularly with supportive comments and targets becomes my marking poses questions about students’ progress as learners, I am secure and confident in my curriculum knowledge becomes I show students that I too am learning in lessons. Thus, in theory, an epistemic partnership is forged.

There is some discussion of curriculum changes to support BLP, which are broadly what I would expect, and a variety of simple scales to measure pupils’ progress against the BLP objectives to complement more traditional academic attainment. The software Blaze BLP is mentioned, which looks well worth investigating further – everyone likes completing quizzes about themselves, and if this could be used to help schools reflect on pupils’ self-perception of learning, that has the potential to be very useful.

In a similar vein, but for school leadership teams, the Learning Quality Framework looks worth investigating as a methodology for schools to follow when asking themselves questions about how to engage in a philosophy such as BLP. It also provides a “Quality Mark” as evidence of process.

Finally, the book summarizes ideas for engaging parents in the BLP programme, modifying homework to fit BLP objectives and improve resilience, etc.

Overall, I like the focus on:

an evidence-based approach to learning (though the material in this book is clearly geared towards school leaders rather than researchers, and therefore the evidence-based nature of the material is often asserted rather than demonstrated in the text)
the idea of creating a culture of enquiry amongst teachers, getting teachers to run their own mini research projects on their class, reporting back, and thinking about how to evidence results, e.g. “if my Year 6 students create their own ‘stuck posters’, will they become more resilient?”

I would strongly recommend this book to the leadership of good schools who already have the basics right. Whether schools choose to adopt the philosophy or not, whether they “buy in” or ultimately reject the claims made, I have no doubt that they will grow as places of learning by actively engaging with the ideas and thinking how they could be put into practice, or indeed whether – and where – they already are.

Insure yourself against your own inaccuracy

Last week saw the 19th World Congress of the International Federation of Automatic Control in Cape Town, South Africa. Three of my collaborators, Andrea Suardi, Stefano Longo and Eric Kerrigan, were there to present our joint paper Robust explicit MPC design under finite precision arithmetic.

The basic idea of this work is simple but interesting. Since we know we make mistakes, can we make decisions in a way that insures ourselves against our own faulty decision making? In a control system, we typically want to control a “real world thing” – an aircraft, a gas turbine, etc. Ourselves and others have proposed very sophisticated ways to do this, but since with each finite precision operation we might drift further away from the correct result, can we develop our algorithm in a way that provides a guaranteed behaviour?

We show that since control engineering provides tools to control systems with uncertain behaviour, it’s possible to incorporate the uncertainty of the control algorithm itself into the model of the system we’re controlling, to produce a kind of self-aware system design.

While the setting of this paper is in so-called explicit model predictive control, there’s no reason why this general philosophy should not extend to other decision making processes. It provides a rigorous way to think about the impact of decision quality on the overall behaviour of a system, since we can generally make decisions in any number of ways ranging from “quick and dirty” to “slow and thoughtful”, we could decide how to decide based on ideas like this.

Review: Practical Foundations for Programming Languages

A lot of my work revolves around various problems encountered when one tries to automate the production of hardware from a description of the behaviour the hardware is supposed to exhibit when in use. This problem has a long history, most recently going by the name “High Level Synthesis”. A natural question, but one that is oddly rarely asked in computer-aided design, is “what kind of description?”

Of course not only hardware designers need to specify behaviour. The most common kind of formal description is that of a programming language, so it seems natural to ask what the active community of programming language specialists have to say. I am fortunate enough to be an investigator on a multidisciplinary EPSRC project with my friend and colleague Dan Ghica, specifically aimed at bringing together these two communities, and I thought it was time to undertake sufficient reading to help me bridge some gaps in terminology between our fields.

With this is mind, I recently read Bob Harper‘s Practical Foundations for Programming Languages. For an outsider to the field, this seems to be a fairly encyclopaedic book describing a broad range of theory in a fairly accessible way, although it did become less readily accessible to me as the book progressed. My colleague Andy Pitts is quoted on the back cover as saying that this book “reveals the theory of programming languages as a coherent scientific subject,” so with no further recommendation required, I jumped in!

I like the structure of this book because as a non-specialist I find this material heavy going: Harper has split a 500 page book into fully 50 chapters, which suits me very well. Each chapter has an introduction and a “notes” section and – for the parts in which I’m not very interested – I can read these bits to still get the gist of the material. Moreover, there is a common structure to these chapters, where each feature is typically first described in terms of its statics and then its dynamics. The 50 chapters are divided into 15 “parts”, to provide further structure to the material.

The early parts of the book are interesting, but not of immediate practical relevance to me as someone who wants to find a use for these ideas rather than study them in their own right. It is nice, however, to see many of the practical concepts I use in the rare occasions I get to write my own code, shown in their theoretical depth – function types, product types, sum types, polymorphism, classes and methods, etc. Part V, “Infinite Data Types” is of greater interest to me just because anything infinite seems to be of interest to me (and, more seriously, because one of the most significant issues I deal with in my work is mapping of algorithms conceptually defined over infinite structures into finite implementations).

Where things really get interesting for me is in Part XI, “Types as Propositions”. (I also love Harper’s distinction between constructive and classical logic as “logic as if people matter” versus “the logic of the mind of God”, and I wonder whether anyone has explored the connections between the constructive / classical logic dichotomy and the philosophical idealist / materialist one?) This left me wanting more, though, and in particular I am determined to get around to reading more about Martin-Löf type theory, which is not covered in this text.

Part XIV, Laziness, is also interesting for someone who has only played with laziness in the context of streams (in both Haskell and Scala, which take quite different philosophical approaches). Harper argues strongly in favour of allowing the programmer to make evaluation choices (lazy / strict, etc.).

Part XV, Parallelism, starts with the construction of a cost dynamics, which is fairly straight forward. The second chapter in this part looks at a concept called futures and their use in pipelining; while pipelining is my bread and butter in hardware design, the idea of a future was new to me. Part XVI, Concurrency, is also relevant to hardware design, of course. Chapter 43 makes an unexpected (for me!) link between the type system of a distributed concurrent language with modal logics, another area in which I am personally interested for epistemological reasons, but know little.

After discussing modularity, the book finishes off with a discussion of notions of equivalence.

I found this to be an enlightening read, and would recommend it to others with an interest in programming languages, an appetite for theoretical concerns, but a lack of exposure to the topics explored in programming language research.