Why distinct namespaces?
Axel Schairer
I remember having read a discussion of pros and cons of having
different namespaces for variables and named functions; and why it was
actually a good thing to have these different namespaces. But I cannot
remember where. Does anyone have a pointer (or an opinion for that
matter)?
Thanks in advance,
Axel
=== Axel Schairer, http://www.dfki.de/vse/staff/schairer/ ===
More detailed: Scheme and CL differ in that in CL a symbol is
evaluated differently depending on whether it is the first element of
a form or not, i.e. the first occurence of f in `(f f)' evaluates to
the doubling function, whereas the second one evaluates to 5:
(defvar f 5)
(defun f (x) (* 2 x))
(f f) => 10
This implies that to apply a named function one simply writes its
name, whereas to apply a function stored in a variable, one has to
write something like
(defvar a (list #'(lambda (x) (* 2 x))) ...)
(funcall (first a) 3) => 6
instead of simply `((first a) 3)'. This can clutter code considerably.
Kent M Pitman
In article <33B37B...@dfki.uni-sb.de> Axel Schairer
<scha...@dfki.uni-sb.de> writes:
Axel> I remember having read a discussion of pros and cons of having
Axel> different namespaces for variables and named functions; and why
Axel> it was actually a good thing to have these different
Axel> namespaces. But I cannot remember where. Does anyone have a
Axel> pointer (or an opinion for that matter)?
In Vol I, No. 1 of Lisp and Symbolic Computation (LASC), Dick Gabriel
and I published a paper on this matter. "Technical Issues In The
Separation of Function Cells and Value Cells". This was a trimmed
down and cleaned up version of a document that we used in discussing
the issue for X3J13 (designing ANSI Common Lisp).
Although not stated explicitly in the paper, Gabriel took the position
that merging the namespaces was good; I took the position it was bad.
I hold to that position.
I'll make a note to do a Parenthetically Speaking article on this issue,
which I've long regretted not doing. Because the paper Gabriel and I
did tried to look balanced, neither of us got to make our points as
clearly as perhaps we should have.
Axel> (funcall (first a) 3) => 6
Axel> instead of simply `((first a) 3)'. This can clutter code considerably.
Language features should NEVER be compared in the abstract.
Languages are ecosystems and one must look at the features that make
them up in the context of the service they provide to typical users of
the language.
Scheme programmers generally prefer passing functions, but Lisp
programmers generally do not. This came up over and over in the design
of CL and the community presented itself as very shy about excess
emphasis of functional abstraction. Consequently, among other things,
Lisp programmers worry that
((first a) 3)
might be an editing error. It's really very very unusual to get a list
of functions as an argument in Lisp, and not just because (as Scheme
programmers would rush to assert) we make it hard to program with functions.
Writing one extra funcall is not exactly an overwhelming burden for as
often as this situation comes up. The REAL TRUTH is that it's a good
property of a language that it flags the unusual explicitly, and it's a
good property of a language when it is `sparse enough' in what's "defined"
that you can recognize a programming error easily. Teco and APL are
examples of languages that are "not sparse"; just about any character string
is "defined". This means programs can run well beyond the point of an error
before you find that an error has occurred because so many things are
valid programs. In Lisp, (funcall (first a) 3) is not viewed as clutter
because it announces the unusual case of A holding a list of functions and says
"yes, I really want to funcall this." In Scheme, that may be more normal,
so it's appropriate for there to be more checking.
Note also that nothing ever comes for free in a design choice.
It's a common source of programmer error in Scheme to write a long
function that says
(DEFINE (MY-SORT LIST ...)
... lots of code ...
... (SET! TEMP (LIST A B)) ...)
forgetting that LIST was bound, and so you end up funcalling your
bound variable. This doesn't tend to happen in Lisp. Lisp
programmers often hate how ugly Scheme programs look with people
misspelling variables all over the place to avoid name collisions.
I never hesitate to write:
(DEFUN MY-SORT (LIST FUNCTION) ...)
But the seasoned programmer will start out misspelling things just to avoid
name collisions:
(DEFINE (MY-SORT LST FNCTN) ...)
This is a price which must be attributed directly to the merged namespace,
and it's not a price I like.
There are several other reasons as well... some are not just aesthetic
but technical. I'll write them up and send you a pointer.
Juergen Nickelsen
Kent M Pitman <pit...@world.std.com> wrote:
> There are several other reasons as well... some are not just aesthetic
> but technical. I'll write them up and send you a pointer.
Could you send a pointer to the group as well? I used to prefer Scheme's
shared namespace for variables and functions, but your arguments make me
doubt. Is the article you wrote with Richard Gabriel available on the
net?
--
Juergen Nickelsen
Richard A. O'Keefe
pit...@world.std.com (Kent M Pitman) writes:
>It's a common source of programmer error in Scheme to write a long
>function that says
> (DEFINE (MY-SORT LIST ...)
> ... lots of code ...
> ... (SET! TEMP (LIST A B)) ...)
>forgetting that LIST was bound, and so you end up funcalling your
>bound variable.
This is an error that every Schemer makes *once*.
>I never hesitate to write:
> (DEFUN MY-SORT (LIST FUNCTION) ...)
Oh _dear_. But 'list' is such a _dreadful_ name. What's it a list _of_?
>But the seasoned programmer will start out misspelling things just to avoid
>name collisions:
> (DEFINE (MY-SORT LST FNCTN) ...)
Wrong. The seasoned programmer will start out spelling out *meaningful*
names where medium to long names are needed. For example, someone (me)
defining a sorting function might write
(define (my-sort Sequence Less?) ...)
or
(define (my-sort Items Compare) ...)
where "Compare" is a heck of a lot more informative than "FUNCTION".
>This is a price which must be attributed directly to the merged namespace,
>and it's not a price I like.
The price is not exactly what you say it is. The real price is the cost
of producing *better* names.
>There are several other reasons as well... some are not just aesthetic
>but technical. I'll write them up and send you a pointer.
I was under the impression that one of the original motivations for the
name-space split was that Interlisp did *different* spelling correction
depending on the context of the misspelled identifier: if you misspelled
an identifier in function position, it tried to correct it to a function.
--
Four policemen playing jazz on an up escalator in the railway station.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.
Kent M Pitman
In article <5pfff8$4nk$1...@goanna.cs.rmit.edu.au>
o...@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
> > (DEFUN MY-SORT (LIST FUNCTION) ...)
>
> Oh _dear_. But 'list' is such a _dreadful_ name. What's it a list _of_?
It doesn't pre-suppose what it's a list of. That's why it takes a function
to use as a sort predicate. SORT is a completely general utility.
> Wrong. The seasoned programmer
I promise you, I'm a seasoned programmer.
> will start out spelling out *meaningful*
> names where medium to long names are needed. For example, someone (me)
> defining a sorting function might write
>
> (define (my-sort Sequence Less?) ...)
The name sequence is also taken by Common Lisp, btw. Fortunately, this
set of namings would work in Common Lisp, though, since multiple namespaces
protect you from having to know that (even without a hygienic macro system).
> or (define (my-sort Items Compare) ...)
>
> where "Compare" is a heck of a lot more informative than "FUNCTION".
Well, I'm not going to make the argument that there is never a more informative
name (even if I don't think Compare is it--Less? might be closer), but my point
is entirely made by having LIST be the right name. A more general name is not
required, and in fact ITEMS and SEQUENCE are both less informative.
> >This is a price which must be attributed directly to the merged namespace,
> >and it's not a price I like.
>
> The price is not exactly what you say it is. The real price is the cost
> of producing *better* names.
For you to score a debate point on this, you would have to show not that there
exists a better name than some name I chose, but rather that for all possible
name choices, the name of a globally defined function will never be the name
that is most informative. I don't think you can do that, so I'll rest easy.
> >There are several other reasons as well... some are not just aesthetic
> >but technical. I'll write them up and send you a pointer.
>
> I was under the impression that one of the original motivations for the
> name-space split was that Interlisp did *different* spelling correction
> depending on the context of the misspelled identifier: if you misspelled
> an identifier in function position, it tried to correct it to a function.
Because of the way these languages evolved, I'm sure you have the
causality backwards. CL is a Maclisp descendant, and Maclisp is not
an Interlisp descedant. I believe they both came out of some earlier
(pre-DWIM) dialect, but I'm not sure which. I'm sure some other
lurker on this list will say--it might have been BBN Lisp. Anwyay,
I'm pretty confident spelling correction was not an issue in the
original design.
However, I also was not talking about writing up reasons the decision
HAD been made. I was talking about wirting up the reasons why it was a
good decision regardless of why it was made.
Surely, there are some reasons favoring single namespace as well,
especially in Scheme. We did some "clever" things with it in T (Yale
Scheme) that could not have been done in multinamespace Lisps. But
there are things you can do in multinamespace Lisps that you can't do
in single namespace Lisps. Never assume any design decision is
automatically right independent of its context. Language design, like
most other kinds of design, is a process of trade-offs -- of
optimization in a huge multi-dimensinoal space that defies total
optimization. Nothing ever comes for free. People who criticize
multiple namespaces are always concerned with what is lost; I don't
deny things are lost. I'm just saying there are things you gain, too.
It was not simply a choice made by idiots waiting to be fixed as a
no-brainer. Backward-compatibility is not all that invites a
continuation of the status quo.
Tim Olson
In article <1997070201...@n245-146.berlin.snafu.de>
jnick...@acm.org (Juergen Nickelsen) writes:
> Kent M Pitman <pit...@world.std.com> wrote:
>
> > There are several other reasons as well... some are not just aesthetic
> > but technical. I'll write them up and send you a pointer.
>
> Could you send a pointer to the group as well? I used to prefer Scheme's
> shared namespace for variables and functions, but your arguments make me
> doubt. Is the article you wrote with Richard Gabriel available on the
> net?
>
> --
> Juergen Nickelsen
In his book "Lisp In Small Pieces", Queinnec points out that in "Lisp2"
(separate function and variable namespaces), it is easier to create
efficient function calls, because direct modification of the function
environment is not possible (no assignment form). Thus, compilers can
inline function calls where applicable without having to worry about
global binding changes.
-- Tim Olson
Apple Computer, Inc.
(t...@apple.com)
Vassil Nikolov
Tim Olson wrote:
>
> In his book "Lisp In Small Pieces", Queinnec points out that in "Lisp2"
> (separate function and variable namespaces), it is easier to create
> efficient function calls, because direct modification of the function
> environment is not possible (no assignment form). Thus, compilers can
> inline function calls where applicable without having to worry about
> global binding changes.
>
Yes!
I would also like to put it in this way:
in Lisp, there are two cells associated with each symbol:
cell A cell B
is: settable bindable
holds: function value
accessible in: O(1) time implementation-dependent
From memory, the standard leaves the consequences of
storing a non-function in the function cell undefined;
it is only the function cell that is guaranteed to be
accessible in constant time, at the expense of being
out of reach for the binding mechanism. (Please note
that binding with LET is *not* simply
(UNWIND-PROTECT
(PROGN
(SETF saved-value variable
variable new-value)
...body...
)
(SETF variable saved-value)
)
since you might have deep binding.)
--
Vassil Nikolov, visitor at LRI:
Laboratoire de Recherche en Informatique, Universite Paris-Sud
Until 9 July 1997: Vassil....@lri.fr
Normally: vnik...@bgearn.acad.bg
Barry Margolin
In article <5pjd1b$imt$1...@cerberus.ibmoto.com>, Tim Olson <t...@apple.com> wrote:
]In his book "Lisp In Small Pieces", Queinnec points out that in "Lisp2"
](separate function and variable namespaces), it is easier to create
]efficient function calls, because direct modification of the function
]environment is not possible (no assignment form). Thus, compilers can
]inline function calls where applicable without having to worry about
]global binding changes.
Huh? What about (setf (symbol-function <exp1>) <exp2>)?
This allows you to change a function binding. And if <exp1> isn't a
constant, the compiler won't be able to determine what functions might be
modified.
ANSI Common Lisp has some wording that allows compilers to assume that the
programmer isn't redefining his functions dynamically without warning the
compiler (via NOTINLINE declarations). This allows block compilation.
--
Barry Margolin, bar...@bbnplanet.com
BBN Corporation, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Kent M Pitman
In article <5pjsmk$6...@pasilla.bbnplanet.com> Barry Margolin
<bar...@bbnplanet.com> writes:
> In article <5pjd1b$imt$1...@cerberus.ibmoto.com>, Tim Olson
> <t...@apple.com> wrote:
>
> ] Thus, compilers can inline function calls where applicable without
> ] having to worry about global binding changes.
>
> Huh? What about (setf (symbol-function <exp1>) <exp2>)?
No, Barry, unless I'm confused too, you missed his point, which is not
really about the extraction of the DATA but rather about the
type-testing of the extracted data to be sure it's a function that can
really be jumped to.
In a Lisp1 (the term I coined in the paper I wrote with Gabriel for
the class of languages that, like Scheme, have only one namespace),
you cannot type-check a global variable FOO to see if it's a function
because there is only one kind of variable and you have to assume it
can be used for any kind of data. So if/when you do (FOO X) you have
to type-check it there [unless by some luck you have managed to
type-propagate the necessary type information at compile time; hard to
do with modular compilation] or else you cannot risk jumping directly
to it to be executed, only to find it's not executable. This slows
function call.
But in a Lisp2 (a Lisp dialect with two namespaces), you can declare
that the function namespace must only contain functions, and so you
can test this at storage time rather than access time, so you can get
better efficiency (if you think storage happens less often than
access, which I think is a good guess).
Scheme (the predominant Lisp1) also avoids declarations, so they can't
type-declare individual variables to be restricted to type FUNCTION,
which would help to alleviate this inefficiency. You can, of course,
declare a variable to be a constant, and that gets a lot of the common
cases. But there are still places where you lose.
Barry Margolin
In article <sfw3epu...@world.std.com>,
>the class of languages that, like Scheme, have only one namespace),
>you cannot type-check a global variable FOO to see if it's a function
>because there is only one kind of variable and you have to assume it
>can be used for any kind of data. So if/when you do (FOO X) you have
>to type-check it there [unless by some luck you have managed to
>type-propagate the necessary type information at compile time; hard to
>do with modular compilation] or else you cannot risk jumping directly
>to it to be executed, only to find it's not executable. This slows
>function call.
First of all, there's no requirement for the implementation to warn you if
you try to execute data (well, in CL you can declare high safety, which
reduces the ability to optimize stuff like this).
Second, there are ways to manipulate memory management so that this will be
caught by hardware. If non-function objects are stored in memory pages
with their execute bits turned off, trying to execute data will result in a
trap that the Lisp implementation can handle and turn into a type error.
Third, given all the generic operations that most Lisp systems offer, it
seems a little silly to worry about this one. How many instructions can it
take to determine whether FOO's value is a function?
Kent M Pitman
In article <5pk47j$8...@pasilla.bbnplanet.com> Barry Margolin
<bar...@bbnplanet.com> writes:
> First of all, there's no requirement for the implementation to warn you if
> you try to execute data (well, in CL you can declare high safety, which
> reduces the ability to optimize stuff like this).
We're talking Lisp2 (the class of languages that includes CL).
There's no requirement of anything indeed. But we're talking about
what it takes to efficiently execute safe code in general. And, in
general, if you can create a situation in which the slot is 'typed'
you can check it at store time and save at access time.
A Lisp2 (assuming the two namespaces are function and value :-) has
the feature that its 'function' namespace can be typed, even if the
dialect has no other provision for type declaration.
Second, there are ways to manipulate memory management so that this
will be caught by hardware. If non-function objects are stored in
memory pages with their execute bits turned off, trying to execute
data will result in a trap that the Lisp implementation can handle
and turn into a type error.
This depends on the hardware and OS, of course. I'm speaking in
general about efficient error checking that can be achieved regardless
of assumptions about the OS. Sure, if you get hardware support, you
can even just have a tag for functions, but we may not all be that lucky.
Third, given all the generic operations that most Lisp systems offer, it
seems a little silly to worry about this one. How many instructions can it
take to determine whether FOO's value is a function?
Well, if you're going to talk about making a mountain out of a molehill,
would you think that just changing CL from a Lisp2 to a Lisp1 would suddenly
cause the Scheme community to abandon their language and flock to CL as the
new model of simplicity? :-)
I was simply defending the isolated technical claim which is that the
theoretical efficiency of function calling in a Lisp2 has an edge over
a Lisp1, and for reasons that are philosophically sound: when you
create categories, you know more specific information about the things
in each categories. People complain about Lisp2 as "adding
complexity" (which, by your same metric--with all these generic
functions around, seems to me inconsequentually small extra
complexity) as if they get nothing for it.
If you like, consider me to just be saying that when you add a tiny
conceptual amount of theoretical complexity going from a Lisp1 to a
Lisp2, you get an tiny theoretical speedup...
Vassil Nikolov
Barry Margolin wrote:
#<quoted text omitted>
> Huh? What about (setf (symbol-function <exp1>) <exp2>)?
>
> This allows you to change a function binding.
But there is no way to _establish_a_new_binding_ for the function cell!
(There is no ``(DECLARE (FSPECIAL ...))'' which would be to
``(DECLARE (SPECIAL ...))'' as FBOUNDP is to BOUNDP,
not to mention that FLET is very much unlike LET in this respect.)
So there are et least two efficiency issues here:
* eliminating checks whether the function cell indeed holds
executable code; *and*
* having a cell that is accessible in constant time, and the
`normal' use of that cell is for the function definition.
(I hope that my previous posting on this issue also made it through...)