Miranda programming language
Encyclopedia
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. of England (which holds a trademark on the name Miranda) and was the first purely functional language to be commercially supported.
Miranda was first released in 1985, as a fast interpreter in C
for Unix
-flavour operating systems, with subsequent releases in 1987 and 1989. The later Haskell
programming language is similar in many ways to Miranda.
, purely functional
programming language. That is, it lacks side effect
s and imperative programming
features. A Miranda program (called a script) is a set of equation
s that define various mathematical function
s and algebraic data type
s. The word set is important here: the order of the equations is, in general, irrelevant, and there is no need to define an entity prior to its use.
Since the parsing
algorithm makes intelligent use of layout
(indentation), there is rarely a need for bracketing statements and no statement terminators are required. This feature, inspired by ISWIM
is also used in occam
and Haskell
and was later popularized by Python
.
Comment
ary is introduced into regular scripts by the characters
", in which every line is considered a comment unless it starts with a
Miranda's basic data type
s are
integers (a.k.a. bignums) by default, and regular floating point
values as required.
Tuple
s are sequences of elements of potentially mixed types, analogous to record
s in Pascal
-like languages, and are written delimited with parentheses:
this_employee = ("Folland, Mary", 10560, False, 35)
The list instead is the most commonly used data structure in Miranda. It is written delimited by square brackets and with comma-separated elements, all of which must be of the same type:
week_days = ["Mon","Tue","Wed","Thur","Fri"]
List concatenation is
days = week_days ++ ["Sat","Sun"]
days = "Nil":days
days!0
→ "Nil"
days = days -- ["Nil"]
#days
→ 7
There are several list-building shortcuts:
fac n = product [1..n]
odd_sum = sum [1,3..100]
More general and powerful list-building facilities are provided by "list comprehensions" (previously known as "ZF expressions"), which come in two main forms: an expression applied to a series of terms, e.g.:
squares = [ n * n | n <- [1..] ]
(which is read: list of n squared where n is taken from the list of all positive integers) and a series where each term is a function of the previous one, e.g.:
powers_of_2 = [ n | n <- 1, 2*n .. ]
As these two examples imply, Miranda allows for lists with an infinite number of elements, of which the simplest is the list of all positive integers:
The notation for function application is simply juxtaposition, as in
In Miranda, as in most other purely functional languages, functions are first-class
citizens, which is to say that they can be passed as parameter
s to other functions, returned as results, or included as elements of data structures. What is more, a function requiring two or more parameters may be "partially parameterised", or curried
, by supplying less than the full number of parameters. This gives another function which, given the remaining parameters, will return a result. For example:
add a b = a + b
increment = add 1
is a roundabout way of creating a function "increment" which adds one to its argument. In reality,
Any function taking two parameters can be turned into an infix operator (for example, given the definition of the
Thus:
increment = (+) 1
is the briefest way to create a function that adds one to its argument. Similarly, in
half = (/ 2)
reciprocal = (1 /)
two single-parameter functions are generated. The interpreter understands in each case which of the divide operator's two parameters is being supplied, giving functions which respectively divide a number by two and return its reciprocal.
Although Miranda is a strongly typed programming language, it does not insist on explicit type declaration
s. If a function's type is not explicitly declared, the interpreter infer
s it from the type of its parameters and how they are used within the function. In addition to the basic types (
rev [] = []
rev (a:x) = rev x ++ [a]
which can be applied to a list of any data type, for which the explicit function type declaration would be:
rev :: [*] -> [*]
Finally, it has mechanisms for creating and managing program modules whose internal functions are invisible to programs calling those modules.
subsets [] =
subsets (x:xs) = ] ++ y | y <- ys] ++ ys
where ys = subsets xs
and this is a literate script for a function
which gives the list of all prime numbers
> || The infinite list of all prime numbers, by the sieve of Eratosthenes.
The list of potential prime numbers starts as all integers from 2 onwards;
as each prime is returned, all the following numbers that can exactly be
divided by it are filtered out of the list of candidates.
> primes = sieve [2..]
> sieve (p:x) = p : sieve [n | n <- x; n mod p ~= 0]
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...
purely functional
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....
designed by David Turner
David Turner (computer scientist)
Professor David Turner is a British computer scientist.He has a D.Phil. from the University of Oxford. He has held professorships at Queen Mary College, London, University of Texas at Austin and the University of Kent at Canterbury, where he now retains the post of Emeritus Professor.He is...
as a successor to his earlier programming languages SASL
SASL programming language
SASL is a purely functional programming language developed by David Turner at the University of St Andrews in 1972, based on the applicative subset of ISWIM. In 1976 Turner redesigned and reimplemented it as a non-strict language...
and KRC
Kent Recursive Calculator
KRC is a lazy functional language developed by David Turner in 1981 based on SASL, with pattern matching, guards and ZF expressions ....
, using some concepts from ML and Hope. It was produced by Research Software Ltd. of England (which holds a trademark on the name Miranda) and was the first purely functional language to be commercially supported.
Miranda was first released in 1985, as a fast interpreter in 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....
for Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
-flavour operating systems, with subsequent releases in 1987 and 1989. The later Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
programming language is similar in many ways to Miranda.
Overview
Miranda is a lazyLazy 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...
, purely functional
Purely functional
Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications...
programming language. That is, it lacks side effect
Side effect (computer science)
In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...
s and imperative programming
Imperative programming
In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...
features. A Miranda program (called a script) is a set of equation
Equation
An equation is a mathematical statement that asserts the equality of two expressions. In modern notation, this is written by placing the expressions on either side of an equals sign , for examplex + 3 = 5\,asserts that x+3 is equal to 5...
s that define various mathematical function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
s and algebraic data type
Algebraic data type
In computer programming, particularly functional programming and type theory, an algebraic data type is a datatype each of whose values is data from other datatypes wrapped in one of the constructors of the datatype. Any wrapped datum is an argument to the constructor...
s. The word set is important here: the order of the equations is, in general, irrelevant, and there is no need to define an entity prior to its use.
Since the parsing
Parsing
In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...
algorithm makes intelligent use of layout
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...
(indentation), there is rarely a need for bracketing statements and no statement terminators are required. This feature, inspired by ISWIM
ISWIM
ISWIM is an abstract computer programming language devised by Peter J. Landin and first described in his article, The Next 700 Programming Languages, published in the Communications of the ACM in 1966...
is also used in occam
Occam (programming language)
occam is a concurrent programming language that builds on the Communicating Sequential Processes process algebra, and shares many of its features. It is named after William of Ockham of Occam's Razor fame....
and Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
and was later popularized by Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
.
Comment
Comment (computer programming)
In computer programming, a comment is a programming language construct used to embed programmer-readable annotations in the source code of a computer program. Those annotations are potentially significant to programmers but typically ignorable to compilers and interpreters. Comments are usually...
ary is introduced into regular scripts by the characters
|| and continue to the end of the same line. An alternative commenting convention affects an entire source code file, known as a "literate scriptLiterate programming
Literate programming is an approach to programming introduced by Donald Knuth as an alternative to the structured programming paradigm of the 1970s....
", in which every line is considered a comment unless it starts with a
> sign.Miranda's basic data type
Data type
In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
s are
char, num and bool. A character string is simply a list of char, while num is silently converted between two underlying forms: arbitrary-precisionArbitrary-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...
integers (a.k.a. bignums) by default, and regular floating point
Floating point
In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent. The base for the scaling is normally 2, 10 or 16...
values as required.
Tuple
Tuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
s are sequences of elements of potentially mixed types, analogous to record
Record (computer science)
In computer science, a record is an instance of a product of primitive data types called a tuple. In C it is the compound data in a struct. Records are among the simplest data structures. A record is a value that contains other values, typically in fixed number and sequence and typically indexed...
s in Pascal
Pascal (programming language)
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
-like languages, and are written delimited with parentheses:
this_employee = ("Folland, Mary", 10560, False, 35)
The list instead is the most commonly used data structure in Miranda. It is written delimited by square brackets and with comma-separated elements, all of which must be of the same type:
week_days = ["Mon","Tue","Wed","Thur","Fri"]
List concatenation is
++, subtraction is --, construction is :, sizing is # and indexing is !, so:days = week_days ++ ["Sat","Sun"]
days = "Nil":days
days!0
→ "Nil"
days = days -- ["Nil"]
#days
→ 7
There are several list-building shortcuts:
.. is used for lists whose elements form an arithmetic series, with the possibility for specifying an increment other than 1:fac n = product [1..n]
odd_sum = sum [1,3..100]
More general and powerful list-building facilities are provided by "list comprehensions" (previously known as "ZF expressions"), which come in two main forms: an expression applied to a series of terms, e.g.:
squares = [ n * n | n <- [1..] ]
(which is read: list of n squared where n is taken from the list of all positive integers) and a series where each term is a function of the previous one, e.g.:
powers_of_2 = [ n | n <- 1, 2*n .. ]
As these two examples imply, Miranda allows for lists with an infinite number of elements, of which the simplest is the list of all positive integers:
[1..]The notation for function application is simply juxtaposition, as in
sin x.In Miranda, as in most other purely functional languages, functions are first-class
First-class function
In computer science, a programming language is said to have first-class functions if it treats functions as first-class objects. Specifically, this means that the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning...
citizens, which is to say that they can be passed as parameter
Parameter (computer science)
In computer programming, a parameter is a special kind of variable, used in a subroutine to refer to one of the pieces of data provided as input to the subroutine. These pieces of data are called arguments...
s to other functions, returned as results, or included as elements of data structures. What is more, a function requiring two or more parameters may be "partially parameterised", or curried
Currying
In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument...
, by supplying less than the full number of parameters. This gives another function which, given the remaining parameters, will return a result. For example:
add a b = a + b
increment = add 1
is a roundabout way of creating a function "increment" which adds one to its argument. In reality,
add 4 7 takes the two-parameter function add, applies it to 4 obtaining a single-parameter function that adds four to its argument, then applies that to 7.Any function taking two parameters can be turned into an infix operator (for example, given the definition of the
add function above, the term $add is in every way equivalent to the + operator) and every infix operator taking two parameters can be turned into a corresponding function.Thus:
increment = (+) 1
is the briefest way to create a function that adds one to its argument. Similarly, in
half = (/ 2)
reciprocal = (1 /)
two single-parameter functions are generated. The interpreter understands in each case which of the divide operator's two parameters is being supplied, giving functions which respectively divide a number by two and return its reciprocal.
Although Miranda is a strongly typed programming language, it does not insist on explicit type declaration
Declaration (computer science)
In programming languages, a declaration specifies the identifier, type, and other aspects of language elements such as variables and functions. It is used to announce the existence of the element to the compiler; this is important in many strongly-typed languages that require variables and their...
s. If a function's type is not explicitly declared, the interpreter infer
Type inference
Type inference refers to the automatic deduction of the type of an expression in a programming language. If some, but not all, type annotations are already present it is referred to as type reconstruction....
s it from the type of its parameters and how they are used within the function. In addition to the basic types (
char, num, bool), it includes an "anything" type where the type of a parameter does not matter, as in the list-reversing function:rev [] = []
rev (a:x) = rev x ++ [a]
which can be applied to a list of any data type, for which the explicit function type declaration would be:
rev :: [*] -> [*]
Finally, it has mechanisms for creating and managing program modules whose internal functions are invisible to programs calling those modules.
Sample code
The following Miranda script determines the set of all subsets of a set of numberssubsets (x:xs) = ] ++ y | y <- ys] ++ ys
where ys = subsets xs
and this is a literate script for a function
primeswhich gives the list of all prime numbers
> || The infinite list of all prime numbers, by the sieve of Eratosthenes.
The list of potential prime numbers starts as all integers from 2 onwards;
as each prime is returned, all the following numbers that can exactly be
divided by it are filtered out of the list of candidates.
> primes = sieve [2..]
> sieve (p:x) = p : sieve [n | n <- x; n mod p ~= 0]