Coq Language

Introduction to Coq Language

Coq Language is a functional programming language and is dependently typed, which is used to write programs and verify that user specifications are met accordingly. This type of functional programming language is focused on simple and mathematical intuition. When viewed as a programming language, Coq implements a dependently typed functional programming language. And when viewed as a logical system, Coq implements a higher-order theory.

Why do we Need a Coq Language?

• The development of Coq is supported since 1984, initiated its development by Gerard Huet and Thierry Coquand; more than 40 people have contributed interesting features to the core system.
• Coq is mainly implemented with C, and the core system can be extended with a plug in mechanism.
• Coq is dependently typed; this type of methodology helps develop the software perfectly while code construction and possible bugs and exceptions are ruled out.
• This Coq language’s common features, being a functional language, include algebraic data types and pattern matching.
• It also gives ease of coding and manipulates rich data structures.
• Coq programming also offers polymorphic type structures supporting abstraction of code and reuse.
• Coq also provides a specification language known as Gallina.
• Programs written in Gallina have weak normalization property, which is a distinct property that implies programs always terminate.
• This particular feature is distinct in a way since infinite loops are too common in another programming language (Non Terminating programs).

Working of Coq Language or its Usage

Coq language is designed for developing mathematical proofs and also for writing formal specifications. It verifies the programs are correct or not with respect to the specifications. Gallina, the specification language represents the programs, properties and proofs for Coq language.
Coq language has Curry – Harvard Isomorphism technique. Using this, programs, properties and proofs and formalized to a language called Calculus of Inductive Constructions, which is an Alpha – Calculus with a rich type system.

In Coq, all logical judgements are typing judgements. The heart of Coq language is a type-checking algorithm, which checks the correctness of proofs. In other words, the Type checking algorithm checks if the program compiles to the specifications. Coq provides interactive proof assistant to build proofs using the specific programs called as tactics. All these services of Coq proof assistant are accessible by command language interpretation called as Vernacular. As Coq has an interactive mode where commands are interpreted as user types.

There are two types of modes where commands are processed from file:

• Interactive Mode: Users develop the theories and proofs quickly and query the system for theorems and definitions available. This type of interactive mode is run with the help of IDE, such as Coq Integrated Development Environment.
• Compiled Mode: This mode acts as a proof checker, which takes a file containing complete development in order to ensure correctness. Coq’s compiler provides an output file that contains a similar representation of the input. This mode runs with coqc command.

Advantages and Disadvantages of Coq Language

Given below are the advantages and disadvantages mentioned:

Advantages:

• Coq lacks many reasoning principles, which are common in mathematical practices.
• Coq language was designed to allow people to add the reasoning principles safely as extra axioms.
• It is easier to have this kind of reasoning since logic was built from the ground or from scratch.
• Coq has many powerful automation procedures such as congruence and omega, but these are not generally applicable and require more explicit proofs.

Disadvantages:

• This becomes a problem in proving simple theorems but makes an issue when the proof automation is not that powerful.
• Coq has tactic language for the writing of the proofs, known as Ltac. A different situation arises in supporting user-defined and proof automation procedures.
• Ltac has some design problems but allows users to encode fairly complicated proof automation procedures in a lightweight manner.
• Coq will also allow users to write plugins in Coq;s implementation language for some heavier tasks.
• There is only a single higher-level automation language, i.e. Ltac, and the only way to customize these programs is through plugins.
• Coq is more strict, using intuitionistic logic. It has several orders and allows type dependencies that are non-terminating in some of the circumstances.

Coq objects are sorted into two categories:

• Prop sort
• Type sort

1. Prop sort is for propositions. New predicates can be defined either inductively or by abstracting the existing propositions.

Typical propositions:

∀ A B : Prop, A /\ B -> B \/ B

∀ x y : Z, x * y = 0 -> x = 0 \/ y = 0

New predicated defined inductively:

Inductive even : N -> Prop :=

| even_0 : even 0

| even_S n : odd n -> even (n + 1)

with odd : N -> Prop :=

| odd_S n : even n -> odd (n + 1).

Abstracting existing propositions:

Definition divide (x y:N) := ∃ z, x * z = y.

Definition prime x := ∀ y, divide y x -> y = 1 \/ y = x.

2. Type sort is for mathematical structures and data types that are well-formed.

Basic Coq example:

Z -> Z * Z

Inductive structure:

Inductive nat : Set :=

| 0 : nat

| S : nat -> nat.

Inductive list (A:Type) : Type :=

| nil : list A

| cons : A -> list A -> list A.

Types of tuples:

Structure monoid := {
dom : Type ;
op : dom -> dom -> dom where "x * y" := (op x y);
id : dom where "1" := id;
assoc : ∀ x y z, x * (y * z) = (x * y) * z ;
left_neutral : ∀ x, 1 * x = x ;
right_neutral : ∀ x, x * 1 = x
}.

Examples of Coq Language

Given below are the examples of Coq Language:

Example #1

Simple module interactively.

Code:

Module M.
Definition T := nat.
Definition x := 0.
Definition y : bool.

Output:

Example #2

Definition of using N module type expression.

Code:

Module Type SIG'.
Definition T : Set := nat.
Parameter x : T.
End SIG'.
Module N : SIG' := M.
Module P <: SIG := M.
Print P.y.

Output:

Example #3

Functor creator.

Code:

Module Two (X Y: SIG).
Definition T := (X.T * Y.T)%type.
Definition x := (X.x, Y.x).
End Two
Module Q := Two M N.
Eval compute in (fst Q.x + snd Q.x).

Output:

A career in Coq Language

• There are a lot of career chances available in various countries, designed as an Operating Engineer.
• People with a passion for functional programming and an interest in mathematics, proof assistants( Coq ) can have people surrounded by like-minded individuals.
• Most of the candidate recruited in this particular technology should have a Degree in Mathematics or Computing and a Secondary Degree in MPhil.
• Have experience in functional programming, with design knowledge in simple and elegant solutions.
• Also should have experience in delivering enterprise quality software’s.

Conclusion

With this, we shall conclude the topic ‘Coq Language’. We have seen what Coq language is and how it works. We have also seen some of the advantages and disadvantages, their uses and how Coq language works. There are also career openings for this Coq language who have experience in proofs programming. We have also seen some of the examples with Coq IDE.

Recommended Articles

This is a guide to Coq Language. Here we discuss the introduction, need, working, advantages & disadvantages, examples and career in Coq language. You may also have a look at the following articles to learn more –

1. Best Programming Languages
2. Back End Programming Languages
3. Programming Errors in C
4. Functional Programming in JavaScript