Fun Data + Algo

Week 3 Programming

Topics

Introduction to Som language
Programming
iterative
recursive
Abstract Data Type

----------------

Case: Write a program to insert numbers into a list.
      Show how to program in two styles: iterative and recursive.

note : The program text is displayed in Courier face

A list stores a variable number of items. Each item stores a number. A list can grow.
A data item has two slots:
first keeps a number
second keeps a link (to other data item)

A pool of storage is defined as an array. Three global variables are defined:
storage[], free, end.

storage[] --> newitem --> a data item

storage = array 1000
free = 1
end = 1000

These are functions to access a data item:

to setnum a b = storage[a] = b
to setlink a b = storage[a+1] = b
to getnum a = storage[a]
to getlink a = storage[a+1]
to notnull p = p != 0
to isnull p = p == 0

They are called "abstract data type". The actual details how the data is kept is shielded from users of these functions.
Now we write a function to create a new data item:

// create a new data item stored a number n
to newitem n | a =
if free >= end
    error "no more memory"
a = free
free = free + 2
setnum a n
setlink a 0
a              // return a new data item

The function "newitem n" creates a data item that stored "n". It returns a "handle" (or pointer) to this new item.
A list is a linked data item. It has a "head" node which is used as a place holder of the list. A list can be empty, which is signified by a header that has
a null link.

to newlist = newitem 0    // create an empty list, return a handle to its header

Now we can manipulate the list. First we insert numbers into the list.

to insert a k =    // insert an item "a" into the list "k"
setlink a (getlink k)
setlink k a

Now we can try using our program to make a list of numbers: 2,3,5,7.

to makelist | k a =
k = newlist      // make an empty list
a = newitem 2    // make a new node storing 2
insert a k
insert (newitem 3) k
insert (newitem 5) k
insert (newitem 7) k
k                // return the list

The first program that manipulate this list is a program to print out the items in the list. It uses loop to print each item. The first one is special as it is the header node.

to printlist k | p =
p = getlink k    // get the list
while notnull p
    print (getnum p) space
    p = getlink p      // get to the next item
nl

Now try to run it.

to testlist | k =
k = makelist
printlist k

The second version of printlist uses recursion. It strips the header node out and uses a recursive print to walk into the list.

to printlistrec2 k = {}   // forwardly define

to printlistrec k =
printlistrec2 (getlink k) nl

to printlistrec2 k =
if notnull k
    print (getnum k) space
    printlistrec2 (getlink k)

Some function must be "forwardly" defined so that the compiler knows about its type and arity. This occurs naturally in recursive programs, such as "printlistrec2".

To show you more examples of iterative vs recursive style, we will write a program to count the length of a list. It is similar to "printlist", ie. strip the head then walk into the list. First version is an iterative one.

to listlen k | c p =
c = 0
p = getlink k    // strip the head
while notnull p
    c = c + 1
    p = getlink p // next item
c

Now the recursive style, it reads as follows. There are two cases of the length of a list, either it is empty, therefore its length is 0, or, it is not empty then its length is 1 + the length of the rest of the list.

to listlenrec k =
listlenrec2 (getlink k)

to listlenrec2 k =
if isnull k
    0
else
    1 + (listlenrec2 (getlink k))

Instead of using 1 + ... (rest), one can use an "accumulator" (variable) to keep the resulting sum so that the last line of a recursive function will be only the recursive call (this helps a compiler to improve the efficiency of the running code). In this case, "c" is used to "accumulate" the length.

Now it reads, first, call "listlenreca2" with an initial sum of 0. In "listlenreca2", if the list is empty, it is at the end of a list, returns c. In other case, walk into the list while incrementing c.

to listlenreca k =
listlenreca2 (getlink k) 0

to listlenreca2 k c =
if isnull k
    c
else
    listlenreca2 (getlink k) (c+1)

Don't forget to put the "forwardly define" recursive function into your working code.

End

19 Jan 2010