Scheme in Python

The Scheme in Python series has been completed! Since there are still a few readers of this blog and I haven’t yet setup domain forwarding, I’ll post the links page here.


The Scheme in Python project is a port of the Scheme in Scheme project. The goal is to implement a small subset of Scheme as an interpreter written in Python.

There are a number of goals for this project. First, implementing Scheme in Scheme allowed us to “cheat” a bit by having access to the Scheme reader and data structures. Using Python as the implementation language will force us to code the reader by hand and create new data structures where there isn’t a one-to-one mapping from Scheme to Python.

There are also two auxiliary goals to this project. Using Python should make this more accessible to programmers who are interested in language development, but are unfamiliar with Scheme. Also I’m using this project as a way to familiarize myself with branching and merging in git, so each post will correspond to a branch in the repository.

All the code for this project will be hosted on GitHub. The code is licensed under a BSD license if you are interested in forking it for any reason.

This series will focus on building a very simple interpreter for the purpose of learning the steps involved in building one. For this reason there will be no/very little error checking or optimization. This port will be slightly more complicated than Scheme in Scheme so if you are interested in an even simpler interpreter look here.

Part 0 | Reading from stdin

Part 1 | Numbers

Part 2 | Extending the read layer

Part 3 | Pairs and linked lists

Part 4 | Self-evaluating values

Part 5 | Assignment and define

Part 6 | scheme-syntax macro

Part 7 | Refactor and load

Part 8 | Primitive procedures and apply

Part 9 | Environments

Part 10 | lambda

* Most implementations of Scheme in Python use regular expressions in the reader. I chose to write a parser by hand so I could explain some of the details of parsing. As this is an educational exercise I think this is appropriate.

Other resources for writing a Scheme in Python

lis.py and lispy.py
Simple Schemes written by Peter Norvig.

Psyche
pyscheme
I haven’t got the chance to look at Psyche or pyscheme, but you may be interested in them as well.

Other resources for writing a Scheme in Scheme or other languages

Structure and Interpretation of Computer Programs
Chapter 4 onward covers designing and implementing a number of interpreters and was the inspiration for this interpreter.

An Incremental Approach to Compiler Construction (PDF)
Great paper on building a Scheme compiler from the ground up. Each step is simple and results in a fully working compiler.

Scheme from Scratch
The blog series that inspired and guided the development of the original Lispy. Even if you don’t know C (I didn’t at the time) you will still be able to follow along and construct your own Scheme. Peter’s coding style is easy and pleasant to read and he mentions tips for going in different directions for your own implementations.

A Self-Hosting Evaluator using HOAS (PDF)
An interesting implementation of Scheme using a Higher-Order Abstract Syntax representation. This paper, An Incremental Approach to Compiler Construction and SICP were the primary motivating forces behind my interest in PL design and implementation. The author, Eli Barzilay, has many other interesting papers at his site.

Chai – Math ∩ Programming
A series detailing the development of Chai (what appears to be a Scheme-like language). It is well written and currently in development. I’ll post more information when it’s available.

Scheme in Scheme
Another series that is just beginning about writing a bytecode interpreter. It appears to be put on hold as of April 2011.

Lisp in Scheme
An implementation of McCarthy’s original Lisp in Scheme.

Offline

Lisp in Small Pieces
Great book. Contains code for 11 interpreters and 2 compilers. Source code from the book available here.

Koding in Kate

I’ve recently been preparing to begin looking for my first programming job. As such I’ve been reading a number of “what employers are looking for” type posts. A while ago I read a comment that one interviewer asks candidates what IDE(ditor) they use and uses that information, along with some other things I consider just as trivial to judge candidates. Remembering that post (I think it was in comments on a reddit submission, but I’m not sure) led me to write this one.

I use Kate and I’m proud of it.

Yes Kate, the KDE Advanced Text Editor. Kate is more than a text editor but not quite an IDE, yet is very versatile. From what I’ve read Kate is not used very much by developers, I personally love it and here’s a few reasons why…

Kate works with just about anything I’ve thrown at it:

I do a decent amount of Scheme development and Kate does a surprisingly good job at both highlighting and indenting Scheme. Parenthesis are colored at all times and are highlighted as a matching set when the cursor is over them. It is one of the few editors that I have used that not only works adequately well with Scheme but also has a modern interface and handles other languages very well.

