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.

Advertisements

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?

Television Episode Tracker – A strange question with a fun answer

Yesterday I was browsing Yahoo Answers1 and came across an interesting question…

I want to create a program that can keep track of what episode of different shows im on.
I’m watching several and have trouble remembering which in’s im on. I know i could just make a word doc but this seems cooler. Id like each show to have a button that says what episode and when i click it, the number goes up. Also, it has to save that information. Thanks anybody for helping.

The first response was priceless. I’m only going to quote part of it, you can find the rest here.

geez dude, what you’re asking for isnt exactly a DOS kind output…(sic)

I had the same reaction to the question at first. After a minute or so I realized that I could probably use a program like this. I too watch a number of television shows, almost exclusively downloaded from the internet, and I find myself looking through my file system to figure out which episode I need to download next. Surely this is wasteful, and a quick program could save me precious seconds each day (which I would undoubtedly use to browse reddit or LtU).

About 20 minutes later I hacked together some of the ugliest code I’ve seen in a while and posted an answer to the question. Then I made some nachos. About an hour later I decided to spend another 10 minutes and fix a few bugs in my first version. After about 30 minutes of hacking I came up with this code, which is probably the most functionality I’ve ever created from scratch in 30 minutes of coding (though the code itself is crap).

You can also find a more current version of this as a gist at my github account.

#!/usr/bin/env python
##############################################################################
## If you would like to contribute, contact jacktradespublic@gmail.com
##
## tvtracker is free software: you can redistribute it and/or
## modify it under the terms of the GNU Affero General Public
## License version 3 as published by the Free Software Foundation.
##
## This program is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
## GNU Affero General Public License version 3 for more details.
##
## You should have received a copy of the GNU Affero General Public
## License version 3 along with this program. If not, see
## <http://www.gnu.org/licenses/>.
##############################################################################
## Known Bugs:
## - This needs some serious refactoring, even for this simple script
## - The current episode number just keeps growing and doesn't wrap
##   around seasons.
## - There is no way to undo an increment.
##
## Improvements
## - Next episode available: Input the day of the week that the
##   show is usually aired and the program will notify you when the
##   next episode is available. You should also be able to enter a
##   delay (for things like hulu or torrents).
##############################################################################


from Tkinter import *
import pickle


def loadShows():
  global shows
  f = open(filename, 'r')
  shows = pickle.load(f)
  f.close()

def saveShows():
  f = open(filename, 'wb')
  pickle.dump(shows, f)
  f.close()


class Add_Episode:
  def __init__(self, parent):
    self.add_frame = Frame(parent)

    self.name_label = Label(self.add_frame, text="Name: ")
    self.name_entry = Entry(self.add_frame)
    self.episode_label = Label(self.add_frame, text="Current Episode: ")
    self.episode_entry = Entry(self.add_frame)
    self.add_show_button = Button(self.add_frame, text="Add Show", command=self.add_show)

    self.name_label.pack(side=LEFT)
    self.name_entry.pack(side=LEFT)
    self.episode_label.pack(side=LEFT)
    self.episode_entry.pack(side=LEFT)
    self.add_show_button.pack(side=LEFT)
    self.add_frame.pack(side=TOP)

  def add_show(self):
    name = self.name_entry.get()
    episode = int(self.episode_entry.get())
    shows[name] = episode
    Show(root, name, episode)
    saveShows()


class Show:
  def __init__(self, parent, name, episode):
    self.name = name
    self.episode = episode
    
    f = Frame(parent)
    f.pack(side=LEFT)
    self.label = Label(f, text=name)
    self.entry = Label(f, text=episode)
    self.button = Button(f, text="Increment", command=self.increment)
    
    self.label.pack()
    self.entry.pack()
    self.button.pack()
  
  def increment(self):
    self.episode += 1
    self.entry.config(text = self.episode)
    shows[self.name] += 1
    saveShows()


if __name__ == "__main__":

  filename = "tvshows.pk"

  try:
    loadShows()
  except IOError:
    shows = {}

  root = Tk()
  root.title('Tv Shows')

  Add_Episode(root)

  for n, e in shows.items():
    Show(root, n, e)

  root.mainloop()

The reason I’m posting this here is not because the code is elegant (it definately isn’t) or because the app is great (again, not so much). I’m posting this because I think this is a good project for a beginner to bite into. This is a very simple application and adding features, fixing bugs and refactoring my poorly thought out code is a great exercise.

If anyone is interested in helping with this project I would be more than willing to give you help, hints, code reviews, ideas or whatever other assistance you want. You can also take this code and work on it yourself if you want, it’s really up to you. Though I haven’t started using it yet, it is quickly approaching “good enough for my use case” and I probably won’t be doing much more to it.

1 Yahoo Answers is just about the worst service I’ve ever used. The interface is horrible and if you copy/paste the question into a search engine, the vast majority of the time the answer will be the #1 result. However, unlike stackoverflow or the mailing lists, I don’t feel like I have to spend all day watching for a new question, just to have a chance at answering it before someone else.