Motivating Category Theory for Haskell for Non-mathematicians

The Issue:  Why Study Category Theory?

Two days ago, there was another interesting post by Andrzej Jaworski, entitled “[Haskell-cafe] Mathematics for Uninterested,” dated “Sat, 17 Jan 2009 05:15:25 +0100,” on the Haskell-cafe mailing list on the Haskell programming language, offering an explanation of why mathematics is important for learning Haskell. In particular, he wrote:

MATHEMATICS_IS_ABOUT_SIMPLIFYING_THINGS.

MATHEMATICS = MATHEMATICAL_KNOWLEDGE + FORMAL_METHODS_of_THINKING

You need only the second part for Haskell.

He then continued:

… Category Theory generalizes our mathematical experience along the line that we know
more that we can prove.

Nevertheless, many non-mathematicians continue to have much difficulty in motivating study of category theory.  Some regard it as too theoretical.  Others regard it as too abstract.  And still others regard it as too dry.

While I cannot argue too much against the second point (indeed, category theory has been nicknamed “abstract nonsense,” although not necessarily pejoratively), and cannot truly deny the first for those who do not prefer theory, I have something to say from personal experience, as a student who overcame math phobia to appreciate beauty in mathematics, about the third.

Each student learns differently.  Some learn best by seeing examples.  Some learn best by studying theory.  Still others learn best by actually solving problems.

Case Study:  My Personal Experience in Approaching Mathematics

Several years ago, when I was still living in Manhattan, I read an article in a local newsletter about how different students had different learning styles in primary (and possibly secondary) school, and how putting different students into the wrong type of class inhibited their learning.  In particular, the article discussed how most students in the classes could be grouped into either of two different learning styles:  those who learned by example, and those who learned by theory.  Students who learned by example needed to see concrete examples of the mathematics in action in order to infer the reasoning; conversely, students who learned by theory learned best by studying the general theory from which to deduce specific applications.  Neither style was correct; they were simply different, and suited different types of students.

The same can probably be said for learning category theory.  Personally, I learn best from a combination of first studying theory, and actually applying the theory to incrementally more sophisticated problems.  Without the theory, I cannot understand the examples, but without actually applying the theory, I tend to forget about it very quickly.  Applying the theory, especially in a creative manner, makes it stick in my brain.

However, although I eventually was able to major in computer science, getting there was a long, arduous, grueling odyssey.  The most difficult part was conquering a required course in the design and analysis of algorithms.  I had come to college from a self-educated background, studying on my own since fifth grade in elementary school without any teacher, using only books, because of family circumstances.  In the end, I wound up studying throughout my secondary school years at home.

However, my interests had been in writing and multimedia applications.  As a result, prior to coming to college, while I had had extensive practice in writing, I had had minimal exposure to mathematics.  My first exposure to college-level mathematics resulted in an outbreak of math phobia.

Nevertheless, I still wished to study something related to computers in college.  Because the school happened to be a research-oriented school with a theoretically-oriented faculty, the only computer-related topic available happened to be computer science, and the focus was on theory.

Theoretical computer science happens to have a heavy focus on mathematics.  However, I happened to be struggling with math phobia.  I needed to find something interesting about mathematics if I was to remain in computer science.

Fortunately, one very generous mathematics student offered to tutor me gratis once per week over one summer.  He gave me what he termed “an elementary course from an advanced viewpoint.”  He started out from axiomatic set theory, focusing on lemmas and proofs of theorems, and gave me an intuitive grasp of such elementary concepts as set comprehension, power sets, ordered pairs, and Cartesian products.  I later learned about Russell’s paradox, and found it rather interesting.  At the end of the summer, I was able to take and pass an undergraduate course at my college in axiomatic set theory.  Then I discovered Gödel, Escher, Bach: an Eternal Golden Braid, was fascinated, and the next semester, I proceeded on to pass recursive function theory.  Then I took a course in automata theory.  Then I took a course (albeit in the philosophy department) in meta-logic.  Then I took a graduate-level course in recursion equations (domain theory).

After then taking a year’s leave of absence to study discrete mathematics for computer science outside of my official curriculum, I was able to return and eventually pass the required course in the design and analysis of algorithms.  The next semester, I then took an additional course in advanced algorithms, which turned out to be significantly less of a hassle than the first course in algorithms (the exercises were more abstract, but the workload was considerably less, so I went to the library and did some research for each problem set).  One of my favorite courses later wound up being one in formal semantics of programming languages, where I was exposed to this fascinating creature, the lambda calculus.

Yet somehow along the way … I forgot how to program well.  I had to struggle through another required course in systems programming in C, and this time acquired programming phobia, which I had not had before.  Oh dear, I had forgotten how to use pointers in coding linked lists!  I only recovered after auding a course using Scheme to teach computer science under a professor who also taught Haskell.  Then I audited another course under this professor in Haskell.  Thank goodness!  No more pointers, no more memory management!  Instead, higher-order functions!

