4 ms·

Would there be AI methods that would produce deterministic results for code formatting? Deterministic output seems to be the main draw of a code formatter.

pmoriarty 9y ago
The code formatter described in the article is not deterministic either. The author admits the search space is far too large for him to brute-force it, so his formatter does the best it can, which might not get the optimal results: "If the line splitter tries, like, 5,000 solutions and still hasn't found a winner yet, it just picks the best it found so far and bails." This sounds like it would give no more guarantees of a deterministic result than AI methods would. They also try their best, only search a subset of the search space, and bail when user-defined criteria such as time, iteration, or space limits are reached. Another approach could be to use both the author's hand-crafted algorithm and an AI method. There are at least two ways to go about that. The first would be to run the hand-crafted algorithm and pass its evaluation of the best solutions to seed an AI method (for example, as the seed populations in an evolutionary algorithm). The second would be to do the opposite, and run the AI method first, and seed the hand-crafted algorithm with the best solutions the AI method discovered.
- deleted 9y ago
  [deleted]
- acchow 9y ago
  The chosen quote doesn't indicate whether or not it's deterministic.
- jpfed 9y ago
  ...But if, for the same input, it always tries the same candidates in the same order, then it is deterministic.
- bradleyjg 9y ago
  I doesn't look like that stopping time is user-defined, it's a compiled in constant. Given that, I don't see any reason why the algorithm should be non-deterministic just because it gives up after a set number of iterations. As long every time it sees a given string it tries the possibilities in the same order, scores them the same way, and stops at the same place then it should be deterministic.
  - pmoriarty 9y ago
    By "user-defined", I meant to refer to the user of the algorithm (AI or not), who is the developer. You're right that if the algorithm described in the article will always get the same result given the same input it will be deterministic in a way that the kinds of AI methods I'm thinking of (the stochastic kind) will not. That sort of non-determinism will be a problem if you expect your code to be formatted the same way every time it goes through the formatter.
mzl 9y ago
There are lots of "AI methods" that can be used to produce deterministic results. In general, this sounds like a problem where combinatorial optimization techniques can be useful. For example, constraint programming, mixed integer programming, and various local search methods. For all techniques, there are both deterministic and non-deterministic approaches.
yters 9y ago
Set the random seed?

pmoriarty 9y ago

The code formatter described in the article is not deterministic either. The author admits the search space is far too large for him to brute-force it, so his formatter does the best it can, which might not get the optimal results: "If the line splitter tries, like, 5,000 solutions and still hasn't found a winner yet, it just picks the best it found so far and bails." This sounds like it would give no more guarantees of a deterministic result than AI methods would. They also try their best, only search a subset of the search space, and bail when user-defined criteria such as time, iteration, or space limits are reached. Another approach could be to use both the author's hand-crafted algorithm and an AI method. There are at least two ways to go about that. The first would be to run the hand-crafted algorithm and pass its evaluation of the best solutions to seed an AI method (for example, as the seed populations in an evolutionary algorithm). The second would be to do the opposite, and run the AI method first, and seed the hand-crafted algorithm with the best solutions the AI method discovered.

deleted 9y ago
[deleted]
acchow 9y ago
The chosen quote doesn't indicate whether or not it's deterministic.
jpfed 9y ago
...But if, for the same input, it always tries the same candidates in the same order, then it is deterministic.
bradleyjg 9y ago
I doesn't look like that stopping time is user-defined, it's a compiled in constant. Given that, I don't see any reason why the algorithm should be non-deterministic just because it gives up after a set number of iterations. As long every time it sees a given string it tries the possibilities in the same order, scores them the same way, and stops at the same place then it should be deterministic.
- pmoriarty 9y ago
  By "user-defined", I meant to refer to the user of the algorithm (AI or not), who is the developer. You're right that if the algorithm described in the article will always get the same result given the same input it will be deterministic in a way that the kinds of AI methods I'm thinking of (the stochastic kind) will not. That sort of non-determinism will be a problem if you expect your code to be formatted the same way every time it goes through the formatter.

mzl 9y ago

There are lots of "AI methods" that can be used to produce deterministic results. In general, this sounds like a problem where combinatorial optimization techniques can be useful. For example, constraint programming, mixed integer programming, and various local search methods. For all techniques, there are both deterministic and non-deterministic approaches.

yters 9y ago

Set the random seed?