If I have a recursive function like this:
(define (double-n-times x n)
(if (= n 0)
x
(double-n-times (* 2 x) (- n 1))))
How can I make a lambda version of it and never give it a name? ... like if i want to inline it somewhere. Is that possible? (I mean in this case I could use fold - so maybe the example isn't that great) - Is there some kind of symbol or placeholder for "self" that I haven't been able to find? Or do you just have to give it a name.
The Y-Combinator in Racket is:
(lambda (f)
((lambda (h) (h h))
(lambda (g) (f (lambda args (apply (g g) args))))))
This function can take any anonymous function and apply it on themselves recursively.
Let us define your function's part. double-n-times-part written only with lambdas:
(lambda (f)
(lambda (x n)
(if (= n 0) x (f (* 2 x) (- n 1))))))
where f we could name as we want - so we could also call it double-n-part.
If we apply the Y-Combinator on this, we get:
((lambda (f)
((lambda (h) (h h))
(lambda (g) (f (lambda args (apply (g g) args))))))
(lambda (f)
(lambda (x n)
(if (= n 0) x (f (* 2 x) (- n 1))))))
This spits out a function which takes the arguments x and n and applies the inner function of the second definiton on them.
So now, without any named functions - only using lambda expressions - you can apply on your arguments - let's say x=3 and n=4:
(((lambda (f)
((lambda (h) (h h))
(lambda (g) (f (lambda args (apply (g g) args))))))
(lambda (f)
(lambda (x n)
(if (= n 0) x (f (* 2 x) (- n 1))))))
3 4)
;;=> 48 ; as expected (3 * 2 * 2 * 2 * 2)
This is more convenient to read.
But we could also define the Y combinator without apply and args when we allow only monadic functions (functions with one arguments) instead of variadic ones. Then it looks like this (and we have to give the arguments one after another like this):
((((lambda (f)
((lambda (h) (h h))
(lambda (g) (f (lambda (x) ((g g) x))))))
(lambda (f)
(lambda (x)
(lambda (n)
(if (= n 0) x ((f (* 2 x)) (- n 1)))))))
3) 4)
;;=> 48
The answer to your question is yes, by using macros. But before I talk about that, I have to ask this first: do you ask because you are just curious? Or do you ask because there are some issues, like you don't want to pollute the namespace with names?
If you don't want to pollute the namespace with names, you can simply use local constructs like named let, letrec, or even Y combinator. Alternatively, you can wrap define inside (let () ...).
(let ()
(define (double-n-times x n)
(if (= n 0)
x
(double-n-times (* 2 x) (- n 1))))
(double-n-times 10 10))
;; double-n-times is not in scope here
For the actual answer: here's a macro rlam that is similar to lambda, but it allows you to use self to refer to itself:
#lang racket
(require syntax/parse/define)
(define-syntax-parse-rule (rlam args body ...+)
#:with self (datum->syntax this-syntax 'self)
(letrec ([self (λ args body ...)])
self))
;; compute factorial of 10
((rlam (x)
(if (= 0 x)
1
(* x (self (sub1 x))))) 10) ;=> 3628800
Yes. Being a placeholder for a name is what lambda function's parameters are there for:
(define (double-n-times x n)
(if (= n 0)
x
(double-n-times (* 2 x) (- n 1))))
=
(define double-n-times (lambda (x n)
(if (= n 0)
x
(double-n-times (* 2 x) (- n 1)))))
=
(define double-n-times (lambda (self) ;; received here
(lambda (x n)
(if (= n 0)
x
(self (* 2 x) (- n 1)))))) ;; and used, here
but what is this "self" parameter? It is the lambda function itself :
= ;; this one's in error...
(define double-n-times ((lambda (u) ;; call self with self
(u u)) ;; to receive self as an argument
(lambda (self)
(lambda (x n)
(if (= n 0)
x
(self (* 2 x) (- n 1)))))))
;; ...can you see where and why?
= ;; this one isn't:
(define double-n-times ((lambda (u) (u u))
(lambda (self)
(lambda (x n)
(if (= n 0)
x
((self self) (* 2 x) (- n 1)))))))
;; need to call self with self to actually get that
;; (lambda (x n) ... ) thing to be applied to the values!
And now it works: (double-n-times 1.5 2) returns 6.0.
This is already fine and dandy, but we had to write ((self self) ... ...) there to express the binary recursive call. Can we do better? Can we write the lambda function with the regular (self ... ...) call syntax as before? Let's see. Is it
= ;; erroneous
(define double-n-times ((lambda (u) (u u))
(lambda (self)
(lambda (x n)
(lambda (rec body) (self self)
(if (= n 0)
x
(rec (* 2 x) (- n 1))))))))
(no) Or is it
= ;; also erroneous...
(define double-n-times ((lambda (u) (u u))
(lambda (self)
(lambda (x n)
((lambda (rec body) body)
(self self)
(if (= n 0)
x
(rec (* 2 x) (- n 1)))))))) ;; ...can you see why?
(still no) Or is it perhaps
= ;; still erroneous...
(define double-n-times ((lambda (u) (u u))
(lambda (self)
((lambda (rec)
(lambda (x n)
(if (= n 0)
x
(rec (* 2 x) (- n 1)))))
(self self) ))))
(no yet again ... in an interesting way) Or is it actually
=
(define double-n-times ((lambda (u) (u u))
(lambda (self)
((lambda (rec)
(lambda (x n)
(if (= n 0)
x
(rec (* 2 x) (- n 1)))))
(lambda (a b) ((self self) a b)) ))))
(yes!) such that it can be abstracted and separated into
(define (Y2 g) ((lambda (u) (u u))
(lambda (self)
(g
(lambda (a b) ((self self) a b))))))
(define double-n-times (Y2
(lambda (rec) ;; declare the rec call name
(lambda (x n)
(if (= n 0)
x
(rec (* 2 x) (- n 1))))))) ;; and use it to make the call
and there we have it, the Y combinator for binary functions under strict evaluation strategy of Scheme.
Thus we first close over our binary lambda function with our chosen recursive call name, then use the Y2 combinator to transform this "rec spec" nested lambdas into a plain callable binary lambda function (i.e. such that expects two arguments).
Or course the name rec itself is of no importance as long as it does not interfere with the other names in our code. In particular the above could also be written as
(define double-n-times ;; globally visible name
(Y2
(lambda (double-n-times) ;; separate binding,
(lambda (x n) ;; invisible from
(if (= n 0) ;; the outside
x
(double-n-times (* 2 x) (- n 1))))))) ;; original code, unchanged
defining exactly the same function as the result.
This way we didn't have to change our original code at all, just close it over with another lambda parameter with the same name as the name of our intended recursive call, double-n-times, thus making this binding anonymous, i.e. making that name unobservable from the outside; and then passing that through the Y2 combinator.
Of course Scheme already has recursive bindings, and we can achieve the same effect by using letrec:
(define double-n-times ;; globally visible name
(letrec ((double-n-times ;; internal recursive binding:
(lambda (x n) ;; its value, (lambda (x n) ...)
(if (= n 0)
x
(double-n-times (* 2 x) (- n 1))))))
double-n-times)) ;; internal binding's value
Again the internal and the global names are independent of each other.