A Short, Thin, Elementary, Yet Influential Book and Its Approach

One of the most influential books in my struggle to conquer algorithms was a most unassuming, very thin, informal book called Naive Set Theory, by Paul R. Halmos.  This book had no explicit exercises marked as such, and the treatment was almost conversational in tone, yet almost every sentence was an implicit exercise in abstract thinking.  Each chapter was only three to five pages long, with almost no equations, and the entire book was only about a hundred pages long.  The covers together were barely thicker combined than the text.  Yet it still covered the following topics:

the Axiom of Extension
the Axiom of Specification
unordered pairs
unions and intersections
complements and powers
unordered pairs
relations
functions
families
inverses and composites
numbers
the Peano Axioms
arithmetic
order
the Axiom of Choice
Zorn’s Lemma
well ordering
transfinite recursion
ordinal numbers
sets of ordinal numbers
ordinal arithmetic
the Schröder-Bernstein Theorem
countable sets
cardinal arithmetic
cardinal numbers

Imagine covering an entire topic in mathematics with almost no equations, and no explict exercises, and only three to five pages per chapter!  This was easily one of the shortest books I ever read in college, yet one of the most influential: Not only did it resolve the math phobia, but it also imbued me with an appreciation for elegant proofs, and hence for beauty in mathematics.

A Related Topic:  Computability Theory

Another experience that helped in my endeavor was an independent seminar with one researcher in automata theory (it was actually this experience which eventually led to my auditing a course in this subject).  My employer for one summer was a programmer who had graduated from the same university.  He helped me set up an independent once-a-week seminar (actually a private tutorial) covering the book Elements of the Theory of Computation (first hardcover edition), by  Harry R. Lewis and Christopher Papadimitriou.  I would read the book, collect questions, and bring them to the seminar every week.  This book covered such topics as computability, the diagonalization lemma, unsolvability, finite state automata, Turing machines, mathematical logic, and other related topics.  What I liked about this book was the aspect that, although it gave a very formal, abstract treatment to computability theory, otherwise it did not assume any specific knowledge of any area of mathematics.

I think that a book similar to the above two for category theory would be highly useful, at least for students with the same learning pattern as myself.  For such students, I believe that what is most important is the intuition; the formalism can come later.  Mathematics is not about formalism; it is about insight: insight into patterns and structure, and the beauty that comes with such patterns.  While a book with many exercises would probably be necessary at some point, for a first course in category theory for a non-mathematician, an approach similar to Halmos’ would seem most effective.

Set Theory vs. Category Theory:  The Conflict in Approach

The only problem with recommending a book on set theory to a student of category theory is that the approaches do not overlap. Set theory studies what is inside sets; category theory studies what is outside them.

Specifically, set theory starts out by defining the empty set, then defining basic axioms, and then defining certain operations on sets and functions operating on sets in leading up to lemmas and theorems about properties of sets.  However, the focus is essentially on what is inside the sets.

However, category theory ignores what is inside, and instead focuses on structure-preserving mappings (known as “homomorphisms”) between different sets having a specific structure.  These homomorphisms lead to theorems about the structure of the sets.  Thus, it is these mappings in category theory that are the focus, not explicitly what is inside the sets.  This is the origin of the nickname of “abstract nonsense” in reference to category theory.

Therefore, there is a risk that exposing a new student of Haskell first to set theory could actually confuse the student upon subsequent exposure to category theory. Therefore, I might substitute instead an elementary introduction to category theory with an informal, somewhat conversational tone, such as the following:

Conceptual Mathematics: A First Introduction to Categories
by F. William Lawvere and Stephen Hoel Schanuel
Cambridge: Cambridge University Press, 1997
As discussed in my blog entry “Learning Haskell through Category Theory, and Adventuring in Category Land: Like Flatterland, Only About Categories,”this is an elementary introduction to category theory, with a conversational tone, using such examples as Galileo and the flight of a bird for illustration.

Advanced Topics for Further Study

Once the student has had a taste of category theory, there are two possible alternatives:  Either broaden the topics, or deepen them.  The latter has already been discussed in my above-mentioned blog post “Learning Haskell through Category Theory, and Adventuring in Category Land: Like Flatterland, Only About Categories“; here I discuss the former.

As mentioned above, automata theory is one possibility for advanced study for students who have acquired a taste for theory and wish to explore more:

