Common Lisp Implementations and Applications - Case Study Example

Common Lisp Introduction Common Lisp, generally abbreviated as CL, is one of the various dialects of the Lisp programming language, which itself is the second oldest high level language after Fortran. The initial design of CL was presented in 1982 (Guy, 1990). The CL dialect got standardized by ANSI X3J13 (previously X3.226-1994) in 1994. This standardization of Common Lisp accounts for it being the most widely used dialect of Lisp even at present. 2. Common Lisp Implementations CL is a language specification rather than implementation. A number of implementations of the Common Lisp standard are currently available comprising of commercial products as well as open source software. Table 1 shows some of the mostly used implementations of Common Lisp (Daniel, 2010). Table 1 Famous Implementations of Common Lisp Name a.k.a. License Platforms Allegro CL Commercial Linux, Unix, Mac, Windows Armed Bear CL ABCL GPL Linux, Unix, Mac, Windows CMU CL CMUCL Open Linux, Unix, Mac Clozure CL OpenMCL LLGPL Linux, Unix, Mac Corman CL Commercial Windows Embedded CL ECL LGPL Linux, Unix, Mac, Windows GNU CL GCL LGCP, GPL Linux, Unix, Mac, Windows GNU CLISP CLISP GPL Linux, Unix, Mac, Windows LispWorks Commercial Linux, Unix, Mac, Windows Scieneer CL SCL Commercial Linux, Unix Steel Bank CL SBCL BSD/Public Linux, Unix, Mac 3. Common Lisp Applications Common Lisp has been the chosen Lisp dialect in various development industries worldwide. One such industry is the Web. Some online shopping sites such as “Yahoo! Store” provide its users with a WYSIWYG editor for editing their online store through any standard web browser (Graham 2003). This editor is developed in Common Lisp. CL-HTTP is public domain web server developed by MIT Artificial Intelligence Lab. Some big companies such as AT&T have been using Common Lisp in their telecom systems. A UK based company, Harlequin, is known to have provided Common Lisp based products and consultancy services to AT&T (Kantrowitz 1994). Xanalys Ltd is another giant company that has been using Common Lisp within their application products. Xanalys LinkEXPLORER, is one of their products that is developed in LispWorks (an implementation of Common Lisp) (Levine & Pitman 2010). Common Lisp has successfully been used in areas of fraud detection so it could be that the underlying technology for authorization of the credit cards be CL based (Levine & Pitman 2010). Besides being used in internet web services, telecom industry, document translation, fraud detection in credit cards as well as crime investigation, CL has successfully been used in applications related to analysis of investments, finances, tracking of trends in stock markets, airline scheduling systems, space exploration, robotics, process planning, process scheduling, chemistry, physics and medicine. All these discussed application areas have a common trait; the problem structure is usually too complex. The following discussion depicts the situations where it is generally advised to use CL to simplify complex problems. 4. When to use Common Lisp Common Lisp has been used in the field of Artificial Intelligence since its inception. Although it may not be an optimal solution for common problems involving bulk processing based on clear cut, well defined data, yet it can still be used in these system. In a business accounting system that usually involves straight forward data, Common Lisp can actually find its worth due to the ever growing business needs. Wherever there is evolution, CL can find its application (Levine & Pitman 2010). CL truly finds its application in situations where the problem is too complex and has ambiguous specifications. In such cases the programmer writes the approximate program for the process and interactively allows the programming to make it specific to the problem. Furthermore, in case where the data has variable sources and multiple representations, the dynamic typing and flexible objects can configure to systems robustly. In cases where new data types, functions and classes are defined or removed, the existing instances do not require recompilation to be able to interact or stop interaction with each other. CL is optimized for incremental changes and therefore, CL is used in time evolving systems. The automatic garbage collection (storage mechanism) is constantly on watch and reclaims the old storage in cases of redefinitions. Rapid prototyping and deliverance is supported by CL. It comprises of a comprehensive library of pre-defined functionalities. The garbage collector saves the programmer from dealing with memory reclaiming aspects. In cases where the execution is not wanted to cease in case of erroneous data arrival, CL is used. Errors can be dealt with actively by defining transfer of controls in case of error occurrences (Levine & Pitman 2010). 5. Common Lisp Language Features Common Lisp is a high-level, general purpose language that supports multi programming paradigms (functional, procedural as well as object oriented). As the language is dynamic, it supports the incremental as well as evolutionary software development, wherein efficient programs are rendered at run-time through the iterative compilation. Common Lisp uses S-expressions for representing both code as well as data. S-expressions are list-based data structures that are used to represent semi structured data. S-expressions could be nested. They are generally expressed in text where a parenthesized, sequence of characters is separated by white spaces. The first element of every S-expression is an operator followed by the data e.g.: (= 6 (+ 3 3)) is a boolean S-expression that checks whether 3 + 3 is equal to 6 (square 3) calls a function square with argument as 3 (defun square (x) (* x x)) defines a function square that returns square of the argument x Common Lisp has more data types than any other language. It has scalar data type which includes numbers, characters and symbols. The number type includes integers, floating points, ratios and complex numbers. The character type includes not just the ASCII characters but also the Unicode. The symbol type is specific to CL alone and includes data objects that comprise of name, value, function, property list and package. Another data type is data structures that include lists, strings, vectors, bit-vectors, single and multi-dimensional arrays, hash tables, packages, structures and classes. Another data type is functions which may be first-class functions i.e. the functions may take other functions as arguments or they may return other functions. This allows for writing very general functions (Guy 1990). The supported features of Common Lisp include interactivity (through dynamic redefinitions), computations involving arbitrary precision integers, exact rational arithmetic or well-integrated complex numbers. It supports anonymous functions, method combinations, special (dynamically scoped) variables, named blocks, non-local ‘goto’ (catch/throw), type declarations, conditions, restarts, format function, arguments (optional/keyword) and extensive list processing features. It supports meta-object protocol, runtime compiler availability and multiple dispatch features. CL has a built-in programmable parser/un-parser, macros (reader/compiler) and loop macros, first-class symbols/classes/meta-classes/packages/functions, generalized references, multiple inheritance and generic functions. Although Common Lisp may not be as popular as the non-Lisp languages, yet many of its features have been adapted into the more widely used programming systems and languages. 6. Example Problem solved using Common Lisp In order to explain how Common Lisp can be used to solve problems that some other non-Lisp programming languages (e.g. C++) can solve, this section presents one such problem with its solution in Common Lisp. Problem Statement Tower of Hanoi (Petković 2009, Weisstein 2012) is a simple toy problem in artificial intelligence which is a puzzle that comprises of three rods, and ‘n’ number of disks of variable sizes that can slide onto any of the three rods. At the starting position of the puzzle, all the disks are stacked neatly in an ascending order of their sizes on any one of the rods (i.e. a conical shape is made with the smallest disk on the top). The objective is to move the whole stack of disks from the existing rod to another rod, while abiding by the following rules: 1. Only one of the disks can be moved at a time 2. Only the topmost disc can be moved from one rod to another. The rod may be empty or have a disc already. 3. A bigger disk cannot be placed on a smaller one The number of moves to solve the Tower of Hanoi is 2n -1, where n is the number of disks. So, for 3 discs, the problem can be solved in 7 moves. Figure 1 shows the starting position of the puzzle. Figure 1 Initial State of Tower of Hanoi Problem Solution In order to solve the problem, it is repeatedly broken down into smaller, simplified versions until the solution is reached. For example, for ‘n’ number of discs, label the three rods as A, B and C and number the discs according to sizes i.e. smallest disc as 1 and largest as n. In order to move discs from rod A to C, the clear cut solution is to 1. Move all the n-1 discs from rod A to B first which would leave only disc n on the rod 2. Move the nth disc from rod A to C 3. Move all the n-1 discs from rod B onto C onto the disc n But in order to move n-1 discs from rod A to B, the same sequence of steps would be required as the rules need to be followed. This forms the solution a recursive algorithm where one method is called from within the method. The algorithm will apply till n=1 i.e. till only a single disc will have to be moved from rod A to B. Devising the Algorithm Assuming a tower of height ‘n’ (n = number of disks) from the starting rod A (assuming ‘from’) onto the destination rod C (assuming ‘to’), it is assumed that B is the remaining third rod (assuming ‘via’) and that to ≠ from. In case of only one disc (h=1), the disc can simply be moved. But in the case where n>1, then in all the moves, the largest disc would eventually have to move to rod C. This is possible only when all smaller discs are moved on rod B (Petković 2009). See Figure 2. Figure 2 Tower of Hanoi - First Moves Therefore, first all n-1 discs need to be moved to B. For that again, in order to move the largest disc all the smallest discs must first be moved from peg B to C. Assuming, 1 to be the smallest disc and n, the largest, the algorithm steps would be 1. If n>1 then use same method to first move the n-1 smaller discs from rod A to B 2. Now the largest disc, i.e. disc n-1 can be moved from rod A to C 3. If again n>1 then again use same method to move the n-1 smaller disks from rod B to C Code in Common Lisp Following is the code for the Tower of Hanoi in Common Lisp. The following code is saved in a file called “hanoi.lisp”. (defun move (n from to via) (cond ((= n 1) (format t "Move topmost disc from ~A to ~A.~%" from to)) (t (move (- n 1) from via to) (format t "Move topmost disc from ~A to ~A.~%" from to) (move (- n 1) via to from)))) (defun hanoi(n) (move n #\A #\C #\B) ) The Steele Bank CL (see Table 1), an implementation of Common Lisp was used to compile the code. The “hanoi.lisp” file was initially loaded into memory and then the function ‘hanoi’ was called with number of discs as argument. Shown below is the program’s output. Microsoft Windows [Version 6.1.7601] Copyright (c) 2009 Microsoft Corporation. All rights reserved. C:\Program Files (x86)\Steel Bank Common Lisp\1.0.55>sbcl This is SBCL 1.0.55, an implementation of ANSI Common Lisp. More information about SBCL is available at . SBCL is free software, provided as is, with absolutely no warranty. It is mostly in the public domain; some portions are provided under BSD-style licenses. See the CREDITS and COPYING files in the distribution for more information. This is experimental prerelease support for the Windows platform: use at your own risk. "Your Kitten of Death awaits!" * (load "hanoi.lisp") T * (hanoi 3) Move topmost disc from A to C. Move topmost disc from A to B. Move topmost disc from C to B. Move topmost disc from A to C. Move topmost disc from B to A. Move topmost disc from B to C. Move topmost disc from A to C. NIL As can be seen above, for 3 discs, the number of moves is equal to seven. 7. Conclusion Common Lisp is the first ANSI standard for object oriented programming language. It is a fully featured alternative to the non-Lisp programming language. CL generates compiled machine code which runs equally fast as any other language. As unlike other languages, the code can be compiled without direct declaration of data types and so types can be determined dynamically and behavior be assigned on runtime dispatch. So the dynamic declarations and runtime dispatch features may make the program slow, but these features relieve the program of considerable debugging issues. When using these features, the code is faster to write in CL than other languages. The size of CL has also shrunk over the years and is now comparative to the other alternatives. It has support for the useful data structures such as single and multi-dimensional, fixed and dynamic arrays of varying element types. In the Common Lisp, the compiler is not explicitly required as the interpreter is embedded with required semantics. Owing to emphasis put on its portable capacity in its design, the same CL program can be deployed on a number of platforms without installing upgrades of any kind. A few vendors (LispWorks) have also added the features of a CL program interacting with other programs of other languages e.g. C. It easily interfaces with TCP, CORBA, SQL and ODBC databases and DDC Client. COM and automation modules are also available. The language once understood, is easier to code and parse. Several text editors are available that further ease the coding aspect of CL. The generational garbage collection feature utilized in CL provides an efficient search mechanism particularly in systems that use virtual memory. 8. References Guy. L., Steele. Common Lisp: the language, 2nd Edition. Digital Press. 1990. Print. Daniel, Weinreb. Common Lisp Implementations: A Survey, Version 8. 2010. Web. 8 Feb 2012. Graham, Paul. Beating the Averages. 2003. Web. 8 Feb 2012. Kantrowitz, Mark. “A Timeline of Artificial Intelligence”. Selections from Milestones in the Development of Artificial Intelligence. 1994. Web. 8 Feb 2012. Levine, Nick and Pitman, Kent M. Common Lisp: Myths and Legends. 2010. Web. 8 Feb 2012. Petković, Miodrag. Famous Puzzles of Great Mathematicians. AMS Bookstore. pp. 197. 2009. Print. Weisstein, Eric W. "Tower of Hanoi." MathWorld--A Wolfram Web Resource. 2012. Web. 8 Feb 2012. Read More