Ответ 1

Я использую ваш вопрос в качестве предлога для улучшения и демонстрации a Haskell библиотека отслеживания звонков Я работаю на. В контексте трассировка, очевидным способом создания дерева доказательств является отслеживание типа и затем отформатировать трассировку как доказательство естественного вычета. к все в порядке вещей, мой пример логики - просто типизированная лямбда исчисление (STLC), что соответствует импликационному фрагменту пропозиционального интуиционистский логика.

Я использую proofs.sty, но не через HaTeX или любой другой Haskell Латексная библиотека. Латекс для деревьев доказательств очень прост и использует Библиотека Haskell Latex просто усложнит ситуацию.

Я дважды написал код генерации доказательства:

• автономным способом, написав средство проверки типов, которое также возвращает дерево доказательств;

• используя мою библиотеку трассировки, путем трассировки вызова проверки типа, а затем после обработки трассировки в дерево доказательств.

Поскольку вы не спрашивали о библиотеках трассировки вызовов, вы можете быть меньше заинтересованы в версии на основе трассировки вызовов, но я думаю, что это интересно сравнить обе версии.

Примеры

Сначала начнем с некоторых примеров вывода, чтобы узнать, что все это нам доставит. Первые три примера мотивированы система аксиом для импликационного высказывания Исчисление; первые два также соответствуют S и K:

• Первая аксиома K с доказательными терминами:

• Вторая аксиома S с доказательными условиями, но с предположениями в контекст, а не lambda bound:

• Четвертая аксиома, modus ponens, без доказательств:

Третья аксиома в этой статье в Википедии (закон Пирса) неконструктивным, и поэтому мы не можем это доказать здесь.

Для другого рода примера, здесь неудачная проверка типа Y Комбинатор:

Стрелки предназначены для того, чтобы привести к ошибке, которая отмечена bang (!).

Код

Теперь я опишу код, который создал эти примеры. Код от this файл если иное не отмечено. Я не включаю здесь каждую строку кода; см. эту ссылку, если вы хотите что-то, что вы можете построить с помощью GHC 7.6.3.

Большая часть кода - грамматика, парсер и красивый принтер - это одинаковые для обеих версий; только контролеры типов и дерево доказательств генераторы различаются. Весь общий код находится в файле только ссылка.

грамматика STLC

Грамматика STLC в ASCII:

-- Terms
e ::= x | \x:T.e | e e
-- Types
T ::= A | T -> T
-- Contexts
C ::= . | C,x:T

И соответствующий Haskell:

type TmVar = String
type TyVar = String
data Tm = Lam TmVar Ty Tm
        | TmVar TmVar
        | Tm :@: Tm
  deriving Show
data Ty = TyVar TyVar
        | Ty :->: Ty
  deriving (Eq , Show)
type Ctx = [(TmVar,Ty)]

Проверка типа + генерация дерева доказательств

Обе версии реализуют один и тот же абстрактный STLC-тип проверки. В ASCII:

(x:T) in C
---------- Axiom
C |- x : T

C,x:T1 |- e : T2
--------------------- -> Introduction
C |- \x:T1.e : T1->T2

C |- e : T1 -> T2    C |- e1 : T1
--------------------------------- -> Elimination
C |- e e1 : T2

Версия 1: автономная с встроенным построением дерева доказательств

Полный код для этой версии здесь.

Генерация дерева доказательств происходит в контроле типа, но фактическое код генерации кода доказательств учитывается в addProof и conclusion.

Проверка типов

-- The mode is 'True' if proof terms should be included.
data R = R { _ctx :: Ctx , _mode :: Bool }
type M a = Reader R a

extendCtx :: TmVar -> Ty -> M a -> M a
extendCtx x t = local extend where
  extend r = r { _ctx = _ctx r ++ [(x,t)] }

-- These take the place of the inferred type when there is a type
-- error.
here , there :: String
here = "\\,!"
there = "\\,\\uparrow"

