epsilon

Real World Haskell: Log for Week 1

Yesterday, April 9, 2020, I started ~~reading~~ studying Real World Haskell by Bryan O’Sullivan. It is excellent. Most of all, I like the balanced mix of the theoretical and the practical. I am going to learn a lot. (Some homework on GitHub)

Below is an annotated reading log. I am keeping it in order to keep motivated. Also to collect a few notes and nuggets along the way. (Note: a “week” in the terminology of this blog does not necessarily consist of seven contiguous days. That is because stuff happens.)

Day 1, April 9. Chapters 1 and 2.

Why Care About Types, p. 17

Before we launch into a deeper discussion of Haskell’s type system, let’s talk about why we should care about types at all — what are they even for? At the lowest level, a computer is concerned with bytes, with barely any additional structure. What a type system gives us is abstraction. A type adds meaning to plain bytes: it lets us say “these bytes are text,” “those bytes are an airline reservation,” and so on. Usually, a type system goes beyond this to prevent us from accidentally mixing up types. For example, a type system usually won’t let us treat a hotel reservation as a car rental receipt. The benefit of introducing abstraction is that it lets us forget or ignore low-level details. If I know that a value in my program is a string, I don’t have to know the intimate details of how strings are implemented. I can just assume that my string is going to behave like all the other strings I’ve worked with.

Day 2, April 10. Chapter 3

Algebraic data types allow us to distinguish between otherwise identical pieces of information. Two tuples with elements of the same type are structurally identical, so they have the same type.

Consider first the tuples a and b:

a = ("Porpoise", "Grey")
b = ("Table", "Oak")

We can pass b to a function expecting an pair consisting of an cetacean’s name and a color. The compiler will not complain, since a and b have the same type. But there is another way:

data Cetacean = Cetacean String String
data Furniture = Furniture String String

c = Cetacean "Porpoise" "Grey"
d = Furniture "Table" "Oak"

This second way let’s us bring the type system to bear in writing programs with fewer bugs. With the tuples we just defined, we could conceivably pass a description of a whale to a function expecting a chair, and the type system could not help us. With the algebraic data types, there is no such possibility of confusion. (p. 46)

Day 3, April 11, 2020, Chapter 3

Just realized that both of the following are product types:

data Point3Da = Point3Da (Double, Double, Double)
data Point3Db = Point3Db { x :: Double, y:: Double, z:: Double}

But the record syntax gives accessor functions by default, e.g.

Main> b = Point3Db { x = 1, y = 2, z = 3}
Main> x b
1.0

Working through the exercises. Feels good.

Day 4, April 12, 2020, Chapter 4: Functional Programming

On page 72, an 11-line skeleton of a command-line program for working with files. Nice!

Day 5, April 13, 2020

Having fun working the exercises in Chapter 4, page 84. Problem 4, scrambling text is especially nice. View a piece of text as an irregular list of exploded strings, so that “abc” explodes to ["a", "b", "c"]. The core of the problem is to design a function

transpose :: [[String]] -> [[String]]

such that transpose . transpose is the identity, modulo empty lists. From this one the desired function

transposeString :: String -> String

Here is a sample:

> str = "abc\ndef\ngh"
> transposeString str
"adg\nbeh\ncf"
> transposeString $ transposeString str
"abc\ndef\ngh"

Day 6: April 15, 2020: Still in Chapter 4

Missed a day yesterday due to pressing real-world obligations as well as a time-sink of a mini-disaster: my usual computer is ill and possibly approaching its final weeks of life. No way to repair it as we are confined to our apartment due to the pandemic. Anyway: onward!

In today’s reading: structural recursion, which the O’Donnell introduces in the humble context of writing a function to convert a string representing an integer to an integer. Also a discussion of tail recursion, constant space versus linear space, and tail call optimization. There is also a good treatment of this X’s book on ML, which, in common with Real World Haskell, has a pleasant mix of the theoretical and the practical.

