Category: resources

To Mock a Mockingbird or: How I learned to stop worrying and learned combinatory logic

mockingbirdYesterday I finished reading one of the most remarkable books I read in my life: “To Mock a Mockingbird and Other Logic Puzzles: Including an Amazing Adventure in Combinatory Logic” by Raymond Smullyan. When I finished reading The Little Schemer that book was listed as one of the suggested further readings. The title was quite intriguing so I got the book and started reading it. That was a year ago and I finished the book yesterday. Why? Because I got stuck and couldn’t understand some of the material. Luckily I now had some time to approach the book once again and grok it.

As the title suggests the book is a collection of logic puzzles. Out of six parts of the book – 25 chapters total – two are devoted to general logic puzzles, many of them about different aspects of truth telling. These can be regarded as a warm-up because in the third part the book makes a sudden turn towards combinatory logic. And this is the moment I found difficult in the book. Of course Smullyan doesn’t expect that readers work with combinators so he camouflages them as singing birds. Having some mathematical background I rejected this cover and tried to approach problems formally. Now, after reading the book, I think this was a major mistake that lead to my failure. I wasn’t able to deal with first 10 puzzles but I was more or less able to follow the solutions. Still I felt that reading solutions without being able to solve puzzles by myself was cheating so I gave up. A few months later I made another approach to the book but the results were exactly the same. Three weeks ago I made a third attempt, but I decided not to give up even if I won’t be able to come up with my own solutions. I figured that being able to only understand given solutions is completely fine. That decision turned out to be a good one. Although at first I wasn’t able to solve puzzles on my own at some point things just clicked. I solved one puzzle, then another and another and I realized that I know how to solve most of the puzzles. From now on the book went quite smoothly. Part four about logical paradoxes and inconsistencies in logical systems gave me some problems and I was afraid that each subsequent part will be equally challenging but it turned out that it was not the case. Part five gives a nice overview of computations using SKI combinators, while part six presents Church encoding of natural numbers and culminates with a proof of Gödel’s theorem.

Some advice

The book is challenging on the one hand but it is also very rewarding. One of the most satisfying moments was realizing that I am able to write expressions like

g\tilde{a}\tilde{b}=Z\tilde{a}f(Z\tilde{b}t(g(P\tilde{a})(P\tilde{b})))

and then seeing that these are in fact nothing more but recursive programs. However it took me some work to get to this point and I think I can give future readers some advice about approaching the book. I’ve seen people on the internet saying they don’t understand parts of the book about combinators. In fact this is the same problem I faced on my initial contact. So my advice number one is: don’t give up. It looks like working with combinators just isn’t an inborn talent for most of us. It’s something that we just need to learn and it’s completely fine if you can’t figure out solutions on your own. It is important however to follow solutions given in the book. At some point you should understand how all of this works. Also don’t make my mistake of trying too formalize things to much. Don’t try to apply presented facts about combinators to anything else you know like maths or functional programming. This seems to only bring confusion. At some point things will become clear, but until then be patient. I wasn’t and in my attempts I even tried to introduce universal and existential quantification, which was a complete overkill. Also, it is very important to make notes. Keep conclusions of the puzzles in a notebook so you have easy access to a list of known facts. This is crucial since some solutions are based on facts proved 100 pages earlier. I also suggest having a separate scratch-pad.

Summary

To “Mock a Mockingbrd” was a very insightful book and one of the most unusual ones I have read. It presents difficult material in a fun and entertaining way, but don’t be fooled – you will spend hours with pen and paper to complete this book. I highly recommend it to anyone interested in logic and functional programming. What functional programming has to do with it? Unrelated as it may seem I feel that this book has given me knowledge necessary to tackle type-level programming in Haskell. Just three weeks ago this seemed like a complete black magic and now it looks comprehensible.

Coders at work. A short review

CodersAtWorkI was visiting my friend before Christmas and on his shelf I found “Coders at Work” by Peter Seibel1. It’s a collection of interviews with fifteen world-known programmers (assuming a programmer can be world-known). Among the names two have caught my eye: Simon Peyton Jones and Guy Steele. I borrowed the book and ended up reading interviews with these two researchers and Donald Knuth. Not surprisingly, interview with Simon Peyton Jones was the one that interested me the most. I found it very enjoyable to read accounts of how these people became programmers in times where computers where huge machines available only at universities. On the other hand I also found some parts of the interviews to be a bit dry, e.g. SPJ goes into the discussion of Software Transactional Memory in Haskell and I think that reader not familiar with STM will not get much out of this. Also, reader familiar with STM will probably not need this discussion.