Elements of the Theory of Computation (first hardcover edition)
by Harry R. Lewis and Christopher Papadimitriou
New Jersey: Prentice Hall, Inc., June 1981
As discussed above, a formal, rigorous treatment of the theory of computation. The book assumes the ability to reason abstractly, but does not assume familiarity with any specific areas of mathematics. Most readers either love or hate this book, depending on whether they are theoretically-inclined.

Another possibility is recursive function theory:

Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science (Computer Science and Scientific Computing)
by Martin Davis, Ron Sigal, and Elaine J. Weyuker
San Francisco, California: Morgan Kaufmann Publishers, 1994
This book, like Elements of the Theory of Computation, is formal, but does not assume any specific background in mathematics.  One of the authors of this book, Ron Sigal, used to be my professor for set theory, recursive function theory, and recursion equations (domain theory) in college. He was friendly and approachable, had an exceptionally clear teaching style, and usually spent the first class in an interesting lecture discussing the historical background of the subject.

Still another possibility is my nemesis, the design and analysis of algorithms:

Compared to What?: An Introduction to the Analysis of Algorithms (Principles of Computer Science Series)
by Gregory J.E. Rawlins
New York: W. H. Freeman, November 15, 1991
This was my favorite book on algorithms in college, and played an instrumental role in allowing me to pass this subject. Without this book, I probably would have had a much more difficult time in clearing this subject. This book approaches each algorithm from the perspective of how the algorithm is arrived at, rather than just handing the solution ready-made, interspersing numerous entertaining illustrations and quotes from works by Lewis Carroll. I further wrapped this book in kaleidoscopic bookwrap to strengthen the feeling of being in algorithm wonderland while reading this book, and the effect worked like a charm: I learned the algorithms, finally passed the course, and completed the major.

Introduction to Algorithms, Second Edition
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Cambridge, Massachusetts: The MIT Press, September 1, 2001
This is the second edition of a classic work in the subject. It provides a rigorous theoretical treatment of algorithms. The first edition of this book forced the author of this blog to undertake a seemingly never-ending journey through set theory, discrete mathematics, recursive function theory, automata theory, meta-logic, and recursion equations (domain theory) in order to clear the topics covered by this book. I haven’t read the second edition yet, but the first edition was very complete and thorough, and was basically a mathematical encyclopedia on algorithms, complete with a brief introduction to prerequisite topics, detailed development of proofs, numerous exercises that led to other parts of the main text, numerous starred exercises of special difficulty (my professor hired a student who did all the starred exercises on his problem sets as a summer research intern), detailed pseudocode, analysis of the pseudocode, proofs of the analysis of the pseudocode, and highly detailed illustrations covering details of the algorithms and their proofs. Of course, this book has no solutions. Hey, who needs solutions? Nobody said you needed sleep, right?

The Art of Computer Programming (currently, Volumes 1 to 3 and Fascicles 0 to 4 of Volume 4, with Volume 5 planned for release in 2015, and Volumes 6 and 7 planned for later release)
by Donald E. Knuth
Reading, Massachusetts: Addison-Wesley, 1997 to 2006 and pending
The original classic work on the design and analysis of algorithms.  Still in progress.  Originally begun in 1962, written by compiler expert Donald E. Knuth.  Volume 1 covers fundamental algorithms, volume 2 covers seminumerical algorithms, volume 3 covers sorting and searching, volume 4 covers combinatorical algorithms, volume 5 is scheduled to cover syntactic algorithms, volume 6 is scheduled to cover the theory of context-free languages, and volume 7 is scheduled to cover compiler techniques.  Exercises range in difficulty from “warm-up” exercises to research problems.

One last topic is algebra, for which there is reputedly a very approachable work focusing on a limited scope of topics and exploring them to great depth:

Topics in Algebra
by I. N. Herstein
Xerox Corporation, 1975
Although I haven’t read this book, it has earned very high reviews for exposition and flow. The book is reputedly designed so that a few basic ideas are focused on, and problems in them explored, so that each new topic flows seemlessly from the previous one.

Conclusion

Let students take the book on the subway, train, or bus, and have them think about the categories in their sleep!  Gradually, their curiosity will be piqued, and they will understand categories.  Then they can read a second book with many exercises.  But while they still have curiosity, let them at least visualize and juggle the categories in many ways in their heads before forcing them off!  The more easily they can digest their first book, the more likely their curiosity will stay.

Learning Haskell through Category Theory, and Adventuring in Category Land: Like Flatterland, Only About Categories

