Parenthesised Road Of Lisp

Jack Dikian

December 1998

Introduction

Back in the 1980’s the author was involved in writing a formal (limited) grammar to support the development of an “expert” system to deal with the diagnosis and configuration of Unix file systems.

When reviewing a number of artificial (programming) languages we become interested in LISP. We realised that it’s strong expressive language for stating computational linguistics and flexible data constructs might meet the needs of yet to be fully defined project.

We were particularly interested in manipulating symbols (words, parts of speech) and structured objects (sequences) and perform express operations on them without having to worry about how these “natural” concepts are actually represented in the machine. Also, the ability for routines to call themselves with no restrictions as found in the recursion techniques of LISP.

Our need to understand LISP took us down a very parenthesised road. This is a very brief introduction of what we saw in LISP.

What is LISP

Lisp is a programming language developed as a mathematical notation for computer programs, greatly influenced by the work of Alonzo Church's lambda calculus and become, pretty much, the programming language staple for artificial language research. Lisp derives its name from LIST Processing and it is no surprise that linked lists is one of LISP’s key data constructs. LISP provided a basis or became a genesis for significant concepts in early computer science thinking. LISP’s ability to type data objects instead of variables gives it the flexibility to provide native support for arranging data into a hierarchy based on subset relationship.

Linked lists are one of Lisp’s major data structures, and Lisp source is itself made up of lists. As a result, Lisp programs can manipulate source as a data structure, giving rise to both grammar parsing and even creating new syntax. The inter-changeability of source (formal grammar defining language) and data gives LISP its unique syntax. All source is written as s-expressions, or parenthesized lists. A call to a routine is written as a list with the operator's name first, and the arguments following; for instance, a function F that takes 2 arguments might be called using (f x y).

Why LISP

The biggest advantage LISP has over other languages such as C, C++, and PASCAL is due to the idea that LISP follows the philosophy that what's good for the language's designer is also good for the language's users. Consequently, the programmer, unlike in other languages, can add features to the language making it a self-hosting language. LISP tends to provide a more transparent map between ideas about how the program functions and its source. This is therefore ideal for situations where problems are partially specified and/or where problems whose nature is not fully understood at the outset. Approximation can be developed and refined interactively over time.

Also where a problem involves multiple representations of data from varying sources, LISP's flexible data abstraction system makes configuring robust systems simpler.

The Parentheses ( )

For people like me who was used to looking at C, Pascal, and even Fortran. LISP was initially confusing. Its syntax was nothing like I had seen before (perhaps with the exception for APL which was itself mathematically inspired and served as a executable notation for mathematical algorithms). Parentheses are the basic building blocks of LISP. All functions, operations, and scripts take place within parentheses. Complete functions have a matching number of open and closed parentheses.

When merging lists

(APPEND `((A B)(C D)))

Answer (A B C D)

Creates a function called ADDIT that takes two parameters x and y and adds them.

(DEFUN ADDIT (x y) (+ x y))

(ADDIT 3 4)

Answer 7

Creates a function for calculating powers

(defun expon (base powr)

(cond ((zerop powr) 1)

((evenp powr) (expon (* base base ) (truncate powr 2)))

(t (* base (expon (* base base) (truncate powr 2))))))