I've written a Lisp HTML parser before, but I was never quite satisfied with it; so I decided to start again from scratch.
Well, I was working on a recursive function that walks through an HTML string and turns it into valid Lisp, so this:
<html>
<head>
<title>Some Title</title>
</head>
<body>
<h1>Some header</h1>
<p>Some paragraph containing <a href='#'>some link</a></p>
</body>
</html>
Should get converted to:
(html
(head (title "Some Title"))
(body (p "Some paragraph containing" (a "some link"))))
Not exactly rocket science, but it has the advantage of generating valid Lisp as an output format. That way, I ought to be able to define functions "html", "head", "title", etc. that know how to render their arguments, and I have used HTML to generate a Lisp program that generates a PDF. Slightly circuitous, but a good pet project to learn some Lisp nuances while I get a tedious task done.
Notice too my example dropped the attributes for the <a> tag. That's because I haven't decided how to handle tag attributes yet.
Well, I was working on that piece of code (so far just under 100 lines and generates the Lisp: I need to write the compiler next) when I had a sudden flash of insight.
Functional programming is essentially applying a series of transformations to data.
OK, that is oversimplifying a little, but consider this example. Suppose we want to write a function in Lisp that doubles each element of a list. With no error handling, type-checking, etc. one might write something like this:
(defun double-list (some-list &optional accumulator)
"Double every element in a list."
(if (null some-list)
(nreverse accumulator)
(double-list (rest some-list)
(push (* 2 (first some-list))
accumulator))))
OK, OK, it would be easier to just do something like this:
(defun double-list (some-list)
"Double every element in a list."
(mapcar #'(lambda (x) (* 2 x)) some-list))
But that wouldn't make my point so clearly!
But in the end, I finally saw something I hadn't seen before: the work is done entirely in the call to the next function. That is, successive calls to the function only transform the data, then call the function again. So essentially the only work done in the function is to decide what arguments to use when it calls them again.
OK, that's rather simplistic. I mean, that's not really worthy of writing a book or anything, but it helped me understand a little better why functional gurus keep going on about applying successive transformations.
I guess it all comes back to what I said to a buddy a year or so ago: "Recursion is just iteration that keeps its state on the call stack."
5 comments:
That's what I have been trying to tell you for years.
Could you re"iterate" that, please?
Funny you should say that to your buddy 'cause it's one of my pet sayings. In fact I have a fridge magnet with that on it.
True! I read it recently in a Max Lucado book.
Chuck, do you seriously want me to re-iterate that?
Post a Comment