Id (programming language)

From HandWiki

Irvine Dataflow (Id) is a general-purpose parallel programming language, started at the University of California at Irvine in 1975[1] by Arvind and K. P. Gostelow.[2] Arvind continued work with Id at MIT into the 1990s.

The major subset of Id is a purely functional programming language with non-strict semantics. Features include: higher-order functions, a Milner-style statically type-checked polymorphic type system with overloading, user defined types and pattern matching, and prefix and infix operators. It led to the development of pH, a parallel dialect of Haskell.

Id programs are fine grained implicitly parallel.

The MVar synchronisation variable abstraction in Haskell is based on Id's M-structures.[3]

Examples

Id supports algebraic datatypes, similar to ML, Haskell, or Miranda:

type bool = False | True;

Types are inferred by default, but may be annotated with a typeof declaration. Type variables use the syntax *0, *1, etc.

typeof id = *0 -> *0;
def id x = x;

A function which uses an array comprehension to compute the first [math]\displaystyle{ n }[/math] Fibonacci numbers:

typeof fib_array = int -> (array int);
def fib_array n =
  { A = { array (0,n) of
        | [0] = 0
        | [1] = 1
        | [i] = A[i-1] + A[i-2] || i <- 2 to n }
  In A };

Note the use of non-strict evaluation in the recursive definition of the array A.

Id's lenient evaluation strategy allows cyclic datastructures by default. The following code makes a cyclic list, using the cons operator :.

def cycle x = { A = x : A In A };

However, to avoid nonterminating construction of truly infinite structures, explicit delays must be annotated using #:

def count_up_from x = x :# count_up_from (x + 1);

Implementations

pHluid
The pHluid system was a research implementation of Id programming language, with future plans for a front-end for pH, a parallel dialect of the Haskell programming language, implemented at Digital's Cambridge Research Laboratory. and non-profit use. It is targeted at standard Unix workstation hardware.

References

  1. Sharp, J.A. (1992). Data Flow Computing: Theory and Practice. Intellect, Limited. p. 125. ISBN 9780893919214. https://books.google.com/books?id=dS4b3i36qsEC. Retrieved 2014-12-02. 
  2. Arvind; Gostelow, Kim P.; Plouffe, Wil (1978). "The (preliminary) Id report: an asynchronous programming language and computing machine (revised)" (in en). Technical Report TR-114, Department of Information and Computer Science, University of California, Irvine. https://escholarship.org/uc/item/0rr7573w. 
  3. "Concurrent Haskell". Peyton-Jones, Gordon and Finne. POPL 1996.

External links

  • ID Language Reference Manual, Rishiyur S. Nikhil, 1991.
  • "An Asynchronous Programming Language for a Large Multiprocessor Machine", Arvind et al., TR114a, Dept ISC, UC Irvine, Dec 1978