Two days ago, there was an interesting post by Andrzej Jaworski, entitled “[Haskell] Teach theory then Haskell as example,” dated “Wed, 14 Jan 2009 04:37:33 +0100,” on the Haskell mailing list on the Haskell programming language, recommending that Haskell be taught “on most abstract terms in a framework of higher order logic, types and CT right from the start.”  While I agreed with the gist of his post, I hadn’t found an appropriate publication on category theory that addressed the subject at the proper pace, level, and perspective.  Most publications did not explain enough detail, assumed too many topics not covered, or did not explain the concepts in a manner which would allow me to form a visual framework of reference in my mind.  In my response, I listed the following publications on category theory, a branch of mathematics which forms a theoretical framework for Haskell. (Author names and dates have been added, explicit URL’s replaced by hyperlinks in titles, and descriptions expanded, for referential convenience. In addition, I have added one additional book entry for cross-referential purposes.):

Category Theory Books:

Conceptual Mathematics: A First Introduction to Categories (Paperback)
by F. William Lawvere (author) and Stephen Hoel Schanuel (author)
Cambridge: Cambridge University Press, 1997
An elementary introduction to category theory

An introduction to category theory in four easy movements
by A. Schalk (author) and H. Simmons (author)
Manchester: A. Schalk and H. Simmons, October – December, 2005
A somewhat informal, reportedly in-depth introduction to category theory, which some students have described as being intricately layered. Personally, I like Harold Simmons style, because it seems to have more personality than that of many other authors on category theory. Sometimes he is actually funny; e.g., he writes (see p. 6),

“In the original examples of categories the arrows were morphisms which were then called homomorphism, and it wasn’t realized that this family could be very large. (Some out and out category theorists still don’t realize the significance of this. On the other hand, some off the wall set theorists don’t realize the significance of category theory.)”

I’ve heard of the UNIX wars and the editor wars, but now we have the category theory vs. set theory wars! The more some things change, the more they stay the same….

Category Theory by Magic: A short introduction to the basics of category theory
by Harold Simmons
Manchester: Harold Simmons, November 29, 2008
A somewhat more advanced text than An introduction to category theory in four easy movements, intended specifically for “postgraduate students,” but written in an exceptionally clear style.

Toposes, Triples and Theories
by Michael Barr and Charles Wells
Michael Barr and Charles Wells, 2000
An often-referenced introduction to category theory, intended for graduate students, reportedly
discussing monads as “triples.”  This book is a sequel to Category Theory for Computing Science, by the same author. This is one of the publications listed in the bibliography by Simmons in Category Theory by Magic: A short introduction to the basics of category theory.

Category Theory for Computing Science (Third Edition)
by Michael Barr and Charles Wells
Hertfordshire, U.K.: Prentice Hall International (UK) Ltd., 1999
Prequel to Toposes, Triples and Theories, “written specifically to be read by researchers and students in  computing science.”    Apparently, only available in dead-tree format.  Can be ordered from Centre de recherches mathématiques, or by e-mail to crmbooks@crm.umontreal.ca.  Often cited in the literature.

Categories and Computer Science
by R. F. C. Walters
Cambridge: Cambridge University Press, August 1992
Reportedly a straightforward introduction to category theory, with many examples from computer science

Arrow, Structures and Functors – The Categorical Imperative (no hyperlink available)
According to the HaskellWiki page on category theory, an out-of-print book covering monads and the Yoneda lemma, with very little prerequisite knowledge

Category Theory
by Steve Awodey
Oxford: Oxford University Press, 2006
This text aims to minimize mathematical prerequisites in providing an introduction to category theory for students in such topics as computer science, logic, linguistics, cognitive science, or philosophy, who may not necessarily be working (or aspiring) mathematicians. Students are not assumed to have much background in mathematics beyond a course in discrete mathematics and some calculus or linear algebra or logic.

The book starts out with a few basic examples of posets and monoids, and then develops them in further detail. While the book assumes little in mathematical prerequisites, it does not sacrifice rigor, and covers categories, functors, natural transformations, equivalence, limits and colimits, functor categories, representables, Yoneda’s lemma, adjoints, and monads. Optional topics covered include cartesian closed categories and the lambda calculus. However, 2-categories and monoidal categories are purposely excluded, and toposes are not covered in any depth.

Two aspects that I like about this book are the author’s style of starting out with examples from and references to set theory (although it is true that arrows, not objects, are the focus in category theory, many students come from a set-theoretical background, and references to set theory can ease the transition), and offering occasional examples from computer science. For instance, Example 10 on page 11 provides a case in which a functional programming language L is given and an associated category is shown where the objects are the data types of L, the arrows are the computable functions of L (“processes,” “procedures,” and “programs”), the composition of two programs, f mapping X to Y, and g mapping Y to Z, “is given by applying g to the output of f,” and the identity is the “do nothing” program. Such examples help tie the subject to computer science (in particular, to functional programming), and help render the subject more appealing to students of functional programming.

Category Theory Lecture Notes:

Category Theory Lecture Notes for ESSLLI
by Michael Barr and Charles Wells
Michael Barr and Charles Wells, 1999
Condensed version of Category Theory for Computing Science, discussing category theory from a computer science perspective

