Newsgroups: comp.lang.scheme Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!snorkelwacker.mit.edu!bloom-beacon!dont-send-mail-to-path-lines From: STCS8004%IRUCCVAX.UCC.IE@mitvma.mit.EDU Subject: Logic does not apply Message-ID: <9105031031.aa16176@mc.lcs.mit.edu> Sender: daemon@athena.mit.edu (Mr Background) Organization: The Internet Date: 3 May 91 15:18:00 GMT Lines: 160 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 ...) 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: 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: ; var y: ): ; begin ... x := y ...; ... end; by function f2 (x, y: ): ; 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.ie