« Articles

(Don't Fear) The Lambda

Introducing a practical λ-based object-oriented programming language. By Nick Webster on July 27, 2023

The class as the definition of a unit of behaviour and state has become the de facto building block for many object-oriented languages like Java, C#, C++, and Ruby. However, classes have limitations with multiple inheritance and composability. Fearless is a new programming language that unifies functional and object-oriented programming using "multi-lambdas". A multi-lambda (referred to simply as a "lambda" from now on) are lambdas that take an initial method name argument, allowing the lambdas to encode multiple functions. Like in pure lambda calculus, all values in Fearless are lambdas, including numbers and strings. However, thanks to having methods and dynamic dispatch, Fearless's lambdas also behave like objects in pure object calculi, such as Featherweight Java.

Panic, the fearless mascot reading a book of dark secrets (this blog post) in shock!

Fearless booleans

We define the interface and behaviour of a lambda with traits, distinct from classes, in that they do not hold state via fields. For example, here is a trait defining a boolean:

Bool:{}

The trait's name goes before the colon, followed by its methods written within the braces ({}). Traits can also implement other traits. For example, True and False can implement Bool:

True:Bool{}
False:Bool{}

When a trait implements another trait, it becomes a subtype of that trait allowing for polymorphism. Traits can implement multiple other traits.

Stringable:{}
Bool:{}
True:Bool,Stringable{}
False:Bool,Stringable{}

The implements relationship is transitive, so if Bool implements Stringable, both True and False would automatically implement it too. With this knowledge, we can make all booleans implement Stringable:

Stringable:{}
Bool:Stringable{}
True:Bool{} // also Stringable
False:Bool{} // also Stringable

Fearless has abstract methods, which only define the method's signature. Fearless also has concrete methods, which define an implementation of what the method does. Traits inherit methods from the other traits they implement, so methods do not need to be repeated unless they are being overridden. Let's add a method to Stringable for turning our booleans into strings:

Stringable:{ .str: Str }

The keen-eyed amongst you may have noticed that our method name (.str) looks odd due to the . in front of the name. The reason for writing method names this way is because, in Fearless, method names are written as their whole selector (i.e. how we invoke them). Methods can also have symbols as method names, which allows us to write code like a && b (calling the && method on a, with b as an argument).

To implement a method, we add an arrow followed by an expression after the signature (.str: Str). The first expression we will look at is creating a lambda. The simplest form of this expression is to write a trait name, like True. The trait must be concrete (have no abstract methods) to create a lambda in this way. While Fearless has no primitive types, strings like "Hello" are valid trait names, and the Fearless compiler will automatically make a trait for every string literal used in your code. This means that we can write the expression "True" to create a lambda that implements the "True" trait, which itself implements the Str trait. Using this knowledge, we can implement the Stringable trait's method in our booleans:

Stringable:{ .str: Str }
Bool:Stringable{}
True:Bool{ .str: Str -> "True" }
False:Bool{ .str: Str -> "False" }

Fearless is smart enough to infer some details about the methods we inherit, so we can skip writing the return-type of the .str method in True and False:

True:Bool{ .str -> "True" }
False:Bool{ .str -> "False" }

Method signatures can also include a list of parameters for the arguments to that method. For example: .and(b: Bool): Bool defines a method that takes one Bool argument and makes it available with the name b. With this knowledge we can finally define methods for boolean logic on our Bool trait:

Bool:{
  .and(b: Bool): Bool,
  .or(b: Bool): Bool,
  .xor(b: Bool): Bool,
  .not: Bool,
  }

To implement these methods we will need the other two expressions in fearless:

Method calls in fearless are in the conventional form reciever methodName (expressions). For example: A.meth1(B, C) would create a lambda that implements A, then call a method called .meth1 with the arguments of a lambda that implements B and a lambda that implements C. If there are no arguments or only one argument, the brackets can be omitted (i.e. True.not or True .and False). Alongside method parameters, another identifier called this is in-scope. The identifier this refers to the lambda implementing the trait, similar to how this refers to an object instance of a class in languages like Java. With these two new expressions, we can implement True and False:

True:Bool{
  // by definition, if the left hand side of the 'and' is true
  // the answer is the other boolean
  .and(b) -> b,
  // the inverse of '.and'.
  .or(b) -> this,
  // exclusive-or, true if 'b' is false.
  .xor(b) -> b.not,
  .not -> False,
  .str -> "True",
  }
// For completeness, the opposite of 'True'
False:Bool{
  .and(b) -> this,
  .or(b) -> b,
  .xor(b) -> b,
  .not -> True,
  .str -> "False",
  }

We have now defined booleans exclusively using traits, lambdas, method calls on lambdas, and bound identifiers (i.e. b and this). No secret primitives are hiding in the code sample; everything we have written is self-sufficient and uses the entirety of the expressions that the Fearless programming language has to offer.

As a final treat, we can add some methods which allow us to do boolean logic using binary operators, like && and ||. To save us from having to duplicate code, we can call the English-named methods as the implementations for our symbol-named methods:

Bool:{
  .and(b: Bool): Bool,
  &&(b: Bool): Bool -> this.and(b),
  .or(b: Bool): Bool,
  ||(b: Bool): Bool -> this.or(b),
  .xor(b: Bool): Bool,
  ^(b: Bool): Bool -> this.xor(b),
  .not: Bool,
  }

Higher-order methods for control-flow and branching

The next step to make our booleans fully featured (and match the definition seen in the standard library) is to add a way to alter behaviour based on whether we have True or False. To achieve this, we will use a "matcher" lambda which contains a method for each scenario:

ThenElse:{
  .then: Str,
  .else: Str,
  }

Unlike other languages which have a "match" construct built-in, we rely on dynamic dispatch and our multiple-method lambdas to achieve an identical result.

We can then have a higher-order method on True and False which invokes the correct method on our matcher:

// methods defined earlier in the article are omitted for space
Bool:{
  .if(m: ThenElse): Str,
  ?(m: ThenElse): Str -> this.if(m),
  }
True:{
  .if(m) -> m.then,
  }
False:{
  .if(m) -> m.else,
  }
// example usage:
Mood:{
  .msg(isAfraid: Bool): Str ->
    isAfraid ? ThenElse{ .then -> "AAH!", .else -> "No panic here" }
  }

To make things a little less verbose, Fearless can infer that our lambda used in .msg needs to implement ThenElse, so we can omit the trait name:

Mood:{
  .msg(isAfraid: Bool): Str ->
    isAfraid.if{ .then -> "AAH!", .else -> "No panic here" }
  }

The higher-order .if method has added control flow into our application using our matcher, but it is currently limited to returning lambdas that implement the string trait. To add some more flexibility, we need to use generic type parameters. A generic type parameter on a trait can refer to any type in Fearless and has to be specified (or inferred) by any trait or lambda that implements it. Similarly to a method parameter, it creates a new variable that refers to something concrete when used. However, this "type variable" is used in place of trait names for types instead of being used as an expression. For example, here is ThenElse with a generic type parameter for the return type of our branches:

ThenElse[R]:{
  .then: R,
  .else: R,
  }

We also need generic methods because otherwise, we would have no value for R within the signature for the .if method. When a generic method is called, a type must be provided (or inferred), which will be used as the concrete type for the type parameter. With generic methods, we now have fully-flexible branching control flow on booleans:

Bool:{
  .if[R](m: ThenElse[R]): R,
  ?[R](f: ThenElse[R]): R -> this.if(f),
  }
Mood:{
  .describe(isAfraid: Bool): Mood ->
    isAfraid ? { .then -> Afraid, .else -> Calm },
  .test1: Mood -> this.describe(False || True), // returns Afraid
  .test2: Mood -> this.describe(False && True), // returns Calm
  }
Afraid:Mood{}
Calm:Mood{}

Capturing parameters for keeping state immutably

In our programs, we will likely want to keep state. For example, we could have a trait for our fluffy mascot seen earlier in the article, Panic. Panic is an easily frightened creature, so we want a method that tells us if Panic is frightened:

Panic:{ .isAfraid: Bool, }

To create a lambda that implements Panic, we must capture a boolean to return in the .isAfraid method. We will do this with a method in another trait because we could not make a lambda on the Panic trait without a concrete implementation for .isAfraid. By convention, when making a "helper trait", we give it the same name as the trait it is related to, but with a prime (') at the end of its name. We also often use # as a method name for "constructor" methods, which you can read as "of". For example:

Panic':{ #(isAfraid: Bool): Panic -> { .isAfraid -> isAfraid } }

Because .isAfraid is the only method in the Panic trait, we can save some effort and skip writing its name:

Panic':{ #(isAfraid: Bool): Panic -> { isAfraid } }

We can also call other methods while capturing a value:

Panic:{
  .thoughts: Thoughts
  }
Panic':{
  #(isAfraid: Bool): Panic -> isAfraid ? {
    .then -> { Fear },
    .else -> { Calm },
    }
  }
