Pure (programming language)
Encyclopedia
Pure is a dynamically typed, functional
programming language
based on term rewriting. It has facilities for user-defined operator
syntax, macros, multiple-precision numbers
, and compilation to native code through the LLVM. It is the successor to the Q programming language.
Pure comes with an interpreter and debugger, provides automatic memory management, and has powerful functional and symbolic programming capabilities as well as interface to C libraries (e.g. for numerics, low-level protocols, and other such tasks). At the same time, Pure is a "small" language designed from scratch; its interpreter is not large, and the library modules are written in Pure itself. The syntax of Pure resembles that of Miranda
and Haskell, but it is a free-format language and thus uses explicit delimiters (rather than indentation
) to indicate program structure.
The Pure language is a successor of the Q language created previously by the same author, Albert Gräf at the University of Mainz in Germany. Compared to Q, it offers some important new features (in particular, local functions with lexical scoping, efficient vector and matrix support and the built-in C interface) and programs run much faster as they are JIT-compiled
to native code on the fly. Pure is mostly aimed at mathematical applications and scientific computing currently, but its interactive interpreter environment, the C interface and the growing collection of addon modules make it suitable for a variety of other applications, such as artificial intelligence, symbolic computation, and real-time multimedia processing.
Pure plugins are available for the Gnumeric
spreadsheet and Miller Puckette's Pure Data
graphical multimedia software, which make it possible to extend these programs with functions written in the Pure language. Interfaces to GNU Octave
, OpenCV
, OpenGL
, the GNU Scientific Library
, FAUST
, SuperCollider
and liblo (for OSC) are also provided as library modules.
Pure is free software
distributed (mostly) under the GNU Lesser General Public License
version 3 (or later).
fib 0 = 0;
fib 1 = 1;
fib n = fib (n-2) + fib (n-1) if n>1;
Better (tail-recursive and linear-time) version:
fib n = fibs (0,1) n with
fibs (a,b) n = if n<=0 then a else fibs (b,a+b) (n-1);
end;
Compute the first 20 Fibonacci numbers:
map fib (1..20);
An algorithm
for the n queens problem
which employs a list comprehension to organize the backtracking search:
queens n = search n 1 [] with
search n i p = [reverse p] if i>n;
= cat [search n (i+1) ((i,j):p) | j = 1..n; safe (i,j) p];
safe (i,j) p = ~any (check (i,j)) p;
check (i1,j1) (i2,j2)
= i1
end;
While Pure uses eager evaluation
by default, it also supports lazy
data structures such as streams (lazy lists). For instance, here is a version of the sieve of Eratosthenes
which computes the stream of all prime numbers:
primes = sieve (2..inf) with
sieve (p:qs) = p : sieve [q | q = qs; q mod p] &;
end;
Note the use of the
to delay its computation. The thunk is evaluated implicitly and then memoized
(using call by need evaluation) when the corresponding part of the list is accessed, e.g.:
primes!!(0..99); // yields the first 100 primes
Pure has efficient support for vectors and matrices (similar to that provided by MATLAB
and GNU Octave
), including vector and matrix comprehensions. E.g., a Gaussian elimination
algorithm with partial pivoting can be implemented as follows in Pure:
gauss_elimination x::matrix = p,x
when n,m = dim x; p,_,x = foldl step (0..n-1,0,x) (0..m-1) end;
step (p,i,x) j
= if max_x0 then p,i,x else
// updated row permutation and index:
transp i max_i p, i+1,
{// the top rows of the matrix remain unchanged:
x!!(0..i-1,0..m-1);
// the pivot row, divided by the pivot element:
{x!(i,l)/x!(i,j) | l=0..m-1};
// subtract suitable multiples of the pivot row:
when
n,m = dim x; max_i, max_x = pivot i (col x j);
x = if max_x>0 then swap x i max_i else x;
end with
pivot i x = foldl max (0,0) [j,abs (x!j)|j=i..#x-1];
max (i,x) (j,y) = if x
/* Swap rows i and j of the matrix x. */
swap x i j = x!!(transp i j (0..n-1),0..m-1) when n,m = dim x end;
/* Apply a transposition to a permutation. */
transp i j p = [p!tr k | k=0..#p-1]
with tr k = if ki then j else if kj then i else k end;
/* Example: */
let x = dmatrix {2,1,-1,8; -3,-1,2,-11; -2,1,2,-3};
x; gauss_elimination x;
As a language based on term rewriting, Pure fully supports symbolic computation
with expressions. Here is an example showing the use of local rewriting rules to expand
and factor
simple arithmetic expressions:
expand = reduce with
(a+b)*c = a*c+b*c;
a*(b+c) = a*b+a*c;
end;
factor = reduce with
a*c+b*c = (a+b)*c;
a*b+a*c = a*(b+c);
end;
expand ((a+b)*2); // yields a*2+b*2
factor (a*2+b*2); // yields (a+b)*2
Calling C
functions from Pure is very easy. E.g., the following imports the
extern int puts(char*);
hello = puts "Hello, world!";
hello;
See also
External links
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
based on term rewriting. It has facilities for user-defined operator
Operator (programming)
Programming languages typically support a set of operators: operations which differ from the language's functions in calling syntax and/or argument passing mode. Common examples that differ by syntax are mathematical arithmetic operations, e.g...
syntax, macros, multiple-precision numbers
Arbitrary-precision arithmetic
In computer science, arbitrary-precision arithmetic indicates that calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system. This contrasts with the faster fixed-precision arithmetic found in most ALU hardware, which typically...
, and compilation to native code through the LLVM. It is the successor to the Q programming language.
Pure comes with an interpreter and debugger, provides automatic memory management, and has powerful functional and symbolic programming capabilities as well as interface to C libraries (e.g. for numerics, low-level protocols, and other such tasks). At the same time, Pure is a "small" language designed from scratch; its interpreter is not large, and the library modules are written in Pure itself. The syntax of Pure resembles that of Miranda
Miranda programming language
Miranda is a non-strict purely functional programming language designed by David Turner as a successor to his earlier programming languages SASL and KRC, using some concepts from ML and Hope. It was produced by Research Software Ltd...
and Haskell, but it is a free-format language and thus uses explicit delimiters (rather than indentation
Off-side rule
A computer programming language is said to adhere to the off-side rule if the scope of declarations in that language is expressed by their indentation. The term and the idea are attributed to Peter J. Landin, and the term can be seen as a pun on the offside law of football .- Definition :Peter J...
) to indicate program structure.
The Pure language is a successor of the Q language created previously by the same author, Albert Gräf at the University of Mainz in Germany. Compared to Q, it offers some important new features (in particular, local functions with lexical scoping, efficient vector and matrix support and the built-in C interface) and programs run much faster as they are JIT-compiled
Just-in-time compilation
In computing, just-in-time compilation , also known as dynamic translation, is a method to improve the runtime performance of computer programs. Historically, computer programs had two modes of runtime operation, either interpreted or static compilation...
to native code on the fly. Pure is mostly aimed at mathematical applications and scientific computing currently, but its interactive interpreter environment, the C interface and the growing collection of addon modules make it suitable for a variety of other applications, such as artificial intelligence, symbolic computation, and real-time multimedia processing.
Pure plugins are available for the Gnumeric
Gnumeric
Gnumeric is a spreadsheet program that is part of the GNOME Free Software Desktop Project. Gnumeric version 1.0 was released December 31, 2001. Gnumeric is distributed as free software under the GNU GPL license; it is intended to replace proprietary and other spreadsheet programs such as Microsoft...
spreadsheet and Miller Puckette's Pure Data
Pure Data
Pure Data is a visual programming language developed by Miller Puckette in the 1990s for creating interactive computer music and multimedia works. While Puckette is the main author of the program, Pd is an open source project with a large developer base working on new extensions to it. It is...
graphical multimedia software, which make it possible to extend these programs with functions written in the Pure language. Interfaces to GNU Octave
GNU Octave
GNU Octave is a high-level language, primarily intended for numerical computations. It provides a convenient command-line interface for solving linear and nonlinear problems numerically, and for performing other numerical experiments using a language that is mostly compatible with MATLAB...
, OpenCV
OpenCV
OpenCV is a library of programming functions mainly aimed at real time computer vision, developed by Intel and now supported by Willow Garage. It is free for use under the open source BSD license. The library is cross-platform. It focuses mainly on real-time image processing...
, OpenGL
OpenGL
OpenGL is a standard specification defining a cross-language, cross-platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex three-dimensional scenes from simple primitives. OpenGL...
, the GNU Scientific Library
GNU Scientific Library
In computing, the GNU Scientific Library is a software library written in the C programming language for numerical calculations in applied mathematics and science...
, FAUST
FAUST (programming language)
FAUST, that stands for Functional AUdio STream, is a programming language that provides a purely functional approach to signal processing while offering a high level of performance...
, SuperCollider
Supercollider
A Supercollider is a high energy particle accelerator. The term may refer to:* Superconducting Super Collider, planned 80 km project in Texas, canceled in 1993...
and liblo (for OSC) are also provided as library modules.
Pure is free software
Free software
Free software, software libre or libre software is software that can be used, studied, and modified without restriction, and which can be copied and redistributed in modified or unmodified form either without restriction, or with restrictions that only ensure that further recipients can also do...
distributed (mostly) under the GNU Lesser General Public License
GNU Lesser General Public License
The GNU Lesser General Public License or LGPL is a free software license published by the Free Software Foundation . It was designed as a compromise between the strong-copyleft GNU General Public License or GPL and permissive licenses such as the BSD licenses and the MIT License...
version 3 (or later).
Examples
The Fibonacci numbers (naive version):fib 0 = 0;
fib 1 = 1;
fib n = fib (n-2) + fib (n-1) if n>1;
Better (tail-recursive and linear-time) version:
fib n = fibs (0,1) n with
fibs (a,b) n = if n<=0 then a else fibs (b,a+b) (n-1);
end;
Compute the first 20 Fibonacci numbers:
map fib (1..20);
An algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for the n queens problem
Eight queens puzzle
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal...
which employs a list comprehension to organize the backtracking search:
queens n = search n 1 [] with
search n i p = [reverse p] if i>n;
= cat [search n (i+1) ((i,j):p) | j = 1..n; safe (i,j) p];
safe (i,j) p = ~any (check (i,j)) p;
check (i1,j1) (i2,j2)
= i1
i2 || j1
j2 || i1+j1i2+j2 || i1-j1
i2-j2;end;
While Pure uses eager evaluation
Eager evaluation
In computer programming, eager evaluation or greedy evaluation is the evaluation strategy in most traditional programming languages. In eager evaluation an expression is evaluated as soon as it gets bound to a variable. The term is typically used to contrast lazy evaluation, where expressions are...
by default, it also supports lazy
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
data structures such as streams (lazy lists). For instance, here is a version of the sieve of Eratosthenes
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
which computes the stream of all prime numbers:
primes = sieve (2..inf) with
sieve (p:qs) = p : sieve [q | q = qs; q mod p] &;
end;
Note the use of the
& operator which turns the tail of the sieve into a thunkThunk
Thunk may refer to:* Thunk , a piece of code to perform a delayed computation * Thunk : a feature of some virtual function table implementations...
to delay its computation. The thunk is evaluated implicitly and then memoized
Memoization
In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs...
(using call by need evaluation) when the corresponding part of the list is accessed, e.g.:
primes!!(0..99); // yields the first 100 primes
Pure has efficient support for vectors and matrices (similar to that provided by MATLAB
MATLAB
MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...
and GNU Octave
GNU Octave
GNU Octave is a high-level language, primarily intended for numerical computations. It provides a convenient command-line interface for solving linear and nonlinear problems numerically, and for performing other numerical experiments using a language that is mostly compatible with MATLAB...
), including vector and matrix comprehensions. E.g., a Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
algorithm with partial pivoting can be implemented as follows in Pure:
gauss_elimination x::matrix = p,x
when n,m = dim x; p,_,x = foldl step (0..n-1,0,x) (0..m-1) end;
step (p,i,x) j
= if max_x0 then p,i,x else
// updated row permutation and index:
transp i max_i p, i+1,
{// the top rows of the matrix remain unchanged:
x!!(0..i-1,0..m-1);
// the pivot row, divided by the pivot element:
{x!(i,l)/x!(i,j) | l=0..m-1};
// subtract suitable multiples of the pivot row:
when
n,m = dim x; max_i, max_x = pivot i (col x j);
x = if max_x>0 then swap x i max_i else x;
end with
pivot i x = foldl max (0,0) [j,abs (x!j)|j=i..#x-1];
max (i,x) (j,y) = if x
/* Swap rows i and j of the matrix x. */
swap x i j = x!!(transp i j (0..n-1),0..m-1) when n,m = dim x end;
/* Apply a transposition to a permutation. */
transp i j p = [p!tr k | k=0..#p-1]
with tr k = if ki then j else if kj then i else k end;
/* Example: */
let x = dmatrix {2,1,-1,8; -3,-1,2,-11; -2,1,2,-3};
x; gauss_elimination x;
As a language based on term rewriting, Pure fully supports symbolic computation
Symbolic computation
Symbolic computation or algebraic computation, relates to the use of machines, such as computers, to manipulate mathematical equations and expressions in symbolic form, as opposed to manipulating the approximations of specific numerical quantities represented by those symbols...
with expressions. Here is an example showing the use of local rewriting rules to expand
Polynomial expansion
In mathematics, an expansion of a product of sums expresses it as a sum of products by using the fact that multiplication distributes over addition...
and factor
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplied together give the original...
simple arithmetic expressions:
expand = reduce with
(a+b)*c = a*c+b*c;
a*(b+c) = a*b+a*c;
end;
factor = reduce with
a*c+b*c = (a+b)*c;
a*b+a*c = a*(b+c);
end;
expand ((a+b)*2); // yields a*2+b*2
factor (a*2+b*2); // yields (a+b)*2
Calling C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
functions from Pure is very easy. E.g., the following imports the
puts function from the C library and uses it to print the string "Hello, world!" on the terminal:extern int puts(char*);
hello = puts "Hello, world!";
hello;
See also
- Functional programmingFunctional programmingIn computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
Functional languages
External links
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...