A Reputable Journal

I consider myself pretty up to speed on web development.

I’ve spent the last two days trying to find a hosting solution for the data structures eBook…. I looked at too many of the following:

• Google App Engine — I’m a long time GAE user, but the setup I have uses sphinx to generate content on the fly which it wants to store in pickle files on the local file system.  This doesn’t work with a GAE and some other systems that treat the file system as read only and expect any writing you do to go to a database.
• heroku — seems very promising, but I’m not sure how to configure web2py so it doesn’t need any local file system write access.  The lack of ssh access is a bit disconcerting.
• dotcloud — seems promising but the app kept hanging for no discernible reason.  I fought with it for the better part of the afternoon before deciding to move on.
• fluxflex — easy to get web2py installed, (1 minute)  but a real pain to try to work with a real app.  I’m not going to use the web interface for all my editing.  I want to git push and/or git pull to deploy and update the app.  It doesn’t seem possible to get both ease of installation and robust configuration management.
• pythonanywhere - non-starter
• webfaction — Its not free, but at least it has a command line I can work with and I’ve got the whole thing running.  The only confusing thing about webfaction is that they don’t list web2py as a supported framework, but when you type it in under other it magically works for  you….  The other annoying thing that I just discovered is that the 256MB limit is way too low for the default configuration.  I just now got a helpful email saying a support ticket had been opened for me because I was using too much memory.  This was like 15 minutes after I finally got my app running and I’d made about 5 page requests.

Now that I’m back from traveling in South America I’ve started on a project to add a turtle graphics module to skulpt.  Skulpt is a javascript implementation of Python written by Scott Graham, and is available on skulpt.googlecode.com.  Its a very nice project because it allows you to embed a Python interpreter right in your web page.  I’ve written about how to do this in a previous post.
The skulpt interpreter works like a charm, but it does not yet have any of the Python standard library modules implemented.  Scott has been working with wrapping some of Googles closure libraries, and has a webgl module too.  But none of your regular Python friends are available, things like math, random, turtle, etc need to be implemented.  For the most part these things are already available in javascript so the work is in creating the module and then wrapping the underlying Javascript inside the standard Python API.
Where to start?  There’s not a lot of documentation provided for skulpt, so I’m hoping this post will be enough to help others get going a bit quicker.  Scott was very helpful in responding to all my emails so this is not a criticism of him, rather I’m hoping this will save him the effort the next time someone wants to extend skulpt.  So, here’s the deal.  skulpt relies on two javascript files the first is skulpt.js  and builtin.js  A very minimal installation only uses skulpt.js, whereas if you want to use any modules they are in builtin.js.  Looking around the distribution you will not immediately find skulpt.js because you need to build it. You get a sculpt.js file by using the m script that comes with the distribution.  running m –help will give you the full list of commands, but the two that you probably most care about are m dist and m docbi The dist command builds both skulpt.js and builtin.js  docbi builds builtin.js and puts a new copy of it in the doc/static directory.
Lets begin with a quick tour of the source tree:

• src - contains the implementation of the Python interpreter
• src/lib - has the module implementations of webgl and goog.  This is where turtle will live and any other modules I implement along the way.
• doc - This directory contains a google app engine application and is what you see on skulpt.org There are a couple of important files to check out in here.  One of them is doc/static/env/editor.js  This is the code that ties together the interactive editor on the home page with the skulpt interpreter and the codemirror editor.  If you know how to build a google app engine app then this directory makes sense.  One thing about the home page is that it is not set up to use any of the modules.  The modules are used in the more advanced ide, which you can find in doc/ide/static.  I’m going to tell you how to add modules to the simpler editor later in this article.
• test - this directory contains a bunch of files for testing the implementation in a batch mode.  These tests are run whenever you run m dist, or m test.
• dist - This directory gets created and populated when you run the m dist command.  It contains the built and compressed versions of skulpt.js and builtin.js

To illustrate how to make use of modules, here’s an extended version of my earlier hello world style example.

<html>
<head>
<script src=“skulpt.js” type=“text/javascript”></script>
<script src=“builtin.js” type=“text/javascript”></script>

