Miranda (programming language)

Last updated
Miranda
Miranda logo (programming language).jpg
Paradigm lazy, functional, declarative
Designed by David Turner
Developer Research Software Ltd
First appeared1985;38 years ago (1985)
Typing discipline strong, static
Website miranda.org.uk
Major implementations
Miranda
Influenced by
KRC, ML, SASL, Hope
Influenced
Clean, Haskell, Orwell, Microsoft Power Fx

Miranda is a lazy, 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) [1] and was the first purely functional language to be commercially supported.[ citation needed ]

Contents

Miranda was first released in 1985 as a fast interpreter in C for Unix-flavour operating systems, with subsequent releases in 1987 and 1989. It had a strong influence on the later Haskell language. [2] Turner stated that the benefits of Miranda over Haskell are: "Smaller language, simpler type system, simpler arithmetic". [3]

In 2020 a version of Miranda was released as open source under a BSD licence. The code has been updated to conform to modern C standards (C11/C18) and to generate 64-bit binaries. This has been tested on operating systems including Debian, Ubuntu, WSL/Ubuntu, and macOS (Catalina). [3] [4]

Overview

Miranda is a lazy, purely functional programming language. That is, it lacks side effects and imperative programming features. A Miranda program (called a script) is a set of equations that define various mathematical functions and algebraic data types. 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, via off-side rule), bracketing statements are rarely needed and statement terminators are unneeded. This feature, inspired by ISWIM, is also used in occam and Haskell and was later popularized by Python.

Commentary 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 script", in which every line is considered a comment unless it starts with a > sign.

Miranda's basic data types are char, num and bool. A character string is simply a list of char, while num is silently converted between two underlying forms: arbitrary-precision integers (a.k.a. bignums) by default, and regular floating point values as required.

Tuples are sequences of elements of potentially mixed types, analogous to records 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 ++, subtraction is --, construction is :, sizing is # and indexing is !, so:

days=week_days++["Sat","Sun"]days="Nil":daysdays!0"Nil"days=days--["Nil"]#days7

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:

facn=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 citizens, which is to say that they can be passed as arguments to other functions, returned as results, or included as elements of data structures. What is more, a function with two or more parameters may be "partially parameterised", or curried, by supplying fewer arguments than the full number of parameters. This gives another function which, given the remaining parameters, will return a result. For example:

addab=a+bincrement=add1

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 with two parameters (operands) 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 declarations. If a function's type is not explicitly declared, the interpreter infers 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)=revx++[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 numbers

subsets[]=[[]]subsets(x:xs)=[[x]++y|y<-ys]++yswhereys=subsetsxs

and this is a literate script for a function primes which gives the list of all prime numbers

> || The infinite list of all prime numbers.  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] 

Here, we have some more examples

max2::num->num->nummax2ab=a,ifa>b=b,otherwisemax3::num->num->num->nummax3abc=max2(max2ab)(max2ac)multiply::num->num->nummultiply0b=0multiplyab=b+(multiply(a-1)b)fak::num->numfak0=1fakn=n*fak(n-1)itemnumber::[*]->numitemnumber[]=0itemnumber(a:x)=1+itemnumberxweekday::=Mo|Tu|We|Th|Fr|Sa|SuisWorkDay::weekday->boolisWorkDaySa=FalseisWorkDaySu=FalseisWorkDayanyday=Truetree*::=E|N(tree*)*(tree*)nodecount::tree*->numnodecountE=0nodecount(Nlwr)=nodecountl+1+nodecountremptycount::tree*->numemptycountE=1emptycount(Nlwr)=emptycountl+emptycountrtreeExample=N(N(NE1E)3(NE4E))5(N(NE6E)8(NE9E))weekdayTree=N(N(NEMoE)Tu(NEWeE))Th(N(NEFrE)Sa(NESu))insert::*->stree*->stree*insertxE=NExEinsertx(NlwE)=Nlwxinsertx(NEwr)=Nxwrinsertx(Nlwr)=insertxl,ifx<w=insertxr,otherwiselist2searchtree::[*]->tree*list2searchtree[]=Elist2searchtree[x]=NExElist2searchtree(x:xs)=insertx(list2searchtreexs)maxel::tree*->*maxelE=error"empty"maxel(NlwE)=wmaxel(Nlwr)=maxelrminel::tree*->*minelE=error"empty"minel(NEwr)=wminel(Nlwr)=minell||Traversing:goingthroughvaluesoftree,puttingtheminlistpreorder,inorder,postorder::tree*->[*]inorderE=[]inorderNlwr=inorderl++[w]++inorderrpreorderE=[]preorderNlwr=[w]++preorderl++preorderrpostorderE=[]postorderNlwr=postorderl++postorderr++[w]height::tree*->numheightE=0height(Nlwr)=1+max2(heightl)(heightr)amount::num->numamountx=x,ifx>=0amountx=x*(-1),otherwiseand::bool->bool->boolandTrueTrue=Trueandxy=False||AAVL-Treeisatreewherethedifferencebetweenthechildnodesisnothigherthan1||istillhavetotestthisisAvl::tree*->boolisAvlE=TrueisAvl(Nlwr)=and(isAvll)(isAvlr),ifamount((nodecountl)-(nodecountr))<2=False,otherwisedelete::*->tree*->tree*deletexE=Edeletex(NExE)=Edeletex(NExr)=NE(minelr)(delete(minelr)r)deletex(Nlxr)=N(delete(maxell)l)(maxell)rdeletex(Nlwr)=N(deletexl)w(deletexr)

Related Research Articles

<span class="mw-page-title-main">AVL tree</span> Self-balancing binary search tree

In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