Thoughts:{ .describe: Str }
Fear:Thoughts{ "Panic holds their book of dark secrets and looks upon it in TERROR" }
Calm:Thoughts{ "Panic sits and thinks about if their soul has referrential equality too" }

In that example, the # method on Panic' does not capture the Bool lambda in the Panic lambda that it creates. Instead, Panic captures one of the two Thoughts lambdas. The reason for writing the method in this order is because otherwise, every time we call the .thoughts method, the if method on the boolean will be re-executed. We can see the slower approach here:

Panic':{
  #(isAfraid: Bool): Panic -> {
    isAfraid ? {
      .then -> Fear,
      .else -> Calm,
      }
    }
  }

The problem becomes fairly obvious when we write everything verbosely:

Panic':{
  #(isAfraid: Bool): Panic -> Panic{
    .thoughts: Thoughts -> isAfraid ?[Thoughts](ThenElse[Thoughts]{
      .then: Thoughts -> Fear{},
      .else: Thoughts -> Calm{},
      }
    })
  }
// vs.
Panic':{
  #(isAfraid: Bool): Panic -> isAfraid ?[Panic](ThenElse[Panic]{
    .then: Panic -> Panic{ .thoughts: Thoughts -> Fear{} },
    .else: Panic -> Panic{ .thoughts: Thoughts -> Calm{} },
    })
  }