I also do a lot of Python, and Kate has phenomenal support for that. When I did projects in C, Javascript, HTML and even plain text files, Kate supported them well. Kate might not be the best at any one thing, but since it’s usually close to the top, I don’t have to waste any time learning yet another editor/IDE just because I’m doing a project in a new language. Even though it doesn’t take that long, I’d rather focus on developing (and writing blog posts about my editor).

Sessions

Kate has really good support for sessions. You can choose to have your last session open automatically, or use a Kate launcher that lets you choose sessions. Any files you open will be automatically saved to the current session (unless you’re using the anonymous session feature). I rarely “use” sessions in Kate they just do their thing with little interference from me, except for the occasional “Sessions” -> “Quick Open Session”.

Tabs, Documents and the File Manager

Managing the documents in your current session is both easy and customizable. There is a toolbar on the left hand side that has both an open documents manager and a filesystem browser. Both are easy and intuitive to use, but if that’s not enough there are extensions that offer tabs as well. In fact there are two, an older extension “Tab Bar” and a newer and sleeker looking “Tabify”.

Terminal and External Tools

Most of the languages that I use have some sort of REPL. In almost all these cases using the REPL from the command line is not only easy, but is “the way to do it”. Kate offers an embedded terminal that allows quick testing of code snippets in a REPL*. In addition the terminal can be set to auto-sync with the current document, which comes in handy in a number of situations.

With External Tools, Kate can be set up to compile/execute your files just about any way you see fit. External tools can be used for lots of other scripting tasks too, though I haven’t played with it much and can’t comment further.

Find and Regular Expressions

Kate has a pretty powerful search/replace feature including highlighting of all found terms. It’s not just for the document you have open though, Kate can search through multiple files or the entire hard drive if you want. You can also type your query as a regular expression giving you that much more power to find what you’re looking for.

Code Folding, Bookmarking and Split Views

Common IDE features such as code folding and bookmarking are also present in Kate. You can also split the view pane of the editor, horizontally or vertically, allowing multiple documents to be viewed and edited at once.

Shortcuts and VI mode

Just about every command in Kate can be set as a keyboard shortcut. This makes things like the terminal plugin feel right at home. In addition there is also a VI mode that provides Vi(m) like editing. Though not 100% compatible with VI(m) commands, it is an interesting feature. Unfortunately not one that I have any experience using yet, so you can check here and here for more info.

Word/Code Completion and Auto-Braces

One of the things I really like in Kate is word completion. It’s a bit different from the code completion that is commonly found in IDEs. The word completion in Kate is based off other words that are present in the file. This means that you won’t be able to do someObject.met and see all the attributes/methods of that object that start with “met”. However you can use auto-completion when you’re writing anything from C to Scheme to HTML to README files.

Code Tools

Kate also comes with a number of tools for working with code. A comment/uncomment command that works with just about any language and style of comment. Indent/Dedent, support for Unix, Windows and Mac newlines and tons of character encodings, word wrap and spell checking are available and that just barely scratches the surface.

Plugins, Extensions and Scripting

Over 20 plugins and extensions are available (some for KatePart and some for Kate) that add more functionality. Plus you can write KatePart scripts in JavaScript that can add tons of features or just implement a quick hack to get things done.

 

There are many good things that coding in Kate brings.
These are but a few of my favorite things!

 

Links

The Kate Editor Homepage

Using Kate As a Web Editor

Pipes in Python – Infix Syntax for Function Calls

Usually posting nothing more than a simple link is not my style, but this is just really cool.

Pipe: Infix syntax for Python

Here’s some more links…

Python Package Index Page
Github Page

For now this is simply a reminder to myself to play around with this code a bit. At some point in the future I may write up a short post on this.

Here’s a short excerpt from Julien Palard’s post:

Compare the readability of the classical prefix syntax :

sum(select(where(take_while(fib(), lambda x: x < 1000000) lambda x: x % 2), lambda x: x * x))

And the infix syntax :

fib() | take_while(lambda x: x < 1000000)
      | where(lambda x: x % 2)
      | select(lambda x: x * x)
      | sum()

Isn’t the infix syntax more readable?