Advanced topics

Stringbuffers

In Moss strings are immutable. That means, after construction, a string cannot be modified. Therefore one cannot append a string s2 to a string s1. To bypass this problem one could write s1=s1+s2. But this sparks off another problem. To understand this we should have a look on the following statement:

s = s1+s2+s3+s4+s5+s6

All additions except the last require the construction of a temporary string that will be deleted after the next addition. This results in a huge amount of memory allocations and memory displacements. And the memory to displace gets longer and longer. The following program unveils the full painfullness of this approach.

n = 1000
s = ""
for i in 1..n
  s = s+"."
end

We may increase n to 10000 or 100000 and measure how long it takes. A better method is to use the method join that glues strings together:

s = [s1,s2,s3,s4,s5,s6].join()

Now one can use a list as a buffer.

a = []
for i in 1..n
  a.push(".")
end
s = a.join()

Memoisation

We can directly obtain an implementation from the recursive definition of the Fibonacci-squence:

fib = |n| 1 if n==1 or n==2 else fib(n-1)+fib(n-2)

If n increases by one, the number of needed calls to fib is multiplied by a factor of two. Ok, let N be this number of needed calls. Then we have

N(n+1) = 2N(n).

Mathematics says, the solution of this equation is N(n)=c+2^n. That c is some uninteresting constant. If t is the amount of time a call would take, the computer spends t*N(n) for the computation.

But fib is so simple, it is obvious, that the computation should take only N(n)=c+n calls.

The following memoizing fixed point combinator achieves this.

function fix(F)
  m = {}
  return fn g|n|
    if n not in m then m[n] = F(g,n) end
    return m[n]
  end
end

fib = fix(|f,n| 1 if n==1 or n==2 else f(n-1)+f(n-2))

Unique

Uniq(ue) is an operation that removes duplicates from a list. Sets and maps provide a simple way to state this operation. The first way to achieve unique is to convert the list into a set and then back into a list.

# (1)
uniq = |a| list(set(a))

If two non-equal elements have a different string representation, we can use a map construction instead of a set construction.

# (2)
uniq = |a| list(map(a.map(|x| [str(x),x])).values())

What should be equal and what not, may be abstracted by a projection function p:

uniq = |a,p| list(map(a.map(|x| [p(x),x])).values())

The last one is very general, with uniq(a,|x| x) equivalent to (1) and uniq(a,str) equivalent to (2).

Floating point numbers need a version of unique that takes a desired precision:

uniq = |a,prec| list(map(a.map(|x| [int(x/prec),x])).values())

Multiple dispatch

Here is a basic implementation of multiple dispatch in Moss. At first, some auxiliary functionality is to be defined.

dtab = {}

function define(m,d)
  if m not in dtab
    dtab[m] = d
  else
    dtab[m].update(d)
  end
end

method = {
  2: fn|m|
    f = dtab[m]
    return |x,y| f[[type(x),type(y)]](x,y)
  end
}

So far, dtab is thought to contain a dispatch table for each method name.

Now we can specify a multimethod:

Str = String

define("f",{
  [Int,Int]: |x,y| "({},{}) [Int,Int]"%[x,y],
  [Str,Str]: |x,y| "({},{}) [Str,Str]"%[x,y],
  [Int,Str]: |x,y| "({},{}) [Int,Str]"%[x,y],
  [Str,Int]: |x,y| "({},{}) [Str,Int]"%[x,y]
})

f = method[2]("f")

print(f(1,2))
print(f("x","y"))
print(f(1,"y"))
print(f("x",2))

# Output:
# (1,2) [Int,Int]
# (x,y) [Str,Str]
# (1,y) [Int,Str]
# (x,2) [Str,Int]