CS412/413 Spring 2001 Introduction to Compilers

Iota Language Sample Programs

You are strongly encouraged to write your own sample programs, however here are a few to get you started.


Iota Standard Library Interfaces

The basis of the Iota Standard Library contains certain useful operations that cannot be expressed in Iota itself. Here we provide the interfaces files for those functions. An actual implementation of the standard library will be made available later.

Example Programs


Job Scheduling

schedule.im:

/* scheduling: find the smallest time that all the jobs can be completed using 2 identical machines */

uses io.printi

schedule(a: array[int], sum:int) : int = (
    opt: int = sum/2;

    if (opt * 2 < sum) opt = opt + 1;
    
    while (opt < (sum + 1)) (
	if (subset_sum(a, opt, 0)) return opt;
	opt = opt + 1
    );
    -1
)

subset_sum(a: array[int], sum: int, index:int) : bool = (
    nextInd: int = index + 1;
    if (sum == 0) 
	return true;
    if (sum < 0)
	return false;
    if (index == length(a)) 
	return false;
    subset_sum(a, sum-a[index], nextInd) | subset_sum(a, sum, nextInd)
)

sums(a:array[int]) : int = (
    count:int = 0;
    sum:int = 0;
    while (count < length(a)) (
	sum = sum + a[count];
	count = count + 1
    );
    sum
)

main(args:array[string]): int = (
    a: array[int] = new int[17](0);
    count: int = 0;
    value: int = 10;
    //initialize the jobs
    while (count < 17) (
	a[count] = value;
	value = value + 10;
	count = count + 1
    );
    sum: int = sums(a);
    //least total amt of time needed to complete all jobs
    d: int = schedule(a, sum);
    printi(d);
    0
)
Back to top

Making Change

coins.im:


// given a set of coins(with an infinite supply of each type of coins)
// and an amount, check if there is an exact change

uses io.print, io.printi, io.readln, conv.stoi

change(amount: int, coins: array[int],
    a: array[int], flag: bool, pos: int): bool = (
    times: int;
    count: int = 0;
    nextpos: int = pos + 1;

    if (amount == 0)
	return true;
    if (amount < 0) (
	return false
    );
    if (amount > 0 & pos == length(a)) (
	return false;
    );
    times = amount / coins[pos];
    while (count < times + 1) (
	flag = change(amount-count*coins[pos],coins,a,flag, nextpos);
	if (flag) (
	    a[pos] = count;
	    return flag
	);      
	count = count + 1
    );
    false
)

main(args:array[string]): int = (
    Ncoins: int = 5;
    coins: array[int] = new int[Ncoins](0);
    //one entry for each different kind of coin that could be used
    coins[0] = 5; coins[1] = 7; coins[2] = 10;
    coins[3] = 20; coins[4] = 30;
    
    flag: bool = true;
    pos: int = 0;
    //output array
    a: array[int] = new int[Ncoins](0);
    print("How much do you want change for? ");
    amount:int = stoi(readln(),0);
    flag = change(amount, coins, a, flag, pos);     
    if (flag) (
	print("Here is the change!\N"); 
	i:int = 0;
	while (i < length a) (
	    printi(a[i]); print(" * ");
	    printi(coins[i]); print("\N");
	    i = i + 1
	)
    ) else
	    print("no change!");
    0;
)
Back to top

N Queens

Nqueens.im:

/* a program to solve the N-queens problem */

uses io.print

printboard(col: array[int], N: int) = (
    i: int = 0;
    j: int = 0;

    while (i < N) (
	j = 0;
	while (j < N) (
	    print((if (col[i] == j) " 0" else " ."));
	    j = j + 1;
	);
	print("\N");
	i = i + 1;
    );
    print("\N");
)

try(c:int, row:array[int], col:array[int],
    diag1:array[int], diag2:array[int]) =
(
    N: int = length col;
    r: int = 0;
    
    if (c == N) (
	printboard(col, N);
    ) else (
	while (r < N) (
	    if (row[r] == 0 &
		diag1[r+c]== 0 &
		diag2[r+(N-1)-c]== 0) (
		    row[r] = 1;
		    diag1[r+c] = 1;
		    diag2[r+(N-1)-c] = 1;
		    col[c] = r;
		    try(c+1, row, col, diag1, diag2);
		    row[r] = 0;
		    diag1[r+c] = 0;
		    diag2[r+(N-1)-c] = 0;
	    );
	    r = r + 1;
	)
    )
)

