Development blog 2020

A complication with traits

So I set up a type system with general type inference and parametric polymorphism. One can already state such code:

function map[X,Y](a: List[X], f: X->Y): List[Y]
   let b = []
   for x in a
      b.push(f(x))
   end
   return b
end

let a = map(list(1..10), |x| 2*x)
print(a)

Or this:

let compose = |g,f| |x| g(f(x))
let add = |x,y| x+y
let h = compose(|x| add(x,1), |x| add(x,1))
print(h(0))

The type inference algorithm deduces:

compose: (Int->Int,Int->Int)->Int->Int
add: (Int,Int)->Int
h: Int->Int

One can also state compose in polymorphic fashion:

function compose[X,Y,Z](g: Y->Z, f: X->Y): X->Z
   return |x| g(f(x))
end

Currently, there is no notion of mutability, because firstly this introduces a subtype relation and secondly I don't know whether it should become a first class feature of the type system or not. The type system and type checker will become more complex, one has to work out what the best algorithms would be.

Of course, reassignable variables are introduced with another syntax – var – instead of let. That's not the same as mutability, although both concepts are slightly intertwined in Rust.

Regarding parametric polymorphism with type variables restricted by traits, a further complication emerges. Let's have a look at this code:

function pow[T: Mul+One](x: T, n: Int): T
   var y = T.one
   for k in 1..n
      y = y*x
   end
   return y
end

print(pow(2,10))

Here, pow needs the type T at runtime, because it occurs explicitly in T.one. One could obtain it through x, but in general this is not feasible — for example, one cannot simply obtain the element type of list, because the list could be empty, and an empty list does not know its element type at runtime.

The best approach would be to give the type as an additional argument. The resulting code at runtime would be:

# impl One for Int
Int.one = 1

function pow(x,n,T)
   y = T.one
   for k in 1..n
      y = y*x
   end
   return y
end

print(pow(2,10,Int))

This means, the ABI of a polymorphic function type would depend one the standalone occurrence of the type. Thus one must take care, this information is not erased during unification. It would be easier if the type argument is given explicitly for every type variable restricted by a trait.

Generic map

Say we would like to code the generic map function. A first consideration would be:

List.zero = || []
Map.zero = || {}
List.plus = fn|x| self.push(x); self end
Map.plus = fn|x| self.add(x); self end

map = |a,f| a.reduce(a.zero(), |b,x| b.plus(f(x)))

Now two problems arise. Firstly, there is monkey patching. Secondly, in Moss there is no separate type for sets. The above code will work for lists and sets, but not for maps.

A cleaner solution:

class Set = {}

MapTrait = {}
MapTrait[List] = table{
   zero = || [],
   plus = fn|a,x| a.push(x); a end,
   iter = iter
}
MapTrait[Set] = table{
   zero = || {},
   plus = fn|s,x| s.add(x); s end,
   iter = iter
}
MapTrait[Map] = table{
   zero = || {},
   plus = fn|m,[k,v]| m[k] = v; m end,
   iter = |m| m.items()
}

function map(T,a,f)
   M = MapTrait[T]
   M.iter(a).reduce(M.zero(), |b,x| M.plus(b,f(x)))
end

print(map(List,[1,2,3,4],|x| 2*x))
print(map(Set,{1,2,3,4},|x| 2*x))
print(map(Map,{x=1,y=2},|[k,v]| [k,2*v]))

Would sets and maps have a different type, a simplification would be allowed:

MapTrait = {}
MapTrait[List] = table{
   zero = || [],
   plus = fn|a,x| a.push(x); a end
}
MapTrait[Set] = table{
   zero = || {},
   plus = fn|s,x| s.add(x); s end
}
MapTrait[Map] = table{
   zero = || set{},
   plus = fn|m,[k,v]| m[k] = v; m end
}

function map(a,f)
   M = MapTrait[type(a)]
   a.reduce(M.zero(), |b,x| M.plus(b,f(x)))
end

print(map([1,2,3,4],|x| 2*x))
print(map(set{1,2,3,4},|x| 2*x))
print(map({x=1,y=2},|[k,v]| [k,2*v]))

One may ask whether unification of map and set was a mistake. Anyway, the specific tasks may accomplished by iterator comprehensions, which are more general in certain ways.

print(list(2*x for x in [1,2,3,4]))
print(set(2*x for x in {1,2,3,4}))
print(map([k,2*v] for k,v in {x=1,y=2}.items()))

The right semantics of orbit

Until now f.orbit(x) was defined like this:

function orbit(f,x)
   return fn||
      y = x
      x = f(x)
      return y
   end
end

This is actually wrong semantics. Say we have a function next_perm(a), which returns the next permutation of a list a with regard to lexicographical order, but works in-place and thus modifies a itself. We would like to generate all the permutations of an ordered list this way:

permutations = |a| next_perm.orbit(a).take(fac(len(a)))

print(permutations([0,1,2]).map(copy).list())

As one can see, orbit will eat up the first permutation by calling f = next_perm once before returning y. A second indication for the wrong semantics is that f is called once more than necessary. The right behavior is

function orbit(f,x)
   first = true
   return fn||
      if first
         first = false
      else
         x = f(x)
      end
      return x
   end
end

or equivalently

function orbit(f,x)
   return fn*||
      yield x
      x = f(x)
   end
end

Development blog 2020

Table of contents

A complication with traits

Generic map

The right semantics of orbit