A Gentle Introduction to Category Theory – the calculational approach
by Maarten M. Fokkinga
Amsterdam: M. M. Fokkinga, 1992 (version of June 6, 1994)
Another set of lecture notes referenced on the HaskellWiki page on category theory

Categorical Programming with Examples in Haskell:

Categorical Programming with Inductive and Coinductive Types
by Varmo Vene
Tartu, Estonia: Varmo Vene, 2000 (Ph.D. dissertation)
A thesis on categorical programming, exploring inductive and coinductive types, and several programming constructs related to them in Haskell

In conclusion, I stated as follows:

I would believe that having specific Haskell code to help interact
with the categorical examples would help to motivate study of the
abstract theory for many programmers.  One problem that many people
have with studying abstract theory in isolation is that they often
tend to lose motivation unless they can see how the theory directly
relates to and influences the semantics and data structures in the
code.  Having specific examples of Haskell code to tie together
immediately with the abstract theory would most likely help to
motivate and maintain interest.

Then I discovered a similar thread in the USENET newsgroup comp.lang.haskell which had originated two days earlier, entitled “Book recommendations on underlying theory,” dated “Sun, 11 Jan 2009 15:11:40 -0800 (PST),” in which a reader nicknamed “grimey” was asking for recommended readings on the theory behind Haskell.  Grimey described himself as a programmer who had “studied physics at the undergrad level,” and whose mathematical background included “Diff & Integ. Calc, Linear Algebra, Diff Eq, Advanced (Vector) Calc, [and] Complex Analysis.”  In particular, he added,

Although the Vector Calc class was particularly difficult
for me and sort of “took the wind out of my sails” and leaving me
adrift on the sea of mathematics for a long time.  I always wanted to
continue on with more abstract math, like algebra and group theory, to
gain understanding of the beauty behind quantum physics; but for
various reasons, that didn’t happen.  Anyway years later I still use
Linear Algebra and Diff Eq quite frequently for work, and have a good
practical engineer’s grasp of those topics.  I use advanced calculus
less frequently and I use quaternions for very practical, non-
theoretical way for rotation sequences in 3D.  I am an expert C/C++
programmer.

He then mentioned the following books as two that had “piqued [his] interest,” before asking for further suggestions:

Topics In Algebra
by I.N. Herstein
Xerox Corporation: 1975

Lambda-Calculus and Combinators
by J. Roger Hindley and Jonathan P. Seldin
Cambridge: Cambridge University Press, 2008

In my response linking the two threads, I mentioned Andrzej Jaworski’s response to my earlier posting in the first thread, in which he had replied in part that:

[T]here are many very good
articles addressing specific issues of Haskell's theoretical foundations (e.g.
http://www.cs.ut.ee/~varmo/papers/thesis.pdf).  They however always assume more than they target to
explain making student turn around them like a dog not knowing which ball to catch first.

I.e., the problem was that many such papers depended on parts of other papers, which either depended on other parts of the first paper, or on parts of still other papers.  Then I mentioned a response to this issue that I had received in a private e-mail message from a reader of the first thread, in which that reader had written that:

… the problem “comes from trying to use academic papers as textbooks, a
purpose for which they’re not usually designed.”

I then added that this was the gist of the problem, and, as a possible solution, added a dead-tree-based book that I had read about earlier (already mentioned above):

Conceptual Mathematics: A First Introduction to Categories (Paperback)
by F. William Lawvere and Stephen Hoel Schanuel
Cambridge: Cambridge University Press, 1997
An elementary introduction

I added:

This book is reputed to be interesting even to non-mathematicians at a
philosophical level.  I myself have purchased a copy.

Then, on an afterthought, in an additional post immediately afterwards, I added that what would be even better would be a mathematical storybook (separate links to the storybooks hyperlinked in the following quoted portion):

What would be especially interesting would be an introductory storybook on category theory:  a book similar to, say, Flatland, by Edwin Abbott Abbott, or even Flatterland, by Ian Stewart.  These books would elevate category theory out of the realm of dry equations into a story which would keep me awake with suspense reading through the night.

Yes!  What we need is Category Land:  Like Flatterland, Only About Categories.  If only a book were so.  Any suggestions?

Refal: Recursive Functions Algorithmic Language

Last month, while reading a post by Cyril Slobin, dated “Fri, 12 Dec 2008 09:20:35 +0300,” in the thread “Beginnings – History of Declarative Languages” on the Qilang mailing list on the Qi programming language, I came across a reference to an unusual functional programming language called “Refal.”  “Refal” is short for “Recursive functions algorithmic language,” and is a language designed by Valentin Turchin for symbol manipulation.

Refal is based on pattern matching, and unlike Prolog, pattern matching in Refal works forwards, not backwards.

