Nick Mudge Ignition Software Consulting & Development

Recently I've been reading a great little book called The Little Schemer. The goal of the book is "to teach the reader to think recursively" and it uses Scheme to do it. I found out about it and was inspired by Douglas Crockford who has his webpage The Little JavaScripter.

Interesting how the concepts and methods of recursion are the same in different languages. I guess that's pretty obvious but it is interesting to see. In looking at Scheme I can't but think of Haskell's pattern matching and type system. Haskell makes recursion concise and elegant.

It became much more real to me recently why Haskell is good for parsing and maybe for writing compilers. Because I learned that a compiler is really a parsing problem, and a parsing problem is really a tree problem and a tree is really recursive. You take some text that is high level language and parse it into a tree. And you parse it some more, breaking it down into smaller and smaller pieces, closer to machine instructions. You get it to a point where you can replace the pieces in the tree with machine instructions (or assembly or something) and spit them out into a file in the correct order.

As an anonymous reader commented, writing compilers isn't tied to any specific programming languages, it's the programming logic that matters. It's interesting that such a high-level, abstract language like Haskell might be great for producing the most concrete, lowest-level code, machine code.

Steve Folta wrote on programming.reddit.com:

You take some text that is high level language and parse it into a tree. And you parse it some more, breaking it down into smaller and smaller pieces, closer to machine instructions. You get it to a point where you can replace the pieces in the tree with machine instructions (or assembly or something) and spit them out into a file in the correct order.
It's a wonderful dream. But where it differs from reality is that processors only have a finite number of registers. (In the case of x86, a ridiculously finite number of registers.) So a real code generator has to use some rather less beautifully recursive method of allocating those registers.

Comments

Name: (required)
Email: (required)
Website:
What has four legs, rhymes with bat and says, "Meow?" (One word answer.)
Spam Filter: