{-# OPTIONS_GHC -XTypeOperators #-}
{-# OPTIONS_GHC -fno-monomorphism-restriction #-}
import Prelude hiding ((.),(+))
import Data.List hiding (groupBy)
import Control.Applicative
import Control.Monad
import Control.Monad.State
import Control.Monad.List
import Control.Monad.Identity
import Control.Arrow
infix 8 ≡
infix 8 ⤴
infix 8 ↗
(.) = fmap
(<||>) = liftA2 (||)
(&) = liftM2 (,)
p << q = do x <- q ; p ; return x
message `should` assertion = if assertion then mzero else return ()
groupBy p [] = []
groupBy p (x:xs) = let (yes,no) = sift p (p x) (x:xs)
in yes : groupBy p no
sift p e = foldr sort ([],[])
where sort x (ys,ns) | e == p x = (x:ys,ns)
| otherwise = (ys,x:ns)
type Identifier = String
type Name = String
type Arity = Integer
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
type key :--> val = [(key,val)]
(k ~~> v) σ = (k,v):σ
-- type key -> val
(i --> t) σ = \e -> if e == Var i then t else σ e
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
data Term = Var Identifier | (Name,Arity):>[Term] deriving Eq
instance Show Term where
show (Var v) = v
show ((name,0):>[]) = name
show ((name,_):>args) = name ++ "(" ++ intercalate "," (show . args) ++ ")"
functor (f:>_) = f
variables (Var v) = [v] ; variables (_:>vs) = variables=<<vs
σ⤴ t = case σ t of p:>ps -> p:>(σ↗ps) ; v -> if t == v then t else σ⤴ v
σ↗ ts = (σ⤴).ts
i `occur` Var _ = False
i `occur` (_:>ts) = any ((== Var i) <||> (i `occur`)) ts
(p:>ps ≡ q:>qs) σ = do "Cyclic" `should` (p /= q) ; foldM unify σ (zip (σ↗ ps) (σ↗ qs))
(Var x ≡ t) σ = do "Occurs check" `should` (x `occur` (σ⤴ t)) ; return $ (x --> t) σ
(t ≡ Var x) σ = (Var x ≡ t) σ
unify σ (p,q) = (p ≡ q) σ
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
type Gensym k v m a = StateT (k :--> v,[v]) m a
withGensyms freshVariables = flip evalStateT ([],freshVariables)
names = flip replicateM ['A'..'Z'] =<< [1..]
gensym k = get >>= \(sto,g:gs) -> case lookup k sto of
Nothing -> do put ((k ~~> g) sto,gs) ; return g
Just v -> do return v
putSupply = modify . second . const
symScope p = get >>= runStateT p >>= \(v,s) -> putSupply (snd s) >> return v
copyTerm (Var v) = Var . gensym v
copyTerm (a:>as) = (a:>) . mapM copyTerm as
copyRule (p,q) = symScope (copyTerm p & mapM copyTerm q)
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
type Prolog m a = ListT (StateT (Identifier :--> Identifier,[Identifier]) m) a
--type Prolog m a = ListT (StateT (Identifier :--> Identifier,[Identifier]) (StateT Bool m)) a
type Database = [((Name, Arity), [(Term, [Term])])]
--cut = lift $ lift $ put True
--uncut = lift $ lift $ put False
--branch p q = do b <- lift $ lift $ get ; if b then p else q
clause :: Database -> (Name,Arity) -> Prolog Identity (Term, [Term])
clause db functor = ListT . mapM copyRule $ lookup' db functor
lookup' q db = maybe [] id (lookup db q)
(?-) :: (Database,Term -> Term) -> Term -> Prolog Identity (Term -> Term)
--(db,σ) ?- (("!",0):>[]) = do cut ; return σ
(db,σ) ?- query = do (head,body) <- clause db (functor query)
σ <- (head ≡ query) σ
foldM (prove db) σ body
prove db σ query = (db,σ) ?- (σ⤴ query)
runQuery db query = map (⤴ query).
runIdentity.
-- flip evalStateT False.
withGensyms (names \\ variables query).
runListT$
(db,id) ?- query
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
data Syntax = Term :- [Term]
makeRule (head :- body) = (functor head,[(head,body)])
mergeGroups ((functor,body):rest) = (functor,concat (body:map snd rest))
exampleDb :: Database
exampleDb = map mergeGroups $ groupBy fst $ map makeRule
[true :- [],
Var "X" == Var "X" :- [],
call(Var "P") :- [Var "P"],
and(Var "This",Var "That") :- [Var "This", Var "That"],
or(Var "This",Var "That") :- [Var "This"],
or(Var "This",Var "That") :- [Var "That"],
-- not(Var "P") :- [call(Var "P"), (!), fail],
-- not(Var "P") :- [],
flip(heads) :- [],
flip(tails) :- [],
n(z) :- [],
n(s(Var "N")) :- [n(Var "N")],
member(Var"E", Var "E" . Var "Xs") :- [],
member(Var"E", Var "X" . Var "Xs") :- [member(Var "E",Var "Xs")],
append(nil, Var "Ys",Var "Ys") :- [],
append(Var "X" . Var "XS",Var "YS",Var "X" . Var "Zs") :- [append(Var "XS",Var "YS",Var "Zs")]
] where true = ("true",0):>[];fail = ("fail",0):>[]
x==y = ("=",2):>[x,y]
call(p) = ("call",1):>[p];flip(p) = ("flip",1):>[p];not(p) = ("not",1):>[p]
(!) = ("!",0):>[];heads = ("heads",0):>[];tails = ("tails",0):>[]
and(p,q) = (",",2):>[p,q];or(p,q) = (";",2):>[p,q]
member(x,y) = ("member",2):>[x,y];append(x,y,z) = ("append",3):>[x,y,z]
nil = ("[]",0):>[];t . ts = (".",2):>[t,ts]
z = ("z",0):>[];s(x) = ("s",1):>[x];n(x) = ("n",1):>[x]
instance Show Syntax where
show (head :- []) = show head ++ "."
show (head :- body) = show head ++ " :- " ++ intercalate ", " (map show body) ++ "."
showDb = unlines (map show exampleDb)
------------------------------------------------------------------------------------------
Sunday, 27 July 2008
Interpreter for Prolog without cut
I thought this was a good way to write a Prolog interpreter but it is very hard to add cut to. How could it be done?
Wednesday, 23 July 2008
HOAS based self interpreter for lambda calculus
Just copied this out of Self-applicable Partial Evaluation for Pure Lambda Calculus
(define-syntax Q ; quote a lambda term
(syntax-rules (lambda)
((Q (lambda (x) M)) (lambda (a)
(lambda (b)
(lambda (c)
(a (lambda (x) (Q M)))))))
((Q (M N)) (lambda (a)
(lambda (b)
(lambda (c)
((b (Q M)) (Q N))))))
((Q x) (lambda (a)
(lambda (b)
(lambda (c)
(c x)))))))
(define E ; evaluate a quoted lambda term
((lambda (m)
((lambda (f) (m (lambda (a) ((f f) a))))
(lambda (f) (m (lambda (a) ((f f) a))))))
(lambda (E)
(lambda (t)
(((t (lambda (M) (lambda (x) (E (M x)))))
(lambda (M) (lambda (N) ((E M) (E N)))))
(lambda (x) x))))))
(define test-1
(E (Q (lambda (i) i))))
(define test-2
(E (Q (((lambda (m)
((lambda (f) (m (lambda (a) ((f f) a))))
(lambda (f) (m (lambda (a) ((f f) a))))))
(lambda (E)
(lambda (t)
(((t (lambda (M) (lambda (x) (E (M x)))))
(lambda (M) (lambda (N) ((E M) (E N)))))
(lambda (x) x)))))
(lambda (a) (lambda (b) (lambda (c) (a (lambda (i) (lambda (a) (lambda (b) (lambda (c) (c i)))))))))))))
; ((lambda (i) i) 'ok)
; ok
; > (test-1 'ok)
; ok
; > (test-2 'ok)
; ok
Saturday, 19 July 2008
Rascal - Mini-haskell like language
http://rascal-haskell.googlecode.com/files/Rascal.zip
http://code.google.com/p/rascal-haskell/source/checkout
Thank you to google for hosting this.
more code: http://code.google.com/p/janus-haskell/
more still: http://prolog-thoughts.googlecode.com/files/Prolog.zip
http://code.google.com/p/rascal-haskell/source/checkout
Thank you to google for hosting this.
more code: http://code.google.com/p/janus-haskell/
more still: http://prolog-thoughts.googlecode.com/files/Prolog.zip
Friday, 27 June 2008
How could I fix this line spacing?
The line spacing is huge now for no reason, how do I change it back? :/
not that anyone reads this anyway..
not that anyone reads this anyway..
Just a fun Show instance for functions
import Data.List
import Data.Maybe
import Control.Monad
import Control.Arrow
(*) `on` f = \x y -> f x * f y
class Inhabitants a where inhabitants :: [a]
instance Inhabitants () where inhabitants = [()]
instance Inhabitants Bool where inhabitants = [True,False]
instance (Inhabitants x, Inhabitants y) => Inhabitants (x,y) where inhabitants = liftM2 (,) inhabitants inhabitants
instance Inhabitants x => Inhabitants (Maybe x) where inhabitants = Nothing : map Just inhabitants
instance (Inhabitants p, Show p, Show q) => Show (p -> q) where
show f = "(fromJust . flip lookup " ++ show (map (id &&& f) inhabitants) ++ ")"
-- > not
-- (fromJust . flip lookup [(True,False),(False,True)])
-- > (fromJust . flip lookup [(True,False),(False,True)]) True
-- False
-- > \x -> Just Nothing
-- (fromJust . flip lookup [((),Just Nothing)])
-- > id
-- (fromJust . flip lookup [((),())])
-- > maybe not (&&)
-- (fromJust . flip lookup [(Nothing,(fromJust . flip lookup [(True,False),(False,True)])),(Just True,(fromJust . flip lookup [(True,True),(False,False)])),(Just False,(fromJust . flip lookup [(True,False),(False,False)]))])
Saturday, 21 June 2008
Pure Type Systems type checker in Prolog
They ( http://people.cs.uu.nl/andres/LambdaPi/index.html http://augustss.blogspot.com/2007/10/simpler-easier-in-recent-paper-simply.html ) said it was easy but actually it's very hard, of course these posts are very helpful though. My other reference is the book Lectures on the Curry-Howard Isomorphism (Studies in Logic and Foundations of Mathematics - Vol 149).
Assuming this doesn't have any bugs, does it..?
Assuming this doesn't have any bugs, does it..?
:- op(1200, xfx, :=).
:- op(150, xfx, ⊢).
:- op(140, xfx, :).
:- op(100, yfx, $).
sort(★).
sort(▢).
axiom(★,▢).
rule(★,★,★). % λ→
rule(★,▢,▢). % λP
rule(▢,★,★). % λ2
rule(▢,▢,▢). % λω
unfold(Term, TermU) :- unfold([],Term,TermU).
unfold(_, Sort, Sort) :- sort(Sort).
unfold(Γ, Ident, Value) :- member(Ident, Γ) -> Ident = Value ; ( Ident := ValueD ), unfold(ValueD, Value).
unfold(Γ, λ(Var:Type,Body), λ(Var:TypeU,BodyU)) :- unfold(Γ, Type, TypeU), unfold([Var|Γ], Body, BodyU).
unfold(Γ, π(Var:Type,Body), π(Var:TypeU,BodyU)) :- unfold(Γ, Type, TypeU), unfold([Var|Γ], Body, BodyU).
unfold(Γ, U $ V, P $ Q) :- unfold(Γ, U, P), unfold(Γ, V, Q).
alpha(X,Y) :- alpha([],X,Y).
alpha(_,Id,Id) :- !.
alpha(Γ,Var1,Var2) :- member(Var1=Var2,Γ).
alpha(Γ,λ(Var1:Type1,Body1), λ(Var2:Type2,Body2)) :- alpha(Γ,Type1,Type2), alpha([Var1=Var2|Γ],Body1,Body2).
alpha(Γ,π(Var1:Type1,Body1), π(Var2:Type2,Body2)) :- alpha(Γ,Type1,Type2), alpha([Var1=Var2|Γ],Body1,Body2).
alpha(Γ,U $ V,P $ Q) :- alpha(Γ,U,P), alpha(Γ,V,Q).
subst(X->Y,X,Y) :- !.
subst(_->_,Var,Var) :- atomic(Var).
subst(X->Y,λ(X:Type1,Body),λ(X:Type2,Body)) :- !, subst(X->Y,Type1,Type2).
subst(X->Y,λ(Z:Type1,Body1),λ(Z:Type2,Body2)) :- subst(X->Y,Type1,Type2), subst(X->Y,Body1,Body2).
subst(X->Y,π(X:Type1,Body),π(X:Type2,Body)) :- !, subst(X->Y,Type1,Type2).
subst(X->Y,π(Z:Type1,Body1),π(Z:Type2,Body2)) :- subst(X->Y,Type1,Type2), subst(X->Y,Body1,Body2).
subst(X->Y,U $ V,P $ Q) :- subst(X->Y,U,P), subst(X->Y,V,Q).
eval(λ(U:_,B) $ V, BetaVal) :- !, subst(U->V,B,Beta), eval(Beta,BetaVal).
eval(X $ Y, XY) :- !, eval(X,Xv), eval(Xv $ Y,XY).
eval(Value, Value).
type(Term, Type) :- unfold(Term,TermU), [] ⊢ TermU : Type.
hasType(Term, Type) :- type(Term, Type1), unfold(Type,TypeU), eval(TypeU, Type2), alpha(Type1,Type2).
_ ⊢ S1 : S2 :- axiom(S1,S2).
Γ ⊢ I : T :- once(member(I:T, Γ)).
Γ ⊢ λ(A:T,B) : π(A:Tv,C) :- Γ ⊢ T : S1, sort(S1), eval(T,Tv), [A:Tv|Γ] ⊢ B : C. %%, /* sanity checks: */ Γ ⊢ π(A:Tv,C) : S2, sort(S2).
Γ ⊢ π(A:T,B) : S :- Γ ⊢ T : S1, [A:T|Γ] ⊢ B : S2, rule(S1,S2,S).
Γ ⊢ P $ Q : T :- Γ ⊢ P : π(X:U,B), Γ ⊢ Q : V, alpha(U,V), eval(λ(X:U,B) $ Q,T).
id := λ(t:★, λ(x:t, x)).
idTy := π(x:★, π(e:x, x)).
const := λ(s:★, λ(t:★, λ(u:s, λ(v:t, u)))).
constTy := π(u:★, π(v:★, π(g0:u, π(g1:v, u)))).
%%bool := π(a:★, a -> a -> a).
bool := π(a:★, π(g1:a, π(g2:a, a))).
true := λ(a:★, λ(x:a, λ(y:a, x))).
false := λ(a:★, λ(x:a, λ(y:a, y))).
%%nat := π(u:★, u -> (u -> u) -> u).
nat := π(u:★, π(g1:u, π(g2:π(g3:u, u), u))).
zero := λ(a:★, λ(x:a, λ(f:π(g:a, a), x))).
%%succ := λ(n:nat, λ(a:★, λ(x:a, λ(f:(a -> a), f $ (n $ a $ x $ f))))).
succ := λ(n:nat, λ(a:★, λ(x:a, λ(f:π(g:a, a), f $ (n $ a $ x $ f))))).
add := λ(m:nat, λ(n:nat, m $ nat $ n $ succ)).
eq := λ(a:★, λ(x:a, λ(y:a,
λ(p:π(x:a, ★), π(g:p$x, p$y))))).
%%eq(a:★, x:a, y:a) := λ(p:π(x:a, ★), π(g:p$x, p$y)).
Labels:
Lambda Calculus,
Prolog,
PTS,
pure type systems,
type checking
Thursday, 19 June 2008
Proving RLE encoding and decoding in Coq
Require Import List.
Require Import ListPlus.
Set Implicit Arguments.
Notation "y <- x" := (x -> y) (at level 94, left associativity, only parsing).
Definition compose A B C (f : C <- B) (g : B <- A) := fun x => f (g x).
Infix "∘" := compose (at level 30, right associativity).
(*
* rle = map (length &&& head) ∘ group
* unrle = concat ∘ map (uncurry replicate)
*
* is it always true that (unrle ∘ rle) x = x?
*
* notice:
* rle = f ∘ f'
* unrle = g' ∘ g
*
*)
Theorem sandwich : forall I M O
(f : O <- M) (f' : M <- I)
(g : O -> M) (g' : M -> I),
(forall x, (f ∘ g ) x = x) ->
(forall x, (f' ∘ g') x = x) ->
(forall x, (f ∘ f' ∘ g' ∘ g) x = x).
Proof.
unfold compose; intros.
rewrite (H0 (g x)).
apply H.
Qed.
(*
* so all that must be proved now is
* forall x, (concat ∘ group) x = x
* /\ forall x, (map (uncurry replicate) ∘ map (length &&& head))
*
*)
Theorem map_fuse : forall A B C (f : C <- B) (g : B <- A),
forall x, (map f ∘ map g) x = map (f ∘ g) x.
Proof.
induction x.
reflexivity.
simpl; rewrite <- IHx.
reflexivity.
Qed.
(*
* Now we have "only" to prove
* forall x, (concat ∘ group) x = x
* /\ forall x, (uncurry replicate ∘ (length &&& head)) x = x
*
* This is actually impossible though,
* (uncurry replicate ∘ (length &&& head)) "foo" = "fff"
*
* The reason rle works is because group segments the list
* into *homogenous* chunks, if we knew the input to (length && head)
* was a homogenous list then it would be correct and provable.
* It needs access to this precondition though
*
*)
Theorem sandwich' : forall I M O
(P : M -> Prop)
(f : O <- M) (f' : M <- I)
(g : O -> M) (g' : M -> I),
(forall x, (f ∘ g ) x = x) ->
(forall x, P x -> (f' ∘ g') x = x) ->
(forall x, P (g x)) ->
(forall x, (f ∘ f' ∘ g' ∘ g) x = x).
Proof.
unfold compose; intros.
rewrite (H0 (g x)).
apply H.
apply H1.
Qed.
Inductive Homogenous A : listP A -> Prop :=
| HEnd : forall u, Homogenous (nilP u)
| HOne : forall u, Homogenous (u:~:nilP u)
| HAdd : forall u us, Homogenous (u:~:us) -> Homogenous (u:~:u:~:us).
Hint Constructors Homogenous.
Inductive All X (P : X -> Prop) : list X -> Prop :=
| AllNil : All P nil
| AllCons : forall x xs, P x -> All P xs -> All P (x::xs).
Hint Constructors All.
Section RLE.
Variable A : Type.
Variable eq_dec : forall x y : A, { x = y } + { x <> y }.
Definition head_consP X (e : X) (l : list (listP X)) :=
match l with
| nil => nil
| x::xs => (e:~:x)::xs
end.
Fixpoint group (l : list A) : list (listP A) :=
match l with
| nil => nil
| x::xs =>
match xs with
| nil => nilP x::nil
| y::ys =>
match eq_dec x y with
| left equal => head_consP x (group xs)
| right not_equal => nilP x::group xs
end
end
end.
Fixpoint concat (l : list (listP A)) : list A :=
match l with
| nil => nil
| x::xs => appP' x (concat xs)
end.
Definition crush (l : listP A) : (nat * A) := (lengthP l, headP l).
Definition expand (t : nat * A) : listP A := let (n,e) := t in replicateP n e.
Definition rle := map crush ∘ group.
Definition unrle := concat ∘ map expand.
Functional Scheme group_ind := Induction for group Sort Prop.
Lemma concat_group_inv : forall x, (concat ∘ group) x = x.
unfold compose.
intro x; functional induction (group x).
reflexivity.
reflexivity.
Lemma cat_cons : forall u v vs, concat (head_consP u (v::vs)) = u :: concat (v::vs).
destruct vs; reflexivity.
Qed.
destruct (group (y :: _x)).
inversion IHl.
rewrite cat_cons.
rewrite IHl.
reflexivity.
simpl in *.
rewrite IHl.
reflexivity.
Qed.
Lemma expand_crush_inv : forall x, Homogenous x -> (expand ∘ crush) x = x.
unfold compose.
induction x.
reflexivity.
intro; inversion H.
rewrite <- H2 in IHx.
reflexivity.
simpl in *.
rewrite <- H2 in *.
rewrite <- IHx.
reflexivity.
assumption.
Qed.
(*
* some notes I had to write to crack this lemma,
*
* group [] = []
* group [x] = [[x]]
* group (x:y:ys) = if x == y then headCons x (group (y:ys))
* else [x] : group (y:ys)
* where headCons x (y:ys) = (x:y):ys
*
* Theorem: forall xs, All Homogenous (group xs)
*
* group [] ~ trivial
* group [x] ~ trivial
* group (x:y:ys) = [x] : group (y:ys)
* homo ^ ^ homo by induction
*
* group (x:x:ys) = headCons x (group (x:xs))
*
* (group (x:xs)) = ((x:p):q)
* homogenous ^ ^ all homogenous by induction
*
* group (x:x:ys) = headCons x ((x:p):q)
* = ((x:x:p):q)
* homo cons ^
*)
Lemma group_homo : forall x, All (@Homogenous A) (group x).
induction x.
simpl; auto.
destruct x.
simpl; auto.
simpl.
destruct (eq_dec a a0).
rewrite <- e in *.
Lemma paper_plane : forall xs x,
exists p, exists q,
group (x::xs) = ((x:~:p)::q) \/ group (x::xs) = ((nilP x)::q).
induction xs.
simpl.
intro x; exists (nilP x); exists nil; auto.
intro x.
simpl.
destruct (eq_dec x a).
rewrite <- e in *; clear e a.
destruct (IHxs x).
destruct H.
destruct H.
simpl in H.
rewrite H.
simpl.
exists (x :~: x0).
exists x1.
left; reflexivity.
simpl in H.
rewrite H.
simpl.
exists (nilP x).
exists x1.
left; reflexivity.
destruct (IHxs a).
destruct H.
destruct H.
simpl in H.
destruct xs.
exists (nilP a).
exists (nilP a :: nil).
right; reflexivity.
rewrite H.
exists (nilP a).
exists ((a :~: x0) :: x1).
right; reflexivity.
simpl in H.
rewrite H.
exists (nilP a).
exists (nilP a :: x1).
right; reflexivity.
Qed.
pose (paper_plane x a).
inversion e0.
inversion H.
inversion H0.
rewrite H1 in IHx.
simpl in H1.
rewrite H1.
simpl.
apply AllCons.
apply HAdd.
inversion IHx; auto.
inversion IHx; auto.
rewrite H1 in IHx.
simpl in H1.
rewrite H1.
simpl.
apply AllCons.
apply HOne.
inversion IHx.
assumption.
apply AllCons.
auto.
apply IHx.
Qed.
Theorem rle_inv : forall x, unrle (rle x) = x.
intro; unfold unrle, rle.
apply sandwich' with (P := All (@Homogenous A)).
exact concat_group_inv.
clear x; intros; rewrite map_fuse; induction x.
reflexivity.
simpl.
inversion H.
rewrite (IHx H3).
rewrite (expand_crush_inv H2).
reflexivity.
exact group_homo.
Qed.
End RLE.
Require Import Arith.
Eval compute in (rle eq_nat_dec (1::2::3::3::3::5::5::5::1::1::1::6::6::6::6::6::nil)).
(*
* = (0, 1) :: (0, 2) :: (2, 3) :: (2, 5) :: (2, 1) :: (4, 6) :: nil
* : list (nat * nat)
*)
Eval compute in (unrle (rle eq_nat_dec (1::2::3::3::3::5::5::5::1::1::1::6::6::6::6::6::nil))).
(* = 1::2::3::3 ::3 ::5 ::5 ::5::1::1::1::6::6::6::6::6::nil
* : list nat
*)
Subscribe to:
Posts (Atom)