Share your Programming Language Jam submissions here!

← Back to all posts
PFC - A purely functional language with control flow
takanuva (2)

PFC - A purely functional language with control flow

A simple interpreter may be found here.

Team:

The run button will run a few exemple programs in the tests/ directory.

Control flow, single assignment and free monads

Functional languages, specially purely functional ones, tend to disallow arbitrary control flow such as breaks and early returns. This restriction is not necessary: it's possible to use the SSA algorithm to turn statements with control flow, including goto, into lambda terms.

We propose a purely functional programming language, such as Haskell, but with an imperative look-and-feel. Por example, consider the following code:

var fact(var n) {
  var sum = 1;
  for(var i = n; i > 0; i = i - 1) {
    sum = sum * i;
  }
  return sum;
}

This code (included in the tests), though it makes use of a for loop and local mutability, is still purely functional. Execution works by translating the program into an equivalent lambda term and evaluating it through a small-step operational semantics.

This opens a new programming style for functional programmers, allowing one to write monadic code in a more natural way.

For imperative programmers, a new style of programming is also present, by introducing algebraic effects on the language. Algebraic effects are a subset of monads (common in functional languages) that freely compose, and allow several structures such as concurrency, exception handling, generators and ambiguity to be implemented as libraries inside of the language, such as it's done in the Koka programming language.

For example, it's possible to write a handler for exceptional control flow:

handler catch() {
  case raise(): {
    return "exception";
  }
}

var safediv(var a, var b) {
  if(b < 1) {
    raise();
  }
  return a / b;
}

var main() {
  return catch([] {
    return safediv(10, 0);
  });
}

This file (also present in the tests) gives a lambda expression (whose syntax was borrowed from C++) to a handler, which intercepts the exceptional call and aborts the computation.

Roadmap

  • Due to time constraints, continue, break and switch are not properly working. It's already possible to write code using for, while, do-while and goto, though.

  • Switch statements should support pattern matching on algebraic data types (ADTs), which are not implemented yet. This include support for arrays.

  • Static type checking: though this is missing due to time constraints, a standard Hindley-Milner algorithm with effect rows is capable of inferring types for programs in the language. Arrow types are annotated by the effects they run upon evaluation (i.e., all actions are monadic).

  • Arbitrary monads: though algebraic effects freely compose, users may want to write monadic code, while freely enjoying control flow, for an arbitrary monad. This should be possible by introducing a (!) join operator. For example, programmers familiar to Haskell should comprehend the following example:

    var foo() {
      var x = ![10, 20, 30];
      var y = ![40, 50, 60];
    
      return x + y;
    }

    The join operator suggests that the action is monadic, representing here a binding operation. This function, for example, would have type () -> list int, working in the list monad.