Recursive thought

06-13-2006, 06:08 PM

The notion behind this tutorial is not to teach you Jass. It is to make you a better programmer by teaching you one of the fundamentals of computer science. There are often times we come across situations where we would like to generalize a method. We often do this to make our code easier to read, and to make it more compact. Consider this:

JASS:

constant function Factorial5 takes nothing returns integer
return 120
endfunction

This is an absolutely correct value for 5!, but it isn’t very flexible. We’d like to be able to be able to get not just 5 factorial, but any number factorial we so desire. First we need to define the domain and co-domain of the function.
What is the domain of factorial?
Any natural number.
What is the codomain of factorial?
Any natural number.

So now that we know that how might we define factorial?
We could say a mapping

Code:

Factorial (0)=1
Factorial (1)=1
Factorial (2)=2
Factorial (3)=6
Factorial (4)=24
…

You might laugh, but this is actually an excellent method when you know the operation you are about to perform is very expensive, and the range of values limited. If you know you only want the first 5 factorials you could store them in cache, rather then compute it manually. Most older 3d games use to store arctan values since video cards couldn’t handle it. It’s a generally mantra that memory is cheap, but clock cycle aren’t. You can often get a function which use to run in polynomial time to run in constant time, by simply memorizing its map. You can even though that on the fly, so that in the worst case its o(n), but in the average case its constant. This is not what this tutorial is about.
Let’s think of a recursive algorithm for factorial. A recursive definition for x is x described in terms of x. An old joke goes that the first step to understanding recursion is to understand recursion.
Factorial is a recursively defined function. This makes it easy on us.

Code:

Factorial (0)=1
Factorial (n)=n* Factorial (n-1)

How do we implement that in jass?

JASS:

constant function Factorial takes integer n returns integer
    if(n==0)then
        return 1
    endif
    return n*Factorial(n-1)
endfunction

Unfortunately, Jass isn’t tail form recursive. We will need to translate this to using a loop.

JASS:

constant function Factorial takes integer n returns integer
    local integer product=1
    loop
        exitwhen n==0
        set product=n*product
        set n=n-1
    endloop
    return product
endfunction

Sorry, this isn’t very interesting. It’s apparently an unwritten rule that when your talking about recursion you must demonstration factorial. Similar to when demonstrating proof by contradiction you must prove that square root of 2 isn’t rational. We’d like to do more interesting applications.
What is a pair?
A pair is a data structure with two parts, a car, and a cdr. Car is the first entry, the cdr is the second.
How do we build pairs?
Using cons. Cons takes two values car and cdr
How do we get the car?
Using car
How do we get the cdr?
Using cdr
Aren’t these silly questions?
Absolutely.

What is a list?
A list is either nil , or a value cons to a list.

As you can see a list is a recursive structure, this is very good. This is a tutorial on recursion, so this will be our main structural tool.

What are the functions for dealing with a list in jass?
I’m not going to give you any, because they aren’t why we are using lists. I’ll give you their signatures, but note that there is no builtin handle known as a list. Value can be anything, you can change it to the specification of the example. Note that it must be consistent. So you can have a list of integers, and a list of lists, but you can’t have a list of integers and lists.

JASS:

global list nil

function cons takes value car, list cdr returns list

function car takes list l returns value

function cdr takes list l returns list

function IsNull takes list l returns boolean

When writing a list we will be using the curly braces in this tutorial. {} is nil, {x,y} is the list which contains the element x and y. {x::y}, is the list whose car is x, and whose cdr is y.
Let us say we’d like to add up all the integers in the list l.
How would we define ListAdd?
If the list is nil, there is nothing so we return 0, other wise we get the value of the car, and then apply our ListAdd to the cdr.

Code:

ListAdd {}=0
ListAdd {cons::cdr}=car+ListAdd(cdr)

That seems easy enough lets write it!

JASS:

function ListAdd takes list l returns integer
    local integer sum=0
    loop
        exitwhen IsNull(l)
        set sum=sum+car(l)
        set l=cdr(l)
    endloop
    return sum
endfunction

However, our list is hurt by the strong typing of Jass. We'd like to concretely define what a list is, but we'd still like it to be functional.
What if we say a list will be a location, and that all its values will be locations?
How do we store numbers in there?
Return bug?
Too uninteresting.
Why don't we build numbers?
Sure! But for our sanity, we will only consider the natural numbers
How do we build the natural numbers?
Using Peano arthimetic.
What? How?
We will need to build a zero, and a successor function.
Zero is zero
One is Suc(zero)
Two is Suc(Suc(zero))
Three is Suc(Suc(Suc(zero)))
...

Build?
Yes, using lists.
We could say that zero is nil.
And that one is the list which contains nil.
And two is the list that contains two nils.

Code:

zero={}
one={{}}
two={{},{}}
three={{},{},{}}
n={{}::n-1}

So our successor function is just consing on nil to a list.

JASS:

global location zero=nil
function suc takes location l returns location
    return cons(nil,l)
endfunction

function IsZero takes location l returns boolean
    return IsNull(l)
endfunction

The predecessor is a bit harder, but still easy.
Since we'd like to keep things closed we say the pred of 0 is 0, and the pred of n is n-1.

Code:

pred (0)=0
pred (n)=(n-1)

Since we use list its pretty simple. When its empty, we will return it, but other wise we will return it's cdr.

JASS:

function pred takes location l returns location
    if(IsNull(l))then
        return l
    endif
    return cdr(l)
endfunction

How do we do the add x and y in our new numbers?
we can apply suc x times to y.

JASS:

function add takes location x,location y returns location
    loop
        exitwhen IsNull(x)
        set y=suc(y)
        set x=pred(x)
    endloop
    return y
endfunction

What about subtracting y from x?
subtraction is just applying the pred function on x, y times, if y is greater then x it returns zero.

JASS:

function sub takes location x,location y returns location
    if(IsZero(x))then
        return zero
    loop
        exitwhen IsZero(y)
        set x=pred(x)
        set y=pred(y)
    endloop
    return x
endfunction

How's about the product of x and y?
We can keeping adding x to a new list y times. However, if x or y are zero, just return zero.

JASS:

function mul takes location x,location y returns location
    local location new=zero
    if(IsZero(x))then
        return new
    endif
    loop
        exitwhen IsZero(x)
        set new=add(x,new)
        set y=pred(y)
    endloop
    set x=new
    set new=null
    return x
endfunction

How can we tell if x and y are equal?
We can keep applying pred, until one is zero. If they both are zero then it must be that they are equal. Since we know that we can just test that if they are a warcraft 3 equality since we know zero is a constant.

JASS:

function eq takes location x, location y returns boolean
    loop
        exitwhen IsZero(x) or IsZero(y)
        set x=pred(x)
        set y=pred(y)
    endloop
    return x==y
endfunction

How can we if know x is greater then y?
Same as before, we keep applying pred until they return zero. If they equal its false, but if y returns first then it must be that x is greater.

JASS:

function gt takes location x,location y returns boolean
    if(eq(x,y))then
        return false
    endif
    loop
        exitwhen IsZero(x) or IsZero(y)
        set x=pred(x)
        set y=pred(y)
    endloop
    return IsZero(y)
endfunction

We can then build any of the functions we desire by using greater and equal.
For instance Les than is just

JASS:

function lt takes location x,location y returns boolean
    return not(eql(x,y) or gt(x,y))
endfunction

But what can we do with this?
We can try to sort the numbers in a list.
How?
Using mergesort.

What is mergesort?
Mergesort is a recursive algorithm that works great on lists, which is what we have.
We need three functions.
Split
Merge
Sort
When sort is called on a list, its splits the list in two, sorts the halves, and then merges them.

How do we split a list l?
We'd rather not get the length, and then counting half its element. That is too costly. Instead, we will build two lists left and right. We will cons (car l) to left, and
car(cdr (l)) to right, and repeat until l is exhausted. We will return a list with two elements left, and right.

Code:

split {}={{},{}}
split {a}={{a},{}}
split {x::y::s}=let xs=car(split(s))
                    let ys=car(cdr(split(s)))
                    {{x::xs},{y::ys}}

The psuedo code is starting to look more and more scary. But the jass version is pretty nice, even with all its syntatic salt.

JASS:

function Split takes location l returns location
    local location left=nil
    local location right=nil
    location res=nil
    loop
        if(IsNull(l))then
            set res=cons(right,res)
            set res=cons(left,res)
            return res
        elseif(IsNull(cdr(l)))then
            set left=cons(car(l),left)
            set res=cons(right,res)
            set res=cons(left,res)
            return res
        endif
        set left=cons( car(l),left)
        set right=cons( car(cdr(l)),right)
        set l=cdr(cdr(l))
    endloop
    return nil
endfunction

How would we merge list right and left?
We can say

Code:

merge left,nil=left
merge nil,right=right
merge {x::xs},{y::ys}=if(x<y)then {x::merge(xs,{y::ys})}
                      else {y::merge({x::xs},ys)}

That looks worse then it is.
let's write it recursively, since it'll be easier.

JASS:

function merge takes location left,location right returns location
    if(IsNull(left))then
        return right
    elseif(IsNull(right))then
        return left
    elseif(Lesser( car (left), car (right))then
        return cons( car (left), merge (cdr (left),right) )
    endif
        return cons( car (right),merge ( left,cdr(right) )
endfunction

Finally, how do we write sort?

Code:

sort {}={}
sort {a}={a}
sort l=let r=split(l)
       let x=sort(car(r))
       let y=sort(car(cdr(r)))
       merge(x,y)

Well that looks easy enough! Lets put it to code, recursively of course!

JASS:

function sort takes location l returns location
    location r
    if(IsNull(l) or IsNull(cdr(l)))then
        return l
    endif
    set r=split(l)
    return merge(sort(car(r)),sort(car(cdr(r)))))
endfunction

Wow, we did it! We wrote merge sort in Jass. For our own peano natural numbers.

But there are some more things we could insert a merge order. We have two choices on this matter
we can hardcode in a few set of orders we can sort in, or let the user provide his own sorting function. This is the way we will be doing it.

First we need to set up some ground rules. The function given has to be a boolexpr. It needs to take no parameters. IT will instead no to look for two globals LX, LY.
Let set up the interface.

JASS:

global location LX
global location LY
function EvalPred takes boolexpr b,location x, location y returns boolean
    local trigger t=CreateTrigger()
    local triggercondition tc=TriggerAddCondition(t,b)
    local boolean c
    set LX=x
    set LY=y
    set c= TriggerEvaluate(t)
    call TriggerRemoveCondition(t)
    call DestroyTrigger(t)
    set t=null
    set tc=null
    return c
endfunction

EvalPred puts the given values in the right place, and then evaluates then using the predicate function b.

Let's rewrite mergesort to now use a predicate p past to the function!

JASS:

    
function merge takes location left,location right,boolexpr p returns location
    if(IsNull(left))then
        return right
    elseif(IsNull(right))then
        return left
    elseif(EvalPred(p,car (left),car (right)))then
        return cons( car (left), merge (cdr (left),right,p) )
    endif
        return cons( car (right),merge ( left,cdr(right),p ) )
endfunction

JASS:

function sort takes location l,boolexpr p returns location
    location r
    if(IsNull(l) or IsNull(cdr(l)))then
        return l
    endif
    set r=split(l)
    return merge(sort(car(r),p),sort(car(cdr(r)),p),p)
endfunction

You see it was pretty easy. Now we have a very flexible mergesort, that can take any predicate. Thus we can sort in counting order like

JASS:

function LessCond takes nothing returns boolean
    return Lesser(LX,LY)
endfunction

Or we can do it backwards

JASS:

function GreatCond takes nothing returns boolean
    return Greater(LX,LY)
endfunction

Now how's about the definitions for car, cdr,cons, nil etc?
No, This is the fun part, write you own:P This should be the ultimate example of applying a recursive definition to paper.
In case you forgot

Code:

cons x,nil={x}
cons x,xs={x::xs}

car nil=error
car {x::xs}=x

cdr nil=error
cdr (x:;xs}=xs

IsNull nil=true
IsNull x=false

These are easy enough, they just require playing with the return bug, which is not what this tutorial is about.
I hope you enjoyed this.

For more on this style of thought, I would suggest to pick up
The Little Schemer
The Seasoned Schemer

Both are excellent texts in a simmilar Q&A format on a language known as scheme. However, much like my examples were using Jass just to make it applicable, they use scheme. It is not a text on scheme, it is just a text on recursion. Learn it, love it, use it.

06-15-2006, 02:10 AM	#2
Jazradel	Very nice tutorial. I got to the bit about Lists before I was overwhelmed with technical words I have no basis of understanding for. I'll continue to work through as I was planning on doing a similar sort of thing with less complex working.

06-16-2006, 03:44 AM

weaaddar

Here is a demo map with a function example of the mergesort, and an implementation of car,cdr,cons.

Attached Files

RecursiveThoughte.w3x (16.7 KB)

06-16-2006, 05:14 AM

PipeDream

After lots of testing on all the types I've found multiboards are suitable for pairs. You get two integers and a string so there's no difficulty with real return bugs and you can store some extra information in the string.
Here's a port of weaaddar's code with out function passing. Includes a toy mark/sweep garbage collector.

JASS:

globals
    multiboard udg_gclist
endglobals

//****************************************************************
//Predicates, accessors, mutators and the like
function HtoI takes handle h returns integer
    return h
    return 0
endfunction
function ItoMB takes integer i returns multiboard
    return i
    return null
endfunction

//Cdr is always a multiboard.  type field determines car
function MB_PAIR takes nothing returns string //Car is another multiboard
    return "P"
endfunction
function MB_INT takes nothing returns string //Car is an integer
    return "I"
endfunction
function MB_MARK takes nothing returns string
    return "B"
endfunction
function MB_NOMARK takes nothing returns string
    return "W"
endfunction
function MB_ACTIVE takes nothing returns string
    return "A"
endfunction
function MB_INACTIVE takes nothing returns string
    return "I"
endfunction

function mb_gettype takes multiboard mb returns string
    return SubString(MultiboardGetTitleText(mb),0,1)
endfunction
function mb_getmark takes multiboard mb returns string
    return SubString(MultiboardGetTitleText(mb),1,2)
endfunction
function mb_getactive takes multiboard mb returns string
    return SubString(MultiboardGetTitleText(mb),2,3)
endfunction

function mb_activate takes multiboard mb returns nothing //Could be optimized
    call MultiboardSetTitleText(mb,mb_gettype(mb)+mb_getmark(mb)+MB_ACTIVE())
endfunction
function mb_deactivate takes multiboard mb returns nothing //Could be optimized
    call MultiboardSetTitleText(mb,mb_gettype(mb)+mb_getmark(mb)+MB_INACTIVE())
endfunction
function mb_mark takes multiboard mb returns nothing //Could be optimized
    call MultiboardSetTitleText(mb,mb_gettype(mb)+MB_MARK()+mb_getactive(mb))
endfunction
function mb_unmark takes multiboard mb returns nothing //Could be optimized
    call MultiboardSetTitleText(mb,mb_gettype(mb)+MB_NOMARK()+mb_getactive(mb))
endfunction

function setcar takes multiboard mb, integer v returns nothing
    call MultiboardSetRowCount(mb,v)
endfunction
function setcdr takes multiboard mb, multiboard oCdr returns nothing
    call MultiboardSetColumnCount(mb,HtoI(oCdr))
endfunction
function car takes multiboard mb returns multiboard
    return MultiboardGetRowCount(mb)
    return null
endfunction
function cdr takes multiboard mb returns multiboard
    return MultiboardGetColumnCount(mb)
    return null
endfunction

function pairp takes multiboard mb returns boolean
    return mb_gettype(mb)==MB_PAIR()
endfunction
function activep takes multiboard mb returns boolean
    return mb_getactive(mb)==MB_ACTIVE()
endfunction
function markedp takes multiboard mb returns boolean
    return mb_getmark(mb)==MB_MARK()
endfunction
function nullp takes multiboard mb returns boolean
    return mb == null
endfunction

//*********************************************************************
//Use these functions if you want to manually manage memory

function mb_alloc takes string stype returns multiboard
    local integer mb = HtoI(CreateMultiboard())
    call MultiboardSetTitleText(ItoMB(mb),stype+MB_NOMARK()+MB_INACTIVE())
    return mb
    return null
endfunction
function mb_destroy takes multiboard mb returns nothing
    call DestroyMultiboard(mb)
endfunction
function mb_cons takes multiboard mbCar,multiboard mbCdr returns multiboard
    local multiboard mb = mb_alloc(MB_PAIR())
    local integer ret = HtoI(mb)
    call setcar(mb,HtoI(mbCar))
    call setcdr(mb,mbCdr)
    set mb = null
    return ret
    return null
endfunction

//****************************************************************
//Use these functions for automatic memory management

//car takes free list, cdr takes inuse list
function GC_init takes nothing returns nothing
    set udg_gclist = mb_cons(null,null)
endfunction

//If the free list is empty, creates a new multiboard
//If it's not, removes from freelist
//Puts on inuselist
function GC_alloc takes string stype returns multiboard
    local multiboard freelist = car(udg_gclist)
    local multiboard inuselist = cdr(udg_gclist)
    local multiboard oNew
    if(nullp(freelist)) then
        set oNew = mb_alloc(stype)
        call setcdr(udg_gclist,mb_cons(oNew,inuselist))
    else
        set oNew = car(freelist)
        call setcar(udg_gclist,HtoI(cdr(freelist)))    //Cut allocated node out of freelist
        call setcdr(freelist,inuselist)    //Inject allocated node into inuselist
        call setcdr(udg_gclist,freelist)
    endif
    set freelist = null
    set inuselist = null
    return oNew    //Don't have to null since we don't deallocate user pairs
endfunction

function GC_color takes multiboard mbObj returns nothing
    if(not (nullp(mbObj) or markedp(mbObj))) then
        call mb_mark(mbObj)
        if(pairp(mbObj)) then
            call GC_color(car(mbObj))    //Only pairs have an mb car
        endif
        call GC_color(cdr(mbObj))    //Every object has an mb cdr
    endif
endfunction

function GC_mark takes nothing returns nothing
    local multiboard list = cdr(udg_gclist)    //inuselist
    local multiboard entry
    local integer nactive = 0
    loop
        exitwhen list == null
        set entry = car(list)
        if(activep(entry)) then
            call GC_color(entry)
            set nactive = nactive + 1
        endif
        set list = cdr(list)
    endloop
//	call BJDebugMsg("GC mark: "+I2S(nactive)+" active.")
    set list = null
endfunction
//cdr(udg_gclist) -> inuselist
//car(udg_gclist) -> freelist
function GC_sweep takes nothing returns nothing    //Bit of a hack, since we abuse two different meanings of cdr
    local multiboard list = udg_gclist
    local multiboard next
    local multiboard afternext
    local integer freed = 0
    local integer notfreed = 0
    loop
        exitwhen nullp(list)
        set next = cdr(list)
        exitwhen nullp(next)    //Reuse the entry going from inuse list to freelist
        if(markedp(car(next))) then
            call mb_unmark(car(next))
            set notfreed = notfreed + 1
            set list = cdr(list)
        else
            set afternext = cdr(next)
            call setcdr(list,afternext)    //snip next out of the inuse list
            call setcdr(next,car(udg_gclist))    //push it on top of the free list
            call setcar(udg_gclist,HtoI(next))
            set freed = freed + 1
        endif
    endloop
    call BJDebugMsg("GC sweep: "+I2S(freed)+" freed, "+I2S(notfreed)+" still in use.")
    set list = null
endfunction

function GC_activate takes multiboard mb returns nothing
    call mb_activate(mb)
endfunction
function GC_deactivate takes multiboard mb returns nothing
    call mb_deactivate(mb)
endfunction

function GC_collect takes nothing returns nothing
    call GC_mark()
    call GC_sweep()
endfunction

function cons takes multiboard oCar, multiboard oCdr returns multiboard
    local multiboard oNew = GC_alloc(MB_PAIR())
    call setcar(oNew,HtoI(oCar))
    call setcdr(oNew,oCdr)
    return oNew
endfunction

//***********************************************************************
//Test code.  Weaaddar's peano numbers and merge sort
function zerop takes multiboard list returns boolean
    return nullp(list)
endfunction
function succ takes multiboard list returns multiboard
    return cons(null,list)
endfunction
function pred takes multiboard list returns multiboard
    if(nullp(list)) then
        return list
    else
        return cdr(list)
    endif
endfunction
function add takes multiboard x, multiboard y returns multiboard
    loop
        exitwhen nullp(x)
        set y = succ(y)
        set x = pred(x)
    endloop
    return y
endfunction
function eq takes multiboard x, multiboard y returns boolean
    loop
        exitwhen zerop(x) or zerop(y)
        set x = pred(x)
        set y = pred(y)
    endloop
    return x == y
endfunction
function greatereq takes multiboard x, multiboard y returns boolean
    loop
        exitwhen zerop(x) or zerop(y)
        set x = pred(x)
        set y = pred(y)
    endloop
    return zerop(y)
endfunction
function split takes multiboard list returns multiboard
    local multiboard left = null
    local multiboard right = null
    local multiboard res = null
    loop
        if(nullp(list)) then
            set res = cons(right,res)
            set res = cons(left,res)
            return res
        elseif(nullp(cdr(list))) then
            set left = cons(car(list),left)
            set res = cons(right,res)
            set res = cons(left,res)
            return res
        else
            set left = cons(car(list),left)
            set right = cons(car(cdr(list)),right)
            set list = cdr(cdr(list))
        endif
    endloop
    return null
endfunction

function merge takes multiboard left, multiboard right returns multiboard
    if(nullp(left)) then
        return right
    elseif(nullp(right)) then
        return left
    elseif(greatereq(car(left),car(right))) then
        return cons(car(left),merge(cdr(left),right))
    else
        return cons(car(right),merge(left,cdr(right)))
    endif
endfunction

function sort takes multiboard l returns multiboard
    local multiboard res
    if(nullp(l) or nullp(cdr(l))) then
        return l
    else
        set res = split(l)
        return merge(sort(car(res)),sort(car(cdr(res))))
    endif
endfunction

function printnum takes multiboard x returns nothing
    local integer i = 0
    loop
        exitwhen nullp(x)
        set x = cdr(x)
        set i = i + 1
    endloop
    call BJDebugMsg(I2S(i))
endfunction

function printlist takes multiboard l returns nothing
    loop
        exitwhen l == null
        call printnum(car(l))
        set l = cdr(l)
    endloop
endfunction

function testsort takes nothing returns multiboard
    local multiboard zero = null
    local multiboard one = cons(null,null)
    local multiboard two = add(one,one)
    local multiboard three = add(two,one)
    local multiboard four = add(three,one)
    local multiboard five = add(four,one)
    local multiboard l = cons(three,null)
    set l = cons(four,l)
    set l = cons(zero,l)
    set l = cons(two,l)
    set l = cons(one,l)
    set l = cons(five,l)
    return sort(l)
endfunction

function testgc takes nothing returns nothing
    local multiboard sorted
    set sorted = testsort()
    call GC_activate(sorted)
    call GC_collect()
    call printlist(sorted)
    call GC_deactivate(sorted)
    call GC_collect()
endfunction

One nice thing about it is that multiboards are recycled but never deallocated, so you don't need to set them to null.

Edit: Arrrrrgh. As much fun as this, it's useless. You can only get MB's to not allocate space if you run it during start up.

12-11-2006, 09:45 PM	#5
PandaMine	If you need more help understanding linked lists look at the wiki entry below http://en.wikipedia.org/wiki/Linked_list (i found it very helpful)