ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
I'm developing a tool that work as "reverse c++ processing", this tool parse the source code and find out all the argument and input that needed by a program to reach certain line in source code. The detail is in http://www.revexecute.com. Please give comment. I'm actually looking for partner for the development as well.
Sorry, but I don't think what you're attempting is feasible. Static lexical analysis of a program isn't enough to determine which code path gets executed, you would have to also take into account the dynamic execution environment. This is especially true of a multi-threaded / event driven program.
In effect what you're trying to do is solve the Halting Problem, which has been proved by Alan Turing to be unsolvable for Turing Machines (all current computers). The Halting Problem is that given a description of an arbitrary computer program (your source) decide whether the program finishes running or not (reaches a particular point of code).
If I get it right, the Halting Problem says that there is no universal program which can decide this for all algorithms. Nevertheless someone could write a program which could output “yes”, “no” or “don’t know” for a given algorithm.
If I get it right, the Halting Problem says that there is no universal program which can decide this for all algorithms. Nevertheless someone could write a program which could output “yes”, “no” or “don’t know” for a given algorithm.
Yes, you're right. For some programs it's trivial - a singe line Hello World program would be an example where you could decide, however the OP was planning on writing a piece of software that did it for all programs, which is a different matter altogether. Additionally, it's not easy to write a program to determine which category a given program would fall into.
It's possible to look at a simple program yourself and decide if it finishes or not, but that's because you're using a highly parallel pattern recognition engine with heuristics built up through experience, i.e. your brain, but writing a piece of software that does the same thing is significantly more challenging.
Quote:
Originally Posted by famsinyi
It really make sense if someone had concluded that 'Halting problem' is not solvable.
Not just "somebody", but Alan Turing, one of the titans of computer science! To quote wikipedia: "Turing is widely considered to be the father of computer science and artificial intelligence."
I remembered when I analysed while loop and recursive function for my tool, a purposely weirdly written loop or recursive function could easily defeats my algorithm. But such loop or function seems really weird until most programmers couldn't understand what it is trying to do, or there is no real world application would need such a function, loop (If you guys need an example, I could prepare). If the tool is targeted for applications that human could understand, I believe it is feasible.
A study called 'dynamic program slicing' has the same objective with what I'm trying to do. May I know anyone of you feel this kind of tool useful? Or it is just a kind of 'advance' debugging tool that will not be widely used?
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.