[Haskell-cafe] Fwd: representing institutions in haskell
Till Mossakowski
till at iws.cs.uni-magdeburg.de
Sat May 28 14:33:24 UTC 2016
Dear Rick,
actually, in the Hets system [1], which is one of the largest Haskell
programs, we have represented logics as institutions since 2002. Hets
comprises of about 25 logics represented as institutions, including
propositional logic, first-order logic, higher-oder logic, modal logic,
OWL, and even some functional programming language. Hets provides
parsing, static analysis, and proof management for logical theories
formulated within these institutions (and also heterogeneous theories
spanning several institutions). Interfaces to various theorem provers,
SAT solvers and model finders are included.
Hets' input language is the Distributed Ontology, Model and
Specification language (DOL) [2], which has been standardized by the
Object Management Group (OMG).
More specifically, Hets employs a type class "Category" for representing
categories, with functions for identities, domain, codomain and
composition. On top of this, institutions form a multi-parameter type
class "Logic", with a representation of signatures and signature
morphisms as a category. The set of sentences is represented as one
parameter type. This is a pragmatic decision, since in most
institutions, sentences are uniform over signatures, and making this
dependent on signature would be much more complicated. But many
functions on sentences depend on a signature. Sentence translation along
a signature morphism is represented by a function of the type class as
well. Models and satisfaction are generally not represented due to their
(in general) infinitary nature. But in some case, we represent models as
certain theories, e.g. when processing the output of some model finder.
Such models can even be translated using institution comorphisms.
That said, we are interested in improving the representations of
institutions in Hets, e.g. by making more using some libraries for
category theory that have not been available in 2002 when we started Hets.
However, I must admit that I did not understand your representation,
Rick. Could you explain its general principles?
What is the purpose of having "data Sign a = Sign a"? Why do conjunction
and disjunction play such a role, given that there are institutions like
equational logic that neither have conjunction nor disjunction?
I could I execute your code, neither with ghc 7.6.3, nor ghc 8.0.2.
I suggest that you choose some simple logic, like propositional logic,
and represent it as an institution in Haskell with your approach. Then
we will have a better basis for discussion.
Best, Till
[1] http://hets.eu
[2] http://dol-omg.org
Am 17.05.2016 um 14:55 schrieb rick:
> Hello Christian:
>
> I thought I should send this to you separately in case you are not on
> the Haskell list any more.
>
> You may enjoy the samples below which use some standard Haskell
> libraries that may not have been available when you and Till started
> work on HETS.
>
> --
> Rick
>
> -------- Forwarded Message --------
> Subject: [Haskell-cafe] representing institutions in haskell
> Date: Mon, 16 May 2016 15:13:34 -0400
> From: rick <rick at rickmurphy.org>
> To: haskell-cafe at haskell.org
>
> Has anyone here taken an interest in representing institutions [1] in
> Haskell?
>
> Institutions originated in work on CLEAR [2] which was the first
> algebraic specification language with rigorous semantics.
>
> Institutions take some time to explain, or unravel if you follow the
> reference, but they come with a convenient slogan : "Truth is invariant
> under change of notation."
>
> The stretch goal of institutions is transforming logics while preserving
> satisfaction.
>
> They are conceived in terms of categorical abstractions, so it's natural
> to represent them in categories. I hope some folks here find
> institutions a useful domain to apply their work on categories.
>
> I've attached two samples in Haskell that uses some standard libraries :
> Arrow, Monad, Category and Dual.
>
> The first sample, ri-0, outlines the essentials. The category of
> signatures, constructions in the categories, signature morphisms,
> sentences, models and the satisfaction condition.
>
> Using plain old Nat reduces the complexity of the exposition.
>
> I provide a constructive witness for satisfaction of the morphism from
> conjunction to disjunction.
>
> You may recognize that I borrow some Bird/Hinze notation on Functors
> like mapSign. And you find some experiments with Quickcheck and Yampa.
>
> Ri-0 runs from main, but just computes the witness to the satisfaction
> condition.
>
> The second sample, ri-1, builds on ri-0. Rather than Nat, I use Either
> to inject disjunction into the exposition. The exposition becomes more
> complex, but the increased complexity is justified because maintaining
> satisfaction under change on notation is central to institutions.
>
> The functions prodSum takes conjunction to disjunction and sumProd takes
> disjunction to conjunction. I owe a citation to @BartoszMilewski and his
> work on categories for programmers where I first saw these functions.
>
> The satisfaction condition and witness appear more complex in ri-1, but
> its really just the substitution of the signature morphism on product
> and sum rather than plain old Nat as in ri-0.
>
> I also plan a better write up, but before I do I expect to learn much
> from an email exchange with interested folks here.
>
> Thanks for taking a look at this material.
>
> 1. https://cseweb.ucsd.edu/~goguen/pps/ins.ps
>
> 2. http://hopl.info/showlanguage.prx?exp=945
>
More information about the Haskell-Cafe
mailing list