Appendix: Benchmark Sources

A1.1 Nfib Napier88 Source

rec let nfib = proc( n:int -> int )
    if n < 2 then 1 else 1 + nfib( n-1 ) + nfib( n-2 )

A1.2 Quicksort Napier88 Source

let partition = proc( A : *int; l,r : int -> int )
begin
     let k = ( l + r ) div 2
     let al = A( l ) ; let ar = A( r ) ; let ak = A( k )
     let t = case true of
     al < ar :
          if ak < al then al else
          if ak < ar then { A( k ) := al ; ak }
                     else { A( r ) := al ; ar }
     ak < ar : { A( r ) := al ; ar }
     ak < al : { A( k ) := al ; ak }
     default : al

     let v := l ; r := r + 1
     let notdone := true
     while notdone do
     begin
          repeat l := l + 1 while l < r and A( l ) < t
          if l = r then notdone := false else
          begin
               repeat r := r - 1
               while l < r and t < A( r )
               if l = r then notdone := false else
               begin
                    A( v ) := A( r ) ; A( r ) := A( l )
                    v := l
               end
          end
     end
     l := l - 1
     A( v ) := A( l ) ; A( l ) := t
     l
end

rec let quicksort = proc( A : *int ; l,r : int )
while l < r do
begin
     let k = partition( A,l,r )
     if k - l > r - k
          then { quicksort( A,k + 1,r ) ; r := k - 1 }
          else { quicksort( A,l,k - 1 ) ; l := k + 1 }
end