I completely agree.
i.e You need to invalidate my "solution" ;-)
You mean like MyNum(2).plus(MyNum(3)).equals(MyNum(5)) // true ?
like MyNum(2).plus(MyNum(3)).equals(MyNum(5)) // true
.. and Best Practice would have been to extend Number.
Agreed. Almost entirely a duplicate, the term's reverse polish notation and postfix expression are even interchangeable...
You are absolutly right. I never use things like that in real code.
@damjan to my understanding revision 1 is very elegant because strict evaluation is extremely straightforward. non-strict evaluation gets muddy very quickly, requiring additional complexity in the evaluator. I only had very general understanding of these concepts before I began this project; working on this stuff has taught me a lot. It's less of a surprise to me now that most language use strict evaluation – I'm guessing it's because it's just ridiculous easy in comparison to non-strict. From what I can tell tho, it seems like strict evaluation is totally sufficient in almost all cases. non-strict evaluation mostly feels like a novelty unless we had machines that were very specifically designed for it – hence my interest in SECD and Krivine.
As an aside, I'd love to have an collection of Kata that focuses on the slight variances between each evaluation strategy with tests to ensure you've implemented them correctly. I think it would really help people to understand the the reason different strategies exist and the trade-offs involved in their implementations.
This comment is hidden because it contains spoiler information about the solution
@damjan Thanks again for taking the time to work thru the rough spots. I'm very passionate about the topic and it's nice interact with other lambda lovers. I'm equally impressed with your solution. I haven't seen how other people implement evaluators so one of the primary reasons I made this Kata was to learn from others. Before reading your answer, I had never even heard of deBruijn notation. I was initially trying to come up with ways to reduce under unapplied lambdas but I was finding it extremely difficult. I feel like deBruijn notation might be one step toward achieving that goal. Particularly, I was struggling with this notion that reducing under an unapplied lambda was almost like an eager evaluation (of sorts), but I wrote it off as unachievable because if we start evaluating under an unapplied lambda, we could put the evaluator into an infinite loop – at least a naive implementation would fall into that trap – I just couldn't figure out how to avoid it.
Anyway, this is really cool to see a solution that's so vastly different from mine. This is the first evaluator I've written1 so it's really neat to see I still have many of things to learn too. I'm going to review your answer more closely tomorrow. I'm very much a "understand code by working thru it with a pencil and paper" type of girl. It's likely I'll have some questions for you, so don't go too far ^_^
1 It went thru about 35 iterations before I ended up publishing it here. It first started out as a basic recursive strict evaluator using nothing but a switch; then some thunks for non-strict evaluation; then continuation passing style so that I could eventually use a trampoline to make it stack safe. I had memoisation for call-by-need working in previous iterations but once I switched to CPS, I couldn't get that working again. It'll be nice to revisit this after learning some more to see if I can improve this on other ways.
Wow, that's very accommodating of you! Thanks! :D I did pass the tests, but it took a little over a second. I feel defeated, relieved and also a little ashamed about how large my solution is compared to yours. Clearly I have a lot to learn!
EDIT: I'll try to implement some of the less naive ideas I had for the solution. But for now, I am pleased to finally be able to vote this 100%. Hope it gets the attention it deserves!
@damjan, yeah normal order is not an expectation, tho if you can manage to implement a normal order evaluator, it might help. The implementation in my solution uses call-by-name, so it doesn't reduce under an unapplied lambda.
Per your request, I did comment out tests 1 thru 23 and re-run my solution. In fact, just to be sure, I ran each test independently to ensure each one returned the expected result. My solution does pass each test independently and run as the complete 24-test suite.
What I could do do is change the test 24 to (eq #24 (Y fact #4)) to make it a little less intensive – that'd be about 90% less computation if my rough calculations are correct.
(eq #24 (Y fact #4))
It's really sad that codewars has this arbitrary 8 seconds to work with – it drastically limits the type of kata you can post here – and consequently the types of solutions that can be submitted. The choice between a practical and esoteric solution often is made for you as esoteric/creative answers are not always mindful of space/time but still arrive at the same answer. Oh well. I doubt there's anything we can do to change that now.
I was curious how long test 24 was taking on it's own. With test 24 exlucded, the test suite runs in about 350 ms. With all of the tests disabled, the test suite runs in about 300 ms – this means that codewars itself has an overhead of 300 ms. For my solution: