Saturday, September 1, 2012

Common Lisp Tutorial preamble

Welcome to my Lisp tutorial. Just a while ago Lisp was a foreign language to me, and through study and determination (and a boatload of help from IRC users) I am finally started to get a grasp on the language. As a return to the Lisp community I will be writing the most extensive guide on this blog yet in a hope to teach Common Lisp to a complete newcomer to the language.

On IRC, many were in favor of using Common Lisp as a first programming language. I am in strong support of teaching FUNCTIONAL  programming as the first paradigm, but I am not in support of using Lisp for this purpose. For this reason the tutorial assumes a background in another programming language, but what that language is does not matter. If you know what the terms global variable, function (method), and structure mean then you are ready to learn Lisp.

How this guide will work
This will be a ten-part guide written as I learn the language. That means there could be gaps in the writing of the guide. The reason it is being written during the learning process is that common problems will arise, be solved, and then transcribed here for newcomers that encounter those same issues with the language. Here is a general outline (incomplete) for what the guide will shape up to be. Note that with my current knowledge of the language, I do not have the experience to write the entire guide yet but I will constantly update it as I learn new facets of the language.
  1. Setting up Lisp
  2. Functional Programming
  3. Data types in Lisp
  4. Writing Functions and recursion
  5. Common Functions
Here are some good Lisp resources if you do not want to read this guide or you feel that you need some backup.  - A book explaining in great detail how Lisp works, but less on how to use it. - A guide to procedural programming in Lisp. Great for reference and quick learning - Documentation for about every function Lisp has to offer, as provided by the creators of LispWorks - the most famous commercial lisp IDE. - The homepage for the book "Land of Lisp" - the most commonly recommended book regarding common Lisp and second only to SICP for Lisp altogether. I commend the book's creative use of educational artwork, but I disagree with using large examples and third party software (graphivz) to teach the reader a language.
Common Lisp Tutorial section 1 - In
stalling Lisp

The theories behind Lisp are mostly abstract. In fact, many are derived from Lambda calculus - a mathematical genre that is incredibly similar to programming. And you will learn in Chapter 7 that lambdas actually have a lot to do with Lisp. However, you will want to have Lisp installed so that you CAN muddle with the  concrete. On Linux the name of the common lisp package is clisp, so install it with your package manager. After it is installed you can start a clisp session directly from the command line with the command clisp.

Congratulations, you now have Lisp installed. But what is this, exactly? If you are familiar with an intepreted language you can start off by thinking of common lisp as an interpreter, but in reality it is not. Lisp is a functional language. Everything other than symbols and other special forms is a function. Instead of making an executable with a set line-by-line set of instructions, lisp functions are read and then executed. This is called the Read-eval print loop. It reads a statement, evaluates its value, prints the value, and then loops back to the read phase.

For extensive saved-program Lisp files we will be using GNU Emacs (preferably version 24 or any above version) and an inferior-lisp mode called Slime. On Debian-based systems, emacs and slime can be installed with this command: sudo apt-get install emacs slime. On Arch Linux slime is not a package, so the command would be: sudo pacman -S slime-cvs. For other distributions try both of these options before installing from the source. On Arch Linux, editing one of emacs's Lisp files was necessary, but on Debian it was not.  If you end up having to do so, follow the instructions that slime provides after installation. path-to-lisp should be /usr/bin/clisp. To start slime in emacs the command is M-x slime (alt+x slime). As an interpreter, slime is basically just clisp inside of emacs. Using clisp in a terminal will provide the best interpreting experience. Once you start writing larger programs, the slime interpreter is a good tool for testing whether or not a function works.

Slime provides tools for interacting with Lisp. Compilation, documentation queries, an integrated Clisp interpreter, and improved pretty-printing / indentation are just some of the perks of using slime with Emacs.

You will want to have clisp running for all of these tutorials since they will require evaluating Lisp code.


Common Lisp Tutorial section 2 - Functional Programming

Many languages are object-oriented and procedural, or procedural without being object oriented. This means that a program is just basically a script that input follows to reach output. In Common Lisp, the functional paradigm is used. Everything is a function that should work independanctly of any outside variables or adjustments. There should only be a small chunk of imperative code for a specific task and an underlying library of information.

For instance, take a problem where you are working with two numbers. You have to make a library to perform actions on these numbers. In a language such as Java you may make two variables with mutators, and then have functions that take no argument -- loading the global variables.

