Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Q: 101 Buzzwords in Scheme

36 views
Skip to first unread message

Xah

unread,
Dec 28, 1997, 3:00:00 AM12/28/97
to

What does it mean of the concept that program and data are treated the same
way (as in lisp-like languages)?

Intuitively, uneducated programers (me) know what it means, but how about an
exact explaination? (e.g. a formal definition)

--

Why is lisp expression called S-expression?

--

Some questions from reading the Intro section of R4RS.

>Scheme was one of the first programming languages to incorporate first
>class procedures as in the lambda calculus

What does this mean exactly? If it means no more than that procedures are
first class (meaning it can be manipulated as data), then isn't it in LISP
all along?

>, thereby proving the
>usefulness of static scope rules and block structure in a dynamically
>typed language.
>
>Scheme was the first major dialect of Lisp to
>distinguish procedures from lambda expressions and symbols,
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

How so? (don't understand)

> to use a
>single lexical environment for all variables,

>and to evaluate the
>operator position of a procedure call in the same way as an operand
>position.

What's the significance of this?

>By relying entirely on procedure calls to express iteration,
>Scheme emphasized the fact that tail-recursive procedure calls are
>essentially goto's that pass arguments.
>
>Scheme was the first widely used
>programming language to embrace first class escape procedures, from
>which all previously known sequential control structures can be
>synthesized.

Someone please explain 'first class escape procedures'.

>With the appendix to this report Scheme becomes the
>first programming language to support hygienic macros, which permit the
>syntax of a block-structured language to be extended reliably.

'hypienic macros'? What's not a 'block-structured language'?

PS I'm in Chapter 3 of SICP, and 2/3 way through R4RS. Have read Scheme FAQ.
(no formal CS training) Tttthanks.

Xah, x...@best.com
http://www.best.com/~xah/
"Unix + C + Perl = Human Resource Hog of the Century"

Kent M Pitman

unread,
Dec 28, 1997, 3:00:00 AM12/28/97
to

[You cross-posted your query, but I won't cross-post my reply.
I find cross-posting antisocial.]

"Xah" <x...@best.com> writes:

> Why is lisp expression called S-expression?

Somebody just recently returned my Lisp 1.5 Programmer's Manual, so it
was out on my desk wanting to be used as a reference. The manual (by
John McCarthy et al, Second Edition, 1965, talks about symbolic
expressions, S-expressions, and meta expressions M-expressions. "All
data are in the form of syjmbolic expressions referred to as
_S-expressions_." S-expressions were like:
(A B)
"The second important part of the LISP language is the source language
itself which specifies in what way the S-expressions are to be
processed. This consists of recursive functions of S-expressions.
Since the notation for the writing of recursive functions of
S-expressions is itself outside the S-expression notation, it will be
called the meta language. These expressions will therefore be called
_M-expressions_." M-expressions were like:
cons[A;B]
It was possible to mix S- and M-expressions as in:
car[(A . B)]

(I think S-expressions were implicitly quoted.)

Plainly, M-expressions later "fell away". (I think I've heard told,
but I don't recall the specific story of how that happened, so I can't
repeat it.) This left only S-expressions. In most modern Lisp
dialects, we just call them "expressions" since there is no longer any
ambiguity.

Ray Dillinger

unread,
Dec 28, 1997, 3:00:00 AM12/28/97
to

Xah wrote:
>
> What does it mean of the concept that program and data are treated the same
> way (as in lisp-like languages)?
>
> Intuitively, uneducated programers (me) know what it means, but how about an
> exact explaination? (e.g. a formal definition)

It has several meanings, actually.

1) Any sequence of symbols which denotes an expression
(including programs) if read as program also denotes a
constant if read as data. Usually this constant is a
long and structured list. But the important thing to
this bit of the definition is that you can use scheme
to read scheme expressions and you get structured
data back -- your parsing is already done for you.

2) procedures are first-class -- meaning they can be
used as variable values, stored in arrays, returned from
function calls, etc.

> Why is lisp expression called S-expression?

I believe it stands for "scheme expression." I'm not
sure though.

> >Scheme was one of the first programming languages to incorporate first
> >class procedures as in the lambda calculus
>
> What does this mean exactly? If it means no more than that procedures are
> first class (meaning it can be manipulated as data), then isn't it in LISP
> all along?

LISP had first-class procedures way back when. But scheme was the
first language to have the same kind of first-class procedures that
the Lambda Calculus has -- and other LISP's still don't. The crucial
difference, I think, is touched on in one of your other questions.


