Why must implementing Python be hard unlike Scheme?

John Nagle nagle at animats.com
Thu Feb 21 18:28:53 CET 2008

seberino at spawar.navy.mil wrote:
> I'm learning Scheme and I am amazed how easy it is to start building a
> half baked Scheme implementation that somewhat works.
> After knowing Python for *years* I have no idea how to actually
> implement the darn thing.

     Why?  It's not very difficult.  Get a parser for LALR(1) grammars,
like YACC or Bison, write a tokenizer that understands Python indentation,
hook up a dictionary, and parse the thing into a tree.  This is all
covered in Compilers 101.  Get the Dragon Book if you don't know this stuff.

     Once you have a tree, figure out some way to encode the tree into a linear
form, and write an execution engine that reads byte codes and has the
big switch to call the function for each byte code.

     The run-time data implementation is all dictionaries.  In Python,
everything is a variable-sized hash.  You don't even have to allocate
storage during compile time.  The run-time environment is a tree of hashes.

     The resulting implementation will be slow, but then, so is CPython.
Too much time goes into hash lookups.

					John Nagle

More information about the Python-list mailing list