DROPS

Document

DOI: 10.4230/LIPIcs.ECOOP.2024.45

Higher-Order Specifications for Deductive Synthesis of Programs with Pointers

Authors: David Young, Ziyi Yang, Ilya Sergey, and Alex Potanin

Published in: LIPIcs, Volume 313, 38th European Conference on Object-Oriented Programming (ECOOP 2024)

Abstract

Synthetic Separation Logic (SSL) is a formalism that powers SuSLik, the state-of-the-art approach for the deductive synthesis of provably-correct programs in C-like languages that manipulate heap-based linked data structures. Despite its expressivity, SSL suffers from two shortcomings that hinder its utility. First, its main specification component, inductive predicates, only admits first-order definitions of data structure shapes, which leads to the proliferation of "boiler-plate" predicates for specifying common patterns. Second, SSL requires concrete definitions of data structures to synthesise programs that manipulate them, which results in the need to change a specification for a synthesis task every time changes are introduced into the layout of the involved structures. We propose to significantly lift the level of abstraction used in writing Separation Logic specifications for synthesis - both simplifying the approach and making the specifications more usable and easy to read and follow. We avoid the need to repetitively re-state low-level representation details throughout the specifications - allowing the reuse of different implementations of the same data structure by abstracting away the details of a specific layout used in memory. Our novel high-level front-end language called Pika significantly improves the expressiveness of SuSLik. We implemented a layout-agnostic synthesiser from Pika to SuSLik enabling push-button synthesis of C programs with in-place memory updates, along with the accompanying full proofs that they meet Separation Logic-style specifications, from high-level specifications that resemble ordinary functional programs. Our experiments show that our tool can produce C code that is comparable in its performance characteristics and is sometimes faster than Haskell.

Cite as

David Young, Ziyi Yang, Ilya Sergey, and Alex Potanin. Higher-Order Specifications for Deductive Synthesis of Programs with Pointers. In 38th European Conference on Object-Oriented Programming (ECOOP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 313, pp. 45:1-45:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{young_et_al:LIPIcs.ECOOP.2024.45,
  author =	{Young, David and Yang, Ziyi and Sergey, Ilya and Potanin, Alex},
  title =	{{Higher-Order Specifications for Deductive Synthesis of Programs with Pointers}},
  booktitle =	{38th European Conference on Object-Oriented Programming (ECOOP 2024)},
  pages =	{45:1--45:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-341-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{313},
  editor =	{Aldrich, Jonathan and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2024.45},
  URN =		{urn:nbn:de:0030-drops-208946},
  doi =		{10.4230/LIPIcs.ECOOP.2024.45},
  annote =	{Keywords: Program Synthesis, Separation Logic, Functional Programming}
}

Document

Artifact

DOI: 10.4230/DARTS.10.2.25

Higher-Order Specifications for Deductive Synthesis of Programs with Pointers (Artifact)

Authors: David Young, Ziyi Yang, Ilya Sergey, and Alex Potanin

Published in: DARTS, Volume 10, Issue 2, Special Issue of the 38th European Conference on Object-Oriented Programming (ECOOP 2024)

Abstract

This artifact provides a translator from Pika code to SuSLik specifications. Additionally, it contains a test suite and benchmark suite. These suites are fully automated using provided scripts. All source code is included.

Cite as

David Young, Ziyi Yang, Ilya Sergey, and Alex Potanin. Higher-Order Specifications for Deductive Synthesis of Programs with Pointers (Artifact). In Special Issue of the 38th European Conference on Object-Oriented Programming (ECOOP 2024). Dagstuhl Artifacts Series (DARTS), Volume 10, Issue 2, pp. 25:1-25:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{young_et_al:DARTS.10.2.25,
  author =	{Young, David and Yang, Ziyi and Sergey, Ilya and Potanin, Alex},
  title =	{{Higher-Order Specifications for Deductive Synthesis of Programs with Pointers (Artifact)}},
  pages =	{25:1--25:2},
  journal =	{Dagstuhl Artifacts Series},
  ISBN =	{978-3-95977-342-3},
  ISSN =	{2509-8195},
  year =	{2024},
  volume =	{10},
  number =	{2},
  editor =	{Young, David and Yang, Ziyi and Sergey, Ilya and Potanin, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.10.2.25},
  URN =		{urn:nbn:de:0030-drops-209239},
  doi =		{10.4230/DARTS.10.2.25},
  annote =	{Keywords: Program Synthesis, Separation Logic, Functional Programming}
}

Search Results

Documents authored by Young, David

Higher-Order Specifications for Deductive Synthesis of Programs with Pointers

Abstract

Cite as

Higher-Order Specifications for Deductive Synthesis of Programs with Pointers (Artifact)

Abstract

Cite as

Thanks for your feedback!

Could not send message