type_theory.d:

module type_theory;
import std.conv;
import prod;

class Type
{
public:
   Prod opBinary(string op="*")(Type r)
   {
      alias l = this;
      return new Prod(l, r);
   }

   Type opBinary(string op="^")(int k)
   in {
      assert (k > 0);
   }
   do {
      if (k == 1)
         return this;

      auto P = this;

      while (k > 0)
      {
         k --;
         P = this * P;
      }

      return P;
   }

   override string toString() {
      auto str = to!string(cast(void*) this);
      if (isAtomic)
         return str;
      return "(" ~ str ~ ")";
   }

   @property string typename() {
      return typeof(this).stringof;
   }

   string typingString() {
      return *this ~ ":" ~ typename;
   }

   string opUnary(string op="*")() {
      return toString();
   }

   bool isAtomic() { return false; }
}

prod.d:

module prod;
import type_theory;

class Prod : Type
{
public:
   this(Type l, Type r)
   {
      this.l = l;
      this.r = r;
   }

   @property Type left() { return l; }
   @property Type right() { return r; }

   override string toString() {
      return "(" ~ *l ~ r"\times " ~ *r ~ ")";
   }

protected:
   Type r,l;
}

unittest {
   import std.stdio;
   auto A = new Type();
   auto P = new Prod(A,A);
   writeln("P = ", P);
   readln();
}

var.d:

module var;

import type_theory;

class Var : Type
{
public:
   alias assign this;

   this(string syms)
   {
      this.syms = syms;
   }

   Var opOpAssign(string op="~")(Type assign)
   {
      this.assign = assign;
      return this;
   }

   override string toString() { return syms; }

   @property override bool isAtomic() { return true; }

protected:
   Type assign;
   string syms;
}


unittest {
   import std.stdio;

   Var A = new Var("A");
   A ~= new Type();
   writeln(A);
   auto B = A*A^2;
   writeln(A);

   writeln("B=", B);
   readln();
}

Result should be "A\times (A\times A)" however it's always coming out (in the var.d unittest):

B=((A\times A)\times ((A\times A)\times (A\times A)))

In other words when it is supposed to print A for each of the components, it instead prints "A\times A".

Please give me a D recipe for accomplishing this relatively simple thing.

Thanks!

On Monday, 19 August 2024 at 09:42:44 UTC, Daniel Donnelly, Jr. wrote:

module type_theory;
import std.conv;
import prod;

[...]

I had to put while (k > 1) instead of while (k > 0) and it works. I still though can't get it to work with the obvious recursive formula of this * this^(k-1) for example (same issue); any ideas?

On Monday, 19 August 2024 at 09:42:44 UTC, Daniel Donnelly, Jr. wrote:

   Type opBinary(string op="^")(int k)
   in {
      assert (k > 0);
   }
   do {
      if (k == 1)
         return this;

      auto P = this;

      while (k > 0)
      {
         k --;
         P = this * P;
      }

      return P;
   }

^ should be a bitwise XOR, instead you can overload ^^ which is for exponentiation.

Also, your algorithm is a little bit flawed. To rework it, it would help if you consider cases like:

• 1^^n == 1
• n^^0 == sign(n) (if n is 0, returns 1 or undefined)
• 0^^n == 0 (divide by zero if n is negative)

It’s cases like these which can help inform us how the algorithm should work. If you can’t think of how you’d make all those cases line up correctly, try looking at an existing integer exponentiation algorithm online. An algorithm written in another language will still be applicable in D.