www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - C++ to D

reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
Hi,
Please help rewrite this code to D:

#include <iostream>

// Peano Arithmetic

struct zero;

template <typename T>
struct succ {
};

template <typename T>
struct increment {
	using result = succ<T>;
};

template <typename T>
struct decrement;

template <typename T>
struct decrement<succ<T>> {
	using result = T;
};

template <typename A, typename B>
struct addition;

template <typename A>
struct addition<A, zero> {
	using result = A;
};

template <typename A, typename T>
struct addition<A, succ<T>> {
	using result = typename addition<succ<A>, T>::result;
};

template <typename T>
struct to_int;

template <>
struct to_int<zero> {
	static constexpr auto result = 0;
};

template <typename T>
struct to_int<succ<T>> {
	static constexpr auto result = 1 + to_int<T>::result;
};

template <typename T>
using inc = typename increment<T>::result;

template <typename T>
using dec = typename decrement<T>::result;

template <typename A, typename B>
using add = typename addition<A, B>::result;

class nil;

template <typename T, typename Rest>
struct list {
	using head = T;
	using tail = Rest;
};

template <typename T>
struct length;

template <>
struct length<nil> {
	static constexpr auto result = 0;
};

template <typename Head, typename Tail>
struct length<list<Head, Tail>> { // pattern-matching
	static constexpr auto result = 1 + length<Tail>::result;
};

template <template <typename> class Func, class List>
struct map;

template <template <typename> class Func>
struct map<Func, nil> {
	using result = nil;
};

template <template <typename> class Func, class Head, class Tail>
struct map<Func, list<Head, Tail>> { // first-order function
	using result = list<Func<Head>, typename map<Func, 
Tail>::result>;
};

template <template <typename, typename> class Func, class Init, 
class List>
struct fold;

template <template <typename, typename> class Func, class Init>
struct fold<Func, Init, nil> {
	using result = Init;
};

template <template <typename, typename> class Func, class Init, 
class Head, class Tail>
struct fold<Func, Init, list<Head, Tail>> {
	using result = Func<Head, typename fold<Func, Init, 
Tail>::result>;
};

template <class List>
struct sum {
	using result = typename fold<add, zero, List>::result;
};

int main() {

	using one = inc<zero>;
	using two = inc<inc<zero>>;
	using four = inc<inc<inc<inc<zero>>>>;

	using two_plus_one = add<two, one>;
	std::cout << to_int<two_plus_one>::result << std::endl; // 
prints 3

	using l = list<one, list<two, list<four, nil>>>;
	std::cout << length<l>::result << std::endl; // prints 3

	using res = sum<map<inc, l>::result>::result;
	std::cout << to_int<res>::result << std::endl; // prints 10

	return 0;
}
Apr 01 2015
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 1 April 2015 at 13:59:10 UTC, Dennis Ritchie wrote:
<snip>

You can do this:

import std.typetuple;

//helper for staticReduce
template Alias(alias a)
{
	alias Alias = a;
}

// staticReduce should really be in std.typetuple, or
// the soon to arrive std.meta package.
template staticReduce(alias F, TL ...)
if (TL.length >= 2)
{
	static if (TL.length == 2)
		alias staticReduce = Alias!(F!(TL));
	else
		alias staticReduce
		    = staticReduce!(F, F!(TL[0..2]), TL[2..$]);
}

enum Add(Args...) = Args[0] + Args[1];

enum Inc(Args...) = Args[0] + 1;

alias staticSum(TL ...) = staticReduce!(Add, TL);

void main()
{
	//using two_plus_one = add<two, one>;
	enum two_plus_one = 2 + 1;
	//std::cout << to_int<two_plus_one>::result << std::endl;
	static assert(two_plus_one == 3);

	//using l = list<one, list<two, list<four, nil>>>;
	alias l = TypeTuple!(1, 2, 4);
	//std::cout << length<l>::result << std::endl; // prints 3
	static assert(l.length == 3);

	//using res = sum<map<inc, l>::result>::result;
	enum res = staticSum!(staticMap!(Inc, l));
	//std::cout << to_int<res>::result << std::endl; // prints 10
	static assert(res == 10);
}

but really, there's no point:

import std.algorithm;
//All at compile-time:
static assert(1+2 == 3);
static assert([1,2,4].length == 3);
static assert([1,2,4].map!"a+1".sum == 10);

Compile Time Function Evaluation (CTFE) is a very powerful tool
to avoid having to enter in to all that C++ style mess.
Apr 01 2015
parent reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Wednesday, 1 April 2015 at 15:22:10 UTC, John Colvin wrote:

 Compile Time Function Evaluation (CTFE) is a very powerful tool
 to avoid having to enter in to all that C++ style mess.


