Code Monkey home page Code Monkey logo

synquid's Introduction

Synquid

Synquid synthesizes programs from refinement types.

For example, given the following type as the specification:

replicate :: n:Nat -> x:a -> {List a | len _v = n}

and an appropriate set of components, Synquid will automatically generate a program:

replicate = \n . \x .
  if n <= 0
    then Nil
    else Cons x (replicate (dec n) x)

Synquid is based on the combination of bidirectional synthesis and liquid types.

News

April 5, 2022: A docker for Synquid is avaiable now! Thanks to yinergy!

June 18, 2016: Synquid mode for Emacs is now available on MELPA! Thanks to Clément Pit--Claudel!

June 16, 2016: The Synquid paper was presented at PLDI'16 in Santa Barbara!

Try Synquid

  • Try in your browser!
  • Build from source: You will need stack and z3 version 4.7.1. Clone this repository and then run stack setup && stack build from its top-level directory. You can then run synquid using stack exec -- synquid [args].

Testimonials

testimonial.png

synquid's People

Contributors

aleksandarmilicevic avatar corwin-of-amber avatar garciat avatar ikuraj avatar isaacg1 avatar kevinhine avatar nadia-polikarpova avatar sevko avatar tjknoth avatar vinaymayar avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar

synquid's Issues

Runtime error

I asked Synquid (via 'try online') a question that is a variation on the replicate problem, given below. I got this error (truncated for brevity):

/var/www/comcom/tmp/Synquid/9586857029030353/Synquid.sq:29: Error:
Cannot match shape 'List (A4)'
with shape 'Int'
when checking...

The way I read this error is as if synquid is synthesizing something that is not type correct, and then fail because of it. Therefore I believe this would be a bug in synquid. I'm not sure whether synquid should be able to give me sufficiently strong refinements for this particular input, but I do expect synquid's output to be either a solution or a more reasonable error message.

Not sure if and how you would like to see bugs like these reported, let me know or just take your liberties in editing this issue. Thanks for the amazing work in building Synquid!

-- Type synonym for natural numbers (_v denotes the "value variable")
type Nat = {Int | _v >= 0}

-- List data type: just like in Haskell
data List a where
	Nil :: List a
	Cons :: x: a -> xs: List a -> List a
  
-- Measures define recursive properties of datatypes, which we can mention in refinements; 
-- this measure is also marked as a termination metric for recursive calls
termination measure len :: List a -> {Int | _v >= 0} where
  Nil -> 0
  Cons x xs -> 1 + len xs 
  
-- Synquid composes programs from component functions;
-- here are some standard integer components we might need
one :: {Int | _v == 1}
minus :: x: Int -> {Int | _v == (0 - x)}
plus :: x: Int -> y: Int -> {Int | _v == x + y}
leq :: x: Int -> y: Int -> {Bool | _v == (x <= y)}
	
-- Our synthesis goal: a function that returns 'n' copies of 'x'
replicate :: n: Nat -> x: a -> {List a | len _v == n}
replicate = ??

Error with len > 3 but not len <= 3

Changing a line in the "list replicate" example on the ComCom website from:

replicate :: n: Nat -> x: a -> {List a | len _v == n}

to:

replicate :: x: a -> {List a | len _v == 4}

we see the following error:

/var/www/comcom/tmp/Synquid/0719913783814785/Synquid.sq:29: Error:
Cannot match shape 'Bool'
with shape '_'
when checking neq :: X1:_ -> X0:_ -> _
in
\x .
match neq ?? ?? with

If you instead use:

replicate :: x: a -> {List a | len _v == 3}

the following result is produced:

replicate = \x . Cons x (Cons x (Cons x Nil))

From my trivial investigation it appears that the simplifyContraint' function does not contain a case for one of the types being an LetT _ _ AnyT which I presume would constitute an empty constraint. This is me just guessing because it looks like simplifyContraint' already handles the AnyT case and that is the only RType whose pretty-printed shape could match "_" while also not being AnyT.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.