Soufflé (programming language)
Soufflé is an open source parallel logic programming language, influenced by Datalog.
Programming examples
Given a set of edges in a graph, the following program computes the set of (directed) edges between any two nodes. This is also known as the transitive closure of the edge relation.
.decl edge(x:number, y:number)
.input edge
.decl path(x:number, y:number)
.output path
path(x, y) :- edge(x, y).
path(x, y) :- path(x, z), edge(z, y).
Features
- Automatic index selection[1]
- Specialized parallel data structures,[2] including disjoint-sets,[3] B-trees,[4] and tries.[5]
Related tools
In addition to a compiler and an interpreter the Soufflé project also publishes:
- a profiler,
- a "provenance"-based debugger,[6]
- an "auto-scheduler" that chooses efficient query plans based on a profile, as in profile-guided optimization.[7]
References
Notes
- ^ Subotić, Pavle; Jordan, Herbert; Chang, Lijun; Fekete, Alan; Scholz, Bernhard (2018-10). "Automatic index selection for large-scale datalog computation". Proceedings of the VLDB Endowment. 12 (2): 141–153. doi:10.14778/3282495.3282500. ISSN 2150-8097.
{{cite journal}}: Check date values in:|date=(help) - ^ Jordan, Herbert; Subotić, Pavle; Zhao, David; Scholz, Bernhard (2022-01-25). "Specializing parallel data structures for Datalog". Concurrency and Computation: Practice and Experience. 34 (2). doi:10.1002/cpe.5643. ISSN 1532-0626.
- ^ Nappa, Patrick; Zhao, David; Subotić, Pavle; Scholz, Bernhard (2019-09). "Fast Parallel Equivalence Relations in a Datalog Compiler". 2019 28th International Conference on Parallel Architectures and Compilation Techniques (PACT): 82–96. doi:10.1109/PACT.2019.00015.
{{cite journal}}: Check date values in:|date=(help) - ^ Jordan, Herbert; Subotić, Pavle; Zhao, David; Scholz, Bernhard (2019-02-16). "A specialized B-tree for concurrent datalog evaluation". Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming. PPoPP '19. New York, NY, USA: Association for Computing Machinery: 327–339. doi:10.1145/3293883.3295719. ISBN 978-1-4503-6225-2.
- ^ Jordan, Herbert; Subotić, Pavle; Zhao, David; Scholz, Bernhard (2019-02-17). "Brie: A Specialized Trie for Concurrent Datalog". Proceedings of the 10th International Workshop on Programming Models and Applications for Multicores and Manycores. PMAM'19. New York, NY, USA: Association for Computing Machinery: 31–40. doi:10.1145/3303084.3309490. ISBN 978-1-4503-6290-0.
- ^ Zhao, David; Subotić, Pavle; Scholz, Bernhard (2020-04-17). "Debugging Large-scale Datalog: A Scalable Provenance Evaluation Strategy". ACM Transactions on Programming Languages and Systems. 42 (2): 7:1–7:35. doi:10.1145/3379446. ISSN 0164-0925.
- ^ Arch, Samuel; Hu, Xiaowen; Zhao, David; Subotić, Pavle; Scholz, Bernhard (2022). Villanueva, Alicia (ed.). "Building a Join Optimizer for Soufflé". Logic-Based Program Synthesis and Transformation. Cham: Springer International Publishing: 83–102. doi:10.1007/978-3-031-16767-6_5. ISBN 978-3-031-16767-6.
{{cite journal}}: no-break space character in|title=at position 11 (help)
Sources
- Jordan, Herbert; Scholz, Bernhard; Subotić, Pavle (2016). Chaudhuri, Swarat; Farzan, Azadeh (eds.). "Soufflé: On Synthesis of Program Analyzers". Computer Aided Verification. Cham: Springer International Publishing: 422–430. doi:10.1007/978-3-319-41540-6_23. ISBN 978-3-319-41540-6.
- Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (2017-06-18). "Porting doop to Soufflé: a tale of inter-engine portability for Datalog-based analyses". Proceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis. SOAP 2017. New York, NY, USA: Association for Computing Machinery: 25–30. doi:10.1145/3088515.3088522. ISBN 978-1-4503-5072-3.