Similar functional languages

Similar functional languages

There are several languages similar to Objective CAML, whether through the functional aspect, or through typing. Objective CAML is descended from the ML family, and thus it has cousins of which the closest are across the Atlantic and across the channel in the lineage of SML (Standard ML). The Lisp family, and in particular the Scheme language, differs from ML mainly by its dynamic typing. Two lazy languages, Miranda and Haskell, take up or extend ML's typing in the framework of delayed evaluation. Two functional languages, Erlang and SCOL, developed by the Ericsson and Cryo-Networks corporations respectively, are directed towards communication.

ML family

The ML family comprises two main branches: Caml (Categorical Abstract Machine Language) and its derivatives Caml-Light and Objective CAML, SML (Standard ML) and its descendants SML/NJ and mosml. Caml, the ancestor, was developed between 1986 and 1990 by INRIA's FORMEL project in collaboration with University Paris 7 and the École Normale Supérieure. Its implementation was based on Le_Lisp's runtime. It integrated within the language the definition of grammars and pretty-printers, which allowed communication of values between the language described and Caml. Its type system was more restrictive for mutable values, insofar as it did not allow such values to be polymorphic. Its first descendant, Caml-Light, no longer used the CAM machine, but instead used Zinc for its implementation. The name was nevertheless retained to show its ancestry. It contributed a more lightweight implementation while optimizing the allocation of closures and using an optimizing GC as a precursor to the actual GC. This streamlining allowed it to be used on the PC's of the time. The various Caml-Light versions evolved towards actual typing of imperative features and were enriched with numerous libraries. The following offshoot, Caml Special Light or CSL, introduced parameterized modules and a native-code compiler. Finally the baby is actually Objective CAML which mainly adds the object-oriented extension to CSL. Since there has never been a complete specification of the Caml languages, these various changes have been able to take place in complete freedom.

The SML approach has been the opposite. The formal specification [MTH97] was given before the first implementation. It is difficult to read, and a second book gives a commentary ([MT91]) on it. This method, specification then implementation, has allowed the development of several implementations, of which the best-known is SML/NJ (Standard ML of New Jersey) from Lucent (ex-AT&T). Since its origin, SML has integrated parameterized modules. Its initial type system was different from that of Caml for imperative features, introducing a level of weakness for type variables. The differences between the two languages are detailed in [CKL96]. These differences are being effaced with time. The two families have the same type system for the functional and imperative core, Objective CAML now has parameterized modules. SML has also undergone changes, bringing it closer to Objective CAML, such as for record types. If the two languages don't merge, this mainly derives from their separate development. It is to be noted that there is a commercial development environment for SML, MLWorks, from Harlequin:

Link

http://www.harlequin.com/products/

An SML implementation, mosml, based on Caml-Light's runtime, has also been implemented.

Scheme

The Scheme language (1975) is a dialect of the Lisp language (1960). It has been standardized (IEEE Std 1178-1990). It is a functional language with strict evaluation, equipped with imperative features, dynamically typed. Its syntax is regular and particular about the use of parentheses. The principal data structure is the dotted pair (equivalent to an ML pair) with which possibly heterogeneous lists are constructed. The main loop of a Scheme toplevel is written (print (eval (read))). The read function reads standard input and constructs a Scheme expression. The eval function evaluates the constructed expression and the print function prints the result. Scheme has a very useful macro-expansion system which, in association with the eval function, permits the easy construction of language extensions. It not only supports interrupting computation (exceptions) but also resuming computation thanks to continuations. A continuation corresponds to a point of computation. The special form call_cc launches a computation with the possibility of resuming this one at the level of the current continuation, that is to say of returning to this computation. There are many Scheme implementations. It is even used as a macro language for the GIMP image manipulation software. Scheme is an excellent experimental laboratory for the implementation of new sequential or parallel programming concepts (thanks to continuations).

Languages with delayed evaluation

In contrast with ML or Lisp, languages with delayed evaluation do not compute the parameters of function calls when they are passed, but when evaluation of the body of the function requires it. There is a ``lazy'' version of ML called Lazy ML but the main representatives of this language family are Miranda and Haskell.

Miranda

Miranda([Tur85]) is a pure functional language. That is to say, without side effects. A Miranda program is a sequence of equations defining functions and data structures.