</head>

<body>
<script type=“text/javascript”>
function outf(text) {
   var mypre = document.getElementById(“output”);
   mypre.innerHTML = mypre.innerHTML + text;
}

function builtinRead(x)
{
    if (Sk.builtinFiles === undefined || Sk.builtinFiles[“files”][x] === undefined)
        throw “File not found: ‘” + x + “'";
    return Sk.builtinFiles[“files”][x];
}

function runit() {
   var prog = document.getElementById(“yourcode”).value;
   var mypre = document.getElementById(“output”);
   mypre.innerHTML = ‘';
   Sk.configure({output:outf,
           read: builtinRead
              });
   try {
      Sk.importMainWithBody("<stdin>",false,prog);
   } catch (e) {
      alert(e);
   }
}
</script>
<h3>Try This</h3>
<form>
<textarea edit_id=“eta_5” id=“yourcode”>
print “Hello World”
</textarea>
<button onclick=“runit()” type=“button”>Run</button>
</form>

<pre id=“output”></pre>

</body>
</html>

There are some important differences between this version, and the version and the non-module version.  First off, the call to Sk.configure contains another key value pair which sets up a specialized read function.  This is the function that is responsible for returning your module out of the large array of files that are contained in the builtin.js file.  You will see that all of the modules are contained in this one file, stored in a big JSON structure.  The extra key value pair is:
read: builtinRead
The read function is just for loading modules and is called when you do an import statement of some kind.  In this case the function accesses the variable builtinFiles which is created from the builtin.js file.  The other difference, of course, is that you have to include builtin.js in your html file.  Note that builtin.js must be included after skulpt.js
Now as far as the module itself goes, the easiest thing to do is to start your module in the src/lib directory.  This way it will automatically get built and included in builtin.js.  If you don’t put it there then you are going to have to modify the m script, specifically the docbi function in the m script to include your module.  Suppose that you want to have a module called bnm.test  Here’s what you have to do.  First, you need to make a bnm directory under lib.  In this directory you will need to have either init.py or init.js or bnm.js to stand in for the bnm module.  There doesn’t need to be anything in the file as long as it exists.  This is just like CPython by the way.  Then to make a test module you can either make a test directory and put all your javascript code in init.js or you can simply create a test.js file in the bnm directory.  Lets look at the test module.

var $builtinmodule = function(name)
{
    var mod = {};
    var myfact = function(n) {
 if(n < 1) {
     return 1;
 } else {
     return n * myfact(n-1);
 }
    }
    mod.fact = new Sk.builtin.func(function(a) {
 return myfact(a);
    });

    mod.Stack = Sk.misceval.buildClass(mod, function($gbl, $loc) {
 $loc.init = new Sk.builtin.func(function(self) {
     self.stack = [];
 });
 
 $loc.push = new Sk.builtin.func(function(self,x) {
     self.stack.push(x);
 });
 $loc.pop = new Sk.builtin.func(function(self) {
     return self.stack.pop();
 });
    },
    ‘Stack’, []);


    return mod;
}

All modules start out with the $var builtinmodule = statement.
This test module exposes a single method to the outside world, called fact, There are a couple of key functions for building up a module.  The Sk.builtin.func   call for adding functions to your module, and the Sk.misceval.buildClass method.  This test module defines a simple factorial function called fact, and a class called stack.  Here’s a simple Python program that exercises the module:

import bnm.test

print ‘starting’

print bnm.test.fact(10)

x = bnm.test.Stack()

x.push(1)

x.push(2)

print x.pop()

print ‘done’

Its not obvious, but the buildClass method takes four parameters:  globals, func, name, bases
It seems that you always pass the mod object itself as the globals parameter, the func parameter is a function that represents the class object, the Name is the external name of the class, and bases presumably would be if the class is inheriting from another class.
The Sk.builtin.func method creates a function.  For module creation we typically only have to worry about the one parameter, func, which is the javascript implementation of our Python function.  The method can also take a globals object and two closure objects.  Look at the comments in function.js if you want more explanation of how the builtin.func method works.
Well, I think this should be enough to get you going.  Its worth repeating, if you made it this far, don’t forget to call m docbi or m dist after you make changes in your module, its easy to get into the mode of thinking that the new javascript is automatically loaded.  But builtin.js is not automatically rebuilt!
I’ll consider this post a work in progress, please leave a comment if something is unclear or you would like something explained in more detail.