Following a few more such examples, all done with recursion defined via pattern-matching, the author introduces the map, filter, and foldl functions as a way of capturing common patterns of computation.

Notes

- foldl, which is defined recursively by two pattern-matching equations, yields tail-recursive functions. That is good for performance: a smart compiler compiles a foldl into a for loop.
- Ditto for foldr. Functions are expressible via foldr if and only if they are primitive recursive.
- See Ravi Chug’s cs223 course for notes on tail recursion.

See also this code in the Elm compiler (List.foldl is stack-safe and. List.foldr is , according to @Robin, stack-safe-ish: it will consume more and more stack space up to a point, then move to a stack-safe but slower algorithm

Day 7, April 16, 2020. On to Chapter 5, Writing a Library (Working with JSON data)

Still have to do a few of the exercises in Chapter 4, but decided to forge ahead today. Lots of practical advice about designing a library, e.g., this:

Instead of rendering straight to a string, our Prettify module will use an abstract type that we’ll call Doc. By basing our generic rendering library on an abstract type, we can choose an implementation that is flexible and efficient. If we decide to change the underlying code, our users will not be able to tell.

Here is the type signature:

data Doc = Empty
| Char Char
| Text String
| Line
| Concat Doc Doc
| Union Doc Doc
deriving (Show,Eq)

Note that a Doc is really a tree. There is a concatenation operator:

(<>) :: Doc -> Doc -> Doc
Empty <> y = y
x <> Empty = x
x <> y = x `Concat` y

so that Empty is the “zero” element. Actual rendering is done by compact :: Doc -> String. I’ll have to come back to this chapter and reread it when I’m writing a package of my own.

Next “Haskell Week:” on to Type classes!

Compilers and Interpreters

Screen Shot 2020-04-08 at 08.36.59

Lately I’ve been thinking about what to do to better understand compilers and interpreters, having done most everything so far by the seat of my pants. Fun, but not necessarily recommended. Some possibilities:

1. Robert Nystrom’s Crafting Interpreters
2. Stephen Diehl’s Write You a Haskell
3. William Appel’s Modern Compiler Implementation in ML

I looked into the Nystrom’s book, and liked the first chapters, but the code, in Java, puts me off. I also looked into (3), but that would require learning ML. I tried this briefly, and it was pleasant. Most suited to my tastes was Stephen Diehl’s online book (2). There is, for example, this quote:

In mathematics a function is defined as a correspondence that assigns exactly one element of a set to each element in another set. If a function f(x)=a then the function evaluated at x will always have the value a. Central to the notion of all mathematics is the notion of equational reasoning, where if a=f(x) then for an expression g(f(x),f(x)), this is always equivalent to g(a,a). In other words, the values computed by functions can always be substituted freely at all occurrences.

The implementation may perform effects, but central to this definition is the unobservability of such effects. A function is said to be referentially transparent if replacing a function with its computed value output yields the same observable behavior.

The choice of (2) requires more Haskell than I am comfortable with, but my experience with Elm, another statically typed language of pure functions should help. I’m going to take the plunge!

On Pencil and Paper

I’ve had a pencil in my hand ever since I can remember. On the floor, under my grandmother’s table, scribbling away. On the SS United States returning from a year in Bad Kreutznach, Germany, where my father had been stationed during the Korean war. I can date the voyage precisely because one day, March 5, 1953, my mother, reading the ship’s paper at breakfast, announced that Stalin had died. I asked “who is Stalin.” A very bad man, she said. Paper on the ship was in short supply and we quickly ran out. My mother somehow managed to find a thick stack for us. A precious possession, it was rationed a few pages at a time. But this too soon ran out, after which the days became long indeed. The boredom was terrible, and we must have driven Mom crazy.

Much, much later, my own son started his drawing career, following much the same path that I and all other children follow. First random scribbles, carried out with great gusto and whole-arm motion, preferably in color, and not necessarily just on paper. Later circles of a sort appear, and soon one can find eyes, a mouth, ears, and hair — often wild, wild hair standing straight out or straight up. Arms and legs sprout from the circles, and there stand at last are human figures. Animals soon follow. About this time, I started making little picture books for my son, some with text, others pure imagery. All could be colored, and Dylan did that with enthusiasm, not necessarily respecting outlines. Why should one?

Throughout my life I enjoyed making doodles and drawings. They also helped me think. About all sorts of things, but especially about mathematics and physics. There is a very visual element to much of these subjects. A gas is thought of as a container full of hard little balls zipping this way and that, bouncing off the walls and thereby creating what we experience as pressure. If we need more detail, we imagine arrows attached to the balls, short if they are moving slowly and long if they are moving fast. There is a fancy name, vector, for these arrows, and they can be described by a triple of numbers giving their velocities in the east-west, north-south, and up-down directions. Vectors even have their own little algebra. But what is fundamental, despite the power of the mathematics, is the mental picture of the balls zipping to and fro.

Lately my interests have turned to applications of functional programming languages such as Elm to problems of parser and compiler construction. Such languages are made up entirely of pure functions. These are like the functions in mathematics: what is computed depends only on what information is given to the function as an input. Naturally, as a mathematician, this kind of language appeals to me. Again, as with mathematics or physics, visual thinking plays a role. On the right, for example is some scratchwork for a recent project — developing a configurable parser for a family of block-structured markup languages, if you want to know the buzzwords. Such work uses what are called parse trees, which look like what you see in the drawing. I had to figure out how manipulate these trees, detaching subtrees, changing them, and then reattaching them in just the right place. I tried pure thought, with eyes closed, but that didn’t work. Many sketches later, however, I had working code. It may very well be, and probably is, that other people working on the same problem don’t need to draw pictures. For me, it is essential.

forms

I want to end with a comment. Though one can do a great deal with computer tools — word processors, graphics programs, etc — there is a difference both in the thought process and the physical experience when one uses pencil and paper. Thinking, for me at any rate, is much less constrained. (That is also why I prefer unlined paper. The lines are like a prison.) One can write diagonally, vertically, or in a curve, changing letter sizes from small to large and back again. One can doodle, and one can draw diagrams, even miniature works of art. There is also the physical experience of pressing the pencil against the paper, the ritual of sharpening the pencil, and even the smell of the pencil shavings. And one more thing. Consider a page of hand-written text, written in pencil or perhaps ball-point pen. Run your fingertips over it. Though you cannot read the text this way, you feel the letters. It is a thrill. It is a comfort.

Things Change

As any of you know who have experienced fatherhood for long enough, there comes a time when the role of the father, so long a teacher of the child, begins change. Such is my case in many ways. Long ago it was “Papa, why does the moon follow us as we walk along the path?” Today it was “Dylan, could you help me set up this blog? I can’t figure it out.” But technical advice is the smallest part of it. As I write these pages, I find my words forming in a strange stylistic echo of the writing in Dylan’s blog, dilibop.wordpress.com. This all came about because of a lunchtime conversation a few days ago, when Dylan showed me his first posts. “Dad, you should do this too.” Things change.

On Lies

The other day I happened on an episode of the Bulwark podcast in which political writer David Frum cites Hannah Arendt’s words on lies:

This is because lies, by their very nature, have to be changed, and a lying government has constantly to rewrite its own history. On the receiving end you get not only one lie—a lie which you could go on for the rest of your days—but you get a great number of lies, depending on how the political wind blows. And a people that no longer can believe anything cannot make up its mind. It is deprived not only of its capacity to act but also of its capacity to think and to judge. And with such a people you can then do what you please.

The source for Arendt’s words is a 1978 article in The New York Review of Books, based on a 1974 interview by the French writer Roger Errera. I give the date to underline the fact that a nearly 50-year-old description applies almost verbatim to today’s events. Frum’s mention of Arendt comes just after time code 00:04:02 in the podcast.

Links

Lying in Politics (Hanna Arendt in BrainPickings)

Hanna Arendt on Propaganda