Link

http://www.engin.umd.umich.edu/CIS/course.des/cis400/miranda/miranda.html

For example the fib function is defined in this way:

 
 fib a = 1, a=0 
       = 1, a=1 
       = fib(a-1) + fib(a-2), a>1

Equations are chosen either through guards (conditional expressions) as above, or by pattern-matching as in the example below:

fib 0 = 1
fib 1 = 1
fib a = fib(a-1)+ fib(a-2)

These two methods can be mixed.

Functions are higher order and can be partially evaluated. Evaluation is lazy, no subexpression is computed until the moment when its value becomes necessary. Thus, Miranda lists are naturally streams.

Miranda has a concise syntax for infinite structures (lists, sets): [1..] represents the list of all the natural numbers. The list of values of the Fibonacci function is written briefly: fibs = [a | (a,b) <- (1,1),(b,a+b)..]. Since values are only computed when used, the declaration of fibs costs nothing.

Miranda is strongly typed, using a Hindley-Milner type system. Its type discipline is essentially the same as ML's. It accepts the definition of data by the user.

Miranda is the archetype of pure lazy functional languages.

Haskell

The main Haskell language website contains reports of the definition of the language and its libraries, as well as its main implementations.

Link

http://www.haskell.org

Several books are dedicated to functional programming in Haskell, one of the most recent is [Tho99].

This is a language which incorporates almost all of the new concepts of functional languages. It is pure (without side effects), lazy (not strict), equipped with an ad hoc polymorphism (for overloading) as well as parametric polymorphism à la ML.

Ad hoc polymorphism

This system is different from the polymorphism seen up to now. In ML a polymorphic function disregards its polymorphic arguments. The treatment is identical for all types. In Haskell it is the opposite. A polymorphic function may have a different behavior according to the type of its polymorphic arguments. This allows function overloading.

The basic idea is to define type classes which group together sets of overloaded functions. A class declaration defines a new class and the operations which it permits. A (class) instance declaration indicates that a certain type is an instance of some class. It includes the definition of the overloaded operations of this class for this type.

For example the Num class has the following declaration:

class Num a where
  (+)    :: a -> a -> a
  negate :: a -> a

Now an instance Int of the class Num can be declared in this way:

instance Num Int where
  x + y    =  addInt x y
  negate x = negateInt x

And the instance Float:

instance Num Float where
  x + y    =  addFloat x y
  negate x = negateFloat x

The application of negate Num will have a different behavior if the argument is an instance of Int or Float.

The other advantage of classes derives from inheritance between classes. The descendant class recovers the functions declared by its ancestor. Its instances can modify their behavior.

Other characteristics

The other characteristics of the Haskell language are mainly the following:

a purely functional I/O system using monads;
arrays are built lazily;
views permit different representations of a single data type.

In fact it contains just about all the high-strung features born of research in the functional language domain. This is its advantage and its disadvantage.

Communication languages

ERLANG

ERLANG is a dynamically typed functional language for concurrent programming. It was developed by the Ericsson corporation in the context of telecommunications applications. It is now open source. The main site for accessing the language is the following:

Link

http://www.erlang.org

It was conceived so that the creation of processes and their communication might be easy. Communications take place by message passing and they can be submitted with delays. It is easy to define protocols via ports. Each process possesses its own definition dictionary. Error management uses an exception mechanism and signals can propagate among processes. Numerous telephony applications have been developed in Erlang, yielding non-negligible savings of development time.

SCOL

The SCOL language is a communication language for constructing 3D worlds. It was developed by the Cryo Networks corporation:

Link

http://www.cryo-networks.com

Its core is close to that of Caml: it is functional, statically typed, parametrically polymorphic with type inference. It is ``multimedia'' thanks to its API's for sound, 2D, and 3D. The 3D engine is very efficient. SCOL's originality comes from communication between virtual machines by means of channels. A channel is an (environment, network link) pair. The link is a (TCP or UDP) socket.

SCOL's originality lies in having resolved simply the problem of securing downloaded code: only the text of programs circulates on the network. The receiving machine types the passed program, then executes it, guaranteeing that the code produced does indeed come from an official compiler. To implement such a solution, without sacrificing speed of transmission and reception, the choice of a statically typed functional language was imposed by the conciseness of source code which it supports.