<span class="mw-page-title-main">Binary search tree</span> Rooted binary tree data structure

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is linear with respect to the height of the tree.

<span class="mw-page-title-main">Binary tree</span> Limited form of tree data structure

In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. That is, it is a k-ary tree with k = 2. A recursive definition using set theory is that a binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set containing the root.

In computer science, a red–black tree is a specialised binary search tree data structure noted for fast storage and retrieval of ordered information, and a guarantee that operations will complete within a known time. Compared to other self-balancing binary search trees, the nodes in a red-black tree hold an extra bit called "color" representing "red" and "black" which is used when re-organising the tree to ensure that it is always approximately balanced.

Standard ML (SML) is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular for writing compilers, for programming language research, and for developing theorem provers.

Curry is a declarative programming language, an implementation of the functional logic programming paradigm, and based on the Haskell language. It merges elements of functional and logic programming, including constraint programming integration.

In programming languages and type theory, parametric polymorphism allows a single piece of code to be given a "generic" type, using variables in place of actual types, and then instantiated with particular types as needed. Parametrically polymorphic functions and data types are sometimes called generic functions and generic datatypes, respectively, and they form the basis of generic programming.

In computer science, a type class is a type system construct that supports ad hoc polymorphism. This is achieved by adding constraints to type variables in parametrically polymorphic types. Such a constraint typically involves a type class T and a type variable a, and means that a can only be instantiated to a type whose members support the overloaded operations associated with T.

<span class="mw-page-title-main">Recursion (computer science)</span> Use of functions that call themselves

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

In computer science, weight-balanced binary trees (WBTs) are a type of self-balancing binary search trees that can be used to implement dynamic sets, dictionaries (maps) and sequences. These trees were introduced by Nievergelt and Reingold in the 1970s as trees of bounded balance, or BB[α] trees. Their more common name is due to Knuth.

C++11 is a version of the ISO/IEC 14882 standard for the C++ programming language. C++11 replaced the prior version of the C++ standard, called C++03, and was later replaced by C++14. The name follows the tradition of naming language versions by the publication year of the specification, though it was formerly named C++0x because it was expected to be published before 2010.

In many programming languages, map is a higher-order function that applies a given function to each element of a collection, e.g. a list or set, returning the results in a collection of the same type. It is often called apply-to-all when considered in functional form.

In functional programming, a generalized algebraic data type is a generalization of parametric algebraic data types.

In functional programming, filter is a higher-order function that processes a data structure in some order to produce a new data structure containing exactly those elements of the original data structure for which a given predicate returns the boolean value true.

<span class="mw-page-title-main">ATS (programming language)</span> Programming language

In computing, ATS is a programming language designed to unify programming with formal specification. ATS has support for combining theorem proving with practical programming through the use of advanced type systems. A past version of The Computer Language Benchmarks Game has demonstrated that the performance of ATS is comparable to that of the C and C++ programming languages. By using theorem proving and strict type checking, the compiler can detect and prove that its implemented functions are not susceptible to bugs such as division by zero, memory leaks, buffer overflow, and other forms of memory corruption by verifying pointer arithmetic and reference counting before the program compiles. Additionally, by using the integrated theorem-proving system of ATS (ATS/LF), the programmer may make use of static constructs that are intertwined with the operative code to prove that a function conforms to its specification.

This article describes the features in the programming language Haskell.

Idris is a purely-functional programming language with dependent types, optional lazy evaluation, and features such as a totality checker. Idris may be used as a proof assistant, but is designed to be a general-purpose programming language similar to Haskell.

In computer science, a WAVL tree or weak AVL tree is a self-balancing binary search tree. WAVL trees are named after AVL trees, another type of balanced search tree, and are closely related both to AVL trees and red–black trees, which all fall into a common framework of rank balanced trees. Like other balanced binary search trees, WAVL trees can handle insertion, deletion, and search operations in time O(log n) per operation.

In computer science, join-based tree algorithms are a class of algorithms for self-balancing binary search trees. This framework aims at designing highly-parallelized algorithms for various balanced binary search trees. The algorithmic framework is based on a single operation join. Under this framework, the join operation captures all balancing criteria of different balancing schemes, and all other functions join have generic implementation across different balancing schemes. The join-based algorithms can be applied to at least four balancing schemes: AVL trees, red–black trees, weight-balanced trees and treaps.

Flix is a functional, imperative, and logic programming language developed at Aarhus University, with funding from the Independent Research Fund Denmark, and by a community of open source contributors. The Flix language supports algebraic data types, pattern matching, parametric polymorphism, currying, higher-order functions, extensible records, channel and process-based concurrency, and tail call elimination. Two notable features of Flix are its type and effect system and its support for first-class Datalog constraints.

References

  1. Turner, D. A. (1985). "Miranda: A non-strict functional language with polymorphic types". In Jouannaud, Jean-Pierre (ed.). Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science. Vol. 201. Berlin, Heidelberg: Springer. pp. 1–16. doi:10.1007/3-540-15975-4_26. ISBN   978-3-540-39677-2.
  2. Hudak, Paul; Hughes, John; Peyton Jones, Simon; Wadler, Philip (2007-06-09). "A history of Haskell: Being lazy with class". Proceedings of the third ACM SIGPLAN conference on History of programming languages. New York, NY, USA: ACM. doi:10.1145/1238844.1238856. ISBN   9781595937667. S2CID   52847907.
  3. 1 2 Turner, David (2021-03-22). "Open Sourcing Miranda". Code Sync. London (published November 2020). Retrieved 2021-12-30.
  4. "Miranda download page". www.cs.kent.ac.uk. Retrieved 2021-12-30.