Traits vs Haskell typeclasses (for tagless final programming)

Hi
I'm not a specialist of Rust, although I have been following it for some years. Preparing some possible project, I was testing implementing typed tagless final style, as described by Oleg Kyseliov and colleagues. This kind of code heavily relies on Haskell typeclasses, although some things along the same lines are also doable in OCaml (although in a little more contrived way).

Thus, I wanted to check whether something similar was doable in Rust too, using traits. Here is the code I ended with:

mod exp {
    pub trait Exp {
        fn lit(_: i32) -> Self;
        fn neg(_: Self) -> Self;
        fn add(_: Self, _: Self) -> Self;
    }
    pub fn lit<T: Exp>(x: i32) -> T {
        T::lit(x)
    }
    pub fn neg<T: Exp>(x: T) -> T {
        T::neg(x)
    }
    pub fn add<T: Exp>(x: T, y: T) -> T {
        T::add(x, y)
    }
    impl Exp for i32 {
        fn lit(x: i32) -> Self {
            x
        }
        fn neg(x: Self) -> Self {
            -x
        }
        fn add(e1: Self, e2: Self) -> Self {
            e1 + e2
        }
    }
    impl Exp for String {
        fn lit(x: i32) -> Self {
            format!("{}", x)
        }
        fn neg(x: Self) -> Self {
            format!("(- {})", x)
        }
        fn add(e1: Self, e2: Self) -> Self {
            format!("({} + {})", e1, e2)
        }
    }
    // view and eval are there to choose an implementation by forcing a type for the parameter
    pub fn view(x: String) -> String {
        x
    }
    pub fn eval(x: i32) -> i32 {
        x
    }
}

use exp::*;

fn main() {
    let value = add(lit(5), neg(lit(3)));
    println!("{}", view(value));
    println!("{}", eval(value));
}

As you may have guessed, this code doesn't compile, with the following error:

error[E0308]: mismatched types
  --> src/main.rs:52:25
   |
52 |     println!("{}", eval(value));
   |                         ^^^^^ expected i32, found struct `std::string::String`
   |
   = note: expected type `i32`
              found type `std::string::String`

I was said that I could make value a function as in:

fn value<T: Exp>() -> T {
    add(lit(5), neg(lit(3)))
}
fn main() {
    println!("{}", view(value()));
    println!("{}", eval(value()));
}

Indeed, it compiles. But I'd like value to keep being a value (no pun intended). The function-based solution makes me call value() twice, which is obviously not the same as only once (as is possible in Haskell). I'd love to be made aware of a solution...

AFAIK, it is not possible in Haskell to reuse the same value as instance of two different types. It is possible to pass a generic function into the functions expecting different types, and the passed function will be evaluated (lazily) inside them, but if you've produced (somehow) the value of some type, you can't pass this value to the place expecting different type. So your last approach is roughly what you've done in Haskell, too (except that eval and view would probably receive the function and call it themselves).

2 Likes

I am by no means a Haskell specialist, so I may miss something, but this is possible:

{-# LANGUAGE NoMonomorphismRestriction #-}
{-# LANGUAGE FlexibleInstances #-}

class Exp repr where
  lit :: Int -> repr
  neg :: repr -> repr
  add :: repr -> repr -> repr

instance Exp Int where
  lit n = n
  neg e = - e
  add e1 e2 = e1 + e2

instance Exp String where
  lit n = show n
  neg e = "(-" ++ e ++ ")"
  add e1 e2 = "(" ++ e1 ++ " + " ++ e2 ++ ")"

view :: String -> String
view e = e

eval :: Int -> Int
eval e = e

tf1 = add (lit 8) (neg (add (lit 1) (lit 2)))

tf1_eval = eval tf1 
-- 5

tf1_view = view tf1 
-- "(8 + (-(1 + 2)))"

main = do
  print tf1_eval
  print tf1_view

Rust equivalent of this Haskell code should be like:

trait ExpValue {
    fn force<E: Exp>(&self) -> E;
}

fn main() {
    struct Value;
    impl ExpValue for Value {
        fn force<E: Exp>(&self) -> E {
            add(lit(5), neg(lit(3)))
        }
    }
    let value = Value;
    println!("{}", value.force::<i32>());
    println!("{}", value.force::<String>());
}
4 Likes

Interesting, thank you.

  1. Is there a way to push as many definitions as possible in the exp module? In particular, having functions view and eval deinfed in exp and calling value.force... in the appropriate way.
  2. This way of doing looks like it could be systematized. Do you know if there are there plans to make such uses of traits simpler in the future, in Rust, mimicking somehow Haskell (even without Haskell's type inference)? It looks like a "natural" mode of use...

Is there a way to push as many definitions as possible in the exp module? In particular, having functions view and eval deinfed in exp and calling value.force... in the appropriate way.

Yes, you can define functions:

fn eval(value: &impl ExpValue) -> i32 { value.force() }

This way of doing looks like it could be systematized. Do you know if there are there plans to make such uses of traits simpler in the future, in Rust, mimicking somehow Haskell (even without Haskell's type inference)? It looks like a "natural" mode of use...

This is a (partial) emulation of Haskell's lazy evaluation. Rust is a strict language and uses monomorphization for generics. You should keep in mind not all Haskell patterns translates well to other languages naturally.

1 Like

Just to elaborate a little more on @pcpthm's post, this is because you're using NoMonomorphismRestriction, which means that your top-level declarations (tf1, tf1_eval, tf1_view) that don't have type signatures are polymorphic. This means that they are not actually a single value, but evaluated potentially multiple times in order to produce a value under different types. Essentially they are like functions that take no arguments and have a generic return type.

1 Like

Thank you. For the sake of completeness, this is how you could do in OCaml:

module type EXP_SYM = sig
  type repr 
  val lit : int -> repr
  val neg : repr -> repr
  val add : repr -> repr -> repr
end

module Exp_sym_int = struct
  type repr = int
  let lit n = n
  let neg n = ~- n
  let add n m = n + m
end

module Exp_sym_string = struct
  type repr = string
  let lit n = string_of_int n 
  let neg n = "(-" ^ n ^ ")"
  let add n m = "(" ^ n ^ " + " ^ m ^ ")"
end

type 'a exp_sym = (module EXP_SYM with type repr = 'a)

let tf1 : type a . a exp_sym -> a = function (module E) ->
  let open E in 
  add (lit 8) (neg (add (lit 1) (lit 2)))

let eval (m : int exp_sym -> int) = 
  m (module Exp_sym_int)

let view (m : string exp_sym -> string) = 
  m (module Exp_sym_string)

let _ = view tf1

let _ = eval tf1

As there are no typeclasses in OCaml (although some work is in progress for so-called modular implicits), you must pass a module implementing the meaning of view or eval, which I'm doing here using first-class modules.

OK. However, I don't see why you're saying they're not a single value. In functional languages, a closure is a value, so that's how I interpreted them. Here, I guess, a particular kind of value, as what's passed as an implicit argument is the appropriate typeclass instance. But as I said, I'm not a Haskell expert, so I may fool myself here. Now the OCaml version passes the "instance" explicitly and tf1 is indeed a value, so that's why I apply the same reasoning to Haskell.

Sorry @pcpthm , I jumped a bit too quickly on the "Solution" button. It was perhaps not clear in my original post, but a value such as value would in principle be created at runtime, for instance by a parser for arithmetic expressions. Your solution needs to build a struct and an impl: I do not know Rust very well but I have the impression it wouldn't be compatible with an arbitrary number of values (such as value) created at runtime. With OCaml or Haskell, this is straightforward.

with an arbitrary number of values (such as value ) created at runtime

Please clarify what you want to achieve in the end?
Maybe Rust code closer to Haskell's implementation of typeclass or OCaml's module is like this:

trait Exp {
    type Repr;
    fn lit(&self, x: i32) -> Self::Repr;
    fn neg(&self, x: Self::Repr) -> Self::Repr;
    fn add(&self, x: Self::Repr, y: Self::Repr) -> Self::Repr;
}

struct Eval;
impl Exp for Eval {
    type Repr = i32;
    fn lit(&self, x: i32) -> Self::Repr {
        x
    }
    fn neg(&self, x: Self::Repr) -> Self::Repr {
        -x
    }
    fn add(&self, x: Self::Repr, y: Self::Repr) -> Self::Repr {
        x + y
    }
}

struct View;
impl Exp for View {
    type Repr = String;
    fn lit(&self, x: i32) -> Self::Repr {
        format!("{}", x)
    }
    fn neg(&self, x: Self::Repr) -> Self::Repr {
        format!("(- {})", x)
    }
    fn add(&self, x: Self::Repr, y: Self::Repr) -> Self::Repr {
        format!("({} + {})", x, y)
    }
}

fn main() {
    fn value<E: Exp>(e: &E) -> E::Repr {
        e.add(e.lit(5), e.neg(e.lit(3)))
    }
    println!("{}", value(&Eval));
    println!("{}", value(&View));
}

A is value will be monomorphized for each type. Haskell boxes Int and String to a pointer thus those types can be erased.
As far as I know, there is no easy way to use boxed type and type erasure while keeping type safety in Rust.

Thank you for your answer. Sorry for not being sufficiently clear. The idea of "tagless final" style is, instead of representing a DSL (domain-specific language) as an enum (one constructor per type of node of the AST), to represent it as a trait (with one function per AST node type). Then, you have in particular two problems to address:

  1. To evaluate a term (here an Exp), you need to provide it a function giving it its semantics (here: view or eval). For this to be sensible, the term must be built only once, avoiding to give it a concrete type like String or i32. You answered this before :slight_smile:
  2. But terms must also be built dynamically. Typically, a parser would parse a file showing an expression in concrete syntax and build a corresponding AST in terms of calls to the trait functions. This is what I felt was missing in your former answer as the Value struct and the impl can certainly not be returned by a parser (I suppose). In the sense that the same parser may parse an unbounded number of expressions and should produce the same number of AST terms.

Here I think your solution almost solves this latter question of mine :slight_smile: I want to mimick a parse function that would produce value by parsing a file. Meaning, the main function should look like:

fn main() {
    let value = parse();
    println!("{}", value(&Eval));
    println!("{}", value(&View));
}

Unfortunately, I didn't find how to implement parse (of course, I don't care about real parsing here, the question is that of giving a type to parse and being able to return an AST term that could be arbitrary). I tried this, but I have several errors:

fn parse<E: Exp, F: Fn(&E) -> E::Repr>() -> F {
    |e : Exp|{e.add(e.lit(5), e.neg(e.lit(3)))}
}

type of parse

is

trait ExpValue {
    fn apply<E: Exp>(&self, e: &E) -> E::Repr;
}

Functions or closures cannot implement this directly, you have to wrap in a type because Rust doesn't have generic closures or hyper-ranked trait bounds.
Also because we cannot erase type of implementation of Exp or ExpValue, it is very awkward to implement this.
You have to somehow tame monomorphization. That is a difference between Rust and Haskell.
For existing codes, I think parser combinators https://crates.io/crates/nom or https://crates.io/crates/combine are good examples of how to somewhat-higher-ranked generic programming in Rust without sacrificing performance.

You want this,

fn parse<E: Exp>() -> impl Fn(&E) -> E::Repr {
    |e : Exp|{e.add(e.lit(5), e.neg(e.lit(3)))}
}

You would need HRTB to get a more general solution i.e. generic closures.

It would probably be spelled,

fn parse() -> impl for<E: Exp> Fn(&E) -> E::Repr {
    |e| {e.add(e.lit(5), e.neg(e.lit(3)))}
}

But we don't have this yet

HRTB = Higher Rank Type Bounds

@pcpthm @KrishnaSannasi thank you very much for your answers.