There are two thoughts that stroke me during the reading. When reading interview with Knuth I realized that there are actually people that are unable to learn programming. I teach at the university and I’ve seen many first year students who completely don’t grasp programming but somehow it never occurred to me that some of them might not ever be able to learn this. Second thought, the more important one, is that all these famous programmers were extremely lucky guys. They all got the chance to develop their talents. I believe that there are even more very talented people who could have had even greater impact on computer science, but they just didn’t get their chance.

One last thing. SPJ mentions that his “Aha!” moment in functional programming was Arthur Norman’s demonstration of implementing double-linked list in a purely functional fashion, that is without any side effects. I tried to google more information on that but with no result. So if anyone has an idea how to implement such a list please tell me. The only thing that comes to my mind are zippers. They do allow traversal of list in both directions and modifying its elements so this might be it.

  1. In fact I found Polish edition. []

The Little Schemer. Book review

Exactly one year ago I was in the middle of reading “Seven languages in seven weeks” by Bruce Tate. This book introduced me to functional programming with languages like Erlang, Scala, Haskell and Lisp. Now, the Lisp part is the interesting one. I was googling some things about Lisp and somehow I landed on Paul Graham’s page. His essays on Lisp fascinated me so much that I decided to learn me some Lisp for great good. So when I reached the chapter about Clojure (Lisp dialect for JVM) I actually decided to skip it and learn more on my own. After some googling I settled on Scheme (another alternative was Common Lisp). I began with reading the official R5RS specification (only about 50 pages) but that definitely wasn’t enough. On various blogs and sites on the Internet I found people talking about this book The Little Schemer by Daniel P. Friedman and Matthias Felleisen, how great and different from other books it is and how it can change the way you think. I decided to give The Little Schemer a try.

The_Little_SchemerThe first thing I noticed after opening the book is that it is indeed unlike anything I have read so far. Instead of explaining things directly, the book presents a dialogue between the authors and a reader. There are no paragraphs, just two columns of text – left with authors’ questions, the second with reader’s responses. This dialogue is very informal and usually ends up with talking about food. Sounds strange? Well, it was at first but as I went on I found this style very fun. Of course reading is not enough – you have to actually work through the code on your own and I admit that I found that part very entertaining and rewarding, especially when I was able to figure out solutions before reading them.

The book consist of ten chapters. Eight of them are dedicated to general lisp programming. Book starts with simple concepts like basic operations on lists and moves on to more and more advanced aspects of recursion. I feel that it has learned me how to think in a recursive way, which in turn made learning Haskell much easier. Last two chapters of the book are quite difficult though. Chapter 9 gives a step by step derivation of the Y-combinator. Well, almost step by step – I had a feeling that some parts were actually left out and I had problems understanding what is going on. Luckily Peteris Krumins has written a great post in which he derives Y-combinator and fills the gaps present in The Little Schemer. Even after reading that post I still needed about 3 days to understand what’s going on in the Y-combinator, but once things clicked it was my “Aha!” moment. That’s probably the most fascinating thing I’ve learned so far in computer science. Chapter 10 pursues the goal of writing Lisp interpreter in Lisp. The beauty of Lisp lies in the fact that it is actually a relatively easy task requiring surprisingly little lines of code. Check out this article by Paul Graham to see for yourself. Solution from The Little Schemer is actually a bit more complex than the one given by Graham and again it took me some considerable effort to work my way through this chapter.

At the end of The Little Schemer there are some references to books that in the authors’ opinion are worth reading. This is not only computer science stuff – among references is The Annotated Alice: Alice’s Adventures in Wonderland and Through the Looking Glass by Lewis Carroll – and I found one of the listed books to be very fascinating: To Mock a Mockingbird by Raymond Smullyan. It’s an introduction to combinatory logic given in a form of riddles. I’m somewhere in the middle and will hopefully finish reading it some day.

I guess the opinions on the internet were right – The Little Schemer is a great book and it really teaches how to think in a recursive way. I suggest reading it to anyone who is interested in being a better programmer, functional or not. This will be a good investment, especially that reading the book doesn’t take much time (authors warn the reader not to read it in less than three sittings).

Finally, there’s a sequel to The Little Schemer called The Seasoned Schemer. Unfortunately I was unable to find it so if any of you has a spare copy and would be willing to send it to Poland just let me know :-)

Staypressed theme by Themocracy