Code Monkey home page Code Monkey logo

Comments (2)

johnyf avatar johnyf commented on May 30, 2024

Adjusting the recursion limit is not a fail-proof solution, because a hard limit does exist. The general solution is to remove recursion. Nonetheless, another suggestion may allow to avoid this.

Though I am not familiar with the internals of the algorithm, a similar issue arises in flattening a syntax tree with more nested operators than the default recursion limit. Increasing the recursion limit is not a solution there, because an expression can have arbitrarily many operators. Clearly, an unbounded number of operators can't be handled (unless processing in a streaming fashion). Nonetheless, the bound can be increased significantly, compared to that imposed by the recursion limit.

The solution is to arrange the (associative) operators in a binary tree. The total number of operators is the same, but the recursion depth is their logarithm. So a the required recursion depth becomes logarithmic in the number of operators, as opposed to linear (which it was initially).

Sidenote: humans do not manually write expressions with more associative operators (e.g., conjunctions) than the recursion depth, but machines do. The expressions mentioned above are generated by a machine, so the number of conjunctions is unavoidable. At the same time, this also allows automatically generating them in a binary tree (using parentheses to prevent the parser from blindly applying the associativity of that operator, which would yield a linear tree).

As already noted, I am not familiar with the details of the layout algorithm, and whether its recursive calls can be arranged as a binary call tree, but it is a possibility that can avoid rewriting the whole algorithm in a non-recursive paradigm.

from grandalf.

bdcht avatar bdcht commented on May 30, 2024

I see what you mean (actually amoco/cas/expressions.py and associated parser.py illustrate this as well) but unfortunately the final phase of the layout algorithm does not involve binary operators.
It is really recursive "by nature" (like a factorial function is) and thus is very easy to implement this way.
Removing recursion is a pain but I don't see any other option here...

from grandalf.

Related Issues (19)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.