ImplicitFuck.scala

package implicitfuck;
import metascala.Nats._;
import metascala.TLists._;

object ImplicitFuck {
  type < = _0 // Left
  type > = _1 // Right
  type |# = _2 // while
  type #| = _3 // end while
  type + = _4 // inc
  type - = _5 // dec
  type ! = _6 // show
  type ? = _7 // get
  
  class State[
    Prog, // Code to be executed
    LTape, // Left tape stack
    Ptr, // element I'm pointing to
    RTape, // right tape
    Input, // input list
    Output,
    State]; // output list

  // end of the recursive execution
  implicit def end[
    Tape<:TList,
    Ptr<:Nat,
    RTape<:TList,
    Input<:TList] = new State[TNil, Tape, Ptr, RTape, Input, TNil, TNil];

  implicit def left[
    PRest<:TList,
    L<:Nat, LRest<:TList,
    Ptr<:Nat,
    RTape<:TList,
    Input<:TList,
    Output<:TList,
    Stack<:TList] (implicit state: State[PRest, LRest, L, Ptr::RTape, Input, Output, Stack]) = {
    new State[< :: PRest, L::LRest, Ptr, RTape, Input, Output, Stack];
  }

  implicit def right[
    PRest<:TList,
    LTape<:TList,
    Ptr<:Nat,
    R<:Nat, RRest<:TList,
    Input<:TList,
    Output<:TList,
    Stack<:TList](implicit state: State[PRest, Ptr::LTape, R,RRest, Input, Output, Stack]) = {
    new State[> :: PRest, LTape, Ptr, R::RRest, Input, Output, Stack];
  }

/* Makes scala sad.
  // so we can hallucinate an infinite tape.
  implicit def rightOnEmpty[
    PRest<:TList,
    LTape<:TList,
    Ptr<:Nat,
    Input<:TList,
    Output<:TList,
    Stack<:TList](implicit state: State[PRest, Ptr::LTape, _0, _0 :: TNil, Input, Output, Stack]) = {
    new State[> :: PRest, LTape, Ptr, TNil, Input, Output, Stack];
  }
*/


/*
  implicit def end_|# [
    LoopBody<:TList,
    PRest<:TList,
    LTape<:TList,
    RTape<:TList,
    Input<:TList,
    Output<:TList,
    S, Stack<:TList](implicit removePrefix: RemoveMatched[ |#, #|, LoopBody, |# :: LoopBody :: PRest,_0], state: State[PRest, LTape, _0, RTape, Input, Output, Stack]) = {
    new State[ |# :: (LoopBody ::: PRest), LTape, _0, RTape, Input, Output, S :: Stack];
  }
  */


  implicit def loop_|# [
    PRest<:TList,
    LTape<:TList,
    Ptr<:Succ[_],
    RTape<:TList,
    Input<:TList,
    Output<:TList,
    Stack<:TList](implicit state: State[PRest, LTape, Ptr, RTape, Input, Output, PRest :: Stack]) = {
    new State[ |# :: PRest, LTape, Ptr, RTape, Input, Output, Stack];
  }

  implicit def loop_#| [
    PRest<:TList,
    LTape<:TList,
    Ptr <: Succ[_],
    RTape<:TList,
    Input<:TList,
    Output<:TList,
    S, Stack<:TList](implicit state: State[S, LTape, Ptr, RTape, Input, Output, S :: Stack]) = {
    new State[ #| :: PRest, LTape, Ptr, RTape, Input, Output, S :: Stack];
  }

  implicit def end_#| [
    PRest<:TList,
    LTape<:TList,
    RTape<:TList,
    Input<:TList,
    Output<:TList,
    S, Stack<:TList](implicit state: State[PRest, LTape, _0, RTape, Input, Output, Stack]) = {
    new State[ #| :: PRest, LTape, _0, RTape, Input, Output, S :: Stack];
  }


  implicit def inc[
    PRest<:TList,
    LTape<:TList,
    Ptr<:Nat,
    RTape<:TList,
    Input<:TList,
    Output<:TList,
    Stack<:TList](implicit state: State[PRest, LTape, Succ[Ptr],RTape, Input, Output, Stack]) = {
    new State[+ :: PRest, LTape, Ptr, RTape, Input, Output, Stack];
  }

  implicit def dec[
    PRest<:TList,
    LTape<:TList,
    Ptr<:Nat,
    RTape<:TList,
    Input<:TList,
    Output<:TList,
    Stack<:TList](implicit state: State[PRest, LTape, Ptr#Pre, RTape, Input, Output, Stack]) = {
    new State[- :: PRest, LTape, Ptr, RTape, Input, Output, Stack];
  }

  implicit def show[
    PRest<:TList,
    LTape<:TList,
    Ptr<:Nat,
    RTape<:TList,
    Input<:TList,
    Output<:TList,
    Stack<:TList](implicit state: State[PRest, LTape, Ptr, RTape, Input, Output, Stack]) = {
    new State[! :: PRest, LTape, Ptr, RTape, Input, Ptr :: Output, Stack];
  }

  implicit def get[
    PRest<:TList,
    LTape<:TList,
    Ptr<:Nat,
    RTape<:TList,
    I<:Nat, IRest<:TList,
    Output<:TList,
    Stack<:TList](implicit state: State[PRest, LTape, I,RTape, IRest, Output, Stack]) = {
    new State[? :: PRest, LTape, Ptr, RTape, I::IRest, Output, Stack];
  }

  type EmptyTape = _0 :: _0 :: _0 :: TNil;
  //type EmptyTape = TNil;

  def brainfuck[Prog<:TList, Input, Output<:TList, Stack<:TList](prog:Prog, in: Input)(implicit state: State[Prog, TNil, _0, EmptyTape, Input, Output, Stack]):Output = null.asInstanceOf[Output];

  object Test {
    type Prog = ! :: (>) :: (+) :: (!) :: TNil;
    //type Prog = (>) :: TNil;
    type Input = TNil;
    brainfuck(new Prog, new Input)
  }
}