Menu
Search

Forums

Forum Index

Thread overview
C++ to D
Apr 01, 2015
Dennis Ritchie
Apr 01, 2015
John Colvin
Apr 01, 2015
Dennis Ritchie
Apr 01, 2015
John Colvin
Apr 01, 2015
John Colvin
Apr 02, 2015
Dennis Ritchie
April 01, 2015
Gravatar of Dennis RitchiePosted by Dennis RitchieReply
Dennis Ritchie
Gravatar of Dennis Ritchie


Reply
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;
}
April 01, 2015
Gravatar of John ColvinPosted by John Colvin
in reply to Dennis Ritchie		Reply
John Colvin
Gravatar of John Colvin
Posted in reply to Dennis Ritchie


Reply
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.
April 01, 2015
Gravatar of Dennis RitchiePosted by Dennis Ritchie
in reply to John Colvin		Reply
Dennis Ritchie
Gravatar of Dennis Ritchie
Posted in reply to John Colvin


Reply
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;
}
April 01, 2015
Gravatar of John ColvinPosted by John Colvin
in reply to Dennis Ritchie		Reply
John Colvin
Gravatar of John Colvin
Posted in reply to Dennis Ritchie


Reply
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));
}
April 01, 2015
Gravatar of John ColvinPosted by John Colvin
in reply to John Colvin		Reply
John Colvin
Gravatar of John Colvin
Posted in reply to John Colvin


Reply
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.
April 02, 2015
Gravatar of Dennis RitchiePosted by Dennis Ritchie
in reply to John Colvin		Reply
Dennis Ritchie
Gravatar of Dennis Ritchie
Posted in reply to John Colvin


Reply
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.