Lisp

Many people have proposed implementations of full lambda calculus. This permits higher level functions, i.e. functions of functions of functions etc., but allows only manipulations based on composition and lambda conversions, not general manipulations of the symbolic form of functions. ...

: Mysteries and other Matters, John McCarthy (father of Lisp)

Lisp, short for LISt Processing, is a family of functional programming languages first specified in 1958.

A modern dialect is Scheme--although that identification is about as incendiary in some circles as the observation that political, not linguistic, markers separate Serbia from Croatia.

Blurbs edit

This is one of the great advantages of Lisp-like languages: They have very few ways of forming compound expressions, and almost no syntactic structure. All of the formal properties can be covered in an hour, like the rules of chess. After a short time we forget about syntactic details of the language (because there are none) and get on with the real issues -- figuring out what we want to compute, how we will decompose problems into manageable parts, and how we will work on the parts.

: Abelson, Harold, and Gerald Jay Sussman, Structure and Interpretation of Computer Programs, New York: The MIT Press, 1985, p. xvi

I guarantee you there isn't one single Lisp programmer out there who uses exclusively Lisp. Instead we spend our time hacking around its inadequacies, often in other languages.

: Steve Yegge, Lisp is Not an Acceptable Lisp, 2006-04-14

The meaning of expressions in the language is defined by the interpreter: You could write your own interpreter that assigned different meanings to the expressions. This is Alan Kay's notion of "late binding". Since we don't know much about how to program well, it would be a mistake to build in too many assumptions into the base of the language. So we want a system that will allow us to swap out the assumptions as we learn more without having to throw it all away.

: Eric Normand, The Idea of Lisp

Documentation edit

On Lisp, a book by Paul Graham
Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, a book by Morgan Kaufmann, 1992
Practical Common Lisp, a book by Peter Seibel

Lisps edit

newLisp: exploring how much Lisp can be improved before it becomes Tcl ;)

Resources edit

Association of Lisp Users: maintains a wiki and runs conferences
CMU Artificial Intelligence Repository: established by Mark Kantrowitz in 1993
Common Lisp the Language, 2nd Edition, by Guy L. Steele: available online
Lisp as an Alternative to Java (alternates: [1]), Erann Gat, Intelligence, Winter 2000: a response to An empirical comparison of C, C++, Java, Perl, Python, Ress, and Tcl, by Lutz Prechelt, 2000-03-10. slashdotted on 2001-09-08
Lisp as an Alternative to Java, Peter Norvig, 2000: a response to An empirical comparison of C, C++, Java, Perl, Python, Ress, and Tcl, by Lutz Prechelt, 2000-03-10
ANNOUNCE: Lisp Without Parentheses Project (Lispin) Site Open, 2006-12-02: Ranier Josweg enumerates some of the significant differentiating characteristics of Lisp]
Redable Lisp S-expressions: a project that proposes a set of abbreviations that can be added to most Lisp readers, allowing a form of lisp that eschews parentheses, adds infix notation, and adds c-style function call notation.

Introduction to Lisp edit

The big insight of Lisp was that most data structures and also most programming structures could be expressed using a single notation for the higher-level concept of a list. Rather than manipulating such low-level structures directly, a programmer could think and code in terms of lists while the LISP system would take care of managing the lower-level constructs necessary to carry out the operations.

A List is also known as a generalized array, meaning an array that may contain any Lisp object, including other lists. A string is a specialized array, meaning that every object in the array is restricted to a certain type.

Lisp takes an input stream, reads the representation of one or more objects from the stream, and constructs the corresponding objects. Each object is either a number or a token, except that some special characters, called macro characters, hand the input stream off to a user-definable function for processing in arbitrary ways. When that happens, all bets are off as to how the input stream will be processed, although there is a standard set of macro characters that are enabled by default, and that implement the standard behaviour of Lisp. A function triggered by a macro character returns a value (or no value), and hands the possibly-modified input stream back to the standard Lisp reader for further processing.

