Getting Started
Installation Guide
Tutorial
Issue Tracker
Tools
Verifier
Alpinist
VeSUV
VeyMont
Showcases
Publications
About
VerCors Team
News
Contact
Credits
License
Induction lemma (succeeding)
A lemma, written out as a PVL function, that applies induction on the length of an input list.
General Information
Backend
: Silicon
Language
: PVL
Features
: Sequences
Path to Example File
: manual/induction-lemma.pvl
Should Verify
: Yes
Date
: 2017-06-20
Lines of Code
: 18 (comments not included)
Lines of Specification
: 4 (22.2% of total)
Computation Time
: 19.2 seconds
// -*- tab-width:2 ; indent-tabs-mode:nil -*- //:: cases InductionSolution //:: tools silicon //:: verdict Pass class C { static int len(seq<int> xs)=|xs|==0? 0 : 1 + len(tail(xs)); void main(seq<int> xs,seq<int> ys){ lemma(xs,ys); assert len(xs+ys)==len(xs)+len(ys); } ensures len(xs+ys)==len(xs)+len(ys); void lemma(seq<int> xs,seq<int> ys){ if (|xs|==0){ assert xs+ys==ys; } else { lemma(tail(xs),ys); assert tail(xs+ys)==tail(xs)+ys; } } }
Language:
PVL
Java
Cuda
C / OpenMP / OpenCL
Viper