ladder-calculus/coq/bbencode.v

From Coq Require Import Strings.String.

Require Import terms.
Require Import subst.
Require Import smallstep.

Open Scope ladder_type_scope.
Open Scope ladder_expr_scope.


Definition bb_zero : expr_term := [{
  (Λ"α" ↦
  λ"s",(%"α"% -> %"α"%) ↦
  λ"z",(%"α"%) ↦
  %"z"%)
  as $"ℕ"$~$"BBNat"$
}].

Definition bb_one : expr_term := [{
  (Λ"α" ↦
  λ"s",(%"α"% -> %"α"%) ↦
  λ"z",(%"α"%) ↦
  (%"s"% %"z"%))
  as $"ℕ"$~$"BBNat"$
}].

Definition bb_two : expr_term := [{
  (Λ"α" ↦
  λ"s",(%"α"% -> %"α"%) ↦
  λ"z",(%"α"%) ↦
  (%"s"% (%"s"% %"z"%)))
  as $"ℕ"$~$"BBNat"$
}].

Definition bb_succ : expr_term := [{
  λ"n",$"ℕ"$
      ~$"BBNat"$
      ~(∀"β",(%"β'"%->%"β"%)->%"β"%->%"β"%)
      ↦
    ((Λ"α" ↦
      λ"s",((%"α"%->%"α"%)->%"α"%->%"α"%) ↦
      λ"z",%"α"% ↦
      (%"s"% ((%"n"% # %"α"%) %"s"% %"z"%)))
      as $"ℕ"$~$"BBNat"$)
}].

Example  example_reduction :
    (expr_app bb_succ bb_one) -->β* bb_two
.
Proof.

  apply Multi_Step with (y:=[{
    (λ"n",$"ℕ"$
        ~$"BBNat"$
        ~(∀"β",(%"β'"%->%"β"%)->%"β"%->%"β"%)
        ↦
      ((Λ"α" ↦
        λ"s",((%"α"%->%"α"%)->%"α"%->%"α"%) ↦
        λ"z",%"α"% ↦
        (%"s"% ((%"n"% # %"α"%) %"s"% %"z"%)))
        as $"ℕ"$~$"BBNat"$))

    (Λ"β" ↦
     λ"s",(%"β"% -> %"β"%) ↦
     λ"z",(%"β"%) ↦
      (%"s"% %"z"%))
      as $"ℕ"$~$"BBNat"$
  }]).
Admitted.
(*
  apply E_Alpha.
  apply E_App2.
  apply EAlpha_Rename.

  apply Multi_Step with (y:=[{
      (Λ"α" ↦
        λ"s",((%"α"%->%"α"%)->%"α"%->%"α"%) ↦
        λ"z",%"α"% ↦
        (%"s"% (
        (((Λ"β" ↦
          λ"s",(%"β"% -> %"β"%) ↦
          λ"z",(%"β"%) ↦
          (%"s"% %"z"%)) as $"ℕ"$~$"BBNat"$)
          # %"α"%) %"s"% %"z"%)))
    as $"ℕ"$~$"BBNat"$ }]).

  apply E_AppLam.

  apply Multi_Step with (y:=[{
      (Λ"α" ↦
        λ"s",((%"α"%->%"α"%)->%"α"%->%"α"%) ↦
        λ"z",%"α"% ↦
        (%"s"% (
        (((Λ"α'" ↦
          λ"s",(%"α'"% -> %"α'"%) ↦
          λ"z",(%"α'"%) ↦
          (%"s"% %"z"%)) as $"ℕ"$~$"BBNat"$)
          # %"α"%) %"s"% %"z"%)))
    as $"ℕ"$~$"BBNat"$ }]).
  }].
Qed.
*)

Compute     (expr_app bb_succ bb_zero) -->β bb_one.