Prefix, Postfix, Newfix, Bluefix

My, my, look at all those notations. You can infix: 2 + 2. You can prefix: + 2 2. You can postfix: 2 2 +. All three notations are perfectly arbitrary for the purposes of mathematics. (2 + 2) * 3 = 12, so what’s really different about these codes?

Code 1

x = 2 + 2
y = x * 3
print(y)

Code 2

x := 2 plus: 2
y := x times: 3
y print

Code 3

2 2 + 3 * print

Code 4

(let* (
   (x (+ 2 2))
   (y (* x 3)))
      (print y))

Code 1 is typical of procedural programming (Python¹, C, Basic, Pascal). You declare variables, store data in variables, and display variables.

Code 2 is typical of object oriented programming (Java, C++, Ruby², Smalltalk²). You instantiate objects, send messages to objects, and display objects.

Code 3 is typical of stack programming (Factor, Joy, Forth). You push values onto the stack, push functions onto the stack, and display the stack.

Code 4 is typical of functional programming (Haskell, ML, Erlang, Lisp). You pass expressions, evaluate expressions, and display expressions.

But what’s really different?

Codes 1 and 2 are fundamentally the same: they’re stateful computations. Code 1 stores state in variables, Code 2 stores state in objects, but it’s all the same. Code 2 is syntactical sugar for Code 1. And Code 1 is syntactical sugar for:

Code 0

add x,2,2
mul y,x,3
put y

In other words, you’re still explicitly performing register transactions. Do this calculation then STORE THE RESULT IN HERE. Do that calculation then MOVE THE BYTES TO THERE.

By contrast, Codes 3 and 4 are an island all their own: they’re functional computations. Instead of manipulating machine registers, they manipulate mathematical expressions³. Code becomes data becomes code again; you can pass functions as arguments to other functions as if they were pure mathematical constructs. Code 4 named the expressions “x” and “y”, while Code 3 didn’t, but as Code 3 shows, naming isn’t really necessary, it’s just a convenience.

So what’s really different? Functional programming provides a whole new level of abstraction, one that allows you to write more complex code than you could in low-level languages like Java. Really. Do you like moving bytes around, or would you prefer to leave that as an exercise for the compiler?

¹ Python has functional elements, but they’re underused. Most Python programmers aren’t even aware that Python has list comprehensions and anonymous functions.

² Ditto for Ruby and Smalltalk. They have blocks, and therefore can do functional programming, but it’s not emphasized. With all the OOP hullabaloo, the incentive is to write stateful methods instead of pure methods, especially in Ruby where the line between f and f! blurs because the result of the last evaluated expression is always returned.

³ Most functional languages have stateful capabilities, but they’re strictly only necessary for specialized calculations such as pseudo-random number generation, concurrent programming, and I/O. Also, functional language compilers must be stateful in order to compile functional programs that provide the abstraction of pure, stateless code. (see Haskell).

Haskell Type Transparency

Coding is often a matter of looking up API calls, chaining them together, and outputting the result. In a dynamically typed language like JavaScript, it can be difficult to determine exactly what kind of thing a function returns. For example, a JSON parsing library might have the function:

function parse(data) {
   ...
}

According to the docs, parse() takes JSON text and turns it into a JSON object. But will parse() return a tree literal? A manipulable JSON object? A callback that returns a JSON object? Does parse() return anything at all? Does parse() modify data in place to become a JSON object? What is the type of data anyway? A string? A URL to a location containing a string?

In statically typed languages, types are more transparent:

parse :: String -> Tree String
parse = ...

This Haskell code defines parse as a function which accepts a string and returns a tree of strings. No more slogging through Google results just to see how to use API calls. Haskell’s type strictness is a blessing in disguise; although it may seem inconvenient to specify types up front, in the long run, the code is more readable and more robust.

There’s the JavaScript bayou of playtesting combinations of o.foo(), o.bar(), o.foo(o.bar()) in the interpreter until o responds to one of them.

There’s the scurvy C, where data is could be a long, or a pointer, or a pointer to a pointer, or NULL. The type system is more what you’d call “guidelines” than actual rules.

Then there’s the calm, steady stream of lucidly typed Haskell.

top: The poor man’s performance analyzer

