Seminaive Evaluation for a Higher-Order Functional Language

被引:12
作者
Arntzenius, Michael [1 ]
Krishnaswami, Neel [2 ]
机构
[1] Univ Birmingham, Sch Comp Sci, Birmingham B15 2TT, W Midlands, England
[2] Univ Cambridge, Dept Comp Sci & Technol, Cambridge CB2 1TN, England
来源
PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL | 2020年 / 4卷 / POPL期
关键词
Datafun; Datalog; functional languages; relational languages; seminaive evaluation; incremental computation;
D O I
10.1145/3371090
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
One of the workhorse techniques for implementing bottom-up Datalog engines is seminaive evaluation. This optimization improves the performance of Datalog's most distinctive feature: recursively defined predicates. These are computed iteratively, and under a naive evaluation strategy, each iteration recomputes all previous values. Seminaive evaluation computes a safe approximation of the difference between iterations. This can asymptotically improve the performance of Datalog queries. Seminaive evaluation is defined partly as a program transformation and partly as a modified iteration strategy, and takes advantage of the first-order nature of Datalog code. This paper extends the seminaive transformation to higher-order programs written in the Datafun language, which extends Datalog with features like first-class relations, higher-order functions, and datatypes like sum types.
引用
收藏
页数:28
相关论文
共 28 条
[11]   Differential categories [J].
Blute, R. F. ;
Cockett, J. R. B. ;
Seely, R. A. G. .
MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2006, 16 (06) :1049-1083
[12]   A Theory of Changes for Higher-Order Languages Incrementalizing λ-Calculi by Static Differentiation [J].
Cai, Yufei ;
Giarrusso, Paolo G. ;
Rendel, Tillmann ;
Ostermann, Klaus .
ACM SIGPLAN NOTICES, 2014, 49 (06) :145-155
[13]  
Ceri S., 1989, IEEE Transactions on Knowledge and Data Engineering, V1, P146, DOI 10.1109/69.43410
[14]   Complexity and expressive power of logic programming [J].
Dantsin, E ;
Eiter, T ;
Gottlob, G ;
Voronkov, A .
ACM COMPUTING SURVEYS, 2001, 33 (03) :374-425
[15]  
de Moor O, 2008, LECT NOTES COMPUT SC, V5235, P78, DOI 10.1007/978-3-540-88643-3_3
[16]   The differential lambda-calculus [J].
Ehrhard, T ;
Regnier, L .
THEORETICAL COMPUTER SCIENCE, 2003, 309 (1-3) :1-41
[17]  
Fourtounis George, 2019, V109
[18]   Incremental λ-Calculus in Cache-Transfer Style Static Memoization by Program Transformation [J].
Giarrusso, Paolo G. ;
Regis-Gianas, Yann ;
Schuster, Philipp .
PROGRAMMING LANGUAGES AND SYSTEMS, ESOP 2019: 28TH EUROPEAN SYMPOSIUM ON PROGRAMMING, 2019, 11423 :553-580
[19]  
Hickey Rich, 2012, DATOMIC FULLY T CLOU
[20]  
Hofmann M, 1998, LECT NOTES COMPUT SC, V1414, P275, DOI 10.1007/BFb0028020