packages feed

Dung (empty) → 0.9

raw patch · 5 files changed

+310/−0 lines, 5 filesdep +basedep +containerssetup-changed

Dependencies added: base, containers

Files

+ Dung.cabal view
@@ -0,0 +1,31 @@+name:          Dung+category:      Argumentation, Embedded, AI+version:       0.9+license:       BSD3+cabal-version: >= 1.2+license-file:  LICENSE+author:        Bas van Gijzel+maintainer:    Bas van Gijzel <bmv@cs.nott.ac.uk>+stability:     experimental+homepage:      http://www.cs.nott.ac.uk/~bmv/Dung/+copyright:     Copyright (C) 2013 Bas van Gijzel+synopsis:      An implementation of the Dung argumentation frameworks.+description:   An implementation of Dung's argumentation frameworks, an abstract argumentation model used to either directly represent conflicting information, or used as+               a translation target for more complex (structured) argumentation models. For an introduction to Dung's frameworks see +               <http://en.wikipedia.org/wiki/Argumentation_framework> and Dung's paper from 1995: \"On the acceptability of arguments and its fundamental role+               in nonmonotonic reasoning, logic programming, and n-person games\", Artificial Intelligence 77: 321-357.+               For the paper accompanying this library see \"Towards a framework for the implementation and verification of translations between argumentation+               models\" available at <http://www.cs.nott.ac.uk/~bmv/Dung/>.++build-type:    Simple++Library+  build-depends:+    base                   >= 4        && < 5,+    containers             >= 0.3      && < 0.6++  exposed-modules:+    Language.Dung.AF+    Language.Dung.Examples+    +
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright (c)2013, Bas van Gijzel++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Bas van Gijzel, Henrik Nilsson, nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ Language/Dung/AF.hs view
@@ -0,0 +1,121 @@+-- | This module implements Dung's argumentation frameworks. 
+module Language.Dung.AF 
+ (
+    -- * Basic definitions  
+   DungAF(..), 
+   setAttacks, conflictFree, acceptable, f, admissible, unattacked, attacked, 
+   -- * Grounded semantics through fixpoints and labelling
+   groundedF, Status(..), grounded, groundedExt)
+ where
+import Data.List (intersect, (\\))
+
+
+-- |An abstract argumentation framework is a set of arguments 
+-- (represented as a list) and an attack relation on these arguments. 
+data DungAF arg = AF [arg] [(arg, arg)]
+  deriving (Eq, Show)
+
+
+-- |Given an argumentation framework, determines whether args 
+-- (subset of the arguments in the AF), attacks an argument arg (in the AF).
+setAttacks :: Eq arg => DungAF arg -> [arg] -> arg -> Bool
+setAttacks (AF _ def) args arg 
+  = or [b == arg | (a, b) <- def, a `elem` args] 
+
+-- |Given an argumentation framework, determines whether args 
+-- (subset of the arguments in the AF) is conflict-free.
+conflictFree :: Eq arg => DungAF arg -> [arg] -> Bool
+conflictFree (AF _ def) args 
+  = null [(a,b) | (a, b) <- def, a `elem` args, b `elem` args] 
+
+  
+-- |Given an argumentation framework, determines whether an  
+-- argument is acceptable with respect to a list of 'args' (subset of the arguments in the AF). 
+acceptable :: Eq arg => DungAF arg -> arg -> [arg] -> Bool
+acceptable af@(AF _ def) a args 
+  = and [setAttacks af args b | (b, a') <- def, a == a']
+
+-- |Given an argumentation framework, determines whether an  
+-- argument is acceptable with respect to 'args' (subset of the arguments in the AF). 
+f :: Eq arg => DungAF arg -> [arg] -> [arg]
+f af@(AF args' _) args = [a | a <- args', acceptable af a args]  
+
+-- Returns 'True' if 'xs' is a subset of 'ys'
+subset :: Eq a => [a] -> [a] -> Bool
+xs `subset` ys = null (xs \\ ys)
+
+-- |Given an argumentation framework, determines whether 
+-- the set of arguments 'args' (subset of the arguments in the AF) is admissible,
+-- i.e. if 'args' is 'conflictFree' and args is a subset of @f af args@
+admissible :: Eq arg =>  DungAF arg -> [arg] -> Bool
+admissible af args = conflictFree af args && args `subset` f af args 
+
+-- alternatively: 
+-- if 'args' is 'conflictFree' and and each argument in args is acceptable with respect to args.
+-- admissible af args = conflictFree af args && and [acceptable af arg args | arg <- args]
+
+-- |Given a characteristic function f, computes the grounded extension
+-- by iterating on the empty set (list) until it reaches a fixpoint.
+groundedF :: Eq arg => ([arg] -> [arg]) -> [arg]
+groundedF f = groundedF' f []
+  where  groundedF' f args 
+           | f args == args  = args
+           | otherwise       = groundedF' f (f args)
+
+
+-- |Given a list of arguments that are 'Out' in an argumentation framework af, 
+-- an argument 'arg' is unattacked if the list of its attackers, ignoring the outs, is empty. 
+unattacked :: Eq arg => [arg] -> 
+              DungAF arg -> arg -> Bool
+unattacked outs (AF _ def) arg = 
+  let attackers = [a | (a, b) <- def, arg == b]
+  in null (attackers \\ outs)
+
+-- |Given a list of arguments that are 'In' in an argumentation framework af, 
+-- an argument 'arg' is attacked if there exists an attacker that is 'In'.
+attacked :: Eq arg => [arg] -> 
+            DungAF arg -> arg -> Bool
+attacked ins (AF _ def) arg = 
+  let attackers = [a | (a, b) <- def, arg == b]
+  in not (null (attackers `intersect` ins))
+
+  
+-- |Labelling of arguments.
+data Status = In | Out | Undecided
+  deriving (Eq, Show)
+
+-- |Computes the grounded labelling for a Dung argumentation framework,
+-- returning a list of arguments with statuses.
+-- 
+-- Based on section 4.1 of Proof Theories and Algorithms for Abstract Argumentation Frameworks
+-- by Modgil and Caminada
+grounded :: Eq arg => DungAF arg -> [(arg, Status)]
+grounded af@(AF args _) = grounded' [] [] args af
+ where 
+ grounded' :: Eq a => [a] -> [a] -> 
+              [a] -> DungAF a -> [(a, Status)]
+ grounded' ins outs [] _   
+  =    map (\ x -> (x, In)) ins 
+    ++ map (\ x -> (x, Out)) outs
+ grounded' ins outs args af  = 
+   let newIns   = filter (unattacked outs af)  args
+       newOuts  = filter (attacked ins af)     args
+   in if null (newIns ++ newOuts) 
+      then  map (\ x -> (x, In)) ins
+        ++  map (\ x -> (x, Out)) outs 
+        ++  map (\ x -> (x, Undecided)) args
+      else grounded' (ins ++ newIns) 
+                     (outs ++ newOuts) 
+                     (args \\ (newIns ++ newOuts)) 
+                     af
+
+-- |The grounded extension of an argumentation framework is just the grounded labelling, 
+-- keeping only those arguments that were labelled 'In'.
+groundedExt :: Eq arg => DungAF arg -> [arg]
+groundedExt af = [arg | (arg, In) <- grounded af] 
+
+
+
+
+
+
+ Language/Dung/Examples.hs view
@@ -0,0 +1,126 @@+-- | This is the examples module accompanying the implementation of Dung's 
+-- argumentation frameworks. 
+--
+-- This module contains a collection of examples, showing how to define 
+-- arguments, argumentation frameworks and how to use the standard definitions.
+--
+-- To run these examples, or your own: start GHCi and do the following:
+--
+-- @\:l Language.Dung.Examples@
+-- 
+module Language.Dung.Examples 
+  (
+   -- * Example uses of the basic definitions 
+   AbsArg, exampleAF, exampleAF2,
+   -- * Example uses of the fixpoint definitions
+   faf)
+ where
+import Language.Dung.AF
+
+-- | The simplest abstract argument is an argument identifiable by its name
+type AbsArg = String 
+
+-- @a = \"A\"@, @b = \"B\"@, @c = \"C\"@
+-- * Tests using the above argumentation frameworks:
+a, b, c :: AbsArg 
+a = "A"
+b = "B"
+c = "C"
+
+
+-- |Example AF: A -> B -> C 
+exampleAF :: DungAF AbsArg
+exampleAF = AF [a, b, c] [(a, b), (b, c)]
+
+-- |Example AF: A \<-> B
+--
+-- Now follow a few example outputs using the above argumentation frameworks.
+--
+-- [setAttacks:]
+-- 
+--  @[a,b]@ 'setAttacks' @c@ in the argumentation framework 'exampleAF':
+-- 
+-- >>> setAttacks exampleAF [a,b] c
+-- True
+--
+-- >>> setAttacks exampleAF [b,c] a
+-- False
+-- 
+-- >>> setAttacks exampleAF2 [] b
+-- False
+--
+-- [conflictFree:]
+--
+-- @\[a,c\]@ is 'conflictFree' in the argumentation framework 'exampleAF':
+-- 
+-- >>> conflictFree exampleAF [a,c]
+-- True
+--
+-- >>> conflictFree exampleAF [a,b,c]
+-- False
+--
+-- >>> conflictFree exampleAF2 [a,b]
+-- False
+-- 
+-- [acceptable:]
+--
+-- @c@ is acceptable w.r.t. @\[a,b\]@ in the argumentation framework 'exampleAF':
+--
+-- >>> acceptable exampleAF c [a,b]
+-- True
+-- 
+-- >>> acceptable exampleAF c [] 
+-- False
+--
+-- >>> acceptable exampleAF b [a,b,c] 
+-- False
+-- 
+-- [admissible:]
+-- 
+-- @\[a,b,c\]@ is admissible in the argumentation framework 'exampleAF':
+--
+-- >>> admissible exampleAF [a,b,c]
+-- False
+-- 
+-- >>> admissible exampleAF [a,c]
+-- True
+-- 
+-- >>> admissible exampleAF [a]
+-- True
+--
+-- [grounded:]
+-- 
+-- The grounded labelling of the argumentation framework 'exampleAF':
+--
+-- >>> grounded exampleAF
+-- [("A",In),("C",In),("B",Out)]
+-- 
+-- >>> grounded exampleAF2
+-- [("A",Undecided),("B",Undecided)]
+--
+-- [groundedExt:]
+-- 
+-- The grounded extension of the argumentation framework 'exampleAF':
+--
+-- >>> groundedExt exampleAF
+-- ["A", "C"]
+-- >>> groundedExt exampleAF2
+-- []
+exampleAF2 :: DungAF AbsArg 
+exampleAF2 = AF [a, b] [(a, b), (b, a)]
+
+-- |fixed point function for a specific argumentation framework,
+-- @faf = f exampleAF@.
+-- 
+-- [groundedF:]
+--
+-- The grounded extension of the argumentation framework 'exampleAF' using the fixpoint definition:
+--
+-- >>> groundedF faf
+-- ["A","C"]
+--
+-- >>> groundedF (f exampleAF2)
+-- []
+faf :: [AbsArg] -> [AbsArg]
+faf = f exampleAF
+
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple
+main = defaultMain