> >Scheme was the first major dialect of Lisp to
> >distinguish procedures from lambda expressions and symbols,
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
> How so? (don't understand)

In most early LISPs, a symbol which is also a variable name bound
to a location where a value is stored is indistinguishable from
that value. In scheme, you have a syntactic form named quote which
returns the symbol regardless of whether it is the name of a variable
or not.

Thus, after evaluating

(define foo 38) you can evaluate

foo => 38
(quote foo) => FOO

> >and to evaluate the
> >operator position of a procedure call in the same way as an operand
> >position.
>
> What's the significance of this?

Basically, it means your procedure name is actually an expression which
is evaluated like any other variable, returning the desired procedure
as a value. But if you want, you can use *any* expression which
evaluates to a procedure instead. In most LISPS, you have to use some
extra syntax (funcall, etc) to do things like this. In fact, this is
the easiest way to get specialized OO routines in any language, as far
as I can tell. My "objects" in scheme are just procedures bound with
their environments. I call them with a single argument and they return
procedures that manipulate their environments(which contain the object's
local variables). Thus my OO call on a bank account object could look
like this:

((Janies_account 'withdraw) #e100.00 '$US )

I'm in the minority for liking this one - most programmers prefer
to make up some syntax to hide the evaluation of the first expression.
But since it usually comes out as something just as ugly and more
comprehensible only if you're accustomed to C naming conventions
(which I'm not) such as

(Janies_account.withdraw #e100.00 '$US )

, I'm inclined to just ignore that and avoid defining syntactic
forms at all, thus retaining my ability to use my knowledge of
standard scheme procedure calls (which follow rules that user-
defined syntax isn't obliged to) to know what's going on.


> >
> >Scheme was the first widely used
> >programming language to embrace first class escape procedures, from
> >which all previously known sequential control structures can be
> >synthesized.
>
> Someone please explain 'first class escape procedures'.

There is not a very simple explanation.... but one way to think of
it is that you can 'save your place' at any point in the execution
of a program. When you do, you get a value that you can do anything
you like with. Store it in an array, or whatever, until you need it,
and later use it to continue execution from that place.


> >With the appendix to this report Scheme becomes the
> >first programming language to support hygienic macros, which permit the
> >syntax of a block-structured language to be extended reliably.
>

> 'hygienic macros'? What's not a 'block-structured language'?


a hygienic macro is a macro whose expansion is guaranteed to
not cause collisions with definitions already existing in your
environment.

Many languages are not block structured - which ones are not,
depends on your definition of what 'block structured' means.
It is generally agreed that any language where all variables
are global, such as assembly languages and early basics, is not
block structured. Nor is any language where there is not
recursion (early fortrans and basics). Unification languages
such as prolog and most database languages don't conform to
some ideas of block structure, either. Languages where goto's
allow execution to jump arbitrarily are not block structured.


> PS I'm in Chapter 3 of SICP, and 2/3 way through R4RS. Have read Scheme FAQ.
> (no formal CS training) Tttthanks.

Perhaps you should put together some programs using SICP as a
guide. The waters in that book get deep, and if you skip over
much, you'll get lost on other bits of it. The questions you're
asking now are not really things that, as a beginning schemer,
you should be very much worried about. You will find that you
can do amazing things with this language as you work with it,
just because of its implicit structure; the fact that the things
you can do and the reasons you can do them have names won't
prevent you from discovering and using them if you don't know
those names, and knowing them won't really help that much.

In other words, relax and play with it. :-) have fun. You
don't need to worry at this point about principles of language
design any more than you need to worry about principles of game
design to enjoy a good game of monopoly or chess.

When you want to seriously think about what makes monopoly or
chess enjoyable to you, *then* you think about game design.
When you start to wonder why scheme is so darn effective,
*then* it is time to think about language design.

Bear

Gareth McCaughan

unread,
Dec 28, 1997, 3:00:00 AM12/28/97
to

"Xah" wrote:

> What does it mean of the concept that program and data are treated the same
> way (as in lisp-like languages)?
>
> Intuitively, uneducated programers (me) know what it means, but how about an
> exact explaination? (e.g. a formal definition)

I'm not sure that there is a formal definition. After all, you could
argue that in C program and data are treated the same way, because you
can represent any program as a big long string. What's different about
languages in the Lisp family is that the way they represent code
externally is structured in a way that fits in well with the way they
represent data. And of course Lisps with an `eval' function also have
a nice way of treating data as program, as well as treating program
as data. :-)

But there isn't a sharp distinction here.

> Why is lisp expression called S-expression?

Kent Pitman has already answered this one.

> >Scheme was one of the first programming languages to incorporate first
> >class procedures as in the lambda calculus
>
> What does this mean exactly? If it means no more than that procedures are
> first class (meaning it can be manipulated as data), then isn't it in LISP
> all along?

Older versions of Lisp were dynamically scoped. This makes procedures
a little less first-class, I suppose: in Scheme you can do

(define (adder x)
(lambda (y) (+ x y)))

so that (adder 5) yields a function that, given x, returns x+5. In
dynamically-scoped Lisps, the equivalent of this would return (no
matter what you passed to ADDER) a function that, given x, returns
x plus the current value of y. Not so useful.

These days, most Lisps are lexically scoped; Scheme introduced this
to the Lisp family. (I think a major reason why Lisp got lexical
scoping quite late was the tradition of thinking of Lisp as an
interpreted language. Dynamic scoping is a bit easier to implement
if you're writing an interpreter...)

> >Scheme was the first major dialect of Lisp to
> >distinguish procedures from lambda expressions and symbols,
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
> How so? (don't understand)

In early Lisps, procedures *were* lists beginning with LAMBDA,
or symbols with suitable properties. In Scheme (and most modern
Lisps) procedures usually aren't either of these: a procedure is
an opaque object that can perform computations for you. This is
a healthier attitude to have...

> >and to evaluate the
> >operator position of a procedure call in the same way as an operand
> >position.
>
> What's the significance of this?

In some Lisps, you can do

(let ((cons 123))
(cons 1 1))

and get (1 . 1) out, because they maintain (at least) *two* bindings
for each symbol: one for when it's considered as a variable, and one
for when it's considered as a function. (So

(let ((cons 123))
(cons cons cons))

would yield (123 . 123).) This was the case for early Lisp dialects,
and it's still true of most Lisps other than Scheme (including e.g.
Common Lisp and Emacs Lisp). In Scheme, a variable has a single
value; the value of CONS is a procedure that conses its arguments.
If you try to do the above in Scheme, the machine will complain that
you can't apply 123 as a function. This is sort of connected with
the idea of making functions first-class (though, as usual, there's
no very rigorous way of saying that). The Scheme way is more elegant;
the Common Lisp way is arguably more practical. I have seen quite
convincing arguments in both directions.

> >Scheme was the first widely used
> >programming language to embrace first class escape procedures, from
> >which all previously known sequential control structures can be
> >synthesized.
>
> Someone please explain 'first class escape procedures'.

OK. Hold on to your seat.

Scheme has a procedure called `call-with-current-continuation'
(usually, thank goodness, abbreviated to `call/cc'). This returns
a procedure object (let's call it FOO) with the following amazing
property: calling (FOO x) produces the same effect as if that call
to `call/cc' had returned x. This applies *whenever* you call FOO;
you can even do it several times.

This is how one does `catch/throw' in Scheme; you can also use it
for more interesting things, such as backtracking algorithms.
So, suppose you have an algorithm that needs to make some random
decisions every now and then, with the property that as soon as
it becomes apparent that something isn't going to work it tries
a different choice at the most recent `choice point'. Then you
can do something like this:

;; List of backtrack points, most recent first.
;; It is an error for any of those lists to be empty.
(define backtrack-points ())

;; Backtrack to the most recent backtrack point,
;; trying the next value specified there.
;; It is an error to call FAIL when BACKTRACK-POINTS is empty.
(define (fail)
(let ((latest-btp (car backtrack-points))
(other-btps (cdr backtrack-points)))
(set! backtrack-points other-btps)
(latest-btp)))

;; Call PROC (a procedure of one argument) with a value
;; from list VALS. Arrange that FAIL will try the next
;; value in the list.
(define (backtrackable-call proc vals)
(if (null? vals)
(fail)
(call-with-current-continuation
(lambda (cont)
(set! backtrack-points
(cons (lambda ()
(cont (backtrackable-call proc (cdr vals))))
backtrack-points))
(proc (car vals))))))

Working out how to set up BACKTRACK-POINTS for the first time is
left as an exercise for the reader. After giving a suitable definition,
you can do

scheme> (backtrackable-call display '(1 2 3 4))
1
; No value returned
scheme> (fail)
2
; No value returned
scheme> (fail)
3
; No value returned
scheme> (fail)
4
; No value returned
scheme> (fail)
; Value returned: failed

> >With the appendix to this report Scheme becomes the
> >first programming language to support hygienic macros, which permit the
> >syntax of a block-structured language to be extended reliably.
>

> 'hypienic macros'? What's not a 'block-structured language'?

A hygienic macro is one that doesn't interfere with variable bindings
in a way that it shouldn't. So, an *unhygienic* macro might expand
from (if-foo blarf) into (let ((a (foo))) blarf) [yes, this is a very
artificial and pointless example]. To see why this is a problem,
suppose it was called as (if-foo (set! a 123)) and consider what
might happen.

A hygienic macro system gets round these problems by renaming things,
or by some other equivalent technique.

Typical language that isn't block-structured: FORTRAN 77. Or many
versions of BASIC. Or Perl, if I recall aright.

--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
gj...@dpmms.cam.ac.uk Cambridge University, England.

Keith Wright

unread,
Dec 28, 1997, 3:00:00 AM12/28/97
to

>> Why is lisp expression called S-expression?
>
> I believe it stands for "scheme expression." I'm not
> sure though.

Definitely wrong, since they were called S-expr's in the Lisp 1.5
manual written around 1959, fiffteen years before the first Scheme.
Originally they were given a name to distinguish them from "real"
expressions (which were to be more like traditional algebraic
notation). Best to treat it as a totaly arbitrary traditional name.

--
--Keith

This mail message sent by GNU emacs and Linux.
Power to the people. Linux is here.
Food, Shelter, Source code.

Robert D. Skeels

unread,
Dec 29, 1997, 3:00:00 AM12/29/97
to

Xah:

Some good sources of information besides what your working with are:

Prof. Paul R. Wilson's "An Introduction to Scheme and its Implementation"
<ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_toc.html>

Indiana Universities C201 Lecture Notes
<http://www.iue.indiana.edu/csci/C201/c201.html#lectures>

There are a few other good educational resources listed at the Scheme
Repository that will help you as well.


Robert D. Skeels ath...@earthlink.net | "created and sent via the
Los Angeles, CA illustration & design | Cyberdog mail system"
http://home.earthlink.net/~athene | eti kai nun Hellada phileo

IBM 350 MHz PowerPC 604e unveiled: world's fastest microcomputer cpu

Jim White

unread,
Dec 29, 1997, 3:00:00 AM12/29/97
to

Xah wrote in message <685r5q$5tf$1...@nntp1.ba.best.com>...

>Some questions from reading the Intro section of R4RS.
>
>>Scheme was one of the first programming languages to incorporate first
>>class procedures as in the lambda calculus
>
>What does this mean exactly? If it means no more than that procedures are
>first class (meaning it can be manipulated as data), then isn't it in LISP
>all along?


It means that an object of type procedure will return #t from the predicate
procedure? and not one of the other type predicates (see Disjointness of
types in R4RS). In most earlier LISP implementations procedures were either
a list (and so would return true from consp or pair? in Scheme) or an
attribute of a symbol. A significant consequence of that is that it was
generally invalid to eval a lambda.

jim
-----------------------------------------------------------------------
James P. White Netscape DevEdge Champion for IFC
Director of Technology Adventure Online Gaming http://www.gameworld.com
Developers of Gameworld -- Live Action Role-Playing and Strategic Games
j...@aognet.net Pagesmiths' home is http://www.pagesmiths.com


Barry Margolin

unread,
Dec 30, 1997, 3:00:00 AM12/30/97
to

In article <sfwen2x...@world.std.com>,

Kent M Pitman <pit...@world.std.com> wrote:
>Plainly, M-expressions later "fell away". (I think I've heard told,
>but I don't recall the specific story of how that happened, so I can't
>repeat it.) This left only S-expressions.

I vaguely recall that they fell away when meta-circular EVAL became
popular. In order to use this, you translated an M-expression into a
corresponding S-expression, and then handed it to EVAL, e.g.

eval[(cons 1 2)]

was equivalent to

cons[1;2]

Eventually they decided that two notations for the same thing was
unnecessary; since S-expressions had to be used whenever an expression was
embedded in data, it was adopted as the top-level syntax as well.

--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Please don't send technical questions directly to me, post them to newsgroups.

Brian Harvey

unread,
Dec 31, 1997, 3:00:00 AM12/31/97
to

be...@sonic.net writes:
>> Why is lisp expression called S-expression?
>I believe it stands for "scheme expression." I'm not sure though.

In McCarthy's original idea for Lisp, there were "symbolic expressions"
used to represent data, and there were "meta expressions" used to
represent programs. The M-expressions looked a little more like
traditional programming languages, with cons[a;b] instead of (cons a b).
From the beginning, one of McCarthy's goals was that programs could be
represented as S-expressions for secondary purposes, e.g., writing a
program verification program. But it took a little while before he and
his group decided to dispense with M-expressions altogether and just
write an interpreter for S-expressions.

Indeed, the first Lisp interpreter was not a read-eval-print loop,
but had a distinguished top-level evaluator called evalquote that
read two things, a procedure name and a list of quoted arguments.

>> >Scheme was the first major dialect of Lisp to
>> >distinguish procedures from lambda expressions and symbols,
>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>> How so? (don't understand)
>In most early LISPs, a symbol which is also a variable name bound
>to a location where a value is stored is indistinguishable from
>that value. In scheme, you have a syntactic form named quote which
>returns the symbol regardless of whether it is the name of a variable
>or not.

No, every version of Lisp has had QUOTE. The understanding of variables
hasn't changed all that much since the early days, except that in versions
other than Scheme, there is a separate namespace for procedures, so that
you can say things like

(define (double list)
(list list list))

and in these other versions the first LIST on the second line means the
primitive procedure, whereas the other two mean the argument to DOUBLE.

But none of that has anything to do with the distinction between
procedures and lambda expressions. Common Lisp, for example, has
a separate procedure namespace (and an awful syntactic kludge to get
around it), but has the same understanding of procedures that Scheme
does, namely (as other messages have explained) lexical scope.

A dynamically scoped procedure contains no information other than what's
in the lambda expression itself. A lexically scoped procedure contains
that information and also a pointer to the environment in which the
procedure was created. So, dynamically scoped Lisps understood lambda
as essentially a funny sort of quotation; the value of the lambda
expression was just the expression itself. That's not true in Scheme,
nor in Common Lisp, both of which are lexically scoped.

William Paul Vrotney

unread,
Jan 1, 1998, 3:00:00 AM1/1/98
to

In article <68e08l$krc$1...@agate.berkeley.edu> b...@anarres.CS.Berkeley.EDU
(Brian Harvey) writes:

>
> But none of that has anything to do with the distinction between
> procedures and lambda expressions. Common Lisp, for example, has
> a separate procedure namespace (and an awful syntactic kludge to get
> around it), but has the same understanding of procedures that Scheme

I am interested in why you think it is an awful syntactic kludge.
Not preferences but just a rational comparison.

While I agree that Scheme's evaluation of the expression CAR is in some
sense more elegant than CL (Common Lisp), there is a quirk to the Scheme
idea that makes the two eval strategies more or less symmetric in elegance.
The quirk is that Scheme still needs a programmer visible APPLY.

We think of the function in CL as the value of a built in property of the
symbol much as the symbol's print name and variable value property. This
delineation allows more flexibility in the implementation of interpreters
and efficiency in compiled code. It would seem that the cost to the
programmer is having to use FUNCALL. But since the programmer needs APPLY
anyway in both Scheme and CL, having FUNCALL as a peer to APPLY has its own
strange elegance.

--

William P. Vrotney - vro...@netcom.com

Richard Mlynarik

unread,
Jan 1, 1998, 3:00:00 AM1/1/98
to

William Paul Vrotney wrote:
[...] But since the programmer needs APPLY

> anyway in both Scheme and CL, having FUNCALL as a peer to APPLY has
> its own strange elegance.

At one stage I proposed that (foo bar baz) be treated as
syntactic sugar for the special form (call foo bar baz).
Thus every expression in the language would uniformly be of the form
(<keyword> <expression>*)

One can turn your argument on its head and claim that apply is really
a kludge due to &rest arguments having reified list representation.
Better would be to have them represented in an
implementation-dependent (and hence compact and stack-allocable)
fashion and for the the usual operations on rest arguments to be
directly supported by the language.

Scheme (and CL) has weird hybrid calling: unlike typical function
languages multi-argument functions aren't just syntactic sugar for
one-argument functions of a single tuple, but &rest arguments do turn
into such tuples (lists in this case.) I think there are real
practical advantages to the former practise, just as I think there are
real practical advantages to being able to return multiple value
without consing tuples to represent the results, but there's an ugly
wart, often with practical performance disadvantages, involved in
using the latter approach for &rest arguments.

A different approach is to use new rest-argument syntax, writing
(define (foo bar . baz) (if bar (apply quux #f baz))
as
(define (foo bar ... baz) (if bar (quux #f ... baz)))
The "..." business is (strictly-redundant, except in lambda
lists) syntax which says that the pseudo-argument representing the
rest list is to be "spread" at this point in the call. (It is
redundant because spreading a non-rest argument should be illegal and
any operation other using a rest "argument" spread out in a call isn't
allowed, but it turned out to be a useful marker in the
very-Scheme-like language I implemented with this feature.

If a reified rest-argument were desired, the user could cons it up
explicitly, using (list ... rest) or (vector ... rest)
Scheme-style apply would be:
(define apply
(letrec ((a (lambda (f ... extras list-rest)
(if (null? rest)
(f ... extras))
(a f ... extras (car list-rest) (cdr
list-rest)))))
a))

The one addition the language needs to support this ... business is an
"arity" built-in function, which counts the number of arguments it is
passed. (This is needed since length operates on lists, not on
rest-arguments.) An example:

(define list
(lambda (... args)
(case (arity ... args)
((0)
'())
((1)
(cons ... args '())) ; "... args" will spread to one arg
exactly.
(else
((lambda (head ... tail) ; Apply this procedure ...
(cons head (list ... tail)))
... args))))) ; ... to these spread args

Barry Margolin

unread,
Jan 2, 1998, 3:00:00 AM1/2/98
to

In article <vrotneyE...@netcom.com>,
William Paul Vrotney <vro...@netcom.com> wrote:
]
]In article <68e08l$krc$1...@agate.berkeley.edu> b...@anarres.CS.Berkeley.EDU

](Brian Harvey) writes:
]
]>
]> But none of that has anything to do with the distinction between
]> procedures and lambda expressions. Common Lisp, for example, has
]> a separate procedure namespace (and an awful syntactic kludge to get
]> around it), but has the same understanding of procedures that Scheme
]
]I am interested in why you think it is an awful syntactic kludge.
]Not preferences but just a rational comparison.
]
]While I agree that Scheme's evaluation of the expression CAR is in some
]sense more elegant than CL (Common Lisp), there is a quirk to the Scheme
]idea that makes the two eval strategies more or less symmetric in elegance.
]The quirk is that Scheme still needs a programmer visible APPLY.
]
]We think of the function in CL as the value of a built in property of the
]symbol much as the symbol's print name and variable value property. This
]delineation allows more flexibility in the implementation of interpreters
]and efficiency in compiled code. It would seem that the cost to the
]programmer is having to use FUNCALL. But since the programmer needs APPLY

]anyway in both Scheme and CL, having FUNCALL as a peer to APPLY has its own
]strange elegance.