I’ve recently been looking for ways to run Python in a browser. There are lots of reasons why I think this is a cool idea. For example, creating some simple tutorials, Making some online quizzes and tests, getting Python to run on my iPad…

It looks like there are two projects that are actively working on solving this problem. The first is called skulpt (see the demo on skulpt.org.) This project actually reimplements the core of Python in Javascript by hand. They are working on some modules, but right now it is basically the core Python language.

The other project uses Emscripten to compile the CPython C source code to javascript! Yep you read that right. You can see here that the core of Python 2.7 is running. You can import sys, but thats about it. Nevertheless both of these are really useful for beginning Python exercises.

The problem with both of these is that right now there is no user level documentation. Skulpt is particularly difficult as you can’t even look at the demo page to see how its done. You need to go digging through some additional source files from the distribution to figure out how to make it work for yourself. The source code of the syntensity page is pretty easy to follow. So here’s a hello world program using skulpt.

<script src=“skulpt.js” type=“text/javascript”>
</script>


<script type=“text/javascript”>
function outf(text) {
   var mypre = document.getElementById(“output”);
   mypre.innerHTML = mypre.innerHTML + text;
}

function runit() {
   var prog = document.getElementById(“yourcode”).value;
   var mypre = document.getElementById(“output”);
   mypre.innerHTML = ‘';
   Sk.configure({output:outf});
   try {
      eval(Sk.importMainWithBody("<stdin>",false,prog));
   } catch (e) {
      alert(e);
   }
}
</script>
<h3>Try This</h3>
<form>
<textarea edit_id=“eta_5” id=“yourcode”>
print “Hello World”
</textarea>
<button onclick=“runit()” type=“button”>Run</button>
</form>

<pre id=“output”></pre>

Its a bit on the verbose side, and it could certainly be improved so that less code would have to be replicated if you wanted to put multiple input/output areas on a single page, but as a learning example I think it works OK. The try/catch block around the Sk.importMainWithBody function call will capture Python runtime errors and throw them. This is a nice way to inform your users of syntax errors in any code they are trying out.

I’m certainly no expert in either implementation, I just offer this post as an example and a time saver for anyone else trying to get going with either implementation.

Now that I’m back from my JTerm travels, I’m happy to let you know that the second edition of Problem Solving with Algorithms and Data Structures using Python is available.  (www.fbeedle.com) David and I have worked hard on this new edition for about a year now, and we are really excited about it. We think it is a great step forward from the first edition, and I’m really looking forward to teaching out of it next year.


Here’s whats new:

• All code is now written using Python 3.2
• Chapter 1 now introduces Python sets, and exception processing.
• Eliminated third party graphics package.  All graphics are done using the built-in turtle module
• Focus on algorithm analysis in a newly written chapter 2.  In addition this chapter includes the analysis of Key Python data structures used throughout the book
• New section on linked list implementation in Chapter 3
• Moved Dynamic Programming to the end of chapter 4
• Introduction of C style arrays and array management in Chapter 8
• More focus on graphical recursive algorithms, including recursive tree drawing, and a recursive maze search program.
• All source code for data structures has been organized into a single Python package to make it easy to incorporate into homework assignments.
• Source for complete examples from each chapter are included so you do not need to piece together code from each listing
• A new improved version of binary search trees in chapter 6.
• New secion on balanced binary trees (AVL trees) added to chapter 6.

The main site for resources for this book is at www.pythonworks.org

In the meantime, here’s the cover for the second edition

So I’m working on an app during my sabbatical that has an iPad component and an online Google App Engine component. The Google App Engine part is half web based and half web service based. Of course this means that the local client part has to be able to authenticate itself to the Google App Engine before it can communicate and do useful stuff. Finding good reliable examples of how to do this is surprisingly hard. For the Objective C code I’m working on I found a nice set of classes that do the trick for you here: On Github For Python I found some example code on stackoverflow. However it was not really in a reusable form.