To illustrate a Refal program in action, let us consider the problem of determining whether a given string is a palindrome.  Here is a formal definition of a palindrome (quoted from “Section 1.1: A Simple Function Definition” of the online manual “REFAL-5: programming guide & reference manual“):

1. An empty string is a palindrome.
2. A string of one symbol is a palindrome.
3. If a string starts and ends with the same symbol, then it is a palindrome if and only if the string which remains after the removal of the first and the last letters is a palindrome.
4. If none of the above are applicable, the string is not a palindrome.

Based on the above definition, here is an example of a typical Refal program for determining whether a given string is a palindrome:

Pal { = True;
     s.1 = True;
     s.1 e.2 s.1 = <Pal e.2>;
     e.1 = False;  }

Here, “Pal” is the function name, followed by a definition.  In the definition, the first line matches a blank string with “True.”  Thus, an empty string is a palindrome.

In the next line, “s.1″ is a free variable of type symbol, which matches any single symbol, but only a single symbol, with “True.”  (The ‘1′ here is a subscript.)  I.e., such symbols as ‘a,’ ‘1,’ ‘%,’ etc. match with “True,” and hence are palindromes as well.

In the following line, “e.2″ is a free variable of type expression, where an expression is the most general data type in Refal, possibly being a string of symbols.  This line matches any single symbol, followed by any expression, followed by the same single symbol.  Angular brackets denote a function call, so “<Pal e.2>” denotes a recursive call of Pal on “e.2.”  Here, “e.2″ is just the inner expression, sans the outer pair of identical symbols.  Thus, “aba” will match and then recursively call Pal on the inner ‘b,’ “abca” will call on the inner “bc,” “ab1a” will call on the inner “b1,” and so forth.

In the last line, any other expression which does not match the other two lines above it is not a palindrome.  E.g., “ab” is not, nor is “a%,” nor is “a1,” nor are any other similar expressions that do not match the above two lines.

In practice, Pal is called with a line such as the following at the top of a .ref Refal source file:

$ENTRY Go { = <Prout <Pal ‘tattarrattat‘>> }

Here, “tattarrattat” can be replaced by any other palindrome.  (I haven’t yet proceeded far enough to explain this line in the manual, so I shall leave explanation of this line for a possible alternative time.)

The above-referenced Refal manual also includes a reference to an online Refal compiler for viewing, editing, compiling, and executing Refal snippets in a Web browser.  This compiler even saves source code in a temporary file between Web sessions!

There is also Refal-SciTE, a compact combined GUI-based editor, REPL, and compiler, based on Refal-5 and the SciTE editor.

What I find especially notable about Refal is its emphasis on symbol manipulation, instead of numeric computation.  Many other functional languages tend to focus more on numeric computation; however, one of my original interests in programming back in the 1980’s, when I was still reading such ancient computer magazines as Byte, was in simulating human verbal communication.  I fondly remember one article back at the time (unfortunately, I do not remember in which magazine the article had been published) about somebody who had written a simple program (I think that it had actually been in a dialect of BASIC) to create sentences using grammatical units stored in a dictionary which was part of the program.

This person reportedly spent just one afternoon writing the program, and then sat back for several hours as he watched, fascinated, as the program output sentence after sentence of original prose, in which some sentences were quite unusual and unlike anything that a human being would naturally come up with.  For example (I am coming up with these examples on my own, based upon what I remember of the kinds of examples given in the article), some possible sentences created by the program could be the following:

Fish swim in cheese under umbrellas.

Nelson coughed dynamite eating raw fish.

Jack sweated programs sleeping monkeys.

These are all grammatically correct English sentences, but unlike anything that most English speakers would come up with on their own, because the ideas behind them tend to be considered absurd or preposterous by most human English speakers.  However, a computer program that simply pulled grammatical units out of a dictionary and matched them at random in following grammatical rules could easily come up with such examples.  It is precisely the absurdity of such examples that caused their type to stick in my mind and to stay there for more than twenty years.

Other examples of functional programming languages focusing on symbol processing often cited are LISP and Scheme, but while Scheme remains one of my favorite functional programming languages, it lacks pattern matching.  Prolog has pattern matching, but employs backtracking instead of forward reasoning; in addition, Prolog programs tend to be very verbose compared to equivalent programs in such functional programming languages as Haskell.

Furthermore, recently my interests have been veering towards such statically typed programming languages as Haskell, Typed Scheme, and Qi, which have the advantage of increasing the probability that a program which successfully compiles does not need to be debugged (while decreasing the probability that a program hastily written will compile in the first place).

