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]

Call stack size

You might want to load a large array or map from a text file as a Moss program, for example to initialize a database. But then something like this happens:

> eval(str(list(1..10000)))
thread 'main' panicked at 'index out of bounds: the
len is 3997 but the index is 3997', src/vm.rs:3829:11
note: Run with `RUST_BACKTRACE=1` for a backtrace.

Whoops. We have produced a stack overflow of the object stack, a part of the internal call stack system.

The same happens if you try to call a recursive function, but the recursion depth is too high:

> f = |n| 0 if n==0 else 1+f(n-1)
> f(10000)
thread 'main' panicked at 'index out of bounds: the
len is 4000 but the index is 4000', src/vm.rs:3829:11
note: Run with `RUST_BACKTRACE=1` for a backtrace.

To solve this issue, at any point in a program, a subprogram can be run on a new object stack of greater size. There is a function call(n,main), with the purpose to run main on a new object stack of size n.

use sys: call

f = |n| 0 if n==0 else 1+f(n-1)

function main
   a = eval(str(list(1..10000)))
   print(f(10000))
end

call(100000,main)

Even in call(n,main) by sufficient n you might suffer a stack overflow of the actual machine stack, in case the recursion involves higher order functions built-in in the interpreter. To circumvent this, there is a module called sys.stackless. Loading this module replaces the built-in higher order functions with Moss code.