Some tricky AutoLISP examples / more Lisp

• AutoLISP
  • Sorting in AutoLISP
  • Common Lisp ports
  • Computional Geometry
  • Trivia
• LISP, Common Lisp, Scheme, Links
  • FFI's
  • CormanLisp
  • CL books

AutoLISP

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.

• Fast Boyer-Moore String Search in strings by Serge Pashkov. Fastest Boyer-Moore string search in files by Serge Pashkov
• iterative MAPATOM by Serge Pashkov
• Self-Modifying Code in AutoLISP
• Printing a Tree
• more AutoLISP goodies by various authors
• Useful String -> List functions
• Look also in Vladimir Nesterovski's code directory for some tricky lisp functions (have I published some tricky ones of mine too?)
• Okay, there are the champions. The lisp puzzle contest: Serge Volkov wins in one line.
  

  (defun remove (expr lst)
    (apply 'append (subst nil (list expr) (mapcar 'list lst))))
  

  Apparently Tony Tanzillo stated at the 12.May 99 that he is the author, posted 8 years ago to the compuserve forum. Sorry about the confusion!

• Vladimir Nesterowski's string parsing work (very elegant!) plus a complete explanation of mapcar and lambda followed by the apply discussion
  Douglas Wilson:
  

  (defun list-transpose (l)
    (apply 'mapcar (cons 'list l)))

• The Recursion Document (from usenet, thanks Dennis Shinn)
  Also a general intro into recursion

Sorting in AutoLISP

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 STDLIST.LSP

References:

Sedgewick: Algorithms
Knuth: part 3, Winston-Horn: Lisp

The Common Lisp sort function looks like this:
(sort sequence less-than-predicate) (simplified)
In AutoLISP try to implement it like this:
(sort list lambda-expr) eg:

(sort pts '(lambda (p1 p2)(< (car p1)(car p2)))) which sorts points for its x value.

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 reasons only:
  • 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 eric boehlke
  • 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.
  • ur_sort.lsp
    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:
  • bubble sort
    recursive implementation
    Strange, but bubble sort is usually fastest with small lists (<20) though algorithmically its a very weak sort method.
  • shell sort
  • shell sort for lists of lists
  • sort-down
    uses (bubble) for sorting sublists

Definition

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:
http://ourworld.compuserve.com/homepages/tonyt/sortsort.htm
but dont use that with negative numbers or sort it using qsort() of the c lib (->ADS)
http://xarch.tu-graz.ac.at/autocad/news/sort.c
With Vital Lisp use the builtin (vlx-sort)
merge-sort is usually fastest but uses the most resources (see the FAQ: [16] stack overflow).
Some tricky sort functions use the internal hash-table for fast symbol access, but have some overhead (i.e. nssort) see http://www.autodesk.com/support/techdocs/td30/td300517.htm

Common Lisp ports

• 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 here ASAP. 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 job paper: "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)
• WCMATCH workaround
• 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
• stdlib/test/RUNTEST.LSP 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 usenet thread.

Trivia

• Femfatalatron 1.0 Product Description includes some of the very first citations of autolips in the wild.
• AIML for Lisp Programmers describes AIML, the "Artificial Intelligence Marketing Language".

Computional Geometry

• Recommended ADS/ARX solutions with external libraries.

  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 <piazza@mec-sol.com> 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 Geometry page. 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))))) pts ) Extensions:
  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

misc

• New Riders LISP API Toolkit General ASE, Xdata, ... toolkit
• I explained my sigs here. My signatures may look cryptic, but once understood it helps a lot understanding recursion at all.

LISP

• Design Issues for Foreign Function Interfaces
  A survey of existing native interfaces for several languages.
  Not quite finished yet.
• My Emacs for Win32 page. (for XEmacs and GNU ntemacs)

  ---

• The Association of Lisp Users should be the startpoint for everyone looking for lisp links.

  And because this is getting asked over and over again:

  • Common Lisp - Myths and Legends
  • What is Lisp?
  • What is Lisp Good For?
• The fundamental FUNARG problem for dynamical lisps explained by Jeff Dalton on comp.lang.lisp. This was the reason to fix this with FUNCTION or #' in the late 50's and lexical scoping later.
• The complete idiot's guide to special variables by Eran Gat. Why and when DEFVAR and DEFINE-SYMBOL-MACRO is EVIL and should be avoided at all. From comp.lang.lisp.
• Riesbeck Lisp Style Some brief notes on good coding practice plus recommended notes on good function and variable naming.
• The highly recommended book "The Computional Beauty of Nature" features a tiny lisp, called stutter, with only seven primitives: car, cdr, cons, if, set, equal, quote, and lambda. Note that there are explicitly no numbers. The sample file float.slp shows how to represent numbers and calculate with this.
• Tony Tanzillo's AutoLISP-XLISP Tutorial (zipped) A good introductory into LISP for AutoLISP'ers.
• more notes about match
• some common lisp prejudices which are NOT true.
• Symbolic link to the local Lisp FAQ directory XLISP - Where it all started...
  A free Lisp for all platforms. A bit hairy for AutoLISP used programmers. Just the Lisp prompt, nothing else.

  Sources from "Winston/Horn" See also my match.lsp

  official FAQ's, other groups

  Complete xlisp 2.1 w/ byte-compiler source tree
  downloadable archive for unix

  xlisp 1.1 was the source for AutoLISP. Here is the source code. Also included a byte compiler, similar to the acomp compiler. For those who want to know how some lisp functions are defined in C, and what functions where dismissed by AutoDESK

  Learning Common Lisp

  Lisp on the net

  CMU Common Lisp repository (as part of the huge AI repository, tons of software)

  Common Lisp: The Language 2nd Ed. Steele

  ANSI Common Lisp HyperSpec

  SIOD Scheme In One Defun (before: Scheme written In One Day :)

  A tiny scheme with 500% functionality of AutoLISP (regex, db access), written to do some practical with Scheme: here a cgi-scripting implementation for the MS NT web server.

  Lily 0.1 (fixed link)

  This directory contains the Lily (LIsp LibrarY) C++ class library which gives C++ programmers the capability to write LISP-style code.

  I (Roger Sheldon) think Lily will be useful in academia for instructors who want to teach artificial intelligence techniques with C++. The garbage collection mechanism employed by Lily is slow which will make it unattractive for commercial use.
  (local copy, readme and docs
  )

  lpp (Lisp Plus Plus). A lisp in C++ by William Paul Vrotney. Similar to lily but apparently better. Specialized on dynamic typing as in lisp, overcoming the virtual function problems (vtable dispatch) in C++ by using a meta type object. Funny name indeed.

  See also the very recommended splash c++ library at ftp://ftp.netcom.com/pub/mo/morris/ for perl like constructs in C++ (esp. regex and hashed arrays). local readme

  Elegant LISP programs A transcript of lecture by G. J. Chaitin, chaitin@watson.ibm.com

  Pitman about CL

  An Easy Lisp Primer

  The Lisp part of the comp.ai.imho FAQ by Jorn Barger.

  ELM-ART: Episodic Learner Model Online interactive LISP course, based on CL-HTTP, a free Common Lisp web server. In german or english.

  History: stallman about gnu language extension plans: a modified, lisp-like scheme. not easy to find on the web. Now it turned out to be guile. This is also a fine comparsion of typical extension languages, like perl, tcl, python, scheme and lisp.

• "ANSI Common Lisp" by Paul Graham. The code, 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 Dalton (j.dalton@ed.ac.uk)
• 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: