"PARADIGMS OF ARTIFICIAL INTELLIGENCE PROGRAMMING" by Peter Norvig

• All too often, the teaching of computer programming consists of explaining the syntax of the chosen language, showing the student a 10-line program, and then asking the student to write programs.
• To be sure, no one can be a good AI programmer without first being a good programmer.
• In particular, Lisp makes it easy to define new languages especially targeted to the problem at hand.
• There is a myth that Lisp (and Prolog) are “special-purpose” languages, while languages like Pascal and C are “general purpose.” Actually, just the reverse is true. Pascal and C are special-purpose languages for manipulating the registers and memory of a von Neumann-style computer. The majority of their syntax is devoted to arithmetic and Boolean expressions, and while they provide some facilities for forming data structures, they have poor mechanisms for procedural abstraction or control abstraction. In addition, they are designed for the state-oriented style of programming: computing a result by changing the value of variables through assignment statements.
• This flexibility derives from two key features of Lisp: First, Lisp has a powerful macro facility, which can be used to extend the basic language.
• The macro facility is possible because Lisp programs are composed of a simple data structure: the list.
• Nowadays, Lisp is more often compiled than interpreted, and programmers rely more on Lisp’s second great flexible feature: the function.
• Computers allow one to carry out computations.
• Normally, the distinction between a computer “user” and a computer “programmer” is that the user provides new input, or data (words or numbers), while the programmer defines new operations, or programs, as well as new types of data.
• Lisp convention for arithmetic expressions is slightly different: a computation consists of a parenthesized list with the operation name first, followed by any number of operands, or arguments. This is called prefix notation.
• One advantage of parenthesized prefix notation is that the parentheses clearly mark the beginning and end of an expression.
• In Lisp, lists are evaluated by first evaluating all the arguments, then applying the function to the arguments, thereby Computing the result.
• First, many other languages make a distinction between statements and expressions.
• Statements have effects, but they do not return values.
• In Lisp, there is no such distinction: every expression returns a value.
• Second, the lexical rules for Lisp are much simpler than the rules for other languages.
• Third, while many languages use semicolons to delimit statements, Lisp has no need of semicolons, since expressions are delimited by parentheses.
• The quote mark instructs Lisp to treat the list as a piece of data rather than as a function call:
• First, it is important to remember that Lisp does not attach any external significance to the objects it manipulates.
• Every symbol can be used as the name of a variable or a function, or both, although it is rare (and potentially confusing) to have symbols name both.
• Besides the syntax of atoms and function calls, Lisp has a small number of syntactic expressions. They are known as special forms.
• Special forms are expressions that return a value.
• The philosophy of Lisp is to provide a small number of special forms to do the things that could not otherwise be done, and then to expect the user to write everything else as functions.
• It turns out that the quote mark is just an abbreviation for another special form.
• The symbol nil and the form () are completely synonymous; they are both representations of the empty list.
• nil is also used to denote the “false” value in Lisp.
• The function cons stands for “construct.”
• It is important to note that these functions create new lists; they don’t modify old ones.
• The special form defun stands for “define function.”
• Documentation strings are crucial tools for debugging and understanding large systems.
• mapcar's name cornes from the fact that it “maps” the function across each of the arguments.
• It is a widely used convention among Lisp programmers to mark special variables by spelling their names with asterisks on either end.
• Only the value nil is considered false; all other values are considered true.
• Every recursive call chops off the first element and looks at the rest, so for an n-element list there can be at most n recursive calls.
• Functions in Lisp can not only be “called,” or applied to arguments, they can also be manipulated just like any other kind of object.
• A function that takes another function as an argument is called a higher-order function.
• The name lambda cornes from the mathematician Alonzo Church’s notation for functions (Church 1941).
• Lambda derives from the notation in Russell and Whitehead’s Principia Mathematica,
• The normal rule for evaluation states that symbols are evaluated by looking up the value of the variable that the symbol refers to.
• There are two reasons why lambda expressions are very useful.
• First, it can be messy to clutter up a program with superfluous names.
• Second, and more importantly, lambda expressions make it possible to create new functions at run time.
• Strings are used mainly for printing out messages, while symbols are used for their relationships to other objects, and to name variables.
• We can now summarize the evaluation rule for Lisp.
• Every expression is either a list or an atom.
• Every list to be evaluated is either a special form expression or a function application.
• A special form expression is defined to be a list whose first element is a special form operator. The expression is evaluated according to the operator’s idiosyncratic evaluation rule.
• A function application is evaluated by first evaluating the arguments (the rest of the list) and then finding the function named by the first element of the list and applying it to the list of evaluated arguments.
• Every atom is either a symbol or a nonsymbol.
• A symbol evaluates to the most recent value that has been assigned to the variable named by that symbol.
• A nonsymbol atom evaluates to itself.
• Every variable, regardless of its name, is just a memory location, and the time to access the location does not depend on the name of the variable.
• Why is it a good language for AI applications? There are at least eight important factors:
• Built-in Support for Lists
• Automatic Storage Management
• Dynamic Typing
• First-Class Functions
• Uniform Syntax
• Interactive Environment
• Extensibility
• History
• In sum, these factors allow a programmer to delay making decisions.
• This ability to delay decisions—or more accurately, to make temporary, nonbinding decisions—is usually a good thing, because it means that irrelevant details can be ignored.
• The great advantage of strongly typed languages is that they are able to give error messages at compile time.
• Traditionally, a programmer would write a complete program, compile it, correct any errors detected by the compiler, and then run and debug it. This is known as the batch mode of interaction.
• The easiest way to extend the language is with macros.
• In general, there are six maxims that every programmer should follow:
• Be specific.
• Use abstractions.
• Be concise.
• Use the provided tools.
• Don’t be obscure.
• Be consistent.
• Remember that only nil counts as false; all other values are considered true for the purpose of conditionals.
• Every programmer learns that there are certain kinds of loops that are used again and again. These are often called programming idioms or cliches.
• Lisp has gained a reputation as a “recursive” language, meaning that Lisp encourages programmers to write functions that call themselves.
• In general, most recursive functions derive from the recursive nature of the data they are operating on.
• Programs written in a functional style never need a sequence of actions, because they don’t have side effects.
• Writing a macro is a four-step process:
• Decide if the macro is really necessary.
• Write down the syntax of the macro.
• Figure out what the macro should expand into.
• Use defmacro to implement the syntax/expansion correspondence.
• Introducing a macro puts much more memory strain on the reader of your program than does introducing a function, variable or data type, so it should not be taken lightly.
• Introduce macros only when there is a clear need, and when the macro fits in well with your existing system.
• The list is a convenient abstraction, but the actual implementation of lists relies on lower-level building blocks called cons cells.
• A cons cell is a data structure with two fields: a first and a rest.
• All proper lists have a last cons cell whose rest field is nil.
• The association list is a type of list used to implement tables. An association list is a list of dotted pairs, where each pair consists of a key and a value. Together, the list of pairs form a table: given a key, we can retrieve the corresponding value from the table, or verify that there is no such key stored in the table.
• The advantage of using bit sequences is that it takes less space to encode a set, assuming a small universe.
• In many languages, there are two strategies for debugging: (1) edit the program to insert print statements, recompile, and try again, or (2) use a debugging program to investigate (and perhaps alter) the internal state of the running program.
• A program is not complete just because it gives the right output. It must also deliver the output in a timely fashion.
• However, it is usually a bad idea to worry too much about efficiency details while starting to develop a program. It is better to design a flexible program, get it to work, and then modify the most frequently used parts to be more efficient. In other words, separate the development stage from the fine-tuning stage.
• However, in the general case, a function consists of the body of the function coupled with any free lexical variables that the function references. Such a pairing is called a lexical closure, or just a closure, because the lexical variables are enclosed within the function.
• We distinguish five stages in the development of a program. First is the problem description, which is a rough idea–usually written in English prose–of what we want to do. Second is the program specification, where we redescribe the problem in terms that are closer to a computable procedure. The third stage is the implementation of the program in a programming language such as Common Lisp, the fourth is testing, and the fifth is debugging and analysis.
• Often there are costs associated with actions, and we want to find a solution with minimal, or near-minimal costs.
• Exponential growth means that problems that can be solved in seconds for, say, a five-input case may take trillions of years when there are 100 inputs.
• This style of programming, where pattern/action pairs are stored in a table, is called data-driven programming. It is a very flexible style that is appropriate for writing extensible systems.
• Most “real” AI programs deal with large amounts of data, and with large search spaces.
• Lisp encourages a style with lots of function calls, particularly recursive calls.
• There are four very general and language-independent techniques for speeding up an algorithm:
• Caching the results of computations for later reuse.
• Compiling so that less work is done at run time.
• Delaying the computation of partial results that may never be needed.
• Indexing a data structure for quicker retrieval.
• Interpreters are also inherently more flexible than compilers, because they put off making decisions until the last possible moment.
• The flip side of losing run-time flexibility is gaining compile-time diagnostics.
• The major advantage of a compiler is speed of execution, when that makes a difference.
• A delay structure has two fields: the value and the function.
• Improving little-used features is a waste of time.
• With an inline function, the body of the function is compiled in line at the place of the function call.
• One proven technique for improving efficiency is to replace the interpreter with a compiler.
• The idea of eliminating unneeded computation is so attractive that entire languages have built around the concept of lazy evaluation–don’t evaluate an expression until its value is needed.
• You should declare a function inline when it is short and the function-calling overhead will thus be a significant part of the total execution time.
• Functions with keyword arguments suffer a large degree of overhead.
• Lisp guarantees that unused space will eventually be reclaimed by the garbage collector. This happens automatically—the programmer need not and indeed can not explicitly free storage.
• Garbage collection is particularly worrisome for real-time systems, because it can happen at any time.
• The beauty of using Lisp's built-in memory management is that it is guaranteed never to leak and never to deallocate structures that are in use. This eliminates two potential bug sources. The penalty you pay for this guarantee is some inefficiency of the general-purpose memory management as compared to a custom user-supplied management scheme.
• an interpreter takes a program (or expression) as input and returns the value computed by that program.
• Tail-recursion is crucial to Scheme.