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.

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.

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.

Review: Children’s Minds

My third and final piece of holiday reading this Summer was Margaret Donaldson’s Children’s Minds, the first book I’ve read on child psychology.

This is a book first published in 1978, but various sources suggested it to me as a good introduction to the field.

I wasn’t quite sure what to make of this book. The initial chapters seem to be very much “of the time”, a detailed critique of the theory of Piaget, which meant little to me without a first hand knowledge of Piaget’s views. Donaldson does, however, include her own summary of Piaget’s theories as an appendix.

Donaldson argues that children are actually very capable thinkers at all ages, but that effort must be made to communicate to them in a way they can understand. Several interesting experiments by Piaget, from which he apparently concluded that children are incapable of certain forms of thought, are contrasted against others by later researchers who found that by setting up the experiments using more child-friendly communication, these forms are apparently exhibited.

The latter half of the book becomes quite interesting, as Donaldson explores what schools can do during reception (kindergarten) age and beyond to ensure that the early excitement of learning which most children have is not destroyed by schools themselves. It is fascinating, for example, to read that

There is now a substantial amount of evidence pointing to the conclusion that if an activity is rewarded by some extrinsic prize or token – something quite external to the activity itself – then that activity is less likely to be engaged in later in a free and voluntary manner when the rewards are absent, and it is less likely to be enjoyed.

I would be most interested in what work has been done since the 70s on this point, as if this is true then it seems to clash markedly with practice in the vast majority of primary schools I know.

The final part of the text is remarkably polemical:

Perhaps it is the convenience of having educational failures which explains why we have tolerated so many of them for so long…

A vigorous self-confident young population of educational successes would not be easy to employ on our present production lines. So we might at last be forced to face up to the problem of making it more attractive to work in our factories – and elsewhere – and, if we had done our job in the schools really well, we should expect to find that economic attractions would not be enough. We might be compelled at last to look seriously for ways of making working lives more satisfying.

Little progress since the 70s, then! Interestingly (for me) Donaldson approvingly quotes A.N. Whitehead’s views on the inertia of education; I know Whitehead as a mathematician, and was completely unaware of his educational work.

As I mentioned, this is the first book on child psychology I’ve read. I found it rather odd; I am not used to reading assertions without significant citations and hard data to back up the assertions. I am not sure whether this is common in the field, whether it is Donaldson’s writing, or whether it is because this is clearly Donaldson writing for the greater public. I tended to agree with much of what was written, but I would have been far more comfortable with greater emphasis on experimental rigour. There is much in here to discuss with your local reception class teacher; I want to know more about older children.


Review: Risk Savvy

My second piece of holiday reading this Summer was Gigerenzer’s Risk Savvy. This is an “entertaining book” for a general readership.

I learnt quite a bit from this book, but still found it frustrating and somewhat repetitive. There are many very interesting anecdotes about risk and poor decision making under risk, as well as lots of examples of how we are manipulated by the press and corporations into acting out of fear.

However, I don’t necessarily agree with the conclusions reached.

As an example, Gigerenzer clearly shows that PSA testing for prostate cancer is the US does more harm than good compared to the UK’s approach. More people are rendered incontinent and impotent through early intervention, without any significant difference in mortality rate. A similar story is told for routine mammography. But the conclusion that Gigerenzer seems to draw from these – and similar – studies, is that “it’s better not to know”, whereas my conclusion would be “it’s better not to intervene immediately”. I can’t see why simply knowing more should be worse.

I was also frustrated by the way Gigerenzer deals with the classification of risks into “known risks”, i.e. those for which good statistical information is available, and “unknown risks”. He convincingly shows that – all too often – we deal with unknown risks as if they were known risks, resulting in poor decision making. To me this appears to be a mirror of the two ways I know of dealing with uncertainty in mathematical optimization: stochastic versus robust optimization. This is a valuable dichotomy, but I don’t think that Gigerenzer’s conclusion that, in the presence of “unknown risk”, “simple is good” and “go with your gut feeling” is well justified. I do think that more needs to be done by decision makers to factor in the computational complexity of making decisions – and the overfitting of overly complex models – into decision making methodologies, but if “simple is good” then this should be a derivable result; I would love to see some mathematically rigorous work in this area.

Review: The Adventure of Numbers

One of the books I took on holiday this year was Gilles Godefroy’s The Adventure of Numbers. This is a great book!

The book takes the reader on a tour of numbers: ancient number systems, Sumerian and Babylonian number systems (decimal coded base 60, from which we probably get our time system of hours, minutes and seconds), ancient Greeks and the discovery of irrational numbers, Arabs, the development of imaginary numbers, transcendentals, Dedekind’s construction of the reals, p-adic numbers, infinite ordinals, and the limits of proof.

This is a huge range, well written, and while fairly rigorous only requires basic mathematics.

I love the fact that I got from this book both things that I can talk to primary school children about (indivisibility of space through a geometric construction of the square root of two and its irrationality) and also – unexpectedly – an introduction to the deep and beautiful MRDP theorem which links two sublime interests for me: computation (in a remarkably general sense) and Diophantine equations.

What’s not to love?