I looked into Python because I was considering translating the Lisp code for the Russell & Norvig AI textbook from Lisp to Java. Then I discovered Python and Jython, and thought they might be a better language than Java.
Python can be seen as either a practical (better libraries) version of Scheme, or as a cleaned-up (no $@&%) version of Perl. While Perl's philosophy is TIMTOWTDI (there's more than one way to do it), Python tries to provide a minimal subset that people will tend to use in the same way (maybe TOOWTDI for there's only one way to do it, but of course there's always more than one way if you try hard). One of Python's controversial features, using indentation level rather than begin/end or braces, was driven by this philosophy: since there are no braces, there are no style wars over where to put the braces. Interestingly, Lisp has exactly the same philosphy on this point: everyone uses emacs to indent their code, so they don't argue over the indentation. If you deleted the parens on control structure special forms, Lisp and Python programs would look quite similar.
Python has the philosophy of making sensible compromises that make the easy things very easy, and don't preclude too many hard things. In my opinion it does a very good job. The easy things are easy, the harder things are progressively harder, and you tend not to notice the inconsistencies. Lisp has the philosophy of making fewer compromises: of providing a very powerful and totally consistent core. This can make Lisp harder to learn because you operate at a higher level of abstraction right from the start and because you need to understand what you're doing, rather than just relying on what feels or looks nice. But it also means that in Lisp it is easier to add levels of abstraction and complexity; Lisp makes the very hard things not too hard.
Here I've taken a blurb from Python.org and created two vesions of it: one for Python in blue italics and one for Lisp in red bold. The bulk of the blurb, common to both languages, is in black.
Python/Lisp is an interpreted and compiled, object-oriented, high-level programming language with dynamic semantics. Its high-level built in data structures, combined with dynamic typing and dynamic binding, make it very attractive for Rapid Application Development, as well as for use as a scripting or glue language to connect existing components together. Python/Lisp's simple, easy to learn syntax emphasizes readability and therefore reduces the cost of program maintenance. Python/Lisp supports modules and packages, which encourages program modularity and code reuse. The Python/Lisp interpreter and the extensive standard library are available in source or binary form without charge for all major platforms, and can be freely distributed. Often, programmers fall in love with Python/Lisp because of the increased productivity it provides. Since there is no separate compilation step, the edit-test-debug cycle is incredibly fast. Debugging Python/Lisp programs is easy: a bug or bad input will never cause a segmentation fault. Instead, when the interpreter discovers an error, it raises an exception. When the program doesn't catch the exception, the interpreter prints a stack trace. A source level debugger allows inspection of local and global variables, evaluation of arbitrary expressions, setting breakpoints, stepping through the code a line at a time, and so on. The debugger is written in Python/Lisp itself, testifying to Python/Lisp's introspective power. On the other hand, often the quickest way to debug a program is to add a few print statements to the source: the fast edit-test-debug cycle makes this simple approach very effective.To which I can only add:
Although some people have initial resistance to the indentation as block structure/parentheses, most come to tolerate or even like/deeply appreciate them.
To learn more about Python, if you are an experienced programmer, I recommend going to the download page at Python.org and getting the documentation package, and paying particular attention to the Python Reference Manual and the Python Library Reference. There are all sorts of tutorials and published books, but these references are what you really need.
The following table serves as a Lisp/Python translation guide. Entries in red mark places where one language is noticibly worse, in my opinion. Entries in bold mark places where the languages are noticibly different, but neither approach is clearly better. Entries in regular font mean the languages are similar; the syntax might be slightly different, but the concepts are the same or very close. The table is followed by a list of gotchas and some sample programs in Python.
Key Features | Lisp Features | Python Features | ||||||
Everything is an object | Yes | Yes | ||||||
Objects have type, not variables | Yes | Yes | ||||||
Support heterogeneous lists | Yes (linked list and array) | Yes (array) | ||||||
Multi-paradigm language | Yes: Functional, Imperative, OO, Generic | Yes: Functional, Imperative, OO | ||||||
Storage management | Automatic garbage collection | Automatic garbage collection | ||||||
Introspection of objects, classes | Strong | Strong | ||||||
Macros for metaprogramming | Powerful macros | No macros | ||||||
Interactive Read-eval-print loop |
> (string-append "hello " "world")
"hello world" |
>>> ['hello', 'world'].join(' ')
'hello world' |
||||||
Concise expressive language |
(defun transpose (m)
(apply #'mapcar #'list m)) > (transpose '((1 2 3) (4 5 6))) ((1 4) (2 5) (3 6)) |
def transpose (m):
zip(*m) >>> transpose([[1,2,3], [4,5,6]]) [(1, 4), (2, 5), (3, 6)] | ||||||
Cross-platform portability | Windows, Mac, Unix, Linux | Windows, Mac, Unix, Linux | ||||||
Number of implementations | Many | One | ||||||
Development Model | Proprietary and open source | Open source | ||||||
Efficiency | About 50 to 110% of C | About 10 to 110% of C | ||||||
GUI, Web, etc. librariees | Not standard | GUI, Web libraries standard | ||||||
Data Types | Lisp Data Types | Python Data Types | ||||||
Integer
Bignum Float Complex String Symbol Hashtable/Dictionary Function Class Instance Stream Boolean Empty Sequence Missing Value Lisp List (linked) Python List (adjustable array) Others |
42
100000000000000000 12.34 #C(1, 2) "hello" hello (make-hash-table) (lambda (x) (+ x x)) (defclass stack ...) (make 'stack) (open "file") t, nil (), #() linked list, array nil (1 2.0 "three") (make-arrary 3 :adjustable t :initial-contents '(1 2 3)) Many (in core language) |
42
100000000000000000 12.34 1 + 2J "hello" or 'hello' ## immutable 'hello' {} lambda x: x + x class Stack: ... Stack() open("file") 1, 0 (), [] tuple, array None (1, (2.0, ("three", None))) [1, 2.0, "three"] Many (in libraries) | ||||||
Control Structures | Lisp Control Structures | Python Control Structures | ||||||
Statements and expressions | Everything is an expression | Distinguish statements from expressions | ||||||
False values | nil is only false value | None, 0, '', [ ], {} are all false | ||||||
Function call | (func x y z) | func(x,y,z) | ||||||
Conditional test | (if x y z) |
if x: y
else: z |
||||||
While loop | (loop while (test) do (f)) | while test(): f() | ||||||
Other loops |
(dotimes (i n) (f i))
(loop for x in s do (f x)) (loop for (name addr salary) in db do ...) |
for i in range(n): f(i)
for x in s: f(x) ## works on any sequence for (name, addr, salary) in db: ... |
||||||
Assignment |
(setq x y)
(psetq x 1 y 2) (setf (slot x) y) user extensible values 1 2 3) on stack (multiple-value-setq (a b c) (values 1 2 3)) |
x = y
x, y = 1, 2 x.slot = y user extensible (1, 2, 3) uses memory in heap (a, b, c) = (1, 2, 3) |
||||||
Exceptions |
(assert (/= denom 0))
(unwind-protect (attempt) (recovery)) (catch 'ball ... (throw 'ball)) |
assert denom != 0, "denom != 0"
try: attempt() finally: recovery() try: ...; raise 'ball' except 'ball': ... |
||||||
Other control structures | case, etypecase, cond, with-open-file, etc. | No other control structures | ||||||
Lexical Structure | Lisp Lexical Structure | Python Lexical Structure | ||||||
Comments | ;; semicolon to end of line | ## hash mark to end of line | ||||||
Delimiters |
Parentheses to delimit expressions:
(defun fact (n) (if (<= n 1) 1 (* n (fact (- n 1))))) |
Indentation to delimit statements:
def fact (n): if n <= 1: return 1 else: return n * fact(n 1) | ||||||
Higher-Order Functions | Lisp Higher-Order Functions | Python Higher-Order Functions | ||||||
Function application
evaluate an expression execute a statement load a file |
(apply fn args)
(eval '(+ 2 2)) => 4 (eval '(dolist (x list) (f x))) (load "file.lisp") |
apply(fn, args) or fn(*args)
eval("2+2") => 4 exec("for x in list: f(x)") execfile("file.py") or import file |
||||||
Sequence functions |
(mapcar length '("one" (2 3))) => (3 2)
(reduce #'+ numbers) (remove-if-not #'evenp numbers) (reduce #'min numbers) |
map(len, ["one", [2, 3]]) => [3, 2]
or [len(x) for x in ["one", [2, 3]]] reduce(operator.add, numbers) filter(lambda x: x%2 == 0, numbers) or [x for x in numbers if x%2 == 0] min(numbers) |
||||||
Other higher-order functions |
some, every, count-if, etc.
:test, :key, etc keywords |
No other higher-order functions built-in
No keywords on map/reduce/filter |
||||||
Parameter Lists | Lisp Parameter Lists | Python Parameter Lists | ||||||
Optional arg
Variable-length arg Unspecified keyword args Calling convention |
(defun f (&optional (arg val) ...)
(defun f (&rest arg) ...) (defun f (&allow-other-keys &rest arg) ...) Call with keywords only when declared: (defun f (&key x y) ...) (f :y 1 :x 2) |
def f (arg=val): ...
def f (*arg): ... def f (**arg): ... Call any function with keywords: def f (x,y): ... f(y=1, x=2) |
||||||
Efficiency | Lisp Efficiency Issues | Python Efficiency Issues | ||||||
Compilation
Function reference resolution Declarations |
Compiles to native code
Most function/method lookups are fast Declarations can be made for efficiency |
Compiles to bytecode only
Most function/method lookups are slow No declarations | ||||||
Features | Lisp Features and Functions | Python Features and Functions | ||||||
Quotation |
Quote whole list structure:
'hello '(this is a test) '(hello world (+ 2 2)) |
Quote individual strings:
'hello' 'this is a test'.split() ['hello', 'world', [2, "+", 2]] |
||||||
Introspectible doc strings |
(defun f (x)
"compute f value" ...) > (documentation 'f 'function) "compute f value" |
def f(x):
"compute f value" ... >>> f.__doc__ "compute f value" | ||||||
List access |
Via functions:
(first list) (setf (elt list n) val) (first (last list)) (subseq list start end) (subseq list start) |
Via syntax:
list[0] list[n] = val list[-1] list[start:end] list[start:] |
||||||
Hashtable access |
Via functions:
(setq h (make-hash-table)) (setf (gethash "one" h) 1.0) (gethash "one" h) (let ((h (make-hash-table))) (setf (gethash "one" h) 1) (setf (gethash "two" h) 2) h) |
Via syntax:
h = {} h["one"] = 1.0 h["one"] or h.get("one") h = {"one": 1, "two": 2} Operations on lists |
(cons x y)
| (car x) (cdr x) (equal x y) (eq x y) nil (length seq) (vector 1 2 3) [x] + y but don't do this
| x[0] x[1:] but don't do this x == y x is y None or () or [ ] or 0 len(seq) (1, 2, 3) Operations on arrays |
(make-array 10 :initial-element 42)
| (aref x i) (incf (aref x i)) (setf (aref x i) 0) (length x) #(10 20 30) if size unchanging 10 * [42]
| x[i] x[i] += 1 x[i] = 0 (len x) [10, 20, 30] |
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 LispThis 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 ...
>>> x = 'global' >>> def f(x): return (lambda (y): (x, y)) >>> def g(x): return f('call f')('y value') >>> g('call g') ('global', 'y value')In Lisp, the equivalent would return ("call f" "y value"), because Lisp would use the local value for x within the lambda. There are three ways to get around this problem in Python. The first one can be used when you only need read-only access to local lexical variables. What you do is bind the variables you want to access in the argument list of the inner function. For example:
>>> def scale(k, vector): return map(lambda x, k=k: k*x, vector) >>> scale(2, [10,20,30]) [20, 40, 60]Note the k=k in the lambda argument list. This says that the function takes an argument k, whose default value is the value of k at the time the function is created. If you don't need to assign a new value to k in the body of the inner function, and if it doesn't bother you that the function will have default arguments that should never be supplied, this is an adequate solution. (In a way its nice to have the explicit reminder of what variables you're closing over.) If you do need to modify a variable, you can wrap the variable(s) in 1-element lists instead, but its not pretty:
def sum(items): total = [0.0] def f(x, total=total): total[0] = total[0] + x map(f, items) return total[0] >>> sum([1.1, 2.2, 3.3]) 6.6Notice also that you could not use a lambda here, because the lambda function body must be a single expression, not a statement. The third approach is to use objects instead of functions; this is not too bad because objects can be callable, but is still fairly verbose. Still, verbosity is in the eye of the beholder. Lisp programmers think that (lambda (x) (* k x)) is about right, but Smalltalk programmers think this is way too much, they use [:x | x * k], while Java programmers put up with a three-line inner class expression.
>>> 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. It seems that the grammar of Python is written in such a way that there are many intermediate nodes that contribute nothing. Only a real expert would want to manipulate these trees, whereas Lisp syntax trees are simple for anyone to use. It is still possible to create something similar to macros by concatenating strings, but this remains a weakness of Python when compared to Lisp.
Lisp Program simple.lisp | 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*))) |
from whrandom import choice def dict(**args): return args grammar = dict( 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 is_list(phrase): return mappend(generate, phrase) elif grammar.has_key(phrase): return generate(choice(grammar[phrase])) else: return [phrase] def generate_tree(phrase): "Generate a random sentence or phrase, with a complete parse tree." if is_list(phrase): return map(generate_tree, phrase) elif grammar.has_key(phrase): return [phrase] + generate_tree(choice(grammar[phrase])) else: return [phrase] def mappend(fn, list): "Append the results of calling fn on each element of list." return reduce(lambda x,y: x+y, map(fn, list)) def is_list(x): return type(x) is type([]) |
Running the Lisp Program | Running the Python Program |
> (generate 'S) (the man saw the table) |
>>> generate('S') ['the', 'man', 'saw', 'the', 'table'] >>> string.join(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 this logic expression evaluator:
Python Program logic.py |
import string class LogicExpr: """A logic expression or parse tree representing a formula. Use p&q for and, p|q for or, p^q for exclusive or, ~p for not, and p>>q for implies. Warning: >> has too high a precedence, so use parens: (p&q) >> (~r | s & ~t). Once you have an expression, evaluate it with exp.val().""" def __init__(self, *parts): self.parts = parts def __repr__(self): return "(" + string.join(map(str,self.parts)) + ")" def __and__(self, other): return LogicExpr(self, '&', other) def __or__(self, other): return LogicExpr(self, '|', other) def __xor__(self, other): return LogicExpr(self, '^', other) def __rshift__(self, other): return LogicExpr(self, '>>', other) def __invert__(self): return LogicExpr('~', self) def val(x): if x.parts[0] == '~': return not x.parts[1].val() (p, op, q) = x.parts if op == '&': return p.val() & q.val() if op == '|': return p.val() | q.val() if op == '^': return p.val() ^ q.val() if op == '>>': return (1 - p.val()) | q.val() raise ValueError, "unknown operator in" + str(x) class LogicVar(LogicExpr): "A logic variable can be set to true (1) or false (0) or unbound (None)." def __init__(self, name, value=None): self.name = name; self.value = value def __repr__(self): return self.name def set(self, value): self.value = value def val(self): return self.value true = LogicVar('true', 1) false = LogicVar('false', 0) def logic_vars(vars, ns=globals()): "Initialize vars to logic variables in namespace ns" ns['true'] = true; ns['false'] = false if type(vars) == type(""): vars = string.split(vars) for var in vars: ns[var] = LogicVar(var) |
Running the Python Program |
>>> logic_vars("a b c d") >>> expr = (a & b | c & d) >> (a ^ ~b) >>> expr (((a & b) | (c & d)) >> (a ^ (~ b))) >>> a.set(1); b.set(0); c.set(1); d.set(1) >>> expr.val() 0 >>> (a | b).val() 1 |
Now that I have more experience in Python, I can see that the more typical approach is to write a trivial ad-hoc parser for grammar rules: a grammar rule is a list of alternatives, separated by '|', where each alternative is a list of words, separated by ' '. 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) |
"""Module to 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 it is not in the grammar it rewrites as itself. The functions rewrite and rewrite_tree take as input a list of words and an accumulator (empty list) to which the results are appended. The function generate and generate_tree are convenient interfaces to rewrite and rewrite_tree that accept a string (which defaults to 'S') as input.""" import random def make_grammar(**grammar): "Create a dictionary mapping symbols to alternatives." for k in grammar.keys(): grammar[k] = [alt.strip().split(' ') for alt in grammar[k].split('|')] return grammar grammar = make_grammar( S = 'NP VP', NP = 'Art N', VP = 'V NP', Art = 'the | a', N = 'man | ball | woman | table', V = 'hit | took | saw | liked' ) def rewrite(words, into): "Replace each word in the list with a random entry in grammar (recursively)." for word in words: if grammar.has_key(word): rewrite(random.choice(grammar[word]), into) else: into.append(word) return into def rewrite_tree(words, into): "Replace the list of words into a random tree, chosen from grammar." for word in words: if grammar.has_key(word): into.append({word: rewrite_tree(random.choice(grammar[word]), [])}) else: into.append(word) return into def generate(str='S'): "Replace each word in str by a random entry in grammar (recursively)." return ' '.join(rewrite(str.split(' '), [])) def generate_tree(cat='S'): "Use grammar to rewrite the category cat" return rewrite_tree([cat], []) |
I was running Python on a Mac, for which the integrated development environment does not work, so I missing some debugging capabilities. So I decided to see if I could implement Common Lisp's trace facility in Python. The answer is yes:
Python Program trace.py |
"""Module trace: trace(fn1, fn2, ...): Causes the functions to be traced, as in Common Lisp untrace(fn1, fn2, ...): Undoes the effect of a trace. With no args, untraces everything. If you redefine a function, it becomes untraced, but is retraced the next time you do any trace, even trace().""" traced = {} ## Dictionary of traced functions level = 0 ## Trace level, for indentation def trace(*fns): for fn in list(fns) + traced.keys(): if isinstance(fn, TracedFunction): pass elif not callable(fn): print fn, "is not a function, can't be traced" else: traced[fn] = 1 globals()[fn.__name__] = TracedFunction(fn) def untrace(*fns): if len(fns) == 0: fns = traced.keys() for fn in fns: if isinstance(fn, TracedFunction): del traced[fn.fn] globals()[fn.__name__] = fn.fn else: print fn, "is not a traced function, can't be untraced" class TracedFunction: def __init__(self, fn): self.fn = fn; self.__name__ = fn.__name__ def __call__(self, *args): global level name = getattr(self.fn, '__name__', '??') print ' '*2*level + '=>', name + str(args) try: level = level + 1 val = apply(self.fn, args) print ' '*2*(level-1) + '<=', name + str(args), '=', val finally: level = level - 1 return val |
Running the Python Program |
>>> def fact(n): if n <= 1: return 1 else: return n * fact(n-1) >>> fact <function fact at b750aa0> >>> trace(fact) >>> fact(5) => fact(5,) => fact(4,) => fact(3,) => fact(2,) => fact(1,) <= fact(1,) = 1 <= fact(2,) = 2 <= fact(3,) = 6 <= fact(4,) = 24 <= fact(5,) = 120 120 >>> fact <__main__.TracedFunction instance at b751c60> >>> untrace(fact) >>> fact <function fact at b750aa0> |
Next, I decided to try a re-implementation of part of the search code, since we had had a recent discussion about some problems with that code. It was easy to program (after discovering some of the gotchas above):
Python Program search.py |
class Problem: """A formal problem, with initial state, goal or is_goal test, successsor function and arc_cost function.""" def __init__(self, initial, goal=None): self.initial = initial; self.goal = goal def succ(self, state): return () ## default no successors def is_goal(self, state): return state == self.goal def arc_cost(self, state1, operator, state2): return 1 class Node: "A node in a search tree." def __init__(self, state, parent=None, operator=None, path_cost=0): self.state, self.parent, self.operator, self.path_cost = \ state, parent, operator, path_cost def __repr__(self): return "<" + str(self.state) + ">" def path(self): if self.parent is None: return [self.state] else: return self.parent.path() + [self.operator, self.state] def print_path(self): fmt = "%-20s %-20s %s" if self.parent is None: print fmt % ("Operator", "State", "Cost") else: self.parent.print_path() print fmt % (self.operator, self.state, self.path_cost) def actions(self): if self.parent is None: return [] else: return self.parent.actions() + [self.operator] def states(self): if self.parent is None: return [self.state] else: return self.parent.states() + [self.state] class GraphSearch: """Expand nodes according to the specification of the problem until we find a solution or run out of nodes to expand. [p 73]. To make this work, you subclass GraphSearch, providing an enqueue method. Then do SubClassSearch(problem).search().""" def __init__(self,problem): self.problem = problem def enqueue(self, nodes, new): raise 'Need to define an enqueue method' def search(self): nodes = [Node(self.problem.initial)] while nodes != []: ### print nodes ### debugging node = nodes.pop() if self.problem.is_goal(node.state): return node self.enqueue(nodes, self.expand(node)) return None def expand(self, parent): new_nodes = [] for (op, state) in self.problem.succ(parent.state): cost = self.problem.arc_cost(parent.state, op, state) new_nodes.append(Node(state, parent, op, parent.path_cost + cost)) return new_nodes class BreadthFirstSearch(GraphSearch): "Search the shallowest nodes in the search tree first. [p 74]" def enqueue(self, nodes, new): nodes[0:0] = new ## Enqueue-At-End class DepthFirstSearch(GraphSearch): "Search the deepest nodes in the search tree first. [p 74]" def enqueue(self, nodes, new): nodes.extend(new) ## Enqueue-At-Front |
Running the Python Program |
>>> class NumberProblem(Problem): limit = 50 def __init__(self, initial, goal): self.initial, self.goal = initial, goal def succ(self, n): if n < self.limit: return (('L', 2*n), ('R', 2*n+1)) else: return () def is_goal(self, n): return n == self.goal >>> p = NumberProblem(initial=1, goal=7) >>> node = BreadthFirstSearch(p).search() >>> node.state 7 >>> node.path() [1, 'R', 3, 'R', 7] |