Moreover, I tend to enjoy the mental gymnastics of writing in a purely functional programming language, which does not allow side effects, such as Haskell; it is rather like trying to navigate through town while being limited to jumping over the tops of buildings and flying down their staircases like Spider-Man.  To stretch the analogy, the higher-order functions are the buildings, the spider webs are the maps, and the staircases are the recursive calls, which typically bottom out at the zeroth floor level.  There are fewer steps required, because each step jumps over an entire building, or maps over an entire series of buildings, but if you actually want to get in or out of a building, you need to do something special in binding yourself in returning through the door.

Yet while the purely functional style of Haskell often leads to interesting mental exercises in concocting elegant programs that do not rely on side effects, most Haskell examples tend to be focus on some form of numeric computation, rather than symbol manipulation; in addition, most discussion on Haskell seems to touch on some form of mathematics, often category theory; there is relatively little discussion focusing on symbol manipulation.  Refal, on the other hand, specializes in symbol manipulation, uses forward reasoning, and is concise.  I have barely started reading about Refal, but it seems a possibly interesting alternative for writing programs to deal with words and phrases.

A Cross-language Comparison of Monads in Haskell, O’Caml, and Qi

A few days ago, there was an interesting post by Rafael Gustavo da Cunha Pereira Pinto, dated “Mon, 5 Jan 2009 09:08:37 -0200,” on the Haskell-beginners mailing list on the Haskell programming language, referencing a monad tutorial for the O’Caml programming language that provided an alternative perspective in helping to illustrate monads in Haskell, mentioned in the thread “Yet Another Monad Tutorial.” In my response, I introduced an alternative monad tutorial for the Qi programming language, which also referenced Haskell.

Since the O’Caml monad tutorial mentioned design patterns as an alternative to category theory in forming a basis for describing monads, this reminded me of the book How to Design Programs, by Felleisen, Findler, Flatt, and Krishnamurthi, on Scheme, which led to a mention of Typed Scheme, which in turn led to a mention of Qi.  In turn, this led to a cross-language comparison of monad definitions in Haskell, O’Caml, and Qi, and their implications.

Hereinafter I have quoted parts of my response for reference (with minor edits to hyperlink various keywords, as opposed to leaving the link URL’s separate from their references):

The focus on design patterns brings to
mind the book How to Design Programs, by
Felleisen, Findler, Flatt, and Krishnamurthi, on Scheme, and the
recent dialect of Typed Scheme, as well as the
language Qi.

There is a somewhat similar tutorial on monads using Qi (see
“Programming Kung Fu Qi: Monads in Qi”).

For reference, I shall use the Haskell-based monad tutorial “All About
Monads” as a base for one of the Haskell versions of the examples.  Most of my
descriptions of the Haskell version will be borrowed from the
descriptions contained in the section there entitled “Meet the Monads”.

Let’s compare the Haskell version with the O’Caml version and a
hypothetical pure Scheme version:

Haskell version of monad rules (borrowed from the Qi-based tutorial):
>class Monad m where
>   return :: a -> m a
>   (>>=)  :: m a -> (a -> m b) -> m b

O’Caml version of monad rules (borrowed from the O’Caml-based
tutorial):
>module type MonadRequirements = sig
>    type ‘a t
>    val bind : ‘a t -> (’a -> ‘b t) -> ‘b t
>    val return : ‘a -> ‘a t
>end;;

