LLM-powered Datalog Code Translation and Incremental Program Analysis Framework

Datalog, a declarative logic programming language, is widely applied in various fields. In recent years, there has been a growing interest in Datalog from both the academic and industrial communities, leading to the design and development of multiple Datalog engines and corresponding dialects. However, one problem brought about by the multiple dialects is that the code implemented in one Datalog dialect generally cannot be executed on the engine of another dialect. Therefore, when a new Datalog engine is adopted, the existing Datalog code needs to be translated into the new dialect. The current Datalog code translation techniques can be classified into two categories: manually rewriting the code and manually designing translation rules, which have problems such as being time-consuming, involving a large amount of repetitive work, and lacking flexibility and scalability. In this work, a Datalog code translation technique empowered by large language model (LLM) is proposed. By leveraging the powerful code understanding and generation capabilities of LLMs, through the divide-and-conquer translation strategy, the prompt engineering based on few-shot and chain-of-thought prompts, and an iterative error-correction mechanism based on check-feedback-correction, high-precision code translation between different Datalog dialects can be achieved, reducing the workload of developers in repeatedly developing translation rules. Based on this code translation technique, a general Datalog-based declarative incremental program analysis framework is designed and implemented. The performance of the proposed LLM-powered Datalog code translation technique is evaluated on different Datalog dialect pairs, and the evaluation results verify the effectiveness of the proposed code translation technique. This paper also conducts an experimental evaluation of the general declarative incremental program analysis framework, verifying the speedup effect of incremental program analysis based on the proposed code translation technique.