Discussion:
Has FUNARG ever been implemented properly?
(too old to reply)
Nils M Holm
2020-09-10 08:11:39 UTC
Permalink
While doing some research for a book, I stumbled across this:

The LISP 1 manual (p.45) and the LISP 1.5 manual (p.71) state that

apply[(FUNCTION f);x;a] = list[FUNARG;f;a]

apply[(FUNARG,f,q);x;p] = apply[f;x;q]

That is, FUNCTION is defined to create a lexical closure (FUNARG)
and when the FUNARG is evaluated, its function evaluates in the
captured environment. In other words, FUNCTION is supposed to
implement lexical scoping.

However, I have never seen this in action and in fact all examples
in the literature (the LISP manuals themselves, Weissman's LISP 1.5
Primer, etc) carefully avoid the topic. On the other hand McCarthy's
History of LISP (HOPL II) describes FUNARG exactly as above and
claims that it indeed did solve the FUNARG problem.

So the literature *so far* suggests that

(LAMBDA (X) Y) or (QUOTE (LAMBDA (X) Y)) just created a function
without capturing Y and (FUNCTION (LAMBDA (X) Y)) created a closure.

Then, however, the LISP 1.6 (PDP-6 LISP) manual states that (p.10)
FUNCTION is just equal to QUOTE and *FUNCTION is used to create
FUNARG bindings.

The MACLISP manual of 1974, finally states that (p.18)

*FUNCTION solves the downward FUNARG problem, but not the upward FP.

The consensus, of course, is that pre-Scheme LISP was dynamically
scoped and later versions used lexical scope, and this certainly
matches my experience with various dialects of LISP.

Was LISP 1.5 really ahead of its time then? Or was the FUNARG device
never properly implemented? If it was, did it work in compiled
programs? (I suspect not.)

Can enbody shed any light on the matter?
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
Jeff Barnett
2020-09-10 18:58:55 UTC
Permalink
Post by Nils M Holm
The LISP 1 manual (p.45) and the LISP 1.5 manual (p.71) state that
apply[(FUNCTION f);x;a] = list[FUNARG;f;a]
apply[(FUNARG,f,q);x;p] = apply[f;x;q]
That is, FUNCTION is defined to create a lexical closure (FUNARG)
and when the FUNARG is evaluated, its function evaluates in the
captured environment. In other words, FUNCTION is supposed to
implement lexical scoping.
However, I have never seen this in action and in fact all examples
in the literature (the LISP manuals themselves, Weissman's LISP 1.5
Primer, etc) carefully avoid the topic. On the other hand McCarthy's
History of LISP (HOPL II) describes FUNARG exactly as above and
claims that it indeed did solve the FUNARG problem.
I worked with Weissman and helped review and edit the Primer. That Lisp
did not have any gesture at lexical closures - environments were not
captured. In fact, our knowledge and interest in lexical closures was
piqued by Algol. Even the later Lisp machines lacked real lexical
closures until the move toward what was called Common Lisp started. Not
even the DARPA-sponsored Lisp 2 program dealt with lexical closures.
During the period of time I was involved -- mid 1960's to mid 1970's -
persistent lexical scoping was a hot discussion topic but it was much
too tough to provide on the minuscule machines available if one wanted
performance. There were a few experiments but lexical-first systems just
were not viable for large developments and there were many during that
period of time.
Post by Nils M Holm
So the literature *so far* suggests that
(LAMBDA (X) Y) or (QUOTE (LAMBDA (X) Y)) just created a function
without capturing Y and (FUNCTION (LAMBDA (X) Y)) created a closure.
Then, however, the LISP 1.6 (PDP-6 LISP) manual states that (p.10)
FUNCTION is just equal to QUOTE and *FUNCTION is used to create
FUNARG bindings.
The MACLISP manual of 1974, finally states that (p.18)
*FUNCTION solves the downward FUNARG problem, but not the upward FP.
The consensus, of course, is that pre-Scheme LISP was dynamically
scoped and later versions used lexical scope, and this certainly
matches my experience with various dialects of LISP.
Was LISP 1.5 really ahead of its time then? Or was the FUNARG device
never properly implemented? If it was, did it work in compiled
programs? (I suspect not.)
Can enbody shed any light on the matter?
Look at http://www.softwarepreservation.org/projects/LISP/ if you
haven't already. It makes available many early Lisp documents including
listings of some implementations.
--
Jeff Barnett
Zyni Moë
2020-09-10 20:29:15 UTC
Permalink
Post by Jeff Barnett
I worked with Weissman and helped review and edit the Primer.
This is why usenet is not dead. Thank you.
--
the small snake
Nils M Holm
2020-09-12 08:41:45 UTC
Permalink
Post by Jeff Barnett
Post by Nils M Holm
The LISP 1 manual (p.45) and the LISP 1.5 manual (p.71) state that
apply[(FUNCTION f);x;a] = list[FUNARG;f;a]
apply[(FUNARG,f,q);x;p] = apply[f;x;q]
I worked with Weissman and helped review and edit the Primer. That Lisp
did not have any gesture at lexical closures - environments were not
captured.
Interesting! This is what I suspected, but then the manual claimed
that the FUNARG problem was solved. It is a rather simple fix, too,
at least in a deep-binding interpreter, so I thought it might have
been possible.
Post by Jeff Barnett
During the period of time I was involved -- mid 1960's to mid 1970's -
persistent lexical scoping was a hot discussion topic but it was much
too tough to provide on the minuscule machines available if one wanted
performance. There were a few experiments but lexical-first systems just
were not viable for large developments and there were many during that
period of time.
That's why I thought that IF the FUNARG device had worked, it probably
would have worked only in the interpreter. Lexical scoping is much harder
to implement when done efficiently (i.e. with shallow-binding and/or
compiled code). It is surprising to hear that LISP 1.5 does not follow
its specification, though!
Post by Jeff Barnett
Look at http://www.softwarepreservation.org/projects/LISP/ if you
haven't already. It makes available many early Lisp documents including
listings of some implementations.
Thanks!