For the sake of the future of all mankind, I wrote a tiny web server for proving that Hunchentoot works with certain system specs. “doeshunchentootwork” is only 77 lines long, serves a singe page and its favicon, and the application is compiled, not interpreted. So why does top show it using so many CPU cycles?

Daemonization may have been a bad idea, at least this early in development. The process spends a lot of time… doing what exactly?

Since the app is only 77 lines long, debugging wasn’t that hard. Long story short, CL loads the program and quits, so I was using (loop) to keep the program running. I know, I know, terrible. (read) is a better choice, since it doesn’t waste CPU by looping but merely blocks for command line input that will never arrive to a daemonized web server.

With the new code, top shows almost no activity for doeshunchentootwork unless someone is currently requesting the webpage. Whew! Now the resources can be wasted on other servers.

Reading programming books on the Nook

Programming books are hard enough to read: cryptic jargon, poor phrasing, blatant omission of critical details… the list goes on. But it’s even harder to read technical books on the Nook (or any ereader for that matter), because of some limitations of HTML (ePubs are zipped XHTML files).

HTML was not designed for consideration of really small screens. Coders typically use an 80-character margin for easy viewing on medium and large screens. So when a code snippet is shown on the Web, it also assumes a medium or large screen. Textbooks are also pretty big surfaces for code. That’s why Real World Haskell and Practical Common Lisp don’t chop up their code blocks very much. Both the print versions and the electronic versions rely on a big surface for viewing–about 80 characters or more.

Not surprisingly, when this code is viewed on a Nook, the code is cut off. Here’s an example:

PRE-Normal.epub

#!/usr/bin/env runhaskell

module Magic where

import Text.Printf

magic :: String
magic = unlines $ map magic
        where
                magicN :: Int -> S
                magicN n
                        | n > 0 && n

main :: IO ()
main = putStr magic

This is not valid Haskell code. It’s not even readable Haskell code. What’s the rest of the n > 0 && n condition? What happens after that condition is met?

The solution is to instruct Nook (and any other HTML viewer) to wrap the code and set it to a reasonable size (10pt or less). Add the following to the ePub’s CSS:

pre {
	font-family: Andale Mono, "Courier New", Courier, monospace;
	font-size: 80%;

	overflow-x: auto;
	white-space: -moz-pre-wrap !important;
	white-space: -pre-wrap;
	white-space: -o-pre-wrap;
	white-space: pre-wrap;
	word-wrap: break-word;
}

Now the code is readable. Choppy, at least you can see all of it.

#!/usr/bin/env runhaskell

module Magic where

import Text.Printf

magic :: String
magic = unlines $ map magicN [1..7]
        where
                magicN :: Int -> String
                magicN n
                        | n > 0 && n <
8 && n /= 4 = "09 f9 11 02 9d
74 e3 5b d8 41 56 c5 63 56 88 " ++ printf
"%02x" (0xbc + n)
                        | otherwise                = "
                 [ redacted ]                  "

main :: IO ()
main = putStr magic

Update: I received a Kindle for Christmas (will blog Kindle vs Nook soon). It turns out the Kindle automatically wraps PRE tags, and the above CSS ruins that wrap. To reiterate, Nook books require explicit PRE wrapping, but that same explicit wrapping destroys Kindle’s excellent autowrap.

Practical Common Lisp Rolling Review

As I follow the exercises in Practical Common Lisp (PCL) by Peter Seibel, I’ll post the experiences here. Let’s get started.

The Book Itself

is available in dead-tree format and as a series of HTML files. My new Nook is hungry for ePubs, so I downloaded each PCL chapter, dragged and dropped into Sigil, and tweaked the resulting ePub. Sigil has a horrible bug which shoves code blocks way down pages, so my copy of PCL isn’t looking too great. But I plan to write a CL program to restore its former glory.

Chapter 1

is an introduction designed to welcome programmers to Lisp. A short summary would be: DON’T PANIC. The intro is humorous and intriguing.

Chapter 2