The most prominent macro character is (, which hands the input stream to the list constructor. Another macro character, ", reads the input stream until a matching " is found and creates an object of type string. #x reads a rational number in hexadecimal. #\ simply escapes any special interpretation of the following character. Other macro characters construct objects such as binary number, octal number, radix number, complex number, vector, bit vector, array, structure, expression, and more exotic types such as uninterned symbol.

The ` (back quote) macro character provides a sort of template facility to parameterize object construction from its representation, allowing the interpreter to construct the corresponding object from dynamically-defined components.

The set of active macro characters is kept in an object called the current reader table, which can be modified or replaced with a different table, making the process of reading the input stream is fully programmable.

An object that can be evaluated, is called a form and is either a symbol, a cons (list), or a self-evaluating object. When such an object is constructed and returned to the Lisp reader, it is immediately evaluated unless evaluation has been suppressed by the macro character ' (single quote). For a symbol, evaluation means looking up a variable by the name of the symbol or, if the symbol is a symbol macro rather than a variable name, passing the symbol to the function associated with it, and processing the return value in place its place. If the symbol is a cons and the first element in the list is a symbol referring to an operator, the special form, macro form, or function form bound to that operator is invoked with the remaining elements of the cons as arguments. Alternatively, the cons may be a lambda form, which is directly evaluated. A self-evaluating object such as a string, number, pathname, or array is simply evaluated as itself.

A Comparison with Tcl edit

One of the key difference between Tcl and Lisp is that in Lisp, since each object has a type, Lisp can use the type of an object to guide its treatment of it. A list may contain other lists, which themselves contain other lists, and Lisp will descend down through the lists to construct the objects they contain. In contrast, Tcl interprets each argument as a word, and only performs additional evaluation as explicitly directed via command or variable substitution syntax.

Another key difference is that the Lisp reader, which ingests the input stream from an I/O source, can be programmed to to respond to arbitrary character sequences in the script. This gives the Lisp reader the ability process any text, even if it isn't Lisp. This is not part of the language design, per-se. Lisp just happens to include a general-purpose programmable lexer/parser. Such a facility could also be added to Tcl without necessitating any change to the language specification.

Yet another key difference is that Lisp can be programmed to dispatch certain forms to a function instead of evaluating them directly, and then process the result in place of the original form. This is known as macro expansion. Tcl may in the future also provide this feature.

In some ways, Lisp and Tcl are the inverse of each other. The character ' tells Lisp not to evaluate an object, whereas [ tells Tcl to evaluate a script, and $ tells Tcl to perform a variable substitution. In Fexprs as the basis of Lisp function application

, 2010, John Shutt

, describes an inverted Lisp that performs selective evaluation instead of selective suppression, so perhaps Lisp is coming around to the Tcl way.

Lisp's decision to interpret every non-numeric string in the input stream as a token, possibly evaluating it, can lead to some additional syntax when one wants to suppress the evaluation:

(list 'this 'is 'some 'data (list 'containing 'a 'sublist (list 'and 'another 'sublist)))

To alleviate the need for so many single quotes, the Lisp reader provides the macro character, ', which indicates that automatic evaluation should be disabled for the object, and if the object is a container, for all objects it contains, recursively. ' suppresses all forms of evaluation, including variable dereferencing.

'(this is some data (containing a sublist (and "another" sublist)))
; -> '(THIS IS SOME DATA (CONTAINING A SUBLIST (AND "another" SUBLIST)))

In the example above, a list was created, and the elements of the list processed into tokens, another list, and a string value. The tokens, however were not evaluated for further processing. Most Lisp implementations convert characters in token names to upper case. ' does not suppress the special of macro characters for the reader of the input stream, so the sublist and the string value were constructed as they normally would be. The tokens, however, were processed any further.

Lisp, like Tcl, imposes very little absolute syntactic structure. In both languages, the functional units of the program are written in the representation of the list data structure of the language. Lisp defers to its readers for additional syntactic interpretation, and Tcl defers to its commands.

Tcl is the more pure list processor than in the sense that while a Lisp script can be parsed into a Lisp list, A Tcl script already is a Tcl list. Lisp lives in a world of objects. Tcl lives in a world of words. Lisp has its reader to bootstrap into its world. Tcl expects the world it encounters to be properly formed. If one counts the default reader macros, a Lisp like Common Lisp has considerably more syntax than Tcl, primarily in order to support syntactical representation of different types such as "object", "string", and "number", but also to counteract some of the typical behaviour of Lisp such as automatic translation of tokens into upper-case, and automatic evaluation of lists. EIAS` is largely responsible for Tcl's smaller syntax footprint in comparison with Lisp.

The difference (apart from expr, of course) is more in how words are grouped - in Lisp they form a list of tokens, not a string. So manipulating expressions "as text" is done by manipulating tokens in macros. And I'm at a bit of a loss to explain $...

Foo $bar baz corresponds to

`(Foo ,bar baz)

One key visual difference between Lisp and Tcl is that in a Tcl script, newlines between list items delimit commands. Whithout that feature, Tcl would look more like lisp:

#! /bin/env tclsh

#what Tcl would look like if newlines and semicolons didn't delimit commands

[set a {one two three four five}]

[proc swap {listname idx1 idx2} {
    [upvar $listname list]
    [set tmp [lindex $list $idx1]]
    [set list [lreplace $list $idx1 $idx1 [lindex $list $idx2]]]
    [set list [lreplace $list $idx2 $idx2 $tmp]]
}]

[puts [swap a 1 3]]

There have been a few "dual-language" ties between Tcl and Lisp, including several exploitations of Tk as a GUI for one or another Lisp variant. Ltk [2], in particular, is a Tk binding for Common Lisp.

Mapping Tcl to Lisp edit

The following mappings do not, of course, indicate an exact match in functionality, but a starting point to expore approximately-equivalent system features.

Tcl	Lisp	Notes
<<no analog>>	`	In Lisp, ` indicates that an object that would normally be evaluated should not be evaluated. In Tcl, the approach is to not place values at a position in the script where they would be evaluated as a command
[...]	<<no analog>>
{ ... }	\|..\|
<<no analog>>	" "	Tcl has no special syntax for constructing strings.
<<no analog>>	( ... )	Tcl has no special syntax for constructing lists.
word
command	form
script	progn
level	dynamic environment
{*}	Similar to @ in `(... ,@...)
\	#\	The overlap in functionality is limited to the case of removing special meaning of characters that are normally interpreted.

Discussion edit

RS: It seems to me that Lisp will probably be superseded for many purposes by a language that does to Lisp what Lisp does to machine language. Namely it will be a higher level language than Lisp that, like Lisp and machine language, can refer to its own programs." Does Tcl fit that description? I think so! As (names of) functions are just strings, they can be manipulated at every level, and both names and bodies can be manipulated...

MSW: I strongly disagree! Tcl is NOT higher level than lisp, while lisp is "a bit" higher level than machine language :). It, in some areas, comes near Lisp because it's conceptually small, functional and list-based. Simply lacking the ability of using the language itself to easily compile itself into itself (Yes I know you can write string-procs and evaluate that, but it's super-ugly)...