I have lots of printed or photocopied manuals here as well as some
gigbytes of documents downloaded from the Software Preservation Group
and bitsavers.org. The overall picture is pretty clear and reflects
what you have explained above, but then the definition of FUNCTION and
FUNARG in the LISP 1.x manuals caught my attention.
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
Jeff Barnett
2020-09-12 19:26:17 UTC
Permalink
Post by Nils M Holm
Post by Jeff Barnett
Post by Nils M Holm
The LISP 1 manual (p.45) and the LISP 1.5 manual (p.71) state that
apply[(FUNCTION f);x;a] = list[FUNARG;f;a]
apply[(FUNARG,f,q);x;p] = apply[f;x;q]
I worked with Weissman and helped review and edit the Primer. That Lisp
did not have any gesture at lexical closures - environments were not
captured.
Interesting! This is what I suspected, but then the manual claimed
that the FUNARG problem was solved. It is a rather simple fix, too,
at least in a deep-binding interpreter, so I thought it might have
been possible.
Post by Jeff Barnett
During the period of time I was involved -- mid 1960's to mid 1970's -
persistent lexical scoping was a hot discussion topic but it was much
too tough to provide on the minuscule machines available if one wanted
performance. There were a few experiments but lexical-first systems just
were not viable for large developments and there were many during that
period of time.
That's why I thought that IF the FUNARG device had worked, it probably
would have worked only in the interpreter. Lexical scoping is much harder
to implement when done efficiently (i.e. with shallow-binding and/or
compiled code). It is surprising to hear that LISP 1.5 does not follow
its specification, though!
Post by Jeff Barnett
Look at http://www.softwarepreservation.org/projects/LISP/ if you
haven't already. It makes available many early Lisp documents including
listings of some implementations.
Thanks!
I have lots of printed or photocopied manuals here as well as some
gigbytes of documents downloaded from the Software Preservation Group
and bitsavers.org. The overall picture is pretty clear and reflects
what you have explained above, but then the definition of FUNCTION and
FUNARG in the LISP 1.x manuals caught my attention.
Back in the 1960's Bouroughs corporation made Algol machines where the
lexical scoping was "built in the hardware". They had "display"
registers were one pointed at a lexical frame on the stack. There were
separate back pointers for program flow and scope flow. For example: if
you recurred through a routine, the immediate scope and return pointed
at different blocks. These machines were made almost specifically for
banks! Though others could buy them. If memory serves me correctly, you
could not lift a closure beyond where it was defined. I think the Algol
feature that invoked all of this magic was "call by name".

