-
Notifications
You must be signed in to change notification settings - Fork 0
Open
Labels
enhancementNew feature or requestNew feature or request
Description
If you have a super deeply nested expression, the Evaluator#resolve method is susceptible to stack overflows.
We could rewrite using a stack and a while loop to avoid this problem. (This may make it easier to build a stack trace for error messages too)
here's a failing test:
conflisp-ruby/spec/conflisp/evaluator_spec.rb
Lines 23 to 32 in eed1adc
| # The Evaluator#resolve method is susceptible to stack overflows. | |
| # The test below uncovers that. | |
| # | |
| # it 'can evaluate nested expressions of arbitrary depth' do | |
| # expression = ['add', 0, 1] | |
| # 3843.times do | |
| # expression = ['add', expression, 1] | |
| # end | |
| # expect(evaluator.resolve(expression)).to eq(3844) | |
| # end |
Notes:
- Explanation of inorder tree traversal using a loop and a stack. https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
- Example of a stack and a loop in ruby parsing an AST https://gitlab.com/inko-lang/inko/blob/master/compiler/lib/inkoc/parser.rb#L184
Metadata
Metadata
Assignees
Labels
enhancementNew feature or requestNew feature or request