Final Project Write-up, Part 3: Supported Features

1. The Domain

Our algorithm for auto-parallelization can be applied on general programs written in a modified version of the 164 language we developed in the previous project. This is ideal for divide and conquer algorithms like mergesort. Although the language only allows mutation for primitives and does not make functions first-class, the constructs the language provides for operating on strings, lists, and matrices still make it versatile.

2. Programming Model

We sought to pursue a language model that is as powerful as it can be while being simple enough to allow auto-parallelization to be feasible. Thus, our language follows the structured and functional programming paradigms.

However, functions in the language are not entirely functional: commands such as input and print statements are other ways functions can receive input and produce output. (This is the reason why functions in our language cannot be first-class.) In such cases, they must be treated as if they are themselves commands. In particular, the order of commands cannot be rearranged. To determine if a function should be treated as commands, all functions are global like in C and must be declared before any other program statements. Functions can thus be placed in a namespace separate from that of variables as it is done in Logo.

Besides basic control structures such as if- and while-statements, our language allows operations on strings and lists (called deques as in C++). Since deques can be nested deeply, they can be thought of as matrices, so our language allows for matrix and element-wise operations. Strings and deques can be concatenated using the addition operator and can be split using the slice operator as in Python. This is how strings and deques are operated on in the absence of mutation for them.

3. Example Programs

Five dependencies:

def x = 0
if (true) {
____def y = x
____x = 1
____y
}
print x
print "end"



Fibonacci:

# fibonacci

def fib(n){
____if (n < 3) {
________1
____} else {
________def a = fib(n-1)
________def b = fib(n-2)
________a + b
____}
}

def first = fib(1)
def second = fib(2)
def third = fib(11)

print first
print second
print third



Mergesort:

# merge sort

def merge(list1, list2) {
____if (len(list2) == 0) {
________list1
____} else if (len(list1) == 0) {
________list2
____} else if (list2[0] < list1[0]) {
________[list2[0]] + merge(list1, list2[1:])
____} else {
________[list1[0]] + merge(list1[1:], list2)
____}
}

def mergesort(the_list) {
____def length = len(the_list)
____if (length <= 1) {
________the_list
____} else if (length == 2) {
________def first = the_list[0]
________def second = the_list[1]
________if (second < first) {
____________[second, first]
________} else {
____________[first, second]
________}
____} else {
________# recursively call the program
________def mid_index = int(len(the_list) / 2)
________def a = mergesort(the_list[:mid_index])
________def b = mergesort(the_list[mid_index:])
________merge(a, b)
____}
}

def test1 = [4,6,5,8,9,3,1,7,10,2]
print mergesort(test1)

def test2 = [6,2,4,5,1,8,3,10,9,7]
print mergesort(test2)

def test3 = [5,8,3,1,4,9,6,2,10,7]
print mergesort(test3)