-- Return the inferred type---or error string if type inference
-- fails---and the latex proof-tree presentation of the inference.
--
-- This produces different output than 'infer' in the error case: here
-- all premises are always computed, whereas 'infer' stops at the
-- first failing premise.
inferProof :: Tm -> M (Either String Ty , String)
inferProof [email protected](Lam x t e) = do
  (et' , p) <- extendCtx x t . inferProof $ e
  let et'' = (t :->:) <$> et'
  addProof et'' [p] tm
inferProof [email protected](TmVar x) = do
  mt <- lookup x <$> asks _ctx
  let et = maybe (Left here) Right mt
  addProof et [] tm
inferProof [email protected](e :@: e1) = do
  (et , p) <- inferProof e
  (et1 , p1) <- inferProof e1
  case (et , et1) of
    (Right t , Right t1) ->
      case t of
        t1' :->: t2 | t1' == t1 -> addProof (Right t2)   [p , p1] tm
        _ ->                       addProof (Left here)  [p , p1] tm
    _ ->                           addProof (Left there) [p , p1] tm

Генерация дерева доказательств

addProof соответствует proofTree в другой версии:

-- Given the inferred type, the proof-trees for all premise inferences
-- (subcalls), and the input term, annotate the inferred type with a
-- result proof tree.
addProof :: Either String Ty -> [String] -> Tm -> M (Either String Ty , String)
addProof et premises tm = do
  R { _mode , _ctx } <- ask
  let (judgment , rule) = conclusion _mode _ctx tm et
  let tex = "\\infer[ " ++ rule ++ " ]{ " ++
            judgment ++ " }{ " ++
            intercalate " & " premises ++ " }"
  return (et , tex)

Код для conclusion является общим для обеих версий:

conclusion :: Mode -> Ctx -> Tm -> Either String Ty -> (String , String)
conclusion mode ctx tm e = (judgment mode , rule tm)
  where
    rule (TmVar _) = "\\textsc{Axiom}"
    rule (Lam {}) = "\\to \\text{I}"
    rule (_ :@: _) = "\\to \\text{E}"

    tyOrError = either id pp e

    judgment True = pp ctx ++ " \\vdash " ++ pp tm ++ " : " ++ tyOrError
    judgment False = ppCtxOnlyTypes ctx ++ " \\vdash " ++ tyOrError

Версия 2: посредством трассировки вызова, с генерированием дерева доказательств в качестве пост-обработки

Здесь средство проверки типов даже не знает о генерации дерева доказательств и добавление трассировки вызова - это всего лишь одна строка.

Проверка типов

type Mode = Bool
type Stream = LogStream (ProofTree Mode)
type M a = ErrorT String (ReaderT Ctx (Writer Stream)) a

type InferTy = Tm -> M Ty
infer , infer' :: InferTy
infer = simpleLogger (Proxy::Proxy "infer") ask (return ()) infer'

infer' (TmVar x) = maybe err pure . lookup x =<< ask where
  err = throwError $ "Variable " ++ x ++ " not in context!"
infer' (Lam x t e) = (t :->:) <$> (local (++ [(x,t)]) . infer $ e)
infer' (e :@: e1) = do
  t <- infer e
  t1 <- infer e1
  case t of
    t1' :->: t2 | t1' == t1 -> pure t2
    _ -> throwError $ "Can't apply " ++ show t ++ " to " ++ show t1 ++ "!"

LogStream типа и proofTree класс из библиотеки. LogStream - это тип событий журнала, которые магия " simpleLogger журналы. Обратите внимание на строку

infer = simpleLogger (Proxy::Proxy "infer") ask (return ()) infer'

который определяет infer как зарегистрированную версию infer', фактический тип проверки. Это все, что вам нужно для отслеживания монадической функции!

Я не буду понимать, как simpleLogger действительно работает здесь, но результатом является то, что каждый вызов infer регистрируется, включая контекст, аргументы и возвращаемое значение, и эти данные группируются вместе со всеми зарегистрированными подколями (здесь только до infer). Это было бы легко записать такой код регистрации для infer, но это приятно что с библиотекой вам не нужно.

Генерация дерева доказательств

Чтобы сгенерировать деревья с доказательством Латекса, мы реализуем proofTree для публикации процесс infer трассировка вызова. Библиотека предоставляет proofTree функция, которая вызывает методы proofTree и собирает доказательство деревья; нам просто нужно указать, как заключаются наборы текста суждения будут отформатированы:

instance ProofTree Mode (Proxy (SimpleCall "infer" Ctx InferTy ())) where
  callAndReturn mode t = conclusion mode ctx tm (Right ty)
    where
      (tm , ()) = _arg t
      ty = _ret t
      ctx = _before t
  callAndError mode t = conclusion mode ctx tm (Left error)
    where
      (tm , ()) = _arg' t
      how = _how t
      ctx = _before' t
      error = maybe "\\,!" (const "\\,\\uparrow") how

Вызовы pp относятся к определенному пользователем принтеру; очевидно, библиотека не умеет печатать ваши типы данных.

Поскольку вызовы могут быть ошибочными - библиотека обнаруживает ошибки - мы должны сказать, как отформатировать успешных и неудачных вызовов. См. Пример выше Y-combinator для примера, проверка отказа, соответствующая callAndError здесь.

библиотека proofTree функция довольно просто: он создает дерево доказательства proofs.sty с текущим вызывать как заключение, а субколлами как помещения:

proofTree :: mode -> Ex2T (LogTree (ProofTree mode)) -> String
proofTree mode (Ex2T [email protected](CallAndReturn {})) =
  "\\infer[ " ++ rule ++ " ]{ " ++ conclusion ++ " }{ " ++ intercalate " & " premises ++ " }"
  where
    (conclusion , rule) = callAndReturn mode t
    premises = map (proofTree mode) (_children t)
proofTree mode (Ex2T [email protected](CallAndError {})) =
  "\\infer[ " ++ rule ++ " ]{ " ++ conclusion ++ " }{ " ++ intercalate " & " premises ++ " }"
  where
    (conclusion , rule) = callAndError mode t
    premises = map (proofTree mode)
                   (_children' t ++ maybe [] (:[]) (_how t))

Я использую proofs.sty в библиотеке, потому что он допускает сколь угодно много помещения, хотя bussproofs.sty будет работать для этого примера STLC поскольку ни одно правило не имеет более пяти помещений (предел для bussproofs). Оба пакета Latex описаны здесь.

Довольно печать

Теперь мы возвращаемся к коду, который является общим для обеих версий.

Симпатичный принтер, который определяет pp, использованный выше, довольно длинный - он обрабатывает приоритет и ассоциативность и записывается таким образом, что должен быть расширяемым, если больше условий, например. продуктов, добавляются к исчисление - но в основном прямолинейное. Во-первых, мы создали приоритет таблицы и знака с приоритетом и ассоциативностью:

- Precedence: higher value means tighter binding.
type Prec = Double

between :: Prec -> Prec -> Prec
between x y = (x + y) / 2

lowest , highest , precLam , precApp , precArr :: Prec
highest = 1
lowest = 0
precLam = lowest
precApp = between precLam highest
precArr = lowest

-- Associativity: left, none, or right.
data Assoc = L | N | R deriving Eq

-- Wrap a pretty print when the context dictates.
wrap :: Pretty a => Assoc -> a -> a -> String
wrap side ctx x = if prec x `comp` prec ctx
                  then pp x
                  else parens . pp $ x
  where
    comp = if side == assoc x || assoc x == N
           then (>=)
           else (>)
    parens s = "(" ++ s ++ ")"

И затем мы определяем отдельные симпатичные принтеры:

class Pretty t where
  pp :: t -> String
  prec :: t -> Prec
  prec _ = highest
  assoc :: t -> Assoc
  assoc _ = N

instance Pretty Ty where
  pp (TyVar v) = v
  pp [email protected](t1 :->: t2) = wrap L t t1 ++ " {\\to} " ++ wrap R t t2
  prec (_ :->: _) = precArr
  prec _ = highest
  assoc (_ :->: _) = R
  assoc _ = N

instance Pretty Tm where
  pp (TmVar v) = v
  pp (Lam x t e) = "\\lambda " ++ x ++ " {:} " ++ pp t ++ " . " ++ pp e
  pp [email protected](e1 :@: e2) = wrap L e e1 ++ " " ++ wrap R e e2
  prec (Lam {}) = precLam
  prec (_ :@: _) = precApp
  prec _ = highest
  assoc (_ :@: _) = L
  assoc _ = N

instance Pretty Ctx where
  pp [] = "\\cdot"
  pp [email protected](_:_) =
    intercalate " , " [ x ++ " {:} " ++ pp t | (x,t) <- ctx ]

Добавив аргумент "mode", было бы легко использовать тот же красивый принтер для печати простой ASCII, что было бы полезно с другими обработчики пост-трассировки вызова, такие как (незавершенный) UnixTree процессор.

Синтаксический

Парсер не является существенным для примера, но, конечно, я не входил в введите исходные термины непосредственно как Haskell Tm s.

Вспомните грамматику STLC в ASCII:

-- Terms
e ::= x | \x:T.e | e e
-- Types
T ::= A | T -> T
-- Contexts
C ::= . | C,x:T

Эта грамматика неоднозначна: как термин application e e и тип функции T -> T не имеют ассоциативности, заданной грамматика. Но в терминах STLC применение ассоциативно и функции типы являются правильными ассоциативными, и поэтому соответствующие неоднозначные грамматика, которую мы фактически разбираем,

-- Terms
e ::= e' | \x:T.e | e e'
e' ::= x | ( e )
-- Types
T ::= T' | T' -> T
T' ::= A | ( T )
-- Contexts
C ::= . | C,x:T

Парсер, возможно, слишком прост - я не использую languageDef и он прост в использовании - но он выполняет свою работу:

type P a = Parsec String () a

parens :: P a -> P a
parens = Text.Parsec.between (char '(') (char ')')

tmVar , tyVar :: P String
tmVar = (:[]) <$> lower
tyVar = (:[]) <$> upper

tyAtom , arrs , ty :: P Ty
tyAtom = parens ty
     <|> TyVar <$> tyVar
arrs = chainr1 tyAtom arrOp where
  arrOp = string "->" *> pure (:->:)
ty = arrs

tmAtom , apps , lam , tm :: P Tm
tmAtom = parens tm
     <|> TmVar <$> tmVar
apps = chainl1 tmAtom appOp where
  appOp = pure (:@:)
lam = uncurry Lam <$> (char '\\' *> typing)
                  <*> (char '.' *> tm)
tm = apps <|> lam

typing :: P (TmVar , Ty)
typing = (,) <$> tmVar
             <*> (char ':' *> ty)

ctx :: P Ctx
ctx = typing `sepBy` (char ',')

Чтобы выяснить, как выглядят исходные условия, приведены примеры из Makefile:

#           OUTFILE  CONTEXT                TERM
./tm2latex.sh S.ctx  'x:P->Q->R,y:P->Q,z:P' 'xz(yz)'
./tm2latex.sh S.lam  ''                     '\x:P->Q->R.\y:P->Q.\z:P.xz(yz)'
./tm2latex.sh S.err  ''                     '\x:P->Q->R.\y:P->Q.\z:P.xzyz'
./tm2latex.sh K.ctx  'x:P,y:Q'              'x'
./tm2latex.sh K.lam  ''                     '\x:P.\y:Q.x'
./tm2latex.sh I.ctx  'x:P'                  'x'
./tm2latex.sh I.lam  ''                     '\x:P.x'
./tm2latex.sh MP.ctx 'x:P,y:P->Q'           'yx'
./tm2latex.sh MP.lam ''                     '\x:P.\y:P->Q.yx'
./tm2latex.sh ZERO   ''                     '\s:A->A.\z:A.z'
./tm2latex.sh SUCC   ''                     '\n:(A->A)->(A->A).\s:A->A.\z:A.s(nsz)'
./tm2latex.sh ADD    '' '\m:(A->A)->(A->A).\n:(A->A)->(A->A).\s:A->A.\z:A.ms(nsz)'
./tm2latex.sh MULT   '' '\m:(A->A)->(A->A).\n:(A->A)->(A->A).\s:A->A.\z:A.m(ns)z'
./tm2latex.sh Y.err  ''                        '\f:A->A.(\x:A.f(xx))(\x:A.f(xx))'
./tm2latex.sh Y.ctx  'a:A->(A->A),y:(A->A)->A' '\f:A->A.(\x:A.f(axx))(y(\x:A.f(axx)))'

Генерация документа Latex

./tm2latex.sh script просто вызывает pdflatex на выходе Haskell, описанные выше. Программы Haskell дают доказательство дерево, а затем оберните его в минимальный документ латекс:

unlines
  [ "\\documentclass[10pt]{article}"
  , "\\usepackage{proof}"
  , "\\usepackage{amsmath}"
  , "\\usepackage[landscape]{geometry}"
  , "\\usepackage[cm]{fullpage}"
  -- The most slender font I could find:
  -- http://www.tug.dk/FontCatalogue/iwonalc/
  , "\\usepackage[light,condensed,math]{iwona}"
  , "\\usepackage[T1]{fontenc}"
  , "\\begin{document}"
  , "\\tiny"
  , "\\[" ++ tex ++ "\\]"
  , "\\end{document}"
  ]

Как вы можете видеть, большая часть латекса посвящена созданию деревьев доказательств как можно меньше; Я планирую также написать столбец дерева ASCII-доказательств процессор, который может быть более полезным на практике, когда примеры больше.

Заключение

Как всегда, для написания парсера, проверки типа и кода требуется немного кода. симпатичный принтер. Кроме того, добавление генерации доказательств довольно просто в обеих версиях. Это забавный игрушечный пример, но я ожидают сделать что-то подобное в контексте "реального", унифицированный метод проверки типов для языка с зависимым от языка; там Я ожидаю, что трассировка вызова и создание дерева доказательств (в ASCII) обеспечит значительная помощь в отладке проверки типов.