128a-3aj@e260-3b.berkeley.edu (Jonathan Dubman) (10/18/88)
There seems to be a gross omission in the lambda primitive. It seems like there is no way to create a recursive function on the fly! I'm reading the Abelson and Sussman book but they seem to avoid this issue. For example, how would someone write a function generator that generates the sum of all squares or cubes or fourths, etc., based on an exponent? Bear with me, as I'm not a Scheme expert. My specific problem arises from trying to write a simple object-oriented mini-adventure in Scheme. There are two types of objects: players and rooms. Rooms have four exits. Given a direction and a player, the room will move the player to the new room in that direction. Players have a current room. They accept two messages: 'move direction and 'hop new-room. Say you tell a player to go north. He knows his current room and asks that room to send him north. But how can that happen, if the player doesn't know his own name? Make-player, which is a call to a lambda, can't tell the current room to move the player in the given direction because the player isn't defined until after the lambda is finished! One possible solution is to change the communication method so that players merely ask the room where the exit goes and move THEMSELVES. But that's not the way I wanted to do it. Help! What can I do? -Jonathan Dubman
gjs@ZOHAR.AI.MIT.EDU (Gerald Jay Sussman) (10/18/88)
You ask:
For example, how would someone write a function generator that generates the
sum of all squares or cubes or fourths, etc., based on an exponent?
How 'bout:
(define sum-of-powers
(lambda (power)
(lambda (n)
(sum-of (lambda (i)
(expt i power))
n))))
(define sum-of
(lambda (termfun nterms)
(if (= nterms 0)
0
(+ (termfun nterms)
(sum-of termfun (- nterms 1))))))
;;; e.g.
((sum-of-powers 3) 5)
;Value: 225
Does this solve your problem? If not, call me on the phone and I will
try to debug you. My phone is (617) 253-5874.Krulwich-Bruce@cs.yale.edu (Bruce Krulwich) (10/19/88)
In article <15590@agate.BERKELEY.EDU>, 128a-3aj@e260-3b (Jonathan Dubman) writes: >There seems to be a gross omission in the lambda primitive. It seems like >there is no way to create a recursive function on the fly! I'm reading >the Abelson and Sussman book but they seem to avoid this issue. While this may be theoretically true, it seems trivial to me to just make a LAMBDA-function with a LETREC, where the body of the LETREC is just a call to the (recursive) function defined in the LETREC. Whether this solves the particular problem you described, I don't know. Bruce Krulwich
weening@Gang-of-Four.Stanford.EDU (Joe Weening) (10/19/88)
In article <15590@agate.BERKELEY.EDU>, 128a-3aj@e260-3b (Jonathan Dubman) writes: > >There seems to be a gross omission in the lambda primitive. It seems like >there is no way to create a recursive function on the fly! I'm reading >the Abelson and Sussman book but they seem to avoid this issue. This problem actually has quite an interesting history. From the Lisp 1.5 Programmer's Manual (J. McCarthy et al, 1963), p. 8: "The lambda notation alone is inadequate for naming recursive functions. Not only must the variables be bound, but the name of the function must be bound, since it is used inside an expresion to stand for the entire expression. ... In order to be able to write expressions that bear their own name, we introduce the LABEL notation." LABEL only defines a single function in terms of itself. Scheme's LETREC and Common Lisp's LABELS extend this to allow mutually recursive function definitions. I don't know if it was known in 1963, but LABEL or its equivalent is not actually necessary in order to define recursive functions. The trick is to use the Y combinator. In practice, though, this method would be fairly inefficient. -- Joe Weening Computer Science Dept. weening@Gang-of-Four.Stanford.EDU Stanford University
markv@uoregon.uoregon.edu (Mark VandeWettering) (10/19/88)
In article <4557@polya.Stanford.EDU> weening@Gang-of-Four.Stanford.EDU (Joe Weening) writes: >In article <15590@agate.BERKELEY.EDU>, 128a-3aj@e260-3b (Jonathan Dubman) writes: >> >>There seems to be a gross omission in the lambda primitive. It seems like >>there is no way to create a recursive function on the fly! I'm reading >>the Abelson and Sussman book but they seem to avoid this issue. Oh contraire! There is the most amazing goodie in the world, the Y combinator to save the day... The Y combinator is defined so that when applied to a function, it returns an infinite series of applications: Y H = H (Y H) = H (H (Y H)) = H (H (H (Y H))) = H (H (H ... How do we make use of this? Well, quite simply. Take our definition of factorial? (define factorial (lambda (n) (if (= n 1) 1 (* n (factorial (- n 1)))))) We can "abstract" out the inner call to factorial by making it a parameter, call the result H: H = (lambda (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) and then apply Y to it to get our the definition.... FACTORIAL = (Y H) We can illustrate this by applying it to an arg, say 3: Y H 3 -> H (Y H) 3 -> (if (= 3 1) 1 (* 3 ((Y H) (- 3 1)))) -> (* 3 (Y H 2)) -> (* 3 (H (Y H) 2)) -> (* 3 (if (= 2 1) 1 (* 2 ((Y H) (- 2 1))))) -> (* 3 (* 2 ((Y H) 1))) -> (* 3 (* 2 (if (= 1 1) 1) (* 1 ((Y H) 0)))) -> (* 3 (* 2 1)) -> 6 and we are done! Two important things to note, 1. Y can be written as a lambda itself! Y = (lambda (h) (lambda (x) (h (x x))) (lambda (x) (h (x x)))) Try applying it to an arg, and see... 2. Evaluation of Y will not terminate under an applicative order evaluator (such as those used in Lisp or Scheme. Functions must evaluate their args first, which results in an infinite stream of computation. This isn't a problem for functionally pure languages, which can use normal order evaluation. Abelson and Sussman's SICP does mention this in passing, on pg. 488. They have to be careful that too much doesn't get evaluated, but the idea is the same. >This problem actually has quite an interesting history. From the Lisp >1.5 Programmer's Manual (J. McCarthy et al, 1963), p. 8: > > "The lambda notation alone is inadequate for naming recursive > functions. Not only must the variables be bound, but the name of > the function must be bound, since it is used inside an expresion > to stand for the entire expression. ... In order to be able to > write expressions that bear their own name, we introduce the LABEL > notation." > >LABEL only defines a single function in terms of itself. Scheme's >LETREC and Common Lisp's LABELS extend this to allow mutually >recursive function definitions. > >I don't know if it was known in 1963, but LABEL or its equivalent is >not actually necessary in order to define recursive functions. The >trick is to use the Y combinator. In practice, though, this method >would be fairly inefficient. One element of my master's thesis work is to decide if the Y combinator is indeed as inefficient as people seem to imagine. Nevertheless, the Y combinator has been around for a LONG time, probably to Alonzo Church in the 40's. McCarthy has admitted that his knowledge of the lambda calculus was admittedly limited. Such things as dynamic scoping were less than totally thought through. For an excellent intro the lambda calculus, and functional programming in general, try Simon Peyton Jones' book, the Implementation of Functional Programming Languages. Excellent. >Joe Weening Computer Science Dept. >weening@Gang-of-Four.Stanford.EDU Stanford University
FWHITE@G.BBN.COM (10/20/88)
In "A Basis for a Mathematical Theory of Computation"* by McCarthy, which dates from the 1961 Western Joint Computer Conference, McCarthy mentions that Y can be used to eliminate LABEL but at the expense of giant resulting expressions. Who did invent Y, anyways? ------------ * Reprinted in "Computer Programming and Formal Systems", P. Braffort & D. Hirschberg eds, 1967. See pp 46-7.
augustss@cs.chalmers.se (Lennart Augustsson) (10/21/88)
In article <4557@polya.Stanford.EDU> weening@Gang-of-Four.Stanford.EDU (Joe Weening) writes: >In article <15590@agate.BERKELEY.EDU>, 128a-3aj@e260-3b (Jonathan Dubman) writes: >> >>There seems to be a gross omission in the lambda primitive. It seems like >>there is no way to create a recursive function on the fly! I'm reading >>the Abelson and Sussman book but they seem to avoid this issue. ... [ Talk about LABEL ] ... > >I don't know if it was known in 1963, but LABEL or its equivalent is >not actually necessary in order to define recursive functions. The >trick is to use the Y combinator. In practice, though, this method >would be fairly inefficient. It was certainly known in 1963, the question is who knew it. The fact that Y can be defined in terms of (nonrecursive) functions was discovered in the 30s (I think) by Haskell B. Curry. He didn't die until the -83 (or so) so at least he knew, and assuming that people read his books others knew as well. The problem is that probably very few computer scientist knew about it (well, it's not really a problem since this definition(s) of Y is of theoretical interest only). -- Lennart Augustsson Email: augustss@cs.chalmers.se or augustss@chalmers.csnet