Yes, CTFE in D really cool. Thanks.

I need to implement arithmetic (addition / subtraction) only use 
the type system.
That is, such a design does not suit me:

enum Add(Args...) = Args[0] + Args[1];
enum Inc(Args...) = Args[0] + 1;

I need a code like this:

-----
#include <iostream>

struct zero;

template <typename T>
struct succ {
};

template <typename T>
struct increment {
	using result = succ<T>;
};

template <typename T>
struct decrement;

template <typename T>
struct decrement<succ<T>> {
	using result = T;
};

template <typename A, typename B>
struct addition;

template <typename A>
struct addition<A, zero> {
	using result = A;
};

template <typename A, typename T>
struct addition<A, succ<T>> {
	using result = typename addition<succ<A>, T>::result;
};

template <typename T>
struct to_int;

template <>
struct to_int<zero> {
	static constexpr auto result = 0;
};

template <typename T>
struct to_int<succ<T>> {
	static constexpr auto result = 1 + to_int<T>::result;
};

template <typename T>
using inc = typename increment<T>::result;

template <typename T>
using dec = typename decrement<T>::result;

template <typename A, typename B>
using add = typename addition<A, B>::result;

int main() {

	using one = inc<zero>;
	using two = inc<inc<zero>>;
	using four = inc<inc<inc<inc<zero>>>>;
	using two_plus_one = add<two, one>;

	std::cout << to_int<four>::result << std::endl; // 4
	std::cout << to_int<two_plus_one>::result << std::endl; // 3

	return 0;
}
Apr 01 2015
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 1 April 2015 at 17:03:34 UTC, Dennis Ritchie wrote:

 On Wednesday, 1 April 2015 at 15:22:10 UTC, John Colvin wrote:

 Compile Time Function Evaluation (CTFE) is a very powerful tool
 to avoid having to enter in to all that C++ style mess.


 Yes, CTFE in D really cool. Thanks.

 I need to implement arithmetic (addition / subtraction) only 
 use the type system.
 That is, such a design does not suit me:

 enum Add(Args...) = Args[0] + Args[1];
 enum Inc(Args...) = Args[0] + 1;


Don't really see the point. Here's a neat thing that's definitely 
cheating because although it stores the results in the type 
system, the arithmetic is done in constant-folding:

struct Integer(int a){}
template Value(T)
{
     static if (is(T == Integer!a, int a))
         enum Value = a;
     else static assert(false, "Can't get Value for " ~ 
T.stringof);
}
alias Inc(T) = Integer!(Value!T + 1);


