From Seo Wiki - Search Engine Optimization and Programming Languages

Jump to: navigation, search
Paradigm multi-paradigm: functional, imperative
Appeared in 2009
Designed by Cynbe ru Taren
Typing discipline strong, static, inferred
Major implementations Mythryl
Influenced by ML

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.



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

   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


   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

   fun factorial( n ) = {
       if (n == 0)  1;
       else         n*factorial( n-1 );

or equivalently but more concisely as

   fun factorial( 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:

   fun factorial 0 =>  1;
       factorial n =>  n*factorial( n - 1 );

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

   fun 0! =>  1;
       n! =>  n*(n - 1)! ;

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:

api Queue {
    Queue(X);                            # Instances of Queue hold values of any type X (fixed per-queue).
    exception QUEUE;                     # 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:

package queue: Queue {
    Queue(X) = (List(X), List(X));       # We will implement a queue of Xs using two lists of Xs. 
    exception QUEUE;
    empty = ([], []);
    fun insert ((ins, outs), a)
        (a . ins, outs);

    fun is_empty ([], []) = TRUE;
        is_empty _ = FALSE;

    fun peek ([],  [])       =>  raise QUEUE;   # Cannot peek into an empty queue.
        peek (ins, [])       =>  head (reverse ins);
        peek (ins, a . outs) =>  a;

    fun remove ([], [])
            raise Queue;  # 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);

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;

Hello world

The script

  print "Hello world!\n";

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

  $ ./hello
  Hello world!


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);

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);
 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, [], [])
     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);

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

     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);
     fun split x
         split_loop (x, [], []);

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)
     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);
         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;

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 [], _)
     merge_sort(single as _ . [], _)
     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.

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;

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 [] []
          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;

For example:

  eval:   haar [1, 2, 3, 4, ~4, ~3, ~2, ~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


Personal tools

Served in 0.264 secs.