Open Systems Laboratory at Illinois

Synthesizing geometry constructions

By Sumit Gulwani, Vijay Anand Korthikanti, and Ashish Tiwari. In PLDI, 50–61. ACM, 2011.

Full Text:
Download PDF
Publisher Link:
http://doi.acm.org/10.1145/1993498.1993505

Abstract

In this paper, we study the problem of automatically solving ruler/compass based geometry construction problems. We first introduce a logic and a programming language for describing such constructions and then phrase the automation problem as a program synthesis problem. We then describe a new program synthesis technique based on three key insights: (i) reduction of symbolic reasoning to concrete reasoning (based on a deep theoretical result that reduces verification to random testing), (ii) extending the instruction set of the programming language with higher level primitives (representing basic constructions found in textbook chapters, inspired by how humans use their experience and knowledge gained from chapters to perform complicated constructions), and (iii) pruning the forward exhaustive search using a goal-directed heuristic (simulating backward reasoning performed by humans). Our tool can successfully synthesize constructions for various geometry problems picked up from high-school textbooks and examination papers in a reasonable amount of time. This opens up an amazing set of possibilities in the context of making classroom teaching interactive.

BibTeX

@inproceedings{conf/pldi/GulwaniKT11,
    author = "Gulwani, Sumit and Korthikanti, Vijay Anand and Tiwari,
              Ashish",
    editor = "Hall, Mary W. and Padua, David A.",
    title = "Synthesizing geometry constructions",
    booktitle = "PLDI",
    crossref = "conf/pldi/2011",
    ee = "http://doi.acm.org/10.1145/1993498.1993505",
    keywords = "formal methods",
    pages = "50-61",
    year = "2011",
}

@proceedings{conf/pldi/2011,
    editor = "Hall, Mary W. and Padua, David A.",
    title = "Proceedings of the 32nd ACM SIGPLAN Conference on
             Programming Language Design and Implementation, PLDI 2011, San
             Jose, CA, USA, June 4-8, 2011",
    isbn = "978-1-4503-0663-8",
    publisher = "ACM",
    year = "2011",
}