Re: Real-life examples of lexical binding in Emacs Lisp

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
>>> independence from other functions, you would have
>>> to PREFIX ALL THE LOCAL VARIABLES WITH FUNCTION
>>> SPECIFIC PREFIXES!
>>
>> Actually, not really. The Elisp convention to only
>> use prefixes for global variables is 99% sufficient.
>> In your example, the problem is that `some-function'
>> modifies the (presumably global) variable
>> `scratch-buffer' and that this variable does not
>> have an appropriate prefix.
>
> I'm curious, the techno-science books always speak of
> LISP as a language for "symbolic manipulation".
> Sometimes they mention AI. Anyone care to explain
> this? 

This is because the stress the language puts on symbols and symbolic
expressions (sexps) and the availability of operators to easily process
them.

Consider a simple function to derivate functions (it's about 100 lines
of lisp code), allowing to do things like:

    (simplify (deriv-expr '(+ (* 3 x x) (* 9 x) 3) 'x))
    --> (+ (* 6 x) 9)

Or consider some natural language processing program, like eliza, or
this expression generator: http://paste.lisp.org/+37QP 

In early eliza, the natural language words were represented using
symbols (nowadays, lisp NLP programs would use strings for the
representation of words, or even CLOS objects, but there would still be
good arguments for the use of symbols with property lists in terms of
simplicity and flexibility).

Anyways, in expressions like:

    (defvar insults
      '(
        ("accapareur" (nm))
        ("aérolithe" (nm))
        ("amiral de bateau­lavoir" (gnm))
        ("anacoluthe" (nf))
        ("analphabète" (n a))
        ("athlète complet" (n))
        ("boit­sans­soif" (ni))
        ("vieux" (a))
        ;; …
        ))

    (defvar nm (remove-if-not (lambda (x) (intersection '(n np nm gnm) (second 
x))) insults))
    (defvar nf (remove-if-not (lambda (x) (intersection '(nf np) (second x))) 
insults))
    (defvar ad (remove-if-not (lambda (x) (member 'a (second x))) insults))

the use of symbols to denote the grammatical categories, and their
manipulation to sort out the lexicon is very easy and natural.

In lisp, it's easy to program something like that, because you don't
need to do anything special to encode a symbol like x or nm.

In other programming language, the stress is often on some other data
type, like int in C (if you don't write a type when declaring a
variable, which is possible in C, it is int by default!).  And you will
also have vectors instead of lists, so as soon as you write a collection
of data, you will HAVE to use integers, to index into those vectors (in
lisp when using lists, you don't need integers, just the functions first
and rest).

So in those non-lisp languages, you will have to invent a representation
for these symbolic data, using integers (constants, or enums), or
strings, (or even objects! in OO languages). And naturally you will have
to encode the data using those vectors of integers (and what if you need
to mix integers representing integers and integer representing symbols
as in  (+ (* 3 x x) (* 9 x) 3)? Dang! Now you need some more complex
representtion, perhaps a structure or an object with variants for
integers and symbols.  And soon you're re-implementing a half-assed
buggy lisp: you are greenspunning.


A function to perform symbolic derivation was one of the first lisp
programs written by John McCarthy, this was exactly the kind of
application he had in mind for lisp; nowadays we have maxima :-)
(And mathematica which is to maxima what ruby is to lisp).

For an early symbolic application have a look at Wang's algorithm for
propositional calculus:
http://www.informatimago.com/develop/lisp/com/informatimago/small-cl-pgms/wang.html



> Does it somehow relate to the "dynamic scope"?

Not at all.  Dynamic scope was just an implementation accident, because
not enough about language design was know when lisp was invented.

When you don't have theory, programs may just happen to behave a certain
way depending on how they're implemented.  This is what occured for
lisp.  McCarthy wanted to be able to define anonymous functions using
Church's lambda notation, and it was implemented, but since we didn't
have the language design theory about scopes and bindings, it just
happened that dynamic binding as implemented, and then somebody remarked
that this was a problem (the so called funarg problem), and they spent
ten years developing the theory and practical solution with lexical
binding.


> Or is an implementation-derived situation, i.e.
> a practical measure somewhere along the way?

Yes. 

> I once read that "the programmer has the whole program
> in his head" (pseudo-quote). That's not how
> I experience it. I have some general knowledge of the
> entire program for sure, but the only thing I have
> 100% in my head is the function or even code block I'm
> currently typing. The dynamic scope breaks that zone
> of comfort, which here, is where you want to be.

Of course. You could have the whole program in your head, when computers
had 4 Kwords of memory, and the whole program was at most a ten-page
listing.

But nowadays programs are tens of megabytes of sources!

(Firefox sources were more than 50 megabytes last time I checked; there
are more than 50 MB; emacs are 51 MB compressed!
$ ls -lh /usr/local/src/emacs-24.3.tar.gz 
-rw-r--r-- 1 pjb pjb 51M Dec  1  2013 /usr/local/src/emacs-24.3.tar.gz
I've got more than 2.5 GIGA bytes of Common Lisp libraries sources!
$ du -shc ~/quicklisp/dists/
2.6G    /home/pjb/quicklisp/dists/

Granted, this is not a single program, but a given program could use any
subset of those libraries, so it is very important to ensure
encapsulation, data hiding and locality of effects, and only lexical
binding does that, not dynamic binding.


> This "dynamic scope" as a method is like programming
> on acid with the ant queen communicating to her
> minions through telepathy telling them what to do all
> the time. "Lexical scope" is layed-back, having the
> ants do their work semi-autonomously, now and then
> interfering to solve a well-defined and delimited
> problem. ... Right?

Indeed.

A dynamic variable is global for the time of the dynamic scope.
A lexical variable is local, for the space of the lexical scope.

Notice time/space.  This is important.

Lexical means space, something that is statical and easily observable,
eternal, with delimited contours.

Dynamic means time, something that is dynamic, changing with time, and
therefore more difficult to conceptualize and observe.  We cannot
"observe" time, we have to transform it into slowly moving mechanisms,
so that we observe the SPACIAL position of the hands.  Also, it's proven
scientifically, that the brain constructs time perception in a
non monotonous and linear way (check the experience, where we flash
successive dots aligned on a screen at a given rythm, red dots on the left 
side, and
green dot on the right side.  People will tell you that the dots changed
color right in the middle between the red and green dots, which is not
possible, because they didn't know that the next dot would be green at
the time the imaginary moving dot passed on this middle!  So time is
hard on us, and dynamic is difficult to reason about, and therefore it
leads to more bugs.


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk