Skip to content

Instantly share code, notes, and snippets.

@PyMaster22
Created November 8, 2026 09:03
Show Gist options
  • Select an option

  • Save PyMaster22/a619dcd009aaa67cc329776c6ff35523 to your computer and use it in GitHub Desktop.

Select an option

Save PyMaster22/a619dcd009aaa67cc329776c6ff35523 to your computer and use it in GitHub Desktop.
Type-level metaprogramming in C++. A few features are broken or bad, so I am archiving it and starting on a v2.
/* Requires preprocessing with something that understands variadic macros first. */
#define CPP11 201103L
#define CPP_EMPTY()
#define CPP_DEFER(macro) macro CPP_EMPTY()
#define CPP_GlueHelper_Actual(x,y) x##y
#define CPP_Glue(x,y) CPP_GlueHelper_Actual(x,y)
#define CPP_Identity(x) x
#define CPP_fst(x,...) x
#define CPP_snd(x,...) CPP_fst(__VA_ARGS__,CPP_Nil)
#define CPP_IsProbe(...) CPP_snd(__VA_ARGS__,0)
#define CPP_Probe() idk, 1
#define CPP_NotHelpers_0 CPP_Probe()
#define CPP_Not(Bool) CPP_IsProbe(CPP_Glue(CPP_NotHelpers_,Bool))
#define CPP_Bool(Anything) CPP_Not(CPP_Not(Anything))
#define CPP_IfHelper_0(t,...) __VA_ARGS__
#define CPP_IfHelper_1(t,...) t
#define CPP_If(condition) CPP_Glue(CPP_IfHelper_,condition)
#define CPP_Car(cons) CPP_fst cons
#define CPP_Cdr(cons) CPP_snd cons
#define CPP_IsPairProbe(...) CPP_Probe()
#define CPP_IsPair(x) CPP_IsProbe(CPP_IsPairProbe x)
#define CPP_MapIndirection() CPP_Map
#define CPP_MapStep(func,cons) (func(CPP_Car(cons)),CPP_DEFER(CPP_MapIndirection)()(func,CPP_Cdr(cons)))
#define CPP_MapEnd(func,cons) CPP_Nil
#define CPP_Map(func,cons) CPP_If(CPP_IsPair(cons))(CPP_MapStep,CPP_MapEnd)(func,cons)
#define CPP_EachIndirection() CPP_Each
#define CPP_EachStep(func,cons) func(CPP_Car(cons)) CPP_DEFER(CPP_EachIndirection)()(func,CPP_Cdr(cons))
#define CPP_EachEnd(func,cons)
#define CPP_Each(func,cons) CPP_If(CPP_IsPair(cons))(CPP_EachStep,CPP_EachEnd)(func,cons)
#define CPP_Eval0(x) x
#define CPP_Eval1(x) CPP_Eval0(CPP_Eval0(CPP_Eval0(CPP_Eval0(CPP_Eval0(x)))))
#define CPP_Eval2(x) CPP_Eval1(CPP_Eval1(CPP_Eval1(CPP_Eval1(CPP_Eval1(x)))))
#define CPP_Eval3(x) CPP_Eval2(CPP_Eval2(CPP_Eval2(CPP_Eval2(CPP_Eval2(x)))))
#define CPP_Eval4(x) CPP_Eval3(CPP_Eval3(CPP_Eval3(CPP_Eval3(CPP_Eval3(x)))))
#define CPP_Hash #
/* The only* specialized functions */
struct True;
struct False;
template<class LHS, class RHS> struct Equal;
template<class Condition, class TrueCase, class FalseCase> struct Ternary;
template<class LHS, class RHS> struct Equal{typedef False value;};
template<class LHS> struct Equal<LHS,LHS>{typedef True value;};
template<class T, class F> struct Ternary<False,T,F>{typedef F value;};
template<class T, class F> struct Ternary<True ,T,F>{typedef T value;};
#if (__cplusplus >= CPP11) || (!defined(__cplusplus))
#if !defined(__cplusplus)
CPP_Hash if (CPP_GlueHelper_Actual(__,cplusplus) >= CPP11)
#endif
template<class...> struct ArgContainer;
struct NoArgs;
template<class Type, class Object> struct IsType;
template<class...> struct HasArgs;
template<class... Args> struct TakeFirstArg;
template<class... Args> struct DropFirstArg;
template<template<class...>class Function, class ArgContainer> struct FunctionApplier;
template<class Type, class Object> struct IsType{typedef False value;};
template<template<class...> class Type, class... GenericArgs, class... ObjectArgs> struct IsType<Type<GenericArgs...>,Type<ObjectArgs...> >{typedef True value;};
template<> struct HasArgs<>{typedef False value;};
template<> struct HasArgs<ArgContainer<> >{typedef False value;};
template<class... Args> struct HasArgs{typedef True value;};
template<> struct TakeFirstArg<>{typedef NoArgs value;};
template<class Arg1, class... Args> struct TakeFirstArg<Arg1,Args...>{typedef Arg1 value;};
template<> struct DropFirstArg<>{typedef ArgContainer<> value;};
template<class Arg1, class... Args> struct DropFirstArg<Arg1,Args...>{typedef ArgContainer<Args...> value;};
template<template<class...>class Function, class... Args> struct FunctionApplier<Function,ArgContainer<Args...>>{typedef typename Function<Args...>::value value;};
#if !defined(__cplusplus)
CPP_Hash endif
#endif
#endif
template<class E> struct Error;
template<class X> struct I;
template<class X> struct I{typedef X value;};
template<class X> struct LNot;
template<class X> struct BooleanCast;
template<class X, class Y> struct LAnd;
template<class X, class Y> struct LOr;
template<class X, class Y> struct LXor;
template<class X, class Y> struct LImplies;
template<class X> struct LNot{typedef typename Equal<X,False>::value value;}; /* Only one falsy value */
template<class X> struct BooleanCast{typedef typename LNot<typename LNot<X>::value>::value value;};
template<class X, class Y> struct LAnd{typedef typename Ternary<typename BooleanCast<X>::value, BooleanCast<Y>, I<False> >::value::value value;};
template<class X, class Y> struct LOr{typedef typename Ternary<typename BooleanCast<X>::value, I<True>, BooleanCast<Y> >::value::value value;};
//template<class X, class Y> struct LXor{typedef typename LNot<typename Equal<typename BooleanCast<X>::value, typename BooleanCast<Y>::value>::value>::value value;};
template<class X, class Y> struct LXor{typedef typename Ternary<typename BooleanCast<X>::value,LNot<Y>,BooleanCast<Y> >::value::value value;};
template<class X, class Y> struct LImplies{typedef typename Ternary<typename BooleanCast<X>::value, BooleanCast<Y>, I<True> >::value::value value;};
struct Nil;
template<class Car, class Cdr> struct Cons;
template<template<class> class Funtion, class ConsArr> struct Map;
template<template<class> class Predicate, class ConsArr> struct Filter;
template<template<class, class> class Function, class ConsArr, class InitialLHS> struct FoldLeft;
template<class ConsArr, class Value> struct Prepend;
template<class ConsArr, class Value> struct Append;
template<class LeftArr, class RightArr> struct Concat;
template<class ConsArr, class Value> struct MemberOf;
/* I won't consider this a rule breaking, as technically, with an oracle of IsType, this is possible without specialization.
* See below; C++11 allows, C++98 is a lot more restrictive in what we can do. */
template<class ConsMaybe> struct IsCons;
#if (__cplusplus >= CPP11) || (!defined(__cplusplus))
#if !defined(__cplusplus)
CPP_Hash if (CPP_GlueHelper_Actual(__,cplusplus) >= CPP11)
#endif
template<class ConsMaybe> struct IsCons{typedef typename Ternary<typename Equal<ConsMaybe,Nil>::value,I<True>,IsType<Cons<Nil,Nil>,ConsMaybe> >::value::value value;};
template<class... Args> struct Consify;
template<class... Args> struct Consify{typedef typename Ternary<typename HasArgs<Args...>::value,Cons<typename Ternary<typename Equal<typename TakeFirstArg<Args...>::value,NoArgs>::value,I<Nil>,TakeFirstArg<Args...> >::value::value,typename Ternary<typename HasArgs<typename DropFirstArg<Args...>::value>::value,FunctionApplier<Consify,typename DropFirstArg<Args...>::value>,I<Nil> >::value::value>,Nil>::value value;};
#endif
#if !defined(__cplusplus)
CPP_Hash else
#endif
#if (__cplusplus < CPP11) || (!defined(__cplusplus))
template<class ConsMaybe> struct IsCons{typedef typename Equal<ConsMaybe,Nil>::value value;};
template<class Car, class Cdr> struct IsCons<Cons<Car,Cdr> >{typedef True value;};
#if !defined(__cplusplus)
CPP_Hash endif
#endif
#endif
struct Nil{
typedef Nil car;
typedef Nil cdr;
};
template<class Car, class Cdr> struct Cons{
typedef Car car;
typedef Cdr cdr;
};
template<template<class> class Function, class ConsArr> struct Map{
typedef Cons<
typename Function<typename ConsArr::car>::value,
typename Ternary<typename Equal<typename ConsArr::cdr,Nil>::value,
I<Nil>,
Map<Function, typename ConsArr::cdr>
>::value::value
> value;
};
template<template<class> class Predicate, class ConsArr> struct Filter{
private: /* hygiene */
typedef typename Ternary<typename Equal<typename ConsArr::cdr,Nil>::value,
I<Nil>,
Filter<Predicate, typename ConsArr::cdr>
>::value::value Rest;
public:
typedef typename Ternary<typename Predicate<typename ConsArr::car>::value,
Cons<typename ConsArr::car, Rest>,
Rest
>::value value;
};
template<template<class, class> class Function, class ConsArr, class LHS> struct FoldLeft{
private:
typedef typename Ternary<typename Equal<typename ConsArr::car,Nil>::value,I<LHS>,Function<LHS,typename ConsArr::car> >::value::value Applied;
public:
typedef typename Ternary<typename Equal<typename ConsArr::cdr,Nil>::value,
I<Applied>,
FoldLeft<Function, typename ConsArr::cdr, Applied>
>::value::value value;
};
template<class ConsArr, class Value> struct Prepend{
typedef Cons<Value,ConsArr> value;
};
template<class ConsArr, class Value> struct Append{
private:
typedef typename Equal<typename ConsArr::cdr,Nil>::value Predicate;
public:
typedef Cons<
typename Ternary<Predicate, Value, typename ConsArr::car>::value,
typename Ternary<Predicate, I<Nil>, Append<typename ConsArr::cdr, Value> >::value::value
> value;
};
template<class LeftArr, class RightArr> struct Concat{
typedef typename Ternary<typename Equal<LeftArr,Nil>::value,
RightArr,
Cons<
typename LeftArr::car,
typename Ternary<typename Equal<typename LeftArr::cdr,Nil>::value,
I<RightArr>,
Concat<typename LeftArr::cdr, RightArr>
>::value::value
> >::value value;
};
template<class ConsArr, class Value> struct MemberOf{
typedef typename Ternary<typename Equal<typename ConsArr::car,Value>::value,
I<I<True> >,
Ternary<typename Equal<typename ConsArr::cdr,Nil>::value,
I<False>,
MemberOf<typename ConsArr::cdr, Value>
> >::value::value::value value;
};
/* association con or smth sounded funy */
/* Cons<Cons<key,Cons<value,Nil> >,Cons<Cons<key2,Cons<value2,Nil> >, ... > > */
template<class AssocCons, class Key> struct AssocLookup;
template<class AssocCons, class Key, class Value> struct AssocAdd;
template<class AssocCons, class Key> struct AssocRemove;
template<class AssocCons> struct AssocKeys;
template<class AssocOld, class AssocNew> struct AssocJoin;
template<class AssocCons, class Key> struct AssocLookup{
typedef typename Ternary<typename Equal<typename AssocCons::car::car,Key>::value,
I<I<typename AssocCons::car::cdr::car> >,
Ternary<typename Equal<typename AssocCons::cdr,Nil>::value,
I<Nil>,
AssocLookup<typename AssocCons::cdr,Key>
> >::value::value::value value;
};
template<class AssocCons, class Key> struct AssocRemove{
typedef typename Ternary<typename Equal<typename AssocCons::car::car,Key>::value,
I<I<typename AssocCons::cdr> >,
Ternary<typename Equal<typename AssocCons::cdr,Nil>::value,
I<AssocCons>,
/* I gave up on cleanness here )`: */
I<Cons<typename AssocCons::car,typename Ternary<typename Equal<typename AssocCons::cdr,Nil>::value,I<Nil>,AssocRemove<typename AssocCons::cdr,Key> >::value::value> >
> >::value::value::value value;
};
template<class AssocCons, class Key, class Value> struct AssocAdd{
/* Just to ensure we don't clutter memory with 20000000 instances of the key "Q" or whatever
* May become significantly slow if this is done a lot on large alists */
typedef Cons<Cons<Key,Cons<Value,Nil> >, typename AssocRemove<AssocCons,Key>::value> value;
};
template<class AssocCons> struct AssocKeys{
private:
template<class AList> struct Implementation{
typedef Cons<typename AList::car::car,typename Ternary<typename Equal<typename AList::cdr,Nil>::value,
I<Nil>,
AssocKeys<typename AList::cdr>
>::value::value> value;
};
public:
typedef typename Ternary<typename Equal<AssocCons,Nil>::value,
I<Nil>,
Implementation<AssocCons>
>::value::value value;
};
template<class AssocOld, class AssocNew> struct AssocJoin{
/* for each key in AssocNew, add value AssocNew[key] to AssocOld with key key.
* for key in AssocKeys<AssocNew>::value, AssocOld <= AssocAdd<AssocOld,key,AssocLookup<AssocNew,Key>> */
private:
template<class AList, class Key> struct SubFunc{
typedef typename AssocAdd<AList,Key,typename AssocLookup<AssocNew,Key>::value>::value value;
};
public:
typedef typename FoldLeft<SubFunc,typename AssocKeys<AssocNew>::value,AssocOld>::value value;
};
namespace Comb{ /* Namespaced cause utility is iffy at my best guess. */
/* Macro metaprogram completed; also why this cannot be compiled with pedantic C++98 now :)
* Just make sure you at least have C99 or an extensive compiler like GCC */
/* also technically could all be written via typedef to a certain basis
* but something about that feels wrong. */
#define CPP_CombinatorDeclarer(x) struct x; \
namespace _impl_{ template<class CombArr> struct CPP_Glue(x,Comb); }
/*CPP_CombinatorDeclarer(S)
CPP_CombinatorDeclarer(K)
CPP_CombinatorDeclarer(I)
CPP_CombinatorDeclarer(B)
CPP_CombinatorDeclarer(C)
CPP_CombinatorDeclarer(W)*/
CPP_Eval2(CPP_Each(CPP_CombinatorDeclarer,(S,(K,(I,(B,(C,(W,CPP_Nil))))))))
template<class X> struct TrueIdentity;
template<class CombArr> struct Stepper;
template<class CombArr> struct Normalize; /* Reduce to weak head normal form. */
template<class X> struct TrueIdentity{typedef X value;};
template<class CombArr> struct Stepper{
private:
typedef typename CombArr::car Head;
typedef typename CombArr::cdr Rest;
/* That moment when you make a whole abstraction just so
* that you didn't need a simple binary/linear tree */
typedef typename AssocLookup<
Cons<Cons<S,Cons<_impl_::SComb<Rest>,Nil> >,
Cons<Cons<K,Cons<_impl_::KComb<Rest>,Nil> >,
Cons<Cons<I,Cons<_impl_::IComb<Rest>,Nil> >,
Cons<Cons<B,Cons<_impl_::BComb<Rest>,Nil> >,
Cons<Cons<C,Cons<_impl_::CComb<Rest>,Nil> >,
Cons<Cons<W,Cons<_impl_::WComb<Rest>,Nil> >,
Nil> > > > > >
,Head>::value LookupValue;
public:
typedef CombArr out;
typedef Stepper<typename Ternary<typename IsCons<Head>::value,
/* Hacky cause I is redefined in this land */
TrueIdentity<Concat<Head,Rest> >,
Ternary<typename Equal<LookupValue,Nil>::value,
TrueIdentity<CombArr>,
LookupValue
> >::value::value::value> value;
};
template<class CombArr> struct Normalize{
private:
typedef typename Stepper<CombArr>::value::out Stepped;
public:
typedef typename Ternary<typename Equal<CombArr,Stepped>::value,
TrueIdentity<CombArr>,
Normalize<Stepped>
>::value::value value;
};
namespace _impl_{ /* I am of the opinion these should be hidden */
template<class CombArr> struct SComb{
/* Cons<X,Cons<Y,Cons<Z,Rest> > > => Cons<X,Cons<Z,Cons<Cons<Y,Cons<Z,Nil> >,Rest> > > */
private:
typedef typename CombArr::car X;
typedef typename CombArr::cdr::car Y;
typedef typename CombArr::cdr::cdr::car Z;
typedef typename CombArr::cdr::cdr::cdr Rest;
typedef typename MemberOf<Cons<X,Cons<Y,Cons<Z,Nil> > >,Nil>::value UnderDetermined;
public:
typedef typename Ternary<UnderDetermined, Cons<S,CombArr>,
Cons<X,Cons<Z,Cons<Cons<Y,Cons<Z,Nil> >,Rest> > >
>::value value;
};
template<class CombArr> struct KComb{
/* Cons<X,Cons<Y,Rest> > => Cons<X,Rest> */
private:
typedef typename CombArr::car X;
typedef typename CombArr::cdr::car Y;
typedef typename CombArr::cdr::cdr Rest;
typedef typename MemberOf<Cons<X,Cons<Y,Nil> >,Nil>::value UnderDetermined;
public:
typedef typename Ternary<UnderDetermined, Cons<K,CombArr>,
Cons<X,Rest>
>::value value;
};
template<class CombArr> struct IComb{
/* Cons<X,Rest> => Cons<X,Rest> */
/* could be Identity, but consistency, pls */
private:
typedef typename CombArr::car X;
typedef typename CombArr::cdr Rest;
typedef typename MemberOf<Cons<X,Nil>,Nil>::value UnderDetermined;
public:
typedef typename Ternary<UnderDetermined, Cons<I,CombArr>,
Cons<X,Rest>
>::value value;
};
template<class CombArr> struct BComb{
/* Cons<X,Cons<Y,Cons<Z,Rest> > > => Cons<X,Cons<Cons<Y,Cons<Z,Nil> >,Rest> > */
private:
typedef typename CombArr::car X;
typedef typename CombArr::cdr::car Y;
typedef typename CombArr::cdr::cdr::car Z;
typedef typename CombArr::cdr::cdr::cdr Rest;
typedef typename MemberOf<Cons<X,Cons<Y,Cons<Z,Nil> > >,Nil>::value UnderDetermined;
public:
typedef typename Ternary<UnderDetermined, Cons<B,CombArr>,
Cons<X,Cons<Cons<Y,Cons<Z,Nil> >,Rest> >
>::value value;
};
template<class CombArr> struct CComb{
/* Cons<X,Cons<Y,Cons<Z,Rest> > > => Cons<X,Cons<Z,Cons<Y,Rest> > > */
private:
typedef typename CombArr::car X;
typedef typename CombArr::cdr::car Y;
typedef typename CombArr::cdr::cdr::car Z;
typedef typename CombArr::cdr::cdr::cdr Rest;
typedef typename MemberOf<Cons<X,Cons<Y,Cons<Z,Nil> > >,Nil>::value UnderDetermined;
public:
typedef typename Ternary<UnderDetermined, Cons<C,CombArr>,
Cons<X,Cons<Z,Cons<Y,Rest> > >
>::value value;
};
template<class CombArr> struct WComb{
/* Cons<X,Cons<Y,Rest> > => Cons<X,Cons<Y,Cons<Y,Rest> > > */
private:
typedef typename CombArr::car X;
typedef typename CombArr::cdr::car Y;
typedef typename CombArr::cdr::cdr Rest;
typedef typename MemberOf<Cons<X,Cons<Y,Nil> >,Nil>::value UnderDetermined;
public:
typedef typename Ternary<UnderDetermined, Cons<W,CombArr>,
Cons<X,Cons<Y,Cons<Y,Rest> > >
>::value value;
};
}
}
namespace Integer{
/* Conslike object; also little endian */
template<class Bit, class Rest> struct Int;
/* Conslike object generator */
template<template<class> class Function, class Counter> struct Generator;
struct IntPos; struct IntNeg; /* Determines sign through infinite expansion */
template<class Int1> struct Normalize; /* Normalizes infinite expansion; not strictly needed within Integer:: */
template<class Int1> struct IsNegative;
template<class Int1> struct IsZero;
template<class Int1> struct IsTerminal; /* Is 0 or -1, technically */
template<class Int1> struct BNot;
template<template<class,class> class Operator, class LeftInt, class RightInt> struct BinaryBitwise; /* The functional appraoch is growing! */
#if (__cplusplus >= CPP11) || (!defined(__cplusplus))
#if !defined(__cplusplus)
CPP_Hash if (CPP_GlueHelper_Actual(__,cplusplus) >= CPP11)
#endif
template<template<class...> class Op, class... Args> struct NAryBitwise{
private:
typedef typename FoldLeft<LAnd,typename Map<IsTerminal,typename Consify<Args...>::value>::value,True>::value Terminal;
typedef typename Op<typename Args::head...>::value HeadsValue;
public:
typedef Int<HeadsValue,typename Ternary<Terminal,
Ternary<HeadsValue,IntNeg,IntPos>,
NAryBitwise<Op,typename Args::tail...>
>::value::value> value;
};
#if !defined(__cplusplus)
CPP_Hash endif
#endif
#endif
template<class Int1> struct BitLength;
template<class Int1, class Shift> struct LeftShift;
template<class Int1, class Shift> struct RightShift;
template<class Int1> struct Negate;
template<class Int1> struct Abs;
template<class Int1> struct Sign;
template<class Int1> struct Increment;
template<class Int1> struct Decrement;
template<class Int1, class Int2> struct Add;
template<class LeftInt, class RightInt> struct Subtract;
template<class Int1, class Int2> struct Multiply;
template<class Int1, class Int2> struct IntEqual;
template<class LeftInt, class RightInt> struct GreaterThan;
template<class LeftInt, class RightInt> struct LessThan;
template<class Dividend, class Divisor> struct Divide;
template<class Int1, class Modulus> struct Modulo;
template<class Lower, class Upper> struct Range; /* Inclusive, as it always should have been. */
template<class Int1, class Length> struct Truncate;
namespace Math{
template<class Int1, class Int2> struct Min;
template<class Int1, class Int2> struct Max;
template<class Int1, class Int2> struct GCD;
template<class Int1, class Int2> struct LCM;
template<class Int1> struct IntSqrt;
template<class Base, class Exp> struct Power;
template<class Int1> struct Factorial;
template<class Base, class Exp, class Modulus> struct PowerMod;
template<class Int1, class Modulus> struct ExtendedGCD;
template<class Int1, class Modulus> struct ModularInverse;
}
namespace _impl_{
struct DivideByZero; /* errors */
struct ValueError;
template<class Numer, class Denom, class q, class r, class i> struct DivMod;
template<class Int1, class Left, class Right> struct BinSqrt;
template<class Int1, class Modulus, class PrevX, class X, class PrevY, class Y> struct XGCD;
}
template<class Bit, class Rest> struct Int{
typedef Bit head;
typedef Rest tail;
};
struct IntPos{ /* incidentally 0 */
typedef False head;
typedef IntPos tail;
};
struct IntNeg{ /* incidentally -1 */
typedef True head;
typedef IntNeg tail;
};
template<template<class> class Function, class Counter> struct Generator{
private:
typedef typename Ternary<typename Equal<typename Function<typename Increment<Counter>::value>::value,Nil>::value,
Nil,
Generator<Function,typename Increment<Counter>::value>
>::value Next;
public:
typedef typename Function<Counter>::value car;
typedef Next cdr;
};
template<class Int1> struct Normalize{
typedef typename Ternary<typename IsTerminal<Int1>::value,
typename Ternary<typename Int1::head,IntNeg,IntPos>::value,
Int<typename Int1::head,typename Ternary<typename IsTerminal<Int1>::value,
I<Nil>,
Normalize<typename Int1::tail>
>::value::value>
>::value value;
};
template<class Int1> struct IsNegative{
private:
typedef typename Int1::tail Tail;
public:
typedef typename Ternary<typename Equal<Tail,typename Tail::tail>::value,
Equal<Tail,IntNeg>,
IsNegative<Tail>
>::value::value value;
};
template<class Int1> struct IsZero{
typedef typename Ternary<typename Int1::head,
I<I<False> >,
Ternary<typename Equal<Int1,IntPos>::value,
I<True>,
IsZero<typename Int1::tail>
> >::value::value::value value;
};
template<class Int1> struct IsTerminal{
typedef typename Ternary<typename IsZero<Int1>::value,
I<True>,
IsZero<typename Increment<Int1>::value>
>::value::value value;
};
template<class Int1> struct BNot{
private:
typedef typename Int1::head Head;
typedef typename Int1::tail Tail;
public:
typedef Int<typename LNot<Head>::value, typename Ternary<typename MemberOf<Cons<IntPos,Cons<IntNeg,Nil> >,Tail>::value,
Ternary<typename Tail::head,
IntPos,
IntNeg
>, BNot<Tail>
>::value::value> value;
};
template<template<class,class> class Op, class LHS, class RHS> struct BinaryBitwise{
private:
typedef typename LHS::head LHead;
typedef typename RHS::head RHead;
typedef typename LHS::tail LTail;
typedef typename RHS::tail RTail;
typedef typename LAnd<typename IsTerminal<LHS>::value,typename IsTerminal<RHS>::value>::value Terminal;
public:
typedef Int<typename Op<LHead,RHead>::value,typename Ternary<Terminal,
Ternary<typename Op<LHead,RHead>::value,IntNeg,IntPos>,
BinaryBitwise<Op,LTail,RTail>
>::value::value> value;
};
template<class Int1> struct Negate{
typedef typename Increment<typename BNot<Int1>::value>::value value;
};
template<class Int1> struct Abs{
typedef typename Ternary<typename IsNegative<Int1>::value,Negate<Int1>,I<Int1> >::value::value value;
};
template<class Int1> struct Sign{
typedef typename Ternary<typename IsNegative<Int1>::value,I<IntNeg>,Ternary<typename IsZero<Int1>::value,IntPos,Int<True,IntPos> > >::value::value value;
};
template<class Int1> struct BitLength{
typedef typename Increment<typename Ternary<typename IsTerminal<Int1>::value,
BNot<Int1>,//Ternary<typename IsZero<Int1>::value,IntNeg,IntPos>,
BitLength<typename Int1::tail>
>::value::value>::value value;
};
template<class Int1, class Shift> struct LeftShift{
private:
typedef typename Ternary<typename IsNegative<Shift>::value,Error<_impl_::ValueError>,I<True> >::value::value Check;
public:
typedef typename Ternary<typename LAnd<typename IsZero<Shift>::value,Check>::value,
I<Int1>,
LeftShift<Int<False,Int1>,typename Decrement<Shift>::value>
>::value::value value;
};
template<class Int1, class Shift> struct RightShift{
private:
typedef typename Ternary<typename IsNegative<Shift>::value,Error<_impl_::ValueError>,I<True> >::value::value Check;
public:
typedef typename Ternary<typename LAnd<typename IsZero<Shift>::value,Check>::value,
I<Int1>,
RightShift<typename Int1::tail,typename Decrement<Shift>::value>
>::value::value value;
};
template<class Int1> struct Increment{
private:
typedef typename Int1::head Head;
typedef typename Int1::tail Tail;
public:
typedef Int<typename LNot<Head>::value, typename Ternary<Head,
Ternary<typename MemberOf<Cons<IntPos,Cons<IntNeg,Nil> >,Tail>::value,
Ternary<typename Tail::head,
IntPos,
Int<True,IntPos>
>,
Increment<Tail>
>,
I<I<Tail> >
>::value::value::value> value;
};
template<class Int1> struct Decrement{
private:
typedef typename Int1::head Head;
typedef typename Int1::tail Tail;
public:
typedef Int<typename LNot<Head>::value, typename Ternary<Head,
I<I<Tail> >,
Ternary<typename MemberOf<Cons<IntPos,Cons<IntNeg,Nil> >,Tail>::value,
Ternary<typename Tail::head,
Int<False,IntNeg>,
IntNeg
>,
Decrement<Tail>
> >::value::value::value> value;
};
template<class Int1, class Int2> struct Add{ /* I have never seen a more convoluted addition, but I do usually get specialization */
private:
typedef typename Int1::head Head1;
typedef typename Int1::tail Tail1;
typedef typename Int2::head Head2;
typedef typename Int2::tail Tail2;
typedef typename Ternary<Head1,True,Head2>::value IncrementOnce;
typedef typename Ternary<Head1,Head2,False>::value IncrementTwice;
typedef Int<False, typename Ternary<typename IsTerminal<Int1>::value,
Ternary<typename IsZero<Int1>::value,I<Tail2>,Decrement<Tail2> >,
I<Add<Tail1,Tail2> >
>::value::value::value> Next;
public:
typedef typename Ternary<IncrementOnce,
Increment<typename Ternary<IncrementTwice,
Increment<Next>,
I<Next>
>::value::value >,
I<Next>
>::value::value value;
};
template<class Int1, class Int2> struct Subtract{
typedef typename Add<Int1, typename Negate<Int2>::value>::value value;
};
template<class Int1, class Int2> struct Multiply{
private:
typedef typename Int1::head Head1;
typedef typename Int1::tail Tail1;
typedef typename Int2::head Head2;
typedef typename Int2::tail Tail2;
typedef Int<False, typename Ternary<typename IsTerminal<Int1>::value,
Ternary<typename IsZero<Int1>::value,I<IntPos>,Negate<Int2> >,
I<Multiply<Tail1,Int2> >
>::value::value::value> Next;
public:
typedef typename Ternary<Head1,
Add<Int2,Next>,
I<Next>
>::value::value value;
};
template<class Int1, class Int2> struct IntEqual{
/* Int1 == Int2; 0 == Int1 - Int2 */
typedef typename IsZero<typename Subtract<Int1,Int2>::value>::value value;
};
template<class Int1, class Int2> struct GreaterThan{
/* Int1 > Int2; 0 > Int2 - Int1; IsNegative<Int2 - Int1> */
typedef typename IsNegative<typename Subtract<Int2,Int1>::value>::value value;
};
template<class Int1, class Int2> struct LessThan{
/* Int1 < Int2; Int2 > Int1 */
typedef typename GreaterThan<Int2,Int1>::value value;
};
template<class Int1, class Int2> struct Divide{
private:
typedef typename Ternary<typename IsZero<Int2>::value,Error<_impl_::DivideByZero>,I<True> >::value::value Check;
typedef typename Abs<Int1>::value Abs1;
typedef typename Abs<Int2 >::value Abs2;
typedef typename LXor<typename IsNegative<Int1>::value,typename IsNegative<Int2>::value>::value Sign;
typedef typename _impl_::DivMod<Abs1,Abs2,IntPos,IntPos,typename BitLength<Abs1>::value>::value DivMod_;
public:
typedef typename Ternary<Sign,
Ternary<typename IsZero<typename DivMod_::cdr::car>::value,Negate<typename DivMod_::car>,BNot<typename DivMod_::car> >,
I<I<typename DivMod_::car> >
>::value::value::value value;
};
template<class Int1, class Int2> struct Modulo{
typedef typename Subtract<Int1,typename Multiply<Int2,typename Divide<Int1,Int2>::value>::value>::value value;
};
template<class Low, class High> struct Range{
private:
typedef typename Ternary<typename LessThan<High,Low>::value,Error<_impl_::ValueError>,I<True> >::value::value Check;
public:
typedef Cons<Low,typename Ternary<typename LAnd<typename IntEqual<Low,High>::value,Check>::value,
I<Nil>,
Range<typename Increment<Low>::value,High>
>::value::value> value;
};
template<class Int1, class Length> struct Truncate{
private:
/* Why have _impl_ when ____? */
template<class Int2, class Len> struct Truncate2;
template<class Int2, class Len> struct Truncate2{
typedef typename Ternary<typename GreaterThan<Len,IntPos>::value,
Int<typename Int2::head,
typename Ternary<typename GreaterThan<Len,IntPos>::value,
Truncate2<typename Int2::tail,typename Decrement<Len>::value>,
I<IntPos>
>::value::value>,
IntPos
>::value value;
};
public:
/* Now I can Normalize without being ~O(n^2) */
typedef typename Normalize<typename Truncate2<Int1,Length>::value>::value value;
};
namespace _impl_{
/*
* def DivMod(dividend, divisor,q=0,r=0,i=None):
* #if(divisor==0):1/0
* #if(i==None):i=dividend.bit_length()-1
* if(i==-1):return(q,r)
* R=(r<<1)|((dividend>>i)&1)
* return(DivMod(dividend,divisor,q|(1<<i if R>=divisor else 0),R-(divisor if R>=divisor else 0),i-1))
*/
template<class Dividend, class Divisor, class q, class r, class i> struct DivMod{
private:
typedef typename Abs<i>::value Guardedi;
typedef typename BinaryBitwise<LOr,
Int<False,r>, // slightly smaller <<1
// slightly smaller &1
Int<typename RightShift<Dividend,Guardedi>::value::head,IntPos>
>::value R;
typedef typename LNot<typename LessThan<R,Divisor>::value>::value RGreaterEq;
typedef Cons<q,Cons<r,Nil> > Output;
public:
typedef typename Ternary<typename IntEqual<i,IntNeg>::value,
I<Output>,
DivMod<Dividend,Divisor,
typename BinaryBitwise<LOr,q,typename Ternary<RGreaterEq,
LeftShift<Int<True,IntPos>,Guardedi>,
I<IntPos>
>::value::value>::value,
typename Ternary<RGreaterEq,
Subtract<R,Divisor>,
I<R>
>::value::value,
typename Decrement<i>::value
> >::value::value value;
};
/*
* def isqrt(n,L=0,R=-1):
* #if(n<0):raise ValueError()
* #if(R==-1):R=n+1
* if(L==R-1):return(L)
* M=(L+R)//2
* return(isqrt(n,M if M*M<=n else L,R if M*M<=n else M))
*/
template<class Int1, class L, class R> struct BinSqrt{
private:
typedef typename Add<L,R>::value::tail M;
typedef typename GreaterThan<typename Multiply<M,M>::value,Int1>::value Check;
public:
typedef typename Ternary<typename IntEqual<L,typename Decrement<R>::value>::value,
I<L>,
BinSqrt<Int1,
typename Ternary<Check,L,M>::value,
typename Ternary<Check,M,R>::value
> >::value::value value;
};
/*
* def xgcd(a,b,prevx=1,x=0,prevy=0,y=1):
* if(b==0):return(a,prevx,prevy)
* Q=lambda prev,cur:prev-a//b*cur
* return(xgcd(b,a%b,x,Q(prevx,x),y,Q(prevy,y)))
*/
template<class Int1, class Modulus, class PrevX, class X, class PrevY, class Y> struct XGCD{
private:
template<class Prev, class Cur> struct Q;
typedef typename IsZero<Modulus>::value ModZero;
typedef Cons<Int1,Cons<PrevX,Cons<PrevY,Nil> > > Output;
template<class Prev, class Cur> struct Q{
typedef typename Subtract<Prev,typename Multiply<typename Ternary<ModZero,I<IntPos>,Divide<Int1,Modulus> >::value::value,Cur>::value>::value value;
};
public:
typedef typename Ternary<ModZero,
I<Output>,
XGCD<
Modulus,typename Ternary<ModZero,I<IntPos>,Modulo<Int1,Modulus> >::value::value,
X,typename Q<PrevX,X>::value,
Y,typename Q<PrevY,Y>::value
> >::value::value value;
};
}
namespace Math{
template<class Int1, class Int2> struct Min{
typedef typename Ternary<typename LessThan<Int1,Int2>::value,Int1,Int2>::value value;
};
template<class Int1, class Int2> struct Max{
typedef typename Ternary<typename GreaterThan<Int1,Int2>::value,Int1,Int2>::value value;
};
template<class Int1, class Int2> struct GCD{
private:
/* Anything But 0 */
typedef typename Ternary<typename IsZero<Int2>::value,IntNeg,Int2>::value Guarded2;
public:
typedef typename Ternary<typename IsZero<Int2>::value,
Abs<Int1>,
GCD<Int2,typename Modulo<Int1,Guarded2>::value>
>::value::value value;
};
template<class Int1, class Int2> struct LCM{
typedef typename Divide<typename Abs<typename Multiply<Int1,Int2>::value>::value,typename GCD<Int1,Int2>::value>::value value;
};
template<class Int1> struct IntSqrt{
private:
typedef typename Ternary<typename IsNegative<Int1>::value,Error<_impl_::ValueError>,I<True> >::value::value Check; /* Imaginary numbers are all in your head */
public:
typedef typename _impl_::BinSqrt<Int1,IntPos,typename Increment<Int1>::value>::value value;
};
/* def Power(x,y):return(((x if y&1 else 1)*Power(x*x,y//2)) if y>1 else (x if y>0 else 1)) */
template<class x, class y> struct Power{
private:
typedef typename Ternary<typename GreaterThan<y,Int<True,IntPos> >::value,Power<typename Multiply<x,x>::value,typename y::tail>,I<x> >::value::value BaseCase;
public:
typedef typename Ternary<typename GreaterThan<y,Int<True,IntPos> >::value,
Multiply<typename Ternary<typename y::head,x,Int<True,IntPos> >::value,BaseCase>,
Ternary<typename GreaterThan<y,IntPos>::value,x,Int<True,IntPos> >
>::value::value value;
};
template<class Int1> struct Factorial{
typedef typename FoldLeft<Multiply,typename Ternary<typename IsZero<Int1>::value,
I<Cons<Int<True,IntPos>,Nil> >,
Range<Int<True,IntPos>,Int1>
>::value::value,Int<True,IntPos> >::value value;
};
/* def PowerMod(x,y,m):x%=m;return(((x if y&1 else 1)*PowerMod(x*x,y//2,m)) if y>1 else (x if y>0 else 1)) */
template<class Base, class y, class m> struct PowerMod{
private:
typedef typename Modulo<Base,m>::value x;
typedef typename Ternary<typename GreaterThan<y,Int<True,IntPos> >::value,PowerMod<typename Multiply<x,x>::value,typename y::tail,m>,I<x> >::value::value BaseCase;
public:
typedef typename Modulo<typename Ternary<typename GreaterThan<y,Int<True,IntPos> >::value,
Multiply<typename Ternary<typename y::head,x,Int<True,IntPos> >::value,BaseCase>,
Ternary<typename GreaterThan<y,IntPos>::value,x,Int<True,IntPos> >
>::value::value,m>::value value;
};
template<class Int1, class Modulus> struct ExtendedGCD{
typedef typename _impl_::XGCD<Int1,Modulus,Int<True,IntPos>,IntPos,IntPos,Int<True,IntPos> >::value value;
};
template<class Int1, class Modulus> struct ModularInverse{
private:
typedef typename ExtendedGCD<Int1,typename Abs<Modulus>::value>::value EGCD;
typedef typename Ternary<typename IntEqual<Int<True,IntPos>,typename EGCD::car>::value,
I<True>,
Error<_impl_::ValueError> /* No modular multiplicative inverse exists */
>::value::value Check;
public:
typedef typename Ternary<Check,
Modulo<typename EGCD::cdr::car,Modulus>,
IntPos /* also err here if somehow */
>::value::value value;
};
}
}
namespace Rational{
template<class Numer, class Denom> struct Rational;
template<class Int1> struct ToRational;
template<class Rat1> struct Normalize;
template<class Rat1> struct Sign;
template<class Rat1> struct Negate;
template<class Rat1, class Rat2> struct RatEqual;
template<class Rat1, class Rat2> struct GreaterThan;
template<class Rat1, class Rat2> struct LessThan;
template<class Rat1, class Rat2> struct Add;
template<class Rat1, class Rat2> struct Subtract;
template<class Rat1, class Rat2> struct Multiply;
template<class Rat1> struct Reciprocal;
template<class LeftRat, class RightRat> struct Divide;
template<class Rat1> struct Floor;
template<class Rat1> struct Ceil;
//template<class Rat1> struct Round; /* Round up on tie */
template<class Rat1, class Int1> struct Power;
template<class Rat1, class Rat2> struct Mediant;
template<class Rat1, class Modulus> struct ToModular;
namespace Continued{
template<class Rat1> struct Continue;
template<class Cont> struct Discontinue;
}
template<class Numer, class Denom> struct Rational{
private:
typedef typename Ternary<typename Integer::IsZero<Denom>::value,Error<Integer::_impl_::DivideByZero>,I<True> >::value::value Check;
public:
typedef Numer numer;
typedef Denom denom;
};
template<class Int1> struct ToRational{
typedef Rational<Int1,Integer::Int<True,Integer::IntPos> > value;
};
template<class Rat> struct Sign{
typedef typename Ternary<typename Integer::IsZero<typename Rat::numer>::value,Integer::IntPos,typename Ternary<typename LXor<typename Integer::IsNegative<typename Rat::numer>::value,typename Integer::IsNegative<typename Rat::denom>::value>::value,typename Integer::IntNeg,typename Integer::Int<True,typename Integer::IntPos> >::value>::value value;
};
template<class Rat> struct Negate{
typedef Rational<typename Integer::Negate<typename Rat::numer>::value,typename Rat::denom> value;
};
template<class Rat1, class Rat2> struct RatEqual{
typedef typename Equal<typename Normalize<Rat1>::value,typename Normalize<Rat2>::value>::value value;
};
template<class Rat1, class Rat2> struct GreaterThan{
/* A/B > X/Y; A*Y/B > X; A*Y > B*X */
typedef typename Integer::GreaterThan<
typename Integer::Multiply<typename Rat1::numer,typename Rat2::denom>::value,
typename Integer::Multiply<typename Rat2::numer,typename Rat1::denom>::value
>::value value;
};
template<class Rat1, class Rat2> struct LessThan{
typedef typename GreaterThan<Rat2,Rat1>::value value;
};
template<class Rat> struct Normalize{
private:
typedef typename Rat::numer Numer;
typedef typename Rat::denom Denom;
typedef typename Integer::Math::GCD<Numer,Denom>::value GCD;
typedef typename Integer::Divide<Numer,GCD>::value NNumer;
typedef typename Integer::Divide<Denom,GCD>::value NDenom;
typedef typename Sign<Rat>::value Sign_;
public:
typedef Rational<
typename Integer::Normalize<typename Integer::Multiply<Sign_,typename Integer::Abs<NNumer>::value>::value>::value,
typename Integer::Normalize<typename Integer::Abs<NDenom>::value>::value
> value;
};
template<class Rat> struct Reciprocal{
typedef Rational<typename Rat::denom, typename Rat::numer> value;
};
template<class Rat1, class Rat2> struct Multiply{
typedef typename Normalize<Rational<
typename Integer::Multiply<typename Rat1::numer,typename Rat2::numer>::value,
typename Integer::Multiply<typename Rat1::denom,typename Rat2::denom>::value
> >::value value;
};
template<class Rat1, class Rat2> struct Divide{
typedef typename Multiply<Rat1,typename Reciprocal<Rat2>::value>::value value;
};
template<class Rat1, class Rat2> struct Add{
private:
typedef typename Rat1::numer A;
typedef typename Rat1::denom B;
typedef typename Rat2::numer C;
typedef typename Rat2::denom D;
public:
typedef typename Normalize<Rational<
typename Integer::Add<
typename Integer::Multiply<A,D>::value,
typename Integer::Multiply<C,B>::value
>::value,
typename Integer::Multiply<B,D>::value
> >::value value;
};
template<class Rat1, class Rat2> struct Subtract{
typedef typename Add<Rat1,typename Negate<Rat2>::value>::value value;
};
template<class Rat1> struct Floor{typedef typename Integer::Divide<typename Rat1::numer,typename Rat1::denom>::value value;};
template<class Rat1> struct Ceil{
private:
typedef typename Normalize<Rat1>::value Rat2;
public:
typedef typename Ternary<typename Integer::IntEqual<Integer::Int<True,Integer::IntPos>,typename Rat2::denom>::value,
typename Rat2::numer,
typename Integer::Increment<typename Floor<Rat2>::value>::value
>::value value;
};
template<class Rat1, class Int1> struct Power{
private:
typedef typename Integer::Abs<Int1>::value Abs1;
/* In the case it wasn't already in normal form,
* this protects against unnecessary integer ops. */
typedef typename Normalize<Rat1>::value Rat2;
typedef Rational<
typename Integer::Math::Power<typename Rat2::numer,Abs1>::value,
typename Integer::Math::Power<typename Rat2::denom,Abs1>::value
> Rat3;
public:
typedef typename Ternary<typename Integer::IsNegative<Int1>::value,
Reciprocal<Rat3>,
I<Rat3>
>::value::value value;
};
template<class Rat1, class Rat2> struct Mediant{
private:
/* Absolutely necessary here */
typedef typename Normalize<Rat1>::value Rat3;
typedef typename Normalize<Rat2>::value Rat4;
public:
typedef typename Normalize<Rational<
typename Integer::Add<typename Rat3::numer,typename Rat4::numer>::value,
typename Integer::Add<typename Rat3::denom,typename Rat4::denom>::value
> >::value value;
};
template<class Rat1, class Modulus> struct ToModular{
typedef typename Integer::Modulo<
typename Integer::Multiply<typename Rat1::numer,
typename Integer::Math::ModularInverse<typename Rat1::denom
,Modulus>::value>::value,Modulus>::value value;
};
namespace Continued{
/*
* # Big fan of this, but variadic
* #def Continue(numer,denom,*cont):
* # if(denom==0):return(cont)
* # return(Continue(denom,numer%denom,*cont,numer//denom))
*
* def Continue(numer,denom):
* if(denom==0):return([])
* return([numer//denom,*Continue(denom,numer%denom)])
*/
template<class Rat1> struct Continue{
private:
/* Implementation'd to allow checking if dividing by zero */
template<class Numer, class Denom> struct Implementation{
typedef typename Integer::IsZero<Denom>::value ZeroDenom;
/* So many guards I made a template! */
template<class ValuedObject> struct Guard{typedef typename Ternary<ZeroDenom,I<Nil>,ValuedObject>::value::value value;};
typedef typename Ternary<ZeroDenom,Nil,Cons< /* guard-ish */
typename Guard<Floor<Rational<Numer,Denom> > >::value,
typename Guard<Implementation<
Denom,
typename Guard<Integer::Modulo<Numer,Denom> >::value
> >::value
> >::value value;
};
typedef typename Normalize<Rat1>::value Rat2;
public:
typedef typename Implementation<typename Rat2::numer,typename Rat2::denom>::value value;
};
/*
* def Discontinue(cont):
* if(len(cont)==1):return(cont[0],1)
* Q=Discontinue(cont[1:])
* return(Q[1]+Q[0]*cont[0],Q[0])
*/
template<class ContFrac> struct Discontinue{
private:
typedef typename Equal<typename ContFrac::cdr,Nil>::value EOFrac;
typedef typename Ternary<EOFrac,I<Nil>,Discontinue<typename ContFrac::cdr> >::value::value Q;
typedef typename Ternary<EOFrac,ToRational<Integer::IntPos>,Reciprocal<Q> >::value::value ReciprocalQ;
public:
typedef typename Add<typename ToRational<typename ContFrac::car>::value,ReciprocalQ>::value value;
};
}
}
/* Can hold anything, adresses are designed to be positive integers. */
namespace Memory{
/* A zero indicates that Value is sought.
* Also all addresses are normalized to their absolute value. */
template<class Value, class ZeroBit, class OneBit> struct Memory;
struct NULLMemory;
template<class MemoryObject, class Address> struct MemoryLookup;
template<class MemoryObject, class Address, class NewValue> struct MemoryWrite;
template<class Value, class ZeroBit, class OneBit> struct Memory{
typedef Value value;
typedef ZeroBit zero;
typedef OneBit one;
};
struct NULLMemory{
typedef Integer::IntPos value;
typedef NULLMemory zero;
typedef NULLMemory one;
};
template<class MemoryObject, class Address> struct MemoryLookup{
private:
template<class MemObj, class Addr> struct Implementation;
template<class MemObj, class Addr> struct Implementation{
typedef typename Ternary<typename Equal<Addr,Integer::IntPos>::value,
I<MemObj>,
Ternary<typename Equal<MemObj,NULLMemory>::value,
I<Integer::IntPos>,
Implementation<typename Ternary<typename Addr::head,
typename MemObj::one,
typename MemObj::zero
>::value,typename Addr::tail
> > >::value::value::value value;
};
public:
typedef typename Implementation<MemoryObject,
typename Integer::Normalize<
typename Integer::Abs<Address
>::value>::value>::value value;
};
template<class MemoryObject, class Address, class Value> struct MemoryWrite{
private:
template<class MemObj, class Addr, class Val> struct Implementation;
template<class MemObj, class Addr, class Val> struct Implementation{
typedef typename Ternary<typename Equal<Addr,Integer::IntPos>::value,
I<Memory<Val,typename MemObj::zero,typename MemObj::one> >,
Implementation<typename Ternary<typename Addr::head,
typename MemObj::one,
typename MemObj::zero
>::value,typename Addr::tail,Val>
>::value::value NextMem;
typedef typename Ternary<typename Equal<Addr,Integer::IntPos>::value,
Memory<Val,typename MemObj::zero,typename MemObj::one>,
Memory<typename MemObj::value,
typename Ternary<typename Addr::head,typename MemObj::zero,NextMem>::value,
typename Ternary<typename Addr::head,NextMem,typename MemObj::one>::value
> >::value value;
};
public:
typedef typename Implementation<MemoryObject,
typename Integer::Normalize<
typename Integer::Abs<Address
>::value>::value,Value>::value value;
};
}
namespace LISP{
struct Lambda; template<class Parameter, class Body, class Environment> struct Closure;
//struct Car; struct Cdr; /* unneeded? */
template<class Name> struct Atom;
template<class ConsProgram, class AssocEnvironment> struct Evaluator;
/* this is such a f*king hack */
template<class Program, class Environment> struct Evaluator{
private:
template<class ConsArr, class Env> struct Implementation{
typedef typename ConsArr::car Car;
typedef typename ConsArr::cdr Cdr;
template<class Implementable> struct Implement{
typedef typename Implementable::template Implementation<typename Cdr::car,typename Cdr::cdr::car,Env>::value value;
};
template<class Function, class Argument> struct Applier{
typedef Cons<typename Evaluator<Function,Env>::value,Cons<Argument,Nil> > value;
};
typedef typename Ternary<typename Equal<Car,Nil>::value,
I<Nil>,
Evaluator<typename Ternary<typename IsCons<Car>::value,
Applier<Car,typename Cdr::car>,
Implement<Car>
>::value::value,Env>
>::value::value value;
};
public:
typedef typename Ternary<typename IsCons<Program>::value,
Implementation<Program,Environment>,
I<Program>
>::value::value value;
};
template<class Name> struct Atom{
template<class,class, class Environment> struct Implementation{
private:
typedef typename AssocLookup<Environment,Atom<Name> >::value NameValue;
public:
typedef typename Ternary<typename Equal<NameValue,Nil>::value,
Atom<Name>,
NameValue
>::value value;
};};
struct Lambda{
template<class Parameter, class Body, class Environment> struct Implementation{
typedef Closure<Parameter,Body,Environment> value;
};};
template<class Parameter, class Body, class DefEnv> struct Closure{
template<class Argument, class, class CallEnv> struct Implementation{
typedef typename Evaluator<Body,
typename AssocAdd<typename AssocJoin<CallEnv,DefEnv>::value,Parameter,Argument>::value
>::value value;
};};
}
namespace Lazy{
template<template<class> class Function, class ConsArr> struct Map;
template<template<class> class Predicate, class ConsArr> struct Filter;
/* Not lazy, but for posterity. */
template<template<class,class> class Function, class ConsArr, class InitialLHS> struct FoldLeft;
template<template<class> class Function, class ConsArr> struct Map{
private:
template<template<class> class Func, class Array> struct Implementation{
typedef typename Func<typename Array::car>::value car;
typedef typename Ternary<typename Equal<Nil,typename Array::cdr>::value,Nil,Implementation<Func,typename Array::cdr> >::value cdr;
};
public:
typedef Implementation<Function,ConsArr> value;
};
template<template<class> class Predicate, class ConsArr> struct Filter{
private:
/* yo dawg i heard you like helpers so i made some helpers for your helper */
template<template<class> class phi, class Array> struct Next{
typedef typename Array::car Car;
typedef typename Array::cdr Cdr;
typedef typename Ternary<typename phi<Car>::value,
I<I<Car> >,
Ternary<typename Equal<Cdr,Nil>::value,
I<Nil>,
Next<phi,Cdr>
> >::value::value::value value;
};
template<class Object, class Array> struct RestAfter{
typedef typename Array::cdr Cdr;
typedef typename Ternary<typename Equal<typename Array::car,Object>::value,
I<I<Cdr> >,
Ternary<typename Equal<Cdr,Nil>::value,
I<Nil>,
RestAfter<Object,Cdr>
> >::value::value::value value;
};
template<template<class> class phi, class Array> struct Implementation{
typedef typename Next<phi,Array>::value car;
typedef typename Ternary<typename Equal<typename Array::cdr,Nil>::value,
Nil,
Implementation<phi,typename RestAfter<car,Array>::value>
>::value cdr;
};
public:
typedef Implementation<Predicate,ConsArr> value;
};
template<template<class,class> class Function, class ConsArr, class LHS> struct FoldLeft{
private:
typedef typename Ternary<typename Equal<typename ConsArr::car,Nil>::value,I<LHS>,Function<LHS,typename ConsArr::car> >::value::value Applied;
public:
typedef typename Ternary<typename Equal<typename ConsArr::cdr,Nil>::value,
I<Applied>,
FoldLeft<Function, typename ConsArr::cdr, Applied>
>::value::value value;
};
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment