Linguistics Anonymous

17 January 2006

linguists should learn LISP, pt. 1

this will be a multi-part post, which will grow/be revised/deemed less important the more i learn about the topic.

LISP stands for LISt Processesing and is a functional programming language invented by John McCarthy (not the linguist, the computer scientist - coincidence in names noted) in the 1950's and is the second-oldest programming language still in use today (only FORTRAN is older). the langauge is well known for its bare-bones structure and emphasis on programming in which efficiency is not the main concern (as opposed to accuracy, minimality, etc.). LISP makes complex notions such as recursion and abstraction conceptually easy to implement by way of its structure...

consider the following expression in LISP computing the sum of two integers:
(1) (+ 4 5)

fed into an interpreter, this will, of course, produce the response 9. the interesting part about this is the structure of the expression: there is a prefixed primitive operator and the operands fed to it as arguments. more on why this is interesting after some more examples from the language.

primitive data in LISP comes in two forms, atoms and lists. an atom is any discrete element which evaluates: with no abstraction, this will be numbers and character strings of reasonable length: 3, 56, c3, a, etc. a list is a an element recursively constructed by concatenation of atoms: (3, 4, 6, 8) , (f, matt, 98, john), etc. there are no other kinds of data important to us now (there is another, dated, type, the dotted pair. possibly more on this in another post).

expressions such as (1) can be themselves made up of further expressions, for instance, (2):
(2) (* 9 (+4 5 (-6 4)) (+3 5))

which we could represent more schematically as a tree structure with each tree containing branches for each of the elements in the expression/list:

each node on the tree contains at the left the operator for the expression and the subsequent nodes (which may branch) contain the operands. optionally (because implemented LISP has no notion of trees, this is a loose 'optionally'), the values of the non-terminal nodes may be said to percolate their values upward - shown in fig. 1 by the labeled nodes. finally, terminal nodes are atoms in LISP (or at the current level of abstraction, in the case that other elements have been defined from primitives).

i hope at this point you can see where i am going, but allow me to continue with some preliminary LISP notions.

abstraction in LISP is accomplished in a variety of different ways based on implementation, but let us consider here that of SCHEME. an example will begin the discusison:

(3) (DEFINE SQUARE ((lambda (x))(* x x))

this expression makes reference to DEFINE as a primitive which abstracts. the new element is named SQUARE and is said to be the function that maps from x to the square of x (or x times itself - i apologize for those who might not know any lambda calculus - see Heim and Kratzer's Semantics in Generative Grammar for a good introduction for linguists). note again that we can draw this expression as a tree:

so now we know enough about LISP to begin to see some almost startling parallels.

first, take the notion of recursitivity. it is a well known-fact that langauge is recursive and any grammar which accounts for language must account for this fact - do not fear: i will not be proposing that LISP is that grammar. LISP does, however, capture the notion of recursivity in the same way in which it is captured in the nebulous region between syntax and semantics: atoms are combined to form syntactic constituents which can then be manipulated as atoms again, ad infinitum - just like in LISP, the computational power far exceeds the ability of the human mind to parse, as the computational power is theoretically infinite. we could easily take, using LISP to model, for example, syntactic computation, syntactic features as atoms and the syntactic primitives (words, functional heads) they produce by concatenation (or combination) as lists. elements of these lists are then available as individual entities if necessary (in LISP functions usually packaged with implementations or easily written that operate on lists such as FIRST and LAST can produce these results), which would allow us to model feature checking or valuing easily.

with expressions, again, we can see an interesting parallel: expressions have their operator prefixed to the left which carries the semantic or syntactic weight of the expression and operates on the operands. theoretically, the prefix notation is optional, but if we were to keep it, we could easily see LISP as an implementation of Kayne's antisymmetry and/or Bowers' Grammatical Relations theory (the latter is forthcoming). this is a digression, however, as the major point is this: one element (a head) carries the burden of most of the value of the node and is responsible for percolation - (* 5 5) evaluates to the product of 5 and 5, and (V NP) evaluates to VP - after percolation, the element can be operated upon as a whole (XP movement) or as individual items (Head Movement).

moving on, let's take a moment to look at data abstraction. in LISP, we can name variables to hold set data:

(4) (DEFINE a (* 5 5))

here the symbol a is defined as a certain value. this operation is directly parallel to Chomsky's latest formulation about Merge being an operation which forms a list of two elements and produces a label:

(5) MERGE(a, b) = LB(a){a b}

all that is left to be explained in the analogy (and actually in Chomsky's formulation as well) is how LISP can decide which element produces the label. we could even take a preliminary stab at a LISP representation of Merge:

(6) (DEFINE MERGE ((lambda(a))(lambda(b))(LB(a)(a b))))

all that would be left, then, is a proper definition of LB.

one final point in this disconnected series of parallels. when we look at figure 2, we can immediately see that the node immediately dominating (* x x) would not actually be a valid expression in LISP without some relevant abstraction - we need a binder such as (lambda(x)) or another previous instance of DEFINE to make the expression evaluate. this is analogous to principle a of the binding theory in syntax - anaphors (syntactic representations of unbound variables) must be bound by their antecedent or by a wh-phrase (the syntactic representation of a (lambda(x))). this binding then forces us to make reference to the notion of c-command, which we can see in the LISP expression as well! the lambda operator's mother node (the full lambda expression) must c-command the well-formed formula (* x x) in order for the complex to be a valid expression.

okay, so that's a lot of garbage, but what does it all amount to? is LISP the way to express the universal component of syntax (and possibly semantics?) - probably not, though it does allow us to express directly the conceptual basis for the recent minimalist developments in syntax. however, all the usual questions will remain about how much idealization of human language computation is appropriate before descriptive adequacy is lost.

it may simply be that LISP views data and process in a way similar to the human language faculty (again, a very loose notion of 'similar' is needed here), however even this point should not be understated. we should take note of the power and central notions of recursivity and simplicity in LISP and ask ourselves how this might be instantiated in universal grammar and what it says more generally about natural computational processes.

well, this article has either blithered too long or raised more questions than it answered, but one thing is definitely for certain - in viewing analysis of syntactic phenomena (and probably semantic as well) in natural language, it certainly cannot hurt to have the mental flexibility provided by a background in LISP, since the langauge directly captures notions central to human language: recusivity, simplicity (minimality, in whatever sense is most relevant), and abstraction. therefore, one might say that linguists should learn LISP.


Post a Comment

<< Home