Hypothetical pure Scheme version of monad rules (borrowed from the
Qi-based tutorial):
>   (pipe (lift x) f)   = (f x)
>   (pipe m lift)       = m
>   (pipe (pipe m f) g) = (pipe m (lambda (x) (pipe (f x) g))

The Haskell version is the most concise.  The “return” and “(>>=)”
(“bind”) operations in Haskell correspond to the “return” and “bind”
operations in the O’Caml version, and to the “lift” and “pipe”
operations in the hypothetical pure Scheme version.

In the Haskell version, “m” is the type constructor, “return” is an
operation that creates a value of the monad type “m a,” while “(>>=)”
(a.k.a. “bind”) is an operation that combines a value of that type “m
a” with a computation that produces values of that type to produce a
new computation for values of that type “(a -> m b) -> m b.”

Superficially, so far, the three versions seem fairly equivalent.

Now for examples of list monads:

Haskell version (adapted from combining the Haskell-based and the
Qi-based tutorials):
>instance Monad [ ] where
>   l >>= f = concatMap f l
>   []     >>= f = []
>   return x     = [x]

O’Caml version (borrowed from the O’Caml-based tutorial):
>module ListMonad = struct
>    type ‘a t = ‘a list;;
>
>    let bind lst f = List.concat (List.map f lst);;
>
>    let return x = [ x ];;
>end;;

Qi version (borrowed from the Qi-based tutorial):
>(define bind
>   [] _ -> []
>   [X | Xs] F -> (append (F X) (bind Xs F)))
>
>(define return
>   X -> [X]  )

Here we start to see some differences.

In the Haskell version, “return” simply creates a singleton list
(“[x]“), while “(>>=)” (i.e., “bind”) either returns a blank list “[]“
in the case of a blank list, or otherwise creates a new list
containing the results of applying the function to all of the values
in the original list “concatMap f l.”

In the O’Caml version, notice the “List.concat” operation.  After the
List.map operation, we are left with not a “‘a list”, but instead
with a “‘a list list”, so this is necessary to obtain the correct
type “‘a list.”  Otherwise, the reasoning is similar.

In the Qi version, we have split the monad into two functions:  “bind”
and “return.”  Splitting a large function into a smaller functions is
typical Scheme style.  Here, “return” simply pattern-matches an
element into a list containing that element, while “bind” either
pattern-matches an empty list “[]” followed by anything “_” to an
empty list “[],” or pattern-matches a list consisting of a car and a
cdr “[X | Xs],” followed by a function “F,” to “F” applied to “X,”
which is “(F X),” appended to a binding of the cdr of the list “Xs” to
the function “F.”

It seems that studying the Qi version may shed some insight into the
Haskell version by approaching it from a different perspective.  This
may also be true of the O’Caml version, but personally, I think that
the splitting of the monad into separate functions for “bind” and
“return” in the Qi version helps to differentiate it from the other
two versions, and hence offers additional insight into the nature of
the monad.

It may also be said that the use of both “List.map” and “List.concat”
in the O’Caml version offers similar insight.

Now for a pet peeve that I have with one of the examples in the O’Caml
monad tutorial:

>module SerialMonad = struct
>    type ‘a t = unit -> ‘a;;
>    let serial_mutex = Mutex.create ();;
>    let return x = (fun () -> x);;
>    let bind m g = (fun () -> (g (m ())) ());;
>    let access m =
>        Mutex.lock serial_mutex;
>        try
>            let r = m () in
>            Mutex.unlock serial_mutex;
>            r
>        with
>        | e ->
>            begin
>                Mutex.unlock serial_mutex;
>                raise e
>            end
>end;;
>
>This monad is basically identical to the previous FunMonad with the addition of the access function- which executes the
>process while holding the serial_mutex lock, which is always unlocked when the process completes (even if the process
>throws an exception). This forces all processes executing within a SerialMonad to be executed sequentially and serially
>(thus the name).

While a clear example, one problem that I have with this approach is
that the emphasis on forcing “all processes executing within a
SerialMonad to be executed sequentially and serially” reminds me of
the Imperative Way.  This brings to mind a posting by Paul Hudak on
Haskell-Cafe, entitled “a regressive view of support for imperative
programming in Haskell,” dated “Wed Aug 8 14:20:39 EDT 2007″,
in which he writes as follows:

>In my opinion one of the key principles in the design of Haskell has
>been the insistence on purity.  It is arguably what led the Haskell
>designers to “discover” the monadic solution to IO, and is more
>generally what inspired many researchers to “discover” purely functional
>solutions to many seemingly imperative problems.  With references and
>mutable data structures and IO and who-knows-what-else to support the
>Imperative Way, this discovery process becomes stunted.
>
>Well, you could argue, monad syntax is what really made Haskell become
>more accepted by the masses, and you may be right (although perhaps
>Simon’s extraordinary performance at OSCOM is more of what we need).  On
>the other hand, if we give imperative programmers the tools to do all
>the things they are used to doing in C++, then we will be depriving them
>of the joys of programming in the Functional Way.  How many times have
>we seen responses to newbie posts along the lines of, “That’s how you’d
>do it in C++, but in Haskell here’s a better way…”.

Although I greatly applaud alternative perspectives in learning
Haskell, I am somewhat suspicious of the emphasis on a
quasi-imperative approach.  One of the factors that initially
attracted me to Haskell in the first place was the emphasis on a
functional style.  In particular, purely functional code has a number
of advantages, including easier reasoning about program behavior,
easier formulation of proofs of correctness, and referential
transparency. Together with referential transparency comes
applicativity of formal methods of program analysis.  All this is lost
once the Functional Way is replaced by the Imperative Way.

Here, the Qi-based monad tutorial seems to focus more on examples that
use the functional approach, but perhaps this is just my opinion.

Comparative programming languages can be a very interesting topic.  If
anybody knows of any alternative monad tutorials in other functional
programming languages that could help to shed light on monads, please
feel free to mention them in this thread.

What’s interesting about this comparative programming languages-perspective is that it seems that studying both Haskell and Qi together may actually lead to learning Haskell more quickly than learning just Haskell alone, because the cross-language perspective helps to motivate and shed light on the trickier parts of Haskell semantics.