STCS8004%IRUCCVAX.UCC.IE@mitvma.mit.EDU (04/30/91)
The title says it all, but some elaboration is perhaps in order!
One might expect (naively?) that
(apply bin-op (list item1 item2)) = (bin-op item1 item2)
for *all* bin-ops, provided that bin-op's arguments are compatible with it.
But it is not so, since instead of the expected
(apply and '(#f #t)) --> #f
one gets some grumble that either 'and' is an undefined variable or it is
not the right kind of parameter-1 to 'apply'.
However if one uses the eta-conversion (lambda (x y) (f x y)) = f then
'apply' works as expected:
(apply (lambda (x y) (and x y)) '(#f #t)) --> #f.
The catch is that eta-conversion is normally but not strictly (pun
*intended*) valid for 'and'. Why? Because the lambda-abstracted form will
evaluate *both* arguments before passing them on to the 'and' in its body,
whereas (and a b) will not evaluate 'b' if 'a' evaluates to false (see RxRS
Section 7.3).
Now '+', being a built-in procedure, can be applied directly in expressions
like:
(apply + '( 2 3)) --> 5
so why not 'and' and 'or' without the lambda wrapping?
It seems to me that the difference lies in the fact that the logical
operators are defined in the R3 and R3.99 reports (section 7.3) as being
*derived* expression types, so presumably do not qualify as 'procedures' in
the sense specified for the first argument to 'apply' (section 6.9).
So, we can define operators like 'and', 'or', ... using primitives,
therefore they only rank as *derived expressions*, not procedures. Fine!
But we can also define arithmetic operators in terms of the primitives
zero and the successor function. Even better, everything---boolean values
and functions, integers and arithmetic operators, and so on---all can be
defined in terms of lambdas and applications alone, so why not make *them*
derived expressions also? :-)
That the logical operators are derived expressions may well be the *legal*
answer as to why 'and' and 'or' cannot be used with 'apply'---my question
is though: is it a *reasonable* answer, with or without the RxRs Reports to
hand? Why shouldn't 'and' and 'or' be first class citizens of Scheme?
It seems that logic does not apply! :-)
Gordon Oulsnam stcs8004@iruccvax.ucc.hea.ie
"When *I* use a word," Humpty Dumpty said, in a rather scornful tone,
"it means just what I choose it to mean---neither more nor less."
'Through the Looking Glass', Lewis Carrolldoug@snitor.uucp (Doug Moen) (04/30/91)
>That the logical operators are derived expressions may well be the *legal* >answer as to why 'and' and 'or' cannot be used with 'apply'---my question >is though: is it a *reasonable* answer, with or without the RxRs Reports to >hand? Why shouldn't 'and' and 'or' be first class citizens of Scheme? > >It seems that logic does not apply! :-) > >Gordon Oulsnam stcs8004@iruccvax.ucc.hea.ie Good question. If Scheme were changed to use normal order evaluation, then `and' and `or' would indeed become first class procedures. Also, we could get rid of `delay' and `force', it would become easier to define lazy lists, etc. This increase in expressive power is not without cost: there is a performance penalty, and the new dialect `Lazy Scheme' would not be backward compatible with many existing Scheme programs. Also, the Algol-60 experience indicates that the interaction between call by name and side effects makes imperative programs harder to understand (think of Jensen's Device), and Scheme is, after all, an imperative language with functional tendencies, rather than the other way around. If we further change Scheme to make it both lazy *and* functional, then I think we would end up with a worthy and interesting research project. This new language would differ from the current crop of lazy functional languages in some interesting ways: it would have latent types, rather than strong typing, and it would would have Scheme syntax and macros. -- Doug Moen | doug@snitor.uucp | uunet!snitor!doug | doug.tor@sni.de (Europe)
jaffer@zurich.ai.mit.edu (Aubrey Jaffer) (04/30/91)
> One might expect (naively?) that > > (apply bin-op (list item1 item2)) = (bin-op item1 item2) > > for *all* bin-ops, provided that bin-op's arguments are compatible with it. > But it is not so, since instead of the expected > > (apply and '(#f #t)) --> #f > > one gets some grumble that either 'and' is an undefined variable or it is > not the right kind of parameter-1 to 'apply'. The problem you are having here is that `and' and `or' are poorly named control structures. What you want are `and?' and `or?' anyway since tests are supposed to end with `?'. (define (and? . args) (cond ((null? args) #t) ((car args) (apply and? (cdr args))) (else #f))) (define (or? . args) (cond ((null? args) #f) ((car args) #t) (else (apply or? (cdr args)))))
kend@data.UUCP (Ken Dickey) (05/02/91)
STCS8004%IRUCCVAX.UCC.IE@mitvma.mit.EDU writes: >The title says it all, but some elaboration is perhaps in order! >One might expect (naively?) that > (apply bin-op (list item1 item2)) = (bin-op item1 item2) >for *all* bin-ops, provided that bin-op's arguments are compatible with it. >But it is not so, since instead of the expected > (apply and '(#f #t)) --> #f >one gets some grumble that either 'and' is an undefined variable or it is >not the right kind of parameter-1 to 'apply'. I suggest that the problem is not one of "logic", but of using a similar syntax to express both procedure calls and evaluation rules. {The number of special forms in Scheme is, after all, quite small}. From your comments, you would expect the following to "work": (apply if (list a b c)) (apply begin (list a b c)) (apply set! (list a b)) (apply let (list ((a 1)(b 2) (+ a b)))) ... (apply a b) is *not* equivalent to (eval (cons 'a b)) because of differences in order of evaluation. > Why shouldn't 'and' and 'or' be first class citizens of Scheme? Why are special forms not applications? Because they are very useful is expressing another level of computational specification: how evaluation is to proceed. -Ken Dickey kend@data.uucp
dak@sq.sq.com (David A Keldsen) (05/03/91)
Gordon Oulsnam (stcs8004@iruccvax.ucc.hea.ie) writes: [why aren't 'and' and 'or' strict in Scheme?] >It seems to me that the difference lies in the fact that the logical >operators are defined in the R3 and R3.99 reports (section 7.3) as being >*derived* expression types, so presumably do not qualify as 'procedures' in >the sense specified for the first argument to 'apply' (section 6.9). Correct, although I'd put it more simply: 'and' and 'or' are syntax, not procedures. All Scheme procedures are strict. 'and' and 'or' are not strict, which is how "short-circuiting" boolean evaluation is made available to you in Scheme. >That the logical operators are derived expressions may well be the *legal* >answer as to why 'and' and 'or' cannot be used with 'apply'---my question >is though: is it a *reasonable* answer, with or without the RxRs Reports to >hand? Why shouldn't 'and' and 'or' be first class citizens of Scheme? Because they are syntax, not procedures. You can only apply procedures. >It seems that logic does not apply! :-) As you point out, if you want the strict behavior, you can get it by the usual eta transformation; going the other way is much more difficult. In this sense, scheme is providing you with the "more fundamental" tools. Regards, Dak -- David A. 'Dak' Keldsen of SoftQuad, Inc. email: dak@sq.com phone: 416-963-8337 "I daresay you haven't had much practice," said the Queen. "When I was your age, I always did it for half-an-hour a day. Why, sometimes I've believed as many as six impossible things before breakfast." _Through the Looking Glass_
STCS8004%IRUCCVAX.UCC.IE@mitvma.mit.EDU (05/03/91)
Summary
A collective response to all direct and net mailings regarding what is
(not) a Scheme function is given. (Individual replies have also been
sent---but some replies bounced.)
Sytactic sugar hides normal-order(-like) evaluations in Scheme.
A plea is entered for introducing optional normal order evaluation.
Perceptions of Functionality
Many people have made the point, in various ways, that if an operator, f
say, is such that the evaluation (reduction) of an expression such as (f
<arg1> ...) is done using applicative order (alias reduce inner-most redexs
first, alias evaluate the arguments first) then f is a function.
But the use of any other reduction strategy, such as reduce the left-most
outer-most redex first (alias normal order reduction---described to me in
terms like 'evaluate the arguments left to right but with the ability to
short-circuit later arguments if a result can be returned without using
them') denies f the status of being a function (in Scheme---agreed) and
makes it instead a derived expression, special form, control structure, ...
or whatever.
Aubrey Jaffer in Message-Id: <JAFFER.91Apr30124710@kleph.ai.mit.edu> sees
it this way:
> The problem you are having here is that `and' and `or' are poorly
> named control structures. What you want are `and?' and `or?' anyway
> since tests are supposed to end with `?'.
> (define (and? . args)
> (cond ((null? args) #t)
> ((car args) (apply and? (cdr args)))
> (else #f)))
But I think it is much more than a matter of poor naming conventions.
All right then, is *and below a function or not when used in the expression
(*and #f arg2)? After all, '*and' behaves like 'and':
(define *and
(lambda (x y)
(cond (x (y))
(else #f))))
(define arg2 (lambda ()
(begin
(display "arg2 to AND is true")
(newline)
#t)))
The answer, of course, is:- Yes! Because y evaluates to a function (thunk)
which, ...er, ...in the example cited ... er, ...happens not to be invoked
in deriving the answer ... . Um, yes, thank you, sounds familar!
In other words, what 'and' does covertly, '*and' does overtly: both use
(the equivalent of) normal order evaluation.
Incidentally, one can define *apply to work with *and-like functions:
(define *apply
(lambda (f s)
(f (head s) (cdr s))))
and now (*apply *and (cons #f arg2)) --> #f.
(But of course (*apply + (list 2 3)) doesn't work!)
Syntactic sugar and non-applicative evaluations.
Scheme's 'and' is simply syntactic sugar for what in a Pascal-like syntax
could be declared as:
(define *and (lambda (x #/normal! y) (cond (x y) (else #f))))
Since Pascal got a mention, suppose it did not allow the use of var
parameters. One would soon find it necessary to introduce two operators var
and deref, to replace the usual
function f1 (x: <type>; var y: <type>): <type2>;
begin ... x := y ...; ... end;
by
function f2 (x, y: <type>): <type2>;
begin ... x := (deref y) ...; ... end;
and call it with: f2 (a, (var b)), which would be all very painful. 'Var'
is essentially syntactic sugar which hides this. (Some might recall the
l-value and r-value operators in BCPL.)
Yet the unsugared version is exactly the kind of contortion one must go
through with 'delay' and 'force' (which aren't even classed as 'essential')
if one wants to get the effect of normal order evaluation in Scheme. I do
not think that PASCALers feel that f1 is any less of a 'function' because
of using call-by-reference rather than call-by-value. [No, I'm *not*
confusing normal order evaluation with call-by-reference---just
illustrating the fact, and value, of intelligently interpreted syntactic
sugar to hide non-standard evaluation strategies.]
A plea for user-option Normal Form evaluation
In terms of lambda calculus, and in the absence of side-effects, we know
from the Church-Rosser theorems that *provided* the computations terminate,
the normal form of the expression (its value) is independent of the order
in which the reduction steps are applied (thank goodness!)---Church-Rosser
I. We also know that, for a given expression, it may be case that some
reduction sequences may cause non-termination whilst others terminate.
However, if there is a normal order form for the expression, normal order
reduction *alone* is guaranteed to find it---Church-Rosser II.
Thus the *lambda calculus* expression ((lambda (x) 0) (/ 1 0)) evaluates to
0 using normal order, but does not terminate for applicative order. Is
(lambda (x) 0) - known to mathematicians as the zero *function* - a
function or not? If I write it myself in Scheme, yes, but it will fail for
the example given; but if the implementors build it in for me, name it
'zero' and arrange to ignore the argument for efficiency's sake, then no,
it is a special form!
Scheme's derived expressions, special forms, control structures and so on
are, in lambda calculus terms, functions evaluated in (something like)
normal order. Since the necessity for these is acknowledged, *WHY NOT ALLOW
THE USER* to specify normal evaluation when required? The suggested
syntactic sugar has been given above. Introducing it will not affect (as
far as I can see) the efficiency of programs that did not opt to use it.
The question of whether full normal order evaluation (evaluate the
arguments on every encounter) or lazy evaluation (evaluate each argument at
most once, memoizing the results) should be used can be debated, but a
least let us have the *OPTION* of using some form of normal order
evaluation.
But perhaps Doug Moen in Message <1991Apr30.151352.1460@snitor.uucp> put it
better:
> ... If Scheme were changed to use normal order evaluation,
> then `and' and `or' would indeed become first class procedures. Also,
> we could get rid of `delay' and `force', it would become easier to
> define lazy lists, etc. This increase in expressive power is not without
> cost: there is a performance penalty, and the new dialect `Lazy Scheme'
> would not be backward compatible with many existing Scheme programs.
But I think my suggestion of optional normal order might overcome this. As
I recall it, there was no penalty in ALGOL 60 for the inefficiencies of
call-by-name if one chose not to use it.
> ...
> If we further change Scheme to make it both lazy *and* functional, then
> I think we would end up with a worthy and interesting research project.
> This new language would differ from the current crop of lazy functional
> languages in some interesting ways: it would have latent types, rather
> than strong typing, and it would would have Scheme syntax and macros.
> Doug Moen | doug@snitor.uucp | uunet!snitor!doug | doug.tor@sni.de
> (Europe)
I fully agree!
Gordon Oulsnam stcs8004@iruccvax.ucc.hea.iegateley@rice.edu (John Gateley) (05/03/91)
In article <9105031031.aa16176@mc.lcs.mit.edu> Gordon Oulsnam writes:
Scheme's derived expressions, special forms, control structures and so on
are, in lambda calculus terms, functions evaluated in (something like)
normal order. Since the necessity for these is acknowledged, *WHY NOT ALLOW
THE USER* to specify normal evaluation when required?
Just out of curiosity, how would you compile the following function:
(define foo
(lambda (f x y z)
(f z y x)))
Consider (foo + 1 2 3) and (foo if else then pred)?
The arguments to ANY application must be assumed to be passed in
normal order unless you can prove otherwise. Is this what you really
want? I know - I know - the efficiency of an implementation shouldn't
matter during language design, but the implementor in me feels
otherwise.
John
gateley@rice.edu
--
"I've thought the thoughts of little children and the thoughts of men
I've thought the thoughts of stupid people who have never been
so much in love as they should be and got confused too easily
to fall in love again." The Residents and Renaldo and the Loaf