The historical significance of all this is that the Lisp machines were
not the first to support a specific high level language. For those
considering the truth of this statement, I do not consider FORTRAN or
COBOL high level languages.
--
Jeff Barnett
Tom Russ
2020-09-15 20:34:01 UTC
Permalink
Post by Jeff Barnett
Back in the 1960's Bouroughs corporation made Algol machines where the
lexical scoping was "built in the hardware". They had "display"
registers were one pointed at a lexical frame on the stack. There were
separate back pointers for program flow and scope flow. For example: if
you recurred through a routine, the immediate scope and return pointed
at different blocks. These machines were made almost specifically for
banks! Though others could buy them. If memory serves me correctly, you
could not lift a closure beyond where it was defined. I think the Algol
feature that invoked all of this magic was "call by name".
...
Jeff Barnett
Thanks for bringing this up, Jeff.
I do remember that terminology for the Algol closures. And if memory serves,
the mechanism for implementing "call by name" was called "Thunks". And it
sounds like it just solved the downward funarg problem.

I do recall thinking at the time that the entire funarg problem was some weird,
esoteric problem that only a few computer scientists would ever care about.
But I was just a freshman [1st year] student, so without any real experience.

The downward funarg was much easier to solve. It is interesting to see that
this fairly recently made its way into C++ via lambda functions with variable
capture syntax. Which still doesn't solve the upward funarg problem unless
you take special care to set things up just right. And in typical C++ fashion,
the first indication that you may have done this wrong is a seg fault.
none) (albert
2020-09-16 09:36:44 UTC
Permalink
Post by Tom Russ
Post by Jeff Barnett
Back in the 1960's Bouroughs corporation made Algol machines where the
lexical scoping was "built in the hardware". They had "display"
registers were one pointed at a lexical frame on the stack. There were
separate back pointers for program flow and scope flow. For example: if
you recurred through a routine, the immediate scope and return pointed
at different blocks. These machines were made almost specifically for
banks! Though others could buy them. If memory serves me correctly, you
could not lift a closure beyond where it was defined. I think the Algol
feature that invoked all of this magic was "call by name".
...
Jeff Barnett
Thanks for bringing this up, Jeff.
I do remember that terminology for the Algol closures. And if memory serves,
the mechanism for implementing "call by name" was called "Thunks". And it
sounds like it just solved the downward funarg problem.
You can just say Algol. The differences between Algol 60 and Algol 68
are dramatic. Algol 68 sports call by value only (actually the only sane
calling method IMO), but it has references (type pointers if you will).
Post by Tom Russ
I do recall thinking at the time that the entire funarg problem was some weird,
esoteric problem that only a few computer scientists would ever care about.
But I was just a freshman [1st year] student, so without any real experience.
The downward funarg was much easier to solve. It is interesting to see that
this fairly recently made its way into C++ via lambda functions with variable
capture syntax. Which still doesn't solve the upward funarg problem unless
you take special care to set things up just right. And in typical C++ fashion,
the first indication that you may have done this wrong is a seg fault.
I quote from the govolisp manual I'm currently studying for the simple
implementation it describes:
(govolisp was an early educational lisp)

"
In practice the functional argument problem is not serious.
Displicine and due care in choosing names is all that is needed
to avoid trouble.
"

The author continues by rejecting a solution where "the association list
.. lower priority " .

Comment any one?

Am I right that the problem becomes serious whenever there is a large
implementation with contributions of numerous authors (e.g. clisp) and
you want to keep naive users out of trouble?

Groetjes Albert
--
This is the first day of the end of your life.
It may not kill you, but it does make your weaker.
If you can't beat them, too bad.
***@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
Nils M Holm
2020-09-16 10:23:36 UTC
Permalink
I quote from the govolisp manual [...]
"
In practice the functional argument problem is not serious.
Displicine and due care in choosing names is all that is needed
to avoid trouble.
"
[...]
Am I right that the problem becomes serious whenever there is a large
implementation with contributions of numerous authors (e.g. clisp) and
you want to keep naive users out of trouble?
The upward FUNARG problem is easily avoided by never returning
functions from functions, which was rarely done in dynamically
scoped LISP anyway.

The downward FUNARG problem is a different beast, though. Have a look
at the following function:

(DEFUN MAP-LIST (F X)
(COND ((NULL X) NIL)
(T (CONS (FUNCALL F X) (MAP-LIST F (CDR X))))))

This is a naive implementation of MAPLIST. The following expression
uses it to replace every member of a list with the atom FOO:

((LAMBDA (X)
(MAP-LIST (LAMBDA (Y) X) (QUOTE (A B C))))
(QUOTE FOO))

It works fine in lexically scoped LISP, but in a dynamically scoped
system the downward FUNARG problem will bite you, because it binds
the free variable X to a different value in MAP-LIST.

I would say that no sane amount of discipline and due care will help
you anticipate this case.
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
none) (albert
2020-09-16 12:04:48 UTC
Permalink
Post by Nils M Holm
I quote from the govolisp manual [...]
"
In practice the functional argument problem is not serious.
Displicine and due care in choosing names is all that is needed
to avoid trouble.
"
[...]
Am I right that the problem becomes serious whenever there is a large
implementation with contributions of numerous authors (e.g. clisp) and
you want to keep naive users out of trouble?
The upward FUNARG problem is easily avoided by never returning
functions from functions, which was rarely done in dynamically
scoped LISP anyway.
The downward FUNARG problem is a different beast, though. Have a look
(DEFUN MAP-LIST (F X)
(COND ((NULL X) NIL)
(T (CONS (FUNCALL F X) (MAP-LIST F (CDR X))))))
This is a naive implementation of MAPLIST. The following expression
((LAMBDA (X)
(MAP-LIST (LAMBDA (Y) X) (QUOTE (A B C))))
(QUOTE FOO))
It works fine in lexically scoped LISP, but in a dynamically scoped
system the downward FUNARG problem will bite you, because it binds
the free variable X to a different value in MAP-LIST.
I would say that no sane amount of discipline and due care will help
you anticipate this case.
I have a hard time with this. LISP is supposedly mathematically inclined.

(lambda (x) (+ x x))
represents a function (one could call twice) which is the infinite set of
{ integer x : x,2.x }
Applying the function to a number 12 means selecting the pair 12,24
then selecting the second part.
So the x in the set representation is only there to have a handle to
be able to express and could be replaced by any other symbol.

Likewise the choice of y in
(lambda (y) (+ y y))
should play no role in what the expression represents.
(I can see that the expression represents something different in
a context where '+' represents something different.)

Groetjes Albert
Post by Nils M Holm
--
--
This is the first day of the end of your life.
It may not kill you, but it does make your weaker.
If you can't beat them, too bad.
***@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
Zyni Moë
2020-09-16 13:09:22 UTC
Permalink
Post by none) (albert
I have a hard time with this. LISP is supposedly mathematically inclined.
Yes it is.
Post by none) (albert
(lambda (x) (+ x x))
represents a function (one could call twice) which is the infinite set of
{ integer x : x,2.x }
Applying the function to a number 12 means selecting the pair 12,24
then selecting the second part.
Nearly. Function like this has one free variable, which is +: need to know
what + refers to to know what function means. If assume that + (and other
arithmetic operators) are defined by the language (so not pure lambda
calculus but lambda calculus with arithmetic and number literals perhaps),
then has no free variables.

This function is equal in language to (lambda (y) (+ y y)).

Functions without free variables are never a problem. Also boring.

These were not functions in example though. Functions in example were like

(lambda (x) (+ x y))

This function has free variable which is y. Funarg problem is about
decidign what that y refers to. So in example:

((LAMBDA (X)
(MAP-LIST (LAMBDA (Y) X) '(A B C)))
'FOO)

Then free X in (LAMBDA (Y) X) refers initially to X bound in outer LAMBDA.
But in dynamically scoped Lisp with implementation of MAP-LISP given in
example it later refers to some other value.

And in form like

(((lambda (x) (lambda (y) (+ y x))) 1) 2)

Seems obvious what binding of x in inner lambda refers to, but in
dynamically scoped lisp is not obvious at all and in fact assuming no
top-level binding of x this call is error, because is upward funarg here.
--
the small snake
Stefan Monnier
2020-09-16 13:50:14 UTC
Permalink
Post by Nils M Holm
The upward FUNARG problem is easily avoided by never returning
functions from functions,
And never placing functions inside of a data-structure either, nor
assigning them to a global (or "less local") variable.
Post by Nils M Holm
I would say that no sane amount of discipline and due care will help
you anticipate this case.
There are conventions you can follow to minimize such risks, tho (mostly
using "funny names" for all vars which you know rely on dynamic scoping,
as well as using "funny names" for all local vars of higher-order
functions (such as your `map-list`)).


Stefan
Zyni Moë
2020-09-16 14:10:34 UTC
Permalink
Post by Stefan Monnier
There are conventions you can follow to minimize such risks, tho (mostly
using "funny names" for all vars which you know rely on dynamic scoping,
as well as using "funny names" for all local vars of higher-order
functions (such as your `map-list`)).
Dynamic scope means hygiene problems have leaked from macros out into
functions and are now metre deep tide all over floor, really. Dynamic
scope and lisp-1 means you must swim in leakage or often drown.
--
the small snake
Nils M Holm
2020-09-16 15:16:06 UTC
Permalink
Post by Stefan Monnier
There are conventions you can follow to minimize such risks, tho (mostly
using "funny names" for all vars which you know rely on dynamic scoping,
as well as using "funny names" for all local vars of higher-order
functions (such as your `map-list`)).
The benefit of such conventions is limited in my experience, though
(and I have used them a lot). Either you prefix the names with the
full function name (MAP-LIST-F, MAP-LIST-X), which makes the code
completely unintelligible or you use a more neutral prefix like % and
hope that it never appears in user code, thereby merely postponing
the inevitable. The full-function-name approach works well for *some*
local variables, though.

What else could you do?
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
Stefan Monnier
2020-09-16 17:39:56 UTC
Permalink
Post by Nils M Holm
Post by Stefan Monnier
There are conventions you can follow to minimize such risks, tho (mostly
using "funny names" for all vars which you know rely on dynamic scoping,
as well as using "funny names" for all local vars of higher-order
functions (such as your `map-list`)).
The benefit of such conventions is limited in my experience, though
(and I have used them a lot). Either you prefix the names with the
full function name (MAP-LIST-F, MAP-LIST-X), which makes the code
completely unintelligible or you use a more neutral prefix like % and
hope that it never appears in user code, thereby merely postponing
the inevitable.
In ELisp we used such "full function name prefix" and it worked fine.
It's only needed for higher-order functions, which are/were in
the minority.
Post by Nils M Holm
What else could you do?
Use a more sane scoping rule ;-) ?
Post by Nils M Holm
Dynamic scope means hygiene problems have leaked from macros out into
functions and are now metre deep tide all over floor, really.
Our 30 years of experience with it in Emacs Lisp indicates that it's
surprisingly manageable.

Don't take me wrong: I *much* prefer static scoping, as attested by the
role I played in the addition of static scoping to Emacs Lisp in
Emacs-24. But in such a Lisp-2 context, dynamic scoping is very much
usable. The real pain with dynamic scoping was not the risk of name
conflicts but the lack of closures (i.e. "upward funargs").
Post by Nils M Holm
Dynamic scope and lisp-1 means you must swim in leakage or
often drown.
Indeed Lisp-1 would make dynamic scoping significantly more painful.
I don't have any experience with such a setup, but I guess to be usable
you'd need not just good conventions but probably something like a good
module system.


Stefan
Zyni Moë
2020-09-16 19:47:13 UTC
Permalink
Post by Stefan Monnier
Our 30 years of experience with it in Emacs Lisp indicates that it's
surprisingly manageable
Manageable like recurrent malaria, yes: most of the time you are OK,
sometimes ill, only occasionally actually die.
Post by Stefan Monnier
Indeed Lisp-1 would make dynamic scoping significantly more painful.
I don't have any experience with such a setup, but I guess to be usable
you'd need not just good conventions but probably something like a good
module system.
Ha. Standard Lisp did not have module system. What saved you was that
compiler did not actually do dynamic scope: bindings from fn args and PROG
were not fluid when compiled (think Lisp 1.5 was the same). Was
entertaining in very bad way when you had binding called CAR and loaded
system interpreted to debug. Watch the disk light come on as lisp image
slowly ate all your virtual memory, run from angry users.
--
the small snake
Jeff Barnett
2020-09-16 21:38:55 UTC
Permalink
Post by Zyni Moë
Post by Stefan Monnier
Our 30 years of experience with it in Emacs Lisp indicates that it's
surprisingly manageable
Manageable like recurrent malaria, yes: most of the time you are OK,
sometimes ill, only occasionally actually die.
Post by Stefan Monnier
Indeed Lisp-1 would make dynamic scoping significantly more painful.
I don't have any experience with such a setup, but I guess to be usable
you'd need not just good conventions but probably something like a good
module system.
Ha. Standard Lisp did not have module system. What saved you was that
compiler did not actually do dynamic scope: bindings from fn args and PROG
were not fluid when compiled (think Lisp 1.5 was the same). Was
entertaining in very bad way when you had binding called CAR and loaded
system interpreted to debug. Watch the disk light come on as lisp image
slowly ate all your virtual memory, run from angry users.
Incorrect. Lisp 1.5 compilers - the several I'm familiar with or wrote -
did do dynamic/fluid/special bindings if variables were so declared. The
rest of the scoping was what I called "local". not lexical. Variables so
classed were not closed over in any way and embedded lambda forms could
not see these lexically apparent variables at all. If they needed to be
visible downward, you would use a macro that created a special with a
non global declaration or gensym name. Yech. The machines, particularly
their memories, were so small that managing and keeping stack blocks
around was just too big a burden. Interpreters could play these games if
desired since nobody expected spectacular performance.
--
Jeff Barnett
Zyni Moë
2020-09-17 07:37:30 UTC
Permalink
Post by Jeff Barnett
Incorrect. Lisp 1.5 compilers - the several I'm familiar with or wrote -
did do dynamic/fluid/special bindings if variables were so declared. The
rest of the scoping was what I called "local". not lexical. Variables so
classed were not closed over in any way and embedded lambda forms could
not see these lexically apparent variables at all. If they needed to be
visible downward, you would use a macro that created a special with a
non global declaration or gensym name. Yech. The machines, particularly
their memories, were so small that managing and keeping stack blocks
around was just too big a burden. Interpreters could play these games if
desired since nobody expected spectacular performance.
Yes, sorry I was not clear: this is mostly what standard lisp did too: you
could declare variables as fluid (think only globally fluid) which was like
special, which made them dynamic in compiled code too. Default was fluid
in interpreter and local in compiler. Don't remember if local vars were
visible to lambdas, probably not though. As well there were globals which
you could not bind. I knew that you could say things were special in Lisp
1.5 even in the compiled code I think (never used anything that old
though).
--
the small snake
His Kennyness
2020-09-15 02:25:05 UTC
Permalink
Post by Jeff Barnett
Look at http://www.softwarepreservation.org/projects/LISP/ if you
haven't already. It makes available many early Lisp documents including
listings of some implementations.
Why was I not told about this ^^^^^ ?!!

What an amazing resource. Thx for the reference!

-hk
luserdroog
2020-09-15 04:01:45 UTC
Permalink
Post by His Kennyness
Post by Jeff Barnett
Look at http://www.softwarepreservation.org/projects/LISP/ if you
haven't already. It makes available many early Lisp documents including
listings of some implementations.
Why was I not told about this ^^^^^ ?!!
What an amazing resource. Thx for the reference!
-hk
Just in case, there's also the manx archive.

https://manx-docs.org/help.php

Similar stuff with some differences.
Loading...