A New Realization about Common LISP

In This Posting, I explored the potential fact in great depth, that certain implementations of LISP may have Symbols, one field of which holds a value in the sense that a variable should hold a value, consisting of lists and atoms, while another field can hold a property list, also known as a “Symbol Plist”.

Well it has come to my attention, that Common LISP in particular, has some fixed constraints regarding this subject.

When Common LISP evaluates expressions that are lists, the CAR is allowed to be a nested list, which defines a lambda-expression. But otherwise, the CAR needs to be an atom – i.e., a symbol – which has a compiled function, stored in the plist.

We may export function-definitions into the value-field of a symbol, such as into a variable, like so:

 


(defvar *function-var*
    #'(lambda (pos-arg1 pos-arg2)
        (list pos-arg1 pos-arg2) ) )

 

If we do, then we must call or apply this function like so:

 



(funcall *function-var* 'Foo 'Blatz)

(apply *function-var* '(Foo Blatz) )


 

If we do not abide by this convention, we get error messages, because the function-definition in the value-field is not searched by Common LISP, when the symbol is itself the CAR of a list, and because when we assign lists as function-definitions, those do not get assigned to the symbol plist.

This observation seems to be corroborated here.

This convention, of Common LISP, accelerates execution greatly, because the interpreter does not need to make complicated arrangements, depending on what type of functions appear as the CAR of a list. The context now specifies that.

Once we are aware that this constraint exists, adapting our value-field-functions to it, is straightforward, because of the built-in function

(symbol-function 'symbol)

Which disembodies the part of the plist, that is supposed to hold functions and not values, in this case, belonging to 'symbol. Hence, the following experiment should succeed on a working Common LISP Compiler:

 



GCL (GNU Common Lisp)  2.6.12 CLtL1    Oct 28 2014 10:02:30
Source License: LGPL(gcl,gmp), GPL(unexec,bfd,xgcl)
Binary License:  GPL due to GPL'ed components: (XGCL READLINE UNEXEC)
Modifications of this banner must retain notice of a compatible license
Dedicated to the memory of W. Schelter

Use (help) to get some basic information on how to use GCL.
Temporary directory for compiler files set to /tmp/

>(setf (symbol-function 'my-function)
    (lambda (pos-arg1 pos-arg2)
        (list pos-arg1 pos-arg2) ) )

(LAMBDA-CLOSURE () () () (POS-ARG1 POS-ARG2) (LIST POS-ARG1 POS-ARG2))

>(my-function 'Foo 'Blatz)

(FOO BLATZ)

>(my-function 'Ergo 'Sum)

(ERGO SUM)

>(quit)


 

Now, the somewhat unexpected line output from the definition, is due to the (setf) function doing what all variable-setting functions in LISP do: They not only bind the value asked for, to the field, but also return the same value to the calling context, because doing so can make certain LISP code more practical.

Continue reading A New Realization about Common LISP

Distinguishing between Atoms and Symbols in LISP

Upon closer examination, it seems that public documentation about LISP cites Atoms as an especially simple example of Symbols, that just have an empty Property List (NIL). It is written that they are first created that way by default.

Otherwise, Symbols are capable of carrying Values, which could just be another Atom, or which could be represented by a List in turn, whose first element is a type-atom.

It seems that in my writings, I have just reversed this use of the terms ‘Symbol’ and ‘Atom’. My main reason for not correcting this, is the fact that it would be too complicated to go back and edit so much.

I apologize for this apparent error, but will stick to it for the sake of consistency.

When Function definitions are written, Atoms and Keywords are given that bear no initial value, and which therefore, according to popular documentation, are not fully Symbols yet. These Atoms would be of no usefulness, if during the Evaluation of LISP expressions, they could not be bound to Values with local scope at least. So any Atom can trivially be promoted to a Symbol.

The other Atoms need to state Functions or Macros.

And in cases where they are type-atoms, their value can be a parent type, again leading to an Atom. So those examples should not have NIL as their Property, because the parent-type for all types, is supposed to be T and not NIL. If a type-atom was to have NIL as its ultimate parent, it would just refer to some unrecognized type, outside the LISP Interpreter scope for how to Evaluate.

Dirk

 

Alists and Plists

One of the data-structures that even early LISP implementations possessed, were ‘plists‘. It was only by reading up on LISP lately, that I discovered that many LISP implementations maintained a hidden plist, in which certain Properties of Symbols were stored. This could easily have been found in the CIR of the Atom, the naming of which was later simplified to CDR. Alternatively, this plist could have been the only datum of the Symbol, hence stored at its CAR.

In short, this was an early associative list, consisting of Key:Value pairs, where the Key was supplied by the programmer, in order to retrieve the Value from the plist.

Plists were later superseded by ‘alists‘. An alist has a better storage format, but again stores Key:Value associations. One big advantage of an alist, is the ability to perform a reverse look-up, in which a sought Value is supplied, and the List of Keys returned, that point to this Value.

I think it is agreed, that Hash Tables eventually manage forward-look-ups better than either a plist or an alist, especially if large numbers of Keys are stored. Yet, it is written that for short collections of data, the simplicity with which an alist is stored, actually allows it to work more quickly than a Hash Table, in LISP.

Now, if it was necessary to perform reverse look-ups, yet the large number of objects require a Hash Table, then the most sensible approach might be to create two Hash Tables, one for the forward look-up, and another for the reverse look-up? In that case, if a Hash Table is predicted to serve a one-to-many relationship, then the care should also be taken from the beginning, to encapsulate all the value-sets that result from one Key, into Sets, even if in many cases, there may be only one element in the Set.

Alternatively a system could be devised, so that only one result from the reverse look-up is the correct one.

Dirk