# Mythryl

### From Seo Wiki - Search Engine Optimization and Programming Languages

Paradigm | multi-paradigm: functional, imperative |
---|---|

Appeared in | 2009 |

Designed by | Cynbe ru Taren |

Typing discipline | strong, static, inferred |

Major implementations | Mythryl |

Influenced by | ML |

Website | http://mythryl.org |

**Mythryl** is a general-purpose, modular, functional programming language with compile-time type checking and type inference
supporting both scripting and application development. Mythryl is self-hosting, that is to say the Mythryl compiler is written in Mythryl.

Mythryl is derived from SML/NJ, a compiler and programming environment for Standard ML. It differs in that SML/NJ is a platform-neutral research testbed with an idiosyncratic syntax derived from Robin Milner's work with the logic framework LF, whereas Mythryl is a Linux-centric production-oriented software development platform with a C-flavored syntax.

## Contents |

## Language

Mythryl syntax is easily learned by mainstream programmers. For example the script

#!/usr/bin/mythryl for (i = 0; i < 10; ++i) { printf "%d\n" i; };

does just what a C++ or Java programmer would expect.

Mythryl provides Perl-like scripting convenience in a typed, compiled language. For example the script

#!/usr/bin/mythryl foreach (dir_tree::files ".") .{ if (#file =~ ./\\.[ch]$/) printf "%s\n" #file; fi; };

finds and prints all C files under the current directory. This example illustrates Mythryl's support for Perl-compatible regular expressions via the
standard library `=~`

operator, the compact Mythryl `.{ ... #arg ...}`

syntax for anonymous functions, and also the standard library routines `dir_tree::files`

and `foreach`

.

Unlike (say) Perl, Mythryl does not hardwire into the compiler functionality like
`foreach`

and `=~`

. Mythryl can avoid doing so because
it dynamically compiles scripts into optimized native code, eliminating
the scripting efficiency penalty. This in turn frees users to implement and
use their own variant implementations of regular expressions and such should
they choose.

Mythryl supports a variety of modern constructs such as list comprehensions. For example the expression

[ (i,j,k) for i in 1..20 for j in i..20 for k in j..20 where i*i + j*j == k*k ];

evaluates to the list of Pythagorean triples

[ (3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20) ]

Mythryl provides extensive support for plain and higher order functions. For example, the factorial function may be expressed as

funfactorial( n ) = {if(n == 0) 1;elsen*factorial( n-1 );fi; };

or equivalently but more concisely as

funfactorial( n ) = { (n == 0) ?? 1 :: n*factorial( n-1 ); };

where Mythryl's **cond ?? exp1 :: exp2** syntax corresponds to
C's **cond ? exp1 : exp2** syntax.

The Mythryl compiler infers the static type `Int -> Int` of these functions without user-supplied type annotations. That is, it deduces that *n* is only used with integer expressions, and must therefore itself be an integer, and that all value-producing expressions within the function return integers.

The same function can be expressed with clausal function definitions where the *if*-*then*-*else* conditional is replaced by a sequence of templates of the factorial function evaluated for specific values which are tried one by one in the order written until a match is found:

funfactorial 0 => 1; factorial n => n*factorial( n - 1 );end;

Since Mythryl (unlike SML) supports postfix operators, the mathematically more traditional definition

fun0! => 1; n! => n*(n - 1)! ;end;

may also be used.

### Packages and Generics

Mythryl has an advanced module system, allowing programs to be decomposed into hierarchically organized *packages* of logically related type and value declarations. Mythryl packages provide not only namespace control but also abstraction, in the sense that they allow programmers to define abstract data types.

Three main syntactic constructs comprise the Mythryl package system: API definitions, package definitions and generics. A *package* is a module; it consists of a collection of types, exceptions, values and packages (called *subpackages*) packaged together into a logical unit. An *API* is an interface, usually thought of as a type for a package: it specifies the names of all the entities provided by the package as well as the arities of type components, the types of value components, and APIs for substructures. The definitions of type components may or may not be exported; type components whose definitions are hidden are *abstract types*. Finally, a *generic* is a compile-time function from packages to packages; that is, a generic accepts one or more arguments, which are packages of a given API, and produces a package as its result. Generics are used to implement generic data structures and algorithms.

For example, the API for a queue data structure might be:

apiQueue { Queue(X); # Instances of Queue hold values of any type X (fixed per-queue).exceptionQUEUE; # We may be raising exceptions named QUEUE, with no associated values. empty: Queue(X); # We export an instance of the empty queue to clients. insert: (Queue(X), X) -> Queue(X); # We export a function for inserting X values into an X queue. is_empty: Queue(X) -> Bool; # We export a function for testing whether a queue is empty. peek: Queue(X) -> X; # We export a function for peeking at the next item to be read from queue. remove: Queue(X) -> (Queue(X), X); # Do a pure-functional read, returning value read and new queue. };

This API describes a package that provides a parameterized type `Queue`

of queues, an exception called `QUEUE`

to be raised on attempts to read from an empty queue, an instance of the empty queue for initializing client queue instances, and four functions providing the basic operations on queues. One can now implement the queue interface definition by writing a package with this API:

packagequeue: Queue { Queue(X) = (List(X), List(X)); # We will implement a queue of Xs using two lists of Xs.exceptionQUEUE; empty = ([], []);funinsert ((ins, outs), a) = (a . ins, outs);funis_empty ([], []) = TRUE; is_empty _ = FALSE;end;funpeek ([], []) =>raiseQUEUE; # Cannot peek into an empty queue. peek (ins, []) => head (reverse ins); peek (ins, a . outs) => a;end;funremove ([], []) =>raiseQueue; # Cannot read from an empty queue. remove (ins, []) => { new_outs = reverse ins; (([], taill new_outs), head new_outs); }; remove (ins, a . outs) => ((ins,outs), a); end; };

This definition declares that `queue`

is an implementation of the `Queue`

API.
The body of the package provides all of the components listed in the API declaration.

To use a package, one can access its members using C++ style "package::member" notation.
For example, a queue of strings would have type `queue::Queue(String)`

, the empty queue is `queue::empty`

, and to remove the first element from a queue called `q`

one could write `queue::remove(q)`

.

## Code examples

Snippets of Mythryl code are easily studied by entering them into a top-level read-eval-print loop. This is an interactive session that prints the values of entered expressions:

Linux% my Mythryl 110.58.1 built Fri Feb 29 21:26:24 2009 Do help() for help eval: 1 + 2 * 3; 7

### Hello world

The script

#!/usr/bin/mythryl print "Hello world!\n";

can be executed on Linux like any other script if set executable (`chmod +x hello`

):

$ ./hello Hello world! $

### Quicksort

*Main article:* Quicksort

A one-line implementation of Quicksort demonstrates the conciseness made possible by Mythryl lists, pattern-matching and anonymous functions:

fun qsort [] => []; qsort (x!xs) => qsort (filter .{ #a < x; } xs) @ [x] @ qsort (filter .{ #a >= x; } xs); end;

A more conventional formatting of the function:

fun qsort [] => []; qsort (x ! xs) => qsort (filter .{ #a < x; } xs) @ [x] @ qsort (filter .{ #a >= x; } xs); end;

### Merge Sort

*Main article:* Merge sort

Here we implement Merge Sort as three functions: split, merge and merge_sort.

The split function is implemented with a helper function named split_loop, which has an additional parameter. This function makes use of Mythryl's pattern matching syntax, being defined for both the non-empty ('x . xs') and empty ('[]') list cases.

# Given a list of elements, split it into # two lists of about the same size. # fun split_loop (x1 . x2 . xs, left, right) => split_loop(xs, x2 . right, x1 . left); split_loop ([x], left, right) => (left, x . right); split_loop ([], left, right) => (left, right); end; # fun split(x) = split_loop (x, [], []);

If `split_loop`

is not expected to be used by functions
other than `split`

, it would usually be made local in
order to reduce namespace clutter:

fun split(x) = split_loop (x, [], []) where fun split_loop (x1 . x2 . xs, left, right) => split_loop(xs, x2 . right, x1 . left); split_loop ([x], left, right) => (left, x . right); split_loop ([], left, right) => (left, right); end; end;

If you prefer the reverse ordering,
the **where** clause may be replaced by a **stipulate** clause, yielding the equivalent definition:

stipulate fun split_loop (x1 . x2 . xs, left, right) => split_loop(xs, x2 . right, x1 . left); split_loop ([x], left, right) => (left, x . right); split_loop ([], left, right) => (left, right); end; herein fun split x = split_loop (x, [], []); end;

As with split, merge also uses a helper function merge_loop. Merge_loop is defined in terms of cases: when two non-empty lists are passed, when one non-empty list is passed, and when two empty lists are passed. Note the use of '_' as a wildcard pattern.

This function merges two *ascending* lists into one *descending* because of how lists are constructed in Mythryl. Because Mythryl lists are implemented as imbalanced binary trees, it is efficient to prepend an element to a list, but very inefficient to append an element to a list.

# Given two lists in ascending order, merge them # into a single list in descending order. # # The function lt(a,b) defines the desired # sort order by returning TRUE iff a < b: # fun merge(x,y,lt) = merge_loop([],x,y,lt) where fun merge_loop (out, left as (x . xs), right as (y . ys), lt) = if lt(x, y) merge_loop(x . out, xs, right, lt); else merge_loop(y . out, left, ys, lt); fi; merge_loop (out, x . xs, [], lt) => merge_loop( x . out, xs, [], lt); merge_loop (out, [], y . ys, lt) => merge_loop( y . out, [], ys, lt); merge_loop (out, [], [], _) => out; end; end;

Finally, the merge_sort function itself:

# Sort a list in ascending order # according to lt(a,b) <==> a < b. # # Runs in O(n log n) time and space: # fun merge_sort(empty as [], _) => empty; merge_sort(single as _ . [], _) => single; merge_sort(x, lt) => { my (left, right) = split(x); sl = merge_sort(left, lt); sr = merge_sort(right, lt); s = merge(sl, sr, lt); reverse s; # Final return value. }; end;

Note that the code makes no mention of variable types. This code will sort lists of any type, so long as a consistent ordering function lt can be defined. Using Hindley-Milner type inference, the compiler inferrs the types of all variables, even complicated types such as that of the lt function.

### Numerical derivative (higher-order functions)

It is easy to create and pass around functions in Mythryl programs. This capability has an enormous number of uses. Calculating the numerical derivative of a function is one such application. The following Mythryl function "d" computes the numerical derivative of a given function "f" at a given point "x":

fun d delta f x = (f (x + delta) - f (x - delta)) / (2.0 * delta);

This function requires a small value "delta". A good choice for delta when using this algorithm is the cube root of the machine epsilon.^{[citation needed]}

The function "d" maps a "Float" onto another function with the type "(Float -> Float) -> Float -> Float". This allows us to partially apply arguments. This functional style is known as currying. In this case, it is useful to partially apply the first argument "delta" to "d", to obtain a more specialised function:

d = d 1E~8;

We can compute a numerical approximation to the derivative of x^3-x-1 at x=3 with:

eval: d (fn x = x*x*x - x - 1.0) 3.0; 25.9999996644

The correct answer is f'(x) = 3x^2-1 => f'(3) = 27-1 = 26.

The function "d" is called a higher-order function because it accepts another function ("f") as an argument.

Curried and higher-order functions can be used to eliminate redundant code. For example, a library may require functions of type `A -> B`

, but it is more convenient to write functions of type `(A, C) -> B`

where there is a fixed relationship between the objects of type `A`

and `C`

. A higher order function of type ((A, C) -> B) -> (A -> B) can factor out this commonality. This is an example of the adapter pattern.

### Discrete Wavelet Transform (pattern matching)

The 1D Haar wavelet transform of an integer-power-of-two-length list of numbers can be implemented very succinctly in Mythryl and is an excellent example of the use of pattern matching over lists, taking pairs of elements ("h1" and "h2") off the front and storing their sums and differences on the lists "s" and "d", respectively:

fun haar l = aux l [] [] where fun aux [s] [] d => s . d; aux [] s d => aux s [] d; aux (h1::h2::t) s d => aux t (h1 + h2 . s) (h1 - h2 . d); aux _ _ _ => raise EMPTY; end; end;

For example:

eval: haar [1, 2, 3, 4, ~4, ~3, ~2, ~1]; [0,20,4,4,~1,~1,~1,~1]

Pattern matching is a useful construct that allows complicated transformations to be represented clearly and succinctly. Moreover, the Mythryl compiler turns pattern matches into efficient code, resulting in programs that are not only shorter but also faster.

## External links

## References

This article does not cite any references or sources.Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (August 2009) |