hongjisung / sygusml Goto Github PK
View Code? Open in Web Editor NEWSygus language function automatic synthesis base tool
License: MIT License
Sygus language function automatic synthesis base tool
License: MIT License
if then else 구문이 있으면, if then else 트리를 먼저 구성 후, terminal이 있는 구문들이 먼저 통과 되는지 테스트 하고 안되면 그 관련 파트는 전부 pruning한다.
make all
, make run_examples
을 돌렸을 때 수행되는
ocamlbuild -use-ocamlfind -use-menhir -r -package batteries -package z3 -tags thread -Is src/,src/types,src/utils,src/solver,benchmarks/ main.native
에서 타입 불일치 에러가 발생합니다.
로그:
~/sygusml$ make run_examples
ocamlbuild -clean
Finished, 0 targets (0 cached) in 00:00:00.
00:00:00 0 (0 ) STARTING -------- |ocamlbuild -use-ocamlfind -use-menhir -r -package batteries -package z3 -tags thread -Is src/,src/types,src/utils,src/solver,benchmarks/ main.native
+ ocamlfind ocamlc -c -thread -package z3 -package batteries -I src/solver -I src -I benchmarks -I src/utils -I src/types -o src/solver/z3solver.cmo src/solver/z3solver.ml
File "src/solver/z3solver.ml", line 8, characters 43-47:
Error: This expression has type Z3.Expr.expr
but an expression was expected of type Z3.AST.ASTVector.ast_vector
Command exited with code 2.
Compilation unsuccessful after building 20 targets (0 cached) in 00:00:01.
Makefile:7: recipe for target 'run_examples' failed
make: *** [run_examples] Error 10
실행환경은 다음과 같습니다.
~/sygusml$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 18.04.2 LTS
Release: 18.04
Codename: bionic
~/sygusml$ ocaml --version
The OCaml toplevel, version 4.05.0
~/sygusml$ opam --version
1.2.2
~/sygusml$ opam list
# Installed packages for system:
base-bigarray base Bigarray library distributed with the OCaml compiler
base-num base Num library distributed with the OCaml compiler
base-threads base Threads library distributed with the OCaml compiler
base-unix base Unix library distributed with the OCaml compiler
batteries 2.8.0 a community-maintained standard library extension
conf-gmp 1 Virtual package relying on a GMP lib system installation.
conf-m4 1 Virtual package relying on m4
conf-python-2-7 1.0 Virtual package relying on Python-2.7 installation.
depext 1.0.5 Query and install external dependencies of OPAM packages
menhir 20180905 LR(1) parser generator
num 0 The Num library for arbitrary-precision integer and ratio
ocamlbuild 0.12.0 OCamlbuild is a build system with builtin rules to easily
ocamlfind 1.8.0 A library manager for OCaml
z3 4.7.1 Z3 solver
~/sygusml$ git rev-parse HEAD
f062d07ce2dee338713be834d64e3ec442c02ea0
함수 body인 term을 제작하는 search 알고리즘 구상
DefaultGrammar에 필요한 재료들을 DefaultGrammar을 구현한 함수에 넘겨주기 위해 만듦
feature, logic, feature에 따라 function signature등
FwdDecls 나 Recursion이 true인 경우
Grammar가 없어서 grammar를 만들 때 함수를 사용할 수 있으므로
함수 사용에 사용하기 위한 함수 목록을 따로 분리해놓아야함
Grammar가 별도로 주어지지 않은 경우
주어진 logic과 constraint하에서
함수 바디를 구성하는데 가장 효율적인 grammar를 찾아내는 것
MakeNextSynFuncList.makeNextSynFuncList 의 결과로 나오는 다음 함수 중 중복된 표현 제거하기
ex) ite B I I 의 경우에
I I 가 1 0 혹은 0 1 인 경우를 모두 보아야 하는가?
아니면 B에서 <= 와 >=를 모두 grammar에 포함해야하는가?
이 프로젝트를 라이브러리화 시키는 작업
ocamldoc 을 사용해 프로젝트 document 제작
functional 한 자료구조 사용
search -> verify -> transformer로 이어지는 구현에서
한 개의 synthfun만 deffun으로 바꾸도록 구현되어있음
수정할 필요가 있다.
multifunction 에 대한 기본 sovler 코드
SyGuSML/src/solver/preprocessor.ml
Line 452 in 8821515
Preprocessor.preprocess 내의 analysisCmd
함수에서, Cmd
가 inv-constraint
로 시작하는 경우에도, 그 외의 어느 경우에도 analysisCmd
함수에 넘겨진 invfunclist
의 값을 갱신한 값은 나타나지 않는다.
#4 에서 작성된 src/solver/stringfier.ml 모듈의 cmdToSygusString 의 경우 SynthFun 과 SynthInv 내부 내용을 출력해주지 않아 AST 조작의 결과를 확인하지 못할 때가 있다.
ast 타입의 데이터를 sygus or z3 string으로 변환하는 과정에서
Datatypes 및 assert에 for-all 추가하는 것 필요
대칭적인 식 표현에서는 하나만 테스트한다.
ex) add x 1 === add 1 x 이므로 하나만 테스트
add, mul의 경우 대칭,
if B then I1 else I2에서 B에 사용할 부등식은 단방향만 필요
http://sygus.org/assets/pdf/SyGuS-IF_2.0.pdf 의 9 page 3.7에 나오는 대로
inv-constraint 를 desugar
z3 solver를 돌리기 위해서 필수
(declare-datatypes () (( LList nil (cons (head Int) (tail LList)))))
(define-fun f ((x LList)) Int (+ (+ 1 0) (head x)))
(assert (= (f (cons 4 nil)) 5) )
(assert (= (f (cons 0 nil)) 1) )
(assert (= (f nil) 0) )
(check-sat)
위와 같은 경우에 sat으로 처리되는 문제
(head nil)을 이상하게 처리
\" 부분을 파일에서 읽어서 파싱할 시 Lexer.LexicalError 발생
프로그램을 테스트 해볼 수 있는 벤치마크 제작
현재는 BitVector logic이 우선순위
참고자료
https://github.com/hongjisung/sygus1.0
https://github.com/kupl/SimplPublic/tree/master/benchmarks
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.