0

The following is a question I have on lambda expressions:

def combinator(y):
    return (lambda x: lambda y: x(y))(lambda x:y)

Evaluate the following expression combinator(lambda x: x*10)(11)(12).

I understand that return statements return a value so perhaps, we should start by simplifying the lambda expression of the return statement:

(lambda x: lambda y: x(y))(lambda x:y) simplifies to (lambda y: (lambda x:y)(y)),

which further simplifies to (lambda y: y)

However, following the above logic would lead me to the wrong answer. The answer is 120.

I would like to ask, what is the method to deal with the above lambda expression?

Tan Yong Boon
  • 117
  • 5
  • 2
    You don't simplify functions like equations. You expand them with substitution. For example, the call to `combinator()` passes a lambda function as `y` which you then substitute leading to `(lambda x: lambda y: x(y))(lambda x:lambda x: x*10)(11)(12)` – Mark Jul 28 '22 at 02:30
  • @Mark Thanks for the reply. May I know why you only substituted into the y of the 2nd part of the expression and not the "y"s in the first part of the expression? – Tan Yong Boon Jul 28 '22 at 02:33
  • I was just showing you the first step. You continue substituting until you get an expression. – Mark Jul 28 '22 at 02:34
  • Oh I see. Thanks! Will attempt to do it with your method – Tan Yong Boon Jul 28 '22 at 02:35
  • 1
    Also confusing is the the definition of `combinator` has two different variables named `y` in it, and you need to know which is which. The `lambda y: x(y)` should probably be easier to understand as `lambda z: x(z)`, since it has no relationship to the `y` that's the argument to the function. – Frank Yellin Jul 28 '22 at 02:35
  • @FrankYellin Why do you say that the "y" in lambda y: x(y) has no relationship to the y of the function? – Tan Yong Boon Jul 28 '22 at 02:37
  • @FrankYellin Is this something to do with alpha conversion? – Tan Yong Boon Jul 28 '22 at 02:38
  • 1
    Cause that's what lambda does. It binds a variable to a value within a scope. – Frank Yellin Jul 28 '22 at 02:41
  • Related: "[What are Free and Bound variables?](//stackoverflow.com/q/21855838/90527)", "[What is meant by 'Capture-avoiding substitutions'?](//stackoverflow.com/q/11239262/90527)" – outis Jul 28 '22 at 03:54

1 Answers1

1

(lambda x: lambda y: x(y))(lambda x:y) simplifies to (lambda y: (lambda x:y)(y)),

No. y is free in (lambda x:y), so applying (lambda x: lambda y: x(y)) by simply substituting the expression for x results in variable capture. If you are going to simplify the expression, you must first rewrite (lambda x: lambda y: x(y)) to an alpha-equivalent expression that has no bound variables with the same names as free variables of (lambda x:y) to avoid the capture. How to do this is left as an exercise.

outis
  • 75,655
  • 22
  • 151
  • 221