What's so special about Lisp?
Sep. 24th, 2013 01:37 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
liam_on_linuxThere are some remarkable claims about Lisp out there. Some are
substantiated and there are so many that they cannot all be wrong, it
would seem to me.
http://www.paulgraham.com/avg.html
http://www.lambdassociates.org/blog/bipolar.htm
& in general
https://en.wikiquote.org/wiki/Lisp_programming_language
Disclaimer: the following is all my best-guess approximations to what's
going on, after a LOT of effort, reading, discussion, more reading, and
in a few cases, going to very smart people and feeding them and
interviewing them until they can find sufficiently brain-dead
oversimplifications of things that my stupid non-programmer mind can
comprehend. I may have this all to cock.
The core thing is that Lisp wasn't designed as a programming language.
Lisp was formulated in an academic paper named "part 1" as an abstract
notation to allow mathematicians to describe algorithms in the simplest
possible, generalised, non-specific way. Its inventor expected that this
would be rather unusable and that it would be wrapped in a more readable,
less abstract form for actual implementation.
But then a brilliant programmer went and implemented it, some programmers
discovered that they could work in the simpler, less-structured
abstractions directly, and the rest never got done. The second-level
language was never described or implemented; Part 2 of the paper was never
written.
ISTM that Lisp boils down to 4 main things: 3 language features and a
property of the language's code structure.
The hierarchy seems roughly to be: property, feature, and two sub-features
that make the first feature very powerful and general. The snag is that
these are in escalating order of difficulty of explanation. But let me
have a stab at it.
The property is Lisp's syntax. Lisp is a set of tools for manipulating
lists, and its code is structured as lists of that form.
Then comes the big feature: on top of the list-structured code is Lisp's
syntactic macro system. N.B. these macros are nothing like compiler
macros or macro languages; it's a different usage of the word.) Compiler
macros define terms to be expanded or substituted, or bits of code to be
included or excluded; Lisp macros define what code does. Lisp macros
generate code.
To enable this are the other two uniquely powerful constructs, closures
and the lambda calculus.
Closures are a sort of magic persistent local variable which means that
functions can keep their state from invocation to invocation. Big deal.
What it means is that functions can pass other functions as parameters
and return functions, because remember, Lisp code is also Lisp data.
Not something you need in trivial programs, but immensely handy once stuff
gets complicated.
And lambda calculus, AFAICT, is a way to specify arithmetical operations
without specifying variables: it lets you abstract away the variables when
specifying a computation. So you can write an expression which means "take
something and multiply it by something else", without specifying whether
you're talking about an integer, or a float, or an array, or a function.
Combine these and the result is that the most efficient way to solve
certain classes of programs in Lisp is to write a program which writes
programs to do the work.
These all together build up to the last point, which is what led to
Greenspun's tenth rule:
"Any sufficiently complicated C or Fortran program contains an ad hoc,
informally-specified, bug-ridden, slow implementation of half of Common
Lisp."
https://en.wikipedia.org/wiki/Greenspun's_tenth_rule
Now I am no expert on this, but what he is trying to get at, I think, is
that if you are trying to solve a really complex problem in a procedural
programming language, then you end up writing an elaborate system of rules
to detect various sets of conditions and then to take actions based on
those conditions. In other words, you tend to end up building elaborate
sets of state machines and state-transition tables to drive them.
And if you're going to do that, well, there's an abstract general tool
which is more or less designed for constructing such things, and it's Lisp.
In other words, the very bold claim concealed within this is that for any
serious, non-trivial program, the simplest and most compact way of
describing the problem space and building an algorithm to navigate it is
to do it in Lisp.
This is as best as I can describe it after some years of (admittedly
very part-time) research and reading so far. The world of Lisp is buried
in impenetrable jargon and occasionally abstruse mathematics, and Lisp
code is self-obfuscating because what you do in coding Lisp, AFAICT, is to
write down the parse trees that your compiler generates as it compiles
programs written in procedural language.
IOW, learn to solve problems in Lisp, and you've learned how to build
generalised solutions. This is what ESR's famed quote means:
"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."
The #1 problem for beginners who are familiar with other programming
languages is that Lisp's syntax is weird and hard. Even many Lisp gurus
admit this.
E.g.
"I've used Lisp my whole programming life and I still don't find prefix
math expressions natural." - Paul Graham
The metaproblem, the problem with the problem, is that that syntax is part
of the nature of Lisp; fix the syntax problem, and you've crippled the
language.
Lisp is a system for algorithmically manipulating lists. Lisp code is
itself a set of lists. That's the key to its power. Lisp code structures
are Lisp data structures. There's no difference between code and data; the
representation is the same. This is the meaning of the jargon terms like
"almost-syntaxless notation" and "homoiconicity".
And at the end of the day, all programming is basically about manipulating
lists, because programs /are/ lists and so are data files. Computers are
Turing machines; they start at the beginning of lists of numbers and work
through them. Lisp forces you to confront this right at the beginning and
makes you learn to think in these general terms.
IOW, and AFAICS, there are good grounds for the claim that Lisp is the
highest-level general programming language of all.
(There are things which are even more abstracted and offer more "power",
of course, such as APL, but these address far more limited problem
domains.)
Lispers won't accept anything that removes this. This erects a huge bar to
non-Lisp programmers becoming Lispers.
So you write code in human-readable raw data structures, and the language
gives you some actually quite simple tools to write code that can flexibly
handle abstract computations. You can write programs that defines the
steps your program will take according to the input data it receives,
without needing to explicitly spell out all those steps.
In general, this is a form of functional programming.
Pure iterative procedural languages - like C - require you to spell out
all the steps for every conceivable situation; if you do not specify every
case and handle every exception to it, the program will fail. Thus, you
need to write a lot of code to handle every situation you can envisage,
and if you failed to envisage one, the program will probably fail.
Functional programming means that you just ("just"!) define all the steps
required in advance, and the data falls through the program like balls
through a pachinko machine. There is no program state, no variables
holding values which change. It's a bit like Verilog - it looks like
program code, but it's not, it's a description of a circuit to implement
the algorithm you had in mind. It doesn't "execute", it's a *definition*
of what will happen.
There are pure functional programming languages, such as Haskell and
Erlang.
Functional programming is, I am told, weird and hard but once you master
it it's a powerful way of thinking about problems.
Lisp is also capable of functional programming, but it can also do the
plain old
print "what's your name?"
input name
print "hello, " + name
... imperative procedural type of coding. Increasingly, flexible
high-level languages like Perl are implementing stuff like closures and
lambda calculus and other tools to permit you to write functional programs
in them.
Lisp anticipated all this, by being so simple that it can support both
types.
Perl provides you with a set of very sophisticated engines to perform
transformations on lines of text; it's up to you to decide which ones you
need to use. The art of it is knowing what engines it provides and
combining them cleverly.
Lisp is a toolkit for building transformation-engines which can work on
anything. It doesn't supply any particular ones out of the box but it
makes it really easy to build them.
IOW Perl is a sort of anti-Lisp:
http://www.johndcook.com/blog/2010/11/23/lisp-and-the-anti-lisp/
As such, Lisp is not the anti-Perl - it's the anti-special-purpose
language. It's the universal language.
Well, big deal, so is assembly, so is C if you consider it as a portable
assembly language. They're both Turing-complete; you can write anything in
either.
But C is a way to define the steps which your program will do, and do it
so very efficiently that the result will run fast.
Lisp is more like a tool to describe what your program is /for./ You
describe the problem, and you describe how to build the tool to solve it,
and it builds the tool for you. That's a bit crap and hand-wavey but I've
gone on for long enough.
substantiated and there are so many that they cannot all be wrong, it
would seem to me.
http://www.paulgraham.com/avg.html
http://www.lambdassociates.org/blog/bipolar.htm
& in general
https://en.wikiquote.org/wiki/Lisp_programming_language
Disclaimer: the following is all my best-guess approximations to what's
going on, after a LOT of effort, reading, discussion, more reading, and
in a few cases, going to very smart people and feeding them and
interviewing them until they can find sufficiently brain-dead
oversimplifications of things that my stupid non-programmer mind can
comprehend. I may have this all to cock.
The core thing is that Lisp wasn't designed as a programming language.
Lisp was formulated in an academic paper named "part 1" as an abstract
notation to allow mathematicians to describe algorithms in the simplest
possible, generalised, non-specific way. Its inventor expected that this
would be rather unusable and that it would be wrapped in a more readable,
less abstract form for actual implementation.
But then a brilliant programmer went and implemented it, some programmers
discovered that they could work in the simpler, less-structured
abstractions directly, and the rest never got done. The second-level
language was never described or implemented; Part 2 of the paper was never
written.
ISTM that Lisp boils down to 4 main things: 3 language features and a
property of the language's code structure.
The hierarchy seems roughly to be: property, feature, and two sub-features
that make the first feature very powerful and general. The snag is that
these are in escalating order of difficulty of explanation. But let me
have a stab at it.
The property is Lisp's syntax. Lisp is a set of tools for manipulating
lists, and its code is structured as lists of that form.
Then comes the big feature: on top of the list-structured code is Lisp's
syntactic macro system. N.B. these macros are nothing like compiler
macros or macro languages; it's a different usage of the word.) Compiler
macros define terms to be expanded or substituted, or bits of code to be
included or excluded; Lisp macros define what code does. Lisp macros
generate code.
To enable this are the other two uniquely powerful constructs, closures
and the lambda calculus.
Closures are a sort of magic persistent local variable which means that
functions can keep their state from invocation to invocation. Big deal.
What it means is that functions can pass other functions as parameters
and return functions, because remember, Lisp code is also Lisp data.
Not something you need in trivial programs, but immensely handy once stuff
gets complicated.
And lambda calculus, AFAICT, is a way to specify arithmetical operations
without specifying variables: it lets you abstract away the variables when
specifying a computation. So you can write an expression which means "take
something and multiply it by something else", without specifying whether
you're talking about an integer, or a float, or an array, or a function.
Combine these and the result is that the most efficient way to solve
certain classes of programs in Lisp is to write a program which writes
programs to do the work.
These all together build up to the last point, which is what led to
Greenspun's tenth rule:
"Any sufficiently complicated C or Fortran program contains an ad hoc,
informally-specified, bug-ridden, slow implementation of half of Common
Lisp."
https://en.wikipedia.org/wiki/Greenspun's_tenth_rule
Now I am no expert on this, but what he is trying to get at, I think, is
that if you are trying to solve a really complex problem in a procedural
programming language, then you end up writing an elaborate system of rules
to detect various sets of conditions and then to take actions based on
those conditions. In other words, you tend to end up building elaborate
sets of state machines and state-transition tables to drive them.
And if you're going to do that, well, there's an abstract general tool
which is more or less designed for constructing such things, and it's Lisp.
In other words, the very bold claim concealed within this is that for any
serious, non-trivial program, the simplest and most compact way of
describing the problem space and building an algorithm to navigate it is
to do it in Lisp.
This is as best as I can describe it after some years of (admittedly
very part-time) research and reading so far. The world of Lisp is buried
in impenetrable jargon and occasionally abstruse mathematics, and Lisp
code is self-obfuscating because what you do in coding Lisp, AFAICT, is to
write down the parse trees that your compiler generates as it compiles
programs written in procedural language.
IOW, learn to solve problems in Lisp, and you've learned how to build
generalised solutions. This is what ESR's famed quote means:
"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."
The #1 problem for beginners who are familiar with other programming
languages is that Lisp's syntax is weird and hard. Even many Lisp gurus
admit this.
E.g.
"I've used Lisp my whole programming life and I still don't find prefix
math expressions natural." - Paul Graham
The metaproblem, the problem with the problem, is that that syntax is part
of the nature of Lisp; fix the syntax problem, and you've crippled the
language.
Lisp is a system for algorithmically manipulating lists. Lisp code is
itself a set of lists. That's the key to its power. Lisp code structures
are Lisp data structures. There's no difference between code and data; the
representation is the same. This is the meaning of the jargon terms like
"almost-syntaxless notation" and "homoiconicity".
And at the end of the day, all programming is basically about manipulating
lists, because programs /are/ lists and so are data files. Computers are
Turing machines; they start at the beginning of lists of numbers and work
through them. Lisp forces you to confront this right at the beginning and
makes you learn to think in these general terms.
IOW, and AFAICS, there are good grounds for the claim that Lisp is the
highest-level general programming language of all.
(There are things which are even more abstracted and offer more "power",
of course, such as APL, but these address far more limited problem
domains.)
Lispers won't accept anything that removes this. This erects a huge bar to
non-Lisp programmers becoming Lispers.
So you write code in human-readable raw data structures, and the language
gives you some actually quite simple tools to write code that can flexibly
handle abstract computations. You can write programs that defines the
steps your program will take according to the input data it receives,
without needing to explicitly spell out all those steps.
In general, this is a form of functional programming.
Pure iterative procedural languages - like C - require you to spell out
all the steps for every conceivable situation; if you do not specify every
case and handle every exception to it, the program will fail. Thus, you
need to write a lot of code to handle every situation you can envisage,
and if you failed to envisage one, the program will probably fail.
Functional programming means that you just ("just"!) define all the steps
required in advance, and the data falls through the program like balls
through a pachinko machine. There is no program state, no variables
holding values which change. It's a bit like Verilog - it looks like
program code, but it's not, it's a description of a circuit to implement
the algorithm you had in mind. It doesn't "execute", it's a *definition*
of what will happen.
There are pure functional programming languages, such as Haskell and
Erlang.
Functional programming is, I am told, weird and hard but once you master
it it's a powerful way of thinking about problems.
Lisp is also capable of functional programming, but it can also do the
plain old
print "what's your name?"
input name
print "hello, " + name
... imperative procedural type of coding. Increasingly, flexible
high-level languages like Perl are implementing stuff like closures and
lambda calculus and other tools to permit you to write functional programs
in them.
Lisp anticipated all this, by being so simple that it can support both
types.
Perl provides you with a set of very sophisticated engines to perform
transformations on lines of text; it's up to you to decide which ones you
need to use. The art of it is knowing what engines it provides and
combining them cleverly.
Lisp is a toolkit for building transformation-engines which can work on
anything. It doesn't supply any particular ones out of the box but it
makes it really easy to build them.
IOW Perl is a sort of anti-Lisp:
http://www.johndcook.com/blog/2010/11/23/lisp-and-the-anti-lisp/
As such, Lisp is not the anti-Perl - it's the anti-special-purpose
language. It's the universal language.
Well, big deal, so is assembly, so is C if you consider it as a portable
assembly language. They're both Turing-complete; you can write anything in
either.
But C is a way to define the steps which your program will do, and do it
so very efficiently that the result will run fast.
Lisp is more like a tool to describe what your program is /for./ You
describe the problem, and you describe how to build the tool to solve it,
and it builds the tool for you. That's a bit crap and hand-wavey but I've
gone on for long enough.
