Lisp Language

Lisp is one of the oldest "high level" programming languages; invented by John McCarthy in 1958 while he was at the Massachusetts Institute of Technology (MIT).

Lisp is extensible: It is mostly built in itself, and programs are written by extending the language. Like Forth, for example.

It is interactive; Lisp processes your source code as you type or load, however a stand alone program can be produced by most Lisps. This allows you to update pograms on the fly as you write them, and promotes a "test as you go" method.

Statements in Lisp are called expressions and specifically, "s-expressions" ("s" for symbolic). Lisp is expression based; using pre-fix notation (opposite of Forth), with the verb first, followed by the objects. Oh, and every expression must be enclosed in parentheses. Lots and lots of parentheses. For example: (+ 1 2) returns 3 in the Lisp REPL (Read Eval Print Loop). For fewer parentheses, see LOGO

"Lisp" stands for "List Processing" because the main data structure is a List. (In Forth, the stack; in Javascript, the object). A list is like an array, but made in a way that allows us to easily divide up the list. We can quickly get the first, or first several items from the list. Or we can get the remainder of the list after those items. We call that the "tail" and if you think about it, all lists are just the first item, and then a tail. The tail has a first item, and another tail. And all the tails down the line are just an item and another tail. So a list is just a single value, and another list.

The essence of a list is the data structure (inexplicably called) "cons" that is just a pair of any two items. But cons is used to make a list by having the first element of the pair be the first element of the list and the 2nd element of the pair being the REST of the list.

As a practical example, the following converts 'F into 'C in Lisp:

(defun FtoC(degF) (/ (* (- degF 32)  5) 9) )

Notice "defun" and how it is a very short contraction, instead of something more readable like "define" or "function". Lisp is terse and likes initials. At best. For example, cdr and car are functions that return the first element of a list and the remaining elements of a list.

(car (list 1 2 3)) => 1
(cdr (list 1 2 3)) => (2 3)

The popular explanation that CAR and CDR stand for "Contents of the Address Register" and "Contents of the Decrement Register" based on the addressing instructions of the computer on which it was first written, but that machine does not have a programmer-accessible address register and the three address modification registers are called "index registers." No real understanding of the source of these names exists. Why aren't they called "first" and "rest"? They are in some derivitives of Lisp. And cddr is (cdr (cdr x)) which gives the list items after the first 2 (cddr (list 1 2 3 4 5)) => (3 4 5)

Symbols in Lisp are quoted by a single quote, at the front only, and they end with a space. e.g. ('abc) returns ABC as a symbol. Sometimes, the quoting is assumed, as in define or defun where the name of the function or it's parameters don't have to be quoted. Or when we define a variable. For example:

(setq a 111)

then

(write 'a) => a
(write a) => 111

Videos

Here is a good introduction to Lisp video:
https://www.youtube.com/watch?v=jvnwXHsL8eo&list=TLPQMjIwNjIwMjAVKl-4u8lNFw&index=1

This video does a good job of explaining how Lisp is interpreted. All the code is at:
https://github.com/maryrosecook/littlelisp/blob/master/littlelisp.js
And there is a written out version of the video at:
https://maryrosecook.com/blog/post/little-lisp-interpreter

Examples:

Finding an approx Square Root via successive guesses:

(defun square-root (x) 
    (defun square (x) (* x x))
    (defun average (x y) (/ (+ x y) 2))
    (defun improve (guess)
        (average guess (/ x guess))
        )
    (defun good-enough? (guess)
        (< (abs (- (square guess) x)) 0.001)
        )
    (defun try (guess)
        (if (good-enough? guess)
            guess
            (try (improve guess))
            )
        )
    (try 1)
    
    )
(write (square-root 2))

Comments

Comments on Lisp by Christopher Fry:

Lists are used for data structures (arrays) but they are also used for the data structure that represents a function call. So you can, for instance do
(eval (list '+ 1 2))
which:

Makes a list of 3 elements, the definition of +, and two numbers.
calls it.

The understanding that "code" is "data" is still not recognized in most programming languages. Whereas many programming languages such as JavaScript consider this notion of "code is data" as "dangerous", Lisp programmers consider not using "eval" as "barbaric". Both are correct.
Lisp became the primary language for AI because:

it is better than other languages in handling complexity
it is better than other languages in writing code that writes code.

A comparison of Lisp and Forth by Gordon Charlton:

Forth and Lisp are mirror images. The opposites include postfix v. prefix, static allocation v. dynamic allocation, explicit v. Implicit stack.
The primary point of coincidence is that executing a Forth word and evaluating a Lisp function are both depth first tree traversal. They are both interactive and extensible.
Lisp comes from academia and the lambda calculus, a world where more abstract means more fundamental, and computing is mathematics made real with information processing technology.
Forth comes from pragmatism and electrical engineering, where more fundamental means closer to the physics, and software is hardware by other means.
In short, they are as different as Church and Turing, which is to say demonstrably equivalent.

Implementations

This page does a great job of explaining one possible (minimal) implementation:
http://www.ulisp.com/show?1BLW
below the level of Lisp lists, there are "objects" which tag a "symbol" (generally a pointer to string), "number" (integer), or with a little trick a "cons" (pair of pointers). The trick is that since the first part of memory is always used, the tags for symbol or number are made by setting the upper of the pair of pointers in a cons to 0 or 1. e.g. a symbol is just a cons with a 0 and a pointer to the string, and a number is a 1 and the number.

In any Lisp, the list is a linked list of cons, where the upper pointer "does the work" of pointing to something in the list, and the lower pointer points to the next list element. The last element has a lower pointer of zero. We call the upper pointer the "car" and the lower one the "cdr".

Available memory can be initiallized into a list of empty car's with cdr's that link all the way through RAM. We can make new objects by re-allocating elements from the free list into our own lists. e.g. ( sq 6 ) is made with a 2 element list, the first's car points to a symbol object (it's car is the symbol tag, it's second points to a string) and the 2nd elements car points to an object with a number tag at a cdr of 6. The 1st elements cdr points to the car of the second, and the 2nds cdr is zero, ending the list. These elements (and their sub elements) are removed from the free list, which now links around them.

Symbols can be represented in complex ways as needed. This page:
http://www.ulisp.com/show?2YZ2
describes several ideas. These generally involve clever tags / flags and other tricks, but in all cases, the point is to make data available for easy manipulation by programs.

Welcome to ecomorder.com!

Here is a great gift for computer geeks or widows:
The Backwoods Guide to Computer Lingo