Re: Lambda calculus and it relation to LISP

[Gareth.McCaughan@pobox.com (Gareth McCaughan)]

"gnuist" wrote:

> You guys obviously are very talented in lisp. For me to benefit from
> your posts, which certainly seem of great promise to me due to my inability
> to actually analyze them, I need to bridge the gap from where I am and
> what they propound. It will require me to put more effort. Here is what I
> have to show and then perhaps you can fill in with your explanations and
> what I most request is a concrete example to be able to run on emacs via
> its interpreter. Even if you answer one question in depth, it is better
> than many superficially.

Lambda calculus was never particularly intended to be
a thing for running on computers in general, or in Emacs
in particular. There *were* no computers, I think, when
Church started working on the lambda calculus.

> OK. I have gotten a bibliography of lisp papers. I drove to a library and
> got hold of a section of lisp in honor of jm which has a micro-manual for
> lisp and a single page eval on p712. I know basic car/cdr/cons and the
> notion of list being isomorphic to binary tree. Probably the idea is to have
> pre-parsed expression just as the emacs' delimited prefix notation is
> pre-associated and precedence-explicit, making interpreter simple and less
> on the BNF notation and FiniteStateMachine formalism. I am not a CS so please
> do not throw indigestible theoretical rocks w/o concrete examples at me.

Yes, the idea is as you say. (But I think it would be
a little more accurate to say: originally, parsing wasn't
even a part of McCarthy's concern, any more than when
you talk about arithmetic you're usually thinking about
how to convert strings of decimal digits into actual
numbers.)

> Now I have seen examples of lambda where it is used to associate a hook with
> the anonymous function. I do not see what advantage this gives over defun
> other than saving a name in the name-space. Is there any other advantage
> of lambda? Or is defun defined using lambda and name associating function?

Hmm, OK. At this point what you're talking about really
isn't "the lambda calculus"; that was one of the points
I was making (and William Elliot too, I think). It's just
a notation for functions that happens to use the word
"lambda". This isn't a problem, by the way, but it's
worth being aware of it.

The advantage of making anonymous functions is threefold.

1. As you say, it saves a name which would otherwise
   clutter up some namespace or other.

2. It's more compact.

3. It lets you define the function where it's being used,
   rather than putting it somewhere else and making the
   reader check back for the definition.

As for how DEFUN is defined: I'm not sure about Emacs,
and I'm too lazy to check :-), but in the Common Lisp
implementation I use, DEFUN is a macro whose uses expand
to things like

    (C::%DEFUN 'F #'(LAMBDA () (BLOCK F 123)) NIL '(DEFUN F () 123))

where C::%DEFUN is a plain ol' function, which associates
a function (and a bit of other stuff) with a name.

> The Lisp papers talk of "LABEL" function. But where is it in emacs or what
> is its emacs counterpart called?

Emacs doesn't have LABELS. There's a "cl" package -- do
(require 'cl) -- that probably defines it for you.

> Here is a lambda function that I know for starters.
> 
> ( (lambda(x y) (- x y))  1 2)
> 
> I can write more complicated defuns, single recursion, gcd, and all classic
> stuff. But I am looking for a particularly instructive and clear example
> of a double recursion and then probably a tricky one.
> 
> In the same way I ask for GRADED examples of use of lambda. I am sure many
> of you can just cut and paste from your collection. Examples to illustrate
> recursion, etc. And how will you do recursion without/with "LABEL"?

There are ways to do recursion using just LAMBDA; see the
bizarre-looking things a few people have posted earlier
in the thread. They've usually used LET, which elisp
has, but in any case the LETs can be replaced with LAMBDAs
by rearranging a little. I think you'd need to insert
FUNCALL in quite a lot of places to make that trick work
in elisp. Anyway, it's the Wrong Answer (tm).

The Right Answer (tm) is: If you want recursion, then
either (require 'cl) and use the LABELS macro defined
there, or else give your functions names using DEFUN.

> One last question at this stage: I know how you "add-hook" but how do you
> create a hook variable in the first place? Is it something particular to
> emacs or is it only a lispy object? And a little aside: Can one create
> something close to this in C/C++/Java?

The word "hook" has more than one meaning.

1. Anything that lets you specify something that should
   happen on particular occasions, thus extending the
   functionality of a system someone else has built.

   Hooks in *this* sense can be found all over the place;
   certainly not only in Lisp and similar languages. For
   instance, the atexit function in C's standard library
   is for defining hooks.

2. A variable containing a list of functions or function names,
   which will be called in particular circumstances.

   This meaning is, I think, peculiar to Emacs, though
   it's a straightforward enough way to do hooks (in
   sense 1) that I won't be surprised if it's found
   elsewhere.

Yes, you can create hook-y things in C or C++ or Java.
Here it is in C, for instance:

    typedef struct Hook Hook;
    struct Hook {
      void (*f)(void *);
      Hook * next;
    };

    void run_hook_functions(const Hook * h, void * context) {
      while (h) {
        h->f(context);
        h = h->next;
      }
    }

    Hook * add_to_hook(Hook * h, void (*f)(void *)) {
      Hook * result = safe_malloc(sizeof(Hook));
      result->f = f;
      result->next = h;
      return result;
    }

    #define ADD_HOOK(h,f) ((h)=add_to_hook((h),(f)))

It's more pleasant to do this sort of thing in Lisp-like
languages, though. Partly because you have anonymous
functions, partly because -- at least in better Lisps
than elisp -- your functions are actually closures (which
means, e.g., that you don't need the context argument
nonsense found above).

-- 
Gareth McCaughan  Gareth.McCaughan@pobox.com
.sig under construc