## Sunday, July 10, 2011

After some discussion with Russel Wallace, I've come to a few conclusions about my procedural logic project.

1. FRP provides an in-principle answer: there is no essential problem with describing behavior-in-time in a logically pure way. You just assert some things about how a system behaves through time. There are certainly questions about the details, but the problem of describing actions with logic is not as nebulous as I was making it. It's computer science, not artificial intelligence.
2. The problem which is nebulous is the "reflection problem" that I mentioned in the previous post. This is the problem of making a system which dynamically reasons about and improves its own implementation. It's possible to reduce many aspects of this to computer science as well, but ultimately it is an "AI kind of thing" to worry about.
3. The main technique for making #2 more tractable is to "stage" the reflection, separating an action and reflection on that action. For example, the kind of dynamic priority assessment I was imagining (allowing reasoning about the priority of a task between the time when the task is added to the queue and its execution) is just not a great idea. It's better to reason about the priority of rules.
When it's possible to reduce something to a computer science problem rather than an AI problem, the results become more generally applicable. I mean two things by this. First, it's a computer science problem when it doesn't depend on any standpoint concerning what intelligence is, best approaches to achieving AI, et cetera. It cuts out philosophical stuff and just focuses on a practical problem, with no need to justify itself via claims about building a thinking machine within 20 years. Second, it generally falls within the polynomial-time asymptotic complexity class, rather than exponential-time. Exponential time problems are roughly where the need for methods we refer to as "AI" start, because we need to rely on heuristics for approximate problem-solving. Obviously there is an advantage if we can manage to work on poly-time problems rather than exp-time problems.

Whereas FRP-like solutions to the procedural logic question involve programs which only refer to their external behavior, and so can be implemented in whatever way is convenient, reflective procedural logic would refer to its implementation details. It's possible that it could still maintain a certain amount of purity, but it's difficult to say.

I'm working on a bare-bones implementation of Dyna, with the goal of seeing how much reflection I can conveniently add. I also have a few other goals for the project (but these are not high priorities):
• Integrate functional and logical programming, as with Curry and Mercury
• Integrate the pattern calculus, a generalization of lambda calculus for pattern matching
• Use a type system modeled after the one Qi uses
• Try FRP
• Try uniqueness types
We'll see how far I get. :)