Kata

Implement a lambda function which takes a string (a lambda expression in RPN) and returns an object representation for that input string.

There are three different types of lambda terms:

• A variable: It is specified by its name. Just like a variable in JavaScript. E.g. the RPN string x defines a variable with name x.
• An abstraction λ: Combines a variable input and another lambda term as function body. E.g. the RPN string x y λ defines an abstraction and has the same meaning as the anonymous function x => y in JavaScript.
• An application @: Combines two lambda terms. E.g. the RPN string f x @ has the same meaning as the function application f(x) in JavaScript.

The object returned by the lambda function should have the following methods:

• toString(): Should return the same RPN string as given to the lambda function.
• free(): Should return an array of the names of all free variables in the lambda term. The array can have arbitrary order but should hold no duplicates.
  • A single variable is always free.
  • Free variables of an abstraction are the free variables of the body without the input variable.
  • Free variables of an application are the union of the free variables of both lambda terms.
• bound(): Should return an array of the names of all bound variables in the lambda term. The array can have arbitrary order but should hold no duplicates.
  • A single variable is never bound.
  • Bound variables of an abstraction are the union of the input variable name and the bound variables of the body.
  • Bound variables of an application are the union of the bound variables of both lambda terms.
• reduce(): Return a lambda object which is reduced (β-reduction):
  • A variable cannot be reduced further.
  • An abstraction is reduced to an abstraction with the same input but with reduced body.
  • An application is reduced like this:
    • Reduce both child lambda terms.
    • If the reduced left side is an abstraction, substitute every occurrence of the input variable of the abstraction in its body with the reduced right side of the application, and reduce again.
    • Otherwise, just apply the reduced terms to each other.
    • examples:

        x                 ->  x 
        x y λ             ->  x y λ
        f x @             ->  f x @
        x x λ y @         ->  y
        x x x @ λ y @     ->  y y @
        x x x x @ λ λ y @ ->  x x x @ λ