Norvig Scheme

Peter Norvig's Paradigms of Artificial Intelligence Programming (PAIP, for short) currently sits at the top of my reading list. Some readers will have heard of it before now; for those who have not, PAIP is a classic text in practical computer science. It no longer represents the cutting edge of artificial intelligence, but it treats many classic programs in the field, and propounds many generally-applicable programming techniques.

My current interest in PAIP lies in the pedagogical Scheme implementation contained therein. I have -- as I referenced previously -- become interested in programming languages in their own right, but until recently, I knew nothing about their design or implementation. I know more now about the design of a programming language (enough, at least, to admire the simplicity and elegance of R5RS Scheme) but still little of their implementation. That deficiency is now being rectified. I am working through the first interpreter that Norvig presents -- a very simple one, implementing only a skeletal Scheme. Macros and the attendant control structures come next.

Once I have mastered these implementations of Scheme (and there is also a byte-code compiler presented in PAIP!), then -- perhaps -- I can continue on to the wealth of detail contained in Lisp in Small Pieces, and after that, to the Scheme literature; my ultimate goal is to author a modern implementation that compiles to LLVM.

Scheme

Lately, I have been learning Scheme, an elegant, minimalistic Lisp. Scheme is one of a few dialects of Lisp; two others that are (fairly) popular are Common Lisp and Clojure. I have used Common Lisp before -- it is a large, powerful language of ancient and storied lineage, yet one that is quite modern, if not as rich in libraries as others. Scheme, in comparison (although it shares some of Common Lisp's ancestry), is quite compact.

Perhaps as a side-effect of its compactness and clarity, there exists a large body of literature pertaining to Scheme and its implementation. It seems to me that this is a good place to start learning about the implementation of dynamic, interactive programming languages, a topic in which I am interested. I am especially curious about compiler design and construction for such languages -- what are the techniques for making a dynamic language go fast?

CAS: The Interface

I wrote in the tome-like overview of CAS that I would begin the technical posts with one about the parser. It makes more sense, however, to write first about how one uses CAS. After all, the interface is what unifies the rest of the program!

Primitive Integration

Integration of polynomials, the basic trig functions, and sums of both is simple. Yesterday, I realized I could adapt the strategy I used in CAS's differentiator to implement integration of such expressions. The result is the first iteration of the CAS integrator, now up on my GitHub account.

An Overview of CAS

In this post, I intend to outline the basic problem of computer algebra, exposit the design of CAS, name its principle components, and briefly discuss possible directions of future development.

Note that most of this is written in very basic terms. A reader who has looked at the CAS source, or one who desires a technical description of each of CAS's components should skim the current posting (paying particular attention to the last two sections) and await the forthcoming series of explanations of CAS's constituent parts.

Introduction

Hello.

I am Collin Lally; welcome to my blog. In this space I intend, primarily, to write about my interests (namely: mathematics, physics, computer science) and my projects within those fields, although I expect that the occasional interesting-but-mundane experience will percolate through to the blog.

What lies ahead?

For the near future (at least the span of a few posts), I am going to write about CAS, a work-in-progress, toy computer algebra system that I released just the other day. Computer algebra is an interesting problem space, and a good one in which to grow one's programming skill set -- there are problems of parsing, data structures, rule-set definition, and more. None of this is cutting-edge, of course, but I find it interesting, nonetheless. In the coming days, look for an overview of the CAS architecture, and a post each on its most significant current parts -- parser, differentiator, and simplifier.