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.

Branching, Merging and Other Useful Commands in Git

I recently started a new series called Scheme in Python mainly to teach myself a bit about branching and merging in git. This post is simply a reference for some of the git commands I regularly use, as well as some explanation about branching and merging.

I’ll start with some of the most basic git commands for creating a repo, adding files and commiting changes to those files.

Create a new repo

To create a new repo, first create a new directory and name it whatever you like. Then from the command line cd into that directory and use the following command.

$ git init

This will create a new repo in that directory. If you already had files in that directory, the git init command will not automatically add those files to the repo. To add a file use the add command.

Add files to repo

$ git add filename

Where filename is the name of the file you want to add. However this is not enough to add the file to the repo, it simply stages the file to be added in the next commit. To commit your changes to the repo you need to use the commit command.

Commit changes

$ git commit -a -m "Type your commit message here"

The -m option allows you to write a commit message that describes the changes you made. If this option is not present the default editor will be opened for you to write a commit message, they are mandatory. The -a tells git to commit all the changes from every file. If you only want to commit changes from a specific file, you can specify that file instead of -a.

$ git commit filename -m "Only changes in filename are committed."

Push changes to remote repo

So far all of the changes and commits have been done locally. If you want to upload your changes to a server such as github you would use the push command. However before you can do this you need to tell git where that remote repository is. Your source code hosting site should give you instructions on how to do this. Here’s an example of the command I needed to run to upload to github for Scheme in Python.

git remote add origin git@github.com:jacktrades/Scheme-in-Python.git

You will only need to do this once. Afterward you can just use the push command.

$ git push -u origin master

This will upload the master branch to the server. If you don’t do any branching master will be the only branch you have.

Creating and changing branches

Creating a new branch in git is simple, just use the branch command.

$ git branch v0.01

Here a new branch was created and named v0.01. You could choose any name you want for the branch, though I’m not sure exactly what characters are allowed.

Even though the v0.01 branch was created, git does not automatically switch you into it. To find out what branch you are in you can use the branch command without any other arguments.

$ git branch
* master
  v0.01

The branch name with the asterisk(*) next to it is the branch you are currently in. To change to another branch use the checkout command.

$ git checkout v0.01

This changes the current branch to v0.01, to verify this you can use the branch command again.

$ git branch
  master
* v0.01

When you make changes and commit them you will be commiting to the current branch (in this instance the v0.01 branch). If you make some changes, commit them then switch back to the master branch, you’ll find that the commits are not there.

For convenience git provides a method of creating a new branch and checking out a working copy of it in one command. _{thanks r2p2}

$ git checkout -b v0.01

Pushing branches to a remote repo

To upload the new branch to the server you need to tell the push command which branch you want to push. So for the v0.01 branch you would need to do this.

$ git push origin v0.01

To push changes made in multiple branches you can leave off the branch at the end of the push command.

git push origin will push all changes on the local branches that have matching remote branches at origin.
– docgnome from stackoverflow

Merging

To merge one branch into another first checkout the branch that you want to merge into. For this example we’ll merge the v0.01 branch into master. So first we checkout the master branch then do a merge command.

$ git checkout master
$ git merge v0.01

Links

Git Book – Basic Branching and Merging

StackOverflow – How do I fix merge conflicts in Git

 

* That’s all for now, but I’ll come back and add commands for merging and how to resolve conflicts once I get the chance to use those features. This page will likely be updated a number of times as I learn more about git.

Which programming language should I learn?

The most difficult choice for someone who is new to programming is what language to learn.

You are in the worst position to choose for yourself because you don’t have enough knowledge yet to assess the pros and cons.

If you ask people that do know, you will get tons of different responses.

Most important things:

• There are enough learning materials.
• The community is active and helpful to newcomers.
• The language is difficult enough to challenge you, but easy enough not to discourage you.

Why it doesn’t matter:

• Over the course of the next few years you will learn many languages (if you plan on being any good).
• People say that if you pick an easy language (Python or Javascript) you will not learn the important concepts. This can be true, but only if you stop learning a few months in.
• You’re going to do it wrong in the beginning no matter what language you pick.

The most important thing when learning to program is staying motivated. The easiest way to stay motivated is to work on projects that you think are cool and actually complete them. If you pick a language that is too hard, you are likely to give up in frustration. Nothing is stopping you from learning the harder languages after you pick up the basics of the easier ones.

Pros and Cons of Specific Languages

In order of best to worst languages to learn as your first IMHO.

Python
Pros: Beginner friendly, lots of community support for newbies, lots of libraries to get you going quickly
Cons: If you don’t continually push yourself to learn, you can miss out on a lot of important computer science concepts that Python abstracts away for you.

Javascript
Pros: Very easy to start with, lots of libraries and code in the wild for you to study.
Cons: Community is full of non-programmers, you will pick up bad habits,

Scheme
Pros: Beautiful language, great books for intermediate level study
Cons: Small community, not very beginner friendly, few books that start at the ultra-noob level.

C
Pros: Will force you to learn all of the difficult concepts.
Cons: It will be hard. There are many traps and pitfalls that await you.

Java
Pros: Huge community and libraries
Cons: A sizable portion of people who only know Java (The perils of Java schools), forces you into a single way of thinking about programming. I strongly recommend staying away from Java as a first language.

More Tips

You should spend about a year getting to know your first language. After that you will want to start learning other languages. In my opinion you can’t call yourself a programmer until you are at least familiar with 3 languages. Meaning that you have written a small/medium sized program in each (~3,000 lines each).

But that’s not all. Programming isn’t really about languages at all! Programming is about being familiar with data structures, algorithms and other fundamental computer science concepts and how they apply to solving real problems. In the end it’s all about experience, build applications and solve problems and eventually you will look back on what you have done and say, “Now I think I’m a programmer”.

But wait! That’s not all! Next year you will look back on the year before and say, “I had absolutely no idea what I was doing last year.” The year after you’ll say the same, and the year after that, and the year after that, and so on. Learning to program is a never-ending process that will keep challenging you until you decide to hang up your hat.

Also read Tips for a New Programmer.