RS: Yet I guess you haven't programmed Lisp (yet, or for ages), else you wouldn't get such strange ideas :)

MSW continues: I also think we shouldn't, with all Tcl Advocacy active, try to say, "Yeah, Tcl can be Lisp if you want", or "Tcl can be XXX if you want" because that's just ridiculous. If we don't have a notion of identity, how can we bring Tcl forward ? "Oh wait, Tcl. Isn't that just another Lisp dialect with less uniform syntax ?". Or, "Yeah, C can be lisp, too".

It's the same error as the Perl folks made, when the claimed big-mouthedly, Perl is more portable than C (ever ported socket stuff unix <-> windows ?), higher level (how ever did they come to that conclusion when it's not about syntax-sugared operations ?) and a superset of both sed and awk (..and done so badly you want awk & sed back immediately).

Instead we should be concentrating on Tcl itself ... So please let's stop disparaging any language coming along just to bring Tcl forward. RS, you're doing a good job with your snippets on the wiki, and the wiki community in general, but Tcl fitting that description ? Come on ...

RS replies: It may have been a bit exaggerated. But if you consider a JCL

shell a higher level language than Lisp, because it can glue together Lisp apps and other services, just by passing strings around? I intuitively based my theory on the fact that Tcl is based on Lisp, C, and shells... and "everything is a string" gives me freedoms that I would not have dreamt of when I was working as Lisp programmer (but that was 9 years ago, I admit).

TV: My at least 5 cents about the Lisp stuff is because I like the Lisp father (see above) remark. I too used lisp, I guess 15 years ago, both on the bbc electron (which was good fun, and a good example of what one can do with 64 KiloByte core memory when programmed right) and Cambridge Lisp on the Atari 68000 machines, which I borrowed a little while from the store I bought the computer (just long enough to put the docu over the xerox machine), less fun but quite powerful, with the atari classic Mac redone graphical interface linked into it.

What Lisp does to machine language is probably not straightforwardly understood for those not used to making their own assembler... I guess what he means is that it takes on a certain idea (list processing) and makes that concept into an interpreted, machine independent language with functional (and lambda) programming. As I stated elsewhere on this wiki I think, at some point the 'connection machine' was made, long ago, which took the list processing onto the hardware machine level, and took at least a step further with the Xector concept (as I remember an associative vector, mapped on an Order(kilo) parallel machine).

MSW: To me, Tcl is "another kind of lisp", ranging a bit lower in highlevelness than Lisp (continuations, closures, functional language..), but what I meant is, Tcl is Tcl. Tcl is fine, but Tcl is Tcl. Everything being a string (nearly :) also means you're into Quoting Hell when writing functions which write functions which rewrite themselves on use e.g., or building aggregate functions. It's just too ugly to use for that kind of stuff (imo!), while Lisp macros have a wonderful, sane and clean feeling, and you still use Lisp to write the resulting expressions. (Just as you would use Tcl to write the string, true, but nothing being evaluated, and triggering evaluation with , is much cleaner than fighting with \n's being not evaluated if you use {}s, or $g .. being evaluated if you use "s when you want something to write something for you. Example:

% set str [format {a\nb\n%s\n} banzai]
% puts $str
=> "a\nb\nbanzai\n"
% set str "a\nb\nbanzai\n"
% puts $str
=> a
b
banzai
%

Gluing things together doesn't appear as being "higher level" to me either. It's just a pattern of usage. Hope I didn't sound too offending btw :)

TV: I think the idea of Lisp and Tcl being different shouldn't be played on syntax issues where certain braces and quotes could be replaced by a Lisp eval or subst idea, because I guess it is not untrue those things can make you lose track, but if you'd do the same in lisp, you'd immediately get into braces hell, and maybe worse, and the main event loop of most official lisps is a singular event loop which is also called 'eval', which is not so different at all. The extras in lisp also cost you some link to UI elements, files, and especially sockets, and then the games of interpreted concept complete-like are quite similar, even the functional (de-) composition hierarchy being quite comparable mostly.

When it is about aesthetics, you could shell script lisp applications together, and be in another quoting (and debugging) game. Unless braces are nicer than quotes. In that sense Lisp is (somewhat) more uniform by nature.

Category Language

Tcl and other languages