Lisp Code-Data Duality, Lambda Expressions Are Constants?

What is meant is that a function is a constant object which cannot be modified. Like a shovel: you cannot change the shovel, but you can dig many different ditches with it. Similarly, you cannot change the function, but you can apply it to different arguments and get different values.

Incidentally, this is not necessarily always the case for all implementations. E.g., in CLISP:

(defun f(x) (+ x 10))
(compile 'f)
(f 5)
==> 15
(disassemble #'f)

Disassembly of function F
(CONST 0) = 10
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
4 byte-code instructions:
0     (CONST&PUSH 0)                      ; 10
1     (LOAD&PUSH 2)
2     (CALLSR 2 55)                       ; +
5     (SKIP&RET 2)

Pretty straightforward, huh?

now, if you use internal functionality of CLISP to modify its vector of constants and replace 10 with something else, you will change the function's behavior:

(setf (sys::closure-const #'f 0) 42)
(f 7)
==> 49

This is similar to running a C program under a debugger and modifying local variables.

See also Why does an elisp local variable keep its value in this case? and Why does this function return a different value every time?

PS. Please note that doing this may lead to hard crashes (segfaults). Beware.

Paul Graham talks of constructors as functions which return new function objects. Not just simple function objects, but closures -> a function object and a binding environment. Thus a closure might be allocated at runtime, when a constructor call is evaluated at runtime. In his example he also shows that closures can sometimes also be allocated at read time - though that may have problems like compiling files and dumping function objects - which does not work.

Simple lambda expressions are pre-computed when compiled and thus may not see additional allocation at runtime to exist.