I’m finally done with the basics of Lisp. But being able to finally understand how to use Lisp does not end there. It simply means that there will be more interesting problems to solve in the future and expectations will be high. For this entry, I will be discussing a few things about what I’ve learned about Lisp. I will also be posting source codes from the exercises that I answered and likewise the real-world implementations that I created using Lisp.
I’ve read almost a third of Paul Graham’s On Lisp Book and allow me to summarize it, based on my own pace and understanding, in a nutshell. I will only write important pointers that you might help you understand lisp better. The discussion on the syntax will already be up to you. Don’t worry though since I’ll be posting materials for your reference. 
Introduction:
Lisp stands for List Processor and was developed by John McCarthy in the late 1950s. The paradigm it follows is Functional Programming. That is, functions are the natural place to begin with. This type of paradigm tells you what it wants to do rather than what to do. Lisp allows you to change the language to suit the solution to the problem. Prototyping and debugging of programs are easier and more interactive. Arguments are also evaluated first before the function is issued since it follows the read, evaluate, and then print cycle. Lastly, Lisp can either be compiled, interpreted, or both. Examples of software created using Lisp are GNU Emacs, Autocad, and Interleaf.
There are a lot of dialects that you can use to program in Lisp. The most popular dialect is Common Lisp. But for the entirety of my Lisp entries, I shall be dealing with Common Lisp syntax unless otherwise stated. For the interpreters that you can use , refer to my previous entry which discusses on how to install the interpreters.
In Lisp, f(x) is written as (f x) since it is Postfix.
eg. cos(0) is written as (cos 0).
In Lisp, there are only 2 kinds of objects:
1. Atoms – symbols, arrays, and other data structures.
* symbols are represented as sequences of characters of reasonable length.
2. Lists – are recursively constructed from atoms. It may contain either atoms or lists, or both.
* “()” or “NIL” is both an atom and a list.
* special atoms: numbers, t, or nil.
* primitive functions: +, -, *, /, exp, expt, log, sqrt, sin, cos, tan, max, min.
Ingredients of an abstract data type:
1. Constructors – forms that create new instances of a data type.
i. cons – allows you to add a member to the front of a list
eg. (cons ‘a ‘(1 2 3)) -> (A 1 2 3)
ii. quote or ‘ – use if you do not wish the interpreter to evaluate.
eg. (setq a 4) = (set ‘a 4) = (set (quote a) 4)
*shorthand commands are called macros.
2. Selectors – returns one of its components, given a composite object out of several components.
i. first or car
eg. (first ‘(1 2 3)) -> 1
ii. rest or cdr
eg. (rest ‘(1 2 3)) -> (2 3)
3. Recognizers – expressions that test how an object is constructed.
Lists versus Sets:
1. Sets are unordered but lists are.
eg. (a b c) and (c b a) are two different lists.
2. An element either belongs to a set or not. There is no notion of multiple occurences. Yet, a list may
contain multiple occurences of the same element.
eg. (a b b c) is a list whilst (a b c) is a set.
Recursions:
1. Linear Recursion – the function may make at most one recursive call from any level of invocation.
eg. factorial.lisp
2. Multiple Recursion – the function definition contains two or more self references.
eg. fibonacci.lisp
3. Structural Recursion – the function checks the structure of the parameter.
eg. recursive-list-length.lisp
Tail Recursion means that when the result of each recursive call is returned right away as the value of the function.
* when implementing linearly recursive functions, you are encouraged to restructure it as a tail recursion after you have fully debugged your implementation.
The implementation of tail recursion is new to me since I don’t(or did not) really bother using this in the 2 years that I’ve been working as a developer. This may have been introduced in my Computer Science classes but was not really given that much attention. So I didn’t bother.
Iterators:
- in higher-order function, mapcar is used and does exactly what mapfirst is intended for.
- *car is used to define first in other dialects and rest was called *cdr in these dialects.
- Common Lisp still supports car and cdr but stick with the more readable first and rest.
Types of Iterators:
1. Generic Iterators – captures the generic logic of iterating through a list.
2. Transformation Iterators – transforming a list by systematically applying a list member that
satisfies a given condition.
eg. repeat-transformation.lisp
3. Filter Iteration – screening out all members that does not satisfy a given condition.
Compiling to executable:
Also, if you want your program to be executable within the commandline, you can issue this command:
(save-lisp-and-die “<executable_file_name>” :toplevel #’<function_name> :executable T)
eg. (save-lisp-and-die “javaphones” :toplevel #’main :executable T)
*please do note that I’m running on Ubuntu 9.04 and I haven’t tested it on other Linux distros.
So far those are the pointers written in my Rutter(Blue Notebook). You can download the resources via torrent or direct download (6.73MB). Also, you can join the mailing list at comp.lang.list. There’s a lot of spam there but there a few, great people who can help you in your Lisp endeavors.
Enjoy!
