Showing posts with label lisp. Show all posts
Showing posts with label lisp. Show all posts

Saturday, March 24, 2012

CLISP cheatsheet

A quick-'n'-dirty crib sheet of the GNU Common Lisp programming language, a pragmatical non-minimalist LISP implementation. This is limited to the contents of the wonderful introductory book Land of Lisp and some of the information is paraphrased from this book. Therefore this page is meant to complement the book, since it lacks a reference of the commands, which are introduced in a scattered way.

Integrated development environment


To learn the language, using the REPL or executing Lisp programs saved in text files on the command line is enough. As for documentation, begin with using this simplified reference if the full official standard seems too much stuff for a newbie. Anyway, as you write more and more complex and long Lisp programs, you may find inconvenient and slow to have to continually save a whole Lisp file in your editor of choice and then run it with the Lisp interpreter. Lisp is dynamic in nature and allows you to make a modification to a program and test it immediately. You can even redefine a form!

If you already use the Emacs editor, go for Slime. If you know the VIM editor well there is Slime clone for it called Slimv. If you know neither Emacs nor VIM, I recommend Geany along with the handy LispEdit plugin.

I personally use both Geany and Slimv because I already know VIM and am too lazy to learn another editor like Emacs well. I maintain the Slimv Arch Linux package too. Here is a very useful Slimv tutorial. And a table of Slimv main keyboard shortcuts to get you started in no time:

