Python syntax in Lisp and Scheme
prunesquallor at comcast.net
prunesquallor at comcast.net
Mon Oct 13 13:24:58 EDT 2003
Alex Martelli <aleax at aleax.it> writes:
> The only example of 'power' I've seen (besides the infamous
> with-condition-maintained example) are such trifles as debugging-
> output macros that may get compiled out when a global flag to
> disable debugging is set -- exactly the kind of micro-optimization
> that IS typically (and more often than not inappropriately) done
> using preprocessors (such as, but not limited to, the C one, see
> below).
I posted a simple example that would be easy to understand, but
nonetheless practical. If you would like a more complicated example,
I suggest you look at Richard Waters's Series package at
http://series.sourceforge.net/
and Siskind and McAllister's Screamer package at
http://www.cis.upenn.edu/~screamer-tools/screamer-intro.html
and elsewhere
Both of these packages work through macro-expansion. The expansion
phase is quite complicated so I won't go through the details here.
However, I will demonstrate the expansion.
The Series packages implements a `series' datatype which is an
aggregate datatype much like a list. The functions that operate on
series, however, are usually able to operate via pre-order traversal
of the elements, so the code can often be compiled into a
straight-line loop. Thus you get the illusion of a functional data
structure with the performance and efficiency of a iterative process.
As a concrete example, suppose I have a list of numbers and I wish to
compute the result of dividing the absolute value of the maximum
number in the list by the sum of the other numbers in the list. The
`standard' sequence functions allow me to do this:
(defun example ()
(let ((elements '(3 -1 4 -1 5 -9 2 -6 5 -3)))
(/ (reduce #'max (map 'list #'abs elements))
(reduce #'+ elements))))
This works, but it is inefficient because MAP and the second REDUCE
both traverse the list, and the intermediate list generated by MAP is
immediately discarded (consumed) by the first REDUCE.
The series version appears quite similar:
(defun series-example ()
(let ((elements (scan '(3 -1 4 -1 5 -9 2 -6 5 -3))))
(/ (collect-max (#m abs elements))
(collect-sum elements))))
but if you macroexpand the body, you get this:
(COMMON-LISP:LET* (ELEMENTS (#:LISTPTR-702 '(3 -1 4 -1 5 -9 2 -6 5 -3)) #:ITEMS-710 (#:NUMBER-707 NIL) (#:SUM-714 0))
(DECLARE (TYPE LIST #:LISTPTR-702) (TYPE NUMBER #:SUM-714))
(TAGBODY
#:LL-717 (IF (ENDP #:LISTPTR-702) (GO SERIES::END))
(SETQ ELEMENTS (CAR #:LISTPTR-702))
(SETQ #:LISTPTR-702 (CDR #:LISTPTR-702))
(SETQ #:ITEMS-710 ((LAMBDA (#:V-708) (ABS #:V-708)) ELEMENTS))
(IF (OR (NULL #:NUMBER-707) (< #:NUMBER-707 #:ITEMS-710)) (SETQ #:NUMBER-707 #:ITEMS-710))
(SETQ #:SUM-714 (+ #:SUM-714 ELEMENTS))
(GO #:LL-717)
SERIES::END)
(IF (NULL #:NUMBER-707) (SETQ #:NUMBER-707 NIL))
(/ #:NUMBER-707 #:SUM-714))
This code avoids traversing the series more than once and does not
create an intermediate series just to discard it. It does this by
analyzing the code and determining that the computation may procede in
`lock step'.
This example is simple, and a human could have manually rewritten it,
but it is easy to come up with more complicated examples where the
rewrite is not obvious.
To use another example, Siskind and McAllister's Screamer introduces
non-deterministic forms into Lisp. As an example, you can compute
pythagorean triples via this constraint-based form:
(defun pythagorean-triples (n)
(all-values
(let ((a (an-integer-between 1 n))
(b (an-integer-between 1 n))
(c (an-integer-between 1 n)))
(unless (= (+ (* a a) (* b b)) (* c c)) (fail))
(list a b c))))
The body of this function expands into:
(LET ((VALUES 'NIL) (SCREAMER::LAST-VALUE-CONS NIL))
(LET ((SCREAMER::TRAIL-POINTER (FILL-POINTER SCREAMER::*TRAIL*)))
(SCREAMER::CHOICE-POINT-INTERNAL
(PROGN
(LET ((#:DUMMY-29301 N))
(LET ((#:CONTINUATION-29303
#'(LAMBDA (&OPTIONAL #:DUMMY-29283 &REST #:OTHER-29284)
(DECLARE (SCREAMER::MAGIC) (IGNORE #:OTHER-29284))
(PROGN
(LET ((#:DUMMY-29296 N))
(LET ((#:CONTINUATION-29298
#'(LAMBDA (&OPTIONAL #:DUMMY-29285 &REST #:OTHER-29286)
(DECLARE (SCREAMER::MAGIC) (IGNORE #:OTHER-29286))
(PROGN
(LET ((#:DUMMY-29291 N))
(LET ((#:CONTINUATION-29293
#'(LAMBDA (&OPTIONAL #:DUMMY-29287 &REST #:OTHER-29288)
(DECLARE (SCREAMER::MAGIC) (IGNORE #:OTHER-29288))
(LET ((C #:DUMMY-29287)
(B #:DUMMY-29285)
(A #:DUMMY-29283))
(PROGN
(IF (NULL (= (+ (* A A) (* B B)) (* C C)))
(PROGN (FAIL)))
(LET ((#:DUMMY-29281 (LIST A B C)))
(LET ((SCREAMER::VALUE #:DUMMY-29281))
(PROGN
(GLOBAL
(COND ((NULL VALUES)
(SETF
SCREAMER::LAST-VALUE-CONS
(LIST SCREAMER::VALUE))
(SETF
VALUES
SCREAMER::LAST-VALUE-CONS))
(T
(SETF
(REST SCREAMER::LAST-VALUE-CONS)
(LIST SCREAMER::VALUE))
(SETF
SCREAMER::LAST-VALUE-CONS
(REST
SCREAMER::LAST-VALUE-CONS)))))
(FAIL)))))))))
(DECLARE (DYNAMIC-EXTENT #:CONTINUATION-29293))
(SCREAMER::AN-INTEGER-BETWEEN-NONDETERMINISTIC #:CONTINUATION-29293
1
#:DUMMY-29291)))))))
(DECLARE (DYNAMIC-EXTENT #:CONTINUATION-29298))
(SCREAMER::AN-INTEGER-BETWEEN-NONDETERMINISTIC #:CONTINUATION-29298
1
#:DUMMY-29296)))))))
(DECLARE (DYNAMIC-EXTENT #:CONTINUATION-29303))
(SCREAMER::AN-INTEGER-BETWEEN-NONDETERMINISTIC #:CONTINUATION-29303 1 #:DUMMY-29301))))))
VALUES)
With suitable input from a mechanical engineer, one could
implement this:
(defun reactor-control ()
(all-values
(let ((temperature (an-integer-between -500 500)) ; in Celsius
(pressure (an-integer-between 0 10000)) ; in pascals
(power (an-integer-between 0 1000000000))) ; in watts
(unless (can-safely-operate-at? temperature pressure power) (fail))
(list temperature pressure power))))
More information about the Python-list
mailing list