Kazimir Majorinc
Lisp book

Book cover

Kazimir Majorinc

As Powerful as Possible

The main ideas of Lisp in McCarthy's period

"In developing LISP our first goal is to describe a language which is as powerful as possible from the point of view of the programmer.

McCarthy, Programs in Lisp, AIM-012, 1959, p. 4.

Programming language Lisp is designed as a practical programming language. Surprising combination of the simplicity and expressive power made it, as Paul Abrahams said, an object of beauty, worth to be studied in and on itself. Initial development and later studies and attempts for improvement of the language produced the body of interesting, important, frequently controversial and conflicting ideas, usually with little consensus on their value.

This book is a survey of main ideas of the earliest period of development of Lisp, under leadership of the language creator, John McCarthy. It is written in Croatian language, published under CC= license by Multimedia Institute. and free for download. I consider publishing it in English too. The following volume is in preparation.


1.  Introduction
2. Early influences on McCarthy
2.1.  Technological enthusiasm
2.2.   Finite automata and explicit representations of facts
2.3.  Digital computers as intelligent machines
3.  Dartmouth project
3.1.  The language of intelligent computers
3.2.  Between IPL and Fortran
4.  FLPL
4.1.  Operations on words
4.2.  Lists
4.3.  Creation of lists
5.  Proposal of the compiler
5.1.  Programming language as coordinate system
5.2.  Freedom of the programmer
5.3.  Logical values and functions
5.4.  If function
5.5.  Syntacs
5.6.  Lists
5.7.  The functions with multiple values and composition of functions
6.  Proposal of the programming language
6.1.  Conditional expression
6.2.  Go to statement
6.3.  Macro statement
6.4.  Higher order functions
6.5.  Lambda expressions
7.  Imperative Lisp
7.1.  Imperative and algebraic language
7.2.  Basic types and statements
7.3.  Subroutines and functions
7.4.  Symbolic expressions
7.5.  Property lists
7.6.  The lists and representation of symbolic expressions
7.7.  The functions for analysis and systesy of words and referencing
7.8.  Free memory management
7.9.  Basic functions on the whole lists
7.10. The function maplist
8.  Elements of the functional programming
8.1.  New function maplist
8.2.  McCarthy's lambda expressions
8.3.  Simplification of the language
8.4.  Implementation of recursive functions
8.5.  Functional and imperative style
8.6. Undefinability of the function list
8.7.  Substitutional functions and function apply
8.8. Auxiliary functions and implementation of apply
8.9. Automated memory management
8.10.  Rochester's lambda expressions
8.11. Formatting of the programs
8.12.  Compositions of the functions car and cdr
8.13.  The function compute
9.  Pure Lisp
9.1.  Mathematical expressions
9.2.  Conditional expressions
9.3.  Recursively and simultaneously recursively defined functions
9.4. Lambda-expressions
9.5.  Label-expressions
9.6.  Free and bounded variables
9.7.  Comment on symultaneously recursive functions
9.8. Definition of symbolic expressions
9.9.  Difference from the previous definitions
9.10. Meta-expressions
9.11.  S-functions
9.12.  Elementary S-functions
9.13.  Comment on McCarthy's defining of S-functions
9.14.  Examples of non-elementary S-functions
9.15.  Shorthand and function list
9.16.  Functions as arguments of the functions
9.17.  Comment on elimination of shorthands and non-elementary functions
9.18. Translation of M-expressions into S-expressions
9.19. Comment on translation of M-expressions
9.20. Mathematical definition of S-function eval
9.21. S-function eval
9.22.  Comments on definition of the function eval
9.23. Universal S-function apply
9.24. Interpreter for Lisp
9.25. S-functions and theory of calculability
9.26. Simulation of Turing's machines with S-functions
9.27. Questions on S-functions undecidable with S-function
9.28. Programs as S-functions
9.29.  Representation of symbolic expressions in memory
9.30.  Differences between symbolic expressions and list structures
9.31. Garbage collection
10.  Linear Lisp
10.1.  L-expression
10.2.  Elementary functions
10.3.  Separation of subexpressions
11.  Binary Lisp
12.  Slagle's language for symbol manipulation
13.  Simbolic expressions as syntax of the language
14.  Fortran-like statements, the function program, power and multiparadigmaticity of Lisp
14.1.  Encoding of the state of the machine and fortran-like statements
14.2.  S-function program
14.3.  Symultaneous execution of fortran-like statements and order among symbols
14.4. Multiparadigmatic Lisp
14.5.  Power of the language from the point of view of programmer
15. Woodward-Jenkins arithmetics
16.   Lisp 1.5
16.1. Pure Lisp
16.2.  Use of the property list
16.3. Pseudofunctions
16.4.  Special forms
16.5.  Fexprs
16.6.  Programs in Lisp
16.7.  Functional arguments
16.8.  Special operator prog
16.9.  Gensym and oblist
16.10.  Symbols T, *T* i NIL
16.11. Arithmetics
16.12.  Arrays
16.13.  Logic
17.  Matemathical theory o computation
17.1.  The functions defined with basic functiosn
17.2. Functionals
17.3.  Elimination of label-expressions
17.4. Conditional expressions are not functions
17.5. Uncomputable functions
17.6.  Multivalued functions
17.7. Recursive defintion of the set of symbolic expressions
17.8. Recursive inductions
17.9.  Abstract syntax of programming languages
17.10. Semantics
18.  Gilmore's Lisp-like language
18.1. Conditional expressions
18.2.  Quote and label
18.3.  Abstract machine
19.   Memoization
20.   New function eval
20.1.  Extended Lisp
20.2.  New eval
20.3.  Autonymes lambda and label
21.   The first applications of Lisp

Book Details

AUTHOR Kazimir Majorinc 
TITLE Moćan koliko je god moguće -
glavne ideje Lispa u McCarthyjevom periodu
PUBLISHER Multimedijalni institut 
Preradovićeva 18
HR-10000 Zagreb
YEAR 2015
EDITORS Tomislav Medak, Petar Milat, Marcell Mars
REVIEWER Alan Pavičić Aka
LECTORS Ivana Pejić, Ante Jerić
DESIGN Dejan Dragosavac Ruta
PRESS Tiskara Zelina d.d.
ISBN 978-953-7372-28-6