2021 Spring

Welcome to the homepage of CSE 645: Seminar in Languages (Spring 2021)!

General Information

Course description: We will read papers and discuss research ranging from high-level specifications (such as logic, rules, and sets) to algorithms and methods for efficient implementations, with a wide range of applications. For this semester, we will include the following four topics and possibly others: probabilistic programming, quantum computing, knowledge base languages, and languages for security. In particular, we will start each topic from scratch, and discuss the best overview and survey papers that lead to the state of the art. Everyone is welcome. If you are enrolled in the class, you are expected to attend a majority of the meetings and present at least a paper.

Hours: Thursdays, 11:30AM-12:50PM, on Google Meet https://meet.google.com/frd-aiqs-rkc

Instructors: Annie Liu, CR Ramakrishnan, Michael Kifer, David Warren, and Paul Fodor (contact: paul.fodor@stonybrook.edu).

Schedule

February 4, 2021: Organizational meeting

February 11, 2021: Matt will present his RPE on declarative graphical languages.

February 18, 2021: Yuheng will present his research on https://github.com/tiantiangao7/kalm

February 25, 2021: Anthony will present his research on his system https://github.com/TonyRipa/Leibniz

March 4, 2021: Dakota will present: Bettina Heim, Mathias Soeken, Sarah Marshall, Chris Granade, Martin Roetteler, Alan Geller, Matthias Troyer, and Krysta Svore. Quantum programming languages. Nature 2020. https://www.nature.com/articles/s42254-020-00245-7

March 11, 2021: We participate in a faculty candidate talk held at approximately the same time.

March 18, 2021: Xinyu will present: Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural Logic Machines. International Conference on Learning Representations (ICLR) 2019. https://openreview.net/pdf?id=B1xY-hRctX

March 25, 2021: Tanzir will present: Andrew J. Ko and Brad A. Myers. Debugging Reinvented: Asking and Answering Why and Why Not Questions about Program Behavior. ICSE 2008. https://www.cs.cmu.edu/~NatProg/papers/Ko2008JavaWhyline.pdf

April 1, 2021: Andrew will present: Deshmukh, Jyotirmoy, Horvat, Marko, Jin, Xiaoqing, Majumdar, Rupak, and Prabhu, Vinayak S. Testing Cyber-Physical Systems through Bayesian Optimization. ACM Transactions on Embedded Computing Systems. September 2017. Article No. 170. https://dl.acm.org/doi/abs/10.1145/3126521?casa_token=k1KtC628JYgAAAAA%3AVwbSpf_iTMeffmH9qj5bzbGji2GMGvUVZuwdNLFcwcsT0tYWlqgeWQ2sI59xeKh4Thkf-IVLOPiGlQ

April 8, 2021: Annie will discuss her paper with Matthew Castelllana: Discrete Math with Programming: A Principled Approach. SIGCSE2021. https://arxiv.org/pdf/2011.14059.pdf

April 15, 2021: Tuncay will present: From Expressive Grammars to Efficient Parsing Algorithms.

April 22, 2021: Riguzzi Fabrizio will talk about probabilistic logic programming.

April 29, 2021: Eric Keough will talk about InvTS (an invariant-driven transformation system).

May 6, 2021: Tom Schrijvers will present: Birthe Van Den Berg, Tom Schrijvers, Alexander Vandenbroucke. Forward or Reverse Mode Automatic Differentiation: What’s the Difference. Functional Pearl. IFIP WG2.1: virtual meeting Feb. 2021. https://ifipwg21wiki.cs.kuleuven.be/pub/IFIP21/OnlineFeb21/Deriving%20Automatic%20Differentiation.pdf

May 13, 2021: Marc Denecker, Linde Vanbesien and Maurice Bruynoogh: Logic programming and aggregates: Analyzing Semantics Using Approximation Fixpoint Theory

Aggregates such as cardinality, sum, min, max are expressive higher order language constructs. While they are easily understood by humans and have many useful applications, adding aggregates to logic programming and extensions such as datalog and answer set programming (ASP) has proven to be challenging. The literature offers many approaches that are not always compatible. In this seminar we revisit one of these approaches, the one based on Approximation Fixpoint Theory (AFT).

We begin with a technical contribution, showing how any 3-valued truth assignment for rule bodies with aggregates induces well-founded, stable and Kripke Kleene semantics. We then look how to plug in aggregates constructs in the informal semantics of logic programs as inductive definitions, and argue that the well-founded semantics of aggregate logic programs formalizes this definitional view. We also briefly point at some unbearable weakenesses of the aggregate logic programming formalism from a KR point of view, and show the easy way to eliminate them. This resuls in expressive and natural language construct that can be integrated in classical logics.

The last part of the seminar is technical again and focusses on the aggregate answer set programming. We introduce the abstract notion of a ternary satisfaction relation and define stable semantics in terms of it. We show that ternary satisfaction relations bridge the gap between the standard Gelfond-Lifschitz reduct, and stable semantics as defined in the framework of AFT. We analyse the properties of ternary satisfaction relations for handling aggregates in ASP programs.

Finally, we show how different methods for handling aggregates taken from the literature can be described in the framework and we study the corresponding ternary satisfaction relations.

Papers:

Below are some possible papers to discuss:

Gianluigi Greco, Sergio Greco, Ester Zumpano. A Logic Programming Approach to the Integration, Repairing and Querying of Inconsistent Databases. ICLP 2001.

Hai-Feng Guo, Gopal Gupta: A Simple Scheme for Implementing Tabled Logic Programming Systems Based on Dynamic Reordering of Alternatives. ICLP 2001.

Marc Denecker, Nikolay Pelov, Maurice Bruynooghe: Ultimate Well-Founded and Stable Semantics for Logic Programs with Aggregates. ICLP2001.

Martin Gebser, Roland Kaminski, Torsten Schaub: Complex optimization in answer set programming. 2011.

Fabrizio Riguzzi, Terrance Swift: The PITA system: Tabling and answer subsumption for reasoning under uncertainty. 2011.

Benjamin Bichsel, Maximilian Baader, Timon Gehr, Martin Vechev. "Silq: A High-Level Quantum Language with Safe Uncomputation and Intuitive Semantics". PLDI 2020. https://dl.acm.org/doi/pdf/10.1145/3385412.3386007

Nicos Angelopoulos, Jan Wielemaker. "Advances in Big Data Bio Analytics". https://arxiv.org/abs/1909.08254

Sifis Lagouvardos, Julian Dolby, Neville Grech, Anastasios Antoniadis and Yannis Smaragdakis. Static Analysis of Shape in TensorFlow Programs . 34th European Conference on Object-Oriented Programming (ECOOP 2020) . https://drops.dagstuhl.de/opus/volltexte/2020/13172/pdf/LIPIcs-ECOOP-2020-15.pdf

Will Crichton, Georgia Gabriela Sampaio, and Pat Hanrahan. Automating Program Structure Classification. SIGCSE2021. https://willcrichton.net/pdf/program-structure-classification-draft.pdf