w7cook/aopl

A book on programming languages, using Haskell

Anatomy of Programming Languages

William R. Cook

Copyright © 2013

What?

This document is a series of notes about programming languages, originally written for students of the undergraduate programming languages course at the University of Texas at Austin.

Install

Install "cabal" Install lhs2TeX by using "cabal install lhs2tex" Install Pandoc by using "cabal install pandoc" Install pandoc-citeproc by using "cabal install pandoc-citeproc" Use "make" to build. Here are some things you can build: pretty - builds anatomy.pdf and opens it verb - builds anatomyVerbatim.pdf and opens it anatomy.pdf - builds the pretty version anatomyVerbatim.pdf - builds the text-based version anatomy.htm - builds the HTML version (with source code) and comments clean - clean the builds update - upload a new copy of the book to the public server (requires server access) execute - run all the code and build the tests fixup - modify the core anatomy.lhs file to have updated paragraph marks and code

Why?

I’m writing these notes because I want to teach the theory of programming languages with a practical focus, but I don’t want to use Scheme (or ML) as the host language. Thus many excellent books do not fit my needs, including Programming Languages: Application and Interpretation (Krishnamurthi 2012), Essentials of Programming Languages (Friedman and Wand 2008) or Concepts in Programming Languages (Mitchell and Apt 2001).

This book uses Haskell, a pure functional language. Phil Wadler (Wadler 1987) gives some good reasons why to prefer Haskell over Scheme in his review of Structure and Interpretation of Computer Programs (Abelson and Sussman 1996). I agree with most but not all of his points. For example, I do not care much for the fact that Haskell is lazy. None of the examples in this book rely upon this feature.

I believe Haskell is particularly well suited to writing interpreters. But one must be careful to read Haskell code as one would read poetry, not the way one would read a romance novel. Ponder each line and extract its deep meaning. Don’t skim unless you are pretty sure what you are doing. comment

The title of this book is derived from one of my favorite books, The Anatomy of Lisp (Allen 1978).

Who?

These notes assume knowledge of programming, and in particular assume basic knowledge of programming in Haskell. When I teach the course I give a few hours of lectures to introduce Haskell. I teach the built-in data types including lists, the basic syntax for conditionals, function definitions, function calls, list comprehensions, and how to print out strings. I also spend a day on data definitions (algebraic data types) and pattern matching. Finally, I give a quick introduction to type classes so student will understand how Eq and Show work. During the course I teach more advanced topics, including first-class functions and monads. As background resources, I point students to the many excellent tutorials on Haskell. Search Google for “Haskell Tutorial” to find one. I recommend Learn You a Haskell for Great Good! or the Gentle Introduction To Haskell.

aopl's Issues

Links containing ~ are broken in HTML version

On http://www.cs.utexas.edu/~wcook/anatomy/anatomy.htm#why the links to "Programming Languages: Application and Interpretation" and "Concepts in Programming Languages" are broken.

The reason for that is that the ~ in the respective urls got lost in the transformation from the lhs format to HTML.

The definition of scope is too narrow.

I am not satisfied with the definition of scope in Section 2.3.3. What you give there is more like a definition of lexical/static scope. Using this definition, there is no space for the debate between static scoping and dynamic scoping. But this debate is a very important issue concerning language design. In particular, it is necessary to show how dynamic scoping does something wrong to emphasize how static scoping does it right.

In my opinion, scope should be treated as a term describing run-time aspects of variables because it concerns bindings of variables when a program is running. Lexical/static scoping seems lexical/static because it is so defined to align to the lexical or static structure of the program.

A deriving of Show is missing for arithmetic `Exp`.

In Section 2.1.1 "Abstract Syntax in Haskell", a deriving (Show) for the data type Exp is missing in order to make sense of the main that tests evaluate in Section 2.1.2 since there print is called. The whole source file works, because in Section 2.1.3, you give an instance definition of Show for Exp. However then in Section 2.1.2, you cannot get:

The output is

Evaluating the following expression:
  Subtract (Number 3) (Subtract (Number (-2)) (Number (-7)))

Of course, adding a deriving (Show) in Section 2.1.1 will make the instance definition in Section 2.1.3 cease to work. But you see the trouble. I am sure there is a work-around, e.g., use two data types, Exp1 and Exp2 to serve the two purposes.

lhs2tex misinterprets symbols in code blocks.

The root issue is lhs2tex is converting a lot of symbols in Haskell code into their math equivalents. For example == is converted into ≡ and . to ∘. I'm not sure what a good solution is though...

Unintentional lambda symbol.

While the source shows > f'3 = \x -> x * 2, the generated PDF actually shows:

The reason is lhs2tex converts \ to \hslambda which is then rendered by Pandoc. I think you can use an unset flag to disable lambda.fmt, but it also disables other symbol conversions (e.g. ->, lambda_).

I'm not sure if this is the route you want to take or if it's worth fixing.

can't 'make' the book

After installing with

git clone https://github.com/w7cook/AoPL.git

cabal install pandoc

cabal install pandoc-citeproc

When I do make

I get the following output :

cat anatomy.mkd \
                | sed "s/@@/AtX/g" \
                | sed "s/@/ATSIGN/g" \
                > foo.lhs
cat foo.lhs \
                | pandoc --wrap=none -N --atx-headers  -f markdown+lhs -t latex+lhs --template=template.tex -V documentclass=report  --filter pandoc-citeproc --top-level-division=chapter \
                > foo2.lhs
[WARNING] Deprecated: --atx-headers. Use --markdown-headings=atx instead.
[WARNING] Deprecated: pandoc-citeproc filter. Use --citeproc instead.
pandoc-citeproc: Error in $: Incompatible API versions: encoded with [1,22] but attempted to decode with [1,21].
CallStack (from HasCallStack):
  error, called at ./Text/Pandoc/JSON.hs:112:48 in pndc-typs-1.21-721dbc0a:Text.Pandoc.JSON
Error running filter pandoc-citeproc:
Filter returned error status 1
make: *** [temp.lhs] Error 83

I am on macOSX.

Any pointers to solving this welcome.