This goes against Lisp coding style. In Lisp, all variables that are not constants should be declared within the scope of a function, either as parameters or local variables. In fact, local variables should even be kept to a minimum. Function scopes should be small and problems should be split into many small parts.

When you are finished you will have a library to use with any other Lisp program, rather than some code working specifically for a purpose. This is the whole idea of functional programming.

In Lisp, almost everything is a function other than special forms (like defun), symbols, lists, and sequences. This can make for an odd way of ordering information. For instance, in Java (2 * (1 + 1)) is a valid statement. In Lisp, that statement would be written as (* 2 (+ 1 1)). What is really happpening is the multiplication functionis being called with two arguments, 2 and what + (with two arguments) returns. "Returns" does not actually apply to Lisp. In Lisp, what is returned is the last evaluated statement. A function with the body of "(+ 3 2)" automatically returns five. You will learn about this in the next chapter when data types are discussed.
Common Lisp Tutorial section 3 -- Data Types in Lisp

Lisp has two data types. Lists (made of atoms) and sequences. There are also objects and structures, but these are abstractions on the base Lisp language. Lists are just sets of data declared inside of parenthesis (and a ' if it is an anonymous list. This is discussed in "writing functions".). '(one two three four) is a list. '(1 2 3 4 5 6 7 8 9 10) is a list. (defparameter *gvar* '(1 2 3)) creates a global list named *gvar*. Lists are essential to Lisp, if you could not tell by the name Lisp (LISt Processing).

Lists are really cons cells made of two parts. One is the car, or the value of the current element, and the cdr, the next element of a list. When you think of Lists the idea of a linked list should come to mind. The functions (car) and (cdr) can be used to get the first time of the list or the rest of the list. Thanks to recursion this is all that is needed. To get the first item from the next element of the list, they could be nested: (car (cdr list)) or (cadr list). If you have not picked up on the calling convention for functions yet, it is (functionName arguments). There are no parenthesis involved in the calling of a function unless you are using a list.

Lists are supposed to end with Nil, but they do not have to. If a list does not end like it is supposed to, it becomes a dotted list since the last element usually refers to itself mistakingly. Nil is the Lisp equivalent of 0, false, null, and void. An empty list is a nil list. A false predicate (yes-or-no function) evaluates to nil.

This is literally all that you need to know to start writing some Lisp code. In the next chapter there will be a lot of writing code, so fire up your REPL.


Common Lisp Tutorial section 4 -- Writing Functions

The ability to write functions is essential in Lisp since functions are EVERYTHING in Lisp. There is a special form called defun that can do just this. Defun takes as an argument the name of a function, the list of arguments, and then the body of the function. Here is an example:
(defun square (x) (* x x))
This function squares a number. The ( in the beginning starts the function, and then defun makes the function "square" that takes argument "x" with a body that evaluates the product of x times x. Now you can call (square 5) at the REPL and have the answer piped back to you. Let's write another function that takes two parameters. x and ty. Ty will specify whether to do multiplication or addition on the numbers using the if macro.
(defun square (x ty) (if (equal ty 0) (* x x)
                                        (+ x x)))
This compares ty to 0, the multiplication code, and if it is 0 returns the product. If it is not, it returns the sum. Now we can write a function that works with lists now that we know how functions in lisp work. Remember that car gets the first element of a list and cdr gets the remainder of the list. You will also need to know that an empty list or a nonexistant atom evaluates to nill. This can be checked with the null function and handled with the if function. Also know that cons is used to add an element to the list. To cons onto a list is to add an item. (cons 'foo '(bar)) would create the list '(foo bar).

(defun multList (x) (if (null x) nil (cons (* (car x) 2) (multList (cdr x)))))
This is a confusing function so we will deconstruct it part-by-part. This is a function that takes x as a parameter. Then, it checks if x (the list) is nil, or empty. If it is, it returns nil. Remember when I said that lists should end in nil? This is why.
If x is NOT null, then the first element of the list is multiplied by two and put onto a list with every other element of the list that has already been added by two. How does this work? Recursion with cdr. multList is called with the entire list minus the first element, and this will happen all the way until nil is returned and consed onto the end of the list. In the meanwhile a list is built and returned to where multlist is called on the top-level of the recursion path. Here is how to visualize this function:
Although the cons train starts in the top-case, it starts building from the bottom and conses to the top, forming the list with car X. They are joined because the first element of the list is joined to the function that does the same to the second, and so fourth. Recursion is a hard concept to grasp since so much code executes that is not shown. Just remember to always have the base case (the nil case) return nil when you are consing, or (car x) when doing something like addition.

Now that you have seen how recursion works, why not a function that adds a list together? This could be used for a mean function or standard deviation. Here is the implementation:
 (defun addall (x) (if (null (cdr x)) (car x) (+ (car x) (addall (cdr x)))))
This works much the same as the next one. Here is the deconstruction:
is the NEXT x null? Return this one
If it's not, add this one to the sum of the next one and the one after that until the above case happens. Here is what happens when you call (addall '(1 2 3 4 5 6))