The basic outline of what you have to do is as follows:

1. Login to https://www.google.com/accounts/ClientLogin This will give you an auth token.
2. Use the token you gained in step 1 to login to your Google App engine application or service. When you have successfully logged in to your service google will set an ACSID cookie for you to use when you make subsequent requests to your service. This prevents you from having to login each time you make a web service request.

I’ve taken some ideas from both places mentioned above and have created a Python class for logging in and accessing app engine services from Python. To use this module you just need to import it and create a GoogleAppEngineLogin object. Once the object is created you can use the open method on the object to access further services. The open method is just a convenience wrapper around urllib2.urlopen but it also makes sure that your cookie has not expired before it makes a request. If you have comments or suggestions for how to improve the code please let me know via email or leave a comment.

The code is reproduced below, but you can also just download the file from git clone git@gist.github.com:36b1c45ed39298178907.git

import getpass
import urllib
import urllib2
import cookielib


class GoogleAppEngineLogin(object):
    “""
   Logging in to an App Engine Account (when you use google users) is
   a two step process: First you must login to Google generally.  This
   gets you an auth token.  The auth token is used as part of a
   request to login to your app/service During the login process for
   your app/service the server sets a cookie with the name of ACSID,
   it is this cookie and its value that serves as the authentication
   token for your own service/app.  So, for future requests you need
   to give the server the cookie as part of your request.  Handling
   cookies can be a bit tricky if you haven’t had some experience with
   it but luckily Python’s cookielib module makes it all pretty
   automatic.

    This class takes care of the whole login process for you, and then
    gives you a simple helper to access the URLs for your service.
    The helper function makes sure the cookie is still valid and
    passes on the request along with the cookie.  Technically you
    would not even need to use the helper function, you could use
    urllib2 directly to access your service but this seems a bit
    neater to me.

    Some of this code was inspired by and lifted from an example on
    stackoverflow.com, but that was all in-line code my contribution
    is to add some error handling and encapsulate the whole thing
    inside a class to make it easier to include in my/your own
    programs.  Here’s a link to the original thread on stackoverflow
    http://stackoverflow.com/questions/101742/how-do-you-access-an-authenticated-google-app-engine-service-from-a-non-web-pyt

    “""
    
    def init(self, user_email, user_pw, uri, source):
        “""
        Create a Google App Engine Object.
        Arguments:
        - user_email:  your google username
        - user_pw: your google password
        - uri:  The url of your google app engine service
        - source: The unique name of your google app engine service
        “""
        self._user_email = user_email
        self._user_pw = user_pw
        self._uri = uri
        self._source = source
        self._authtoken = None
        self._auth_cookie = None
        
        if not self.google_client_login():
            raise RuntimeError(“Could not login to Google”)
        
        if not self.app_engine_login():
            raise RuntimeError(“Could not login to your application”)

        
    def google_client_login(self):
        #
        # get an AuthToken from Google accounts
        #
        auth_uri = ‘https://www.google.com/accounts/ClientLogin'
        authreq_data = urllib.urlencode({ “Email”:   self._user_email,
                                          “Passwd”:  self._user_pw,
                                          “service”: “ah”,
                                          “source”:  self._source,
                                          “accountType”: “HOSTED_OR_GOOGLE” })
        auth_req = urllib2.Request(auth_uri, data=authreq_data)
        try:
            auth_resp = urllib2.urlopen(auth_req)
            auth_resp_body = auth_resp.read()
        except:
            return False
        # auth response includes several fields - we’re interested in 
        #  the bit after Auth= 
        auth_resp_dict = dict(x.split("=")
                              for x in auth_resp_body.split("\n”) if x)
        try:
            self._authtoken = auth_resp_dict[“Auth”]
        except:
            return False

        return True

    def app_engine_login(self):
        #
        #  Get a cookie
        #  we use a cookie to authenticate with Google App Engine
        #  by registering a cookie handler here, this will automatically store the 
        #  cookie returned when we use urllib2 to open
        #  http://www.google.com/accounts/ClientLogin
        self._cookiejar = cookielib.LWPCookieJar()
        opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(self._cookiejar))
        urllib2.install_opener(opener)


        serv_args = {}
        serv_args[‘continue’] = self._uri
        serv_args[‘auth’]     = self._authtoken

        full_serv_uri = “%s/_ah/login?%s” % (self._uri,urllib.urlencode(serv_args))

        serv_req = urllib2.Request(full_serv_uri)
        serv_resp = urllib2.urlopen(serv_req)
        serv_resp_body = serv_resp.read()


        for i, c in enumerate(self._cookiejar):
            if c.name == ‘ACSID’:
                self._auth_cookie = c
                return True

        return False

    def open(self,url,data=None):
        “""
        url should be a properly encoded url ready to go.  data is
        optional and should be used to provide parameters to pass
        along with the URL when you want to use POST instead of GET.
        If you provide data it must be properly encoded just as if you
        were calling urlopen directly yourself.
        “""
        if self._auth_cookie.is_expired():
            if not self.google_client_login() or not self.app_engine_login():
                raise RuntimeError(“Cannot get proper authorization for this request”)
            
        serv_req = urllib2.Request(url,data)
        return urllib2.urlopen(serv_req)
        

if name == “main":
    user = raw_input(“User: “)
    pw = getpass.getpass(“Password: “)
    service_url = “http://myapp.appspot.com”
    service_name = “myapp”
    gae = GoogleAppEngineLogin(user,pw,service_url,service_name)
    h = gae.open(“http://myapp.appspot.com/my/service")
    print h.read()
        

I’ve seen several interesting blog posts related to MIT switching from Scheme to Python for their intro course. This is really interesting to me since SICP is one of my favorite CS books of all time. Nevertheless I’m glad to see leading institutions change to my favorite language.

Paraphrase of Gerald Sussman’s remarks

Dan Weinreb’s blog

The other day I discovered that the folks working on VPython have been very busy over the last couple of years. I had given up on VPython because the Mac distribution was so difficult to use. It required the X windows server and one point and lots of other extra junk at other times. But now things are easy! There is a great installer package and it just works.

For those of you who have not heard of VPython before it is a 3D graphics module called visual built on top of Python and OpenGL. You can do a lot of nice 3D graphics very simply with VPython. Its great for education in math and physics and introductory computer science.

So as an experiment I built a turtle graphics module on top of VPython. I use turtle graphics a lot in teaching but the TKinter turtles all suffer from some event loop problems when you use them with IDLE. VPython does not suffer from this problem plus gives you a lot of other cool benefits. One of the benefits is that the window resizes automatically for you based on the units you use in your application. Want to draw a picture at the atomic level of detail? No problem, want to draw planets circling each other? Again no problem.

Here’s a screen capture of a fractal tree created in 3-D using my new turtle.

Here’s the VPython turtle code:

def tree(t,trunkLength):
    if trunkLength < 5:
        return
    else:
        turnDz = random.randint(20,40)
        turnDx = random.randint(20,40)
        trunkShort = random.randint(10,20)
        t.width(trunkLength/10.0)
        if trunkLength < 25:
            t.color(color.green)
        else:
            t.color((174/255.0,145/255.0,0))
        t.forward(trunkLength)
        # right trunk
        t.right(turnDz,ZAXIS)
        tree(t,trunkLength-trunkShort)
        # left trunk
        t.left(2turnDz,ZAXIS)
        tree(t,trunkLength-trunkShort)
        # front trunk
        t.right(turnDz,ZAXIS)
        t.right(turnDx,XAXIS)
        tree(t,trunkLength-trunkShort)
        # back trunk
        t.left(2turnDx,XAXIS)
        tree(t,trunkLength-trunkShort)
        # restore
        t.right(turnDx,XAXIS)
        t.backward(trunkLength)

If you want to check out the turtle module and play with it, you are welcome to do so: hg clone bitbucket.org/bnmnetp/v… Or send me mail.