CS 636 / 338 The Structure of Programming Languages Miranda: A Pure Functional Language

1. In Miranda, A function definition starts with the function name, followed by a list of untyped parameter names, followed by an equal sign and the function's code, indented. Indentation is used (instead of keywords, parentheses, or brackets) to define the scope and structure of the code. In fact, parentheses are used only for grouping in arithmetic expressions. Here is the code for the Greatest Common Divisor algorithm. Note its beautiful simplicity!
   
   

	gcd a b	= gcd (a-b) b,	a > b
		= gcd a (b-a),	a > b
		= a,	a = b

A guarded expression has a series of clauses, where each clause has an action (on the left) and a condition (on the right). The conditions are evaluated in parallel, and exactly one of them should be true. The action corresponding to the true condition is executed. If more than one condition is true, one of the c orresponding actions is selected nondeterministically. Here is a guarded expression used to implement the GCD algorithm.

In Miranda, "where" is used to bind a symbol to a value. (This takes the place of assignment.) Once the binding happens, the value cannot be changed, and remains constant until the symbol goes out-of-scope. Thus, at any given time, a symbol is either unbound, or it is bound to its original value.

In the quadroot function, below, the last four lines define local symbols that are used in the guarded expression above them. Each definition will be evaluated the first time it is needed, and the resulting value will be bound to the symbol for future use. No expression is ever evaluated until its result is needed, and no expression is ever evaluated twice.

	quadroot a b c	= error "complex roots",	delta < 0
		= [term1],	delta = 0
		= [term1+term2, term1-term2],	delta > 0
		where
		delta = b*b - 4*a*c
		term1 = -b/(2*a)
		term2 = radix/(2*a)
		radix = sqrt delta

The primary data structure in Miranda is the list. Lists are ordered and may be treated as whole objects or accessed using subscripts. A literal list is a series of numbers enclosed in square brackets: [4, 8, 12, 16, 20].

In addition, there are list expressions that describe that sequence of values in a list but do not give them literally, or even provide the code to compute them. This powerful notation was originally known as "Zermelo=Frankel" expressions, in honor of the people who invented it. In Miranda, however,these expressions are called list comprehensions. The table below illustrates the kinds of expressions that can be used to denote a list comprehension; after that an EBNF grammer is given for them.

Line (a) in this table should be read as "the list of all values of n, such that n comes from the sequence 1..5".

(a)	[ n | n ← [1..5] ]	Five consecutive integers: [1, 2, 3, 4, 5]
(b)	[ n | n ← [1..] ]	An infinite list--all positive integers
(c)	[ n | n ← [2, 4..10] ]	An arithmetic series: [2, 4, 6, 8, 10]
(d)	[ n+2 | n ← [1..5] ]	[3, 4, 5, 6, 7]
(e)	[ n*2 | n ← [2, 4..10] ]	[4, 8, 12, 16, 20]
(f)	[ n*n | n ← [1, 2 .. ] ]	All perfect squares: 1, 4, 9, etc.
(g)	[ x+y | x ← [1..3]; y ← [3, 7] ]	All combinations of an x plus a y: [4, 5, 6, 8, 9, 10 ]
(h)	[ x*y | x ← [1..3]; y ← [1..3]; x>=y ]	All combinations of an x and a y are generated, but the value pairs are compared before being used to generate a list element. A pair that fails the test is thrown out, a pair that passes is used to compute x*y and the result is put into the answer list: [1, 2, 4, 3, 6, 9]

The syntax for a list comprehension is described by this EBNF grammar. (Note: terminal symbols are quoted, nonterminals are in italics. Other symbols are part of the EBNF formalism.

	ZF expr	::= '[' body '|' qual-list ']'
	qual-list	::= generator { generator | filter }
	generator	::= variable ' ←' list-expression
	filter	::= Boolean-expression
	body	::= list-expression
	list expression	::= literal-list | infinite-list-denotation | arithmetic-series-denotation

Recursion. Miranda functions are polymorphic, that is, they may have multiple definitions, and the definition that is used for a particular function call depends on the type or value of one or more arguments. The pow10 function below illustrates how this is used to define a recursive function. The first line defines a method that for the base case (the argument is 0). The second line defines a recursive method for arguments that are greater than zero. this method also provides a local name, n, for the value that is 1 less than the argument. The third line defines an infinite list based on this function.

	pow10 0	= 1
	pow10 (n+1)	= 10 * powlist ! n
	powlist	= [ pow10(x) | x ← [0..] ]

"Memoizing" a recursive function. An infinite list is part data object (the part of the list that has already been evaluated), and part function (to generate the next item on the list). Using an infinite list to remember function values can increase the efficiency of a recursive function that will be called several times. In the third line, above, we define a "memo" list to store values of the pow10 function after they have been evaluated. A program might use this list by writing powlist ! 5 (subscript 5). If that was previously computed, the answer will be returned immediately. If not, the pow10 function will be called one or more times to compute list values up to slot 5.

Quick? sort. The code below is a Miranda version of quicksort. It splits a list of numbers into two parts, based on a pivot value, recursively sorts each part, then recombines the parts into a sorted list. This is a very slow "quicksort", however, since it traverses the input list twice for each recursive pass.

In the following definition of sort, the first line declares a method that applies only to an empty list (empty brackets). The second line begins a definition for non-empty lists, and provides a pattern to match to the list. This pattern provides local names that can be use to refer to the parts of the list. In this case, the name pivot will be bound to the head of the list (the first item) and the name rest will be bound to the tail of the list (everything except the head). This corresponds to taking the car and the cdr of a list, in LISP, which is an ancestor of Miranda.

	sort [] = []
	sort (pivot:rest) =	sort [ y | y ← rest; b <= pivot ]
		++ [pivot] ++
		sort [ z | z ← rest; b > pivot ]

This sort function follows a pattern typical for a recursive function: it has a base case (for an empty list) and a recursive reduction step that works as follows:

• The first value on the list becomes the quicksort pivot value.
• The rest of the list is scanned once, selecting all values that are less than or equal to the pivot, forming them into a new list, and calling sort recursively to sort this new list.
• The rest of the list is scanned a second time, selecting all values that are greater than the pivot, forming them into a new list, and calling sort recursively to sort this new list.
• The ++ operator concatenates two lists. It is used twice here to form one sorted output list from three partial lists: the result of sorting the first sub-list, a list that contains only the pivot, and the result of sorting the second sub-list.
• The resulting sorted list is returned as the result of the function.

Last updated: 5/8/03