Previous Up Next

Chapter 4  The Standard Library

4.1  General Purpose Exceptions and Functions

The following exceptions are defined: General functions are:

4.2  Lists



The exception:
exception Nth


is defined. It is raised whenever it is attempted to access an element outside of a list. Recall that lists are defined by the datatype declaration:

datatype 'a list = nil | :: of 'a * 'a list


:: : 'a * 'a list -> 'a list is the list constructor, and is declared infix, right associative of precedence 5.

4.3  Sets and Maps



Exceptions related to sets and maps are: Functions on sets and maps are: There is now an alternative data type for maps in HimML, the table type. This implements imperative maps: unlike the map type, objects of type table are updated in a destructive way, just like hash-tables. Objects of type table, which we shall just call tables, are not really faster than using applicative references, but they put less stress on the sharing mechanism and the garbage collector of HimML, which may result in space and even time savings.

The type of tables mapping objects of type ''a to 'b is
type (''a, 'b) table
You can think as a kind of equivalent of the type (''a -m> 'b) ref. Associated functions are:

4.4  Refs and Arrays



Refs and arrays are the fundamental mutable data structures of HimML, as in Standard ML of New Jersey (only refs exist in the definition of Standard ML). Ref and array types always admit equality, even if their argument types do not. Equality is decided according to the following rules: In short, refs and arrays are not shared, and are compared by their addresses1.

Some syntax extensions are defined to allow you to write a more readable code to handle arrays. In particular: There is however no similar syntactic sugar for non-polymorphic integer arrays (of type intarray), only for polymorphic arrays (of type 'a array, for any 'a).

The following exception is defined:
exception Subscript


It is raised when accessing an element outside of an array, by sub or update, or by isub or iupdate.

The following functions are provided:

4.5  Strings



Strings are ordered sequences of characters (we call size of the string the length of the sequence). ML does not provide a type of characters, though one-character strings may serve this purpose. Strings are assumed coded according to the 7-bit ASCII standard. However, characters are usually 8 bits wide: the characters of code greater than 127 are interpreted in a system-dependent fashion. The string length is encoded separately from the sequence of characters that composes it: no special character is reserved to represent the end of a string, in particular, any string may contain the NUL character (\000).

The following exceptions are defined: The functions are:

4.6  Integer Arithmetic

HimML integers are machine integers, that is, integers in the range [min_int,max_int], and are represented with nbits bits.

Exceptions on integer operations can be: Non-negative integers are 0, 1, 2, ..., 42, ...Negative integers are written with the ~ negation operator in front.

The following operations are defined. Basic operations like +, -, etc. are not overloaded as in Standard ML. For example, + is always an integer function. For analogous numerical (floating-point) functions, see Section 4.7. For example, floating-point addition is #+, not +.

4.7  Numerical Operations

The real and imaginary parts of numbers are floating-point numbers, which are classified according to the IEEE754 standard. A floating-point number may be: The fact that an infinity or a Nan is produced (in IEEE754 systems), or an Arith exception is raised (in non-IEEE754 systems) by a computation means usually that the computation is wrong. In this case, the exception system is better suited to find numerical bugs, provided we have a means of locating the place where the exception is raised.

However, in production code, these error conditions may still crop up for limit situations. It is then unacceptable for code to stop functioning because of this: so infinities and NaNs should be used. In general, users had better use a system obeying the IEEE754 standard (or its successors). The IEEE754 standard defines trapping mechanisms to be used for debugging numerical codes; they are not used in HimML now, but may be in a future version of the debugger.

Classification of numbers is accomplished with the auxiliary types:
datatype numClass = MNaN of int | MInf | MNormal | MDenormal
   | Zero | PDenormal | PNormal | PInf | PNaN of int


numClass encodes both the class and the sign of a real number. In the case of a NaN, the NaN code is also provided as an integer. NaN codes are system-dependent; only NaN codes from 1 to 7 are recognized in HimML; unrecognized codes are represented by 0. NaN codes and the constructors MNaN, MInf, MDenormal, PDenormal, PInf, PNan are never used in a non-IEE754 system. The exception:
exception Arith


is raised for all arithmetical errors in non-IEEE754 systems, and is never used in IEEE754 systems.

On a different subject, remember that testing complex numbers for equality is hazardous. Therefore, = is not to be used lightly on numbers (for example, 0.2 * 5 may print as 1 but differ from 1 internally). Normally, though, computations on sufficiently small integers should be exact (at least on real IEEE754 systems). This warning applies not only to the explicit = equality function, but also to all operations that use internally the equality test, in particular the test for being inside a set inset or the application of a map to an object ?, when this object contains numbers.

Moreover, following the principle, valid in HimML, that an object is always equal to itself, +inf = +inf, ~inf = ~inf, and all NaNs are equal to themselves, though they are incomparable with any number (for example, +NAN(0) <= +NAN(0) is false, but +NAN(0) = +NAN(0) is true).

Numerical constants are entered and printed in HimML as x or x:y, where x and y represent real numbers, possibly followed by a scale. The notation x:y denotes the complex number x+i.y. There can be no confusion with the : character used in type constraints, because no type may begin with a character lying at the start of a number. A real number is defined by the regular expression (in lex syntax):
{INT}E{INT}
{INT}\.{DIG}+
{INT}\.{DIG}+E{INT}
[+~]inf
[+~]NAN\([0-7]\)

where DIG = [0-9] and INT = (\~?{DIG}+), with the obvious interpretations. Infinities and NaNs cannot be entered in a non-IEEE754 system.

The exception:

exception Complex


is raised whenever an operation defined only on real values is applied on a complex with a non-zero imaginary part (even if it is denormalized).

The numerical functions are:

4.8  Large Integer Arithmetic

HimML includes a port of Arjen Lenstra's large integer package, which provides arbitrary precision arithmetic, i.e., arithmetic over a type Int that represents actual integers, without any size limitation as with the int type.

The exception:
exception Lip of int
is raised whenever an error occurs in any of the functions of this section. The numbers as arguments to the Lip exception are as follows: The functions are classified into several subgroups.

Conversions

Large Integer Arithmetic

Bit Manipulation



Large integers also serve as bit vectors, of varying size. Every non-negative integer represents a finite set of bits, those that are set in the binary representation of the integer; while every negative integer represents a cofinite set of bits (i.e., a set of bits whose complementary is finite), those that are set in the two's complement binary representation of the integer. For example, 23 is … 00010111 in binary, and represents the set {0, 1, 2, 4}, since 23 = 24 + 22 + 21 + 20. And −23 is … 11101001, and represents the set {0, 3, 5, 6, 7, …}.

Euclidean Algorithms

Standard Modular Arithmetic

Montgomery Modular Arithmetic



Modular multiplications can be done division free and therefore somewhat faster (about 20%), if the Montgomery representation is used [10]. Converting to and from Montgomery representation takes one Montgomery multiplication each, so it only pays to use Montgomery representation if many multiplications have to be carried out modulo a fixed odd modulus.

To use Montgomery arithmetic, first initialize the modulus N by using zmontstart, and convert all operands to their Montgomery representation by ztom, but do not convert exponents. Use the addition, subtraction, multiplication, squaring, division, inversion, and exponentiation functions, which all start with zmont, below on the converted operands, just as you would use the ordinary modular functions (starting with zm). The results can be converted back from Montgomery representation to ordinary numbers modulo N using zmonttoz.

Primes, Factoring

4.9  Input/Output



Two types are defined, first that of output streams outstream:

type 'rest outstream = |[put:string -> unit,... : 'rest]|

means that output streams are extensible records (classes) with at least a put method, to output a string to the stream. For example, to make a stream that prints to a string stored inside a ref sr:string ref:

|[put = fn text => (sr := !sr ^ text)]|

The type of input streams instream is:

type 'rest instream : |[get:int -> string,... : 'rest]|

providing at least a get method, that reads up to n characters from the stream, n being the number in argument. If less than n characters have been read, it usually means that an end of stream has been reached. (After the end of stream is reached, repeated calls to get will return the empty string.) For example, an input stream reading from a string s:string, with current position stored in a ref posr:num ref is:
|[get = fn n => let val goal = !posr+n
                    val newpos = (if goal<size s
                                     then goal
                                  else size s)
                in
                   substr(s,!posr,newpos)
                   before (posr := newpos)
                end]|
Note that if you want to read from a string, the instring primitive does this faster.

The following exception is defined:

exception IO of int

is raised when the system was unable to open a file or any other I/O-related operation; it returns as argument the error code returned by the operating system. (Note that this is OS-dependent.)

The other methods that may be present in predefined streams are: The input/output values and functions are:

4.10  Miscellaneous

Interesting values are:
1
Actually, all objects in HimML are compared by their addresses, because any two equal objects are located at the same address.

Previous Up Next