The "slow" version is not necessarily wrong because, in some cases, it would be desirable to defer an expensive computation until the method that needs it is called. Similarly to many programming languages, it is important to be aware of when computation is eager or delegated when deciding what performance tradeoffs the developer wishes to make.

Bringing it all together 😸

This programming style is a blend of functional and object-oriented programming that offers traits' organisational and code structuring power with only lambdas. For a slightly more substantial example of everything learnt over this article, we have a program that will reduce a list of Panics into a new list of just the ones we need to calm down.

The first task for building our Panic mood-management software is to add a matcher to Panic's thoughts, so we can branch on their current mood:

Thoughts:{ .match[R](m: ThoughtMatcher[R]): R }
ThoughtMatcher[R]:{ .fear: R, .calm: R, }
Fear:Thoughts{ m -> m.fear }
Calm:Thoughts{ m -> m.calm }

Now that we can branch on their thoughts, we can start building our triage system for finding all the ones that are panicking. We will start by delegating the work to a helper method, which receives an empty linked list as an argument (acc):

PanicTriage:{
  .panickingPanics(panics: List[Panic]): List[Panic] ->
    this._panickingPanics({}, panics),
  ._panickingPanics(acc: List[Panic], panics: List[Panic]): List[Panic] ->
      // ...
  }

We will use the acc list on the .panickingPanics method to store any Panic from the panics list that needs care and affection. Before we can find out the emotional state of a Panic, we need to extract it from our panics list. To do this, we have a .head method on List[Panic], which returns an optional Panic depending on if we have reached the end of the list. For more information, the complete code for lists and optionals is in the appendix of this article. Just like with our booleans, we use a matcher to handle control flow with the optional:

PanicTriage:{
  .panickingPanics(panics: List[Panic]): List[Panic] ->
    this._panickingPanics({}, panics),
  ._panickingPanics(acc: List[Panic], panics: List[Panic]): List[Panic] ->
    panics.head.match{
      .some(panic) -> //...
      .none -> acc,
      },
  }

The final step for our triage software to be complete, is to recursively call ._panickingPanics so we can build up our acc list:

PanicTriage:{
  .panickingPanics(panics: List[Panic]): List[Panic] ->
    this._panickingPanics({}, panics),
  ._panickingPanics(acc: List[Panic], panics: List[Panic]): List[Panic] ->
    panics.head.match{
      .some(panic) -> panic.thoughts.match{
        .fear -> this._panickingPanics(acc + panic, panics.tail),
        .calm -> this._panickingPanics(acc, panics.tail),
        },
      .none -> acc,
      },
  }