Shit just got real. Now PCL ushers the reader to install Lisp in a box (really Lispbox). Back in 2005, Lispbox was surely a godsend for the budding Common Lisper, but in 2010 it’s not only aged, it’s broken. I’ve already blogged about the pain and agony of setting up a CL system, and I won’t repeat myself. Suffice to say MacPorts is only half a saving grace for Mac users. I’m currently using Aquamacs and Aquamacs SLIME with MacPorts CLISP and Quicklisp besides. My .emacs is pastebinned.

PCL covers the basics of Emacs shortcut keys then jumps to the Lisp interpreter. SLIME is quite helpful in this endeavor, compiling, running, debugging my code for me. I like the PCL’s Hello World is not a program but an expression entered into the REPL. Since half the work will be done there, it’s a good idea to get acquainted with ol’ Reppy.

PCL dives into writing defun’s; introduces the debugger; details the proper loading of source files and optional compilation of same, and ends with a NASA anecdote. A geek such as I couldn’t hope for much more than this chapter.

Chapter 3

The first practical chapter. PCL invites the reader to construct a simple music database, introducing Lisp syntacs and semantics along the way. I completed save-db, load-db, … up to update and delete-rows. I’m happy to report that Seibel’s code is clear and concise. PCL suggests using a combination of select and where to simulate a SQL query, with the effect that I almost believe I’m using a real database.

The section, “Removing Duplication and Winning Big” is not easy to skim over, so I’m stuck there for now. It covers Lisp macros, a topic I’ve only heard in reverent whispers.

I’ll let you in on a secret: I’m concurrently reading Real World Haskell. There are notable differences between Haskell and Common Lisp.

Haskell vs Common Lisp

Haskell has one official version (GHC) available on multiple platforms, free, and open source. Common Lisp has no official version. There are Windows-only versions, commercial versions, Linux-only versions with broken makefiles, and CL install kits that once served a purpose but now only serve to mock the senseless diversity of CL implementations.

Installing a complete Haskell environment is simple and painless. Installing Common Lisp took me on a journey.

GHC incorporates new features in each version. Common Lisp’s lack of an official version means that each flavor includes and omits important features. E.g., some come with multithreading, some don’t. ANSI can’t be as responsive as the Haskell community, so the Common Lisp standard will likely not benefit from new features anytime soon.

Haskell stores functions and variables in the same space. Common Lisp does not; it requires ' and #' to pass functions around.

Haskell syntax is light and uniform. By PCL Ch. 3, Common Lisp syntax is starting to slow me down.

Haskell has monads. Common Lisp has macros. More on that when I learn precisely what they are and how to use them.

Haskell’s error messages are somewhat esoteric. Common Lisp’s are more readable.

GHCi’s REPL has enough features to satisfy most programmers. Common Lisp REPLs often fail to include expression history, backspace functionality, and other obvious REPL features. CL REPLs are so crippled that Emacs/SLIME is a necessity.

Both Haskell and Common Lisp syntax are unique, requiring special effort to understand. I believe this is because BASIC syntax is more natural. STEP 1 STEP 2 STEP 3 is intuitive for humans. On the other hand, linear procedures aren’t very powerful. Functional languages have power because they break out of the STEP 1 STEP 2 STEP 3 routine: Spaghetti code is the result of a procedural programmer attempting to do more complex work.

Back to PCL

I’m not sure exactly when I need to #' functions in Common Lisp. While following the PCL exercises, I’ve left out #' for lambdas, and my code gives the same results as Seibel’s. It stands to reason that lambdas don’t need to be #'ed since they self-evaluate. Allegro and CLISP don’t need #' for lambdas, but I’m not sure about other CLs. In any case, I’d like to see a note about this in PCL. Also, I wonder why multiple quote syntaxes exist: ', `, and quote.

Common Lisp Syntax

Look at the code for generating a database query. There are SIX different symbols, each with their own purpose and usage.

(defmacro where (&rest clauses)
  `#'(lambda (cd)
    (and ,@(make-comparison-expr-list clauses))))

The ampersand in &rest is CL’s way of handling function arguments. &key would interpret the arguments as a property list, while &rest stores all the arguments in clauses.

The #' references the lambda without evaluating it. That is, pound (#) references an unevaluated (') lambda object.

The comma (,) and at (@) work together to force evaluation inside the unevaluated (`#') lambda expression. The lambda would have been prefaced with '#', but ,@ only works inside the backtick quote (`).

No poofters.