Transcript LISP:Power and Elegance in ONE

LISP: Power and Elegance in
ONE
Overview
The History of Lips
 Lisp, Mathematics and Elegance
 The Power of Lisp
 Lisp in Commercial Use

Some Interesting Quotations
“Lisp is worth learning for the profound enlightenment
experience you will have when you finally get it; that
experience will make you a better programmer for the
rest of your days, even if you never actually use Lisp
itself a lot”
-Eric Raymond, “How to Become a Hacker”
More Quotations
“I have heard more than one Lisp advocate state such
subjective comments as, “Lisp is the most powerful and
elegant programming language in the world” and expect such
comments to be taken as objective truth. I have never heard a
Java, C++, C, Perl, or Python advocate make the same claim
about their own language of choice”
- A guy on Slashdot.com
“Lisp… made me aware that software could be close to
executable mathematics.”
-L. Peter Deutsch
History of Lisp

In 1960 John McCarthy published a paper where he
outlined that given some simple operations and
notation for functions, one can build a whole
programming language.
– Primitive operation were either an atom or a list of atoms.
So, foo, (), (foo) , (foo bar) , were all considered expressions.
– Functions were denoted as (lambda (p..) e) a..).

This was more of a theoretical exercise, in an effort
to define a more convenient alternative to the
Turning Machine.
Lisp as Theory
“Another way to show that Lisp was neater than Turning
machines was to write a universal Lisp function and show
that it is briefer and more comprehensible than the
description of a universal Turning Machine. This was the
Lisp function eval…, which computes the value of a Lisp
expression… Writing eval requires inventing a notation
representing Lisp functions as Lisp data, and such a
notation was devised for the purposes of the paper with no
thought that I would used to express Lisp programs in
practice.”
-John McCarthy
Theory turns to Practice: the
birth of Lisp the language

Later that year one of McCarthy’s graduate students, Steve
Russell, figured out a way to translate the eval function into
machine language.
“Steve Russell said, look, why don’t I program this eval…
and I said to him, ho, ho, you’re confusing theory with
practice, this eval is intended for reading, not for computing,
But he went ahead and did it. That is, he compiled the eval
in my paper into [IBM] 704 machine code, fixing bugs, and
then advertised this as a Lisp interpreter, which it certainly
was . So at that point Lisp had essentially the form that it
has today….”
-John McCarthy
What made Lisp Different









Conditionals: such as if-then-else construct.
Function types: where functions are just like integers
and strings
Recursion: first language to support it.
Dynamic typing: all variable are pointers.
Garbage-Collection.
Programs composed of expressions.
A symbol type.
A notations for code using trees of symbols and
constants.
The whole language is there all the time.
Lisp, Mathematics and Elegance
“Lisp is the only computer programming
language that is mathematically
respectable, because its the only one
that I can prove theorems about”
-G.J. Chaitin
Lisp and Mathematics

Lisp is Set Theory for computable
mathematics rather than for abstract
mathematics.
– A set is made up of objects.
 In mathematics a set is represented like so
{A, B, C,}.
 In lisp, this simple set would look like (A B C).
 A more complex set- (A (B C) 123)
More on Lisp and Mathematics

Why Lips is mathematical:
– time is not a constraint
– a program is essentially an expression
– expressions are evaluated returning a value
– the programmer is not forced to assign
value to variables
Elegant Lisp Programs

Lisp can be used to prove interesting mathematical
problems dealing with formal axiomatic systems.
– Gödel’s Incompleteness Theorem: which states that within
any formal system, there are truths which may be expressed
though they are not provable within the system.

Gödel's original proof of the incompleteness theorem is based
on the paradox of the liar: “This statement is false.''

e.g., try to prove that a Lisp expression is elegant if no smaller
expression gives the same value that it does. (YOU CAN’T!!!!)
The Power of Lisp




The Power of Simplicity
Rapid Prototyping
Unique Functionality
High-Performance: Lisp vs. Java, C, C++
The Power of Simplicity

Lisp is syntactically clean and simple
– symbolically designed
– faster learning-curve
– more time spend on coding
Rapid Prototyping
Lisp is comprehensive
 It supports modular design.

– Using complex constants in code
– Macros
– Optional Declaration
– Higher Order Function
Lisp is Comprehensive

Lisp includes an extraordinary powerful set of predefined tools:
–
–
–
–
–
–
–
–
–
–
–
Numbers
Characters
Arrays
Cones
Symbols, Packages, and Readtables
Functions
Hash Tables
Streams
Classes, Methods, and Generic Functions
Pathnames
Conditions and Restarts
Lisp Supports Modular Design

Using complex literals in code:
– in production code, you might want to make a global variable to keep
track of a quantity shared by several modules,
>(defvar *club-members* ‘())
>(defun add-club-member (who) (pushnew who *club-member*))
>(defun is-club-member? (who) (member who *club-member*))
– in prototyping doing minimal amount of work is needed to make the
program run,
>(defun is-club-member (who) (member who ‘(joe sally fred))
Continuation

Macros
– Macros is what makes Lisp superior compared all other
languages.
– Macros introduce a unique functionality that allows programs
to write other programs.
– It’s a real boon to rapid prototyping.
Instead of writing
>(setf x nil)
We can write a macro
>(defmacro nil! (x) (list ‘setf x nil))
>(nil! x)
NIL
Continuation

Higher Order Functions
– Lisp posses the ability to pass functions as arguments to
other functions.

Optional Declarations
– Lisp does not enforce declarations, so writing a function
such as,
>(defun twice (x) (* 2 x))
will suffice for prototyping.
Lisp vs. Java, C++

In a recent study Prechelt (1999)
compared the relative performance of
Java and C++ in execution time and
memory usage.
Lisp vs. Java, C++




Lisp’s performance is comparable to or better than
C++ in execution speed.
Significantly lower variability, which translates into
reduced project risk.
Development time was found to be significantly lower
and less variable than either C++ or Java.
Memory consumption is comparable to Java.
Some Data


Development time for Lisp ranged from low of 2 hours
to high of 8.5 hours, compared to a range of 3 to 25
hours for C and 4 to 63 hours for Java.
Lisp programs were significantly shorter than C, C++,
and Java programs
– Lisp programs ranged from 51 to 182 lines of code, median
was 134 lines.
– C, C++, and Java programs ranged from 107 to 614 lines of
code, with the median of 244 lines.
The Power is in the Code

Consider the following problem, where we want to write a function
that generates accumulators,i.e, a function that takes a number n,
and returns a function that takes another number i and returns n
incremented by i.
– In Common Lisp this would be:
>(defun foo (n) #’ (lambda (i) (incf n i)))
– In Java we get:
public interface Inttoint { public int call(int i);}
public static Inttoint foo(final int n) {
return new Inttoint() {
int s = n;
public int call(int i) {s = s+i; return s; }};}
Lisp in Commercial Use

Yahoo Store, used to be called Viaweb.
– Founded by Paul Graham
– Lisp was the primary development language for the server-based
applications.
– 20-25% of the source code for Viaweb was made up macros.

Orbitz.com
– came in rather late into the online travel market, with competitors
such as Travelocity and Expedia already dominating the industry.
– Completely rewrote the entire flight search engine package in Lisp,
giving greater functionality and searching capabilities than with the
standard legacy systems used by its competitors.
– Using Lisp, made Orbitz almost completely self-sufficient, with
minimal dependence on third-party vendors.
QUESTIONS?