command action
,c Connect to LISP and show the REPL
<Ctrl-w>w switch between the REPL window and the source code window
,s Describe the symbol under cursor, just like (describe 'symbol)
,h look up the symbol under cursor in the Common Lisp Hyperspec
,d Evaluate the current top-level form
,e Evaluate the current form
,g Set the current package by entering its name
= Indent selected forms
,W or ,w( Wrap current symbol or form inside parens. ,w" for wrapping it in double quotes.
,S Removes outer pair of parens from current symbol or form
,O Splits current string/form into two
,J Joins the two string/form to the left and to the right into one
,> or ,< Move parens to the Right or Left
,F Compile the file
,L Compile and load
,i Like (inspect 'symbol), symbol is the current symbol under the cursor by default
,1 Expand current macro, just like macroexpand-1
,t Toggle tracing for the function name under the cursor, just like (trace function)
,T Untrace all traced functions
Shortcuts available when debugging is activated:
command action
,a Abort restart
,a or ,q or ,n Abort or Quit or Continue restart

If you are confused about the concepts of packages, systems, modules as they apply to Lisp, read this explanation.

conventions and best practices


Naming conventions: functions that return nil or a truth value are called predicates and have a 'p' appended to the end of their name.

Avoid using any function that ends in not. They are considered deprecated and may be removed from future versions in the ANSI Common Lisp standard.

To describe a computation you don't want to run until later (a delayed computation), create a nullary function, that is a function that has zero arguments aka a thunk or a suspension:

(lambda () ...)

E.g. to ease debugging you may want to output to the console, even if output should be directed to a file on disk, the network, etc. You can then wrap the output stuff as a thunk and pass it to another function that calls the thunk, captures the results and sends them to another location (e.g. a file).

read-eval-print loop (REPL)


$ clisp
:q
(quit)

basic data types and operators


Both data and code in Lisp is represented with syntax expressions. In this format, data is represented using nested lists, often with Lisp symbols at the front of each list explaining the structure of the data.

symbols (case-insensitive): any combination of letters, numbers and + - / * = < > ? ! _. Indeed any character othen than ( ) # ' ` whitespace is permitted in a symbol, provided that a symbol does not take the form of a number
symbols (case-sensitive): ditto, but surrounded by vertical pipes. E.g. |Hello!|

keyword symbols: :symbol
A colon-prepended symbol always means itself. It is a constant that evaluates to itself. E.g. used for keyword parameters. Use a keyword symbol every time you know a symbol just has a meaning in its own right.

cons-cell (or "pair"): (cons slot1 slot2) or '(slot1 . slot2)
A pair is a dotted list consisting of two elements only, that is of length two. E.g. useful to store the x- and y-coordinates of a point or a key/value.

lists: (elem1 ... elemn) or (cons elem1 (... (cons elemn ())...) or (list elem1 ... elemn)
List recursive definition: a list is either empty, that is () or nil or a cons whose car is the first element of the list and whose cdr is a list containing the rest of the elements.
elements can be of any Lisp datatype. This implies that the right slot in the last cons cell in a list must contains a nil. E.g. a list of characters is defined as: '(#\! #\? #\.)
This is just a shortcut for creating and display a list, but it always remains a chain of cons cells.

dotted lists: (cons elem1 (... (cons elemn-1 elemn)...) or '(elem1 . (... (elemn-1 . elemn)...)
They are lists that end in something other than a nil. Both dotted and proper list can be created using the dot notation as well, although the bracket syntax for lists is the simplest.

circular lists: they are lists where the last cons cell points to an earlier cons cell in the same list.
This is required for CLISP to be able to print self-referential data structures without getting into an infinite loop:
(setf *print-circle* t)

(defparameter list '(1 2 3))
(setf (cdddr foo) foo)
output: #1=(1 2 3 . #1#)

form: (command arg1 ... argn)
Before the function command is evaluated, all the expressions after the function name are evaluated.

empty command, return nil: ()

fractions: signed-int-numer/int-denom

strings: "Hello \"World\""
Note: storing text as a list of symbols instead of a string often makes it easier to manipulate. But beware of commas, since they are unsupported in symbols. A solution to represent them would be to just fall back on using text strings, e.g. '("Welcome," visitor) and then strip the quotation mark afterwards when processing.

characters: #\a
Literal characters are prefixed by the symbol #\. Special literals are defined for nonvisible chars. E.g. #\newline, #\tab, and #\space.

data mode: 'data or (quote data)
data should be a piece of code you want to treat as data

quasiquoting: `...data...,(command ...)...
This facility allows you to build a piece of data out of function results and some static data, by interpolating command results. E.g. it is a handy way to insert small bits of computer code into larger pieces of data.

nil is a constant that evaluates to itself

boolean values: any empty list '() () 'nil nil is false
everything else is true, including the pre-defined constant t (or T)

#'fun or (function fun)
function operator. Just a shorthand for the function operator. In CLISP must be used to pass a function as argument to another function. Its purpose is to avoid conflicts between the function name and possible variables named the same way. Common Lisp tracks function names differently from variable names. It has multiple namespaces, including one for variables and one for functions. Conversely Scheme has only one namespace for both functions and variables.

(coerce arg 'type)
E.g. to convert a string to a list of chars: (coerce "hullo" 'list) -> (#\h #\u #\l #\l #\o)
to convert a list to an array: (coerce '(one two three) 'array) -> #(ONE TWO THREE)

(lambda (optional args) body)
Define an anonymous function and returns it as a value. There's no need to give the function a name. Note lambda itself is not actually a true function. It is a macro since not all its parameters of the lambda command are evaluated before the function itself is evaluated. The lambda macro allows you to package up an ad hoc function and pass it off to another function of your program that accepts functions as parameters. This technique is called high-order functional programming.

#(elem0 elemn-1)
Zero-based array

#S(HASH-TABLE :TEST FASTHASH-EQL (key1 . value1) (key2 . value2))
Hash table. :TEST specifies the function used to test the equality of keys. Use EQUAL if you want string and not symbol to be the key type. For case-insensitive string hashing use EQUALP.

(type-of expr)
Finds the type of any Lisp value.

t
Although all non-nil values are considered true, by convention the constant t is usually used to represent truth.

globals


redefinable: (defparameter *var* val optional-documentation-string)
non-redefinable: (defvar *var* val)

earmuffs *...* are optional but recommended

cell/list manipulation forms


add elem to the front: (cons elem list)
first elem/slot: (car cell) or (first cell)
car is an old name for first. The name stands for "Contents of the Address Register" the instruction that was used to implement car on the IBM 704, the computer where Lisp was first implemented.

rest/second slot: (cdr cell) or (rest cell)
cdr = Contents of the Decrement Register

(cadr list) or (car (cdr (list)) or (second list)
(cdar list) or (cdr (car (list))
(cadadr list) or (car (cdr (car (cdr list)))) etc.
up to four levels deep all car/cdr combinations are pre-defined
functions to directly access single elements are defined from first to tenth

(last list n)
Returns a list of the last n elements of list, where n defaults to 1.

(nth unsigned-int-index list)
Zero-base indexing on lists. Warning: slow on large lists, use arrays and the aref function instead.

(length sequence)
(list-length list) is a bit faster but only works on lists.

(append list1 ... listn)
Joins lists.

(push item list) or (setf list (cons item list))
Adds item in front of a list variable. Modifies and returns the new list variable.

(pushnew item list)
Same as push, but item is added only if does not already exists in the the list variable.

(find item list :key #'func)
Searches list for item and returns the element that contains item or nil if not found. Optionally you can provide a special keyword parameter named :key to indicate the location where to find key values to compare item with. E.g.: (find 4 '((1 2) (3 4)) :key #'cadr) returns (3 4)

(member elem list)
Returns the tail of the list starting with elem or nil. elem can be nil, since the LISP list recursive definition allows nil values everywhere in a list, not only at the end. elem can be of any Lisp datatype, of course.

(find-if #'func sequence)
High-order function. Returns the first value in the sequence for which func returns true or nil, that is finds the first value that satisfies a predicate. There is no way to find a nil value in list: using null as func, nil is returned both if a nil value is present and not present in list.

(mapcar #'func list)
High-order function. Applies func to every member of list and returns the list of results. Same as map in Scheme.

(mapcar #'func list1 ... listn)
If three or more arguments are passed to mapcar, #'func should be an n-ary function, which will be applied to corresponding elements of the lists list1 ... listn, until the shortest list is exhausted.

(maplist #'func list)
High-order function. This is like the mapcar function, except that the function inside it (func) receives the entire remainder of the list, not just the current item in the list. The first call of func receives the entire list, the second the cdr, the third the cddr, and so on till the last call which receives a list comprising the last element of the list only.

(mapc #'func list)
High-order function. Applies fun to every member of list. More efficient than mapcar in that it does not return the transformed list but the original list. Anyway func can actually do something with every element of the list, e.g. producing some side-effects like outputting the value. In other words, use mapc in places where you care only about the side effects and don't care about generating a final list as a result.

(mapcan #'func list)
Variant of mapcar. It assumes that the values generated by the mapping function #'func are all lists that should be appended together. This is useful when there isn't a one-to-one relationship between the items in a list and the result you want to generate.

(apply #'func list)
High-order function. Invokes func passing each element of list as the function arguments. A maximum of 4096 arguments are supported (this is the value of the global predefinite constant call-arguments-limit). E.g.:

(apply #'append '((one two) (three four))) evaluates to (ONE TWO THREE FOUR)
just like (append '(one two) '(three four))
while
(append '((one two) (three four))) remains the same list: ((ONE TWO) (THREE FOUR))

(funcall func arg1 ... argn)
Calls func with arguments arg1 ... argn. Useful when the name of the function to call is in a variable.

(remove-if-not #'func list)
High-order function. Removes all things from a list for which a passed-in function doesn't return true. Essentially, it returns a filtered list of objects consisting of those items for which func is true.

(set-difference list1 list2)
Returns all items that are in list1 but not list2, in the order they appear in list1 that is it preserves order.

(intersection list1 list2)
Returns all items shared between list1 and list2, nil if none.

forms for abstraction and combination


function def: (defun function_name (optional arguments) "optional documentation string" body)
The last expression is returned as the value of the function call. User functions can be redefined at runtime in Lisp, just like variable values can be changed. Redefining predefined functions works as well, but makes CLISP to issue a warning message.

overloaded statically-typed function def: (defmethod function_name ((arg1 type1) ... (argn typen)) body)
The defmethod function is like defun, except that it allows us to write multiple functions with the same name. When using defmethod, we can explicitly state the type of each parameter in the function's argument list so that Lisp can use these type declarations to figure out the correct version to call for each situation.

returning multiple values: (values expr1 ... exprn) or just return a list (slower)
first value expr1 will be used by default during follow-up calculations, expr2 to exprn will be ignored unless you bind them to variables using: (multiple-value-bind (var1 ... varn) expr-returning-multiple-values body) body means there is an implicit progn

local vars: (let ((var1 val1) ...(varn varn)) body)
Each var will be a lexical, local variable but if a dynamic variable already exists with the same name, let will instead, temporarily, override the value of the dynamic variable to the new value. You may find annoying that you need a parenthesis around each bind when giving the starting value. This syntax has been chosen to group variables and values better visually. It also allow you to omit nil when you want to define a variable but not initialize it. E.g. (let ((var1) (var2 value2)) ...) is equivalent to (let ((var1 nil) (var2 value2)) ...).
(let* ((var1 val1) ...(varn varn)) body)
Same as let but allows you to refer to previously defined variables when assigning the value of a subsequent variable.

local functions: (flet ((fun1 (arg1) body1) (fun2 (arg2) body2)) body)
local functions that can call themselves: (labels ((fun1 (arg1) body1) ... (funn (argn) bodyn)) body)
list def: (list elem1 ... elemn)

code block: (progn expr1 .. exprn)
Evaluates all arguments but returns only the value of the last one as the value of the full expression. Not to abuse in a functional programming style.

(eval data)
Evaluates LISP data as code. Allows to write a program with self-modifying code. Not to be misused or be used instead of macros. Since eval allows you to call any Lisp command, for security do not trust and double check any data read from external sources you don't trust that are going to be evaluated.

(concatenate 'datatype expr1 .. exprn)
Concatenates strings or other types of sequences.
E.g. (concatenate 'string "Hello " "World") returns "Hello World"
(concatenate 'list '(1 2) '(3 4)) produces (1 2 3 4)

forms that produce side-effects


(setq var value)
Set Quantity. setq can assign only to variables. In the majority of cases, the special evaluation of a generalized-reference isn't needed, so you're probably slightly better off (in terms of performance) by using setq. If you get it wrong, LISP will kindly remind you, so you can then still use setf instead when required.

(setf generalized-reference value)
setf (set field) supports generic setters. generalized-reference can not only be a variable. It can be any code for pulling a value out of a data structure (whether an array, list, string, or something else) that can be used for putting data into the same structure. setf is a macro which builds on setq.

(incf generalized-reference inc-number)
inc-number defaults to 1

(decf generalized-reference dec-number)
Variant of setf that subtracts an amount dec-number from the variable generalized-reference. dec-number defaults to 1

To decrement/increment use the built-in "+" or "-" functions, or their shorthand "1+" or "1-", if you just want to use the result, without modifying the original number (the argument). If you do want to modify the original place (containing a number), then use the built-in "incf" or "decf" functions.

forms for flow control (conditionals)


(if cond then-expr optional-else-expr)
The optional-else-expr defaults to nil.
It's a special form in that only one of the expressions after the if is actually evaluated.

(when cond expr1 ... exprn) or (if cond (progn expr1 ... exprn))
Does nothing and returns nil if cond is false

(unless cond expr1 ... exprn) or (if (not cond) (progn expr1 ... exprn))
Does nothing and returns nil if cond is true

(cond (cond1 expr11 ... expr1n) ... (condn exprn1 ... exprnn) (t def-expr1 ... def-exprn))
Conditions are checked in the order cond1 ... condn. An optional special condition t (for true) can provide a default case.

(case expr ((expr1) expr11 ... expr1n) ... ((exprn) exprn1 exprnn) ... (otherwise def-expr1 ... def-exprn))
It could be more efficient but it is limited to eq for comparisons. Therefore it can usually used only for branching on symbol values.

(dolist (var list result) ...)
Executes the body once for each element in list, with var bound to the element. Returns nil if there is no result form, otherwise evaluates and returns the value of this form.

(do ((var1 val1 update1) ...(varn valn updaten)) (termination-predicate [return-value]) ...)
Binds var1 ... varn to their initial value val1 ... valn respectively. If termination-predicate is false, execute body and update var1 ... varn by executing update1 ... updaten respectively and loop again; when termination-predicate becomes true, return the value of return-value.

(loop ...)

This is a very powerful and flexible macro for all your looping needs. It's parameters or tokens are interpreted as a small language. You can use almost any meaningful combination of the following clauses:

expr1 ... exprn
Loops forever. You'll need to hit CTRL-C and type :a to get out of the infinite loop.

repeat number
Loops number times

for n [from number1] [below/to number2]
Declares a variable n that iterates through a range of values, namely from number1 (0 by default), incrementing n by 1 until n <= number2 (to) or n < number2 (below. number2 is infinity by default.
Use it in case you need to keep a running count as you're looping. You can use more than one for clause: variables are incremented in parallel. The loop will stop when any one of the clauses runs out of values.

for n in list
Iterates through values in list.

when (predicate)
Runs the following part of the loop only under the condition predicate

return expr
Breaks out of a loop and returns expr

sum expr
Adds together all values of expr and makes the loop return that number

collect expr
Collects the values of expr into a list that returns

do expr1 ... exprn
Executes arbitrary expressions inside the loop

Some good examples are here: http://www.unixuser.org/~euske/doc/cl/loop.html

boolean forms


(and expr1 ... exprn)
Returns exprn if all expressions evaluate to true, else nil. Stops evaluation at the first false expression.

(or expr1 ... exprn)

CLisp uses shortcut Boolean evaluation. This allows one to use boolean forms as some kind of conditionals. E.g.:

(if cond1 (if cond2 expr)) or (and cond1 cond2 expr) or, clearer but not so short: (if (and cond1 cond2) expr)

(complement #'func)
High-order function. Creates the opposite (or complement) function to func.

comparing forms


Rule of thumb: use eq for comparing symbols because it's faster, equal for everything else.

(eq sym1 sym2)
Compares symbols for equality. Preferable to equal when comparing symbols.

(equal thing1 thing2)
Compares two things for isomorphism, meaning they "look the same". It works for any datatype: symbols, lists, integers, floating point numbers, strings, characters.

(eql thing1 thing2)
Compares symbols, numbers and characters for equality.

(= number1 number2)
Same as equal, but limited to numbers.

(string= string1 string2)
Same as equal, but limited to strings.

(string-equal string1 string2)
Same as string= but differences in case are ignored.

(char-equal char1 char2)
Same as equal, but limited to chars.

(equalp thing1 thing2)
Same as equal, but loose comparison: case-insensitive for strings, same value for intergers and floating-point numbers.

(null expr)
Returns true for any of the nil values: () '() nil 'nil. False otherwise.

(zerop number)
Returns true if number has the value 0, nil otherwise

(numberp expr)
Check whether expr is a number

(consp expr)
Check whether expr is of type cons

(arrayp expr)
(characterp expr)
(consp expr)
(functionp expr)
(hash-table-p expr)
(listp expr)
(stringp expr)
(symbolp expr)

math forms


basic operators: + - / *
increment: (1+ num)
decrement: (1- num)

arithmetic shift: (ash signed-int signed-int-position)
Positive positions shift to the left, negative ones to the right

exponentiation: (expt num-base num-exponent)
(oddp signed-int)
(evenp signed-int)
random integer in the interval [0..num), that is from 0 to n-1: (random num)
round off numbers: (round number) returns both the integer part and the remainder
(max expr1 ... exprn)
(min expr1 ... exprn)
(truncate expr)

I/O forms


Some of these functions can accept a stream as an optional parameter. In this case, these printing functions won't print anything to the console, but instead will print to the stream object.

For computers


(print arg stream)
Prints objects in such a way that they can always be "read" back into their internal representation. Therefore it can't be used to generate any arbitrary bit of text. Use princ for that. It starts a newline before printing arg and places a space character at the end of the printed value. LISP code is printed just as it is, e.g. strings are printed with double quotes but functions cannot be printed. Symbols are printed in all caps. Put an explicit quote on the front of a symbol to not get it mixed up with functions of the same name.

(prin1 arg stream)
Same as print but it only prints arg, no newlines or spaces. The 1 means will stay on a single line.

(prin1-to-string arg)
Same as prin1 but doesn't dump the result to the screen, just returns it as a string. E.g. it can be used for converting a list into a string:
(prin1-to-string '(1 2)) yields "(1 2)"
prin1-to-string acts like write-to-string with :escape t, that is, escape characters are written where appropriate

(write-to-string arg :keyword_parameter value...)
It is the general output function. It has the ability to specify all the parameters applicable to the printing of object. E.g. :pretty nil tells Lisp not to alter the string to make it pretty. Without this, Lisp would place new lines or tabs into our converted string to make it look more pleasing to the eye.

(read stream)
Reads LISP code from stream (by default stdin). E.g. the user will have to type quotes around a string. Security: beware that the user can use reader macros to execute a command by inputting #.{command}

(read-from-string string)
Just like (read) but reads a syntax expression (or any other basic Lisp datatype) from string instead of directly from the console.

For humans


(princ arg stream)
Prints any LISP data. E.g. strings are printed without double quotes, characters in their raw form, etc. Symbols are capitalized.

(read-line stream)
Returns all the text entered until the ENTER key is pressed as a string on the console or a newline is encountered on another kind of stream.

(fresh-line stream)
Makes sure that the next item appearing on the screen/stream will start on a fresh line.

(princ-to-string arg)
princ-to-string acts like write-to-string with :escape nil :readably nil. Thus no escape characters are written.

Streams


Example of opening a file for writing. It creates a locally-scoped (lexical) stream variable my-stream and connects it to an output file (use :if-exists error to prevent overwriting; use :direction :input for the opposite behaviour):

(with-open-file (my-stream
"filename.txt"
:direction :output
:if-exists :supersede)
....body has my-stream defined...))

Use one of the default streams (special global variables) as my-stream to redirect output:

*standard-output*

string functions


(string-trim charliststring string)
Strip some characters from the beginning and end of a string (not the middle).

(string-upcase string)

generic functions


Generic functions can accept multiple datatypes as parameters and handle them appropriately.
E.g. sequences are either lists, strings or vectors (arrays), the three main ways of sequencing objects in Lisp. String components are characters, lists or array ones are elements.

(substitute-if value #'func sequence)
Substitutes each occurrence of value in sequence based on the result of the test func.

(subseq seq start-index end-index)
Returns a subsequence of seq from start-index (included, 0-based) to end-index (not included). If end-index is omitted, it defaults to the sequence length.
E.g. subseq can be used to extract substrings: (subseq "I don't believe it" 2 7) returns "don't"

(remove-duplicates sequence :keyword_parameter value...)
Removes duplicate items from a sequence. By default it uses the eql function to check for equality. Use the :test keyword parameter to choose a different test function.

(some #'func sequence)
Returns the first non-nil value which is returned by an invocation of the predicate #'func. If the end of a sequence is reached without any invocation of the predicate returning true, some returns nil (that is false). Thus, some returns true if and only if some invocation of predicate returns true, that is if any items in sequence satisfy the predicate #'func.

(every #'func sequence)
See if every value in sequence obeys a specific predicate #'func.

(reduce #'func sequence :keyword_parameter value...)
Iterates through a sequence and distills it down into a single result. The first number in the list we're reducing will be used as a starting value, since #'func must be a dyadic operator. If this is a problem, we can instead pass an explicit initial value to the reduce function by passing in a keyword parameter named :initial-value.

(reverse sequence)

(map type #'func sequence)
Identical in behavior to mapcar, but works on all sequence types, not just lists. You specify the type of sequence to return from the mapping by passing an extra argument type

(sort sequence #'func)
Sorts a sequence according to the binary predicate #'func

character functions


(char-upcase char)
(char-downcase char)

(digit-char-p char)
Tells us if a character is a numerical digit

(alphanumericp char)
Tells us if a character is alphanumeric

(count elem sequence)
Finds out how often a certain object elem appears in sequence.

(position elem sequence)
Tells you where an item elem is located in sequence, starting the count from zero (zero-based index).

Association lists (alists)


Alists are lists of pairs. They can be used to store data that is in the form of keys associated with values, when you want to lookup a key and find the information associated with that key.

Drawback: not very efficient. Use only for very short lists (under a dozen items), else use real hash tables.

((key1 ...) ... (keyn ...))
... is a value, any data type. By convention, if a key appears multiple times in the list, it is assumed that the first appearance of the key contains the desired value.

((key1 . value1) ... (keyn . valuen))
Alternative definition of an alist as a list of pairs instead of a list of lists. assoc works with both definitions.

(assoc key alist)
Searches alist from the beginning for the first occurrence of the desired key. Returns a list/pair like (key ...) or (key . value) if key is found - that is it returns both the key and the value from the alist, nil otherwise.

(push item alist)
A common tecnique to replace a value from an alist is to push new items onto the list since only
the most recent value will be reported by the assoc function. This also maintains a history of all old values.

Arrays


The Common Lisp array is very similar to a list. The main advantage of using
arrays is that they require only a constant amount of time to access a value at
any specific location. Array indexing is zero-based as in C.

(make-array unsigned-int-dimension :keyword_parameter value)
Creates and returns an array of specified length, filled with nils, unless the :initial-content list parameter is used.

(aref array-var index)
Gets the index-th element out of array-var.

(setf (aref array-var index) val)
Sets the index-th element of array-var to val

Hash tables


Like alists, hash tables store items using a lookup key and a value, but more efficiently. Anyway, alist remain more efficient for small tables.

(make-hash-table)
Creates a new empty hash table

(gethash key hash-table)
Get a value out of hash-table. Actually returns two values: the first returned value is the actual value stored in the hash table or nil, and the second indicates whether the key was found in the table (nil or t)

(setf (gethash key hash-table) val)
Store val into hash-table with a lookup key of key

Structures


Structures encode objects with multiple properties, typically data that needs to be mutable. They can be simulated using lists, but this approach requires writing more code, is less readable and slower when you change the state of the objects. You have to depend on order to interpret property values and there is no type attached, unless you add one.

Thanks to the print/read symmetry in Lisp, you can create a structure directly from the printed representation of a structure:

#S(TYPE :PROPERTY1 value1 ... :PROPERTYN valuen)

but TYPE must be previously defined using:

(defstruct type property1 ... propertyn)

property can be a field name or a list (field-name expr), where expr is a form that will be evaluated when a new structure of type type is created and returns a default value for that slot.
type can be a type name of a list (type-name (:include parent-struct-type-name)) to include all the fields of another structure.

defstruct also defines a special function for creating instances:

(make-type :property1 value1 ... :propertyn valuen)

and a bunch of accessors/setters (usable with setf):

(type-property1 struct-var)
...
(type-propertyn struct-var)


Debugging


(trace func1 ... funcn)
(untrace func1 ... funcn)
Special forms to turn off and on tracing for func1 ... funcn. Tracing information will be printed if and when the functions are called.

(ed 'function-name)
Opens the default editor to interactively edit function-name definition. This function must already be defined before.

Profiling


(time expr)
Prints various timing data and other information to trace output, such as elapsed real time, machine run time, and storage management statistics

(dotimes (var number) body)
Run a chunk of code (body) number times.


Working with sockets

CLISP has its own socket library, but it is not standard. For more portatibility, I recommed using the USOCKET library.  Here is how the manual simulation of a TCP/IP client-server socket connection, using two REPLs:

ON THE SERVER

; Install, load and import the usocket library
(ql:quickload :usocket)
(use-package :usocket)

(defvar server-socket (socket-listen "localhost" 4321))

(class-of server-socket)

; This blocks, waiting for connections
(defvar connected-socket (socket-accept server-socket))

(class-of connected-socket)
(defvar connection-stream (socket-stream connected-socket))

(read connection-stream)

(print "Ave Client!" connection-stream)
(force-output connection-stream)

; This frees port 4321
(socket-close server-socket)

ON THE CLIENT

(ql:quickload :usocket)
(use-package :usocket)

; Create a connection to localhost or #(127 0 0 1)
; Replace with your server host name or IP address, if you have two machines.
(defvar client-socket (socket-connect "localhost" 4321))
(class-of client-socket)

; Convert the socket to a stream so we can easily read from it or write to it.
(defvar connection-stream (socket-stream client-socket))
(class-of connection-stream)

(print "Ave Server!" connection-stream)

; Output is buffered for efficiency reasons! this forces it to be sent.
(force-output connection-stream)

; This blocks until data are available or the connection drops
(read connection-stream)

; This flushes connection-stream too.
(socket-close client-socket)

Monday, March 19, 2012

HTML generation: templates, DSL and embedded scripts compared

Most web sites aren't 100% dynamic like Gmail or Facebook, even in this Web 2.0 era. There is usually one person who writes the HTML+CSS code and, if needed, a bit of client-side code (JavaScript), but he often uses WYSIWYG tools and is not a good programmer. Then another dude, a specialized programmer and data base expert, adds the server side code where it is needed.

PHP fits this division of labour nicely by providing a tag to embed PHP code directly into HTML.

It works, but it's an unreadable mess, quite hard to maintain, especially because of the verboseness of HTML. To address this problem, a lot of template systems have been developed for PHP, in an attempt to separate the HTML from the PHP code. Instead of inventing a new template language and writing a parser and an interpreter/compiler for it, the most flexible template kits just use PHP itself as a template language!

The PHP template file is just require-d or include-d by the PHP script that implements the page business logic. Such PHP templates are editable by webmasters using WYSIYWG HTML editors in a way that allows them to change most presentational details without screwing up any code.

E.g. in a typical PHP-based template you will find HTML code interrupted by <?php ?> sections that either print out values of variables, define a loop or choose HTML code to print conditionally, usually no more than that. Most WYSIYWG HTML editors display them using small icons, as they were external objects embedded into HTML. All that a webmaster has to take care of is, for instance, make sure that all PHP code sections that print values in a loop are put inside the two outer sections that define the loop itself. Any surrounding HTML code can be changed at will.

There are some disadvantages of using templates, though: they are slower and use more central memory when processed on each request. Caching can help ease this drawback, but for highly dynamic resources is not always easy and effective.

E.g. if you are formatting a big table with some frequently-changing data pulled out from a database, you will need to store them all in memory, then pass this structure to a template engine, which will send the generated HTML page to the web server, either at one bound or, if you're lucky, piecewise, but, you still need to keep all your data in memory, if not the HTML code too.

You can't pass a row at a time as soon as it is returned by the database from the business to the presentational logic. In order to do that you would need to run these two layers as separate processes or threads, but then you have to face the complicated issue of process/thread synchronization as well as buffer the data exchanged. It is so overkill that I do not know of any "scalable" template engine that uses multi-processing or multi-threading. In simple cases, which are the majority, it would be slower than single-process template systems.

This is a scenario where templates don't scale. If you were using PHP embedded into HTML, the output could be flushed more often, virtually after each row is printed, and, in the case of a slow database or overloaded server, the user does not have to wait for the whole page to be generated server-side to actually see or begin to see something - assuming there is some browser support for partial table rendering and such. And the user is not always a rendering browser, it could be web crawler like that of a search engine.

Other than embedding PHP code directly into HTML, whether you use templates or just embed PHP code into a tag, you can also generate the HTML code by using another language, that is a DSL which generates HTML. E.g. in Lisp you can use s-exprs so you don't have to close tags - you close parentheses, but at least any editor with Lisp support matches them for you automatically. The result is less messy than HTML code. HTML has a very bad syntax, indeed! By using Lisp you get some syntax checking too, e.g. it is impossible to overlap tags this way - Lisp closing parentheses are all the same, unlike HTML closing tags. By intermixing Lisp forms (that is commands) you can add any dynamic behaviour you want. Lisp provides you with full support for functional programming, that is you can code functions devoid of side effects, which are easy to test and help to implement a modular approach to HTML generation.

If you define your Lisp macro to generate HTML code which returns strings that are concatenated it will use more memory than PHP templates with <?php ?> tags. If you turn them into (write-string) forms, like CL-WHO does, you save memory but it is slower than both some hand-made (format) code to print HTML tags directly from Lisp and, of course, static HTML. Whatever the method you are using, you pay a performance price for printing HTML from your code using a nicer syntax, the cost of converting from the DSL to HTML. Moreover you have to convince the non-programmer webmasters to learn the Lisp syntax and abandon all their WYSIWYG HTML editors. Quite tough, if not impossible, to do on a large scale!

What is more, this DSL-based model works only if the front-end and back-end developer are the same person, with the same skill sets, but, even in this case, it isn't always feasible! E.g. you may need to add a bit of dynamic behaviour to some existent static HTML code. Suppose you don't have time to convert the whole document using your DSL of choice, they do not pay you for that and it would not be worthwhile anyway, since it is a mostly static page. This is why a <?php ?> is not always a bad idea. Even if you have an automatic HTML to DSL convertor, it is still slower to generate all the bulk of the HTML, which is static, using the DSL at each request.

Ideally you should have both ways to generate dynamic HTML code at hand in a server-side language and choose one case by case. If the page is highly dynamic, go for the DSL, otherwise use templates if they give you roughly the same performance as directly embedded PHP.

The problem with PHP is that it does not make easy and efficient to develop flexible DSLs for HTML generation. This is where Lisp, with its powerful macros, can provide an added value. But AFAIK Lisp-based server solutions do not provide anything like the PHP tag <?php ?>, for quick & dirty dynamic additions or PHP-based template implementations, apart from a small project mod_ecl which has been abandoned.

Tuesday, December 13, 2011

Starting out with Lisp

Tools and tutorials


Windows


You can still run CLISP if you want, although you better change your OS for a real one :)

Linux


www.clisp.org

Your distro may have CLISP already packaged. After installation, enter the interpreter with:

$ clisp

Use (load "/path/to/file.lisp") to load an external Lisp program or you can type your code directly at the prompt.

Mac OS X


Download Allegro CL Express Edition for Mac OS X. Install it with:
$ sudo cp -R /Volumes/AllegroCL\
/AllegroCL/Applications/
$ sudo /Applications\
/AllegroCL/newlicense
Load the interpreter/compiler with:
$ /Applications/AllegroCL/alisp
To avoid too much typing you may want to add this directory to your PATH or make an alias in your ~/.bash_profile.

Tutorials


If you already know C, you should read this very interesting article comparing Lisp and C.

A good resource to start learning Common Lisp is this course materials from Simon Fraser University. Begin with Tutorial 1.

If you'd rather take it easy, then www.lisperati.com is for you!

My intro: Tower of Hanoi

My first simple Lisp (LISt Processing language) program solves the Tower of Hanoi game:

(defun hanoi (n source dest by)
  "Recursive solution of Tower of Hanoi"
  (labels (
      (move (d q source dest by)
        (if (= q 1)
          (format t "~&move disc #~D from ~A to ~A~%" d source dest)
          (progn
            (move (+ d 1) (- q 1) source by dest)
            (move d 1 source dest by)
            (move (+ d 1) (- q 1) by dest source)
          )
        )
      )
    )
    (move 1 n source dest by)
  )
)

Lisp syntax is very simple but must be understood since it is different from many other non-functional languages. Although at first sight it may seem strange and limited, so abounding in parenthesis, it is actually simpler, neater and more powerful than any other syntax-involved language.

Everything in Lisp is an expression and returns a value, there is no artificial distinction between expressions and statements, because it is better to make no difference in this respect. An expression can be an atom (a number, variable name, string, character, etc, all evaluating to themselves) or a list, enclosed by round brackets and interpreted as a command. Unless Lisp is told that a list is just data, it evaluates it as the result of a function call. While in C you write:

func(arg1, arg2)

in Lisp this is

(func arg1 arg2)

There are no commas and the function name slides into the parenthesis, but this is only a superficial way to look at it. The real power of this notation comes from the fact that code just looks like data and this enables powerful macro facilities in Lisp, much more powerful than #define macros in C!

Even a function definition in Lisp is a list: a defun command or special form with a side-effect of defining a new function, with the following syntax:

(defun function-name (arguments) function-body)

where function-body is a sequence of expressions making up the function definition. Only the value of the last expression will be returned as the function value. There is no special syntax for operators, they are just functions, as in mathematics. And thanks to delimiting parenthesis and Lisp prefix notation, where the operator comes first and then all its operands, they can easily accept more than two arguments. E.g. 1<a<3 can be translated directly into (< 1 a 3), while in other languages (e.g. Java) you have to write (1<a && a<3). You can have any number of operands for < and similar operators to build a chain of inequalities.

In the program above the hanoi function's body is an (optional) documentation string followed by a local function definition. The syntax for defining some local functions at the current scope is:

(labels ((fun1 (arg1) body1) ... (funn (argn) bodyn)) body)

fun1 ... funn are functions visible only to "body", which is a sequence of expressions just like function-body. In this case we only need one local function which we named "move" and the labels' body is a single command to invoke this function:

(move 1 n source dest by)

The first parameter to move (d) is the recursion level which corresponds with the disc number every time we are ready to move one disc, provided we agree in numbering discs in ascending order from the bigger to the smaller. You can see from the above call to "move" that this recursion level is initialized to 1. The second argument of move (q) is the quantity of discs to move and is initialized to n. This n is (the value of) a parameter of hanoi, which could also be accessed inside move if we wanted but we do not need that.

By the way notice that Lisp is dynamically typed, so we don't need to declare any variable type. This has pros and cons, but it combines nicely with other Lisp features that enable generic programming with no frills.

Towers of Hanoi is a problem that is best solved using recursion and functional programming. Even if you are using a non-functional programming language, it would be only cumbersome to code the solution in an iterative way, since the use of an explicit stack would be needed anyway.

Once you get used to it, thinking recursively is not difficult. I claim that recursion is actually easier than iteration and should be taught to pupils since primary school. Sure enough, you can read out the following recursive code:

(move (+ d 1) (- q 1) source by dest)
(move d 1 source dest by)
(move (+ d 1) (- q 1) by dest source)

simply as: move q-1 discs from the source rod to the by one, using the dest rod as a foothold. How it does that is not a problem, since it can use the same algorithm, although we still have to finalize its definition. This is the only tricky part of recursion! Once you do that you are left with only one disc in the source rod you can safely move to the dest rod (no "by" rod needs to be used this time, but we must still pass "by" to move in order for the call to be consistent). Now we have q-1 discs on the by rod, only 1 on the dest rod, which is in the right place, thus we just need to move the former to the dest rod using the source rod for support and we're done.

Indeed, this definition makes sense if we also say how to solve the q=1 problem in a non-recursive way. The solution for q=1 is trivial and it's the purpose of that "if" form to print it out.

For recursion definitions to make sense and lead to a program that terminates, they cannot go on forever. They must end on a banal case, and indeed this is the power of recursion: it reduces a bigger problem to a smaller and smaller one until its solution becomes apparent. All the pieces can then be put back on together to build the solution to the whole problem.

And the way we program it is by just stating what has to be done so that thinking recursively is actually simpler than thinking iteratively. Why? Because iterations are based on state. You have to follow up how variables are changed in order to understand an iterative algorithm. It is not a natural way to describe a computation and often you will need pencil and paper to fully comprehend a program you are reading. As programs get bigger and bigger, state information grows as well. Even if using the object-oriented paradigm, state usually stalks big parts of code, bigger than you can manage. Objects interact among themselves in complicated ways: an object sends a message to another object changing the state of the latter and sometimes of both. Making the execution thread of a program gives you a headache. This will never happen with functional program. You can digest a program piece by piece, continuing tomorrow without the need to jot down where execution left.

In Lisp you can use the object-oriented paradigm but it is discouraged to use it as the only way to structure your programs. Lisp instead supports many different programming paradigms, emphasizing functional program in particular. You build the bulk of your program as a bunch of functions who behave like mathematical ones: they contain no side-effects, viz they neither output or input anything or change variables so that the value they return could depend on time. A return value from a function should only depend on the actual arguments, just as in mathematics. Only a minority of functions or objects in your program should have side-effects, where absolutely required.

Programming this way is initially a bit more difficult, until you get used, but leads to programs that have better properties. Generally program execution is just a process performed by a machine and introducing a dependency on time in that process makes it harder to follow, understand and debug by humans. Iterative programming is a big mistake! It may seem apparently more straightforward, but it is not and you pay a high price for it.

Back to our sample program now! I still have to tell you how format, a printf cousin, works. The first argument of format is the destination. T stands for *STANDARD-OUTPUT*. Second argument is the format control string. A ~ character is used to introduce formatting directives. The ~D directive formats an integer as decimal digits with a leading minus sign if the number is negative. ~% is interpreted as a newline, while ~& ensures output starts on a fresh line. Non-numeric Lisp data is printed using the ~A directive. Follows a list of zero or more arguments to be used by the control string to produce formatted output.

We are now ready to give it a try:

CL-USER(2): (hanoi 1 "A" "C" "B")
move disc #1 from A to C
NIL
CL-USER(3): (hanoi 2 "A" "C" "B")
move disc #2 from A to B
move disc #1 from A to C
move disc #2 from B to C
NIL
CL-USER(4): (hanoi 3 "A" "C" "B")
move disc #3 from A to C
move disc #2 from A to B
move disc #3 from C to B
move disc #1 from A to C
move disc #3 from B to A
move disc #2 from B to C
move disc #3 from A to C
NIL

If you are wondering where that NIL comes from, it is just the return value from labels that the interpreter is printing out.

A different implementation using a sort of switch loop (cond in Lisp) is here. In what is this different? Mainly because it changes the recursion base case: n, the number of discs to move is allowed to reach 0, in which case the function dohanoi does nothing. Btw dohanoi is no more a local function and since cond is used, a progn block form is not needed as with if.

Maybe this is not a great use of cond, since there is only one condition to test. Using a base case of 0-discs for the recursion, I would prefer to rewrite the program as follows:

(defun hanoi (n source dest by)
  "Recursive solution of Tower of Hanoi"
  (labels (
      (move (d q source dest by)
        (unless (<= q 0)
          (move (+ d 1) (- q 1) source by dest)
          (format t "~&move disc #~D from ~A to ~A~%" d source dest)
          (move (+ d 1) (- q 1) by dest source)
        )
      )
    )
    (move 1 n source dest by)
  )
)
This makes the move function a bit more robust: it just does nothing if by mistake q (that is n in hanoi) is less than or equal to 0. progn is now unnecessary because, unlike "if", unless accepts a sequence of expressions as its body, having no "else" case. The overall code is a bit more compact, but don't be fooled by the reduced number of recursive calls to move (2 instead of 3): this version does make more recursive calls, e.g. for a problem of dimension 4, only 31 calls instead of 22, but asymptotic complexity is the same.

Friday, December 2, 2011

A taste of functional programming for initiates

What's functional programming? Is it just a passing hype or there is something good with it? I want to show you how easy and fun is to decompose problems using mathematical functions as much as you can, by a very simple example.

Let's consider the problem of demonstrating that the sentence "The quick brown fox jumps over the lazy dog" actually contains all the 26 letters of the English alphabet. First, solve this problem in your favourite imperative or object-oriented programming language and then compare your solution with the following one, written in standard Common Lisp:

(sort (remove-duplicates (string-downcase (remove #\space "The quick brown fox jumps over the lazy dog"))) #'string<)

This program may seem weird and unreadable, especially if you are new to Lisp, but if you put all your imperative code that does the same thing on one line I bet it gets even worse. Of course, you can always make use of some proper indentation to make your programs more readable:

(sort
  (remove-duplicates
    (string-downcase
      (remove #\space "The quick brown fox jumps over the lazy dog")
    )
  ) #'string<)

A good text editor will help you to properly indent your program and balance parenthesis. Lisp has been unfairly criticized because abounds in parenthesis, by people who don't even know it well. If you learn Lisp, you will soon realize that brackets are there for keeping the syntax simple and flexible.

After all, imperative languages use a lot of different parenthesis as well! For instance think of braces (curly brackets) to define code blocks, round brackets to enclose conditions, square brackets to index arrays etc. Not to mention semicolons, used as statement terminators - something that is unnecessary in Lisp. Isn't that worse? A lot of syntax with no added benefit, considering these languages are neither homoiconic, nor full-featured nor fully extendable as Lisp is.

It doesn't seem Java or C++ code looks prettier than Lisp code, but even if it did, who really cares? We only care about power and expressiveness in a programming language, don't we? Simple and powerful is better than elaborate and limited! Lisp has a syntax so simple you can learn it in a minute yet you can do everything that can be done in all the other syntax-involved languages and even more.

The output of our whole program is:

"abcdefghijklmnopqrstuvwxyz"

Wonder why output string are quoted? Lisp output can be used as input, but facilities are offered to output in any other format as well.

If you install a Common Lisp implementation you can try out each sub-expression at the REPL prompt. REPL stands for read-eval-print-loop and it's a Lisp interactive interpreter you can play with. I suggest you use CLISP which is open-source and available for all main platforms. Start with the innermost form:

$ clisp
...
[1]> (remove #\space "The quick brown fox jumps over the lazy dog")
"Thequickbrownfoxjumpsoverthelazydog"

Here we are just stripping blanks off a string. If we hadn't remove we could construct one this way, at least in this case:

(remove-if (lambda (x) (eql x #\space))
  "The quick brown fox jumps over the lazy dog"
)

This may seem convoluted, but it is easily explained: we define an anonymous function to check whether something is a blank character. In Lisp a function without a name can be created on the fly and passed to other functions as an argument or returned as a value from another function. remove-if is a generic function that accepts a function as its first parameter. This function is used as a predicate, that is its return value is interpreted as either true or false. remove-if removes all elements that satisfy this predicate from its second argument and returns the result as a new sequence. No side-effects here! It's generic, you can code any predicate you want.

This is what the OO buffs - or should I say goons - call the "command pattern". It's just a clumsy way to implement the same thing being limited by an inferior programming language. Indeed, not only clumsy, but less powerful too! This is because in Lisp you can nest functions and lambda functions can have unbounded variables, that is access variables in the enclosing scopes apart from its own parameters. These variables are automatically garbage-collected. You just have to think of them as free variables like in mathematics. Why shouldn't we program as we think? Who cares how the computer works? It's better to abstract from that.

The sort function is generic too: its first argument is any sequence (list, string, array) and the second is a comparison function of two arguments, a predicate. Before we used the predefined function string<, which is the specific Lisp operator for comparing strings alphabetically. There is no difference between predefined operators and your own functions in Lisp. Even the < operator for numbers is nothing else that a function we could pass to sort as #'<. #' is just a way to tell Lisp that we want to refer to a function by name and Lisp should not try to evaluate this symbol. For instance we can use sort to sort characters within a string:

[1]> (sort "GCT" #'char<)
"CGT"
or sort a vector (array) of strings by character count, that is sort the elements in order of count of characters:
[2]> (sort '#("Now" "is" "the" "time" "for" "all" "good" "men" "to" "come" "to" "the" "aid" "of" "their" "country.") (lambda (a b) (< (length a) (length b))))
#("is" "to" "to" "of" "Now" "the" "for" "all" "men" "the" "aid" "time" "good" "come"
  "their" "country.")
If you want a stable sorting, just use stable-sort instead of sort. We could even dare more and define remove using remove-if:
(defun my-remove (item seq)
  (remove-if
    (lambda (x) (equal x item)) seq))
This is indeed a simplified version of remove, but illustrates how we can define a lot of specialized and yet reusable tools. Programming with first-class functions is awesome! See the power of having first-class functions? Languages that limit how functions can be used are not good! Since we call pangrams such phrases that contain all of the letters of the alphabet, it makes sense to make our code reusable by defining a predicate to check for "pangramness":
(defun pangramp (string)
  (string=
    (sort
      (remove-duplicates
        (string-downcase
          (remove #\space string)))
      #'string<)
    "abcdefghijklmnopqrstuvwxyz"))
Here's how to use it:
[2]> (pangramp "The quick brown fox jumps over the lazy dog")
T
[3]> (pangramp "Not a pangram")
NIL

You may want to make this function more sophisticated, e.g. stripping not only spaces but any kind of blank character like tabs, newline and even punctuation characters (including dashes), supporting many languages with different alphabets and providing a switch to check for perfect pangrams. A pangram is said to be "perfect" if no duplicate letters occur, that is it has the same length of the alphabet. Btw, you can find a good list of pangrams in several languages on wikipedia.

If you want, Common Lisp supports imperative programming as well: you have even more powerful way to keep and change state (aka variables) than in most imperative functions, but these are features you have to use carefully, only when needed. E.g. Lisp assignment operator setf is more powerful than Java's = in that it supports generic setters. You can set a value inside a data structure as complex as you want by using the same code you use to get that value, whilst in Java you need to duplicate code to implement getters and setters.

And on the OO side, LISP is even more powerful than any other OO language, but wisely encourages you to use the OO paradigm only when appropriate.

Moreover, as we saw, Lisp has full support for generic programming. E.g. remove-if works on strings, lists and arrays, all the ways to sequencing data that are available in Lisp. Same function, same simple syntax. And you can easily write your own generic code too. Unlike minor languages, everything that the standard Common Lisp library does can be done by your code too.

Lisp is both a script and a system language. Very few scripting languages take advantage of the concept of lists like Lisp does. Lists are really Lisp's workhorse and there are a lot of powerful facilities to process them, especially in a functional, state-less way.

I've just touched the surface of Lisp here, but I hope I whet your appetite. The truth they concealed is Lisp is a powerful, standardized, expressive and efficient industrial-strength language. It has all the features you can find combining all the other less-powerful programming languages hyped today, yet in one simple language.

Once you get used to functional programming, you will find out that it is a more straightforward and natural way to code algorithms in. You get out better properties from your code, in terms of correctness, reusability, clarity without introducing unnecessary structure as it is often the case with OOP.

Learn Lisp and functional programming and use it everyday! You will be a better, more productive programmer and will like your job more. It will also give you an edge over competitors using less powerful languages. Two readings I recommend are:

Sunday, November 27, 2011

Nonacceptance of functional programming makes the software industry suck

Abstract


Functional programming (FP), a very useful paradigm of programming devised in the 60s, has been underestimated for a long a time and that turned out to be the biggest mistake in the software industry as software has become more and more complex. FP simply allows one to program what to do, not how to do, leading to software that is easier to read, write, extend, modify and debug.

How? You try to avoid as much as possible keeping state information or having side-effects. The responsibility for having demoted the importance of FP lies with the object-oriented paradigm (OOP) which instead has been promptly and largely adopted by industry. OOP deceptively appears a simpler way to structure software, but being too simple to be generic enough, often misused and retaining the old ideas of keeping and manipulating state information explicitly, has largely failed its objectives in the real word.

Only FP makes possible to really program the way we think, not the way computers work and multiplies the advantage of using a compiler or interpreter instead of pure machine code.

Content


In the object oriented paradigm (OOP) you just wrap code and data into classes thus sweeping under the carpet all problems generated by keeping too much state. But you haven't done much this way: nasty bugs continue to pop up inside classes and haunt you. And, what's worse, by using OOP you are mostly forcing the decomposition of your problem into a hierarchical structure which is not the best one for all situations. OOP is a useful paradigm for certain peculiar kind of problems, like simulation - indeed it is here that the full idea of objects originated in a language called Simula - but pretty unsuitable as a general programming technique.

By the way most companies use OOP just as a framework for mediocre programmers with little or no design skills to fill the gaps. By looking at most OO software in the real world you see that the hierarchies they created often don't decompose problems in a natural way. E.g. top level operations are not primitives. OOP is very easy to misuse and misunderstand and the way the industry took it in has been more a source of bad design than of better solutions compared to the old procedural programming that took code and data completely separate.

Every smart programmer has been disappointed by OOP and discovered that using it as the only paradigm or way of structuring code is just a mere forcing with no added benefits. On the contrary OOP introduces a lot of additional complexity in handling instantiation, communication and, where applicable, synchronization of all these objects your software is artificially fragmented in.

Not everything is an object in the real word: if you force your view of the world as made up of objects only, you will soon find out that it doesn't help to manage complexity at all, since these objects often communicate between themselves in elaborate ways and have to change their own state as a result of this interaction. These are all complications that arose suspicion someone is giving you the illness for selling you the cure afterwards. I can't believe many universities teach OOP to their students ignoring FP completely, while the opposite should be done. Fortunately the best ones (e.g. MIT) don't do such a silly mistake.

Therefore we get back to the crux of the matter: the evil lies exactly in having to maintain too much state! That is a bad programming technique and OOP does not help to remove or at least relieve this problem. On the contrary OOP has made it worse, encouraging people to basically continue to code the same way as computers work at the lowest level, adding only some artificial and unnecessary structure to programs. There is no good reason nor advantages to keep state information spread over all your program. It is ok to introduce a bit of state and side-effects when they are absolutely necessary for a program to actually work (e.g. input/output itself is a side effect that cannot be avoided).

OOP, being just another imperative programming variant, introduces a lot of state to keep the intermediate results of a computation and this is a very bad thing programmers have not be accustomed to think of! From a long time we have garbage-collector technologies and do not need to manage memory in such a low-level fashion like this. That's the truth no bombastic OO programming book will ever tell you and you'll have to learn the hard way. As I did, when I found myself reinventing a bit of FP in non-functional programming languages and trying to avoid using classes and objects for everything.

FP tries to use pure mathematical functions as much as possible. Your program is naturally decomposed into reusable modules that contain almost all code and very little mutable data, especially in the form of state variables. A bit of state information (that is mutable data) shows up, but only in the outer high-level layers of the software, where it is easier to control, or it is hidden in the insides of some functional library and only if absolutely needed. In the latter case state information is usually made private and gets changed in predictable ways only.

E.g. think of a pseudo random number generator that keeps track of the last value generated so to give you an always different value the next time you invoke its primitive. If you want more than one generator (each being an object, you may say in OOP lingo) you can easily use a high-order function that returns many independent random number generators, each with its own state hidden under the bonnet. In FP functions can return other functions (this is the equivalent of a constructor) and the bonnet where some state can be kept is called a closure, a stack frame containing binded variables automatically managed by the system. Functions can thus be objects, destruction is automatic (there are no destructors to invoke explicitely) and you can implement an object system with inheritance and polymorphism and even more if you want - read if it is appropriate, because it isn't always so, since the whole point is to avoid keeping too much state and OOP doesn't do that.

Else most of your code is made up of functions whose result depends only on their arguments, just like in mathematics. These are independent pieces of code that can be easily and separately developed, reused, understood, modified, tested, debugged and even parallelized for faster execution, without changing a line of code or having to write any involved additional test code! Big programs structured this way finally make sense to the initiate: except for very few exceptions, that is objects implemented using FP or global variables - both to be used sparingly, you don't have to take account of current state of many objects when reading a program, which is exactly what makes a program difficult to understand.

A program not written by you (or written by you a few months ago) can be grokked by looking at the "main" code and abstracting over all the other details. You read the program source code and it tells you exactly what the program does instead of puzzling you with stateful objects whose interactions will not be clear until you have a grasp of the whole code AND you have tried some of the involved execution paths that leads to the creation of a particular state of interest among many possible ones. This is practically impossible to do for any large-enough software project.

It should not be needed to read all the code or jump around classes like hell and look at state variables during long and complex execution paths in order to understand how a software works! If you have to do that it means that the code is not well-structured and you aren't working at the right abstraction level. State information and side-effects are the source of all evils and should be avoided, controlled and confined as much as possible, while imperative programming (including OOP) makes unnecessary use of them!

FP is a such a simple miracle, one must be blind not to see it! If you use pure or mostly pure functional programming you can make sense of a piece of code extracted from a large software without knowing anything about the rest! You can even go on and fix a bug in the that code from your first working day. Managers who want new programmers to be productive right away should adopt FP for this reason even if they don't understand what the many other benefits are. If they want to be able to replace people easily, they should use FP, not OOP only.

FP is not a theoretic device, rather OOP is! FP works in practice because of a combination of many features that good functional languages offer, some of them may seem strange at first because we are not used to be able to do these things in imperative programming. Imperative language implementors didn't want to abstract too much from physical machines. It's not that they chose to make their life simpler when implementing interpreters or compilers at the expense of the programmer, because actually a LISP interpreter or compiler is much easier to implement than say a C++ one. They limited the expressiveness and/or extensibility of languages just out of ignorance of more advanced programming techniques.

Well, to be honest not only for that. In the early days of computing, having languages that express algorithms in the same imperative way as machine languages was justifiable by the necessity of saving some CPU cycles and/or a bit of memory. Now both of these are very cheap compared to human programmer's time, but they weren't when computers had the size of a big refrigerator or occupied a whole room. It's a long time that these limitations are not needed anymore and they now seem so ridiculous just as wanting to program at the assembly level.

Nonetheless FP has been literally ignored by the dumb business world for about 50 years, until a recent very mild rediscovery, mostly in the area of concurrent programming. How have programming languages progressed in all this time? Well, we are now very slowly adding some basic functional programming features to less powerful bloated imperative and object-oriented languages, while we should be better off using an old full-featured multi-paradigm functional language like Lisp.

That is why I am giving up to my programmer job after many years of practice and experience. I cannot easily find high-quality code bases to work on and even in new developments I am dictated what programming language to use according to the most recent passing fad. And they are all bad languages, a giant step backward from the Lisp of 1958. Moreover I have to do overtime and work under pressure with a very low wage. Programming is no fun any more this way: we programmers are just slaves forced to work without good tools. But these good tools exists. It's just they don't want us to use them, for no logic reason. So it's not my failure, it's the industry that really sucks and it sucks badly. I made up my mind to abandon programming for the businesses, although I like it out of difficulty to find out a good job.
As of March 2012, I am permanently retired from my profession. Anyway, I am still interested in any kind of casual job NOT INVOLVING computers. But I am no more interested in any kind of IT job as an employee, not even for IBM or Google (not to mention Microsoft). Maybe in 50 years, if the software industry gets better, provided I am still alive. I am still interested in hardware, though, especially sledgehammers. To all IT managers on this planet: to knock a nail one should use a hammer, not a chainsaw. To cut trees one should use a chainsaw, neither a nail nor a hammer.