I don't think he was referring to the use of FUNCALL, but the FUNCTION
special form (usually abbreviated as "#'"), when he mentioned the "awful
syntactic kludge". Many people think that the necessity to state
explicitly that the symbol should be looked up in the function environment,
whereas nothing explicit has to be done for the variable environment, is
asymmetric. One argument that has been espoused is that making use of
first-class functions look clumsy and special may discourage people from
writing code using higher-order functions.

Since I like having two namespaces (I really hate it whenever I see the
variable LST in Scheme examples), I consider #' a necessary evil.

Brian Harvey

unread,
Jan 2, 1998, 3:00:00 AM1/2/98
to

vro...@netcom.com (William Paul Vrotney) writes:
>I am interested in why you think it is an awful syntactic kludge.

My problem is not with FUNCALL so much as with FUNCTION.

First of all, it's unfortunate that there are notations '# and #' whose
meanings are unrelated. And in the case of #' the meaning has nothing
to do with quotation.

More deeply, I find it confusing that the meaning of (function foo)
has very little to do with the meaning of (function (lambda ...)).
The first is a selector, extracting an existing piece of information
from a data structure; the second is a constructor, creating a closure.

But then, I don't like the way SETF blurs the distinction between
list mutation and variable rebinding, either. My students have enough
trouble keeping it straight when they are restricted to distinct SET!
and SET-CAR! notations. This is the same sort of issue, I think.

