Idris (programming language)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Idris
Paradigm Functional
Designed by Edwin Brady
0.9.18 / May 17, 2015 (2015-05-17)
OS Cross-platform
License BSD-3
.idr, .lidr
Website Idris website

Idris is a general-purpose pure functional programming language with dependent types. The type system is similar to the one used by Agda.

The language supports interactive theorem-proving comparable to Coq, including tactics, while the focus remains on general-purpose programming even before theorem-proving. Other goals of Idris are "sufficient" performance, easy management of side-effects and support for implementing embedded domain specific languages.

As of October 2014, Idris compiles to C and relies on a custom copying garbage collector using Cheney's algorithm. There also exist JavaScript and Java backends, and a partial LLVM backend.[2]

The name Idris goes back to the character of the singing dragon in the 70's UK kids' program Ivor the Engine.[3]

Features[edit]

Idris combines a number of features from relatively mainstream functional programming languages with features borrowed from proof assistants, in effect blurring the boundary between the two kinds of software.

Functional programming[edit]

The Syntax of Idris shows many similarities with that of Haskell. A hello world program in Idris might look like this:

module Main

main : IO ()
main = putStrLn "Hello, World!"

The only differences between this program and its Haskell equivalent are the single colon (instead of two) in the signature of the main function and the omission of the word "where" in the module declaration.

Inductive and parametric data types[edit]

Like most modern functional programming languages, Idris supports a notion of inductively-defined data type and parametric polymorphism. Such types can be defined both in traditional "Haskell98" syntax:

data Tree a = Node (Tree a) (Tree a) | Leaf a

or in the more general GADT syntax:

data Tree : Type -> Type where
    Node : Tree a -> Tree a -> Tree a
    Leaf : a -> Tree a

Dependent types[edit]

With dependent types, it is possible for values to appear in the types; in effect, any value-level computation can be performed during typechecking. The following defines a type of lists of statically known length, traditionally called 'vectors':

data Vect : Nat -> Type -> Type where
  Nil  : Vect 0 a
  (::) : (x : a) -> (xs : Vect n a) -> Vect (n + 1) a

This type can be used as follows:

total
append : Vect n a -> Vect m a -> Vect (n + m) a
append Nil       ys = ys
append (x :: xs) ys = x :: append xs ys

The functions appends a vector of m elements of type a to a vector of n elements of type a. Since the precise types of the input vectors depend on a value, it is possible to be certain at compile-time that the resulting vector will be have exactly (n + m) elements of type a. The word "total" invokes the totality checker which will report an error if the marked function doesn't cover all possible cases.

Another common example is pairwise addition of two vectors that are parameterized over their length:

total
pairAdd : Num a => Vect n a -> Vect n a -> Vect n a
pairAdd Nil       Nil       = Nil
pairAdd (x :: xs) (y :: ys) = x + y :: pairAdd xs ys

Num a signifies that the type a belongs to the type class Num. Note that this function still typechecks successfully as total, even though there is no case matching Nil in one vector and a number in the other. Since both vectors are ensured by the type system to have exactly the same length, we can be sure at compile time that this case will not occur. Hence it does not need to be mentioned for the function to be total.

Proof assistant features[edit]

Dependent types are powerful enough to encode most properties of programs, and an Idris program can prove invariants at compile-time. This makes Idris into a proof assistant.

There are two standard ways of interacting with proof assistants: by writing a series of tactic invocations (Coq style), or by interactively elaborating a proof term (Epigram/Agda style). Idris supports both modes of interaction, although the set of available tactics is not yet as useful as that of Coq.

Code generation[edit]

Because Idris contains a proof assistant, Idris programs can be written to pass proofs around. If treated naively, such proofs remain around at runtime. Idris aims to avoid this pitfall by aggressively erasing unused terms,[4] with promising results.[5]

By default, Idris generates native code by going through C. Other backends are available for generating Javascript and Java.

References[edit]

See also[edit]

External links[edit]