CODEWITHSUNDEEP
listdynamiclispruntimesymbols
user922475
user922475

Reputation:

How does Lisp dynamically assign symbols? Underlying data structure/mechanism of a Lisp symbol?

Lisp allows you to define symbols such as A and B in a list like 

(setf mylist '(+ 1 2 A))

You can then go back at any time and set A to a value, for ex. (set 'A 100). At this point you can do (eval mylist) and get back 103. You can then repeatedly reassign A to any new value.

It seems Lisp is saving both the literal "A" (name of the symbol) and it's assigned value. This allows dynamic variable assignment/reassignment. It's kind of like a look up list. What is the underlying data structure or mechanism that allows this?

EDIT: Specifically, how this done internally (or externally since packages appear to be directly involved)? Looking for an in-depth technical answer that focuses on how it's implemented in Lisp-2.

Upvotes: 2

Views: 712

Answers (2)

Will Ness
Will Ness

Reputation: 71070

In Common Lisp symbols are objects in their own right, capable of having named properties with values associated with them. Symbols are created (interned in current package) on read, like so:

> 'a
A

You can inspect them with (describe 'a) or (inspect 'a) (using CLISP here). You can set this symol with (set 'a 1). But you can also call (defun a (x) (+ 1 x)) after that. Inspecting the symbol 'a now reveals that it holds both a value, and a function definition at the same time. That reflects Common Lisp having separate namespaces for variables' values, and functions. Symbols store this extra information in their property lists: 

[19]> (symbol-value 'a)
1
[20]> (symbol-function 'a)
#<FUNCTION A (X) (DECLARE (SYSTEM::IN-DEFUN A)) (BLOCK A (+ X 1))>
[21]> (symbol-plist 'a)
(SYSTEM::DEFINITION
 ((DEFUN A (X) (+ X 1)) .
  #(NIL NIL NIL NIL ((DECLARATION OPTIMIZE DECLARATION)))))

[44]> (setf (get 'a 'prop1) 12)
12
[45]> (symbol-plist 'a)
(PROP1 12 SYSTEM::DEFINITION
 ((DEFUN A (X) (+ X 1)) .
  #(NIL NIL NIL NIL ((DECLARATION OPTIMIZE DECLARATION)))))

See also

http://www.lispworks.com/documentation/HyperSpec/Body/f_get.htm#get http://www.lispworks.com/documentation/HyperSpec/Body/f_intern.htm#intern

Upvotes: 2

Kaz
Kaz

Reputation: 58500

Note that '(+ 1 2 A) is not a variable, but the form (quote (+ 1 2 A)) which evaluates to an object. The A inside the list is a symbol, but it is not a variable.

A variable is a storage location denoted by a symbol.

Re: How does a language like Lisp do this kind of evaluation at run-time?

(Common) Lisp has two kinds of variables: dynamic and lexical. The dynamic variables can be evaluated at run time in the sense that you can take a symbol and determine whether it has a dynamic variable binding, and retrieve or assign that binding.

Lexical variables are the ones that are "baked" at compile time: there is no portable way to reflect over them by name.

Both kinds of variables are useful for different purposes.

A dynamic variable can be stored in a location that is associated with a symbol, called its value cell. (This term actually appears in ANSI Common Lisp). The symbol is used as a kind of key to retrieve the cell (if it has one). For instance a value cell could be the cdr field of some cons cell that is stored in a hash table where the keys are symbols. Various implementations are possible.

There is a complication in that Lisp supports local rebinding of dynamic variables: i.e. you can use let or other binding constructs to create local bindings for dynamic variables which hide any existing binding. When the construct exits (in any manner: including a non-local exit via throw, etc) the hidden binding is restored. This dynamic scoping has to be implemented somehow and it means that a dynamic variable lookup is not necessarily just chasing a pointer from the symbol to a value cell.

A further complication is that users of multi-threaded Lisps want to have per-thread binding of dynamic variables.

There may be more info here: http://en.wikipedia.org/wiki/Scope_%28computer_science%29#Dynamic_scoping

Upvotes: 5

Related Questions