Certified programming with dependent types

We begin with the syntax of the source language. Inductive binop : Set := Plus | Times. Our first line of Coq code should be unsurprising to ML and Haskell programmers. We define an algebraic datatype binop to stand for the binary operators of our source language. There are just two wrinkles compared to ML and Haskell. First, we use the keyword Inductive, in place of data, datatype, or type. This is not just a trivial surface syntax difference; inductive types in Coq are much more expressive than garden variety algebraic datatypes, essentially enabling us to encode all of mathematics, though we begin humbly in this chapter. Second, there is the : Set fragment, which declares that we are defining a datatype that should be thought of as a constituent of programs. Later, we will see other options for defining datatypes in the universe of proofs or in an infinite hierarchy of universes, encompassing both programs and proofs, that is useful in higher-order constructions.