Language complexity vs. expressive power vs. usability

Fearless features the same expressions as lambda calculus (variable, application, and abstraction/lambda). However, Fearless also includes a trait-based type system, providing a table of named traits. A trait table is helpful because it allows for a structure for grouping related (often interrelated) concepts and behaviour. For example, in lambda calculus, we could write our booleans in Church Encoding, with lambdas performing all the boolean operations. Still, with our trait table, we can have a structured collection of functions with well-defined relationships to each other.

Featherweight Java has a class table that provides the same grouping and explicit relational benefits of Fearless's trait table. However, Featherweight Java's classes are less potent than Fearless's traits because they lack multiple inheritance. Additionally, Featherweight Java adds two extra expressions to the three expressions that Fearless and Lambda Calculus have, one for field accesses and one for type-casting.

So, the structure from traits gives Fearless a relatively special position of having more structure than the similarly small lambda calculus. At the same time, the lack of fields and support for multiple inheritance puts Fearless in the position of maintaining a similar level of structure to Featherweight Java but with less verbosity.

What's next

The language presented so far is pure in that it has no side effects, all methods will always do the same thing given the same input, and all expressions are referentially transparent. However, with three additions, Fearless can support mutable state and side effects while maintaining purity and referential transparency in immutable code. In the following article, I will write about how Fearless achieves all this while still exclusively being a lambda-based language.

Further Reading

In 2017, Wang et al. introduced "interface-based object-oriented programming" (IB) and Classless Java— showing how to write practical object-oriented programs exclusively using interfaces. The composability from IB comes from decoupling state and behaviour, removing fields from consideration when composing interfaces together. Servetto et al. refined this concept in "λ-Based Object-Oriented Programming", which Fearless builds from.

Appendix

Definition of List[E]

Cons:{
  #[E](h: E, t: List[E]): List[E] -> { .match(m) -> m.elem(h, t) },
  }
List[E]:{
  .match[R](m: ListMatch[E, R]): R -> m.empty,
  .isEmpty: Bool -> this.match{ .empty -> True, .elem(_,_) -> False },
  .len: UInt -> this.match{ .empty -> 0u, .elem(_,t) -> t.len + 1u, },
  ++(l1: List[E]): List[E] -> this.match{
    .empty -> l1,
    .elem(h, t) -> Cons#(h, t ++ l1)
    },
  +(e: E): List[E] -> this ++ (Cons#(e, {})),
  .get(i: UInt) : Opt[E] -> this.match{
    .empty -> {},
    .elem(h, t) -> (i == 0u) ? { .then -> Opt#h, .else -> t.get(i - 1u) }
    },
  .head: Opt[E] -> this.match{
    .empty -> {},
    .elem(h,_) -> Opt#h,
    },
  .tail: List[E] -> this.match{
    .empty -> {},
    .elem(_,t) -> t,
    },
  }
ListMatch[E,R]:{ .elem(head: E, tail: List[E]): R, .empty: R }

Definition of Opt[T]

Opt:{ #[T](x: T): Opt[T] -> { .match(m) -> m.some(x) } }
Opt[T]:{
  .match[R](m: OptMatch[T, R]): R -> m.none,
  .map[R](f: OptMap[T,R]): Opt[R] -> this.match(f),
  .do(f: OptDo[T]): Opt[T] -> this.match(f),
  .flatMap[R](f: OptFlatMap[T, R]): Opt[R] ->this.match(f),
  ||(alt: T): T -> this.match{ .some(x) -> x, .none -> alt },
  .isNone: Bool -> this.match{ .none -> True, .some(_) -> False },
  .isSome: Bool -> this.match{ .none -> False, .some(_) -> True },
  }
OptMatch[T,R]:{ .some(x:T): R, .none: R }
OptFlatMap[T,R]:OptMatch[T,Opt[R]]{ .none -> {} }
OptMap[T,R]:OptMatch[T,Opt[R]]{ #(t:T):R, .some(x) -> Opt#(this#x), .none -> {} }
OptDo[T]:OptMatch[T,Opt[T]]{
  #(t:T):Void,
  .some(x) -> Opt#(this._doRes(this#x, x)),
  .none->{},
  ._doRes(y:Void,x:T):T -> x
  }

Definition of Void

Void:{}