Thursday, October 12, 2006

The Zen of LISP clusure

Definitions:
A function plus its enviroment is called a closure.

A closure typically comes about when one function is declared entirly within the body of another, and inner function refer to local variables of the outer function.

Example:


(defparameter *fn*
(let ((count 0))
#'(lambda () (setf count (1+ count))))) ; function closure.


count is lambda enviroment( or lambda use count ).

Possible usage: Closures can be used for modularity so you don't have to encapsulate data in classes to prevent it from becoming global.

Тhe names introduced by a LET form turns out not to be a name binding to some immutable values. The names refer to local variables! Such variables(a.k.a lexical variables) follow typical lexical scoping rules, so that LISP always looks up the innermost variable definition when a variable name is to be evaluated.

Example:

(defun bar ()
(foo)
(let ((*x* 20)) (foo))
(foo))

CL-USER: (bar)
X: 10
X: 20
X: 10
NIL


Definition:
A lexical variable is a variable that can only be referenced at the textual location of the code that creates it.

Everything starts from LET (a.k.a binding form). Here is the LET definition:


(let (variable*)
body-form*)


where each variable is a variable initialization form. When the LET form is evaluated, all the initial value forms are first evaluated. Then new bindings are created and initialized to the appropriate initial values before the body forms are executed. Within the body of the LET, the variable names refer to the newly created bindings. After the LET, the names refer to whatever, if anything, they referred to before(out of local scope) the LET. What happend when we use this variable in inner defined function?

What is more interesting is that, due to the ability to return functions as values, the local variable has a life span longer than the expression defining it. Consider the following example:


CL-USER: (setf inc (let ((counter 0))
#'(lambda ()
(incf counter))))
inc
CL-USER: (funcall inc)
1
CL-USER: (funcall inc)
2
CL-USER: (funcall inc)
3


+---------------------+
| |
+-------- lambda function --------+ |
| func. enviroment | |use
ref. | =========== | |
INC --------------> | | counter |<------|---- +
| =========== |
+---------------------------------+


counter has nice "secret" live inside lambda function.
We assign a value to the global variable inc. That value is obtained by first defining local variable counter using LET, and then within the lexical scope of the local variable, a lambda expression is evaluated, thereby creating an annonymous function, which is returned as a value to be assigned to inc. The most interesting part is in the body of that lambda expression - it increments the value of the local variable counter! When the lambda expression is returned, the local variable persists, and is accessible only through the annonymous function.

The thing to remember from this example is that, in other kinds of languages like Java and C/C++ the lexical scope of a local variable somehow coincide with its life span. After executation passes beyond the boundary of a lexical scope, all the local variables defined within it cease to exist. This is not true in languages supporting that return functions as values. Lexical scoping is enforced strictly, and therefore the only place from which you can alter the value of counter is within the lexical scope of the variable - the lambda expression. As a result, the counter state is effectively encapsulated. The only way to modify it is by going through the annonymous function stored in inc. The technical term to refer to this thing that is stored in inc, this thing that at the same time captures both the definition of a function and the variables referenced within the function body is called a function closure.

NOTE: If you keep in mind that "#'" means roughly "allocate (in the heap)
a closure for the following LAMBDA expression".

What if we want to define multiple interface functions for the encapsulated counter? Simple, just return all of them:


CL-USER: (setf list-of-funcs (let ((counter 0))
(list #'(lambda ()
(incf counter))
#'(lambda ()
(setf counter 0)))))
CL-USER: (setf inc (first list-of-funcs))
CL-USER: (setf reset (second list-of-funcs))
CL-USER: (funcall inc)
1
CL-USER: (funcall inc)
2
CL-USER: (funcall inc)
3
CL-USER: (funcall reset)
0
CL-USER: (funcall inc)
1


NIRVANA!

4 comments:

ivant said...

In Common Lisp defun always defines a global function, no matter how deeply it is nested. So, the more convenient and common form for the examples would be:

(let ((count 0))
(defun inc () (incf count))
(defun reset () (setf count 0)))


The other thing to note, is that closers give you the base for encapsulating internal state. This is one of the components of object oriented programming (well, actually of the modular programming, but anyway). As a moderately hard task, you can try to implement something like Java inheritance on top of closers and then use some macros to make it easier to use.

Anonymous said...

Хм има много по-сложни неща. Какво ще кажеш за следното:


(defun create-obi ()
   (let ((h (make-hash-table)))
     (lambda (command field &optional value)
       (case command
         (get (gethash field h))
         (set (setf (gethash field h) value))
         (run (apply (gethash field h) value))))))

(defun ~ (obi field)
     (funcall obi 'get field))

(defun ~> (obi field value)
     (funcall obi 'set field value))

(defun ~! (obi field arguments)
     (funcall obi 'run field arguments))


И после:  

; SLIME: The Superior Lisp Interaction Mode for Emacs
CL-USER> (setf f (create-obi))
#<COMPILED-CLOSURE CREATE-OBI-1>
CL-USER> (~> f ‘color ‘red)
RED
CL-USER> (~> f ’shape ’square)
SQUARE
CL-USER> (~ f ‘color)
RED
T
CL-USER> (~ f ’shape)
SQUARE
T
CL-USER> (~> f ‘add #’+)
#<SYSTEM-FUNCTION +>
CL-USER> (~! f ‘add ‘(1 2 3 4 5 6 7))
28

Anonymous said...

Reading On Lisp now after working through parts of SICP and doing a few small practice projects, I can finally understand what it’s saying. It’s really satisfying to finally “get” what Paul says about closures. Here’s a brief summary of the points about closures he covers:

* Closures emerge from lexical scoping. (Lexical scoping forces the system to save copies of variables when functions are defined and then associate those copies with the functions.)

* Example 1: Create a function that uses a lambda function that references one of the original arguments. (Make an implicit “function factory”.)

* Example 2: Define two functions that share the same counter variable. (Eliminate the need for messy global variables.)

* Example 3: Create a function that returns a customized function based on the arguments. (Make an explicit “function factory”.)

* Example 4: Alter example three so that the customized functions can change their state after they’ve been created. (Use optional arguments on a closure to allow the users to change it’s behavior later– sort of like properties on an object.)

* Example 5: Create a function that returns a group of closures that all use the same data objects.

* Example 6 (Chapter 5): Create a function that takes a function as its argument and returns a function for its value. (In the examples, we get one for Complement and another for Composition. These functions are mainly used to simplify and refactor the core Common Lisp library. SICP‘s coverage of Newton’s Method is much more exciting and as a bonus, it will help you understand the famous fast inverse sqrt routine.)

* Example 7 (Chapter 6): Elegance and speed with closures: Instead of defining a data structure and then defining a set of functions to access it, you can define a “smart” data structure by using closures that keep their own state and reference other closures. The line between code and data can be further blurred here by writing routines to compile your closure-based data structures. “In Lisp we can sometimes use closures as a representation. Within a closure, variable bindings can store information, and can also play the role that pointers play in constructing complex data structures. By making a group of closures which share bindings, or can refer to one another, we can create hybrid objects which combine the advantages of data structures and programs.” (On Lisp, p 76.)

Anonymous said...

What about "composeable abstraction" with monads. For more information you can watch this: http://www.infoq.com/presentations/Monads-Made-Easy

algorithms (1) cpp (3) cv (1) daily (4) emacs (2) freebsd (4) java (3) javascript (1) JSON (1) linux (2) Lisp (7) misc (8) programming (16) Python (4) SICP (1) source control (4) sql (1) думи (8)