Barry Margolin

unread,
Jan 2, 1998, 3:00:00 AM1/2/98
to

In article <68j8sg$gn3$1...@agate.berkeley.edu>,

Brian Harvey <b...@anarres.CS.Berkeley.EDU> wrote:
>More deeply, I find it confusing that the meaning of (function foo)
>has very little to do with the meaning of (function (lambda ...)).
>The first is a selector, extracting an existing piece of information
>from a data structure; the second is a constructor, creating a closure.

If you think of (function foo) as a selector, that's your problem. If FOO
has a lexical binding (as created by FLET), (function foo) is not accessing
a data structure.

The way to think of (function <expression>) is that it evaluates to the
function that would be called if <expression> were found in the function
position of a list form. In this way, (function foo) and (function (lambda
...)) really are the same. Unfortunately, SETF functions, which are named
(setf <symbol>) but called (setf (<symbol> ...) ...) don't follow this
pattern.

>But then, I don't like the way SETF blurs the distinction between
>list mutation and variable rebinding, either. My students have enough
>trouble keeping it straight when they are restricted to distinct SET!
>and SET-CAR! notations. This is the same sort of issue, I think.

Yes, SETF is confusing because it doesn't seem to operate consistently.
(setf (car x) ...) mutates the data structure that X points to, but (setf
(ldb ... x) ...) assigns to X. Simply put, SETF tries to mutate, but when
it can't (in general only if the object is a number, since they're
immutable) it backs out a level and assigns (actually, this could be a
mutation as well, as in the case of (setf (ldb ... (car x)) ...). Perhaps
we should have left out these exceptional cases that can't do mutation (it
probably would have simplified DEFINE-SETF-METHOD), but they were common
practice and it's now 15 years too late to close that Pandora's box.