Recursion, although a hard subject to grasp, is very powerful when compared with iteration. We are able to accomplish a lot with a very small amount of code at the expense of a bit of memory thanks to those waiting cars and any local variables that are continually created. 

If you want to actually set data instead of making it, (setf) can do this. In fact, Lisp works with references often. (setf (car x) 'value) actually works. It is bad practice to modify a parameter in most cases, so use setf carefully.

Common Lisp Tutorial section 5 -- Common functions
Here are my notes on Lisp functions. The hyperspec is also a good place to learn about functions.
let - Declare local variables
flet - Declare local functions
labels - Allows recursive functions

cons - Concatenate
car - Get an item out of the first cons cell
cdr - Get it out of the second slot OR REST OF THE LIST

() - nil, or false
oddp - Is the number odd?

progn - Kind of like if with braces {} INSIDE an if.
when - Like if{}
unless - Like if(!){}

eq - Short equals. Should only be used to compare symbols
equal - Should be used to compare anything else
eql - Compares like eq smartly
equalp - Compares smartly

cond - Many ifs. cond( (condition) (stuff)). Can use progn.
setf - Set something to a value.

case - Check against a value. EX: (case person ((henry) (do-stff))(otherwise (more-stff)))

and - If all evaluated to true. Stops evaluating at first false. (last part important)
or - If at least one evaluated to false

member - Is x a member of a list? EX: (member 1'(3 1 4)) T

find-if - Takes a function and a list. Returns the first list member where the function returns true. ex: (find-if #'oddp '(2 4 5 6)) 5

((garden (you are in the garden)) is an association list. (assoc 'garden *var*) will return that list.

` - Calculate somethin in data mode
, - The things to flop

mapcar - Takes a function and a list and applies the function to every member of the list.
append - Combine lists into a single list
apply - Apply function to every list
find - Search a list for a value, then return that value
push - Add something to the front of a list.
print - Same as System.out.println()
print1 - Same as Systyem.out.print()
read - Get user input
|| - Makes case-sensitive information
princ - Human readable print
read-line - Take in an entirel ine
eval - Execute code
concatenate - Concatenate things together.
coerce - Make a list of characters from a string
lambda - Same as defun but with no name
graphviz - Tool to create graphs
substitute-if - Replaces values based on conditions
loop - Execute code for a while (iteration)
with-open-file (stream) - Opens file
: - Make a constant
maplist - Recursive mapcar
load - Load a library
random - Make a random number less than the integer passed into it
set-difference - An item is in one list but not in another
intersection - Which items are shared by lists
remove-duplicates - Remove items from a list

make-array - Define a new array with an integer for the number of members
aref - Get the item from the index of an array
setf with aref can set arrays
> (setf (second foo) 'z) actually manipulates the list
make-hash-table - Makes a hash table
(gethash - Gets fromt a hastable. (get 'y from hastable x))
> (setf (gethash 'yup x) '25) sets values in a hash table
values - Return multiple values
multiple-value-bind - Bind multiple values from a function. EX: (multiple-value-bind (a b) (foo)

defstruct - Make a structure. First argument is the name of the struct, the rest are the instance variables.
make-* - Used with a struct. Then the instance variables are set with :.
*-* - Used with structs. strct-variable *instance*
count - Get the number of times #\x appears in a word
position - Get the position of #\x in a word
some - If some x are true.
every - if everything in the list is true.
reduce - Do something for every member of a list recursively

subseq - Get a subsequence with two points
sort - Sort with a function that returned something. EX: (sort '(1 2 3) #'<)
defmethod - Used for overloading (defmethod add ((a number) (b number))
dotimes - Repeat code a number of times.
return - break from a loop

error - Something went haywire

This is all that you need to know to understand lisp. The rest lies with extra research and understanding what functions do. Good luck with your lisping, and remember - You are BETTER than procedural languages.

No comments:

Post a Comment