Id Reference Manual
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 60
| Download | |
| Open PDF In Browser | View PDF |
ID
Language Reference Manual
Version 90.1
Rishiyur S. Nikhil
Computation Structures Group Memo 284-2
July 15, 1991
Copyright c 1991 Laboratory for Computer Science,
Massachusetts Institute of Technology
This report describes research done at the Laboratory for Computer Science of the Massachusetts Institute of Technology. Funding for the Laboratory is provided in part by the
Advanced Research Projects Agency of the Department of Defense under the Oce of
Naval Research contract N00014-89-J-1988.
Id
Language Reference Manual
(Version 90.1)
Rishiyur S. Nikhily
July 15, 1991
Computation Structures Group
Laboratory for Computer Science
Massachusetts Institute of Technology
545 Technology Square,
Cambridge, MA 02139, USA
Abstract
Id is a general-purpose parallel programming language designed by members of the Computation Structures Group in MIT's Laboratory for Computer Science, and is used for
programming data ow and other parallel machines.
The major subset of Id (syntactically distinguishable) is a pure functional language with
non-strict semantics. Features include: higher-order functions, a Milner-style statically
type-checked polymorphic type system with overloading, user de ned types and patternmatching notation, lists and list comprehensions, arrays and array comprehensions, and
facilities for delayed evaluation.
The non-functional aspects of Id include I-structures and M-structures (for both arrays
and user-de ned types), and input/output. With respect to the functional subset, programs with I-structures remain deterministic but may not be referentially transparent, and
programs with M-structures and i/o may even be non-deterministic.
Id programs are implicitly parallel to a very ne grain. Some programs with M-structures
and i/o may need explicity sequencing, for which facilities are provided.
y
Inquiries about Id may be directed by mail to Prof. Arvind at the above address, by email
to id@lcs.mit.edu, or to the author. Author's current address: Digital Equipment Corporation,
Cambridge Research Laboratory, One Kendall Square, Bldg 700, Cambridge MA 02139, USA; Email:
nikhil@crl.dec.com; Telephone: (617) 621 6639. This work was done while the author was at MIT.
CONTENTS
i
Contents
1 Introduction
1
2 Functional Id
1
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12
2.13
2.14
2.15
2.16
2.17
2.18
2.19
2.20
2.21
2.22
2.23
2.24
2.25
2.26
2.27
Expressions, Statements and Types : : :
Programs : : : : : : : : : : : : : : : : :
Parentheses and Grouping : : : : : : : :
Semicolons : : : : : : : : : : : : : : : :
Comments : : : : : : : : : : : : : : : : :
Identi ers : : : : : : : : : : : : : : : : :
2.6.1 Reserved Words : : : : : : : : :
2.6.2 Standard Identi ers : : : : : : :
Types : : : : : : : : : : : : : : : : : : :
2.7.1 Precedence in Type Expressions
2.7.2 Polymorphic Types : : : : : : : :
Overloading : : : : : : : : : : : : : : : :
Type synonyms: typesyn : : : : : : : :
Type Declarations: typeof : : : : : : :
Algebraic Types : : : : : : : : : : : : :
Function Applications : : : : : : : : : :
Pre x and In x Operators : : : : : : : :
Operator Precedence : : : : : : : : : : :
Voids : : : : : : : : : : : : : : : : : : : :
Booleans : : : : : : : : : : : : : : : : : :
Integers : : : : : : : : : : : : : : : : : :
Floats : : : : : : : : : : : : : : : : : : :
Characters : : : : : : : : : : : : : : : : :
Strings : : : : : : : : : : : : : : : : : : :
Symbols : : : : : : : : : : : : : : : : : :
Tuples : : : : : : : : : : : : : : : : : : :
Records : : : : : : : : : : : : : : : : : :
2.23.1 Record type de nition : : : : : :
2.23.2 Record construction : : : : : : :
2.23.3 Record eld selection : : : : : : :
Conditional Expressions : : : : : : : : :
Blocks : : : : : : : : : : : : : : : : : : :
Simple Binding Statements : : : : : : :
Patterns : : : : : : : : : : : : : : : : : :
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
2.28
2.29
2.30
2.31
2.32
2.33
Pattern-Matching : : : : : : : : : :
Case-expressions : : : : : : : : : :
Function Abstractions : : : : : : :
Function De nitions : : : : : : : :
Pattern-Binding Statements : : : :
Lists : : : : : : : : : : : : : : : : :
2.33.1 Binary In x List Operators
2.33.2 Arithmetic Series Operators
2.33.3 List Comprehensions : : : :
Arrays : : : : : : : : : : : : : : : :
2.34.1 Array Types : : : : : : : :
2.34.2 Array literals : : : : : : : :
2.34.3 Array Selection : : : : : : :
2.34.4 Array Index Bounds : : : :
2.34.5 Array Comprehensions : : :
Accumulators : : : : : : : : : : : :
Abstract Types : : : : : : : : : : :
Loops : : : : : : : : : : : : : : : :
2.37.1 Scope of Variables in Loops
2.37.2 Loop semantics : : : : : : :
Errors : : : : : : : : : : : : : : : :
: : : :
: : : :
: : : :
: : : :
11
11
12
12
13
13
13
13
13
14
14
14
15
15
15
16
17
17
18
18
19
: : : :
1
: : : :
1
: : : :
2
: : : :
2
: : : :
2
2.34
: : : :
2
: : : :
2
: : : :
2
: : : :
3
: : : :
3
: : : :
3
2.35
: : : :
4
2.36
: : : :
4
2.37
: : : :
5
: : : :
5
: : : :
6
2.38
: : : :
6
6
3 General issues concerning non-functional
7
constructs (I-structures and M-structures) 20
7
3.1 I-structure and M-structure semantics : : 20
7
3.2 Polymorphism of I-structures and Mstructures : : : : : : : : : : : : : : : : : : 21
7
3.3 Referential Transparency, Sharing and Ob8
ject Identity : : : : : : : : : : : : : : : : : 21
8
3.4 What gets evaluated, and when : : : : : : 21
8
3.5 Determinacy : : : : : : : : : : : : : : : : 22
9
3.6 Side-e ect statements : : : : : : : : : : : 23
9
3.7 Sequencing Statements: barriers : : : : : 23
9
3.8 Sequencing expressions : : : : : : : : : : : 25
9
10 4 I-structures
25
10
4.1 I-structure semantics : : : : : : : : : : : : 25
10
4.2 I-structure arrays : : : : : : : : : : : : : : 25
10
4.2.1 I-array types : : : : : : : : : : : : 25
11
4.2.2 I-array creation : : : : : : : : : : : 26
ii
CONTENTS
4.2.3 I-array assignments : : : : : : : :
4.2.4 I-array selection : : : : : : : : :
4.2.5 I-array index bounds : : : : : : :
4.3 I-structure elds in Algebraic Types : :
4.3.1 Type de nition : : : : : : : : : :
4.3.2 Object creation : : : : : : : : : :
4.3.3 Component assignment : : : : :
4.3.4 Component selection : : : : : : :
4.3.5 Component selection in patterns
4.3.6 Example: iterative map : : : : : :
4.4 I-structure elds in records : : : : : : :
4.4.1 Type de nition : : : : : : : : : :
4.4.2 Record creation : : : : : : : : : :
4.4.3 Field assignment : : : : : : : : :
4.4.4 Field selection : : : : : : : : : :
5 M-structures
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
5.1 M-structure semantics : : : : : : : : : : :
5.2 M-structure arrays : : : : : : : : : : : : :
5.2.1 M-array types : : : : : : : : : : : :
5.2.2 M-array literals and comprehensions
5.2.3 M-array creation : : : : : : : : : :
5.2.4 M-array assignment : : : : : : : :
5.2.5 M-array selection : : : : : : : : : :
5.2.6 M-array index bounds : : : : : : :
5.3 M-structure elds in Algebraic Types : : :
5.3.1 Type de nition : : : : : : : : : : :
5.3.2 Object creation : : : : : : : : : : :
5.3.3 Component assignment : : : : : :
5.3.4 Component selection : : : : : : : :
5.3.5 Component selection in patterns :
5.3.6 Example: unique id generator : : :
5.3.7 Example: FIFO queue : : : : : : :
5.4 M-structure elds in records : : : : : : : :
5.4.1 Type de nition : : : : : : : : : : :
5.4.2 Record creation : : : : : : : : : : :
5.4.3 Field assignment : : : : : : : : : :
5.4.4 Field selection : : : : : : : : : : :
33
26 6 Delayed evaluation
6.1 General Delayed Evaluation : : : : : : : : 33
26
6.2 Delayed Evaluation For Data Structure
26
Components : : : : : : : : : : : : : : : : : 33
27
6.2.1 Delayed components in algebraic
types : : : : : : : : : : : : : : : : : 34
27
6.2.2 Delayed components in records : : 34
27
6.2.3 Delayed components in functional
27
arrays : : : : : : : : : : : : : : : : 34
27
6.2.4 Delayed components in I-structure
arrays : : : : : : : : : : : : : : : : 35
27
27 7 Pragmatics
35
28
7.1 Inline substitution : : : : : : : : : : : : : 35
28
7.2 Bounded loops : : : : : : : : : : : : : : : 35
7.3 Pragmas : : : : : : : : : : : : : : : : : : : 36
28
7.4 Loop peeling and unrolling : : : : : : : : 36
28
7.4.1 Loop peeling : : : : : : : : : : : : 36
28
7.4.2 Loop Unrolling : : : : : : : : : : : 37
28
A Standard Identi ers
28
A.1 Booleans : : : : : : : : : : : : : : : : : : :
29
A.2 Numbers : : : : : : : : : : : : : : : : : : :
29
A.3 Characters : : : : : : : : : : : : : : : : : :
A.4 Strings : : : : : : : : : : : : : : : : : : : :
29
A.5 Symbols : : : : : : : : : : : : : : : : : : :
29
A.6 Lists : : : : : : : : : : : : : : : : : : : : :
29
A.7 Lists as Sets : : : : : : : : : : : : : : : : :
30
A.8 Arrays : : : : : : : : : : : : : : : : : : : :
30
A.9 I-structure arrays : : : : : : : : : : : : : :
30
A.10 M-structure arrays : : : : : : : : : : : : :
30
A.11 Object identity : : : : : : : : : : : : : : :
30
A.12 Delayed Evaluation : : : : : : : : : : : : :
A.13 Input/Output : : : : : : : : : : : : : : : :
31
A.14 Storage Management : : : : : : : : : : : :
31
31 B List of overloaded operators and identi ers
31
B.1 Overloaded operators : : : : : : : : : : : :
B.2 Overloaded identi ers : : : : : : : : : : :
32
B.3 Overloaded array notations : : : : : : : :
32
32 C Incompatible Changes
32
C.1 Changes from Id 90.0 to Id 90.1 : : : : : :
32
C.2 Changes from Id 88.x to Id 90.0 : : : : : :
C.3 Changes from Id Noveau to Id 88.x : : : :
33
39
39
39
40
40
41
41
43
43
45
45
45
45
45
48
49
49
49
51
51
51
52
53
2. Introduction/Functional Id
1
1 Introduction
2 Functional Id
Id is a parallel programming language designed by
members of the Computation Structures Group of
MIT/LCS. It is used for programming data ow and
other parallel machines.
Id is a language with three layers. The major subset of Id is a purely functional language; this subset
is described rst, in Section 2. The second layer
extends this with I-structures which are described
in Section 4. The third layer extends this with Mstructures which are described in Section 5. Some
general aspects of these non-functional extensions
are described in Section 3.
Id traces its roots back to 1978 [1]. Since then,
versions of Id have run on simulated data ow machines, and more recently on real data ow hardware
and Unix workstations. Id/83s [4] was a rst cut at
a major redesign of the language, based on contemporary ideas in functional languages. It brie y acquired the name Id Nouveau (1986) [6, 2], and then
reverted to Id in 1988 [3].
Id continues to be a research language. Current
investigations include better constructs to express
non-deterministic computations, I/O, resourcemanagement etc.
This document is not a tutorial on Id. For a tutorial introduction, the reader is referred to [5].
Appendix C lists the incompatibilities between
this version of Id and previous versions.
This section describes the purely functional (and referentially transparent) subset of Id.
Acknowledgements
Many people|past and current members of the
Computation Structures Group, and colleagues
elsewhere|have participated in the design of Id.
Major contributors include: Shail Aditya, Arvind,
Paul Barth, David Culler, Kattamuri Ekanadham,
Steve Heller, James Hicks, Vinod Kathail, Rishiyur
Nikhil, Keshav Pingali, Ken Traub, and Jonathan
Young.
Id is also heavily in uenced by various functional
languages in the ISWIM-ML-SASL family.
2.1 Expressions, Statements and Types
Two major syntactic categories in Id are expressions
and statements .
Every expression denotes a value . In this manual, we use the generic symbols \e", \e1", etc. to
designate arbitrary expressions.
Statements appear in the top-level of programs, in
blocks, etc. Statements are usually identi er bindings and declarations of new types.
Id has a polymorphic type system. Every expression and statement must \type-check", i.e., satisfy
certain type-rules; these are explained as each construct is introduced. Types are described by typeexpressions . In this manual, we use the generic symbols \t", \t0", etc. to refer to types.
Type-checking in Id is done by type inference ,
i.e., in general the programmer is not required to
declare the types of identi ers or expressions|the
type-checker automatically deduces them from the
context. However, for readability, for better errormessages and to assist in overloading resolution,
there is a facility for declaring types of identi ers
(using typeof statements, see Section 2.10).
For explaining the type rules in this manual, we
use the notation:
e
:: t
which is pronounced \e has type t", i.e., the value
of expression \e" lies in the set of values denoted
by type \t". This notation is only a device for this
manual; it is not part of the language.
2.2 Programs
A program is a collection of statements:
STATEMENT ;
...
STATEMENT ;
The statements collectively de ne an environment
in which top-level expressions may be evaluated.
The statements, together with a top-level expression,
have the semantics of a block (see Section 2.25).
2
2. Functional Id
2.3 Parentheses and Grouping
token is read as an identi er only if it is not in one
of these categories.
Any expression or type-expression may be enclosed Upper- and lower-case letters are equivalent in
in parentheses. This may be done to override prece- identi
ers.
dence, or merely for visual clarity.
( 2 + 3 ) * ( 4 - (f x))
(btree (btree N))
2.6.1 Reserved Words
Parentheses are also used for \quoting" binary in x The following words are reserved and may not be
operators (see Section 2.13), for denoting the void used as identi ers:
value (see Section 2.15), and for grouping statements
(see Section 3.7.)
abstype
rep
for
2.4 Semicolons
Semicolons may be used either as a separator between statements, or as a terminator at the end of a
statement.
2.5 Comments
Comments begin with \%" and can contain any text
up to the end-of-line:
accumulate
and
array
bound
by
case
def
defsubst
do
downto
downfrom
else
finally
fun
if
in
instance
instances
matrix
M array
M matrix
M vector
next
of
or
record
seq
sequential
then
to
type
typeof
typesyn
unbounded
unless
upfrom
vector
when
while
In addition, the following families of words are reserved:
We recommend the guidelines on page 348 of the
Common Lisp manual (Guy L. Steele, Jr., Digital
D arrays
D M arrays
Press, 1984) for commenting code, except that Id has
vectors
M vectors
\%" instead of Lisp's \;" as the comment character.
arrays
M arrays
% anything goes till the end of the line
k n
k n
k
k
k
k
matrices
nD array
nD
k
2.6 Identi ers
k
M matrices
M array
Identi ers may contain alphabetics, digits, under- for each 1 and 1.
scores ( ), question marks (?), single quotes (') and Upper- and lower-case letters are equivalent in retildes (~) in any order. Examples:
served words.
k
x
x'
harry
desmond_2_2
2D_array
nil?
done?
The lexical syntax for identi ers overlaps with the
lexical syntax for reserved words (Sections 2.6.1),
numbers (Sections 2.17 and 2.18), character constants (Section 2.19) and the special underscore token \ " (Sections 2.27, 4.3.3 and 5.3.3). A lexical
n
2.6.2 Standard Identi ers
Standard identi ers are not reserved words|they
can be rede ned by the programmer, and the set
of standard identi ers will continue to grow as more
and more useful library functions are identi ed and
implemented. To enhance readability and reusability of code, the programmer is strongly advised not
to rede ne them. See Appendix A for a listing of
standard identi ers.
2. Functional Id
3
2.7 Types
Function Types:
In this manual, we use the generic symbols \t", \t1",
etc. to designate arbitrary type expressions.
Types are denoted by type-expressions , which are
either Type Variables :
*3
*0
*13
or N -ary Constructed Types (N 0):
type-constructor t1 ... tN
A type constructor is an identi er (e.g., bool, list,
tree) or one of the array reserved words (e.g., array,
vector, matrix, nD array, nD M array).
The identi ers used for type constructors may overlap with identi ers used for values. Since type expressions occur only in speci c contexts, there is
no ambiguity. For example, there is a type called
float, and there is also a standard identi er float
representing the function that converts integers into
oating-point numbers.
t0 -> t1
The \->" type operator associates to the right,
so that the parentheses can be omitted in the
following type-expression:
int -> (int -> bool)
Additional pre-de ned constructed types are listed
in Sections 4, 5, 6 and A.13.
2.7.1 Precedence in Type Expressions
Type application binds tighter than \->", which
binds tighter than comma. In each of the following
examples, the parentheses may be dropped:
(btree int) -> int
(list int),int
(int -> int),int
2.7.2 Polymorphic Types
A type containing a type variable is a polymorSome pre-de ned 0-ary constructed types (also phic type, e.g., the type of \:", the list constructor,
called Type Constants ):
is:
void
or C
bool
or B
int
or I
float
or F
string or S
symbol or SYM
The types in each row are synonyms.
Some pre-de ned constructed types:
char
Array Types:
1D array t
2D array t
3D array t
...
list t
The type variable stands for \any type", indicating
that \:" can construct lists of any type. However,
all occurrences of a type variable in a polymorphic
type must be instantiated uniformly . For example,
all these are valid instantiations of the type of the
list constructor:
int -> (list int) -> (list int)
for building lists of integers, or:
bool -> (list bool) -> (list bool)
vector t
matrix t
array t
The types in each row are synonyms.
List Types:
*0 -> (list *0) -> (list *0)
for building lists of booleans, or:
(int->bool)
->
(list (int->bool)) -> (list (int->bool))
for building lists of integer-to-boolean functions.
However, the following is not a valid instantiation:
char -> (list bool) -> (list int)
since the type variable *0 is instantiated nonCertain pre-de ned constructed types also have spe- uniformly to char, bool and int, respectively.
cial syntax:
While this may seem restrictive compared to, say,
Lisp, in fact it is not, because disjoint union types
Tuple Types:
(Section 2.11) give a way of packaging di erent types
t0 , ..., tN
into a common type in a type-safe manner.
4
2. Functional Id
2.8 Overloading
The type of each non-overloaded instance of x is only
allowed to be an instance of the type t. For examThere are many operators and identi ers that are ple:
not polymorphic, but overloaded. A polymorphic overload plus = *0 -> *0 -> *0 ;
function is a single function that works on an in nity of types (each possible instantiation of its type Non-overloaded instances of an identi er x may be
variables). An occurrence of an overloaded identi- declared using the statement:
er, on the other hand, is a syntactic shorthand for instance x = x~a, x~b, ... ;
one of a small set of identi ers that have di erent The reserved word instances is a synonym for
types; which one it actually stands for depends on instance. Here, x must already be known as an overthe context in which it is used|this resolution is loaded identi er (i.e., previously declared using an
performed automatically by type checking.
overload x = t declaration). The types of x~a, x~b,
...
must be known, and must each be an instance of
For example, the operator symbol \+" represents
the
overloaded type t.
one of the following functions:
There may be multiple instance declarations for
plus~int
:: int -> int -> int
the
same overloaded identi er. Example:
plus~float :: float -> float -> float
The identi er length represents one of the following instances plus = plus~int, plus~float;
or
functions
length~string :: string -> int
length~list
:: (list *0) -> int
For each use of an overloaded operator or identi er,
the type-checker will attempt to infer the particular
type at which it is used from the surrounding context, so that the particular function it represents is
known. If it is unable to do so, an error is agged. In
this situation, the programmer must assist the type
checker either by replacing the overloaded identi er
by the intended non-overloaded one, or by using an
explicit type declaration (Section 2.10) to make the
type unambiguous.
We use the following syntactic convention to relate
an overloaded identi er to the corresponding nonoverloaded identi ers. An overloaded identi er foo
represents one of the identi ers:
foo~type1
foo~type2
...
instance plus = plus~int ;
...
instance plus = plus~float ;
All instances of an overloaded identi er should have
mutually exclusive types, i.e., for each pair of instances x~a and x~b, their types should not be uni able.
Polymorphism of overloaded identi ers
Some overloaded identi ers represent polymorphic
functions. For example, length represents:
length~string :: string
-> int
length~list
:: (list *0) -> int
and the latter function is polymorphic. However, a
particular occurrence of length cannot be used polymorphically. Thus, the following program will not
type-check:
{ f = length
In
(f integer_list),(f bool_list) }
Appendix B lists many overloaded operators and
identi ers, and their corresponding non-overloaded
even though it would type-check if we use
identi ers.
length~list instead. Two occurrences of length can,
of course, be used at di erent types.
User-de ned overloading
The user may declare that an identi er
loaded by using the statement:
overload x = t ;
x
is over-
2.9 Type synonyms:
typesyn
A new type constructor may be declared as a synonym for an existing type. The statement:
2. Functional Id
5
Here, tcons is an identi er and represents a new Ladic
( 0) Constructor . Each tJ is a type-expression
declares tx to be a new type. The tvJ's are optional constraining
the type of the J 'th argument of the
type variables (N 0). Examples:
constructor. Thus,
typesyn tx tv1 ... tvN = t ;
typesyn
typesyn
typesyn
typesyn
S
complex
code_mem
eq_func *0
=
=
=
=
string ;
(float,float) ;
array (op,src,dests) ;
*0 -> *0 -> bool ;
tcons :: t1 -> ... -> tL -> (tx tv1 ... tvN)
The type variables in the right-hand side (all disjuncts), if any, must be a subset of the type variables
The type variables in the right-hand side, if any, mentioned in the left-hand side.
must be a subset of the type variables mentioned Implicitly de ned with each L-adic constructor are
in the left-hand side.
also L eld selectors tcons 1, ..., tcons L. Assuming
we have an expression e that evaluates to
2.10 Type Declarations:
typeof
v
:: tx tv1 ... tvN
An identi er's type may be declared anywhere in its then the \dot-notation" expression:
e.tcons_J
scope. The statement:
checks that v is indeed of the form:
typeof x = t ;
asserts that identi er x denotes a value of type t. tcons v1 ... vL
Example:
i.e., checks that it is in the expected disjunct, and
then
returns vJ. If v is a di erent disjunct, a runtypeof map~list = (*0 -> *1) ->
time error occurs, producing the error value ? (see
(list *0) -> (list *1);
Since Id's type-checker automatically infers the Section 2.38).
types of all identi ers, user-speci ed type dec- Implicitly de ned with each constructor tcons is
larations are not generally necessary. However, also a predicate function:
we strongly recommend their plentiful use be- tcons? :: (tx tv1 ... tvN) -> bool
cause:
that tests whether a value of that type is in that
They make programs more readable;
disjunct.
Error messages from the type-checker will be
more localized, and hence more helpful.
Examples
Type declarations are sometimes necessary to assist
the type-checker in resolving overloaded identi ers. Lists of integers:
Note: a type declaration statement does not in- type ilist = Inil | Icons int ilist;
Implicitly de ned constructors:
troduce any new identi ers or types.
2.11 Algebraic Types
Algebraic types are also called \disjoint union"
types. New algebraic types are de ned by the statement:
Inil
Icons
:: ilist
:: int -> ilist -> ilist
Implicitly de ned eld selectors:
ICons_1
ICons_2
:: ilist . int
:: ilist . ilist
both of which produce the error value ? if e evaluates
to INil (see Section 2.38).
Here, tx is the name for the new type. Its optional Implicitly de nied predicates:
N ( 0) type parameters are speci ed by the type- Inil? :: ilist -> bool
variables tvJ. Its M ( 1) disjuncts are speci ed by Icons? :: ilist -> bool
the disjJs, each of which has the form:
tcons t1 ... tL
Polymorphic lists:
type tx tv1 ... tvN = disj1 | ... | disjM;
6
2. Functional Id
type list *0 = Nil | Cons *0 (list *0);
Implicitly de ned constructors:
Nil
Cons
:: (list *0)
:: *0 -> (list *0) -> (list *0)
denotes the application of a function (the value of
) to an argument (the value of ex).
ef
Application associates to the left. Thus, the following two expressions are equivalent:
Implicitly de ned eld selectors:
e1 e2 e3 ... eN
Cons_1
Cons_2
(((e1 e2) e3) ... eN)
:: (list *0) . *0
:: (list *0) . (list *0)
both of which produce the error value ? if e evaluates
to Nil (see Section 2.38).
Implicitly de ned predicates:
Nil?
Cons?
:: (list *0) -> bool
:: (list *0) -> bool
Polymorphic binary trees:
2.13 Pre x and In x Operators
Some functions are designated by special symbols
called operators . Unary pre x operator expressions
are written:
type btree *0 = Empty_btree
| Bnode *0
(btree *0)
(btree *0) ;
op e
Implicitly de ned constructors:
e1 op e2
Empty_btree :: (btree *0)
Bnode
:: *0 ->
(btree *0) ->
(btree *0) -> (btree *0)
Implicitly de ned eld selectors:
Bnode_1
Bnode_2
Bnode_3
:: (btree *0) . *0
:: (btree *0) . (btree *0)
:: (btree *0) . (btree *0)
Binary in x operator expressions are written:
All binary operators can be treated as ordinary identi ers by enclosing them in parentheses, e.g.,
(+) e1 e2
foldr_list (+) 0 list_of_N
This is one of the two special uses of parentheses in
Id, where they are not used for grouping (the other
is the notation for the void value, Section 2.15).
all of which produce the error value ? if e evaluates The unary pre x operator \-" cannot be similarly
to Empty tree (see Section 2.38).
treated as an ordinary identi er by enclosing it in
parentheses,
because \(-)" stands for the value of
Implicitly de ned predicates:
the binary version. For example, if the programmer
Empty_btree?
:: (btree *0) -> bool
needs a unary integer minus function, this can be
Bnode?
:: (btree *0) -> bool
obtained by partially applying the binary function
to the constant \0":
2.12 Function Applications
((-) 0)
Every function has type \t0 -> t1" for some argu- When applied to some x, this becomes \0-x", which
ment type \t0" and result type \t1".
is equivalent to \-x".
Assuming:
ef :: (t0 -> t1)
ex :: t0
then the application expression:
ef ex :: t1
2.14 Operator Precedence
In decreasing precedence:
2. Functional Id
operator
array and eld selection
application
(unary)
associates
Left
Left
Right
^
Right
* /
Left
+ Left
to downto by
:
Right
++
Right
== <> < <= > >=
Left
and
Left
or
Left
,
(comma in tuples) -
2.15 Voids
There is a special constant \()" whose type is void.
There are no other values of this type. It is typically
used in two situations: as an argument for a procedure that does not otherwise have a meaningful
argument, and as a result of a procedure that does
not otherwise have a meaningful result.
Although there is nothing non-functional about
this by itself, it is useful mainly in non-functional
programs (Sections 3, 4 and 5).
This is the second special use of parentheses,
where they are not used for grouping (the rst special use was to \quote" in x operators, Section 2.13).
2.16 Booleans
Booleans are de ned as follows:
type
bool = False | True ;
typesyn B
= bool ;
with implicitly de ned predicates:
False?
True?
:: bool -> bool
:: bool -> bool
7
The following operators are overloaded for
booleans:
==
<>
See Appendix A.1 for standard boolean functions,
including \not", the boolean negation function.
2.17 Integers
Integer numbers have type int (synonym: \I").
Integer constants are written as sequences of digits:
255 :: int
The following operators are overloaded for integers:
- (unary negation)
+
==
-
*
<>
<=
>
>=
Integers may also be used in patterns.
See Appendix A.2 for standard integer functions,
including integer division.
2.18 Floats
Floating point numbers have type float (synonym:
\F").
Floating point constants are written with decimal
points and/or exponents:
0.6667 :: float
1.45
:: float
2.56e4 :: float
3e-3
The radix and exponent are always based on 10.
The decimal point must be preceded or followed by
at least one digit. The \e" must be preceded by a
number and followed by a (possibly signed) integer.
Example: 2.56e4 denotes 2:56 104
The following operators are overloaded for oating
point numbers:
- (unary negation)
+
-
*
<=
Thus, False and True are identi ers representing
boolean constants, and are also constructors (i.e., Division:
they can be used in patterns).
/ :: float -> float
In x operators:
Exponentiation:
==
and :: bool -> bool -> bool
or :: bool -> bool -> bool
<
<>
<
>
>=
-> float
^ :: float -> int -> float
See Appendix A.2 for standard oating point funcBoth left and right arguments are always evaluated. tions.
8
2. Functional Id
2.19 Characters
of the C programming language.
All characters have type char (synonym: \C"). The String constants are written between doublenotation for character constants follows the conven- quotation marks:
tions of the C programming language.
"Hiya"
:: string
"Cab
for
hire"
::
string
Most character constants are written as the char"Wanna take you higher" :: string
acter enclosed in single quotes:
To represent the double quote character, the back'a'
:: char
'?'
:: char
slash character and certain other characters within
'M'
:: char
strings, the same escape sequences as for character
...
constants are available, with the following restricTo represent the single quote character itself, the tion: octal escapes must have exactly three octal
backslash character and certain other characters, the digits, and hex escapes must have exactly two hexfollowing escape sequences may be used:
adecimal digits.
'\n'
:: char newline
Upper- and lower-case are distinguished in string
'\t'
:: char horizontal tab
constants, except for hexadecimal digits in escape
'\v'
:: char vertical tab
sequences.
'\b'
:: char backspace
Example: a string containing a newline.
'\r'
:: char carriage return
'\f'
:: char form feed
"Some like it hot,\nSome like it cold."
'\a'
:: char audible alert
The following operators are overloaded for strings:
'\\'
:: char backslash
==
<>
<=
<
>
>=
'\?'
:: char question mark
'\''
:: char single quote
The ordering uses lexicographic ordering on the char'\"'
:: char double quote
acters in the string.
'\
'
:: char octal code
Strings are zero-indexed (i.e., the rst character
'\x
' :: char hex code
The last two forms are used for specifying octal or is at position 0).
hexadecimal codes for characters. Octal character The string type is di erent from lists or arrays of
codes may be 1, 2 or 3 octal digit sequences. Hex characters for reasons of eciency.
character codes may contain any number of hexadecEven though we use C notation for string conimal digits ( 1).
stants,
strings in Id are not zero-terminated as in
Upper- and lower-case are distinguished in charac- C.
ter constants, except for hexadecimal digits in escape
sequences.
See Appendix A.4 for standard string functions,
including
functions to nd the length of a string and
The following operators are overloaded for characto
convert
to and from lists and arrays.
ters:
ooo
h::h
==
<>
<=
<
>
>=
The obvious lexicographic ordering is guaranteed 2.21 Symbols
only within the following classes: digit characters,
upper case characters, and lower case characters.
All symbols have type symbol (synonym: \SYM"). A
See Appendix A.3 for standard character func- symbol is written as a backslash followed by an identions.
ti er:
2.20 Strings
All strings have type string (synonym: \S"). The
notation for string constants follows the conventions
\A
\x'
\desmond_2_2
\c3po
\7am
::
::
::
::
::
symbol
symbol
symbol
symbol
symbol
2. Functional Id
9
The following operators are overloaded for symbols:
==
<>
Unlike Lisp, symbols are are not related to program
identi ers. Each distinct symbol merely represents
a unique global constant (unique across all Id programs).
See Appendix A.5 for standard symbol functions,
including conversion to and from strings.
2.22 Tuples
An N -tuple has type \(t1,...,tN)" where \tj" is
the type of the j 'th component.
Assuming:
e1
...
eN
:: t1
:: tN
then the tuple expression:
e1, ..., eN
:: t1,...,tN
denotes an n-tuple value (where N 2|there is no
notation for 1-tuples).
The comma has lower precedence than all other
operators. Examples:
4+5, true
:: int,bool
5, (sqr x, false) :: int,(int,bool)
(5,4),"Hi",(a > b) :: (int,int),string,bool
The type variables in the right-hand side, if any,
must be a subset of the type variables mentioned in
the left-hand side.
Fieldnames have the same syntax as program identi ers. However eldnames and identi ers are drawn
from di erent namespaces, i.e., there can be an identi er called x and a eldname called x with no confusion, since they always appear in disjoint regions
of the program text.
The same eldname may not be used in more than
one record type (however, this restriction is likely to
be removed in the future).
Examples:
type person = {record
pname = string ;
age
= int } ;
type complex = {record x = float;
y = float } ;
type node *0 = {record
nname
= int ;
info
= *0 ;
children = list (node *0)};
2.23.2 Record construction
A record is constructed using a record expresThe second expression is a 2-tuple whose second sion:
component is itself a 2-tuple. The nesting structure {record fieldname1 = e1;
is signi cant|it is not equivalent to a 3-tuple.
... ;
fieldnameM
= eM}
Components of a tuple are accessed via patternmatching (see Section 2.28).
The order in which the elds are speci ed does not
have to follow the order of the elds in the record
type de nition. All elds must be speci ed (This is
2.23 Records
2.23.1 Record type de nition
true only in the functional subset of the language; see Sections
4.4.2 and 5.4.2, where we allow I-structure and M-structure
elds to be omitted).
Records are like tuples with named elds. A new
Examples:
record type is de ned using the statement:
type tx tv1 ... tvN =
{record fieldname1 = t1;
...
fieldnameM = tM};
Here, tx is the new type, and the tvJ's are optional
type variables (N 0). The fieldnameJ's are identi ers representing eld names.
{record pname = "Z.Z.Gabor";
age = 16 }
:: person
{record y = 2.3; x = 4.5 }
{record nname = 2345;
info = 6.001;
children = Nil }
:: complex
:: node float
10
2. Functional Id
2.25 Blocks
2.23.3 Record eld selection
Record elds may be selected using explicit eld se- The block expression:
lection:
{ STATEMENT ;
...
STATEMENT
record_expression . fieldname
Examples:
In
e }
p.pname
c.x
n.children
2.24 Conditional Expressions
Assuming:
e1
:: bool
e2
:: t
e3
:: t
then
if e1 then e2 else e3
:: t
is a conditional expression. The predicate e1 is evaluated, and depending on its truth or falsity, either
e2 or e3 (but not both) is evaluated, and returned
as the value of the entire expression.
The conditional expression is equivalent to the following case expression (see Section 2.29):
{case e1 of
True = e2
| False = e3}
In a conditional expression, the phrase \else
may be omitted:
if e1 then e2
:: void
"
e3
denotes the value of e evaluated in the environment
inside the block.
Semicolons may be used as statement separators
or as statement terminators, i.e., the last statement
before \In" is optionally followed by a semicolon.
Each statement must be well-typed. Statements
usually specify bindings associating identi ers to
types or values. The type of the block expression
is the type of e.
Blocks (like all Id constructs) follow a static scoping discipline. The name-environment inside a block
is the surrounding environment augmented by the
names introduced by the statements of the block. A
name X may be introduced at most once in a block,
and hides any X in the surrounding environment.
Names introduced inside a block are invisible outside the block.
Thus, the statements in a block may be recursive
and mutually recursive, and the textual order of the
statements is not signi cant.
The phrase \In e" may be omitted:
{ STATEMENT ;
...
STATEMENT } :: void
This is syntactic shorthand for:
This is syntactic shorthand for:
if e1 then e2 else ()
{ STATEMENT ;
...
STATEMENT
In
() }
Although there is nothing non-functional about this
by itself, it is useful mainly in non-functional programs (Sections 3, 4 and 5).
In parsing, an else matches the nearest preceding Although there is nothing non-functional about this
by itself, it is useful mainly in non-functional prounbalanced then.
grams (Sections 3, 4 and 5).
Precedence of then and else: binds less tightly
even than commas|the parentheses may be omitted
in each of these examples:
2.26 Simple Binding Statements
if ... else (x,y)
if ... then (f x y)
if ... else (x and y)
The statement:
x = e ;
2. Functional Id
11
introduces x as a name for the value of expression e An identi er pattern x successfully matches any
into the current scope. We also say that x is bound value.
to the value of e.
A constant pattern c successfully matches only the
corresponding value c.
2.27 Patterns
A constructor term pattern
c pat1 ... patN
A pattern is one of the following:
successfully matches only a value of the form
an identi er,
c v1 ... vN
an underscore \ " (don't care)
a special constant (void, integer, character, sym- provided also that each patJ matches the correbol),
sponding eld vJ.
a constructor pattern:
c pat1 ... patN
where c is an N -ary constructor name of some
algebraic type t, and the patJ's are themselves
patterns (N 0). The pattern itself is said to
be of type t.
All normal identi ers in a pattern must be unique
(technically, this is called left linearity). The \don'tcare" pattern \ " may be repeated.
Special syntax: list patterns can be written with
an in x colon:
Assuming the pattern matches successfully, the following environment is produced:
A \don't-care" pattern \ " produces no binding.
An identi er pattern x binds x to the value.
A constant pattern c produces no binding.
A constructor term pattern:
pat1:pat2
c pat1 ... patN
Binding
Special syntax: N -tuple patterns can be written when matched to a value:
with commas:
c v1 ... vN
pat1,...,patN
2.28 Pattern-Matching
produces the union of all the bindings obtained by
matching all the patJ's to their corresponding vJ's.
Pattern-matching a pattern to a value has two dis- 2.29 Case-expressions
tinct aspects:
Assuming:
Matching , i.e., testing whether the value is a data e :: te
structure that conforms to the shape speci ed by e1 :: t
the pattern. If so, the match is said to succeed, ...
otherwise it is said to fail.
eN :: t
Binding , i.e., producing an environment in which
identi ers in the pattern are bound to corre- and pat1 ... patN are patterns of type te, then the
sponding components of the value. Binding only case-expression:
{case e of
occurs if the match succeeds.
Matching:
Matching succeeds under the following conditions.
A \don't-care" pattern \ " successfully matches any
value.
|
|
pat1 = e1
...
patN = eN } :: t
behaves as follows. All the patterns pat1 ... patN
are matched to the value of e, in no speci c order.
No more than one match should succeed. If patJ
succeeds, then the resulting bindings augment the
12
2. Functional Id
current environment, eJ is evaluated in that envi- 2.30 Function Abstractions
ronment, and its value is returned as the value of
the whole expression. Note that all eJ's must have A function abstraction expression (a form of lambthe same type t, and the entire case-expression has da-expression) is written:
type t.
{fun pat11 ... pat1N = e1
The patterns must be disjoint, i.e., at most | pat21 ... pat2N = e2
...
one pattern can successfully match any e; this is
|
patM1 ... patMN = eM
checked by the compiler. The pattern-matching is
\parallel"| there is no speci ed top-to-bottom or |.. patL1 ... patLN = eL }
left-to-right order in the pattern-matching. (For spe- and is equivalent to:
cialists: disjoint patterns may require non-sequential
x1 ... xN =
functions for non-strict evaluation; in Id, these be- {fun{case
(x1,...,xN) of
come strict so that the order of patterns is not sig(pat11,...,pat1N) =
ni cant).
|
(pat21,...,pat2N) =
The last clause may be preceded by \.." to designate it as a catch-all clause (this is a limited form
of ordering):
e1
e2
...
|
(patM1,...,patMN) = eM
|.. (patL1,...,patLN) = eL }}
and represents an \anonymous" function of arity
N ( 1) whose formal parameters are the xJs and
whose body is the case-expression. As usual, static
scoping rules are followed.
The nal \catch-all" clause (signalled by \..") is
Here, a match of patF to v (the value of e) is at- optional.
tempted only if all other matches fail. Thus, patF
need not be disjoint from the other patterns.
{case e of
pat1 = e1
|
...
|
patN = eN
|.. patF = eF }
2.31 Function De nitions
The patterns need not be exhaustive|if no pattern matches, a runtime error occurs, and the case- A function de nition statement is written:
expression has the error value ? (see Section 2.38).
This behavior can be understood as follows. A case def f pat11 ... pat1N = e1
expression without a default clause is equivalent to | f...pat21 ... pat2N = e2
one with a default clause added:
|
f patM1 ... patMN = eM
{case e of
pat1 = e1
|
...
|
patN = eN
|..
_ = error "Pattern match"}
(see Section 2.38 for the error function). A case
expression with a default clause is equivalent to one
with the default clause rewritten as follows:
{case e of
pat1 = e1
|
...
|
patN = eN
|..
x = {case x of
patF = eF
|..
_ = error "Pattern match"}}
|.. f patL1 ... patLN = eL
and is equivalent to the simple binding statement:
f = {fun x1 ... xN =
{case (x1,...,xN) of
(pat11,...,pat1N)
|
(pat21,...,pat2N)
|
...
|
(patM1,...,patMN)
|.. (patL1,...,patLN)
= e1
= e2
= eM
= eL }}
The nal \catch-all" clause (signalled by \..") is
optional.
See also Section 7.1 for defsubst, a version of def
that also suggests that it is inlinable for eciency.
2. Functional Id
2.32 Pattern-Binding Statements
A convenient way to access components of a data
structure is to use a pattern-binding statement:
pat = e ;
13
using the usual parenthesized notation for quoting
in x operators. Also, the pattern:
Cons pat1 pat2
can be written
The pattern is matched against the value of e, and pat1 : pat2
if it succeeds, the corresponding bindings are introduced into the current scope.
2.33.1 Binary In x List Operators
If the match fails, a runtime error occurs|
the statement is equivalent to the error statement Appending two lists:
statement? (see Section 2.38), and some or all of the ++ :: (list *0) -> (list *0) -> (list *0)
bindings may not be performed.
Example:
2.33.2 Arithmetic Series Operators
(x,y:ys) = e ;
The expression e should evaluate to a 2-tuple whose
second component is a non-empty list. The statement binds x to the rst component of the tuple, y
to the head of the list and ys to the tail of the list. If
the second component of the 2-tuple is an empty list,
the pattern-match fails; in this case, the statement
is equivalent to the error statement statement? (see
Section 2.38), y and ys remain unbound, and it is unspeci ed whether x is bound to the rst component
of the tuple or remains unbound.
2.33 Lists
The standard list type is de ned as:
type list *0 = Nil | Cons *0 (list *0);
with implicitly de ned eld selectors:
Cons_1
Cons_2
:: (list *0).*0
:: (list *0).(list *0)
and implicitly de ned predicates:
Nil?
Cons?
:: (list *0) -> bool
:: (list *0) -> bool
Special syntax: constructor terms of the form:
Cons e1 e2
may be written with the in x \:" operator:
Assuming:
e1
:: int
e2
:: int
eInc
evaluate to integers v 1, v 2 and vInc, respectively,
then the expressions:
e1 to e2 by eInc
e1 downto e2 by eInc
:: (list int)
:: (list int)
produce lists containing (v 1, v 1 + vInc, v 1 + 2vInc,
..., v 2), and (v 1, v 1 ? vInc, v 1 ? 2vInc, ..., v 2),
respectively.
Note: vInc must always be positive.
The short forms:
e1 to e2
:: (list int)
e1 downto e2 :: (list int)
assume that vInc is +1.
Precedence of to, downto and by: the parentheses
may be omitted in each of these examples:
...
...
...
...
to (f x)
downto (f x)
to (e1 + e2)
by (f x)
See also Section 6.2.1 for arithmetic series of in nite
length.
e1:e2
2.33.3 List Comprehensions
and the higher-order function:
A list-comprehension is written:
Cons
{: e || gen1 ; ... ; genN }
may be written as:
(:)
:: int
(N 1). Each generator gen is written in one of two
ways:
14
2. Functional Id
pat <- eList FILTER1 ... FILTERm
pat = eVal FILTER1 ... FILTERm
(m 0). Each
ways:
FILTER
is written in one of two
where e::t in the environment speci ed by the generators.
Examples
when
epw
unless epu
A list of x-y coordinates in the rst octant of a 100square:
Individual generator behavior
{: x,y || x <- 0 to 100 ; y <- 0 to x }
In the rst form (using <-), eList must be a list of
values; pat is matched to each element of the list,
generating a sequence of environments that bind the
pattern variables. If pattern-matching fails, a runtime error occurs| the failing match of the pattern
to a list element is replaced by the error statement
statement? (see Section 2.38).
In the second form (using =), pat is matched to the
value of eVal, generating an environment that binds
the pattern variables. If pattern-matching fails, a
runtime error occurs| the failing match of the pattern to a list element is replaced by the error statement statement? (see Section 2.38).
The environments are then ltered, i.e., those environments in which an epw evaluates false or an epu
evaluates true are discarded. The lters are tried
in sequence from left to right, i.e., if a lter rejects
an environment, the subsequent lter expressions are
not evaluated for that environment.
Generator sequence behavior
The generators are evaluated from left to right. For
each environment Env in the sequence of environments produced before genJ,
genJ is evaluated in Env, and produces a set of
environments EnvJ 1, EnvJ 2 , ...
Env is replaced in the sequence by the augmented environments Env + EnvJ 1 , Env +
EnvJ 2 , ...
Thus, the net result of the generator sequence is a
sequence of environments containing bindings for the
pattern variables of all the generators.
List-comprehension behavior
A list of x-y coordinates in a 100-square that are not
on the axes or on the diagonals:
{: x,y || x <- 0 to 100 when x <> 0
; y <- 0 to 100 when y <> 0
unless x == y }
See Appendix A.6 for standard list functions.
2.34 Arrays
Arrays are collections of uniformly-typed objects,
with a constant access-time for each component.
2.34.1 Array Types
An n-dimensional array (n 1) whose components
have type t has type:
nD_array t
Arrays can contain objects of any type, including
other arrays.
Nested arrays are not equivalent to multidimensional arrays. The following two types are not
equivalent:
2D_array t
1D_array (1D_array t)
Synonyms for 1D array:
vector
array
Synonym for 2D array:
matrix
The expression e is evaluated in each environment
produced by the generator sequence, and the values 2.34.2 Array literals
are collected into a list (in the same order), which is
the result of the whole expression.
Assuming a bounds expression (an n-tuple of integer
2-tuples):
Type of list comprehension
The type of the list comprehension is (list t), eBounds :: (int,int), ... ,(int,int)
2. Functional Id
which evaluates to (l1,u1),...,(ln,un), an array
with those index bounds can be constructed by enumerating its contents:
{nD_array eBounds of
eFirst ... eLast}
The expressions specify the contents in \row-major"
order, i.e., starting from index l1,l2,...,ln and
ending at index u1,...,un, stepping the right-most
index fastest. The number of contents-expressions
must be equal to the number of components in the
array.
Note that if a component is speci ed by an application \f a", it will have to be parenthesized to
prevent it from being mistaken as two separate component speci cations.
It is legal for the index bounds (l; u) along any
dimension to be empty, i.e., to have u = l ? 1 (zero
components).
2.34.3 Array Selection
Assuming:
a
e
:: nD_array t
:: int,...,int
then the array-selection expression:
a[e]
:: t
returns the value of the j1,...,jn'th component
of the array \a", where j1,...,jn is the value of
\e". The index j1,...,jn must be within the indexbounds of the array|it is a runtime error otherwise,
producing the error value ? (see Section 2.38).
Note that the index expression can be any expression that returns an n-tuple of integers, i.e., it does
not have to be a literal tuple-expression.
Precedence of array selection: tighter even than
application, so that parentheses are not necessary
in:
f (a[e])
2.34.4 Array Index Bounds
15
bounds~1D_array ::
(1D_array *0) -> (int,int)
bounds~2D_array ::
(2D_array *0) -> ((int,int),(int,int))
...
The overloaded identi er bounds represents all these
functions.
2.34.5 Array Comprehensions
Array comprehensions are used to construct arrays,
allowing the programmer to specify the contents of
di erent regions of the array using di erent computation rules.
For each k 1 and n 1, assuming a bounds
expression (an n-tuple of integer 2-tuples):
eBounds :: (int,int), ... ,(int,int)
and a set of index expressions (each an n-tuple of
integers):
eJ1 :: int,...,int
and a set of component expressions (each a ktuple):
eJ2 :: t1,...,tk
then the array comprehension expression:
{k_nD_arrays eBounds of
[e11] = e12 || gen ; ... ; gen
| ...
| [eM1] = eM2 || gen ; ... ; gen }
returns a k-tuple of n-dimensional arrays. Each gen
is a generator, possibly including lters (exactly as
in list-comprehensions).
Array comprehension behavior
is evaluated to produce lower- and upperbounds for each of n dimensions. k arrays with
these dimensions are created. Then, the subsequent
clauses are all executed in parallel to ll the arrays.
(The top-to-bottom order of the clauses has no signi cance.)
eBounds
Clause behavior
See Generator behavior and Generator sequence behavior in Section 2.33.3 on list comprehensions to
see how each generator sequence
gen ; ... ; gen
produces a sequence of environments. Now, in each
For each n 1, there is a function that returns the such environment, eJ1 is evaluated to produce an inindex bounds of n-dimensional arrays:
dex into the arrays (an n-tuple), and eJ2 is evaluated
16
2. Functional Id
to produce a k-tuple specifying the contents of that An array containing the inverse of a given permulocation in each of the k arrays.
tation in array A:
Type of array comprehensions
The type of the value of the array comprehension
is
nD_array t1, ..., nD_array tk
{array (1,N) of
[A[i]] = i || i <- 1 to N }
See also Appendix A.8 for standard array functions.
where t1,...,tk is the type of each eJ2 in each environment speci ed by the J 'th generator sequence. 2.35 Accumulators
A runtime error occurs if the contents of an array at some index is de ned more than once, i.e., Accumulators are an extension of arrays.
if the array comprehension speci es values twice at {k1_n1D_arrays eBounds1 of
the same index j1,...,jN. This is a drastic error|
[ei] = evs || gen ; ... ; gen
the entire program is considered to be inconsistent | ...
| [ei] = evs || gen ; ... ; gen
(see Section 2.38).
k2_n2D_arrays eBounds2 of
If, at some index, the array comprehension speci[ei] = evs || gen ; ... ; gen
es no value at all, then that location simply remains | ...
unde ned (indistinguishable from a non-terminating | [ei] = evs || gen ; ... ; gen
.
computation).
The generator sequences \|| gen ; ... ; gen" ..
are optional. In this case, eJ1 and eJ2 specify the kM_nMD_arrays eBoundsM of
contents of a single location.
[ei] = evs || gen ; ... ; gen
| ...
The k nD arrays keywords have synonyms for | [ei] = evs || gen ; ... ; gen
some common cases:
accumulate k_ops of
k=1
k1
n = 1 array k arrays
[eis] = evs || gen ; ... ; gen
n=2
n1
vector
k vectors
matrix
k matrices
| ...
| [eis] = evs || gen ; ... ; gen }
nD array
This returns a tuple containing k arrays (k = k1 +
It is legal for the index bounds (l; u) along any k2 + ::: + kM ). The rst k1 arrays have bounds
dimension to be empty, i.e., to have u = l ? 1 (zero eBounds1 and are initialized according to the rst set
of clauses, the next k2 arrays have bounds eBounds2
components).
and are initialized according to the second set of
clauses, and so on.
Examples
After the keyword accumulate, the expression
The vector sum of two vectors A and B:
k ops returns a tuple of k operators that are the ac{array (1,N) of
cumulation
operators.
[i] = A[i]+B[i] || i <- 1 to N }
The nal set of clauses speci es the indexes and
values
for the accumulation. In each clause, eis
A statement de ning an array using a \wavefront"
is a k-tuple of indices i1,...,ik, and evs is a krecurrence:
tuple of values v1,...,vk, specifying the accumulaA = {matrix (1,N),(1,N) of
tions:
[1,1] = 1
| [i,1] = 1
| [1,j] = 1
| [i,j] = A[i-1,j] +
A[i,j-1]
|| i <- 2 to N
|| j <- 2 to N
|| i <- 2 to N
; j <- 2 to N };
X1[i1] := op1 X[i1] v1
...
Xk[ik] := opk X[ik] vk
Each such accumulation is executed atomically.
2. Functional Id
17
The array value of the entire expression is returned
only after all the accumulations have been done.
Thus, accumulators are hyperstrict, unlike ordinary
arrays, which are non-strict.
Since the order in which the accumulation operations are performed is non-deterministic, it is the
programmer's responsibility to ensure that the accumulation operators have the following property:
(op (op x y) z)
= (op
(op x z) y)
so that the whole construct is deterministic.
Example
A 10-category histogram of a zillion things:
{array (1,10) of
[i] = 0 || i <- 1 to 10
accumulate (+) of
[classify x] = 1 || x <- zillion_things }
2.36 Abstract Types
A new abstract data type is declared using this statement:
abstype NEWTYPE
typeof x1 = TYPE1 ;
...
typeof xN = TYPEN
rep
REPRESENTATION-TYPE
{
...
def x1 = ... ;
...
def xN = ... ;
...
};
is the (possibly parameterized) new type expression.
The subsequent typeof statements specify the signature (or interface) of the abstract type.
The REPRESENTATION-TYPE is a type-expression
specifying the internal representation of objects of
the new type.
The statements in the braces specify de nitions
for the identi ers in the signature. There may be
other identi ers de ned in the braces, but they are
NEWTYPE
not exported|they are just local types and local
de nitions.
The net e ect of the abstype statement is to introduce the new type identi er and the identi ers x1
through xN into the current scope. Each xJ has the
speci ed type signature and bound value.
Within the braces, the abstract type is treated
as equivalent to the representation type. Outside
the abstype statement, the abstract type and the
representation type are treated as distinct (di erent)
types.
The representation type may be a local type, i.e.,
declared in the braces. If so, it is not even visible
outside.
Example
A stack, with a list representation:
abstype (stack *0)
typeof empty = (stack
typeof empty?= (stack
typeof push = *0 ->
(stack
typeof pop
= (stack
typeof top
= (stack
rep (list *0)
{
empty = nil ;
empty? = nil? ;
push = (:) ;
*0);
*0) -> bool;
*0) -> (stack *0);
*0) -> (stack *0);
*0) -> *0
def pop (x:s) = s
| pop nil
= error "Stack underflow" ;
def top (x:s) = x
| top nil
= error "Stack underflow"
};
(See Section 2.38 for the error function.)
2.37 Loops
While list- and array-comprehensions are convenient
for expressing \mapping" operations over sequences,
loops are convenient for expressing \reduction" operations. Id has while-loops and for-loops.
The general while-loop expression notation
is:
{while eb do
STATEMENT ;
18
...
STATEMENT
finally e}
2. Functional Id
2.37.1 Scope of Variables in Loops
:: t
where eb :: bool and e :: t.
The general for-loop expression notation is:
{for x <- eIndex do
STATEMENT ;
...
STATEMENT
finally e}
:: t
where eIndex :: (list *0) and e :: t. The forloop notation is shorthand for a while-loop:
{ L = eIndex
In
{while (L <> nil) do
x:(next L) = L ;
STATEMENT ;
...
STATEMENT
finally e}}
Here, eIndex is normally an arithmetic-series expression (see Section 2.33.2).
The braces are compulsory. The type of the entire
loop expression is the type of the expression in the
\finally" phrase.
The loop body is a series of statements, with
the following extension: a binding occurrence of an
identi er (say \x") may be pre xed by the keyword
\next", denoting the value to be used for \x" in the
next iteration. This value is also available in the current iteration because \next x" may be used as an
expression.
The phrase \finally e" may be omitted:
{while/for ...
STATEMENT
...
STATEMENT } :: void
This is syntactic shorthand for:
{while/for
STATEMENT ;
...
STATEMENT
finally () }
Although there is nothing non-functional about this
by itself, it is useful mainly in non-functional programs (Sections 3, 4 and 5).
See Section 7.2 on \bounded loops" for annotations to limit the parallelism of loops.
We use the phrase loop context to refer to the set of
variables available to the loop expression from the
surrounding scope. Any variable \x" from the loop
context takes on a new value at each iteration if there
is a \next x" binding in the loop body.
In while-loops, the predicate may only use identiers from the loop context, and is re-evaluated each
time before entering the loop body.
The loop is terminated in while loops when the
predicate evaluates to false. Then, the finally e
expression is evaluated and returned as the value of
the loop. It may only use identi ers from the loop
context.
Within the loop body, only variables from the loop
context may be \nexti ed". The loop body may also
contain ordinary identi er bindings. The scope of all
bindings is the entire loop body (this includes the
nexti ed variables, since \next x" may be used as
an expression within the body).
For any nexti ed identi er \x", the bound value
becomes the value of \x" at the end of the iteration.
2.37.2 Loop semantics
While-loops are equivalent to tail-recursive functions, according to the correspondence illustrated by
the following example. Assume that x and y are the
only two nexti ed variables, and that their bindings
are the last two statements in the loop body:
{while eB do
STATEMENT
...
STATEMENT
next x = ex ;
next y = ey ;
finally eF}
:: t
This loop is equivalent to:
{ def loop x y = if eB then
{ STATEMENT
...
STATEMENT
next_x = ex ;
next_y = ey ;
In
loop next_x next_y}
else
2. Functional Id
19
eF ;
In
loop x y } ;
{ x,y = 1,1
In
{for j <- 1 to n do
next x,next y = y, x+y
finally x}}
The function loop has a parameter for each nextied variable. The loop body is transcribed verbatim
into the block inside the conditional, with the exception that we systematically replace all occurrences 2.38 Errors
of \next x" by the identi er next x. The returnexpression of the block is a tail-recursive call to loop There are three types of errors that may be produced
during execution of an Id program:
using the next values of x and y.
The translation illustrates a number of points.
The initial values of x and y come from the surround- Error values, written ?. For example, the expression v1/v2 evaluates to ? if v2 is zero. Ering scope. If eB evaluates to False the rst time, the
ror values should be regarded as synonymous
loop body is not executed at all. Because of the parwith non-terminating computations, i.e., it is
allel semantics of blocks, the recursive call (to the
as
if the erroneous operation that produced ?
next iteration) may execute in parallel with the curis stuck forever.
rent call. In principle, all iterations may execute in
parallel and, indeed, the loop can even return a nal Error statements, written statement? . For exresult while the loop bodies are still executing.
ample, a pattern-binding statement:
Bounded Loops
(x:y) = e ;
is replaced by statement? if e evaluates to Nil
(i.e., the pattern-match fails). Another reason
for this error is an out-of-bounds index in an
array-store operation (see Sections 4 and 5).
Inconsistency, written >. This is a drastic error,
in that it renders the entire program inconsistent. For example, in an array comprehension,
if some element of the array is speci ed more
than once, the program is inconsistent. The
usual reason for this error is multiple I-stores
into the same location (see Section 4).
The above description of loops semantics is correct
to rst order. However, the user may specify that a
loop should be compiled as a bounded loop, which
limits the degree of unfolding to a xed number of
iterations. The net e ect of bounded loops is possibly to increase the strictness of loops in exchange for
better resource utilization, i.e., it can a ect termination. Bounded loops are discussed fully in Section
7.2.
In the absence of explicit user directives, it is
unspeci ed whether loops are compiled as bounded
loops or not.
For ? and statement? , implementations of Id may
provide some interactive means for the user to articially repair the error and continue execution. For
Examples
>, on the other hand, no such repair is meaningful.
Successive approximations until convergence to a Functional Id programs and programs that use Ilimit:
structures (Section 4) are determinate (Church{ approx = first_guess ;
Rosser) even in the presence of errors. A prodelx
= infinity
gram:
In
may be inconsistent, or
{while (delx > epsilon) do
produces a value (perhaps the error value ?) and
next approx = improve approx ;
next delx
= (next approx)-approx
zero or more statement? s.
finally x}}
This behavior is repeatable, i.e., di erent runs of
the program will always produce the same outcome,
The n'th Fibonacci:
despite di erences in runtime scheduling.
20
3. Functional Id/General non-functional
Forced errors
The programmer can force an error using the function:
error
:: string -> *0
which always evaluates to ?. The argument string
e should be a meaningful error-message. Because of
its polymorphic output type, the error function may
be applied in any context.
3 General issues concerning nonfunctional
constructs
(I-structures and M-structures)
I-structures are a small departure, and M-structures
are a major departure from purely functional semantics. I-structures and M-structures are layered on
top of the purely functional subset of Id by constructs that are distinguished by syntax and by type,
i.e., it is possible to mechanically check whether a
program is purely functional or whether it uses Istructures or M-structures.
This section discusses general issues concerning
these non-functional extensions. I-structures are described in detail in Section 4, and M-structures are
described in detail in Section 5.
3.1 I-structure and M-structure semantics
The primitive side-e ecting constructs in Id have
to do with updating components of data structures.
There is no assignment statement for ordinary variables. A component of a data structure may have
either functional, I-structure or M-structure semantics. Operations on all three have built-in synchronization.
The value of a functional component of a data
structure is speci ed simultaneously with the creation of the data structure. Of course, the component cannot be updated, and it can be read many
times. The programmer never considers synchronization explicitly, except inasmuch as one is aware
that one can use non-strictness to de ne data structures using recurrences. All data structures described in Section 2 were functional.
For a non-functional component of a data structure, no value is speci ed when the data structure is
created; instead, a separate assignment statement is
used. A non-functional component may be in one of
two states: full (with a value), or empty . All components begin in the empty state (when the data
structure is allocated) and later become full through
assignment statements. I-structure and M-structure
components have di erent semantics for reading and
writing, and are described in detail in Sections 4 and
5, respectively.
3. General non-functional
21
For algebraic types and records, di erent elds of
an object may have di erent semantics: functional,
I-structure or M-structure. The semantics of each
eld is speci ed in the type declaration. A given eld
can only be accessed according to its declaration|
with functional, I-structure or M-structure semantics; this is ensured by a combination of syntax and
type checking.
For arrays, on the other hand, there are three
types of arrays: functional, I-arrays and M-arrays.
Thus, all components of an array have the same semantics, and this is re ected in the array type itself.
Again, type-checking ensures proper access.
3.2 Polymorphism of I-structures and Mstructures
Updatable structures do not mesh well with polymorphism. In order to be safe, our type-checker is
very conservative, and so the polymorphism of some
programs with I-structure objects may be less than
expected.
(Comment for experts: the polymorphism of Istructure and M-structure components is expressed
with so-called \weak" type variables, similar to ref
types in ML.)
3.3 Referential Transparency, Sharing
and Object Identity
Programs that use only functional operations are referentially transparent, whereas programs that use Istructures or M-structures may not be. For example,
consider the following two expressions:
(e,e)
{ x = e
In
(x,x) }
These expressions are equivalent (except for eciency considerations) in the functional subset of Id,
i.e., both programs will produce exactly the same
answer except that one may use more resources than
the other. They are no longer equivalent if they use
I-structures or M-structures. For example, if e allocates and returns a data structure, the expression on
the left produces two references to two separate data
structures, whereas the expression on the right produces two references to the same structure. In the
functional subset of Id, these two situations are indistinguishable. With I-structures or M-structures,
on the other hand, they are distinguishable, because
an assignment via one reference to a data structure
can a ect what is read via another reference to the
same data structure.
Thus, when programming with I-structures and
M-structures, the programmer should be clear about
the sharing of computations and, by extension, the
sharing of data structures. The standard procedure:
same? :: *0 -> *0 -> bool
can be used to test if two values are identical (the
same object). Its behavior is unde ned on nonupdatable objects, such as numbers, functions and
algebraic types with no updatable components. For
example,
same? (5,6) (5,6)
may return true or false, depending on the implementation. The programmer is advised to use this
procedure only on updatable objects (I-arrays, Marrays, and algebraic types and records with I- elds
or M- elds).
3.4 What gets evaluated, and when
Consider a conditional expression:
if e1 then e2 else e3
In Section 2.24, we stated that e1 is evaluated rst
and then, depending on its value, either e2 or e3 (but
not both ) is evaluated.
In the functional subset of Id, this level of precision is not necessary| neither what nor when . Even
if some evaluation occurs in both e2 and e3, some
unnecessary work would be done, but it would not
a ect the outcome of the program. Further, it does
not matter if some evaluation occurs in e2 or e3 before e1 is evaluated.
With I-structures and M-structures, however,
both these issues are important. For example, if e2
and e3 both contained assignments to the same Istructure location, a runtime error would occur if
both were performed. Or, if e2 or e3 manipulated
some M-structure location, they could a ect each
other's outcome, or even the outcome of other expressions such as e1, if they were evaluated too early.
22
Thus, when using I-structures and M-structures,
the programmer must be clear about exactly which
expressions get evaluated, and when.
In general, for most expressions that have multiple sub-expressions, all sub-expressions are evaluated, and they are evaluated in parallel. For example, all expressions in a block, both expressions in
an in x expression \e1 op e2", all expressions in a
tuple expression, etc. are evaluated in parallel. The
exceptions to this general rule are described below.
Conditionals :
if e1 then e2 else e3
3. General non-functional
does not cause any evaluations in eBody| it just
creates a function value (a closure). Partial applications of this function value (i.e., applications to
fewer than N arguments) simply build new function
values. When fully applied to N arguments, a new
instance of eBody is created and is evalauted.
Loops : the evaluation order is derived from the
translation to tail-recursive form, as described in
Section 2.37.2. Brie y, without going into this translation, in a while-loop:
{while eb do
STATEMENT ;
...
STATEMENT
finally e}
The predicate e1 is evaluated fully. After its boolean
value is available, one of the arms e2 or e3 is evaluated. However, please note the following subtlety none of the statements in the body are executed until
due to non-strictness: this does not mean that there eb evaluates to True, after which all the statements
is no overlap between the evaluation of e1 and the and the next invocation of eb are evaluated in parallel. After a particular invocation of eb evaluates to
evaluation of e2/e3. Consider this conditional:
False, the corresponding loop body is not executed
if (Nil? (eH:eT)) then e2 else e3
at all, and the corresponding nal expression e is
Because of non-strictness, the predicate can return evaluated.
False even if no evaluation of eH and eT has yet taken
Delayed expressions : See Section 6
place, and this enables the evaluation of e3. Thus,
the evaluations of eH, eT and e3 can overlap. Thus, Barriers : See Section 3.7.
non-strictness should be kept in mind when reasoning about when an expression is evaluated, in this 3.5 Determinacy
and all subsequent rules.
Case expressions (this is the general form of the rule Programs in the functional subset of Id are guaranteed to be determinate, by which we mean that
for conditionals):
that it is impossible for the programmer to write a
{case e of
program that, despite di erent schedules on di erpat1 = e1
ent runs, produces two di erent outcomes. Formally,
| ...
functional programs are said to have the Church| patN = eN }
Rosser property.
The expression e is evaluated completely. When it is
successfully matched to one of the patterns, say patJ, Programs which use only functional data structhe corresponding arm eJ is evaluated completely. tures and I-structures (not M-structures) are also
guaranteed to be determinate (despite the loss of
Function de nitions and applications :
referential transparency).
def f x1 ... xN = eBody ;
Programs that use M-structures are not guaranteed
to be determinate. Of course, through careful
Nothing is evaluated in eBody. After the function f
use
of
M-structures, it is still possible to write dehas been applied to N arguments, a new instance
of eBody is created and is evaluated. Partial appli- terminate programs (indeed, this is often an explicit
cations of f (i.e., application to fewer than N argu- goal), but it is important to understand the di erence: in functional Id and with I-structures, determiments) do not cause any evaluation in eBody.
nacy is a property of the language (every program
Function abstractions have similar behavior. Evalu- has this property), whereas with M-structures, deating the expression:
terminacy is only a property of particular programs
(has to be proved separately for each program).
{fun x1 ... xN = eBody}
3. General non-functional
23
3.6 Side-e ect statements
3.7 Sequencing Statements: barriers
In the functional subset of Id, a statement always
binds identi ers on the left-hand side to values from
the right-hand side (e.g., in a block or loop body).
With I-structures and M-structures, we can also
have side-e ect statements.
Primitive side-e ect statements are assignments of
values to I-structure or M-structure components.
Such a statement has the form:
By using \---" in a statement sequence, the programmer can indicate that all statements before it
must execute completely before any statement after
it can begin:
slot-designator = e ;
{ s1 ;
...
sI ;
--sJ ;
...
sN
In
e }
where slot-designator is an identi er (not a general expression) followed by zero or more functional
or I-structure array and eld selectors, followed by Here, s1 through sI execute completely before the
exactly one I-structure or M-structure array or eld execution of sJ through sN or e begins.
selector. Examples:
When we say that a statement S must \execute
a[3] = e1 ;
completely", we include, transitively, anything that
b![4] = e2
S calls, anything that those computations in turn
c.name = e3;
call, and so on. This is sometimes also referred to as
d!balance = e4;
\hyperstrict" evaluation. The \---" lexeme can be
e[4].name = e5 ;
read
visually as a \barrier".
f.months[12]!balance = e6 ;
Note that slot-designators are unrelated to patterns, Unless the last statement in a block is followed by
an \---", it is executed in parallel with the returnand there are no identi er bindings involved.
expression. Compare these two expressions:
An expression e can be executed purely for its side
{ s1
{ s1
e ect by using it in a statement that discards its
----result:
s2
s2
In
STATEMENT ;
...
_ = e ;
...
STATEMENT
--e}
In
e }
On the left, e is evaluated in parallel with s2; on the
right, e is evaluated after the execution of s2.
The single underscore may be regarded as a special, Parentheses may be used to group statements to
dummy identi er to which the value of e is bound limit the extent of the sequentialization:
and never referred to further.
{ s1 ;
However, conditionals, loops, case and block ex- ( s2
--pressions can be used directly as statements (the
s3 ;
\ = " can be omitted):
s4 ) ;
STATEMENT ;
...
if ... then ... else ;
{while/for ...
} ;
{ STATEMENT; ... ; STATEMENT in e'} ;
{case ...
} ;
...
STATEMENT
s5
In
e }
Here, s1, the parenthesized statement group, s5 and
are evaluated in parallel. Within the statement
group, s2 is evaluated rst, after which s3 and s4
are evaluated in parallel.
e
24
3. General non-functional
Grouping statements using parentheses does not
a ect the scope of identi ers (hence one could not
in general replace the parentheses by braces in the
block shown above). For example:
{ s1 ;
( x = .... y ... ;
--s3 ;
s4 ; ) ;
y = e5 ;
In
e }
% s2
The use of y in statement s2 is perfectly legal; there
is no violation of scope rules.
Similarly, barriers and statement groupings, which
concern dynamic control, are irrelevant for type definitions and type declarations, since these are static
declarations. For uniformity, the programmer may
regard all type de nitions and declarations in a block
as if they occurred at the top of the block.
However, the programmer should notice that while
the order of the statements has not e ect on the
scopes of identi ers, the order can be important to
prevent deadlock. For example:
{ s1 ;
( x = .... y ... ;
--s3 ;
y = e4 ; ) ;
s5 ;
In
e }
% s2
There is no violation of scope rules, but the program
will deadlock because statement s2 cannot complete
until y gets a value, and y cannot get a value until
s2 completes.
The behavior of barriers in loop bodies follows
from the translation to tail-recursive functions described in Section 2.37.2. Consider the following
loop:
{while eB do
STATEMENT1;
--STATEMENT2;
next x = ex ;
next y = ey ;
finally eF}
The translation is:
{ def loop x y = if eB then
{ STATEMENT1;
--STATEMENT2;
next_x = ex ;
next_y = ey ;
In
loop next_x next_y}
else
eF ;
In
loop x y } ;
From this, it is obvious that the recursive call for the
next iteration cannot begin until STATEMENT1 completes. The net e ect is that the entire loop runs sequentially. The programmer should be careful about
this behavior: a single unadorned barrier in a loop
body sequentializes the loop!
If the programmer wishes to localize the barrier
to individual iterations while allowing separate iterations to run in parallel, parentheses may be used as
usual to localize the barrier. For example:
{while eB do
( STATEMENT1;
--STATEMENT2; )
next x = ex ;
next y = ey ;
finally eF}
:: t
The translation is:
{ def loop x y = if eB then
{ ( STATEMENT1
--STATEMENT2 )
next_x = ex ;
next_y = ey ;
In
loop next_x next_y}
else
eF ;
In
loop x y } ;
Now, the recursive call can begin as soon as we know
that eB is True, and all iterations can, in principle,
run in parallel.
Barriers are used primarily in M-structure programs for regulating the order in which side-e ects
are performed (including I/O). Here, insertion or
omission of a barrier must be done with care, as
it can substantially change the semantics of a pro-
4. General non-functional/I-structures
gram (produce di erent answers or introduce runtime multiple-put errors).
For programs that do not use M-structures
(purely functional, or with I-structures), barriers
only change the termination behavior (strictness) of
programs. For example:
( _ = y ;
--x = e ; )
The barrier causes the expression e to become strict
in y, i.e., e does not evaluate until y gets a value
(from the surrounding context). In extreme cases,
of course, insertion of a barrier can introduce deadlock into an otherwise deadlock-free functional or Istructure program.
Barriers are also used in programs that perform
explicit storage management (Appendix A.14).
3.8 Sequencing expressions
The seq form may be used to sequentialize the evaluation of expressions:
{seq e1; e2; ... ; eN}
Here, e1, e2, ..., and eN are evaluated sequentially,
and the value of eN is returned as the value of the
whole expression. The values of the other eJ's are
discarded. The type of the entire expression is the
type of eN.
The seq form is an abbreviation for:
{ _
= e1
--_
= e2
--...
--foo = eN
In
foo }
4 I-structures
25
I-structures are a small departure from purely functional semantics. I-structures are layered on top of
the purely functional subset of Id by constructs that
are distinguished by syntax and by type.
Please refer to Section 3 for general issues concerning non-functional constructs.
4.1 I-structure semantics
A component of a data structure may have Istructure semantics (as opposed to functional or Mstructure semantics). For such a component, no
value is speci ed when the data structure is created;
instead, a separate assignment statement is used. An
I-structure component may be in one of two states:
full (with a value), or empty . All components begin in the empty state (when the data structure is
allocated).
An I-structure component has a single assignment
restriction, i.e., it can only be assigned once, at
which point its state goes from empty to full. Any
attempt to assign it more than once is caught as a
runtime error. The component can be read an arbitrary number of times. Further, any attempt to read
a component that is empty is automatically blocked
until it becomes full. Thus, the programmer does not
have to worry about sequencing the reads after the
assignment|there is no race condition. I-structure
reads and writes are called I-fetches and I-stores ,
respectively.
Multiple I-stores into the same location cause a
drastic runtime error. The entire program is said to
be inconsistent, or > (see Section 2.38).
4.2 I-structure arrays
I-structure arrays are array-like data structures with
empty locations which can be assigned subsequently
using I-structure semantics. These arrays are also
referred to as I-arrays.
4.2.1 I-array types
An n-dimensional I-array whose components are of
type t has type:
26
4. I-structures
nD_I_array t
Synonyms for the type name 1D I array:
I vector
I array
Synonym for the type name 2D I array:
I matrix
4.2.2 I-array creation
4.2.4 I-array selection
Assuming:
a
e1
:: (nD_I_array t)
:: (int,...,int)
then the I-array selection expression:
a[e1]
:: t
An n-dimensional I-array is created using the func- uses an I-fetch operation to return the value of the
tion:
(j1,...,jn)'th component of the I-array \a", where
nD_I_array::((int,int),
(j1,...,jn) is the value of \e1".
...,
If the index e1 is out of bounds, the selection ex(int,int)) -> (nD_I_array *0)
i.e., it takes an index bounds expression (an n-tuple pression evaluates to the error value ? (see Section
of integer 2-tuples) and returns an empty I-array 2.38).
with those bounds.
The selection notation is overloaded in two ways|
It is legal for the index bounds (l; u) along any on functional and I-arrays, and on arrays of di erdimension to be empty, i.e., to have u = l ? 1 (zero ent dimensions| and must thus be resolvable by
components). However, if u < l ? 1, the function the type checker. The corresponding non-overloaded
function for I-arrays is:
returns the error value ? (see Section 2.38).
select~nD_I_array ::
Synonyms for 1D I array allocator:
I vector
I array
(nD_I_array *0) -> (int,...,int) -> *0
Synonym for 2D I array allocator:
I matrix
Example
A 2-dimensional 10 10 I-array:
I_matrix ((1,10),(1,10))
4.2.3 I-array assignments
Assuming:
a
e1
e2
:: (nD_I_array t)
:: (int,...,int)
:: t
then the I-array assignment statement:
a[e1] = e2 ;
4.2.5 I-array index bounds
For each n 1, there is a function that returns the
index bounds of n-dimensional I-arrays:
bounds~1D_I_array ::
(1D_I_array t) -> (int,int)
bounds~2D_I_array ::
(2D_I_array t) -> ((int,int),(int,int))
...
The overloaded identi er bounds represents all these
functions.
See Appendix A.9 for standard I-array functions.
uses an I-store operation to assign the value of \e2"
to the (j1,...,jn)'th component of the I-array \a",
where (j1,...,jn) is the value of \e1".
Example
If the index e1 is out of bounds, the statement An I-array containing j 2 at the j 'th index:
is equivalent to the error statement statement? (see
{ x = I_array (1,10) ;
Section 2.38).
{for j <- 1 to 10 do
The assignment statement is overloaded for all dix[j] = j * j}
mensions of I-arrays and must thus be resolvable by In
x}
the type checker.
4. I-structures
27
4.3 I-structure elds in Algebraic Types
The new value in the J 'th component of X is the
value of eV.
Unlike arrays, where the entire structure has either It is a runtime error if X is not a tcons disjunct|
functional, I-structure or M-structure semantics, an
statement is equivalent to the error statement
algebraic type can have di erent elds with di erent the
statement? (see Section 2.38).
semantics.
4.3.1 Type de nition
4.3.4 Component selection
Recall from Section 2.11 that an algebraic type def- Assuming:
X :: tx tv1 ... tvN
inition looks like this:
type tx tv1 ... tvN = disj1 | ... | disjM;
and assuming that it is of the form:
tcons v1 ... vN
where each disjunct looks like this:
tcons t1 ... tL
the, if its J 'th component is an I- eld, it may be
We extend this notation as follows. In each disjunct, selected using an I-fetch operation using the eld
each tJ may be preceded by \." to indicate that it selection expression:
has I-structure semantics. Such elds are known as X.tcons_J
I- elds.
It is a runtime error if X is not a tcons disjunct,
producing the error value ? (see Section 2.38).
4.3.2 Object creation
First, we de ne Constructor Terms as applicative 4.3.5 Component selection in patterns
forms:
I- elds may be read using pattern-matching in extcons e1 ... eN
actly the same way as functional elds. In other
where tcons is a constructor identi er (not an ar- words, an I- eld may be matched against a variable
bitrary expression or identi er) of arity N of some (in which case the value is bound to that variable),
a constant, another structured pattern, etc.
algebraic type.
Objects are created, as usual, by constructor
terms. However, an I- eld may be left empty by 4.3.6 Example: iterative map
using the special token \ " (underscore). Note:
values must be supplied for all normal functional Here is a tail-recursive implementation of map
components| they cannot be left empty. The type- using \open lists":
checker will ensure this.
type I_list *0 = I_Nil
,
list
| I_Cons *0 .(I_list *0) ;
4.3.3 Component assignment
Assuming:
X :: tx tv1 ... tvN
and assuming that it is of the form:
tcons v1 ... vN
then, if its J 'th component is an I- eld, it may be
assigned using an I-store operation using the eld
assignment statement:
X.tcons_J = eV ;
typeof map~list = (*0->*1) ->
(list *0) -> (list *1) ;
def map~list f Nil
= Nil
| map~list f (x:xs)= { iys = I_Cons (f x) _ ;
_ = map' f xs iys
In
I_list_to_list iys } ;
typeof map' = (*0->*1)
->
(list *0)
->
(I_list *1) -> void ;
28
def map' f Nil
L= { L.I_Cons_2 = I_Nil }
| map' f (x:xs) L= { L' = I_Cons (f x) _ ;
L.I_Cons_2 = L' ;
_ = map' f xs L' } ;
5. I-structures/M-structures
5 M-structures
M-structures are a major departure from purely
functional semantics. M-structures are layered on
The function I list to list converts an I list type top of the purely functional subset of Id by coninto an ordinarly list type.
structs that are distinguished by syntax and by type.
Please refer to Section 3 for general issues con4.4 I-structure elds in records
cerning non-functional constructs.
4.4.1 Type de nition
5.1 M-structure semantics
A eld of a record may be declared to have Istructure semantics by preceding its type with a \.". A component of a data structure may have MSuch elds are called I- elds.
structure semantics (as opposed to functional or Istructure semantics). For such a component, no
Example:
value is speci ed when the data structure is created;
type foo = {record fieldf =
int ;
instead, a separate assignment statement is used. An
fieldi = . int }
M-structure component may be in one of two states:
Here, foo is a new record type, containing a func- full (with a value), or empty . All components betional eld fieldf and an I- eld fieldi.
gin in the empty state (when the data structure is
allocated).
4.4.2 Record creation
An M-structure component can be assigned with
a put operation and read with a take operation. A
In the record construction expression, I- elds may value
be put only into an empty component|
be left empty using the special token \ ". Exam- it is acanruntime
error if it is already full. Many
ple:
take 's may be attempted concurrently on a compo{record fieldf = 23; fieldi = _ }
nent. They all block automatically if the compoFor convenience, I- elds that are to be left empty nent is empty. When it is full, exactly one of them
may be omitted entirely, so that the above example succeeds in reading the value and the component
again becomes empty, so that the other take 's remain
could be written:
blocked.
It is unspeci ed as to which take amongst
{record fieldf = 23}
competing take 's will succeed.
In typical usage of M-structure components, sev4.4.3 Field assignment
eral concurrent computations share a resource. Each
An I- eld fieldi of a record X may be assigned us- computation takes it, computes with it, and puts it
ing an I-store operation using the eld assignment back. The semantics guarantees that each computation has exclusive access to the resource. Note: for
statement:
correct operation, every take must be followed by
X.fieldi = eV ;
a put , i.e., it is the programmer's responsibility to
The new value in the eld of X is the value of eV.
make sure that these operations are \balanced".
In some situations, the value to be put back is the
4.4.4 Field selection
same as the value taken out (e.g., if we simply want
to test the current value in an M-structure eld).
An I- eld fieldi of a record X may be selected using This combination| taking a value, putting it back,
an I-fetch operation using the expression:
and returning the value| is called an examine operX.fieldi
ation, for which syntactic shorthands are provided.
(The notation is the same as for normal functional In some situations, the value to be put back is
elds).
unrelated to the value taken out (e.g., if we simply
5. M-structures
29
want to reset an M-structure eld to a known value). 5.2.3 M-array creation
This combination| taking out the old value and discarding it, and putting in a new value| is called a An empty n-dimensional M-array is created using
replace operation, for which syntactic shorthands are the function:
provided.
mk_ D_M_array::((int,int),
n
...,
(int,int)) -> (nD_M_array *0)
5.2 M-structure arrays
i.e., it takes an index-bounds expression (an n-tuple
of integer 2-tuples) and returns an empty M-array
M-structure arrays are array-like data structures with those bounds.
with empty locations which can be assigned subsequently using M-structure semantics. These arrays It is legal for the index bounds (l; u) along any
dimension to be empty, i.e., to have u = l ? 1 (zero
are also referred to as M-arrays.
components). However, if u < l ? 1, the function
returns the error value ? (see Section 2.38).
5.2.1 M-array types
Synonyms for 1D M array allocator:
mk M vector
mk M array
An n-dimensional M-structure array whose compo- Synonym for 2D M array allocator:
nents are of type t has type:
mk M matrix
nD_M_array t
Synonyms for the type name 1D M array:
M vector
M array
Synonym for the type name 2D M array:
M matrix
Example
A 2-dimensional 10 10 M-array:
mk_M_matrix ((1,10),(1,10))
5.2.4 M-array assignment
5.2.2 M-array literals and comprehensions Assuming:
a
e1
e2
:: nD_M_array t
:: int,...,int
:: t
The array literal notation of Section 2.34.2 is extended to M-arrays by using the keywords M vector,
M array, M matrix and nD M array instead of their then the M-array assignment statement:
functional counterparts:
a![e1] = e2 ;
uses a put operation to assign the value of \e2" to the
j1,...,jn'th component of the M-array \a", where
The array comprehension notation of Section 2.34.5 j1,...,jn is the value of \e1".
is extended to M-arrays by using the keywords An M-array component can be replaced using the
M array, M vector, M matrix, k M arrays, k M vectors, statement:
k M matrices and k nD M arrays instead of their funca!![e1] = e2 ;
tional counterparts:
which is equivalent to:
{k_nD_M_arrays eBounds of
{nD_M_array eBounds of
eFirst ... eLast}
[e11] = e12 || gen ; ... ; gen
| ...
| [eM1] = eM2 || gen ; ... ; gen }
M-array literals and comprehensions are useful for
\initializing" M-arrays. The initializations use put
operations.
i = e1 ;
v = e2 ;
( _ = v
--_ = a![i] ;
--a![i] = v )
30
5. M-structures
In other words, the old value is taken only after bounds~1D_M_array ::
(1D_M_array t) -> (int,int)
the value of e2 is available, but note, due to nonstrictness, that sub-expressions of e2 may still be bounds~2D_M_array ::
(2D_M_array t) -> ((int,int),(int,int))
evaluating.
...
If the index e1 is out of bounds, the statements
are equivalent to the error statement statement? (see The overloaded identi er bounds represents all these
functions.
Section 2.38).
The assignment statement is overloaded for all dimensions of and M-arrays, and must thus be resolv- See Appendix A.10 for standard M-array functions.
able by the type checker.
5.2.5 M-array selection
Assuming:
a
e1
:: nD_M_array t
:: int,...,int
then the M-array selection expression:
a![e1]
:: t
5.3 M-structure elds in Algebraic Types
Unlike arrays, where the entire structure has either
functional, I-structure or M-structure semantics, an
algebraic type can have di erent elds with di erent
semantics.
5.3.1 Type de nition
uses a take operation to return the value of the
Recall from Section 2.11 that an algebraic type defj1,...,jn'th component of the M-array \a", where
inition looks like this:
j1,...,jn is the value of \e1".
An M-array component may be examined using the type tx tv1 ... tvN = disj1 | ... | disjM;
expression:
where each disjunct looks like this:
a!![e1]
tcons t1 ... tL
which is equivalent to:
We extend this notation as follows. In each disjunct,
each tJ may be preceded by \!" to indicate that it
has M-structure semantics. Such elds are known as
M- elds.
{ i
= e1 ;
v
= a![i] ;
a![i] = v
In
v }
If the index e1 is out of bounds, the selection expressions evaluate to the error value ? (see Section
2.38).
The selection notation is overloaded to work on
all dimensions of M-arrays, and must thus be resolvable by the type checker. The corresponding nonoverloaded function for M-arrays is:
5.3.2 Object creation
First, we de ne Constructor Terms as applicative
forms:
tcons e1 ... eN
where tcons is a constructor identi er (not an arbitrary expression or identi er) of arity N of some
take~nD_M_array ::
algebraic type.
(nD_M_array *0) -> (int,...,int) -> *0
Objects are created, as usual, by constructor
terms. However, an M- eld may be left empty
5.2.6 M-array index bounds
by using the special token \ " (underscore). Note:
values must be supplied for all normal functional
For each n 1, there is a function that returns the components| they cannot be left empty. The typeindex bounds of n-dimensional M-arrays:
checker will ensure this.
5. M-structures
31
5.3.3 Component assignment
which is equivalent to:
Assuming:
{ v = X!tcons_J ;
X!tcons_J = v
In
v }
X :: tx tv1 ... tvN
and assuming that it is of the form:
tcons v1 ... vN
It is a runtime error if X is not a tcons disjunct,
producing the error value ? (see Section 2.38).
then, if its J 'th component is an M- eld, then it
may be assigned using a put operation using the eld
assignment statement:
5.3.5 Component selection in patterns
X!tcons_J = eV ;
M- elds may be read using pattern-matching, but
An M- eld can be replaced using the state- only a limited form of patterns may be used:
ment:
X!!tcons_J = eV ;
which is equivalent to:
v = eV ;
( _ = v ;
--_ = X!tcons_J ;
--X!tcons_J = v )
In other words, the old value is taken only after
the value of eV is available, but note, due to nonstrictness, that sub-expressions of eV may still be
evaluating.
The new value in the J 'th component of X is the
value of eV.
It is a runtime error if X is not a tcons disjunct|
the statement is equivalent to the error statement
statement? (see Section 2.38).
_
(!x)
(!!x)
where x is an identi er , not a general pattern. The
parentheses in the latter two cases are mandatory.
When the pattern is an \ ", it indicates that the
M- eld is ignored during the pattern matching (no
take is performed).
When the pattern is \(!x)" or \(!!x)", it indicates that the value in the eld is to be taken or examined, respectively, and bound to the identi er x.
However, the take or examine operation is performed
only after it has been determined that the patternmatching is successful; the M- eld itself plays no role
in whether the pattern-matching is successful or not.
When a pattern fails to match, none of its takes or
examines are performed.
5.3.4 Component selection
5.3.6 Example: unique id generator
Assuming:
A type for data structures for generating unique
identi ers that are strings of the form "foo ":
X :: tx tv1 ... tvN
and assuming that it is of the form:
j
type uid = Uidcell string !int ;
A statement binding u to an updatable data structure for generating unique identi ers that are strings
the, if its J 'th component is an M- eld, then it may of the form "foo ":
be selected using a take operation using the eld
u = Uidcell "foo" _ ;
selection expression:
A statement initializing the unique identi er generX!tcons_J
ator u:
An M- eld may be examined using the expresu!Uidcell_2 = 0 ;
sion:
X!!tcons_J
Generating the next uid foo from the object u:
tcons v1 ... vN
j
j
32
5. M-structures
{ Uidcell prefix (!j) = u ;
u!Uidcell_2 = j+1 ;
uid = conc~string prefix (int_to_string j)
In
uid }
5.3.7 Example: FIFO queue
have I-structure semantics. However, the two components of the queue structure are repeatedly updated (by every enqueuer and dequeuer), so they
have M-structure semantics.
5.4 M-structure elds in records
We can implement a fo queue using the following 5.4.1 Type de nition
type:
A eld of a record may be declared to have Mtype queue *0 = Queue !(open_list *0)
structure semantics by preceding its type with a \!".
!(open_list *0) ;
Such elds are called M- elds.
type open_list *0 = Ocons .*0
Example:
.(open_list *0);
type foo = {record
fieldf =
int ;
For example, a fo queue in which a, b and c have
fieldm = ! int }
been inserted (in that order) would be:
Here, foo is a new record type, containing a func{ tail = Ocons _ _ ;
tional eld fieldf and an M- eld fieldm.
In
Queue (Ocons a
(Ocons b
(Ocons c
tail)))
tail }
5.4.2 Record creation
In the record construction expression, M- elds may
be left empty using the special token \ ". ExamThe idea is that the Queue structure points at the ple:
head and the tail of the queue. The tail is an Ocons {record fieldf = 23; fieldm = _ }
cell containing an empty slot for the next object to
be enqueued, and an empty slot to grow the queue. For convenience, M- elds that are to be left empty
may be omitted entirely, so that the above example
Here are the functions to manipulate the could be written:
queue:
def mk_empty_q () = { ol = Ocons _ _
In
Queue ol ol } ;
def enqueue x q =
{ Queue _ (!tail) = q ;
newtail = Ocons _ _ ;
tail.Ocons_1 = x ;
tail.Ocons_2 = newtail ;
q!Queue_2 = newtail ;
In
() } ;
def dequeue q =
{ Queue (!head) _ = q ;
Ocons x nexthead = head ;
q!Queue_1 = nexthead ;
In
x } ;
Note that the components of the open list structures are each assigned exactly once, so that they
{record fieldf = 23}
5.4.3 Field assignment
An M- eld fieldm of a record X may be assigned using a put operation using the eld assignment statement:
X!fieldm = eV ;
An M- eld fieldm of a record may be replaced using
the statement:
X!!fieldm = eV ;
which is equivalent to:
v = eV ;
( _ = v;
--_ = X!fieldm ;
--X!fieldm = v ; )
6. M-structures/Delayed evaluation
33
In other words, the old value is taken only after 6 Delayed evaluation
the value of eV is available, but note, due to nonstrictness, that sub-expressions of eV may still be Annotations for delayed evaluation are experimental
evaluating.
features of Id to gain experience with in nite strucThe new value in the eld of X is the value of eV. tures. Semantically, their only e ect is to change the
termination behavior of programs. Pragmatically,
they can drastically change the runtime resource re5.4.4 Field selection
quirements of a program.
An M- eld fieldm of a record X may be selected using
a take operation using the expression:
X!fieldi
An M- eld fieldm of a record X may be examined
using the expression:
X!!fieldm
which is equivalent to:
{ v = X!fieldm ;
X!fieldm = v ;
In
v }
6.1 General Delayed Evaluation
Assuming:
e :: t
is an expression that evaluates to v, then the expression:
{# e} :: (delay t)
returns d, an unevaluated representation of e called
a thunk .
The standard function:
force :: (delay *0) -> *0
takes a thunk d, evaluates the delayed expression in
it, and returns v, its value. It also \memoizes" the
value, so that in multiple evaluations of (force d),
the delayed expression itself is evaluated only once.
The memoization is transparent|there is no test
available to the programmer to determine whether
a delayed object has been forced or not.
Note that a delayed object has a di erent type
from the object iteself, and the value is always extracted using force. Thus, the following two expressions below are incorrect and will be caught by the
type-checker:
1 + (force 5)
1 + {# 5}
% forcing an undelayed object
% adding a delayed object
6.2 Delayed Evaluation For Data Structure Components
While expressions in arbitrary contexts may be delayed using {# ...}, it is frequently the case that the
delayed object is a component of a data structure.
In this situation, one can use a special notation for
greater eciency (less space overhead for thunks)
and convenience (no distinction of delayed objects
on the basis of type, no need for an explicit force).
34
6. Delayed evaluation
6.2.1 Delayed components in algebraic types
First, we de ne Constructor Terms as applicative
forms:
c e1 ... eN
where c is a constructor identi er (not an arbitrary
expression or identi er) of arity N of some algebraic
type. Examples:
e1 : e2
bnode e1 e2 e3
e1 :
e1 :#
e1 #:
e1 #:#
e2
e2
e2
e2
normal---eager head and tail
eager head, delayed tail
delayed head, eager tail
delayed head and tail
Delayed list-comprehensions may be written by
changing the opening \:" symbol:
{:
{#:
{:#
{#:#
e
e
e
e
||
||
||
||
gen
gen
gen
gen
...
...
...
...
}
}
}
}
%
%
%
%
normal
delayed heads
delayed tails
delayed heads, tails
Assuming:
but not:
e1::int
(:) e1
bnode e1 e2
%
%
%
%
% arity not satisfied
% arity not satisfied
eInc::int
evaluate to integers v 1 and vInc, respectively, then
the expressions:
(See Section 2.11 for the binary tree algebraic type upfrom e1 by eInc
:: (list N)
with constructor bnode.)
downfrom e1 by eInc
:: (list N)
In a constructor term, any argument may be an- produce in nite lists containing (v 1, v 1 + vInc,
notated by \#" to indicate that it should be delayed. v 1 + 2vInc, ...), and (v 1, v 1 ? vInc, v 1 ? 2vInc,
Example:
...), respectively.
bnode e1 #e2 e3
Note: vInc must always be positive.
constructs a binary tree with the left subtree expres- The short forms:
sion delayed.
upfrom e1
:: (list N)
Unlike general delayed expressions, delayed data- downfrom e1 :: (list N)
structure components are of the same type as if they
were not delayed. There is no explicit force oper- assume that vInc is +1.
ation. A delayed component is evaluated implicitly
(and stored in the data structure) when an attempt 6.2.2 Delayed components in records
is made to select it (usually in some pattern-match).
For example, if e1::t1, then
A component of a record may be delayed using \#"
instead
of \=":
bnode # e1 e2 e3 :: (btree t1)
bnode {# e1} e2 e3 :: (btree (delay t1))
In the former, selecting the rst component of the
bnode implicitly evaluates the delayed expression and
returns an object of type t1, whereas in the latter, it
returns an object of type (delay t1), to which force
must be applied to get an object of type t1.
Delayed Lists
List constructor terms may be annotated too:
e1
e1
#e1
#e1
: e2
: #e2
: e2
: #e2
%
%
%
%
normal---eager head and tail
eager head, delayed tail
delayed head, eager tail
delayed head and tail
For compatibility with the delayed list-comprehension notation (below), the following notations may
also be used:
{record
field1 = e1;
...
fieldJ # eJ;
...
fieldN = eN}
Normal and delayed components may be mixed in a
single record.
6.2.3 Delayed components in functional arrays
Components of array-comprehensions may be delayed using \#" instead of \=":
{array (l,u) of
[ei] = ev || gen ...
| [ej] # ew || gen ... }
% normal components
% delayed components
7. Delayed evaluation/Pragmatics
Normal and delayed components may be mixed in
the same array.
35
7 Pragmatics
7.1 Inline substitution
6.2.4 Delayed components in I-structure arA function de nition
rays
def foo ... = ... ;
The delayed assignment statement (with the same
type rules as the ordinary assignment statement, may also be written:
Section 4.2.3):
defsubst foo ... = ...
;
Evaluation on selection
in which case the compiler will try to expand the
function in place wherever possible. This has no semantic consequence; it merely removes the overhead
of function-calls.
The substitution is semantically transparent (it is
not a macro). The function itself is still available as
a value.
The inlinable functions can be recursive and mutually recursive. The compiler will inline only upto
a xed maximum depth.
c1
(x:_)
c2
7.2 Bounded loops
a[e1] # e2
stores a thunk for e2 in the e1'th location of a. When
that location is selected, the thunk is implicitly evaluated, and the value replaces the thunk.
A component of a data structure that has been delayed using any of the above notations is evaluated
automatically the rst time that it is selected. This
is di erent from the situation in lazy languages!.
Consider:
= e1 #:# e2 ;
= c1
= x #:# e3 ;
Even though all we are doing is copying e1 from one
cons cell to another, it gets evaluated the moment
we select it (delaying the head of the c2 construction
is, therefore, pointless).
In principle, all iterations of a loop can run in parallel
(subject only to data dependencies). Pragmatically,
this may be undesirable as it can swamp the machine. Thus, loops are normally compiled as bounded
loops , i.e., no more than k iterations may execute simultaneously, for some loop bound k.
Normally, a default loop bound is used. The loop
bound can also be speci ed explicitly using the bound
keyword. Assuming ek::int, then in each of the
following forms:
{for j <- e bound ek do ... }
{while b bound ek do ... }
{: e || ... ; j <- e bound ek ... }
{array (l,u) of
...
| [ej] = ev || ... ; j <- e bound ek ...
| ... }
the corresponding loop is bounded to k, the value of
expression ek, which must be a positive integer.
A loop can be forced to execute sequentially using
the sequential reserved word:
36
{for j <- e sequential do ... }
{while b sequential do ... }
{: e || ...; j <- e sequential ... }
{array ... of
...
| [ej] = ev || ...; j <- e sequential ...
| ... }
7. Pragmatics
| [ej] = ev || ... ; j <- e unbounded ...
| ... }
Unbounded loops are semantically identical to tailrecursive functions.
7.3 Pragmas
A pragma is a statement agged by \@":
Bounded loops are not semantically identical to @identifier
tail-recursive functions, because they may deadlock where the corresponding tail-recursive function or
would not. An example using I-arrays:
@identifier expression
{ A = I_array (0,9) ;
A[10] = 0 ;
{for j from 1 to 9 do
A[j] = f A[j+1] }
In
A}
A block of pragmas may be inserted after the formal parameters in a function de nition to indicate
attributes of the function:
def f x1 ... xN {pragma;...;pragma} = e
Another example, in the purely functional subset Currently, the only pragma that may be used here
of Id: Suppose we want to nd biggest, the maxi- is:
mum of a 100-element array, and nbig, the number of @inlinable
elements within 10% of it. Normally, we would tra- @inlineable
verse the array twice, rst computing biggest, then
using it to compute nbig. But non-strictness may Use of this pragma is equivalent to using the keyword
defsubst instead of def.
tempt us to write a single loop:
b,nb = minfloat,0 ;
biggest, nbig =
{for j <- 1 to 100 do
next b = max A[j] b ;
next nb = if A[j]/biggest < 0.9 then nb
else nb+1
finally b,nb} ;
7.4 Loop peeling and unrolling
Loop peeling and unrolling are techniques to reduce
the overhead of loops. If we think of a loop as equivalent to a de nition of a tail-recursive function F
and an initial call to F , then loop peeling is similar
to inline substitution at the initial call site, and loop
unrolling is similar to inline substitution of F in the
(recursive) call site inside the body of F . In the limit
case, when a loop is completely peeled or unrolled,
they are the same.
Note that all iterations of the loop use biggest,
which is itself computed by the loop and is produced
by the last iteration. Thus, this loop will deadlock
with any k that does not allow it to unfold fully.
We strongly recommend against loops with backward dependencies, i.e., where a variable in an iteration depends on computations in future iterations.
However, if an unbounded loop is really necessary, it 7.4.1 Loop peeling
may be written using the unbounded keyword:
{for j <- e unbounded do ... }
The pragma:
{while b unbounded do ... }
{: e || ... ; j <- e unbounded ... }
{array (l,u) of
...
@peel j
when used as a statement in a loop body, may be
used to indicate that upto j iterations should be done
outside the loop. Here, j must be a positive integer
constant. For example,
7. Pragmatics
{while p do
@peel 1 ;
next x = e1 ;
...
finally eFinal}
is equivalent to:
if p then
{ next_x = e1' ;
...
In
{ x = next_x
In
{while p do
next x = e1 ;
...
Finally eFinal}}}
else
eFinal
where e1' uses next x wherever e1 used next x.
When used in for-loops with known index bounds,
the compiler will usually be able to remove the conditional by optimization.
7.4.2 Loop Unrolling
The pragma:
@unroll j
when used as a statement in a loop body, may be
used to transform the loop so that j iterations of
the original loop are performed in a single iteration
of the new loop. Here, j must be a positive integer
constant, or the keyword \completely". For example,
{while p do
@unroll 1 ;
next x = e1 ;
next y = e2 ;
...
finally eFinal}
is equivalent to:
{while p do
next_x' = e1' ;
next_y' = e2' ;
...
next x,next y =
{ x = next_x' ;
y = next_y'
in
if p then
37
{ next_x'' = e1'' ;
next_y'' = e2'' ;
...
In
next_x'',next_y'' }
else
next_x',next_y'}
finally eFinal}
where e1' and e2' use next x' and next y' whereever
e1 used next x and next y, respectively (and similarly for e1'' and e2'').
When used in for-loops with known index bounds,
the compiler will usually be able to remove the conditional by optimization.
The compiler will obey a pragma to unroll the loop
completely only if it is a for loop with known index
bounds.
38
7. Pragmatics
A. Standard identi ers
A Standard Identi ers
39
typeof
typeof
typeof
typeof
typeof
typeof
eq~float
ne~float
lt~float
le~float
gt~float
ge~float
=
=
=
=
=
=
float
float
float
float
float
float
->
->
->
->
->
->
float
float
float
float
float
float
->
->
->
->
->
->
bool;
bool;
bool;
bool;
bool;
bool;
Id has standard libraries that implement many useful
functions. The names and semantics of these functions are based on the corresponding Common Lisp
functions wherever possible. The names for these
functions are not reserved words, but for readability General
and re-usability of code, the programmer is strongly typeof pi = float;
typeof 2pi = float;
advised not to rede ne them.
The compiler should expand these functions in typeof odd? = int -> bool;
situ , so that there is no procedure-calling overhead. typeof even? = int -> bool;
typeof max~int
= int -> int -> int;
Since the Id libraries are a continuously grow- typeof
max~float = float -> float -> float;
ing repository of useful functions, the following list
is necessarily incomplete. The libraries themselves typeof min~int = int -> int -> int;
must be consulted for the current set.
typeof min~float = float -> float -> float;
Implementation-dependent numbers that are the
most positive (largest positive numbers):
A.1 Booleans
typeof maxint = int;
typeof maxfloat = float;
Truth values
Implementation-dependent numbers that are the
most negative (largest negative numbers):
typeof True = bool;
typeof False = bool;
typeof minint = int;
float;
These are also constructors (i.e., they can be used typeof minfloat =
in patterns).
Exponentiation
Negation
typeof exp = float -> float;
typeof not = bool -> bool;
where (exp
y)
Logarithms
) ey
A.2 Numbers
typeof log
= float -> float;
typeof log10 = float -> float;
Basic arithmetic
) loge x,
) log10 x
Square root, absolute value
typeof
typeof
typeof
typeof
negate~int
plus~int
minus~int
times~int
=
=
=
=
typeof
typeof
typeof
typeof
negate~float
plus~float
minus~float
times~float
=
=
=
=
typeof
typeof
typeof
typeof
typeof
typeof
eq~int
ne~int
lt~int
le~int
gt~int
ge~int
->
->
->
->
->
->
Comparison
=
=
=
=
=
=
int
int
int
int
int
int
int
int
int
int
->
->
->
->
int;
int -> int;
int -> int;
int -> int;
float
float
float
float
int
int
int
int
int
int
->
->
->
->
->
->
->
->
->
->
float;
float -> float;
float -> float;
float -> float;
bool;
bool;
bool;
bool;
bool;
bool;
where (log
and (log10
x)
x)
typeof sqrt
typeof abs~int
typeof abs~float
= float -> float;
= int
-> int;
= float -> float;
Trignometric functions
Angles are in radians.
typeof sin
typeof cos
typeof tan
= float -> float;
= float -> float;
= float -> float;
typeof asin = float -> float;
typeof acos = float -> float;
typeof atan = float -> float -> float;
40
A. Standard identi ers
where (atan y x) ) arctan y=x, in the range ? to where (rem
+ . The arguments cannot both be zero.
(x/y)).
Hyperbolic functions
typeof sinh
typeof cosh
typeof tanh
x y)
) x ? qy, where
(q
=
truncate
typeof mod = int -> int -> int;
where
= float -> float;
= float -> float;
= float -> float;
.
(mod x y)
(x/y))
typeof asinh = float -> float;
typeof acosh = float -> float;
typeof atanh = float -> float -> float;
) x ? qy, where
(q
=
floor
A.3 Characters
Conversion of integers to oats
Comparison
typeof float = int -> float;
typeof
typeof
typeof
typeof
typeof
typeof
Conversion of oats to integers
typeof floor = float -> int;
where floor truncates towards ?1.
typeof ceiling = float -> int;
eq~char
ne~char
lt~char
le~char
gt~char
ge~char
=
=
=
=
=
=
char
char
char
char
char
char
->
->
->
->
->
->
char
char
char
char
char
char
->
->
->
->
->
->
bool;
bool;
bool;
bool;
bool;
bool;
The ordering is only guaranteed within the following
classes: digit characters, upper case characters, and
lower case characters.
where ceiling truncates towards +1.
typeof truncate = float -> int;
where truncate truncates towards 0.
Character class predicates
typeof round = float -> int;
typeof digit? = char -> bool;
typeof uc?
= char -> bool;
typeof lc?
= char -> bool;
where round truncates to the nearest integer, with
x:5 truncated towards the even integer.
Convert case
The following four functions are similar to the previto_uc~char
ous four, except that they return their integer-valued typeof
typeof to_lc~char
results as oats, for convenience.
= char -> char;
= char -> char;
typeof ffloor = float -> float;
Character codes
where ffloor truncates towards ?1.
typeof char_to_int = char -> int;
typeof int_to_char = int -> char;
typeof fceiling = float -> float;
where fceiling truncates towards +1.
A.4 Strings
typeof ftruncate = float -> float;
where ftruncate truncates towards 0.
Comparison
typeof fround = float -> float;
where fround truncates to the nearest integer, with The comparison is lexicographic, based on the ordering of characters.
x:5 truncated towards the even integer.
The following functions are case-sensitive:
Integer division
typeof div = int -> int -> int;
where (div
x y)
) q, where ( =
q
.
truncate (x/y))
typeof quo = int -> int -> int;
where (quo
x y)
) q, where ( =
q
typeof rem = int -> int -> int;
.
floor (x/y))
typeof
typeof
typeof
typeof
typeof
typeof
eq~string
ne~string
lt~string
le~string
gt~string
ge~string
=
=
=
=
=
=
string
string
string
string
string
string
->
->
->
->
->
->
string
string
string
string
string
string
->
->
->
->
->
->
bool;
bool;
bool;
bool;
bool;
bool;
The following functions are case-insensitive:
A. Standard identi ers
typeof
typeof
typeof
typeof
typeof
typeof
eq_ci_string
ne_ci_string
lt_ci_string
le_ci_string
gt_ci_string
ge_ci_string
=
=
=
=
=
=
41
string
string
string
string
string
string
->
->
->
->
->
->
string
string
string
string
string
string
->
->
->
->
->
->
bool;
bool;
bool;
bool;
bool;
bool;
Convert to and from arrays of characters
typeof array_to_string =
(array char) -> string;
A.5 Symbols
Comparison
typeof eq~symbol = symbol -> symbol -> bool;
typeof ne~symbol = symbol -> symbol -> bool;
Hashing
typeof hash~symbol = int -> symbol -> int;
where (hash symbol s) hashes symbol
The argument must have index bounds (0, n ? 1) integer in the range 0 to ( ? 1).
when n is the length of the string.
Conversion with strings
n
s
into an
n
typeof string_to_array =
string -> (array char);
typeof string_to_symbol = string -> symbol;
typeof symbol_to_string = symbol -> string;
Convert to and from lists of characters
A.6 Lists
The result has index bounds (0, n ? 1) when n is the
length of the string.
typeof list_to_string = (list char) -> string;
typeof string_to_list = string -> (list char);
Length of string
typeof length~string = string -> int;
Index string
typeof nth~string = int -> string
-> char;
Basic functions
typeof
typeof
typeof
typeof
typeof
Nil
nil?
cons
hd
tl
=
=
=
=
=
(list
(list
*0 ->
(list
(list
First character has index 0.
Length of list
Given a starting position and substring length:
N 'th element of list
Extract substring
typeof substring = string ->
int
->
int
-> string;
Concatenate strings
*0);
*0) -> bool;
(list *0) -> (list *0);
*0) -> *0;
*0) -> (list *0);
typeof length~list = (list *0) -> int;
typeof nth~list = int -> (list *0) -> *0;
The head is the 0'th element.
First N elements of list
typeof first_n = int -> (list *0) -> (list *0);
typeof conc~string = string -> string ->
string;
N 'th tail of list
Map character function over string
typeof drop = int -> (list *0) -> (list *0);
typeof nthtl = int -> (list *0) -> (list *0);
typeof map~string = (char->char) ->
string
-> string;
= tln, so 0'th tail is the list itself.
nthtl is a synonym for drop.
Convert case
Convert a string to upper or lower case:
typeof to_uc~string = string -> string;
typeof to_lc~string = string -> string;
Hashing
typeof hash~string = int -> string -> int;
where (hash string s) hashes string s into an integer in the range 0 to ( ? 1).
n
n
drop n
Last element of list
typeof last = (list *0) -> *0;
Equality of lists
Given predicate to compare equality of components:
typeof eq~list =
(*0 -> *0 -> bool) ->
(list *0)
->
(list *0)
-> bool;
42
A. Standard identi ers
Reverse list
returns
typeof reverse = (list *0) -> (list *0);
f (f
(... (f z l0) l1) ...) ln
Zipping and unzipping
where l0, ..., ln are the elements of the list l.
typeof zipN =
(list *1) ->
...
(list *N) -> (list (*1,...,*N));
typeof foldr~list
(*0 -> *1 -> *1)
*1
(list *0)
A family of functions, for each N :
Right-associative reduction
The N input lists should all have the same length. Example:
If not, a runtime error occurs| the output list is as foldr~list f
long as the shortest input list, and the tail of the last
Returns
list cell is the error value ? (see Section 2.38).
typeof unzipN =
(list (*1,...,*N)) -> (list *1,
...
,
list *N);
Map function over list
Apply a function to each member of a list, returning
list of results in same order:
typeof map~list = (*0->*1) ->
(list *0) -> (list *1);
=
->
->
-> *1;
z l
f l0 (... (f ln z))
where l0, ..., ln are the elements of the list l.
Iteration
typeof iterate =
(*0 -> bool) ->
(*0 -> *0)
->
*0
-> (list *0);
where iterate p f x returns the list containing x,
(f x), (f (f x)), ..., as long as (p (fn x)) is true.
Simultaneous mapping and left-associative reReturn only those elements that satisfy predi- duction
Filtering
cate:
typeof filter =
(*0 -> bool) ->
(list *0)
-> (list *0);
Return longest pre x of elements that satisfy predicate:
typeof takewhile =
(*0 -> bool) ->
(list *0)
-> (list *0);
Omit longest pre x of elements that satisfy predicate:
typeof dropwhile =
(*0 -> bool) ->
(list *0)
-> (list *0);
Left-associative reduction
typeof foldl~list
(*0 -> *1 -> *0)
*0
(list *1)
Example:
foldl~list f z l
=
->
->
-> *0;
typeof map_foldl~list =
(*0->*1->(*0,*2)) ->
*0
->
(list *1)
-> (*0,list *2);
Example:
map_foldl~list f z l
returns (zN,m), where:
z0,m0 = f z l0
z1,m1 = f z0 l1
...
zN,mN = ...
, ..., lN are the elements of the list l, and m0, ...,
are the elements of the list m.
For example, if f was
l0
mN
def f z lj = { w = z + lj
In w,w} ;
was 0, and l contained 1, 2, and 3, then the result
m would be a list of partial sums: 1, 3, and 6, and
the result zN would be the sum 6.
z
Simultaneous mapping and right-associative
reduction
A. Standard identi ers
typeof map_foldr~list =
(*1->*0->(*2,*0)) ->
*0
->
(list *1)
-> (list *2,*0);
Example:
map_foldr~list f z l
returns (m,z0), where:
m0,z0 = f l0 z1
m1,z1 = f l1 z2
...
mN,zN = f lN z
, ..., lN are the elements of the list l, and m0, ...,
mN are the elements of the list m.
For example, if f was
43
Subset test
typeof subset? =
(*0 -> *0 -> bool) ->
(list *0)
->
(list *0)
-> bool;
Set equality test
typeof set_equal? =
(*0 -> *0 -> bool) ->
(list *0)
->
(list *0)
-> bool;
l0
A.8 Arrays
In the following, we describe families of functions,
for 1D arrays, 2D arrays, etc. We describe the entire
family
using the \nD" meta-syntax. In addition, the
z was 0, and l contained 1, 2, and 3, then the result m
substring
1D array can always be replaced by array
would be a list of partial sums (from back to front):
or vector, and the substring 2D array can always be
6, 5, and 3, and the result z0 would be the sum 6.
replaced by matrix.
We refer to a sequence of indices for an array by
its endpoints \first" and \last", meaning n-tuples
A.7 Lists as Sets
containing the lower bounds and upper bounds, respectively,
along all dimensions, and stepping the
All these functions require, as their rst parameter,
an equality function between elements of the sets. rightmost index fastest.
def f lj z = { w = z + lj
In w,w} ;
Conversion from list to set
Removes duplicates:
typeof settify =
(*0 -> *0 -> bool) ->
(list *0)
-> (list *0);
Membership test
typeof member? =
(*0 -> *0 ->bool) ->
*0
->
(list *0)
-> B;
Index bounds
typeof bounds~nD_array =
(ND_array *0) -> ((int,int),...,(int,int));
Synonyms:
bounds~1D_array
bounds~2D_array
bounds~vector
bounds~matrix
bounds~array
Array component selection
typeof select~nD_array =
(nD_array *0) -> (int,...,int) -> *0;
Union, intersection, di erence
Create k arrays, given lling function
typeof union =
(*0 -> *0 -> bool)
(list *0)
(list *0)
typeof intersection
(*0 -> *0 -> bool)
(list *0)
(list *0)
typeof difference =
(*0 -> *0 -> bool)
(list *0)
(list *0)
typeof make_k_nD_arrays =
((int,int),...,(int,int))
->
((int,...,int)->(*1,...,*k)) ->
(nD_array *0,
... ,
nD_array *k);
->
->
-> (list *0);
=
->
->
-> (list *0);
->
->
-> (list *0);
Example:
make_k_nD_arrays b f
returns k arrays a1,...,ak with bounds b, such that
if
44
A. Standard identi ers
Tree-reduction
f (j1,...,jN) == (v1,...,vk)
then
typeof fold~nD_array =
(*0 -> *1 -> *0) ->
*0
->
(nD_array *1)
-> *0;
ai[j1,...,jN] == vi
Synonyms:
n
=1
k
=1
make array
make vector
make matrix
make nD array
k >
1
make k arrays
make k vectors
make k matrices
Example:
fold~nD_array f z a
Equality of arrays
reduces the array to a value by rst computing the
foldls of all the innermost vectors (rightmost index
varying), then the foldls of those results with the
next innermost index varying, and so on. fold ...
has more parallelism than foldl ... and foldr ....
typeof eq~nD_array =
(*0 -> *0 -> bool) ->
(nD_array *0)
->
(nD_array *0)
-> bool;
typeof map_foldl~nD_array =
(*0->*1->(*0,*2)) ->
*0
->
(array *1)
-> (*0,array *2);
=2
n 1
n
Given predicate to compare equality of ele- Simultaneous mapping and left-associative rements:
duction
Map function over array
typeof map~nD_array =
(*0 -> *1)
->
(nD_array *0) -> (nD_array *1);
Example:
map~nD_array f a
returns an array with same bounds as array a, containing (f a[j]) at each index j.
Left-associative reduction
typeof foldl~nD_array =
(*0 -> *1 -> *0) ->
*0
->
(nD_array *1)
-> *0;
Example:
foldl~nD_array f z a
returns:
f (f ... (f z a[first]) ... ) a[last]
Right-associative reduction
typeof foldr~nD_array =
(*0 -> *1 -> *1) ->
*1
->
(nD_array *0)
-> *1;
Example:
foldr~nD_array f z a
returns:
f a[first] ( ... (f a[last] z))
Example:
map_foldl~nD_array f z a
returns (zLast,b), where
bounds as array a, and
b
is an array with same
zFirst, b[first] = f z
a[first]
zSecond,b[second] = f zFirst
a[second]
...
zLast, b[last]
= f zLastButOne a[last]
For example, if f was
def f z aj = { w = z + aj
In w,w} ;
was 0, and a was a vector containing 1, 2 and 3,
then the result b would be a vector of partial sums:
1, 3 and 6, and the result zLast would be the sum 6.
z
Simultaneous mapping and right-associative
reduction
typeof map_foldr~nD_array =
(*1->*0->(*2,*0)) ->
*0
->
(array *1)
-> (array *2,*0);
Example:
map_foldr~nD_array f z a
returns (b,zFirst), where b is an array with same
bounds as array a, and
b[first], zFirst = f a[first] zSecond
b[second],zSecond = f a[second] zThird
...
b[last], zLast
= f a[last]
z
A. Standard identi ers
45
For example, if f was
A.10 M-structure arrays
def f z aj = { w = z + aj
In w,w} ;
M-array allocators
typeof nD_M_array =
was 0, and a was a vector containing 1, 2 and 3, ((int,int),...,(int,int)) ->
then the result b would be a vector of partial sums
(from last to rst): 6, 5 and 3, and the result zFirst Synonyms for 1D M array:
M vector
M array
would be the sum 6.
Synonym for 2D M array:
z
(nD_M_array *0);
M matrix
A.9 I-structure arrays
I-array allocators
typeof nD_I_array =
((int,int),...,(int,int)) -> (nD_I_array *0);
Synonyms for 1D I array:
I vector
M-array index bounds
typeof bounds~nD_M_array =
(nD_M_array *0) -> ((int,int),...,(int,int));
M-array component selection
typeof take~nD_M_array =
(nD_M_array *0) -> (int,...,int) -> *0;
I array
Synonym for 2D I array:
I matrix
I-array index bounds
A.11 Object identity
typeof same? = *0 -> *0 -> bool;
typeof bounds~nD_I_array =
(nD_I_array *0) -> ((int,int),...,(int,int));
I-array component selection
A.12 Delayed Evaluation
typeof select~nD_I_array =
(nD_I_array *0) -> (int,...,int) -> *0;
typeof force = (delay *0) -> *0;
Fill rectangular region of k I-arrays given lling function
A.13 Input/Output
typeof fill~k_nD_I_arrays =
((int,int),...,(int,int))
->
((int,...,int) -> (*1,...,*k))
->
(nD_I_array *0, ... , nD_I_array *k) -> void;
Example:
fill~k_nD_I_arrays r f (a1,...,ak)
lls region r of I-arrays a1,...,ak such that if
f (j1,...,jN) == (v1,...,vk)
then
ai[j1,...,jN] == vi
The following is a temporary library of input/output
types and procedures. This will be replaced by a new
I/O library after we have more experience with this
one.
For synchronization of concurrent I/O operations,
every procedure takes an extra \trigger" argument
and returns an extra \signal" result, both of type
f status. The procedures are all strict in the trigger
argument, i.e., they do not attempt any I/O until it is available. Further, the procedures do not
return the signal result until they have \done" the
I/O. Thus, an application can perform I/O operations in a particular order by threading an f status
46
token through all of them. An application can perform I/O operations in a non-deterministic order by
choosing not to thread this argument through them.
In each of the procedures, the result f status indicates how the i/o operation went (ok, end-of- le,
or error).
I/O types
A. Standard identi ers
The trigger argument is used for sequentialization.
By threading the f status result of the last i/o operation into the trigger of fclose, the programmer can
ensure that the i/o operations on the stream have
been completed before it is closed. If the stream was
an output stream into a string, the remainder of the
string is padded with null characters.
Positioning
There is a built-in type called fstream.
The following type is used to test whether an I/O When an I/O stream is opened, it is initially positioned at the rst character, i.e., the next character
operation succeeded or not.
to be read is the rst one. The position may be
type f_status = F_ok | F_err | F_end ;
moved in front of the j 'th character using the function:
Opening I/O streams
Access modes for opening les:
type access_mode = For_Read
| For_Write
| For_Append ;
Opening an I/O stream on a le:
typeof fopen = string ->
access_mode ->
(fstream,f_status) ;
The string argument is the le name.
Opening an input stream on a string:
typeof sopen_in = string ->
(fstream, f_status) ;
typeof fseek = fstream ->
int ->
f_status ->
f_status ;
The desired position j is supplied as the integer argument. A status of F eof is returned if j is beyond
the end of the stream.
The current position of an i/o stream may be
queried using the function:
typeof fposition = fstream ->
f_status ->
(int,f_status) ;
Input
The string argument is treated as the \input le" for
the stream.
The following functions read (parse) a character, an
integer,
a oat and a string, respectively, from a
Opening an output stream to a string:
stream of characters:
typeof sopen_out = int ->
(fstream,f_status,string) ;
The integer argument speci es the desired length of
the string. The string is returned as the third component of the result tuple, while the stream that writes
into the string is returned as the third component.
Because of non-strictness, the string is returned immediately, but is empty. As output operations on
the stream are performed, the string is lled up.
Closing I/O streams
typeof fclose = fstream ->
f_status ->
f_status ;
typeof fscan_char
= fstream ->
f_status ->
(char,f_status) ;
typeof fscan_int
= fstream ->
f_status ->
(int,f_status) ;
typeof fscan_float = fstream ->
f_status ->
(float,f_status) ;
typeof fscan_string = fstream ->
f_status ->
(string,f_status) ;
In each case, the rst component of the result 2-tuple
is the value that was read, and is meaningful only if
the result f status is F ok.
A. Standard identi ers
For fscan char, a status of F end is returned if no
characters remain in the stream.
For fscan string, a status of F end is returned if
no characters remain in the stream. If any characters remain, the input is consumed upto and including the next newline, if any, or the end of the
stream, otherwise. The consumed characters, minus
the trailing newline, are returned in the result string.
For fscan int, leading whitespace characters are
skipped (spaces, tabs, newlines). Then, a status
of F end is returned if no characters remain in the
stream. Otherwise, it scans an integer:
47
For fprint int, a leading sign is printed only if the
number is negative.
For fprint float, a leading sign is printed only
if the number is negative. The number of digits of
mantissa printed is unspeci ed.
The following function prints out a newline:
typeof fprint_nl
= fstream ->
f_status ->
f_status ;
Formatted I/O
Formatted input involves parsing numbers and
strings
from an input stream of characters, and for[+/-] [whitespace] digit+
matted output involves writing numbers and strings
to
For fscan float, leading whitespace characters are an output stream of characters, according to a list
skipped (spaces, tabs, newlines). Then, a status of format directives.
of F end is returned if no characters remain in the Items to be read or written are placed in a list
stream. Otherwise, it scans a oat:
PRINT ITEM objects:
[+/-] [whitespace] digit+ [ . digit* ]
The following function reads the next character
without consuming it:
typeof fpeek_char
= fstream ->
f_status ->
(char,f_status) ;
Output
type PRINT_ITEM =
|
|
|
|
Pri int
Prf float
Prs string
Prc char
Prnl ;
These are for integers, oats, strings, characters
and newlines, respectively. A possible extension in
the future is to have additional disjuncts with eld
width, centering and padding speci cations.
Formatted output
The following functions print a character, an integer,
a oat and a string, respectively, into a stream of
characters:
typeof fprintf = fstream ->
(list PRINT_ITEM) ->
f_status ->
f_status ;
typeof fprint_char
Example: Suppose i and x evaluate to 23 and 6.847,
respectively. The statement:
= fstream ->
char ->
f_status ->
f_status ;
typeof fprint_int
= fstream ->
int ->
f_status ->
f_status ;
typeof fprint_float = fstream ->
float ->
f_status ->
f_status ;
typeof fprint_string = fstream ->
string ->
f_status ->
f_status ;
stat = fprintf ( Prs "i = "
: Pri i
: Prs ", x = "
: Prf x
: Prnl
: Prs "Voila!"
: Prnl
: Nil )
trig ;
produces output that looks like this:
i = 23, x = 6.847
Voila!
48
A. Standard identi ers
Formatted input
typeof
The desired scanning (parsing) of the input is speci ed in a list of SCAN ITEM objects:
typeof
type SCAN_ITEM =
|
|
|
typeof
Sci
Scf
Scs
Scc
These are for integers, oats, strings and characters,
respectively. A possible extension in the future is to
have additional disjuncts with eld width, matching,
termination and skipping speci cations.
Formatted input is performed by the following
function:
typeof fscanf = fstream ->
(list SCAN_ITEM) ->
f_status ->
(list PRINT_ITEM, f_status) ;
The input is scanned according to the SCAN ITEM list,
and the results are returned in a PRINT ITEM list.
Example: the statement:
typeof
typeof
typeof
typeof
scan_float
= f_status ->
(float,f_status) ;
scan_string = f_status ->
(string,f_status) ;
print_char
= char ->
f_status ->
f_status ;
print_int
= int ->
f_status ->
f_status ;
print_float = float ->
f_status ->
f_status ;
print_string = string ->
f_status ->
f_status ;
print_nl
= f_status ->
f_status ;
typeof scanf
= (list SCAN_ITEM) ->
f_status ->
(list PRINT_ITEM,f_status) ;
typeof printf = (list PRINT_ITEM) ->
f_status ->
f_status ;
items, stat = fscanf file1 (Sci:Scf:Nil) trig ;
scans an integer and a oating point number from
the stream, and returns a list of two PRINT ITEMs, the
components of which can be accessed by the patternbinding statement:
A.14 Storage Management
The following storage management procedures are
very
they are calls to storage manager
This binds the numbers that were read to j and x, that dangerous|
permit
deallocation
and reuse of heap objects
respectively.
instead of relying on general garbage collection. If
the programmer is not careful, programs that use
these procedures can fail in bizarre ways.
Standard input and output
There are three standard streams, usually connected tor:Return a heap object to the storage allocato the terminal:
(Pri j:Prf x:Nil) = items ;
typeof stdin = fstream;
typeof stdout = fstream;
typeof stderr = fstream;
For each of the functions for I/O to streams, there
is a corresponding function for I/O to stdin and
stdout, respectively, by omitting the leading \f" in
the function name and omitting the fstream argument:
typeof
scan_char
typeof
scan_int
= f_status ->
(char,f_status) ;
= f_status ->
(int,f_status) ;
typeof dealloc = *0 -> void ;
If the argument is not a heap object (e.g., it is a number), no action is performed. Note: this only deallocates the object corresponding directly to the argument; it does not transitively deallocate any other
objects to which this object may point. The void result is returned only after the deallocation has been
completed.
Clear a heap object so that all its slots are once
again empty:
typeof clear = *0 -> *0 ;
B. Standard identi ers/Overloaded identi ers
If the argument is not a heap object (e.g., it is a
number), no action is performed. Note: this only
clears the object corresponding directly to the argument; it does not transitively clear any other objects
to which this object may point. As a result of this
clearing, of course, all previous contents of this object are lost. The result is a pointer to the same
object, and is returned only after the clearing has
been completed.
Copy a heap object completely:
typeof copy = *0 -> *0 ;
49
B List of overloaded operators
and identi ers
In almost all cases, the types of the instances of an
overloaded operator or identi er have some common
structure. Thus, to abbreviate the listings below,
for each overloaded operator or identi er, we show a
general type scheme using meta-variable , and then
we list all the instantiations of .
For example, the entry:
T
T
max:
If the argument is not a heap object (e.g., it is a num- typeof max~ = -> -> ;
ber), no action is performed. Note: this only copies
the object corresponding directly to the argument; it where T = int float
does not transitively copy any other objects to which indicates that the overloaded identi er max stands
this object may point. The result is a pointer to the for the two non-overloaded identi ers:
new object, and is returned as soon as it is allocated. typeof max~int = int -> int -> int;
The procedure reads the old object using I-fetches. typeof max~float = float -> float -> float;
T
T
T
T
B.1 Overloaded operators
Unary pre x -:
typeof negate~T =
T
->
T;
where T = int float
Binary in x +, - and *:
typeof plus~T =
typeof minus~T =
typeof times~T =
T
T
T
->
->
->
T
T
T
->
->
->
T;
T;
T;
where T = int float
Binary in x == and <>:
typeof eq~T =
typeof ne~T =
T
T
->
->
T
T
-> bool;
-> bool;
where T = int float char
Binary in x <, <=, > and >=:
typeof
typeof
typeof
typeof
lt~T
le~T
gt~T
ge~T
=
=
=
=
T
T
T
T
where T = int
->
->
->
->
T
T
T
T
->
->
->
->
bool string symbol
bool;
bool;
bool;
bool;
float char string
B.2 Overloaded identi ers
Overloaded identi ers are listed below in alphabetic
order.
abs:
50
B. Overloaded identi ers
typeof abs~T =
->
T
where T = int
T;
typeof hash~T = int ->
where T = string
float
bounds:
length:
typeof bounds~T = (T *0) -> (int,int);
typeof length~T =
where T = 1D array
1D I array 1D M array
typeof bounds~T =
(T *0) -> ((int,int),...,(int,int));
where T = nD array
for all n > 1
nD I array nD M array
conc:
typeof conc~T =
->
T
where T = string
T
->
T;
(list *0)
->
T
where T = int
T
-> bool;
float char bool string symbol
typeof eq~T =
(*0 -> *0 -> bool) ->
(T *0)
->
(T *0)
-> bool;
where T = list
nD array
fill:
typeof fill~k_nD_arrays =
((int,int),...,(int,int))
->
((int,...,int) -> (*1,...,*k))
->
(nD_I_array *0, ... , nD_I_array *k) -> void;
where T = nD I array
for all k 1, n 1
foldl:
typeof foldl~T =
(*0 -> *1 -> *0) ->
*0
->
(T *1)
-> *0;
where T = list
for all n 1
nD array
list
map:
typeof map~string =
(char -> char) -> string -> string;
typeof map~list =
(*0->*1) -> (list *0) -> (list *1);
typeof map~nD_array =
(*0->*1) -> (nD_array *0) -> (nD_array *1);
for all n 1
typeof foldr~T =
(*0 -> *1 -> *1) ->
*1
->
(T *0)
-> *1;
where T = list
for all n 1
typeof map_foldl~T =
(*0->*1-> (*0,*2)) ->
*0
->
(T *1)
-> (*0,list *2);
where T = list
for all n 1
nD array
map foldr:
typeof map_foldr~T =
(*1->*0->(*2,*0)) ->
*0
->
(T *1)
-> (list *2, *0);
where T = list
for all n 1
nD array
max:
typeof max~T =
T
where T = int
->
T
->
T;
->
T;
float
min:
typeof min~T =
T
where T = int
->
T
float
nth:
foldr:
hash:
-> int;
map foldl:
eq:
typeof eq~T =
-> int;
symbol
T
where T = string
T
nD array
typeof nth~string = int -> string -> char;
typeof nth~list
= int -> (list *0) -> *0;
select:
typeof select~T = (T *0) -> int -> *0;
where T = nD array
for all n 1
to uc:
nD I array
C. Overloaded identi ers/Compatibility
typeof to_uc~T =
where T = char
T
->
T;
string
to lc
typeof to_lc~T =
where T = char
T
->
T;
string
B.3 Overloaded array notations
Functional and I-structure array selection expressions:
A[i]
are overloaded to work on:
(nD_array *0)
(nD_I_array *0)
for n = 1, 2, ...
M-structure array selection expressions:
A![i]
A!![i]
C Incompatible Changes
C.1 Changes from Id 90.0 to Id 90.1
Reserved words
The following are now reserved words:
instance
instances
M_array
M_matrix
M_vector
record
sequential
The following families are now reserved words:
k nD
M arrays
M vectors
k M arrays
k M matrices
nD M array
k
are overloaded to work on:
The following are no longer reserved words:
(nD_M_array *0)
assign
error
put
for n = 1, 2, ...
I-structure array assignment statements:
A[i] = v;
are overloaded to work on:
(nD_I_array *0)
for n = 1, 2, ...
M-structure array assignment statements:
A![i] = v;
A!![i] = v;
are overloaded to work on:
(nD_M_array *0)
for n = 1, 2, ...
51
Char, String, Symbol notations
We have abandoned Common Lisp notation and
switched completely to ANSI C notation for character and string constants. The use of single quotes
for character constants also necessitated a change in
the notation for symbols.
Failing patterns in comprehensions
When a pattern fails in a generator in a list or array comprehension, a runtime error occurs. Previously, this was not speci ed. Also, this di ers from
the convention in some other functional languages
where failing patterns are silently dropped (i.e., failing patterns are used as lters).
M-array allocator names
The M-array allocators have been renamed to:
52
mk_m_array
mk_m_vector
mk_m_matrix
mk_nD_m_array
because of a con ict with the reserved words:
m_array
m_vector
m_matrix
nD_m_array
C. Compatibility
Numeric types
The single numeric type N has been replaced with two
separate types int and float. The Id 88.x manual
had indicated that this was likely to happen.
Various operators and identi ers are now overloaded to work on both integers and oats.
I-structure and M-structure eld declaration Identi ers
In algebraic types, I-structure and M-structure elds The identi er \?" consisting of only a question
are signalled by \." and \!", respectively. Previ- mark is no longer treated specially.
ously, they were signalled by \!" and \!!", respectively.
Character and String constants
M-structure assignment and selection nota- Character and string constants now follow the contion
vention in the C programming language instead of
M-structure assignment and selection now use \!" Common Lisp.
explicitly, e.g.,
Escape sequences are available in character and
string
constants, following the convention in the C
A![j] = A![j] + 1;
programming language.
B!age = B!age + 1;
whereas previously they had the same notation as
for functional data structures and I-structures.
Symbols
Storage management pragmas
The following storage management pragmas have
been removed:
@release
@circulate
Symbols now begin with a backslash, instead of a
single quote.
Lists
The standard procedures in Appendix A.14 take The lexical token \!" is no longer an operator. The
their place. These are used in conjunction with bar- standard function nth~list is now available instead
riers to achieve the same e ect.
for indexing lists.
C.2 Changes from Id 88.x to Id 90.0
Overloading
There is now a clear position on overloading, and it is
not as ambitious as originally expected. Only builtin operators and identi ers are overloaded. The
type-checker must be able to resolve overloading locally. If it cannot, the programmer must assist the
type checker with explicit type declarations or by
using a non-overloaded identi er instead.
Equality and inequality
The operators \==" and \<>" are now overloaded
only on a few primitive types (they no longer work
on lists, arrays, tuples or other algebraic types). The
overloaded identi er eq works for the primitive types
as well as for lists and arrays. The standard identiers eq~list and eq~array are available for list and
array equality. The programmer must write equality
functions for other types.
C. Compatibility
53
Patterns
Comprehension notation
Floating point constants are no longer allowed in
patterns.
The don't care pattern \ " consisting of a single
underscore has taken on additional meaning. For
M-structure components of an algebraic type, it also
means that no take operation is to be performed on
that component.
We now use semicolons (;) instead of ampersands
(&) to separate generators in list and array comprehensions. Ampersand is no longer a lexeme.
In array comprehensions and accumulator comprehensions, bounds expressions are now followed by the
keyword \of", bringing it more in line with the notation for case expressions.
In accumulators, in accumulation clauses, we use
the notation:
The lexical token \ "
In patterns, the \don't care" pattern \ " now has additional meaning. For M-structure components of an
algebraic type, it also means that no take operation
is to be performed on that component.
In expressions, \ " no longer stands for the void
value (use \()" instead). In constructor terms for
algebraic types, it is used to indicate that no value
is to be stored into the corresponding I-structure or
M-structure component of the object.
[eis] = evs || gen ; ... ; gen
instead of
eis gets evs || gen ; ... ; gen
Accordingly, gets is no longer a reserved word.
C.3 Changes from Id Noveau to Id 88.x
Function de nitions (see Section 2.31) are now always introduced by the def keyword. Previously,
function de nitions at the top-level had the keyword,
whereas function de nitions inside blocks did not.
Void
The terms array, vector, matrix, k nD arrays, etc.
The type void now has a distinguished constant \()" are now keywords introducing array comprehensions
representing the only value in that type. It can be (see Section 2.34.5).
used in patterns. The previous \ " notation for void
We are now serious about type-checking. Unless
values is no longer available.
you explicitly disable it, every program must now
pass the type-checker. Some existing programs will
Call statements
now be rejected by the type-checker. Typically, such
programs violate the restriction that all components
The statement form:
of a list and all components of an array must be homogeneously
typed. This restriction was mentioned
call e
in the Id Nouveau document, but was not enforced
is no longer available. Use this instead:
by the compiler.
_ = e
For-loop syntax has changed (generalized). Instead of:
Standard identi ers
for j from e1 to e2 by eInc do
In accordance with our new convention for system- we now say:
atically relating overloaded identi ers to the corre- for j <- e do
sponding non-overloaded ones, the names of certain where e is any list expression. The phrase:
standard functions have changed. Examples:
e1 to e2 by eInc
New
Old
is now a full- edged expression (i.e., it can be used
bounds~nD_array
nD bounds
anywhere), and denotes a list containing the arithbounds~nD_I_array nD bounds
metic series from e1 through e2 with eInc increment.
map~list
map list
54
References
[1] Arvind, K. P. Gostelow, and W. Plou e.
An Asynchronous Programming Language and
Computing Machine. Technical Report 114a, Department of Information and Computer Science,
University of California, Irvine, CA, December
1978.
[2] R. S. Nikhil. Id Nouveau Reference Manual, Part
I: Syntax. Technical report, Computation Structures Group, MIT Lab. for Computer Science,
545 Technology Square, Cambridge, MA 02139,
April 1987.
[3] R. S. Nikhil. Id (Version 88.1) Reference Manual. Technical Report CSG Memo 284, MIT Laboratory for Computer Science, 545 Technology
Square, Cambridge, MA 02139, August 1988.
[4] R. S. Nikhil and Arvind. Id/83s. Technical
report, MIT Laboratory for Computer Science,
Cambridge, MA 02139, July 1985. (Prepared for
MIT Subject 6.83s).
[5] R. S. Nikhil and Arvind. Programming in Id: a
parallel programming language. 1990. (book in
preparation).
[6] R. S. Nikhil, K. K. Pingali, and Arvind. Id Nouveau. Technical Report CSG Memo 265, MIT
Laboratory for Computer Science, Cambridge,
MA 02139, July 23 1986. (Prepared for MIT
Subject 6.83s).
LATEX'ed on August 11, 1994
C. References
Source Exif Data:
File Type : PDF File Type Extension : pdf MIME Type : application/pdf PDF Version : 1.3 Linearized : No Page Count : 60 Producer : ESP Ghostscript 815.02 Create Date : 2007:11:08 07:13:51 Modify Date : 2007:11:08 07:13:51EXIF Metadata provided by EXIF.tools