If CL were restricted to the things that students could keep straight, it
would be Scheme. However, CL had more ambitious goals than being a
teaching language. The number of built-in functions in CL is already
staggering; having to have separate mutation functions for every accessor
would have made things worse, and SETF is a simple solution that was
already in common use.

Erik Naggum

unread,
Jan 2, 1998, 3:00:00 AM1/2/98
to

* Brian Harvey <b...@anarres.CS.Berkeley.EDU>

| First of all, it's unfortunate that there are notations '# and #' whose
| meanings are unrelated.

is '# a notation? for what?

# is a dispatching macro character in Common Lisp -- it takes another
character to become a reader macro function. Scheme has this implicitly,
too, in the vector syntax: #(...).

but this is like saying that since #(:foo) is a vector of one keyword and
(#:foo) is a list of an uninterned symbol, something is "unfortunate" in
the syntax. I don't buy this (rather silly) argument at all.

| And in the case of #' the meaning has nothing to do with quotation.

#(...) has nothing to do with lists, either. #:... has nothing to do with
keywords, #+... has nothing to do with the plus operator, etc, for all #x
and x. what's the big problem?

on other hand, (mapcar #'foo ...) replaced (mapcar 'foo ...) and in many
cases, #'(lambda ...) replaced '(lambda ...), so it is not as unrelated as
you seem to want it to be,

| More deeply, I find it confusing that the meaning of (function foo)
| has very little to do with the meaning of (function (lambda ...)).
| The first is a selector, extracting an existing piece of information
| from a data structure; the second is a constructor, creating a closure.

it's amusing to see how mistaken you are when you criticize Common Lisp,
almost to the point of being ridiculous. I wanted to comment on this
previously, too, but it's not very constructive, however, when it goes on
and on unchecked, you do need correction.

the accessor you allude to is `symbol-function'. it only works on symbols,
but `function' works on function names, which also exist in the lexical
environment, where they aren't symbols any more than lexical variables are.

| But then, I don't like the way SETF blurs the distinction between list
| mutation and variable rebinding, either. My students have enough trouble
| keeping it straight when they are restricted to distinct SET! and
| SET-CAR! notations. This is the same sort of issue, I think.

"list mutation"!? `setf' is a lot more than that. indeed, from the
history of the name that I obtained this newsgroup (I believe that, too,
was Kent Pitman giving a lecture :), it's from "set field", and referred
initially to fields in structures, but grew into a more general mechanism.

I don't see the problem with this, either. (setf variable value) is very
obviously very different from (setf (car variable) value) and it would take
a serious amount of _misunderstanding_ to confuse the two.

however, (setf symbol value) is like (setf (symbol-value 'symbol) value),
which is also a mutator of a slot in a data structure, this time a symbol.
(this is also the old (set 'symbol value) in a new wrapping.)

personally, I think Scheme's lack setf and its insistence of a pre-setf
mode of writing mutators is really _ugly_.

#\Erik
--
The year "98" was new 1900 years ago. | Help fight MULE in GNU Emacs 20!
Be year 2000 compliant, write "1998"! | http://sourcery.naggum.no/emacs/

Brian Hawley

unread,
Jan 2, 1998, 3:00:00 AM1/2/98
to

In article <30927584...@naggum.no>, Erik Naggum <cle...@naggum.no> wrote:
>* Brian Harvey <b...@anarres.CS.Berkeley.EDU>

>| And in the case of #' the meaning has nothing to do with quotation.
>
>#(...) has nothing to do with lists, either. #:... has nothing to do with
>keywords, #+... has nothing to do with the plus operator, etc, for all #x
>and x. what's the big problem?
>
>on other hand, (mapcar #'foo ...) replaced (mapcar 'foo ...) and in many
>cases, #'(lambda ...) replaced '(lambda ...), so it is not as unrelated as
>you seem to want it to be,

You mean (mapcar #'foo ...) replaced (mapcar foo ...) and in many cases
#'(lambda ...) replaced (lambda ...). Note the lack of ' which would
denote a quoted value, rather than an actual value. On this one point,
Brian Harvey (no relation) is correct. Otherwise, I agree with you.

>| But then, I don't like the way SETF blurs the distinction between list
>| mutation and variable rebinding, either. My students have enough trouble
>| keeping it straight when they are restricted to distinct SET! and
>| SET-CAR! notations. This is the same sort of issue, I think.
>
>"list mutation"!? `setf' is a lot more than that. indeed, from the
>history of the name that I obtained this newsgroup (I believe that, too,
>was Kent Pitman giving a lecture :), it's from "set field", and referred
>initially to fields in structures, but grew into a more general mechanism.
>
>I don't see the problem with this, either. (setf variable value) is very
>obviously very different from (setf (car variable) value) and it would take
>a serious amount of _misunderstanding_ to confuse the two.
>
>however, (setf symbol value) is like (setf (symbol-value 'symbol) value),
>which is also a mutator of a slot in a data structure, this time a symbol.
>(this is also the old (set 'symbol value) in a new wrapping.)
>
>personally, I think Scheme's lack setf and its insistence of a pre-setf
>mode of writing mutators is really _ugly_.

I agree with you here too. Something like setf (I know more about OakLisp
setters and getters than Common Lisp setf) would be really helpful when
interfacing with OOP systems with object property functions, like OLE. It
would then be easier to make an OLE automation controller or server based
on a Lisp-like language, or perhaps a LispScript language for embedding in
web pages like JavaScript, VBScript, PerlScript, ad nauseum.

>#\Erik

What macro does #\ invoke?
Brian Hawley

-----
Brian Hawley, email: brian....@bigfoot.com
Note: Please reply by email as my newsserver drops 9 out of 10 postings

William Paul Vrotney

unread,
Jan 2, 1998, 3:00:00 AM1/2/98
to

In article <68j8sg$gn3$1...@agate.berkeley.edu> b...@anarres.CS.Berkeley.EDU
(Brian Harvey) writes:

>
> vro...@netcom.com (William Paul Vrotney) writes:
> >I am interested in why you think it is an awful syntactic kludge.
>
> My problem is not with FUNCALL so much as with FUNCTION.
>

> First of all, it's unfortunate that there are notations '# and #' whose

> meanings are unrelated. And in the case of #' the meaning has nothing
> to do with quotation.
>

Thanks for your answer.

Ah, I should have realized that you meant the #' syntax since you qualified
it as a "syntactic" kludge. However the #' syntax has little to do with
evaluation strategies per se. What I mean by that is that CL reader macros
(#<something>, qoutes, backquotes etc.) are absolutely not necessary. We
consider them more as abbreviations of something that gets translated into
something else, that in the final analysis have a more lengthly but pure
form.

The existence of FUNCTION in CL is similar to the FUNCALL/APPLY issue that I
raised as far as comparing elegance between Scheme and CL. Much as APPLY is
still needed in Scheme, QUOTE is still needed in Scheme. And similarly as
FUNCALL is a peer of APPLY, FUNCTION is a peer of QUOTE. And again both
languages have their own kind of elegance in this regard. When one comes
from other procedural languages to Lisp, FUNCTION and QUOTE both seem like
kludges but they are not once one gets used to them, realizes the
flexibility provided by them and thinks of their abbreviations as only
abbreviations.

Notice that this comparison does not bring up the combined name space for
functions and variables of Scheme which some people find unpalatable. This
seems to be more of a preference issue. But it does cause some unsavory
names to be created in Scheme programs. For example if you have a function
named "foo" then you may need to create a corresponding variable named
foo-VAR or some such which is annoying because you don't need that for
variable names that don't have a function counterpart. Also as a
preference, to me I don't like to type #' either, however this
rationalization of reader macros makes them more palatable than the
alternative.

Barry Margolin

unread,
Jan 3, 1998, 3:00:00 AM1/3/98
to

In article <68jl5p$11g$1...@news.megsinet.net>,

Brian Hawley <brian....@bigfoot.com> wrote:
>You mean (mapcar #'foo ...) replaced (mapcar foo ...) and in many cases
>#'(lambda ...) replaced (lambda ...). Note the lack of ' which would
>denote a quoted value, rather than an actual value. On this one point,
>Brian Harvey (no relation) is correct. Otherwise, I agree with you.

No, Erik was correct. Before #' was invented (in Maclisp, although its
scoping rules rarely made it necessary), you would generally pass function
names and lambda expressions to functions that wanted a function argument.
E.g. you would write (mapcar '1+ '(1 2 3)) or (mapcar '(lambda (x) (+ x 2))
'(4 5 6)). If you tried to write (mapcar 1+ '(1 2 3)) it would complain
that there's no variable named 1+, and (mapcar (lambda (x) (+ x 2)) '(4 5
6)) would complain that there's no function named LAMBDA.

>What macro does #\ invoke?

#\<character or character name> returns the specified character object.
E.g. #\space returns the same thing that (aref " " 0) returns.

Brian Hawley

unread,
Jan 5, 1998, 3:00:00 AM1/5/98
to

In article <68k3sj$d...@tools.bbnplanet.com>, Barry Margolin <bar...@bbnplanet.com> wrote:
>In article <68jl5p$11g$1...@news.megsinet.net>,
>Brian Hawley <brian....@bigfoot.com> wrote:
>>You mean (mapcar #'foo ...) replaced (mapcar foo ...) and in many cases
>>#'(lambda ...) replaced (lambda ...). Note the lack of ' which would
>>denote a quoted value, rather than an actual value. On this one point,
>>Brian Harvey (no relation) is correct. Otherwise, I agree with you.
>
>No, Erik was correct. Before #' was invented (in Maclisp, although its
>scoping rules rarely made it necessary), you would generally pass function
>names and lambda expressions to functions that wanted a function argument.
>E.g. you would write (mapcar '1+ '(1 2 3)) or (mapcar '(lambda (x) (+ x 2))
>'(4 5 6)). If you tried to write (mapcar 1+ '(1 2 3)) it would complain
>that there's no variable named 1+, and (mapcar (lambda (x) (+ x 2)) '(4 5
>6)) would complain that there's no function named LAMBDA.

I guess Erik wrote the correct answer to the wrong question then, since the
other Brian was comparing CL and Scheme, and Scheme has never passed quoted
identifiers and lambdas to the map functions. Scheme never needed to because
the single namespace never required a syntactic hack to retrieve the function
value. Erik's and your example does illustrate that the #' syntax isn't as
bad as what it replaced in the multi-namespace world.

I prefer the single namespace for simplicity, but I recognize that seperate
function values do make compilation easier. That is, unless you use some kind
of typing, perhaps soft typing, and partial evaluation to resolve the type
checks for function type at compile time. Of course your multi-namespace code
would need to be rewritten for a single namespace, something which renders a
lot of this argument moot.

0 new messages