main(args: array[string]): int = (
    N: int = 4;
    row: array[int] = new int[N](0);
    col: array[int] = new int[N](0);
    diag1: array[int] = new int[N+N-1](0);
    diag2: array[int] = new int[N+N-1](0);
    try(0, row, col, diag1, diag2);
    0
)
Back to top

Merge Sort

This program consists of three files, the interface and implementation for a merge sort, and a test program that uses that module.

merge.ii:

/* A merge-sort implementation */
merge(A: array[int]) : array[int]

merge.im:

/*
 * merge takes an unsorted array A and sorts it by recursively
 * dividing the array into 3 arrays.
 */


merge(A: array[int]) : array[int] = (
    len: int = length A;
    if (len < 2) return A;
    l: int = len/3;
    if (l * 3 < len) l = l + 1;
    r: int = len - 2 * l;

    // construct the 3 arrays
    a: array[int] = new int[l](0);
    b: array[int] = new int[l](0);
    c: array[int] = new int[r](0);
    count: int = 0;
    while (count < l) (
	a[count] = A[count];
	count = count + 1
    );
    count = 0;
    while (count < l) (
	b[count] = A[count+l];
	count = count + 1;
    );
    count = 0;      
    while (count < r) (
	c[count] = A[count+2*l];
	count = count + 1
    );
    mergeThree(merge(a),merge(b),merge(c));
)

mergeThree(a:array[int], b: array[int], c:array[int]) : array[int] = (
    d: array[int] = new int[length a + length b + length c](0);
    ap: int = 0;
    bp: int = 0;
    cp: int = 0;
    dp: int = 0;
    
    while ((ap < length(a) & bp < length(b))
	    & cp < length(c)) (
	s: int = smallest(a[ap], b[bp], c[cp]);
	if (a[ap] == s) (
	    d[dp]=a[ap];
	    dp = dp + 1;
	    ap = ap + 1
	) else (
	    if (b[bp] == s) (
		d[dp] = b[bp];
		dp = dp + 1;
		bp = bp + 1
	    ) else (
		d[dp] = c[cp];
		dp = dp + 1;
		cp = cp + 1;
	    )
	)
    );

    while ((ap < length(a)) & (bp < length(b))) (
	if (a[ap] < b[bp]) (
	    d[dp] = a[ap];
	    dp = dp + 1;
	    ap = ap + 1
	) else (
	    d[dp] = b[bp];
	    dp = dp + 1;
	    bp = bp + 1
	);
    );
    
    while ((bp < length(b)) & (cp < length(c))) (
	if (b[bp] < c[cp]) (
	    d[dp] = b[bp];
	    dp = dp + 1;
	    bp = bp + 1
	) else (
	    d[dp] = c[cp];
	    dp = dp + 1;
	    cp = cp + 1;
	)
    );
    
    while ((ap < length(a)) & (cp < length(c))) (
	if (a[ap] < c[cp]) (
	    d[dp] = a[ap];
	    dp = dp + 1;
	    ap = ap + 1
	) else (
	    d[dp] = c[cp];
	    dp = dp + 1;
	    cp = cp + 1;
	)
    );

    // 2 of the following 3 loops will fall through 

    while (ap < length a) (
	d[dp] = a[ap];
	dp = dp + 1;
	ap = ap + 1
    );
    while (bp < length b) (
	d[dp] = b[bp];
	dp = dp + 1;
	bp = bp + 1;
    );
    while (cp < length c) (
	d[dp] = c[cp];
	dp = dp + 1;
	cp = cp + 1;
    );
    d;
)

smallest (a:int, b:int, c:int) : int = (
    if (b < a)
	if (c < b) c
	else b
    else
	if (c < a) c
	else a
)

mergetest.im:

uses io.print, io.printi, merge.merge

main(args:array[string]): int = (
    c: array[int] = new int[24](0);
    count: int = 10;
    index: int = 0;

    while (index < 8) (
	c[index] = count;
	count = count + 10;
	index = index + 1;
    );

    count = 25;
    index = 8;
    while (index < 16) (
	c[index] = count;
	count = count + 5;
	index = index + 1
    );
    
    c[16] = 11; c[17] = 38; c[18] = 41; c[19] = 44;
    c[20] = 59; c[21] = 68; c[22] = 75; c[23] = 81;
    
    d: array[int] = merge(c);
    
    count = 0;
    while (count < length(d)) (
	print("d[");
	printi(count);
	print("] = ");
	printi(d[count]);
	print("\N");
	count = count + 1;
    );
    0
)
Back to top