Python for Lisp Programmers

An important point for many people is the speed of Python and Lisp versus other languages. Its hard to get benchmark data that is relevent to your set of applications, but this may be useful:

Speeds are normalized so the g++ compiler for C++ is 1.00, so 2.00 means twice as slow; 0.01 means 100 times faster. For Lisp, the CMUCL compiler was used. Background colors are coded according to legend on right. The last three lines give the mean score, 25% to 75% quartile scores (throwing out the bottom two and top two scores for each language), and overall range. Comparing Lisp and Python and throwing out the top and bottom two, we find Python is 3 to 85 times slower than Lisp -- about the same as Perl, but much slower than Java or Lisp. Lisp is about twice as fast as Java.

Gotchas for Lisp Programmers in Python

1. Lists are not Conses. Python lists are actually like adjustable arrays in Lisp or Vectors in Java. That means that list access is O(1), but that the equivalent of both cons and cdr generate O(n) new storage. You really want to use map or for e in x: rather than car/cdr recursion. Note that there are multiple empty lists, not just one. This fixes a common bug in Lisp, where users do (nconc old new) and expect old to be modified, but it is not modified when old is nil. In Python, old.extend(new) works even when old is [ ]. But it does mean that you have to test against [] with ==, not is, and it means that if you set a default argument equal to [] you better not modify the value.
2. Python is less functional. Partially because lists are not conses, Python uses more methods that mutate list structure than Lisp, and to emphasize that they mutate, they tend to return None. This is true for methods like list.sort, list.reverse, and list.remove. However, more recent versions of Python have snuck functional versions back in, as functions rather than methods: we now have sorted and reversed (but not removed).
3. Python classes are more functional. In Lisp (CLOS), when you redefine a class C, the object that represents C gets modified. Existing instances and subclasses that refer to C are thus redirected to the new class. This can sometimes cause problems, but in interactive debugging this is usually what you want. In Python, when you redefine a class you get a new class object, but the old instances and subclasses still refer to the old class. This means that most of the time you have to reload your subclasses and rebuild your data structures every time you redefine a class. If you forget, you can get confused.
4. Python is more dynamic, does less error-checking. In Python you won't get any warnings for undefined functions or fields, or wrong number of arguments passed to a function, or most anything else at load time; you have to wait until run time. The commercial Lisp implementations will flag many of these as warnings; simpler implementations like clisp do not. The one place where Python is demonstrably more dangerous is when you do self.feild = 0 when you meant to type self.field = 0; the former will dynamically create a new field. The equivalent in Lisp, (setf (feild self) 0) will give you an error. On the other hand, accessing an undefined field will give you an error in both languages.
5. Don't forget self. This is more for Java programmers than for Lisp programmers: within a method, make sure you do self.field, not field. There is no implicit scope. Most of the time this gives you a run-time error.
6. Don't forget return. Writing def twice(x): x+x is tempting and doesn't signal a warning or exception, but you probably meant to have a return in there. In a lambda you are prohibited from writing return, but the semantics is to do the return.
7. Watch out for singleton tuples. A tuple is just an immutable list, and is formed with parens rather than square braces. () is the empty tuple, and (1, 2) is a two-element tuple, but (1) is just 1. Use (1,) instead. Yuck. Damian Morton pointed out to me that it makes sense if you understand that tuples are printed with parens, but that they are formed by commas; the parens are just there to disambiguate the grouping. Under this interpretation, 1, 2 is a two element tuple, and 1, is a one-element tuple, and the parens are sometimes necessary, depending on where the tuple appears. For example, 2, + 2, is a legal expression, but it would probably be clearer to use (2,) + (2,) or (2, 2).
8. Watch out for certain exceptions. Be careful: dict[key] raises KeyError when key is missing; Lisp hashtable users expect nil. You need to catch the exception or test with key in dict, or use a defaultdict.
9. Python is a Lisp-1. By this I mean that Python has one namespace for functions and variables, like Scheme, not two like Common Lisp. For example:

   def f(list, len): return list((len, len(list))) ## bad Python
   (define (f list length) (list length (length list))) ;; bad Scheme
   (defun f (list length) (list length (length list))) ;; legal Common Lisp
   

   This also holds for fields and methods: you can't provide an abstraction level over a field with a method of the same name:

   class C:
    def f(self): return self.f ## bad Python
    ...
   

10. Python strings are not quite like Lisp symbols. Python does symbol lookup by interning strings in the hash tables that exist in modules and in classes. That is, when you write obj.slot Python looks for the string "slot" in the hash table for the class of obj, at run time. Python also interns some strings in user code, for example when you say x = "str". But it does not intern all strings (thanks to Brian Spilsbury for pointing this out; see the details for Python 2.7; other versions have different rules).
11. Python does not have macros. Python does have access to the abstract syntax tree of programs, but this is not for the faint of heart. On the plus side, the modules are easy to understand, and with five minutes and five lines of code I was able to get this:

    >>> parse("2 + 2")
    ['eval_input', ['testlist', ['test', ['and_test', ['not_test', ['comparison',
     ['expr', ['xor_expr', ['and_expr', ['shift_expr', ['arith_expr', ['term', 
     ['factor', ['power', ['atom', [2, '2']]]]], [14, '+'], ['term', ['factor',
     ['power', ['atom', [2, '2']]]]]]]]]]]]]]], [4, ''], [0, '']]
    

    This was rather a disapointment to me. The Lisp parse of the equivalent expression is (+ 2 2). It seems that only a real expert would want to manipulate Python parse trees, whereas Lisp parse trees are simple for anyone to use. It is still possible to create something similar to macros in Python by concatenating strings, but it is not integrated with the rest of the language, and so in practice is not done. In Lisp, there are two main purposes for macros: new control structures, and custom problem-specific languages. The former is just not done in Python. The later can be done for data with a problem-specific format in Python: below I define a context-free grammar in Python using a combination of the builtin syntax for dictionaries and a preprocessing step that parses strings into data structures. The combination is almost as nice as Lisp macros. But more complex tasks, such as writing a compiler for a logic programming language, are easy in Lisp but hard in Python.

Lisp Program simple.lisp Line-by-Line Translation to Python Program simple.py

(defparameter *grammar*
 '((sentence -> (noun-phrase verb-phrase))
 (noun-phrase -> (Article Noun))
 (verb-phrase -> (Verb noun-phrase))
 (Article -> the a)
 (Noun -> man ball woman table)
 (Verb -> hit took saw liked))
 "A grammar for a trivial subset of English.")
(defun generate (phrase)
 "Generate a random sentence or phrase"
 (cond ((listp phrase)
 (mappend #'generate phrase))
 ((rewrites phrase)
 (generate (random-elt (rewrites phrase))))
 (t (list phrase))))
(defun generate-tree (phrase)
 "Generate a random sentence or phrase,
 with a complete parse tree."
 (cond ((listp phrase)
 (mapcar #'generate-tree phrase))
 ((rewrites phrase)
 (cons phrase
 (generate-tree (random-elt (rewrites phrase)))))
 (t (list phrase))))
(defun mappend (fn list)
 "Append the results of calling fn on each element of list.
 Like mapcon, but uses append instead of nconc."
 (apply #'append (mapcar fn list)))
(defun rule-rhs (rule)
 "The right hand side of a rule."
 (rest (rest rule)))
(defun rewrites (category)
 "Return a list of the possible rewrites for this category."
 (rule-rhs (assoc category *grammar*)))
(defun random-elt (choices)
 "Choose an element from a list at random."
 (elt choices (random (length choices))))

import random
grammar = dict( # A grammar for a trivial subset of English.
 S = [['NP','VP']],
 NP = [['Art', 'N']],
 VP = [['V', 'NP']],
 Art = ['the', 'a'],
 N = ['man', 'ball', 'woman', 'table'],
 V = ['hit', 'took', 'saw', 'liked'])
def generate(phrase):
 "Generate a random sentence or phrase"
 if isinstance(phrase, list): 
 return mappend(generate, phrase)
 elif phrase in grammar:
 return generate(random.choice(grammar[phrase]))
 else: return [phrase]
 
def generate_tree(phrase):
 """Generate a random sentence or phrase,
 with a complete parse tree."""
 if isinstance(phrase, list): 
 return map(generate_tree, phrase)
 elif phrase in grammar:
 return [phrase] + generate_tree(random.choice(grammar[phrase]))
 else: return [phrase]
 
def mappend(fn, iterable):
 """Append the results of calling fn on each element of iterbale.
 Like iterools.chain.from_iterable."""
 return sum(map(fn, iterable), [])

> (generate 'S)
(the man saw the table)

>>> generate('S')
['the', 'man', 'saw', 'the', 'table']

I was concerned that the grammar is uglier in Python than in Lisp, so I thought about writing a Parser in Python (it turns out there are some already written and freely available) and about overloading the builtin operators. This second approach is feasible for some applications, such as my Expr class for representing and manipulating logical expressions. But for this application, a trivial ad-hoc parser for grammar rules will do: a grammar rule is a list of alternatives, separated by '|', where each alternative is a list of words, separated by white space. That, plus rewriting the grammar program in idiomatic Python rather than a transliteration from Lisp, leads to the following program:

Python Program simple.py (idiomatic version)

"""Generate random sentences from a grammar. The grammar
consists of entries that can be written as S = 'NP VP | S and S',
which gets translated to {'S': [['NP', 'VP'], ['S', 'and', 'S']]}, and
means that one of the top-level lists will be chosen at random, and
then each element of the second-level list will be rewritten; if a symbol is
not in the grammar it rewrites as itself. The functions generate and
generate_tree generate a string and tree representation, respectively, of
a random sentence."""
import random
def Grammar(**grammar):
 "Create a dictionary mapping symbols to alternatives."
 for (cat, rhs) in grammar.items():
 grammar[cat] = [alt.split() for alt in rhs.split('|')]
 return grammar
 
grammar = Grammar(
 S = 'NP VP | S and S',
 NP = 'Art N | Name',
 VP = 'V NP',
 Art = 'the | a | every | some',
 N = 'man | ball | woman | table | dog | cat | wombat',
 V = 'hit | took | saw | liked | worshiped | remembered',
 Name= 'Alice | Bob | Carlos | Dan | Eve'
 )
def generate(symbol='S'):
 "Replace symbol with a random entry in grammar (recursively); join into a string."
 if symbol not in grammar:
 return symbol
 else:
 return ' '.join(map(generate, random.choice(grammar[symbol])))
def generate_tree(symbol='S'):
 "Replace symbol with a random entry in grammar (recursively); return a tree."
 if symbol not in grammar:
 return symbol
 else:
 return {symbol: [generate_tree(x) for x in random.choice(grammar[symbol])]}

>>> generate_tree('S')
{'S': [{'S': [{'NP': [{'Art': ['every']}, {'N': ['dog']}]},
 {'VP': [{'V': ['saw']}, {'NP': [{'Name': ['Eve']}]}]}]},
 'and',
 {'S': [{'NP': [{'Art': ['every']}, {'N': ['wombat']}]},
 {'VP': [{'V': ['liked']}, {'NP': [{'Name': ['Dan']}]}]}]}]}

Peter Norvig