Friday, May 2, 2014

A snippet from my new programming language

In the last few days I'm thinking about a hypothetical programming language called MVL, which is short for "Manifestly typed Value-level Language" or maybe "Verbose ML".

Here's some example code in that language:

GENERIC(Type) RECORD Group(
  operation: FUNCTION(Type, Type): Type,
  inverse: FUNCTION(Type): Type,
  identity: Type
)

GENERIC(Type) RECORD Field(
  addition: Group(Type),
  multiplication: Group(Type)
)

GENERIC(Scalar, Vector) RECORD VectorSpace(
  scalars: Field(Scalar),
  vectors: Group(Vector),
  scale: FUNCTION(Vector, Scalar): Vector
)

(Yes, I know that multiplication is not a group. But we can throw exceptions on divide by zero, so it's close enough.)

The idea of "value-level programming" (which I got from of Gabriel Gonzalez) is to pass these records around as arguments to functions, instead of using something like OO interfaces, Haskell typeclasses or concepts in C++ templates. The resulting code is similar to Haskell after translating typeclasses to dictionaries. Since it's annoying to always pass the records around, I'm thinking of a system like Agda's instance arguments or Scala's implicit arguments to make it easier:

GENERIC(Type) FUNCTION power(
  x: Type,
  y: Integer,
  IMPLICIT group: Group(Type)
): Type
  IF y > 0
    RETURN group.operation(x, power(x, y - 1))
  ELSE IF y = 0
    RETURN group.identity
  ELSE
    RETURN group.inverse(power(x, -y))

FUNCTION floatMultiply(x: Float, y: Float): Float
  RETURN x * y

FUNCTION floatInverse(x: Float): Float
  RETURN 1 / x

VAR floatMultiplicationGroup: Group(Float) = (
  operation: floatMultiply,
  inverse: floatInverse,
  identity: 1.0
)

VAR x: Float = power(0.5, -2)
# Returns 4.0

When you call the "power" function, you don't need to explicitly pass the group as an argument, because it's marked as implicit and picked up from the closest surrounding scope. The top level call picks up the value of floatMultiplicationGroup, and the recursive calls pick up the value from the enclosing call. If there are multiple matches in the same scope, that's a compile-time error, and you should pass the value explicitly.

Now all that remains is to make that idea into a workable language :-)

No comments:

Post a Comment