But if you really insist on it being all type-system (until you 
wan't the answer of course):

struct Zero{}

template Succ(T)
{
     static if (is(T == Pred!A, A))
		alias Succ = A;
	else
		struct Succ{}
}

template Pred(T)
{
     static if (is(T == Succ!A, A))
		alias Pred = A;
	else
		struct Pred{}
}

enum isPositive(T) = is(T == Succ!A, A);
enum isNegative(T) = is(T == Pred!A, A);
enum isZero(T) = is(T == Zero);

template Add(A, B)
{
	static if (isZero!B)
		alias Add = A;
	else static if (isPositive!B)
		alias Add = Add!(Succ!A, Pred!B);
	else
		alias Add = Add!(Pred!A, Succ!B);
}

template Value(T, int seed = 0)
{
	static if (isZero!T)
		enum Value = seed;
	else static if (isPositive!T)
		enum Value = Value!(Pred!T, seed+1);
	else
		enum Value = Value!(Succ!T, seed-1);
}

unittest
{
	alias One = Succ!Zero;
	alias Two = Succ!One;
	alias MinusThree = Pred!(Pred!(Pred!Zero));
	
	static assert (Value!Zero == 0);
	static assert (Value!One == 1);
	static assert (Value!Two == 2);
	static assert (Value!MinusThree == -3);
	
	static assert (Value!(Add!(One, MinusThree)) == -2);
	static assert (Value!(Add!(One, Two)) == 3);
	static assert (is(Add!(Add!(One, Two), MinusThree) == Zero));
}
Apr 01 2015
next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 1 April 2015 at 17:51:40 UTC, John Colvin wrote:

 On Wednesday, 1 April 2015 at 17:03:34 UTC, Dennis Ritchie 
 wrote:

 On Wednesday, 1 April 2015 at 15:22:10 UTC, John Colvin wrote:

 Compile Time Function Evaluation (CTFE) is a very powerful 
 tool
 to avoid having to enter in to all that C++ style mess.


 Yes, CTFE in D really cool. Thanks.

 I need to implement arithmetic (addition / subtraction) only 
 use the type system.
 That is, such a design does not suit me:

 enum Add(Args...) = Args[0] + Args[1];
 enum Inc(Args...) = Args[0] + 1;


 Don't really see the point. Here's a neat thing that's 
 definitely cheating because although it stores the results in 
 the type system, the arithmetic is done in constant-folding:

 struct Integer(int a){}
 template Value(T)
 {
     static if (is(T == Integer!a, int a))
         enum Value = a;
     else static assert(false, "Can't get Value for " ~ 
 T.stringof);
 }
 alias Inc(T) = Integer!(Value!T + 1);


 But if you really insist on it being all type-system (until you 
 wan't the answer of course):

 struct Zero{}

 template Succ(T)
 {
     static if (is(T == Pred!A, A))
 		alias Succ = A;
 	else
 		struct Succ{}
 }

 template Pred(T)
 {
     static if (is(T == Succ!A, A))
 		alias Pred = A;
 	else
 		struct Pred{}
 }

 enum isPositive(T) = is(T == Succ!A, A);
 enum isNegative(T) = is(T == Pred!A, A);
 enum isZero(T) = is(T == Zero);

 template Add(A, B)
 {
 	static if (isZero!B)
 		alias Add = A;
 	else static if (isPositive!B)
 		alias Add = Add!(Succ!A, Pred!B);
 	else
 		alias Add = Add!(Pred!A, Succ!B);
 }

 template Value(T, int seed = 0)
 {
 	static if (isZero!T)
 		enum Value = seed;
 	else static if (isPositive!T)
 		enum Value = Value!(Pred!T, seed+1);
 	else
 		enum Value = Value!(Succ!T, seed-1);
 }

 unittest
 {
 	alias One = Succ!Zero;
 	alias Two = Succ!One;
 	alias MinusThree = Pred!(Pred!(Pred!Zero));
 	
 	static assert (Value!Zero == 0);
 	static assert (Value!One == 1);
 	static assert (Value!Two == 2);
 	static assert (Value!MinusThree == -3);
 	
 	static assert (Value!(Add!(One, MinusThree)) == -2);
 	static assert (Value!(Add!(One, Two)) == 3);
 	static assert (is(Add!(Add!(One, Two), MinusThree) == Zero));
 }


If the is() expressions are confusing you, in this case they work 
like this;

is (T == B!A, A)

means

is T the same type as B instantiated with A, for some type A?

or more succinctly

is T an instantiation of B?

See http://dlang.org/expression.html#IsExpression, it's quite 
reminiscent of some mathematical set notation.
Apr 01 2015
prev sibling parent "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Wednesday, 1 April 2015 at 17:51:40 UTC, John Colvin wrote:

 Don't really see the point. Here's a neat thing that's 
 definitely cheating because although it stores the results in 
 the type system, the arithmetic is done in constant-folding:

 struct Integer(int a){}
 template Value(T)
 {
     static if (is(T == Integer!a, int a))
         enum Value = a;
     else static assert(false, "Can't get Value for " ~ 
 T.stringof);
 }
 alias Inc(T) = Integer!(Value!T + 1);


 But if you really insist on it being all type-system (until you 
 wan't the answer of course):

 struct Zero{}

 template Succ(T)
 {
     static if (is(T == Pred!A, A))
 		alias Succ = A;
 	else
 		struct Succ{}
 }

 template Pred(T)
 {
     static if (is(T == Succ!A, A))
 		alias Pred = A;
 	else
 		struct Pred{}
 }

 enum isPositive(T) = is(T == Succ!A, A);
 enum isNegative(T) = is(T == Pred!A, A);
 enum isZero(T) = is(T == Zero);

 template Add(A, B)
 {
 	static if (isZero!B)
 		alias Add = A;
 	else static if (isPositive!B)
 		alias Add = Add!(Succ!A, Pred!B);
 	else
 		alias Add = Add!(Pred!A, Succ!B);
 }

 template Value(T, int seed = 0)
 {
 	static if (isZero!T)
 		enum Value = seed;
 	else static if (isPositive!T)
 		enum Value = Value!(Pred!T, seed+1);
 	else
 		enum Value = Value!(Succ!T, seed-1);
 }

 unittest
 {
 	alias One = Succ!Zero;
 	alias Two = Succ!One;
 	alias MinusThree = Pred!(Pred!(Pred!Zero));
 	
 	static assert (Value!Zero == 0);
 	static assert (Value!One == 1);
 	static assert (Value!Two == 2);
 	static assert (Value!MinusThree == -3);
 	
 	static assert (Value!(Add!(One, MinusThree)) == -2);
 	static assert (Value!(Add!(One, Two)) == 3);
 	static assert (is(Add!(Add!(One, Two), MinusThree) == Zero));
 }


Thanks.
Apr 02 2015