4 kyu

Lambda term reduction

35 of 62hhelwich
Description
Loading description...
Mathematics
Logic
Functional Programming
Algorithms
Trees
View
AllIssues2Questions2Suggestions1Show Resolved
  • Please sign in or sign up to leave a comment.
  • Little Turtle Avatar

    In the description, the reduce() method is required to return a lambda object, but the tests expect a string instead.

    • Kacarott Avatar

      Can you specify which tests? All the existing solutions I can see return a lambda object, and not a string...?

  • dfhwze Avatar

    Don't we need to know anything about alpha-reduction to pass this kata?

    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.

    You don't explain how we should "apply" terms.

    Otherwise, just apply the reduced terms to each other.
    • Little Turtle Avatar

      I'm also thinking about it (alpha-reduction). In general, the substitution operation requires that the variable "v" bound by an abstraction "lambda v.body" shouldn't be free in a term which is to replace some variable in the abstraction body (one can say "v" should be "fresh" for the substitution term). Otherwise, an alpha-reduction should be done to avoid changes in semantics. In some random tests such a situation may appear. In my solution https://www.codewars.com/kata/reviews/55f3256f0fd3072e02000115/groups/64f846e2717c5300019e476e, I throw an error then. Anyway, if I ignore it and "force" substitution with usual rules, all tests are passed.

  • ArpadGBondor Avatar

    This was a bit more difficult than I expected on 4 kyu... I liked it, but I didn't plan to spend half of my day with debugging today. :)

  • Kacarott Avatar

    Tests have been updated to use chai, and refactored. Reference solution had a rare bug, so I swapped it out before approval.

  • Kacarott Avatar

    How is this kata a part of -4 collections?? Either I don't understand the metric, or Codewars has a bug.

  • JohanWiltink Avatar
  • Voile Avatar

    Needs random tests

  • JohanWiltink Avatar

    The ß-reduction described is one step of reduction. The later tests (the Church encoded stuff) mostly require at least one extra step of reduction. However, OR TRUE FALSE crashes when I do a second step of reduction. I haven't yet figured out what the problem is. Otherwise, my solution seems to work (at least mostly) for doing that one step of reduction (I'm passing the first six blocks of tests, then it's hit-and-miss).

    When, in general, is it safe to do another step of reduction? When, in general, do I need to do another step of reduction?

    This is the second lambda evaluator kata I'm doing; for the first one (Lambda Calculus Evaluator) I wrote a greedy evaluator which, of course, tanked; now I have a lazy one, but it's tanking as well because it's too lazy. It's getting frustrating. :[ That's not a problem with the respective kata, I'm just missing something. But I don't know exactly what it is. There seems to be no middle ground between lazy and greedy. All my documentation research is getting me nowhere; this problem is just never mentioned.

    I don't even know if I'm asking for a very bad spoiler. But any help would be appreciated. If my problem isn't clear, I'm happy to expand.

    • JohanWiltink Avatar

      It's never safe to reduce another step, but you need to when finding yourself with abstraction value @ after reducing an application. This is not in the description.

      Also not in the description is that lazy evaluation will not be necessary for this kata.

      Question marked resolved by JohanWiltink 4 years ago