Some tricky AutoLISP examples / more Lisp
AutoLISP is the scripting language for AutoCAD by Autodesk, a very
crippled dynamic Lisp-1, based on very early xlisp sources (v1.0),
posted by David Betz on usenet (alt.sources), and without proper
copyright laws that time used by Autodesk as their free scripting
language. There's an old Byte article about that.
To keep the language simple, some typical features such as macros,
vectors, structs, destructive operations and objects were left
out. Memory was low then in the late 80'ies. Since then the language
itself was not improved at all, to keep things simple and to keep
backwards portability. From time to time some library functions were
added, such as DCL support (a cross-platform Dialog Control Language).
More language features or library functions never made it besides some
utility functions introduced with Vital Lisp (now Visual Lisp).
The language has several milestones since 1987:
- autolisp, based on xlisp 1.0 with ent-, ss-, and get- function plus wcmatch,
- extlisp, vmon (virtual memory on), use extended dos memory pages (R10),
- acomp bytecode compiler for european developers, also xlisp based (R10-R12),
- Vital Lisp, external compiler and development system (R12-R14),
- Reactors and Automation support (vill 3.2),
- Visual Lisp, based on vill 3.2, replaced old AutoLisp in R15 aka AutoCAD 2000.
Some trickies and goodies:
General speaking sorting in plain AutoLISP is a pain in the ass, because
you have no random sequence access, but there are some nice tricks. But
use (ads_strlsort) or any other ADS sort which you can get. (vl-sort) with
Visual Lisp is usually the best. Without VLISP use the stdlib implementation.
In Lisp the mostly used sort method is merge sort (also used in (str-sort) in AutoDesk's TABLES.LSP sample) because thats a
natural method for lists.
Normally (in C eg.) you use heap sort (for any
data) or qsort (for random data) and insertion sort for the small lists
(<7) or sublists within the algorithm.
Common Lisp sorting code is here.
The best and cleanest implementation so far is from Serge Pashkov, a stable
and iterative merge-sort for plain AutoLISP, provided with the stdlib, in
Knuth: part 3, Winston-Horn: Lisp
The Common Lisp sort function looks like this:(sort pts '(lambda (p1 p2)(< (car p1)(car p2))))
which sorts points for its x value.
(sort sequence less-than-predicate) (simplified)
In AutoLISP try to implement it like this:
(sort list lambda-expr)
In the examples below only William Kiernan's nssort works like this.
A more complicated usage example with mixed alphabetical and numerical parts
is explained here.
- ADS/CL sort benches by Vladimir Nesterowsky
- All other sort implementations below should be examined for tutorial
- another shell sort by Daniele Piazza
- lispsort by T.J. DiTullio
bubble and shell sort examples for one and more lists.
- nssort by william kiernan
modified shell sort with faster item access, fast for bigger lists
- AutoDESK has a cute example on its server.
a simple short bubble sort with nearly the same trick as william kiernan.
Now who was the first?
- qsort by
- sorts from ACAD Plus
Performance comparison of two "classic" sort algorithms . Performs a sort on long and short
badly-ordered lists using the 'bubble' and the 'shell' sort. Includes useful timing routines.
My own collection of simple lisp sort functions:
insertion, bubble and merge in various variants.
- TRBL_SORT: ADS qsort by William Kiernan
- Sort code from the ATJ V1N4 magazine:
(sort data method) ;method: less-than-predicate
;default for numbers: '<
You want to know the fastest sort method?
First of all it depends on your data. Strings should always be sorted
with the builtin
(acad_strlsort) function. Numbers or
points can be converted to strings:
but dont use that with negative numbers or
sort it using
qsort() of the c lib (->ADS)
With Vital Lisp use the builtin
merge-sort is usually fastest but uses the most resources (see the FAQ:
 stack overflow).
Some tricky sort functions use the internal hash-table for fast symbol
access, but have some overhead (i.e. nssort)
- I compiled the ultimate textbook "Common Lisp The Language 2nd Edition" to
Windows HTMLHelp [1.8mb]
This is more verbose but less exact than the Hyperspec, for which I have to wait for permission.
- I also compiled the complete reference "Common Lisp Hyperspec" to
Windows HTMLHelp [3.5mb], but have to wait for Harlequin, before publication, because I fixed some formatting.
- BTW: Microsoft's free HTML Workshop 1.21 to create your own CHM from HTML or Winhelp
should be here.
You'll need IE4 to read it or this hhupd 1.21 enabler.
- I maintain the Corman Lisp
AutoCAD ARX stub and
the AutoCAD module.
The ARX needs version Corman Lisp 1.3. Now we have COM access to ACAD
from inside and outside a common lisp and also in-proc native access
to ACAD.EXE as with ARX. It needs ccl version 1.3, no samples yet. We
are trying to produce the necessary CLOS code automatically by parsing
the ACAD.TLB and acad.lib export information. This enables easier
fixes and upgrades and needs at least 6 months less time. Rational
Rose support for cross-platform development is also doable, but not
for free. Ask Ralph Gimenez for this biest.
I also compiled the
Corman Lisp docs (v1.3) to Winhelp and HTMLHelp recently
and added CHM and CLtL2 support.
Ralph Gimenez' SAGE-CLOS for Visual Lisp is ready. A demo and some samples will be
It implements most of CLOS functionality in pure AutoLISP, the only drawback is
the syntax of some functions which cannot be ANSI compatible because AutoLISP supports
no macros, no optional arguments and no reader-macros like #', backquote and comma.
Anyway, it's the best, leaving better Lisp's aside.
View the thread on usenet.
I implemented some CL functions too. Some are part of the
AutoLISP Standard Library and some are in /autocad/code/rurban.
I have "almost" ANSI compatible defstruct, setf, vectors, arrays and I'm writing on a better backquote/comma than ralph gimenez already has in his sage-clos, requiring a better eval-read-load to support backquote,
defmacro and &optional.
Autodesk will probably enhance the AutoLISP language after acquiring the
Vital Lisp sources and according this
"Evaluate and recommend various technical possibilities for expanding
AutoLISP coverage in future AutoCAD releases including closer correspondence
with Common Lisp."
But this was some years ago and nothing happened.
Only ActiveX support was improved (exceptions, safearrays).
Fundamental differences between dynamical binding vs. lexical
binding are explained here by myself and here
by Jeff Dalton. AutoLISP uses dynamical binding for all symbols, in
Common Lisp or "true lisp's" you may choose it by yourself, but by
default local variables are lexically bound. In AutoLISP global
variables are much more dangerous. This may be a problem in
implementing object-oriented extensions in AutoLISP, esp. for
managing dialogs. SAGE-CLOS does it just fine. But for dialog
callbacks the usual way to handle list data is through dynamic
variables and not via client_data_tile and $data.
The Beauty of Recursion
Old examples from the "Winston/Horn" standard LISP textbook and a few
basic lisp manipulation functions.
Corrected some nasty bugs.
New: In this text there's a lot of talk about the advantages of tail recursion.
Recently I found a very nice text
which describes what tail-recursion is and why it's better. (Winston-Horn:
"LISP" is not on-line).
Note: VLISP uses no tail-recursion, so it is still stack exhaustive.
See stdlib/STDINIT2.LSP for the values of
the maximal allowed nesting depth (stack size)
Winston/Horn simple match.lsp for AutoLISP
- Winston/Horn extended whmatch.lsp for AutoLISP (fixed)
- CASE and LET, functions from Common Lisp
- ARRAY, AREF, functions from Common Lisp
- Sooner or later my implementation of defstruct, setf - defsetf, get -
getf and a simple class-defmeth-defprop will make it to appear here.
Ports will be made from this code
lets you test automatically function return values. It checks files like this:
(setq a '(0 1 2 3))
(remove 1 a) => (0 2 3)
(remove-duplicates (append a a)) => (0 1 2 3)
There's also a runtest.fas, which suppresses error messages. Then you could
check if functions correctly throw an error exception.
(nth 1.0 '(0 1)) => error
(length (0 1 . 2)) => error
- Binary Search Trees
I ported the example from ANSI CL by
Paul Graham to AutoLISP to have at least one fast and efficient data structure for fast searches.
(the full code in english is here)
But updates are costly, so it can only be used for static code.
Hashes and vectors are still impossible for the plain AutoLISP programmer.
(Vital Lisp Professional owners may ask for my vector and hash functions but
I will have to ask Basis or adesk now first)
News from the hash and vector front:
I recently implemented arrays and vectors with constant access and modification time
in plain AutoLISP, using only stdlib functions.
The trick is explained in this
- Recommended ADS/ARX solutions with
Right now I'm working on some geometric
libraries for perl, but e.g. the linear polygon triangulation with
holes should make it to lisp as well, sooner or later.
It did indeed. See TEST.LSP in Triangle.
Daniele Piazza's delauney triangulation
code for plain AutoLISP.
- Point in Polygon?
Some computional geometry in AutoLISP.
Nice example by Daniele Piazza <firstname.lastname@example.org>
Though it's much easier with
(entmake (list '(0 . "POINT")(cons 10 pt)))
(ssmemb (entlast) (ssget "_WP" poly)))
But: the above description is not foolproof with degenerated polygons
(acad's fault) whilst Daniele's method should work with every polygon.
The method (odd/even number of intersections of the polygon with a ray from
the point to infinity) is described at Paul Bourke's famous
Note also that the algorithm described in Sedgewick is wrong!
My eberly arx has this function also,
but is not as reliable. (strictly inside or on segment also allowed?)
- SweepLine.lsp by Daniele Piazza.
This is a "SWEEPLINE algorithm to compute all intersection points of n line segments"
(Preparata & Shamos - Computational Geometry: an introduction)
This is again academic code and should be used if you expect a huge
number of lines to intersect and you are looking for all intersection
points. (sweepline) should run in O(n*logn), but the shell sort in
AutoLISP is too slow.
;;; Otherwise a greedy method like this is sufficient:
;;; O(n*2), exactly: O(n*(n-1))
;;; test each line with all other lines
;;; segments: ((p1 p2)(p1 p2)...)
(defun greedy-all-intersections (segments / seg1 rest seg2 pt pts)
(setq rest segments)
(foreach seg1 segments
(setq rest (cdr rest))
(foreach seg2 rest
(if (setq pt (inters (car seg1)(cadr seg1)(car seg2)(cadr seg2) T))
(setq pts (cons pt pts)))))
It is possible to add bulged segments too by extending the data structure
"segment" with (p1 p2 bulge) for curved segments and
use a line-arc resp. arc-arc intersection method for those.
Then a straight segment is still representable with (p1 p2)
line-arc and arc-arc intersection methods are e.g. in GLNADS.C of the
AutoCAD SDK 2.0 and may be easily ported to AutoLISP.
Another method is with VLA where it is possible to use
(vla-intersect-with obj1 obj2), which works with curves and splines too.
- Center of Polygon by Reini Urban
Common Lisp, Scheme, xlisp and other lisp supporting stuff which could be
useful for AutoLISP programmers.
Recommended CL Reading
- "ANSI Common Lisp" by Paul Graham. The
also in german
- "LISP" by Winston, Horn
- "A gentle introduction into Lisp" by David Touretzky
- "Paradigms of AI programming" by Peter Norvig
- "Structure and Interpretation of Computer Programs" by Abelson, GJ Sussman, J Sussman, now online in fulltext (!)
- "ANSI Common Lisp HyperSpec", is based on the ANSI Standard, by X3J13, the ANSI CL comitee, provided by Kent
Pitman at Harlequin, is online
- "Common Lisp the Language 2nd ed." by Guy L. Steele is online
the wellknown (as "CLtL2") ANSI CL reference
- A short introduction to CLOS (Common Lisp object-oriented programming extension) by Jeff
- Henry Baker's Papers about efficient Lisp implementation issues.
- David Lamkins' Lisp Tutorial (online book)
- Lisp as an Alternative to Java
Another recent language comparison survey. Lisp (CL/scheme) vs C/C++ vs Java. Thanks Eran.
With marked entries are from this year.
Other AutoCAD pages:
Reini Urban <email@example.com>
Created: 20.Jan 96
Last update: "2002-04-09 14:06:24 rurban"