!݇qh      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                  ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefg  Trustworthy2F5fnom,An abstract unique object. Objects of type < may be compared for equality and ordering and hashed into h.:{do x <- newUnique print (x == x) y <- newUnique print (x == y):}TrueFalsenomCreates a new object of type I. The value returned will not compare equal to any other value of type  returned by previous calls to -. There is no limit on the number of times  may be called.nom Hashes a  into an h. Two Ks may hash to the same value, although in practice this is unlikely. The h! returned makes a good hash key.Helper functions (c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone/=>?@APhI9 nom.Apply f repeatedly until we reach a fixedpointnom(Apply a list of functions in succession. nomStandard function, returns Just a provided True, and Nothing otherwise nom9List subset. Surely this must be in a library somewhere. nom$Interleave a list of lists to a list nomReturns i# the tail of a list if it can, and j otherwise. nomReturns i# the head of a list if it can, and j otherwise.nomECompose functions with one argument with function with two arguments.f .: g = \x y -> f (g x y).nomFinds the unique element in a collection satisfying a predicate. Results in an error if there is no such element or if there are more than one.iota (== 1) [1, 2, 3]1iota (> 1) [1, 2, 3]b*** Exception: iota: expected exactly one element to satisfy the predicate, but found at least two...iota (> 3) [1, 2, 3]Z*** Exception: iota: expected exactly one element to satisfy the predicate, but found none...nomypoint moves the (first) element satisfying the predicate to the head of the list. Error raised if no such element found.point even [1,2,3] 2 :| [1,3]point even [1,3,5]%*** Exception: point: no such element...    8%Nominal theory of names and swappings(c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone&',./12456789;<=>?@AMPXfhonomSome types, like k and l, are . E.g. if we have a truth-value, we know it doesn't have any names in it; we might have used names to calculate the truth-value, but the truth-value itself m or n is nameless. nomA  instance of .nomA name is a pair of  an atom, and a label t. t~ is intended to store semantic information about the atom. For instance, if implementing a simply-typed lambda-calculus then t, might be a dataype of (object-level) types.A similar effect could be achieved by maintaining a monadic lookup context relating atoms to their semantic information; the advantage of using a name is that this information is packaged up with the atom in a local datum of type . nomA permutation at .nomJA permutation represented as a list of swappings (simple but inefficient).nomTypes that admit a swapping action.  A swapping (a b) maps a to b and b to a and  any other c to c.Swappings are invertible, which allows them to commute through type-formers containing negative arities, e.g. the left-hand argument of function arrow. Swappings always distribute: :swp a b (x, y) == (swp a b x, swp a b y) swp a b [x1, x2, x3] == [swp a b x1, swp a b x2, swp a b x3] swp a b (f x) == (swp a b f) (swp a b x) swp a b (abst n x) == abst (swp a b n) (swp a b x) swp a b (res [n] x) == res [swp a b n] (swp a b x) swp a b (Name t x) == Name (swp a b t) (swp a b x)Technical note: The content of  Swappable a is that a. supports a swapping action by atoms of every s. Everything else, e.g.   , just uses s. So kg is a "world" of sorts of atoms, for a particular application. This is invisible at our default world  because  has only one inhabitant, '. See !; and surrounding code for a more sophisticated atoms setup.nomA distinguished type of atoms.It is populated by s (below), thus an element of  is "a Tom". We provide q as primitive for convenience. If you need more than one type of atom (e.g. term atoms and type atoms), look at . nomWe provide a stock datatype .  Using the  DataKinds= package, this is then used to provide a stock type of atoms . nom"An atom is a unique atomic token.  The argument s of K is part of facilities offered by this package for declaring types of atom s ranging over kinds k. For usage see ", and # in !Language.Nominal.Examples.SystemF.IIf your development requires just a single type of atomic tokens, ignore  and use . !nomA proxy element for sort <. If we pass this, we tell the typechecker we are "at Tom"."nom1Make a fresh atom for each element of some list (a ny list). *If you just want one fresh atom, use e.g. [()].EThis is an IO action; when executed, fresh identifiers get generated.#nomMake a fresh atom at  for each element of some list (a ny list).$nom'For convenience: generate a fresh katom%nom&For convenience: generate a fresh atoma <- freshAtomIOb <- freshAtomIOa == bFalse &nomA  -swapping'nomTA permutation acts as a list of swappings. Rightmost/innermost swapping acts first.a <- freshAtomIOb <- freshAtomIOc <- freshAtomIOperm [(c,b), (b,a)] a == cTrue (nom0As the name suggests: overwrite the name's label)nom:Overwrite the name's label. Intended to be read infix as n `withLabelOf n'*nom Name with o. atom, so really just a label. Use with care!+nom Name with o/ label, so really just an atom. Use with care!,nom?A name swap discards the names' labels and calls the atom-swap .-nomA name swap for a /-name. Discards the names' labels and calls a  -swapping..nom8Display an atom by showing (the hash of) its unique id. 1nom'Names are leq when their atoms are leq.5WARNING: Labels are not considered! In particular, t"-names are always ordered even if labels t are unordered. 2nom1Names are equal when they refer to the same atom.5WARNING: Labels are not considered! In particular, t-names always have p, even if the type of labels t does not.:nomSwapping atoms in names distributes normally; so we swap in the semantic label and also in the name's atom identifier. Operationally, it's just a tuple action: Hswp atm1 atm2 (Name t atm) = Name (swp atm1 atm2 t) (swp atm1 atm2 atm);nom.Base case for swapping: atoms acting on atoms.<nom!Swap distributes over map types. Note that maps store their keys ordered for quick lookup, so a swapping acting on a map is not a noop and can provoke reorderings.=nomkSwap distributes over function types, because functions inherit swapping action pointwise (also called the conjugation action) !"#$%&'()*+,- !"#$%&'()*+,-.Theory of support, apartness, and restriction (c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone&',./18;<=>?@APUVXfh]nom Instance of ^ on a .^nomClass for types that support a *remove these atoms from my support, please# operation. Should satisfy e.g.:  2restrict atms $ restrict atms x == restrict atms x 'atms `apart` x ==> restrict atms x == xThe canonical instance of ^ is $. The R constraint is not necessary for the code to run, but in practice wherever we use ^. we expect the type to have a swapping action.Note for experts: We may want ^ without a, for example to work with Nom (Atom -> Atom). Note for experts:w Restriction is familiar in general terms (e.g. pi-calculus restriction). In a nominal context, the original paper is  .https://dl.acm.org/doi/10.1145/1069774.1069779&nominal rewriting with name-generation ( 'http://gabbay.org.uk/papers.html#nomrng author's pdfQ), and this has a for-us highly pertinent emphasis on unification and rewriting. `nomA  instance of a. anomA typeclass for elements for which a supporting set of atoms can be computed in an efficient, structural, type-directed manner. So: lists, sets, and name-abstractions yes, and function-types( no. See instances for full details. Note: This gives as a strictly more specific and structure-directed meaning than the motivating mathematical notion of support, which does work e.g. on function-types.cnomA  instance of b. dnoma and b are d- when they are supported by disjoint sets of s-atoms.We use proxy instead of q6 below, so the user can supply any type that mentions s. enoma and b are e3 when they are supported by disjoint sets of atoms.fnomBring the first element of a list-like structure that an atom points to (by being mentioned in the support), and put it at the head of the nonempty list. Raises error if no such element exists. gnomf2, for names. A name is just a labelled atom, and  namePoint# just discards the label and calls f.hnom\Form of restriction that takes names instead of atoms. Just discards name labels and calls _.inom Restriction is monadic on Maybe jnom5Restriction is trivial on elements of nameless types nnomLeaf has empty supportonom;Support distributes through datatype-formers, taking unionsqnom(Eliminate elements for which any of the atms are in the supportrnomROn lists, Restrict traverses the list and eliminate elements for which any of the atms are in the support. A alternative is to assume restriction on the underlying elements and restrict pointwise. The elimination choice seems more useful in practice. ]^_`abcdefgh ab`cdefg^_]h$A theory of suspended monoid actions(c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone&',./14789;<=>?@ACHPUVXfhnom"A type for suspended restrictions nomA type for suspended swappingsnom/A generic type for suspended monoid operations nom2A typeclass for computing under a monoid action. RULES:  zexit . enter mempty == id flip >>+ . const == >== i.e. a' >>= f = a' >>+ const f enter mempty == returnIn other words: +<< . const and  enter mempty form a monad. enter mempty followed by exit is a noop. nom>Move from one suspended environment to another via a function  i -> a -> m b.nom/Enter the suspended environment, by suspending i on a.nomHExit the suspended environment, discarding any suspended actions. Use 5 to exit while folding actions into the computation. nomAn equivalent to r, with access to the monoid.nomAn equivalent to <&>, with access to the monoid.nom Exit the ?, with a function to fold the monoid into the computation. So: exit = exitWith (,)nom flip nomAn  has an i-monoid actionnom)Exit with a swapping action, if availablenom,Exit with a restriction action, if availablenom Transpose an  with a s Note: if m is instantiated to % s then note there is no capture-avoidance here; local bindings are just moved around. A stronger version (with correspondingly stronger typeclass assumptions) is in &. nom<This is just an instance of a more general principle, since f is t and we assume m applicative.NoneDNominal-flavoured implementation of data in a context of local names(c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone%&',./14567;<=>?@ACHMUVXghk.nom(Data in a local atom-binding context at s.nomData in local  s-binding context.nom+Recover a name-generating IO action from a - binding. If you execute one of these using u, you get the data in a (the bodyF of the binding), with some actual freshly-generated atoms. See also .nomConstructor for  s. nomConstructor for  s (proxy version). nom`Make sure restricted atoms will alpha-convert to avoid capture, if e.g. they were created using  and not . nom A version of  on ^ that takes names, not atoms (it just strips the labels of the names and acts on their atoms).nomUse this to safely exit a ! monad. It works by binding the KNom-bound s -atoms using a's native instance of  KRestrict. See "Language.Nominal.Examples.Tutorial for examples. unNom = resAppC idNote: The less versions of  are the  and  instances of  as an instance of  . See also  '. nomAnother way to safely exit ?: convert it to an IO action (the IO may generate fresh names) nom&Create a fresh atom-in-nominal-contextnom&Canonical version for unit atoms sort.nomFresh t m of atoms (e.g. m is list or stream)nomFresh t m of atoms (e.g. m is list or stream). |  instance.nom4Create a fresh name-in-a-nominal-context with label tnom'Create fresh names-in-a-nominal-contextnomCanonical version of  for  name.nomCanonical version of  for  names.nom4Create a fresh name-in-a-nominal-context with label tnom'Create fresh names-in-a-nominal-contextnomCanonical version of  for  name.nomCanonical version of  for  names.nom commutes down through functors. is a version of C where bindings are have added capture-avoidance (for inverse, see ). nomShow a nom by unpacking itnomIFresh names are generated when name contexts are opened for equality testnom6Alternatives are composed in a capture-avoiding mannernom^ atms in a , inside  monad.nomSwap goes under name-binders. 5swp n1 n2 (ns @> x) = (swp n1 n2 ns) @> (swp n1 n2 x),6Extending algebraic graphs with nominal-style binding (c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone /279=>?@AUV_nomVA datatype of graphs with binding. Perhaps should parameterise over atom type (see )). For now, I use the default atom type .nomFold on graphs with binding. Just like fold on graphs, but with an extra restriction operation, which we go under in a capture-avoiding manner. nom=Filter a list of vertices to obtain those vertices for which  atms :: [] is fresh nomGRestriction action just passes the restriction on to the deep embedding Typeclass theory of binders (c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone%./14567;<=>?@ACMUVXghka`nomSometimes we can concrete a bound entity ctxbody at a datum a% (where it need not be the case that a == ctx), to return a body body. In the case that a == ctx , we expect .(a @> x) `conc` a == x a @> (x' `conc` a) == xnom8Wrapper for generic method of deriving support of bindernom(A typeclass for unpacking local binding.oProvides a function to unpack a binder, giving access to its locally bound names. Examples of binders include ,  (, and ).A . comes with a rich array of destructors, like , , , , , , , , , X. These correspond to common patterns of unpacking a binder and mapping to other types.Below:ctxbody is the type of the datum in its name-binding context, which consists intuitively of data wrapped in a local name binding. (Canonical example: .)ctx is the type of a concrete name-carrying representation of the local binding (atom, names, list of atoms, etc). (Canonical examples:  and [].)body% is the type of the body of the data.s9 is the type of atoms output. Output will be wrapped in  s.For example the  ( instance of  has type +Binder (KAbs (KName s t) a) (KName s t) s a; and this means that a datum in ctxbody = KAbs (KName s t) a can be unpacked as something in ctx = KName s t and something in body = a, andmapped by a function of type KName s t -> a -> b using ,to obtain something in KNom s b.The other destructors (, , , , , , , , `) are variations on this basic pattern which the wider development shows are empirically useful. See also  and .nom&A destructor for the binder (required)nomA constructor for the binder (optional, since e.g. your instance may impose additional well-formedness constraints on the input). Call this res.nom3A partial constructor for the binder, if preferred.nomThis pattern is not quite as useful as it could be, because it's too polymorphic to use a COMPLETE pragma on. You can use it, but you may get incomplete pattern match errors.nom#Use this to map a binder to a type bM, generating fresh atoms for any local bindings, and allowing them to escape.nom#Use this to map a binder to a type b= with its own notion of restriction. Bindings do not escape.nom!Unpacks a binder and maps into a  environment. = v '(@@)'nom!Unpacks a binder and maps into a L environment. Local bindings are not examined, and get carried over to the . =  . wnom8Unpacks a binder. New names are generated and released. = v '(@@!)'nomZUnpacks a binder. New names are generated and released. Local bindings are not examined. =  . wnom1Unpacks a binder and maps to a type with its own _ operation. = v '(@@.)'nom1Unpacks a binder and maps to a type with its own _G operation. Local bindings are not examined, and get carried over and _ed in the target type.A common type instance is (a -> Bool) -> KNom s a -> Bool, in which case  acts to capture-avoidingly apply a predicate under a binder, and return the relevant truth-value. See for example the code for transposeNomFunc. =  . wnom1Unpacks a binder and maps to a type with its own _ operation. Flipped version, for convenience.A common type instance is  KNom s a -> (a -> Bool) -> Bool , in which case n acts to apply a predicate inside a binder and return the relevant truth-value. See for example the code for transposeNomMaybe. = v nom!Evaluate predicate on fresh atom.nom,Evaluate predicate on fresh name with label t.nomn is  a when swp n' n a == a for a  n'. Straight out of the paper ( 7https://link.springer.com/article/10.1007/s001650200016 publisher and  .http://www.gabbay.org.uk/papers.html#newaas-jvauthor's pdfs).M/Note: In practice we mostly need this for names. This version is for atoms.nomn is  a when swp n' n a == a for a  n'. Straight out of the paper ( 7https://link.springer.com/article/10.1007/s001650200016 publisher and  .http://www.gabbay.org.uk/papers.html#newaas-jvauthor's pdfs).nomIs the  binding trivial? This is the aa version, for highly structured data that we can traverse (think: lists, tuples, sums, and maps). See also 1, for less structured data when we have equality p and swapping  KSwappable.nomIs the  binding trivial? This is the p version, using . Use this when we do! have equality and swapping, but can't4 (or don't want to) traverse the type (think: sets). See also , for when we have a.nom Freshen all s-atoms, if we have a. Returns result inside . binding to store the freshly-generated atoms.nomFreshen all atoms, if we have `.nom Acts on a n binder by applying a function to the body and the context of locally bound names. Local names are preserved.nomYConcrete a nominal abstraction at a particular list of atoms. Dangerous for two reasons:!The list needs to be long enough.DThere are no guarantees about the order the bound atoms come out in.nom&Suppose we have a nominal abstraction x' :: KNom s a. Then x'  (Proxy :: Proxy s)$ triggers an IO action to strip the  context and concrete x'! at some choice of fresh atoms. cnoc (Proxy :: Proxy s) = exit nom&Suppose we have a nominal abstraction x' :: KNom s a where a8 has its own internal notion of name restriction. Then  cnoc () x' folds the -bound names down into x'! to return a concrete element of a. cnoc () = unNomnomthe data in its local bindingnom.function that inputs an explicit name context ctx and a body! for that context, and outputs a b.nom Result is a b in a binding context.""9 109 9  Noneinom(! does indeed overwrite the label.9\(n :: Name String) t -> nameLabel (n `withLabel` t) == tnom2Not all names are equal (even with trivial labels)nom&(n' n).x = x (we expect this to fail)nom+n',n#x => (n' n).x = x. Test on x a tuple.nom(n' n).(n' n).x = x nom+n'',n'#x => (n'' n').(n' n).m = (n'' n).m  nom'n'#x => (n'' n').(n' n).x = (n'' n).x  nom(n' n).x = (n n').x    Examples of coding style(c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone /279=?@A_ nom2You probably shouldn't count the atoms bound in a . cbad_countBinding :: Swappable a => Nom a -> Int bad_countBinding x' = x' @@! \atms _ -> length atms nomAYou probably shouldn't look at the order of the atoms bound in a . bbad_countOrder :: Swappable a => Nom a -> Bool bad_countOrder x' = x' @@! \atms _ -> isSorted atms nom:It's OK to create fresh IDs for bound atoms, but doing so  unnecessarily is deprecated.WFor example, here is code for a restrict instance of Nom (code simplified for clarity): ^restrict :: Swappable a => [Atom] -> Nom a -> Nom a restrict atms x' = x' >>= \x -> res atms x We can simplify it down to this: restrict = (=<<) . res  The code for  } below does the same thing, but unnecessarily unpacks the local binding, generates fresh IDs for its atoms, and then rebinds. ubadRestrict :: Swappable a => [Atom] -> Nom a -> Nom a badRestrict atms' a' = a' @@! \atms a -> res (atms' ++ atms) anom Contrast   with the similar (. What separates them is the use of '(@!)' instead of '($.)' (respectively). The latter '(c@.)' avoids an intermediate generation of explicit fresh IDs for the bound atoms, and so is better.In fact  is equivalent to the actual restrict8 instance; it's just expressed using higher-level tools. `okRestrict :: Swappable a => [Atom] -> Nom a -> Nom a okRestrict atms a' = a' @@. \_ -> res atmsAlso OK: +okRestrict' atms' = join . fmap (res atms')nomoStill on the theme of trying to be parsimonious with generating atoms here is code for an equality instance of : kinstance Eq a => Eq (KNom s a) where a1' == a2' = exit $ a1' >>= \a1 -> a2' >>= \a2 -> return $ a1 == a2 Note how we  at k. Contrast with the deprecated version, in which we exit earlier than required, and furthermore, we exit twice (code simplified for clarity): pbadEq :: Eq a => Nom a -> Nom a -> Bool badEq a1' a2' = withExit a1' $ \_ a1 -> withExit a2' $ \_ a2 -> a1 == a2xnomThe x predicate returns mJ if the elements of a list occur in non-descending order, equivalent to y (z).ynomThe y function returns mP iff the predicate returns true for all adjacent pairs of elements in the list.        Nominal atoms-abstraction types (c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone./145679;<=>?@AMPXghnomAbstraction by -names. nom!A datatype for name-abstractions.KAbs n a is a type for abstractions of as by n-names, where we intend that  n = KName s t for some s-atoms (atoms of type s) and t-labels (labels of type t). Abs t a is a type for abstractions of as by t -labelled -atoms. 4Under the hood an abstraction is just an element of  (n, n -> a)R, but we do not expose this. What makes the type interesting is its constructor, ( :: KName s t -> a -> KAbs (KName s t) a1, which is the only way to build an abstraction. It's possible to implement  using   see  and   but this requires a  KSwappable typeclass constraint on a(, which we prefer to avoid so that e.g.  can be a s. {nomWe only care about the name for its label. For reasons having to do with the Haskell type system, it's convenient to wrap this label up in a "dummy name". We do not export { outside this file. |nomA function that  concretesK an abstraction at a particular name. Unsafe if the name is not fresh.  (abst a x) `absApp` a == x <abst a (x `absApp` a) == x -- provided a is suitably fresh. )new' $ \a -> abst a (x `absApp` a) == x nomThe abstraction pattern '(:>)' is just an instance of '(: @!)' for  . Thus,  n :@> x -> f n xis synonymous with  x' -> x' @@! f  Because '(:!>)' is a concrete instance of '(:!)', we can declare it  COMPLETE@.nomtCreate an abstraction by providing a name and a datum in which that name can be swapped (straight out of the paper;  7https://link.springer.com/article/10.1007/s001650200016 publisher and  .http://www.gabbay.org.uk/papers.html#newaas-jvauthor's pdfs). Instance of (, for the case of a nominal abstraction.nomA " is just a pair of a label and an . This version of 3 that takes a label and an atom, instead of a name.nomXFuse abstractions, taking label of abstracted name from first argument. Should satisfy: $fuse (n @> x) (n @> y) = n @> (x, y)nom(Split two abstractions. Should satisfy: &unfuse (n @> (x,y)) = (n @> x, n @> y)nom#Return the label of an abstraction.Note: For reasons having to do with the Haskell type system it's convenient to store this label in the underlying representation of the abstraction, using a "dummy name". However, we do not export access to this name, we only export access to its label, using . nomBijection between Nom and Abs. Just an instance of .nomBijection between Nom and Abs. Just an instance of .nom&Apply f to a fresh element with label tnom.Apply f to a fresh element with default label nom+Near inverse to applicative distribution. absFuncIn . absFuncOut = id& but not necessarily other way around nom9We show an abstraction by evaluating the function inside # on a fresh name (with the default j label)nom<Abstractions are equal up to fusing their abstracted names.  nomTConcretes an abstraction at a particular name. Unsafe if the name is not fresh.  (abst a x) `conc` a == x :abst a (x `conc` a) == x -- provided a is suitably fresh. 'new' $ \a -> abst a (x `conc` a) == x !nomActs on an abstraction x' by unpacking x' as (n,x) for a fresh name n, and calculating f n x.$nomESpelling out the generic swapping action for clarity, where we write KA$ for the (internal) constructor for KAbs: 6kswp n1 n2 (KA n f) = KA (kswp n1 n2 n) (kswp n1 n2 f)%nom.Support of a :@> x is the support of x minus a0 Unification by permutation(c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone&',./178;<=>?@AMPUVXfh[&nom-instance of typeclass '.'nomEqual-up-to-permutation. The algorithm works very simply by traversing the element looking for atoms and when it finds them, trying to match them up. If it can do so injectively then it succeeds with i$ a renaming; if it fails it returns j. Question: Granted that ' is a subset of a, why are they not equal? Because for simplicity we only consider types for which at most one unifier can be found, by an efficient structural traversal. This avoids backtracking, and makes a ( a function to + . So, a key difference is that a[ can easily calculate the support of a set (unordered list without multiplicities) whereas ' does not even attempt to calculate unifiers of sets; not because this would be impossible, but because it would require a significant leap in complexity that we do not seem to need (so far).(nom3This calculates a solution to a unification problem)nom]This applies a solution to a unification problem (represented as a renaming) to an element. Note: ) is not just swapping. It traverses the structure of its argument performing an atom-for-atom renaming. In the case that its argument solves a unification problem, its effect/ is the same as if a permuatation were applied.This is checked in * and +.*nomRenaming on a  instance+nomAn element of + is either i an injective finite map from  to  (for this file, call this a renaming), orA "nomap" value (j).A +& represents a solution to the problem *does there exist a permutation that makes x equal to y?A type in the '. typeclass is structurally guaranteed to give  at most one solution to such a unification problem, up to renaming irrelevant atoms. So in a nutshell: names, lists, and tuples are good here, and functions (not an equality type) and sets (may have multiple solutions) are not good.A i< value represents a solution to this unification problem; a j7 value represents that no such solution can be found. 7 calculates these solutions. .nomThe identity renaming. /nom&The Nothing renaming. If we think of + s@ as type of solutions to permutation unification problems, then /' indicates no solution could be found. 0nomYIs it Just a renaming? (My unification problem can be solved, and here's the solution.) 1nom,Is it Nothing? (Nope; no solution exists.) 2nom*The parts of the map that are not identity3nomExtend a renaming m with a new pair a -> b, maintaining the property of being a partial injection. If adding a->b would destroy partial injectivity, then return Nothing. 4nomExtract the graph of a +, Maybe.5nomConvert a graph to a +. 6nom1Given a block of atoms, remove them from the map providedz that the atoms in that block only map to other atoms within it; if an atom gets mapped across the block boundary, return Nothing.  Needed for equality instance of ).7nom Unify on s, thus  -instance of (.8nomDoes an s-unifier exist? We write proxy instead of qV for the user's convenience, so the user can take advantage of any type that mentions s.9nomDoes a -unifier exist?:nom(Unify a list with a prefix of the other ;nom,Unify a list with a prefix of the other (at  version). <nom,One list unifies with a prefix of the other =nom0One list unifies with a prefix of the other (at  version). >nomThere are two reasonable notions of restriction; filter, or default to Nothing. We choose the option that discards minimal information, i.e. the filter.Anom>Support of a renaming is the set of nontrivially mapped atoms  (supp (idRen :: Ren)) == S.emptyTrue%(supp (nothingRen :: Ren)) == S.emptyTrueBnom Elements of + are compared on their nub 22, meaning just that identity mappings are ignored.Cnom Elements of +$ are compared for equality on their nub 22, meaning just that identity mappings are ignored.a = exit $ freshAtomidRen == renExtend a a idRenTrue KnomUnify  name-abstractionLnomUnify 4 abstractions. Unpack, unify, clean out fresh namesMnom3Unify names: they behave just an atom-label tuple Nnom Unify atoms&'()*+,-./0123456789:;<=+,-*./0123456'()&789:;<=-Theory of equivariant orbit-finite structures(c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone&',./79=>?@AUVXhM]_nom` at a !. Thus, a type for orbit-finite -equivariant maps.`nom)A type for orbit-finite equivariant maps.anom-equivariant function-spacebnomb s a b is just a -> b in a wrapper. But, we give this wrapped function trivial swapping and support. (For a usage example see the source code for ,.) Functions need not be finite and are not equality types in general, so we cannot computably test that the actual function wrapped by the programmer actually does? have a trivial swapping action (i.e. really is equivariant). It's the programmer's job to only insert truly equivariant functions here. Non-equivariant elements may lead to incorrect runtime behaviour. hOn an equivariant orbit-finite type, the compiler can step in with more stringent guarantees. See e.g. `. dnomFunction in a wrapper enomnFilter a list down to one representative from each atoms-orbit (choosing first representative of each orbit). fnom Instance for  atom type.gnomORestrict a Map to its equivariant nub, discarding all but one of each key-orbithnomInstance for unit atom type.inomwEquivariantly apply a list of pairs, which we assume represents a map, to an element. Also returns the source element.jnomUEquivariantly apply a list of pairs (which we assume represents a map), to an elementknomXEquivariantly apply a list of pairs (which we assume represents a map), to an element.  version.}nomEquivariantly apply a map m to an element a. Also returns a unifier.lnomEquivariantly apply a map m to an element a. If  a == ren r a' for some r :: Ren and  m a' == b', then kevLookup m a == ren r b'. #For this to work, we require types a and b to support a )N action, meaning they should support notions of unification up to permutation.mnoml instantiated to a .nnomEquivariant application of an orbit-finite map. Given a map (expressed as finitely many representative pairs) and an argument ... \it tries to rename atoms to match the argument to the first element of one of its pairs and Sif it finds a match, it maps to the second element of that pair, suitably renamed. onom6A constant equivariant map. We assume the codomain is ..(constEvFinMap 42 :: EvFinMap Char Int) $$ 'x'42+(constEvFinMap 0 :: EvFinMap Atom Int) $$ a0 pnom?Extends a map with a new orbit, by specifying a representative a maps to b. We assume codomain b is , as discussed above. D(extEvFinMap 'x' 7 $ (constEvFinMap 42 :: EvFinMap Char Int)) $$ 'x'7D(extEvFinMap 'x' 7 $ (constEvFinMap 42 :: EvFinMap Char Int)) $$ 'y'42.let [m, n, o] = exit $ freshNames [(), (), ()]m == nFalseunifiablePerm m nTrueE(extEvFinMap m 7 $ (constEvFinMap 42 :: EvFinMap (Name ()) Int)) $$ n7W(extEvFinMap o 8 (extEvFinMap m 7 $ (constEvFinMap 42 :: EvFinMap (Name ()) Int))) $$ n8qnomConstructs an orbit-finite equivariant map by prescribing a default value, and finitely many argument-value pairs. We assume the codomain is , as discussed above. Hlet f = evFinMap 42 [('x', 7), ('y', 5), ('x', 13)] :: EvFinMap Char Intmap (f $$) ['x', 'y', 'z'] [13,5,42]Hlet atmEq = evFinMap False [((a,a), True)] :: EvFinMap (Atom, Atom) Bool+map (atmEq $$) [(b,b), (c,c), (a,c), (b,c)][True,True,False,False]Hlet g = evFinMap 2 [((a,a), 0), ((b,c), 1)] :: EvFinMap (Atom, Atom) Int'map (g $$) [(b,b), (c,c), (a,c), (b,c)] [0,0,1,1]rnomLExtracts default value und list of exceptional argument-value pairs from an _.QfromEvFinMap $ (evFinMap 42 [('x', 7), ('y', 5), ('x', 13)] :: EvFinMap Char Int)(42,[('y',5),('x',13)])vnom`g is compared for equality by comparing the default value and the representatives, up to permutations.  Edge case:* If a codomain type is orbit-finite (e.g. k and  '(Atom,Atom)', with two orbits, or  with one), and representatives exhaust all possibilities, then the default value will never be queried, yet it will still be considered in our equality test. wnom We insist a and b be ke-swappable so that the mathematical notion of support (which is based on nominal sets) makes sense. 7Operationally, we don't care: if see something of type KEvFinMap s a b , we return  Set.empty.qnomDefault value.nomcList of exceptional argument-value pairs. In case of conflict, later pairs overwrite earlier pairs._`abcdefghijklmnopqrbcdaefghlmijk`_nopqrn0None-.HXO{nomOnly one orbit of atoms |nom.Two orbits of atom pairs (equal, or disjoint) {|{|NHaskell rendering of the mathematical idealisation of the Extended UTxO model (c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone,./1789;<=>?@ACMUVX_f?~nomA blockchain is a valid , with no unspent inputs.nomA  is a valid list of transactions in a local name-binding context. Think of it as a generalisation of blockhains that allows UTxIs (unspent transaction inputs). nomA ^ is an equivariant orbit-finite predicate on datum and context. For convenience we make it . nomA Q is an equivariant predicate on datum and context. For convenience we make it . nom5A type for trivial validators that always return truenomA typeclass for  validatorsA. A validator is an equivariant object that takes a datum and a , and returns a k.nom1A typeclass for types for which we can calculate output positions.  just traverses a4's type structure, looking for subtypes of the form  p _ _, and collecting the p.s. The only interesting instance is that of  a, where bound ps get garbage-collected. nom1A typeclass for types for which we can calculate input positions. just traverses a4's type structure, looking for subtypes of the form  p _, and collecting the p-s. The only interesting instance is that of  a, where bound ps get garbage-collected. nomA  TransactionF consists of an f$ of inputs, and a list of outputs. Type parameters are:f> a parameter which can be instantiated to a type-constructor ( Chttp://dev.stephendiehl.com/fun/001_basics.html#higher-kinded-typeshigher-kinded types). In this file, f' will be either list or nonempty list. r a parameter for the redeemer.d a parameter for the datum.v a parameter for the  validator.nomAn output has a position, a datum d, and a  validator v.  Think of the datum> as a fragment of state data which is attached to this output. Think of the  validator{ as a machine which, if given a suitable redeemer (along with other stuff), with authorise or forbid access to this output.d and v/ are type parameters, to be instantiated later.nomAn input has a position and a redeemer rt. Think of the redeemer is a key which we use to unlock access to whatever output this input wants to connect to. Here r/ is a type parameter, to be instantiated later.nom4Positions are atoms. These identify locations in a  or ~.nomReturn the output-list of a .nomReturn the input-list of a .nomPoint a transaction at p nomForm the contexts of a .nom Calculate unspent outputs.LWe tell an output is unspent when its position isn't bound in the enclosing  name-context.nom Calculate unspent inputs. EBecause we're dealing with transaction lists, we care about dangling inputs( (which we call UTxIs) as well as UTxOs.nom/What's the point of my context? The position p of the first element of the input list of a context is deemed to be the "call site" from which the context tries to find a preceding output (with position p ) in its . nomCalculate unspent input contexts. EBecause we're dealing with transaction lists, we care about dangling contexts (which we call UTxCs). nomA  transaction3 is valid if (at least) all positions are disjoint nomTries to create a valid  from a single . If it fails, we get j.nomCreates a valid  from a single H. If it fails (because the transaction is invalid), it raises an error.nom&Combine a list of transactions into a  . Return j* if list does not represent a valid chunk.nomCombines a list of s in a  binding context, into a .JGathers any excess positions (those not linking inputs to outputs) in the  binding.Returns j. if the transaction list doesn't form a valid .nomCombines a list of transactions in a binding context, into a Chunk, with a check that no excess positions are bound. Returns Nothing if check fails.nom0Example chunk 0: "Chunk [p] [Transaction [] []]"HA chunk containing an empty transaction, with a vacuous binding by some p.Is chunk. Is blockchain.isChunk exampleCh0TrueisBlockchain exampleCh0TruenomGExample chunk 1: "Chunk [p] [Transaction [] [Output p 0 (const True)]]"BOne output with datum 0 and trivial validator that always returns m. Is chunk. Is blockchain.nom9Example chunk 2: "Chunk [p] [Transaction [Input p 0] []]"One input with redeemer 0. Is chunk. Is not blockchain.nomExample chunk obtained by concatenating chunks 1 and 2. Concat succeeds but positions don't line up. Is not blockchain, and also is not valid chunk because of overbinding.Z"Chunk [p1, p2] [Transaction [Input p2 0] [], Transaction [] [Output p1 0 (const True)])]"[(Note: we write lists with their head to the left, so time flows from right to left above.)isChunk exampleCh12FalsenomaExample chunk obtained by combining chunks 1 and 2, now on same name so input points to output. S"Chunk [p] [Transaction [Input p 0] [], Transaction [] [Output p 0 (const True)])]"[(Note: we write lists with their head to the left, so time flows from right to left above.)Is chunk. Is blockchain.nomTExample chunk obtained by combining chunks 1 and 2, on same name. But output comes after@ input, not before. Concat fails because nameclash is detected.~nom(Calculate the input and output positionsnom tx txs adds tx to txs, provided that:tx is valid$there is no position name-clash and validators are happy.sThis is the core of this file. In a certain sense, everything is just different ways of wiring into this function.nom Version of  that acts directly on Maybe (Chunk r d v).nomConcatenate two s, merging their binding contexts in a capture-avoiding manner. If concatenation is impossible (e.g. because validation fails), defaults to  Chunk Nothing.Note: No explicit checks are made here that inputs are valid chunks. In particular, no overbinding protection (overbinding = Nom binder in Chunk binds excess positions not involved in UTxO-UTxI linkage). If you want such checks, look at  and .OWorks by unpacking first chunk as a list of transactions and appending them to i the second argument. Local binding of first chunk gets carried over automatically; new local bindings may get generated during the append.nom A version of B that performs explicit validity checks on its inputs and result. nom For debuggingnom5Check whether one chunk is a prefix of another. See  to understand why the + binding on the first argument is required.nomCalculate the length of a Chunknom Calculate the head of a chunk. nom0Calculate the tail of a chunk. Two monads here:l, because the underlying list of transactions might be empty and so have no tail. And if it's not empty ...? ... to bind the names of any positions in newly-exposed UTxOs.nom5Compare the code for this function with the code for +. It looks plausible ... but it's wrong.It looks like it returns the tail of a chunk, and indeed it does. However, the result is not a chunk because positions get exposed.  See the test -.nom, for chunks. The X binding captures any dangling UTxOs or UTxIs that are left after truncating the chunk. nomList of subchunks. / binding is to capture dangling UTxOs or UTxIs.nomoTake a chunk and reverse its transactions. Usually this will result in an invalid chunk, in which case we get Nothing. Used for testing. nom%Split a chunk into a head and a tail.nom0Split a chunk into a head and a head and a tail.nomSmart constructor for a ~C. Ensures only valid blockchains are constructed, by testing for .nom,Check that the correct atoms are bound in a .nom-Check that validators are happy, by taking a % apart and putting it together again.nomIs this a valid chunk? (, , , ) resAppC isChunk exampleCh1True resAppC isChunk exampleCh2True isChunk exampleCh12FalseisChunk exampleCh21TruenomiIs this a valid chunk? Test by splitting it into a transaction list and putting it back together again. nomA blockchain is a valid # with no UTxI (unspent transaction inputs). (, , , ) isBlockchain exampleCh0TrueresAppC isBlockchain exampleCh1TrueresAppC isBlockchain exampleCh2False isBlockchain exampleCh12False isBlockchain exampleCh21True nomBlockchain check for  a .nomIntensional equality nom<Maybe Chunk forms a monoid, with unit being the empty chunk.nomChunk forms a partial monoidnomRestrict atoms in a .nomRChunk equality tests for equality, with permutative unification on the local names(==) = unifiablePerm& would be wrong; we should only unify bound atoms.Note: +0 equality compares nubs (non-identity mappings) nom Acts on a c by unpacking it as a transaction-list and a list of locally bound atoms, and applying a function. nomEquality on validators is intensional; (Validator f == Validator f') when f and f' happen to point to the same bit of memory when the equality runs. Thus if iEq f f' returns True this means that f and f' represent the same mathematical function, and indeed are also the same code. If iEq f f' returns False this does not mean that f and f' represent distinct mathematical functions. It just means they were represented by distinct code when iEq is called. This may be useful for running tests where we check that gobs of code get put in the right places and assembled in the right ways, without necessarily caring to execute them (or even without necessarily instantiating executable values). instance IEq Value wherenom is a F}~F~}!Nominal treatment of substitution(c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone,./18;<=>?@APUVfh  nom)Canonical instance for the unit atom sort!nomSubstitution.  sub n x y= corresponds to "substitute the name n for the datum x in y".We intend that n should be a type of names  KName k n. &nomAction on a leaf is trivial'nom$Distributes through datatype-formers)nomgPlaceholder for future development. A general maths behind this definition is given in Section 8.1 of  &https://dl.acm.org/doi/10.1145/2700819+Definition 8.12 of Semantics Out Of Context ( 'http://gabbay.org.uk/papers.html#semooc author's pdf).*nomgPlaceholder for future development. A general maths behind this definition is given in Section 8.1 of  &https://dl.acm.org/doi/10.1145/2700819Semantics Out Of Context ( 'http://gabbay.org.uk/papers.html#semooc author's pdf).+nomesub on a nominal abstraction substitutes in the label, and substitutes capture-avoidingly in the body,nomWNameless form of substitution, where the name for which we substitute is packaged in a  abstraction. -nom sub on names6nomsub on nameless type is trivial !"!" None .7=>?@ACXkQ<nomYl is unifiable with l' for any l and l' Should fail, taking e.g. l = [] and l' nonempty=nomns > ns' > x is unifiable with ns' > ns > x >nom&x' -> ns x -> res ns x unifies with x'?nomUnifiers correctly calculated @nom. equals .> extended with an identity mapping (since equality is on nub).Anom.Permutations and freshening renamings coincide<=>?@ABC<=>?@ABCNSyntax and reductions of the untyped lambda-calculus using the Nominal package(c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone /279=?@A_ Dnom%Terms of the untyped lambda-calculus Enom Variable Fnom Application GnomLambda, using abstraction-type Hnom#Variables are string-labelled namesInom(helper for building lambda-abstractions Jnom'weak head normal form of a lambda-term.Knom(x x) yLnomyMnom(x xy) xNnomxyPnom.Substitution. Capture-avoidance is automatic. DEFGHIJKLMN HDEFGJIKLMNF9 =Name-binding for dummies: tutorial on use of nominal package (c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone/=?@A_ UVVU;Syntax and reductions of System F using the Nominal package(c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone./12789=>?@AUV_fA -Wnom/Typeclass for things that can be pretty-printedZnomSystem F terms. KWe get swapping actions automatically, and also substitution of type names NTyp for types Typ. Substitution of term variables NTrm for terms Trm needs defined separately. [nom5Term variable, labelled by its display name and type \nomApply a term to a term ]nom.Nominal atoms-abstraction by a term variable. ^nomApply a term to a type_nom0Nominal atoms-abstraction by a type variable. `nomA term variable name anom;A term variable is labelled by a display name, and its typebnomDatatype of System F types We use Generic0 to deduce a swapping action for atoms of sorts i and hN. Just once, we spell out the definition implicit in the generic instance:  instance Swappable Typ where swpN n1 n2 (TVar n) = TVar $ swpN n1 n2 n swpN n1 n2 (t' :-> t) = swpN n1 n2 t' :-> swpN n1 n2 t swpN n1 n2 (All x) = All $ swpN n1 n2 xThis is boring, and automated, and that's the point: swappings distribute uniformly through everything including abstractors (the x under the All). p(The mathematical reason for this is that swappings are invertible, whereas renamings and substitutions aren't.)cnom Type variablednomType applicationenomType forall-abstractionfnom3A type variable name. Internally, this consists ofan atom of type  KAtom ATyp, anda label of type g", which is just a display name in l. gnom2A type variable is labelled just by a display namehnomWith  DataKinds , we obtain:ATyp, a type of atoms to identify type variables f, andATrm, a type of atoms to identify term variables `.See ' for more discussion of how this works.inomWith  DataKinds , we obtain:ATyp, a type of atoms to identify type variables f, andATrm, a type of atoms to identify term variables `.See ' for more discussion of how this works.jnomiNominal recursion scheme. We never use it because it's implicit in pattern-matching. See e.g. code for k, n, and X. knomCalculate type of term, maybelnom2Calculate type of term; raise error if none existsmnomm if term is typeable; n if not. nnomNormal form, maybe onom Normal form; raise error if nonepnom,True if term is normalisable; false if not. qnomBBuild type quantification from function: f ! " a.(f a) for fresh arnom:Build type lambda from function: f !  a.(f a) for fresh asnom:Build term lambda from function: f !  a.(f a) for fresh atnomTerm-to-term applicationunomTerm-to-type applicationvnom$polymorphic identity term = X x:X.xwnom.Another rendering of polymorphic identity termxnom0 = X s:X->X z:X.zynom3suc = x:("X.(X->X)->X->X) X s:X->X z:X.s(n[X] s z)znom1{nomnat|nom0Cast an Int to the corresponding Church numeral.}nomTransformer type = "X.X->X~nom*Self-application = x:"X.X->X.x["X.X->X] xnomGSubstitution acts on type variables. Capture-avoidance is automagical.nomSubstitute type variables with type in term variable. Non-trivial because a term variable carries a label which contains a type. Action is functorial, descending into the type label. nom*Substitute term variable with term in termnomPretty-print term nomPretty-print term variable nomPretty-print type nomPretty-print type variable (WXYZ[\]^_`abdecfghijklmnopqrstuvwxyz{|}~(higfbdecja`Z[\]^_klmnopWXYqrstuvwxyz{|}~Substitution properties (c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone-.>HEtnomy[n-> var n] = ynomn # y => y[n->x] = ynomn' # y => y[n->n'] = (n' n).yNone-.=>?HXHnom"For QuickCheck tests: pick a term nom!For QuickCheck tests: pick a typenom Pick an atomnom+We only care about short and simple stringsNoneK.nom Find integers and increment themnomRewrite rewrites inside a [Int] nom"Rewrite rewrites inside a list of h-labelled namesNone.>XUF nomJNom creates local binding, which is unpacked separately by equality. Cf.  UnifySpec" to see how this can be addressed.nom<Check restriction creates local scope. Should return False.nom%n' # n if n' is chosen fresh, after nnomfreshName () /= freshName ()7 Lazy evaluation means distinct fresh names generated.nomSame thing using let.nomQBut if we unpack a single fresh name monadically, we can compare it for equality.nom ~ (n # (n,n'))nom n # n'nom(Nom Maybe -> Maybe Nom -> Nom Maybe = idnom(Maybe Nom -> Nom Maybe -> Nom Maybe = idnomCommute Nom and ListnomCommute Nom and Nom (one way)None&',7=>?@ACSX{nombTakes a context and an output and modifies the output such that it can be consumed by the context.nom<Sanity check: every arbitrary chunk is indeed a valid chunk.nomMSanity check: every arbitrary chunk is indeed a valid chunk (alternate test).nomLSanity check: every arbitrary chunk is equal to itself (not trivial because p instance is nontrivial)nomBSanity check: not every chunk is a blockchain (might have UTxIs)! nomESanity check: an arbitrary transaction is indeed a valid transaction.nomCSanity check: an arbitrary blockchain is indeed a valid blockchain.nomXSanity check: arbitrary instance of TB generates a blockchain, which is equal to itself.9/ must be used here, because of the local scope. nomBlockchain has no UTxIsnomChunk is equal to itselfnomThere are two different chunksnom"Empty chunk is prefix of any chunknom The tail of a chunk, is a chunk.nom7The tail of a chunk, is a prefix of the original chunk.nom8The tail of a chunk, generating fresh atoms if required nomThe tail of a chunk, is a prefix of the original chunk. Gotcha version, that doesn't have the Nom bindings: expect failure here.nomPlausible-but-wrong  is wrong: expect failure here. nom Underbinding/ is when not enough atoms are bound in a chunk nom Overbinding- is when too many atoms are bound in a chunk nom@Gotcha: Fails because loss of information from two Nom bindings.nom>Succeeds because one Nom binding thus no loss of information. nomIIf you reverse the order of transactions in a chunk, it need not be validnomaIf two transactions are apart, they can be validly combined. | Corresponds to Lemma 2.14(1) of  $https://arxiv.org/pdf/2003.14271.pdfEUTxO- vs account-based smart contractblockchain programming paradigms.nomTIf two chunks are apart, they can be validly combined. | Extends Lemma 2.14(1) of  $https://arxiv.org/pdf/2003.14271.pdfEUTxO- vs account-based smart contractblockchain programming paradigms.nomTIf two chunks are apart, they can be validly commuted. | Extends Lemma 2.14(1) of  $https://arxiv.org/pdf/2003.14271.pdfEUTxO- vs account-based smart contractblockchain programming paradigms#. We use smaller chunks for speed.nom3This corresponds to a key result, Lemma 2.14(2) of  $https://arxiv.org/pdf/2003.14271.pdfEUTxO- vs account-based smart contractblockchain programming paradigms.33None; nom fuse a.x a.x' = a.(x,x')nomn # x => [n](x  n) = x@nom n' # x => [n]x = [n'](n' n).xnom  (n.x) @ n = xnom (n.x) @ n' = (n' n).x nom4Atm.(X x Y) iso Atm.X x Atm.Y, left-to-right-to-left!nom5Atm.(X x Y) iso Atm.X x Atm.Y, right-to-left-to-right"nomuIso fails if atoms labelled, since one label lost Atm.X x Atm.Y -> Atm.(X x Y), and one label invented if list empty #nomAtm.X iso Nom (Atm x X)$nomNom (Atm x X) iso Atm.X. 9Note: We have to use unifiability because of local scope.  !"#$  !"#$None-.>H %nomy[n-> var n] = y)nomn # y => y[n->x] = y-nomn' # y => y[n->n'] = (n' n).y1nom.(id id) has no type (it needs a type argument)2nomNot all terms are typeable5nomjType soundness If a term is typeable and normalisable then its normal form has the same type as it does. 6nomtypeof(id t) = typeof(t)7nomIf x : t then (id t x) --> x8nom0 : nat9nom i+1 /= 0 :nom i+1 /= i ;nomi : nat%&'()*+,-./0123456789:;%&'()*+,-./0123456789:;.AImplementation of nominal techniques as a Haskell package, tests (c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone"?A simple assembly language, with binding and variable-swapping (c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone/79=?@A <nomTerms of our assembly language =nomReturn a value >nom"Swap the contents of two variables?nomwAdd two operands and store the value in a fresh variable which is local to subsequent computation (the third argument) @nom.An operand is an integer literal or a variableCnom#Variables are string-labelled namesDnomEvaluate an operand. .A literal maps to its corresponding integer. 0If asked to evaluate a free variable, complain. Enom<Normalise a program by executing any embedded Swp commands. FnomEvaluate a program Gnom'Add 1 2 [v] Add v v [w] Swp v w Ret w Hnom3 InomSubstitution as standard on @RnomSubstitution on <rams is generic <?>=@ABCDEFGH C@AB<?>=DEFGH)A simple assembly language, with binding (c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone/79=?@A SnomTerms of our assembly language TnomReturn a value UnomwAdd two operands and store the value in a fresh variable which is local to subsequent computation (the third argument) Vnom.An operand is an integer literal or a variableYnom#Variables are string-labelled namesZnomEvaluate an operand. .A literal maps to its corresponding integer. 0If asked to evaluate a free variable, complain. [nomEvaluate a program \nomAdd 1 2 [v] Add v v [w] Ret w ]nom6 ^nomSubstitution as standard on VgnomSubstitution on Srams is generic SUTVWXYZ[\] YVWXSUTZ[\]/9Implementation of nominal techniques as a Haskell package(c) Murdoch J. Gabbay, 2020GPL-3murdoch.gabbay@gmail.com experimentalPOSIXNone !"#$%&'()*+,-]^_`abcdefgh&'()*+,-./0123456789:;<=_`abcdefghijklmnopqr !"0123456789:;<=>?@AABCDCEFGHIJKLMKNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ $%$&        '                             ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 ( 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N M O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~  )),,      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUV+W*XYZ[\]^_`abcdefghijklmnop^q]rstuvwxyz{#"|}~_  -    !"#$%&'()*+,-./0123456789:;<=>?@AB^[CDEaFGHIJKLMNOP=>@AB^[CEaFGHIJKLMNOPQRSTUVTUWQRXTYZQR[QR\T]^Q_`TabTYcTYdTefTghTYiTYj k lQ_m n opqTUrTstu"nom-0.1.0.2-Cei0dwnsIrWHLKrPA11A4SLanguage.Nominal.UniqueLanguage.Nominal.UtilitiesLanguage.Nominal.NameLanguage.Nominal.NameSetLanguage.Nominal.SMonad'Language.Nominal.Properties.NameSetSpecLanguage.Nominal.NomLanguage.Nominal.Examples.GraphLanguage.Nominal.Binder$Language.Nominal.Properties.NameSpecLanguage.Nominal.Examples.StyleLanguage.Nominal.AbsLanguage.Nominal.UnifyLanguage.Nominal.Equivar'Language.Nominal.Properties.EquivarSpec(Language.Nominal.Examples.IdealisedEUTxOLanguage.Nominal.Sub%Language.Nominal.Properties.UnifySpec'Language.Nominal.Examples.UntypedLambda"Language.Nominal.Examples.Tutorial!Language.Nominal.Examples.SystemF#Language.Nominal.Properties.SubSpec)Language.Nominal.Properties.SpecUtilities)Language.Nominal.Properties.UtilitiesSpec#Language.Nominal.Properties.NomSpec7Language.Nominal.Properties.Examples.IdealisedEUTxOSpec#Language.Nominal.Properties.AbsSpec0Language.Nominal.Properties.Examples.SystemFSpec#Language.Nominal.Examples.Assembly2#Language.Nominal.Examples.Assembly1Language.Nominal.NamesetKSupportASortATypATrmNomKNom transposeNomF@@KAbsChunkiprop_fresh_renprop_unify_renVal%prop_warningNotChunkTail_is_not_chunk$Language.Nominal.Properties.AllTestsLanguage.NominalUnique newUnique hashUnique $fEqUnique $fOrdUnique $fDataUniquerewrite repeatedlychaintoMaybe isSubsetOf interleavesafeTailsafeHead.:iotapointNameless getNamelessNameKName nameLabelnameAtomPermKPerm SwappablekswpAtomTomKAtomatTom freshKAtomsIO freshAtomsIO freshKAtomIO freshAtomIOswpperm withLabel withLabelOf justALabel justAnAtomkswpNswpN $fShowKAtom $fShowKName $fShowKName0 $fOrdKName $fEqKName$fGSwappableM1$fGSwappable:+:$fGSwappableV1$fGSwappableU1$fGSwappable:*:$fGSwappableK1$fSwappableNameless$fSwappableKName$fSwappableKAtom$fSwappableMap $fSwappable->$fSwappableEither$fSwappable(,,,,)$fSwappable(,,,)$fSwappable(,,)$fSwappable(,)$fSwappableSet$fSwappableNonEmpty $fSwappable[]$fSwappableMaybe $fEqKAtom $fOrdKAtom$fGenericKAtom $fDataKAtom$fEqTom$fOrdTom $fGenericTom $fDataTom$fGenericKName$fFunctorKName$fFoldableKName$fTraversableKName $fDataKName$fShowNameless$fReadNameless $fEqNameless $fOrdNameless$fSwappableChar $fSwappable()$fSwappableInteger$fSwappableInt$fSwappableBoolRestrict KRestrictrestrictSupportksuppsuppkapartapart atomPoint namePoint restrictN$fKRestrictsMaybe$fKRestrictsNameless$fGSupports:+: $fGSupportsM1 $fGSupportsV1 $fGSupportsU1$fGSupports:*: $fGSupportsK1$fKRestrictsSet$fKRestricts[]$fKSupportsEither$fKSupports(,,,,)$fKSupports(,,,)$fKSupports(,,)$fKSupports(,)$fKSupportsSet$fKSupportsNonEmpty $fKSupports[]$fKSupportsMaybe$fKSupportsKName$fKSupportsKAtom$fKSupportsNameless$fKRestrictChar $fKRestrict()$fKRestrictInt$fKRestrictBool$fKSupportInteger $fKSupportInt$fKSupportChar$fKSupportBool $fKSupport()XResXSwpXSuspendSuspend ViaSMonad runViaSMonadSMonad>>+enterexit+<<imappamiexitWithwithExitiactgetSwpgetRes transposeMF transposeFM$fMonadViaSMonad$fApplicativeViaSMonad$fFunctorViaSMonad$fSMonadiXSuspend$fFunctorXSuspend$fApplicativeXSuspend$fMonadXSuspend$fGenericXSuspend$fSwappableXSuspend $fEqXSuspend$fShowXSuspendprop_supp_apartprop_supp_apart_atomgetNomreskresreResresNunNomnomToIO freshKAtom freshAtom freshKAtoms freshAtoms freshKName freshKNames freshName freshNames freshKNameIO freshKNamesIO freshNameIO freshNamesIO $fShowKNom$fEqKNom$fAlternative:.$fKRestricttKNom$fKRestrictsKNom$fKSupporttKNom$fSMonad[]KNom$fSwappableKNom $fGenericKNom $fFunctorKNom$fApplicativeKNom $fMonadKNomGraphEmptyVertexOverlayConnectfoldg filterApart$fKRestrictTomGraph $fShowGraph$fGenericGraph$fSwappableGraph BinderConcconccnoc BinderSupp getBinderSuppBinder@>resMay:@@!@@!@@.nomAppnomAppCgenAppgenAppCresAppresAppCresAppC'newAnew freshForAfreshForisTrivialNomBySuppisTrivialNomByEqkfreshenfreshen kbinderToNomknomToMaybeBinder knomToBinder binderToNomnomToMaybeBinder nomToBinder $fDatactxbody$fBinderKNom[]as$fKSupportsBinderSupp$fBinderConcKNom[]as[]$fBinderConcKNom[]asProxy$fBinderConcKNom[]as()$fGenericBinderSupp$fSwappableBinderSuppprop_namelabel prop_twonamesprop_singleswapprop_freshswapprop_doubleswapprop_doubleswap_fresh'prop_doubleswap_freshprop_swap_symmbad_countBindingbad_countOrder badRestrict okRestrictbadEqAbs:@>abstabst'fuseunfuseabsLabelabsToNomnomToAbsabsFresh absFresh' absFuncOut$fApplicativeKAbs $fShowKAbs$fEqKAbs$fBinderConcKAbsnasn$fBinderKAbsKNameas $fGenericKAbs $fFunctorKAbs$fSwappableKAbs$fKSupportKAbs UnifyPerm KUnifyPerm kunifyPermrenRenKRenunRenidRen nothingRen isJustRen isNothingRenrenNub renExtend renToList renFromListrenRemoveBlock unifyPermkunifiablePerm unifiablePerm kevPrefixRen evPrefixRen kevIsPrefix evIsPrefix$fKRestrictsKRen $fMonoidKRen$fSemigroupKRen$fKSupportsKRen $fOrdKRen$fEqKRen$fSwappableKRen$fGUnifyPermsM1$fGUnifyPerms:+:$fGUnifyPermsV1$fGUnifyPermsU1$fGUnifyPerms:*:$fGUnifyPermsK1$fKUnifyPermsKAbs$fKUnifyPermsKNom$fKUnifyPermsKName$fKUnifyPermsKAtom$fKUnifyPermsEither$fKUnifyPermsMaybe$fKUnifyPermsNonEmpty$fKUnifyPerms[]$fKUnifyPerms(,,,,)$fKUnifyPerms(,,,)$fKUnifyPerms(,,)$fKUnifyPerms(,)$fKUnifyPermsNameless $fShowKRen $fGenericKRen$fKUnifyPermInteger$fKUnifyPermInt$fKUnifyPermChar$fKUnifyPermBool$fKUnifyPerm()EvFinMap KEvFinMapEvFunKEvFunrunEvFunkevRepevRepkevNubevNubkevLookupList' kevLookupList evLookupList kevLookupevLookup$$ constEvFinMap extEvFinMapevFinMap fromEvFinMap$fKSupportsKEvFun$fSwappableKEvFun$fKUnifyPermsKEvFinMap $fEqKEvFinMap$fKSupportsKEvFinMap$fShowKEvFinMap$fGenericKEvFinMap$fSwappableKEvFinMapprop_atoms_one_orbitprop_atomssq_orbitIEq Blockchain getBlockchain chunkToTxListValFinValTriv ValidatorvalidateHasOutputPositionsoutputPositionsHasInputPositionsinputPositionsContext Transaction TransactionFOutputInputPosition outputsOfTx inputsOfTxtxPoint contextsOfTx utxosOfChunk utxisOfChunk contextPos utxcsOfChunktransactionValidsingletonChunkunsafeSingletonChunk txListToChunknomTxListToNomChunknomTxListToChunk exampleCh0 exampleCh1 exampleCh2 exampleCh12 exampleCh21 exampleCh12' appendTxChunkappendTxMaybeChunk concatChunksafeConcatChunk genUnNomChunk isPrefixChunk chunkLength chunkHead chunkTailwarningNotChunkTail chunkTakeEnd subTxListOf reverseTxsOf chunkToHdTl chunkToHdHdTl blockchainchunkBindingOKchunkValidatorsOKisChunkisChunk' isBlockchain isBlockchain' equivChunk$fKUnifyPermTomInput$fSwappableInput$fKSupportTomInput$fKUnifyPermTomOutput$fSwappableOutput$fKSupportTomOutput$fKUnifyPermTomTransactionF$fSwappableTransactionF$fKSupportTomTransactionF$fKUnifyPermTomTransactionF0$fSwappableTransactionF0$fKSupportTomTransactionF0$fValidatorrdValTriv$fValidatorrdValFin $fEqValFin $fMonoidMaybe$fSemigroupMaybe$fPartialMonoidChunk$fPartialSemigroupChunk$fKRestrictTomChunk $fEqChunk$fBinderChunk[][]Tom$fKUnifyPermTomBlockchain$fKSupportTomBlockchain$fSwappableBlockchain $fIEqOutput$fIEq[]$fIEq->$fValidatorrdVal $fShowVal$fGHasInputPositionsM1$fGHasInputPositions:+:$fGHasInputPositions:*:$fGHasInputPositionsU1$fGHasInputPositionsV1$fGHasInputPositionsK1$fHasInputPositionsTransactionF$fHasInputPositionsNonEmpty$fHasInputPositions[]$fHasInputPositions(,)$fHasInputPositionsOutput$fHasInputPositionsInput$fGHasOutputPositionsM1$fGHasOutputPositions:+:$fGHasOutputPositions:*:$fGHasOutputPositionsU1$fGHasOutputPositionsV1$fGHasOutputPositionsK1$fHasOutputPositionsKNom $fHasOutputPositionsTransactionF$fHasOutputPositionsNonEmpty$fHasOutputPositions[]$fHasOutputPositions(,)$fHasOutputPositionsOutput$fHasOutputPositionsInput $fShowInput $fEqInput $fOrdInput$fGenericInput $fShowOutput $fEqOutput $fOrdOutput$fGenericOutput$fGenericTransactionF $fEqValTriv $fOrdValTriv $fShowValTriv $fReadValTriv$fGenericValFin $fShowValFin$fSwappableValFin$fKRestrictValFin$fKSupportValFin $fShowChunk$fGenericChunk$fShowBlockchain$fGenericBlockchain$fIEqVal$fSwappableVal$fKRestrictVal $fKSupportVal $fIEqInput $fIEqKEvFun$fKSupportChunk$fKUnifyPermChunk$fSwappableChunk$fKUnifyPermValFin$fKSupportValTriv$fKUnifyPermValTriv$fSwappableValTriv$fShowTransactionF$fEqTransactionF$fEqTransactionF0SubKSubsub $fGSubnx:+: $fGSubnxM1 $fGSubnxV1 $fGSubnxU1 $fGSubnx:*: $fGSubnxK1 $fKSubn->-> $fKSubn->->0$fKSubKNamexKAbs$fBinderConcKAbsKNameysx$fKSubKNameKNameKName$fKSubnxEither $fKSubnxMaybe$fKSubnxNonEmpty $fKSubnx[]$fKSubnx(,,,,) $fKSubnx(,,,) $fKSubnx(,,) $fKSubnx(,)$fKSubnxNameless $fKSubInteger $fKSubInt $fKSubChar $fKSubBool$fKSub() prop_l_l' prop_res_resprop_res_unres prop_renIdprop_fresh_ren_atmlistlistprop_fresh_ren_absatmlistExpV:@LamVarlamwhnfexample1 example1whnfexample2 example2whnf $fShowExp$fKSubKNameExpExp$fEqExp $fGenericExp $fDataExp$fSwappableExpMyName MyNameLabelPPpppppTrmAppTAppTLamNTrm NTrmLabelTypTVar:->AllNTyp NTypLabel typRecursetypeOftypeOf'typeablenfnf' normalisabletalltlam@.@:idTrmidTrm2zerosuconenatchurch transformselfapp$fKSubKNameTypTyp$fKSubKNameTypKName$fKSubKNameTrmTrm $fShowMaybe $fShowTyp $fShowMaybe0 $fShowTrm$fPPTrm $fPPKName$fPPTyp $fPPKName0 $fDataATyp $fDataATrm$fEqTyp $fGenericTyp$fSwappableTyp $fDataTyp$fEqTrm $fGenericTrm$fSwappableTrm $fKSubTrm $fDataTrm iprop_sub_idprop_sub_id_typevar'prop_sub_id_termvarprop_sub_id_typevariprop_sub_freshprop_sub_fresh_typevar'prop_sub_fresh_typevarprop_sub_fresh_termvariprop_sub_permprop_sub_perm_typevar'prop_sub_perm_typevar''prop_sub_perm_termvarprop_sub_singleton1prop_sub_singleton2prop_sub_abs_1prop_sub_abs_1'prop_sub_abs_3 myatomnames myUniquesmyAtomsarbitrarySizedTyparbitrarySizedTrm genEvFinMap$fArbitraryKEvFinMap$fArbitraryNonEmpty$fArbitraryTrm$fArbitraryTyp$fArbitraryKNom$fArbitraryKAbs$fArbitraryKName$fArbitraryKName0$fArbitraryKAtom $fArbitrary[] superSuccprop_test_rewrite1prop_test_rewrite2 prop_x_neq_xprop_split_scopeprop_fresh_neqprop_fresh_neq'prop_fresh_neq'' prop_fresh_eqprop_freshFor1prop_freshFor2prop_transposeNomMaybeprop_transposeMaybeNom prop_new' prop_not_new'prop_newprop_freshFor_notElemiprop_support_nomprop_support_nom_atmlistprop_support_nom_nomatmlistiprop_freshen_apartprop_freshen_apart_atmlistprop_freshen_apart_nom_atmlistprop_freshen_apart_disjointprop_isTrivial_equalprop_isTrivial_saneprop_isTrivial_sane' deBruijnAcc deBruijn1 deBruijn2prop_transposeNomListprop_transposeNomNomValProxyCValTC'TXTBSmallTCTCTVTDTRFixable fixOutput SmallChunkValidTx fromValidTxfixChunkToBlockchain atValTrivatValFinvalTrivvalFinwithValprop_arbitraryChunkIsValidprop_arbitraryChunkIsValid'prop_arbitraryChunkEqCheckprop_notEveryChunkBlockchainprop_arbitraryTxIsValidprop_arbitraryBlockchainIsValidprop_blockchainToChunkAndBackprop_blockchainHasNoUTxIsprop_chunkrefl prop_chunkneqprop_emptyIsPrefixprop_chunkTail_is_chunkprop_chunkTail_is_prefix genChunkTailprop_chunkTail_is_prefix_gotchaprop_underbindingprop_overbinding"prop_chunkHead_chunkTail_recombineprop_chunkHdTl_recombineprop_reverseIsNotValidprop_subchunksValidprop_apart_is_valid_txprop_apart_is_valid_chobserveprop_chunk_apart_commutesprop_validity_fresh$fArbitraryTransactionF$fArbitraryTransactionF0$fArbitraryOutput$fArbitraryValFin$fArbitraryValTriv$fArbitraryInput$fArbitraryChunk$fArbitraryValidTx$fArbitrarySmallChunk$fArbitraryBlockchain$fFixablerdValTriv$fFixablerdValFin$fFixablerdVal$fArbitraryValProxy$fShowValProxy $fShowValidTx$fGenericValidTx$fShowSmallChunk prop_fuse prop_Abs_Concprop_Abs_alpha prop_Conc_Absprop_Conc_Abs_swapprop_fuse_unfuse_Absprop_unfuse_fuse_Absprop_unfuse_fuse_Abs'prop_abs_to_nomprop_nom_to_absprop_untypeableprop_all_typeableprop_typeable_nfprop_nf_typeableprop_type_soundnessprop_id_type_unchanged prop_app_idprop_typeof_zeroprop_church_numerals0prop_church_numerals1prop_church_numerals_typeProgRetSwpAddOperandLit evalOperand normaliseProgevalProg example1eval$fKSubKNameOperandOperand $fEqOperand$fGenericOperand$fSwappableOperand $fShowOperand$fEqProg $fGenericProg$fSwappableProg $fShowProg $fKSubProgghc-prim GHC.TypesIntbase GHC.MaybeJustNothingBoolGHC.BaseStringTrueFalseGHC.Err undefined GHC.ClassesEq Data.ProxyProxyfmapFunctorData.Traversable Traversable GHC.IO.UnsafeunsafePerformIOflipconstisSorted isSortedBy<=absNameabsApp kevLookup'positionsOfTxsMaybeGHC.Listtake