2&      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJK L M N 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:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./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,[,\,],^,_,`,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.{.|.}.~...////////////////////////////////////////////00000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111 1 1 1 1 1111111111111112222 2!2"2#2$2%2&2'2(2)2*2+3,3-3.3/303132333435363738393:3;3<3=3>3?3@3A3B3C3D3E3F3G3H3I3J3K3L3M3N3O3P3Q3R3S3T3U3V3W3X3Y3Z3[4\4]4^4_4`4a4b4c4d4e4f4g4h4i4j4k4l4m4n4o4p4q4r4s4t4u4v4w4x4y4z4{4|4}4~4444444444444444444444444444445555555555555555555555566666666666666777778888888888888889999999999999999999::::::::::::::::::::::::::::::::: : : ; ; ;;;;;;;;;;;;;;;;;;; ;!;";#;$;%;>+&'()*+,-Standard HList stuff... .AOur (safe) handle is labeled with the monad where it was created /04RMonadIO is an internal class, a version of MonadIO 1234@Raise from one IORT to another: this class lets the user access  handles of an ancestor region % MonadRaise m1 m2 holds when either  * m2 is the same as m1, or : * m2 is the sequence of one or more IORT applied to m1. = In other words, MonadRaise m1 m2 holds if m1 is an improper  suffix of m2. 5@A simple abstract data type to track the duplication of handles  using reference counting 6 DThe IO monad with safe handles and regions (SIO) is implemented as 9 the monad transformer IORT (recursively) applied to IO. 2Each region maintains the state listing all open ! handles assigned to the region. C Since we already have IO, it is easy to implement the state as a : mutable list (IORef of the list) and make this reference  a pervasive environment. F We could have used implicit parameters or implicit configurations to / pass that IORef around. Here, we use ReaderT. 789:; 6Lift from one IORT to an IORT in a children region... D IORT should be opaque to the user: hence this is not the instance  of MonadTrans <DThe following makes sure that a low-level handle (System.IO.Handle) G cannot escape in an IO exception. Whenever an IO exception is caught, B we remove the handle from the exception before passing it to the  exception handler. => @There is no explicit close operation. A handle is automatically > closed when its region is finished (normally or abnormally). 9Create a new handle and assign it to the current region J One can use liftIORT (newSHandle ...) to assign the handle to any parent  region. Safe-handle-based IO... ? The handle is assigned to the current region or its ancestor. B So, we have to verify that the label of the handle is the prefix E (perhaps improper) of the label of the monad (label of the region). FDuplicate a handle, returning a handle that can be used in the parent E region (and can be returned from the current region as the result). 9 This operation prolongs the life of a handle based on a F _dynamic_ condition. If we know the lifetime of a handle statically, D we can execute liftSIO (newSHandle ...) to place the handle in the  corresponding region. If we don' t know the lifetime of a handle K statically, we place it in the inner region, and then extend its lifetime F by reassigning to the parent region based on the dynamic conditions. "It seems however that IOErrors don't invalidate the Handles. ? For example, if EOF is reported, we may try to reposition the file  and read again. That'4s why in Posix, EOF and file errors can be cleared. Useful for debugging Bmake IORef available with SIO, so we may write tests that attempt > to leak handles and computations with handles via assignment ?NThe following is the general definition. It required the following extensions  9 {-# LANGUAGE EmptyDataDecls, FunctionalDependencies #-} = {-# LANGUAGE UndecidableInstances, OverlappingInstances #-} Fto implement the disjunction present in the definition of MonadRaise. 9 In particular, OverlappingInstances are needed for TEQ.      @ABCDEFDarn! GHC doesn'5t provide the real select over several descriptors! # We have to implement it ourselves GAlas, GHC provides no function to read from Fd to an allocated buffer. G The library function fdRead is not appropriate as it returns a string  already. I'!d rather get data from a buffer. C Furthermore, fdRead (at least in GHC) allocates a new buffer each E time it is called. This is a waste. Yet another problem with fdRead 9 is in raising an exception on any IOError or even EOF. I' d rather  avoid exceptions altogether. 4The following fseek procedure throws no exceptions. G<Convert a file descriptor to an FDSet (for use with select) ? essentially encode a file descriptor in a big-endian notation HI0poll if file descriptors have something to read - Return the list of read-pending descriptors JKL8Interface with my sys_open, see sys_open.c for detailed  description and comments 6Close the output direction of the bi-directional pipe  -A very simple language of format descriptors !"#$&Needed only for the sake of Haskell98 G If we are OK with flexible instances, this newtype can be disposed of %&'M)These two instances are all we ever need  !"#$%&NOPQR'S $%&"#! ' ! !"##$%&%&'()*+,-./012345678()*+,-./0123456TUVWXYZ[\]^_`78./0123,-4*+()5678())*++,--./0123/012345678 abcdef'Primitive format descriptors used here gh9Converting from formatting strings to format descriptors 9i356995639:;:;jklmnopqrstuv:;:;;<Printerparsers (injectionprojection pairs) =>?@ABCDHa bit of syntactic sugar to avoid hitting the Shift key too many a time EThe interpreter for printf  It implements Asai'"s accumulator-less alternative to  Danvy's functional unparsing FThe interpreter for scanf GHILThe format specification is first-class. One can build format specification  incrementally  This is not the case with OCaml's printf/scanf (where the B format specification has a weird typing and is not first class). Primitive Printer/parsers JA better prefixOf function  prefix patt str --> Just str' B if the String patt is the prefix of String str. The result str'  is str with patt removed " Otherwise, the result is Nothing <=>?@ABCwxyzDEFGH{|}~IJ>CBA@?<=DEFGHIJ<==>CBA@??@ABCDEFGHIJ K Problem 2 CAnne, Bill and Cath each have a positive natural number written on = their foreheads. They can only see the foreheads of others. B One of the numbers is the sum of the other two. All the previous G is common knowledge. The following truthful conversation takes place:   Anne: I don't know my number.  Bill: I don't know my number.  Cath: I don't know my number. + Anne: I now know my number, and it is 50. 'What are the numbers of Bill and Cath? , Math Horizons, November 2004. Problem 182. "A possible world for a problem 1: * numbers received by Anne, Bill, and Cath L Problem 1 8 Anne and Bill each privately receive a natural number.  Their numbers are consecutive. 2 The following truthful conversation takes place:   Anne: I don't know your number ' Bill: I don't know your number either  Anne: I know your number.  Bill: I know your number too. 7If Anne has received the number 2, what was the number  received by Bill?  This puzzle is also known as `Conway paradox' : it appears C that Anne and Bill have truthfully made contradictory statements. "A possible world for a problem 1: # numbers received by Anne and Bill M(The number Anne received in the world w N(The number Bill received in the world w O3An initial stream of possible worlds for problem 1 P?Encoding the statement of the problem: the conversation steps. 5 The remaining possible world gives us the solution. QA variation of the problem:  Assuming the numbers don't exceed 100, what , are the numbers received by Anne and Bill? = Again, the possible worlds consistent with the statement of  the problem are the solutions. RSpelling out the _) condition, to demonstrate what it means SThe number on Anne's forehead in the world w T!If Anne sees the number x on Bill's forehead and the  number y on Cath'"s forehead, what numbers could be  on Anne' s forehead? 4 In other words, compute the set of possible worlds 7 that are indistinguishable from the world w as far as  Anne is concerned. UThe number on Bill's forehead in the world w VWhich worlds Bill can't distinguish WThe number on Cath's forehead in the world w XDitto for Cath Y4An initial stream of possible worlds for problem 2. 3 The code is naive but hopefully obviously correct < as it clearly corresponds to the statement of the problem. Z?Encoding the statement of the problem: the conversation steps. 5 The remaining possible world gives us the solution. [Reverse application \A stream of naturals ]%A stream of integers starting with n ^ Filter a set of possible worlds ? Given a proj function (yielding a set of keys for a world w), 4 return a stream of worlds that are not unique with 3 respect to their keys. That is, there are several  worlds with the same key. + Our state is a set of quarantined worlds. 5 When we receive a world whose key we have not seen, 2 we quarantine it. We release from the quarantine ' when we encounter the same key again. < Our function is specialized to the List monad. In general, J we need MonadMinus (see the LogicT paper), of which List is an instance. _>Given a proj function (yielding a set of keys for a world w), 0 return a stream of worlds that are unique with 3 respect to their keys. That is, there is only one  world for the key. $ We accept a termination criterion. 7 We terminate the stream once we have received the key ' for which the criterion returns true. 5 When we receive a world whose key we have not seen, 2 we quarantine it. We release from the quarantine  when the stream is terminated. KLMNOPQRSTUVWXYZ[\]^_LMNOPQRKSTUVWXYZ[\]^_KLMNOPQRSTUVWXYZ[\]^_ .`abcdefghijklmnopqrstuvwxyz7The implementation of the interpreter ShowAs shows off = the technique of accumulating new TQ as we traverse the old ( one. We shall see more examples later. . One is again reminded of attribute grammars. {|}~ The view interpreter , The first interpreter is to view the types = The language of type representations: first-order and typed % It is quite like the language of intnegadd we have seen before,  but it is now typed. @ It is first order: the language of simple types is first order -TQ is itself an interpreter, the trivial one A`abcdefghijklmnopqrstuvwxyz{|}~-|}~z{xyvwstupqrmnojklhifgdebc`a-`aabccdeefgghiijklklmnonopqrqrstutuvwwxyyz{{|}~}~<  , .The Semantic monad The order of quantification Semantic forms 8Example from Sec 4.3 of the ESSLLI Advanced ACG course. IAn interpretation of the abstract signature as the surface form: strings 9An interpretation of the base type btyp in the signature  labeled by lab HAbstract signature, which defines base types, constants and their types Movement2 into the position of the prompt selected by psel @Logical forms of sample terms in different semantic environment Auxiliary functions Generate a new variable name 3.. Extension: the ordinary lam Another interpreter # Literally the same as Symantics.S 5 Although I later decided to print linear lambdas as ! x -> ... )Interpreting lam is quite more different  Why? ( Why the simple approach does not work? 9 We need to produce ho when the lambda-form is produced, 3 not when it is applied. But ho of the lambda-form 7 includes the ho for the body of lambda. The latter is ; the result of evaluating the body; but we get to evaluate > the body of the lambda only when the lambda-form is applied. ; But we need that ho now. Fortunately, types are enough to  produce ho. That''s the purpose for the type class HiHo. Typed and tagless evaluator % object term ==> metalanguage value The reason we separate out ! is to expose the type variables L hi and ho in the class head. A particular instance might be able to attach > constraints to hi and ho. The instance for the R interpreter & indeed attaches the HiHo constraint. ?This semantics assumes that all values (that is, substitutable : things) are closed terms. This is the case in CBV or CBN - calculi, which never evaluate under lambda. = Therefore, we do not qualify the types of values by the env 8 Otherwise, we have to qualify each type such as Int or  a with its env. 8 For the unextended linear lambda calculus below, we don't ? need to make this restriction as substitution of linear terms  into linear terms doesn'"t violate the linearity. But that - property is not stated syntactically below. 6 Stating it syntactically does seem possible, but the " code becomes quite more complex. 4Now, non-linear terms like tl2 and the K combinator  become expressible 2The following does not type-check, although it is `morally correct' ( Syntactically, the term is non-linear! 5 The linear calculus without extensions did not have 3 the problem of being too conservative: a function " cannot avoid using its argument. 9 So, a term that is syntactically linear is semantically  linear, and vice versa. < It is only when we added general lambdas that the calculus 7 became conservative: a function like the K combinator - can disregard its argument expression. So, 3 a term that is syntactically non-linear may still - end up using each argument expression once. / In general, we have to evaluate it to see it. 1 tg6 = lam ((tgk `app` z) `app` (add (int 1) z)) <the following are OK because we never evaluate under lambda 0 All values are always closed terms. Therefore, 5 even though a non-linear function may replicate its 4 arguments, it replicates values -- never variables We extend the interpreters C FThe result of subtraction was not needed, and so it was not performed  OTH, (int 5  int 5) was computed four times Call-by-value LInterpretation of EDSL expressions as values of the host language (Haskell) @ An EDSL expression of type a is interpreted as a Haskell value 7 of the type SName m a, SValue m a or SLazy m a, where 5 m is a Monad (the parameter of the interpretation). .The (higher-order abstract) syntax of our DSL A convenient abbreviation A sample EDSL term The addition (x * x) is performed twice because y is bound , to a computation, and y is evaluated twice A more elaborate example A better example  -We reuse most of EDSL (SName) except for lam    7We now evaluate the previously written tests t, t1, t2  under the new interpretation  Call-by-need  (Could be automatically derived by GHC. (Could be automatically derived by GHC.  Call-by-name ACould be automatically derived by GHC. But we stick to Haskell98 %               3 The crucial role of repr being a type constructor 9 rather than just a type. It lets some information about 5 object-term representation through (the type) while + keeping the representation itself hidden.    * Extensions of the language  Multiplication ! R is not a tag! It is a newtype ; The expression with unR _looks_ like tag introduction and < elimination. But the function unR is *total*. There is no > run-time error is possible at all -- and this fact is fully  apparent to the compiler. = Furthermore, at run-time, (R x) is indistinguishable from x $ * R is a meta-circular interpreter 9 This is easier to see now. So, object-level addition is = _truly_ the metalanguage addition. Needless to say, that is  efficient. 7 * R never gets stuck: no pattern-matching of any kind  * R is total    Another interpreter ?The language is simply-typed lambda-calculus with fixpoint and # constants. It is essentially PCF. @ The language is just expressive enough for the power function. ; We define the language by parts, to emphasize modularity. C The core plus the fixpoint is the language described in the paper THongwei Xi, Chiyan Chen, Gang Chen Guarded Recursive Datatype Constructors, POPL2003  which is used to justify GADTs.  Core language  !"#' !"#      !"# !"# !"#$%&'() $%&'()$%&'()$%&'%&'()*+,-./0123456789:;<=>?@ABA*+,-./0123456789:;< !="#$%&>?@'()*+,-./012345AB6789:;<=>?@ABCDE<789:;6345012=-./>?@*+,AB*+,+,-././01212345456789:;89:;<=>?@ABCDEFGHIJKLMNO.The (higher-order abstract) syntax of our DSL P A convenient abbreviation (could've been called bind) QA sample EDSL term RSA more elaborate example TUVWXYZ[F;We use IO to print out the evaluation trace, so to observe % the difference in evaluation orders #CDEFGHIJKLMNOPQRGSHTIUVWJKLXYZ[MNOPOIJKLMNPQFGHERSTDUVWXCYZ[CDEFGHGHIJKLMNJKLMNOPQRSTUVWXYZ[\]FThe result of subtraction was not needed, and so it was not performed  | OTH, (int 5 g int 5) was computed four times ^ Call-by-name _LInterpretation of EDSL expressions as values of the host language (Haskell) D An EDSL expression of the type a is interpreted as a Haskell value O of the type S l m a, where m is a Monad (the parameter of the interpretation) L and l is the label for the evaluation order (one of Name, Value, or Lazy). C (S l m) is not quite a monad -- only up to the Sem interpretation `ab4Interpretation of EDSL types as host language types : The type interpretation function Sem is parameterized by m, ! which is assumed to be a Monad. cWe could have used Haskell')s type Int and the arrow -> constructor. J We would like to emphasize however that EDSL types need not be identical H to the host language types. To give the type system to EDSL, we merely  need labels# -- which is what IntT and :-> are .The (higher-order abstract) syntax of our DSL defghij?Our EDSL is typed. EDSL types are built from the following two  type constructors: kA convenient abbreviation lA sample EDSL term mn Evaluating:  # t = (lam $ \x -> let_ (x `add` x) 6 $ \y -> y `add` y) `app` int 10 The addition (x g* x) is performed twice because y is bound , to a computation, and y is evaluated twice oA better example p.We reuse most of EDSL (S Name) except for lam qrst.We reuse most of EDSL (S Name) except for lam uv$\]^_`abcdefghijklmQnRoSpqrTUVstuvWXYjicdefghklb_`a^mno]pqrs\tuv\]^_`a`abcdefghdefghijklmnopqrstuv#wEIntroducing the combinators to hide single-threaded state tve in one  case of teval'? (the A case). The other cases stay as they are, to illustrate D that our transformation is fully compatible with the earlier code. x2Type Variable Environment: associating types with free type variables yz)Type Environment: associating types with free term variables {|}~@Allocate a fresh type variable (see the first component of TVE) ;Type variables are logic variables: hypothetical reasoning shallow0 substitution; check if tv is bound to anything  substantial :The unification. If unification failed, return the reason CIf either t1 or t2 are type variables, they are definitely unbound !Unify a free variable v1 with t2 )The occurs check: if v appears free in t KThe expression abstracted from the last-but-one re-writing of the A-clause  below )Type reconstruction: abstract evaluation Cwxyz{|}~Z[\]^_`abcdefghijklmnopqrstuvwxy#|~}{zxyw#wxyyz{|~}}~$2Type Variable Environment: associating types with free type variables )Type Environment: associating types with free term variables JMerge two environment, using the given function to resolve the conflicts,  if any @Allocate a fresh type variable (see the first component of TVE) ;Type variables are logic variables: hypothetical reasoning shallow0 substitution; check if tv is bound to anything  substantial :The unification. If unification failed, return the reason CIf either t1 or t2 are type variables, they are definitely unbound !Unify a free variable v1 with t2 )The occurs check: if v appears free in t )Type reconstruction: abstract evaluation /Resolve all type variables, as far as possible Ez{|}~$$ )Type Environment: associating types with free term variables ;Type variables are logic variables: hypothetical reasoning shallow0 substitution; check if tv is bound to anything  substantial :The unification. If unification failed, return the reason CIf either t1 or t2 are type variables, they are definitely unbound !Unify a free variable v1 with t2 )The occurs check: if v appears free in t )Type reconstruction: abstract evaluation /Resolve all type variables, as far as possible ?  ,*TVE is the state of a monadic computation 2Type Variable Environment: associating types with free type variables 4Type Environment: associating *would-be* types with free term variables @Allocate a fresh type variable (see the first component of TVE) ITVE domain predicate: check to see if a TVarName is in the domain of TVE BGive the list of all type variables that are allocated in TVE but  not bound there ;Type variables are logic variables: hypothetical reasoning shallow0 substitution; check if tv is bound to anything  substantial :The unification. If unification failed, return the reason CIf either t1 or t2 are type variables, they are definitely unbound !Unify a free variable v1 with t2 )The occurs check: if v appears free in t DCompute (quite unoptimally) the characteristic function of the set  forall tvb i1n fv(tve_before). Union fv(tvsub(tve_after,tvb)) Monadic version of unify MGiven a type scheme, that is, the type t and the list of type variables tvs, A for every tvs, replace all of its occurrences in t with a fresh  type variable. A We do that by creating a substitution tve and applying it to t. DGiven a typechecking action ta yielding the type t, return the type : scheme quantifying over _truly free_ type variables in t H with respect to TVE that existed before the typechecking action began. E Let tve_before is TVE before the type checking action is executed, ; and tve_after is TVE after the action. A type variable tv C is truly free if it is free in tve_after and remains free if the C typechecking action were executed in any tve extending tve_before > with arbitrary binding to type variables free in tve_before. C To be more precise, a type variable tv is truly free with respect  to tve_before if:  tv notin domain(tve_after)  forall tvb in fv(tve_before). tv notin fv(tvsub(tve_after,tvb)) 4 In other words, tv is truly free if it is free and  independent of  tve_before. 6Our goal is to reproduce the behavior in TInfLetI.hs:  generalize/0instantiate should mimic multiple executions of A the typechecking action. That means we should quantify over all K type variables created by ta that are independent of the type environment & in which the action may be executed. BReturn the list of type variables in t (possibly with duplicates) )Type reconstruction: abstract evaluation ?Resolve all type variables, as far as possible, and generalize M We assume teval will be used for top-level expressions where generalization  is appropriate.  #non-generalizing teval (as before) d , , # *TVE is the state of a monadic computation  2Type Variable Environment: associating types with free type variables   4Type Environment: associating *would-be* types with free term variables  @Allocate a fresh type variable (see the first component of TVE) !"#$;Type variables are logic variables: hypothetical reasoning %shallow0 substitution; check if tv is bound to anything  substantial &:The unification. If unification failed, return the reason 'CIf either t1 or t2 are type variables, they are definitely unbound (!Unify a free variable v1 with t2 ))The occurs check: if v appears free in t *Monadic version of unify +)Type reconstruction: abstract evaluation ,/Resolve all type variables, as far as possible V     !"#$%&'()*+,      !"#$#     !"#$%&'()*+,#      !"#$%&'()*+,-.8A virtual typed AST: associating a type to each subterm /)Type Environment: associating types with free variables 0123456789:;<=>?@AB)Type reconstruction: abstract evaluation ,-./0123456789:;<=>?@AB%&'()*+,-./0123456789:9;:187654320/<=>.-?@AB-./01876543223456789;::;<=>?@ABC)Type Environment: associating types with free variables DEFGHIJKLMNOPQRS)Type reconstruction: abstract evaluation *CDEFGHIJKLMNOPQRS;<=>?@ABCDEFGHIJKLMNOPQRSMONELKJIHGFDCPQRSCDELKJIHGFFGHIJKLMONNOPQRS TUVWXYZ[\9We no longer need variables or the environment and we do  normalization by evaluation. Denotational semantics. Why? ]Operational semantics. Why? F GADT are still implemented imperfectly: we the default case in case C statements (with cannot happen error), to avoid the warning about E inexhaustive pattern match -- although these case-brances can never  be executed. Why? T=Since we rely on the metalanguage for typechecking and hence 6 type generalization, we have to use the metalanguage `let' F The (V n) term, aka the polymorphic lift, is not used in user terms.  This is the internal2 component for the sake of evald only (evalo doesn't  need it). 6It is quite challenging to show terms. In fact, we can't do it K for lambda-terms at all! The argument of the L constructor is a function.  We can'>t show functions; if we find a term to apply the function to, F we obtain a term, which we can show then. The only candidate for the ? term to pass to the body of L is the V term; but to construct 6 (V x) we need x -- the value of some type (and we don't have an idea G of the type). So, the best we can do is (V undefined) -- which, alas,  we can'Bt show. The only solution is to modify the definition of Term t, @ and make the V constructor thusly: V :: t -> String -> Term t. * In that case, we can show V-term values. 4TUVWXYZ[\]UVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ T[ZYXWVU\] T[ZYXWVUUVWXYZ[\] ^9We no longer need variables or the environment and we do  normalization by evaluation. Denotational semantics. Why? _`ab=Since we rely on the metalanguage for typechecking and hence % type generalization, we have to use `let' of the metalanguage. JIt is quite challenging to show terms. Yet, in contrast to the GADT-based = approach (EvalTaglessI.hs), we are able to do that, without 8 extending our language with auxiliary syntactic forms. D Incidentally, showing of terms is just another way of _evaluating_  them, to strings. cdefghij.^_`abcdefghij cdefghib`a^_j ^__`aabcdefghidefghijklmn%Environment: associating values with free variables opqrstuvwxyz9Denotational semantics. Why? How to make it operational? ,klmnopqrstuvwxyzpvutsrqonwxykmlzkmllmnopvutsrqqrstuvwxyz{Unary numerals |}~DEvaluation, substitutions and unification are parametric over terms D (term algebra), provided the following two operations are defined. G We should be able to examine a term and determine if it is a variable G or a constructor (represented by an integer) applied to a sequence of H zero or more terms. Conversely, given a constructor (represented by an J integer) and a list of terms-children we should be able to build a term. + The two operations must satisfy the laws: # either id build . classify === id  classify . build === Right FA clause is a guarded body; the latter is an AND-sequence of formulas  Formulas 7A formula describes a finite or _infinite_ AND-OR tree > that encodes the logic-program clauses that may be needed to  evaluate a particular goal. ? We represent a goal g(t1,...,tn) by a combination of the goal 8 g(X1,...,Xn), whose arguments are distinct fresh logic 3 variables, and a substitution {Xi=ti}. For a goal : g(X1,...,Xn), a |Formula| encodes all the clauses of the A logic program that could possibly prove g, in their order. Each  clause  & g(t1,...,tn) :- b1(t11,...,t1m), ... ?is represented by the (guarding) substitution {Xi=ti, Ykj=tkj} = and the sequence of the goals bk(Yk1,...,Ykm) in the body. 7 Each of these goals is again encoded as a |Formula|. O All variables in the clauses are renamed to ensure the standardization apart. Our trees are similar to Antoy'%s definitional trees, used to encode 5 rewriting rules and represent control strategies in < term-rewriting systems and _functional logic_ programming. @ However, in definitional trees, function calls can be nested,  and patterns are linear. ?The translation from Prolog is straightforward; the first step @ is to re-write clauses so that the arguments of each goal are  logic variables:  A fact   g(term). is converted to   g(X) :- X = term.  A clause  % g(term) :- g1(term1), g2(term2). is converted to  @ g(X) :- X = term, _V1 = term1, g1(_V1), _V2=term2, g2(_V2). !See the real examples at the end CA formula (parameterized by the domain of terms) is an OR-sequence  of clauses IA finite map from vars to terms (parameterized over the domain of terms) 3A logic var is represented by a pair of an integer  and a list of `predicate marks' (which are themselves 4 integers). Such an odd representation is needed to 7 ensure the standardization apart: different instances 5 of a clause must have distinctly renamed variables. 4 Unlike Claessen, we get by without the state monad 5 to generate unique variable names (labels). See the  discussion and examples in the tests section below. 6 Our main advantage is that we separate the naming of 4 variables from the evaluation strategy. Evaluation 5 no longer cares about generating fresh names, which 4 notably simplifies the analysis of the strategies. ) Logic vars are typed, albeit phantomly. =The evaluation process starts with a formula and the initial 5 substitution, which together represent a goal. The ? guarding substitution of the clause conjoins with the current I substitution to yield the substitution for the evaluation of the body. @ The conjunction of substitutions may lead to a contradiction, & in which case the clause is skipped (pruned). IEvaluation as pruning: we traverse a tree and prune away failed branches ?A different evaluator: Evaluate a tree to a stream (lazy list) # given the initial substitution s.  Here we use the SLD strategy. 4Same as above, using the SLD-interleaving strategy. 1 See Definition 3.1 of the LogicT paper (ICFP05) building substitutions Apply a substitution to a term @Conjoin two substitutions (see Defn 1 of the FLOPS 2008 paper). G We merge two substitutions and solve the resulting set of equations, H returning Nothing if the two original substitutions are contradictory. 8Solve the equations using the naive realization of the  Martelli and Montanari process <Encoding of variable names to ensure standardization apart. ? A clause such as genu(X) or add(X,Y,Z) may appear in the tree J (infinitely) many times. We must ensure that each instance uses distinct I logic variables. To this end, we name variables by a pair (Int, VStack) I whose first component is the local label of a variable within a clause. F VStack is a path from the root of the tree to the current occurrence I of the clause in the tree. Each predicate along the path is represented ? by an integer label (0 for genu, 1 for add, 2 for mul, etc).  To pass; arguments to a clause, we add to the current substitution < the bindings for the variables of that clause. See the genu' example D below: whereas (0,h) is the label of the variable X in the current 7 instance of genu, (0,genu_mark:h) is X in the callee. A logic program   genu([]).  genu([u|X]) :- genu(X). Aand the goal genu(X) are encoded as follows. The argument of genu' is ) the path of the current instance of genu' from the top of the AND-OR  tree. ?Constructor UZ is represented by 0, and US is represented by 1 ,{|}~{~}|{~}||}~ +Fand the representation of numerals in the SK calculus. The expression  (F FSum :<= Su Zero) is a partial application of the function sum to 1. $A few examples: SKK as the identity GFinally, we demonstrate that our calculus is combinatorially complete, $ by writing the S and K combinators (Finally, the standard test -- Fibonacci now we tie up the knot #and define the sum of two numerals )At the type level, this looks as follows 1We introduce the applicative fixpoint combinator EThat is all. The rest of the message are the tests. The first one is 6 the type-level equivalent of the following function:  * testb x = and (not x) (not (not x)) 2At the type level, it looks not much differently: &and the big-step evaluation function: $Commonly, abstraction is held to be `more fundamental' , which is ! reflected in the popular phrase `Lambda-the-Ultimate'. In our system, B application is fundamental. An abstraction is a not-yet-applied E application -- which is in itself a first-class value. The class A E defines the meaning of a function, and an instance of A becomes the $ definition of a function (clause). EWe have dealt with simple expressions and applicative things. We now H build sequences of applications, and define the corresponding big step 6 semantics. We introduce the syntax for applications: DThe next function is the boolean And. It takes two arguments, so we  have to handle currying now. >The meaning of |A l a b| is that the application to |a| of an - applicable thing denoted by |l| yields |b|. ISurprisingly, this already works. Let us define the boolean Not function /Indicator for functions, or applicable things: First we define some constants EWe define the instances of Show to be able to show things. We define 8 the instances in a way that the value is not required. Other particular rules  Familiar rules for applications 6Abstractions are values and so evaluate to themselves !Constants evaluate to themselves GWhen we receive the second argument, we are in the position to produce . the result. Again, we use the case analysis. DApplying And to an argument makes a closure, waiting for the second  argument. by case analysis: /##!%and obtain quite a different result:   *TypeFN> :t test_sspn4 D test_sspn4 :: ((((Bool -> Bool) -> Bool) -> Bool) -> Bool) -> Bool CIn effect, we were able to use not only (a->) but also (->a) as an A unary type function. Moreover, we achieved the latter by almost D literally applying the flip function to the arrow type constructor  (->). FUsing the type inspection tools (typecast), we can replace the family B of functions ATC1, ATC2 with one, kind-polymorphic, polyvariadic D function ATC. This approach will be explained in further messages. DWe can use the computed types to drive overloaded functions such as A read and show. The specifically instantiated read functions, in D particular, will check that a (remotely) received serialized value  matches our expectation. Let'*s consider the type of trees of the depth  of at most N. we make a very little change FThe comparison of ATC1 with ATC2 shows two different ways of defining  abstractions: as (F x) terms (`lambda-terms' in our calculus) and as A polymorphic types (Haskell type abstractions). The two ways are E profoundly related. The more verbose type application notation, via  (:<=), has its benefits. After we introduce another higher-order  function To generalize, MWe can then write the type of n-ary propositions Prop(N) in a different way, E as an N-times application of the type constructor (Bool->) to Bool. KWe introduce the combinator Ntimes: |NTimes f x n| applies f to x n times. ' This is a sort of fold over numerals. @We can compute types by applying type functions, just as we can G compute values by applying regular functions. Indeed, let us define a D StrangeProp of the kind NAT -> Type. StrangeProp(n) is the type of E propositions of arity m, where m is fib(n). We compose together the F already defined type function Prop2 and the type function Fib in the  previous message. %Our first example comes from Cardelli's paper: defining the type + Prop(n), of n-ary propositions. That is,  9 Prop(2) should be the type Bool -> Bool -> Bool A Prop(3) is the type of functions Bool -> Bool -> Bool -> Bool etc. Cardelli'$s paper (p. 10) writes this type as  "let Prop:: AllKK(N:: NatK) Type = $ recK(F:: AllKK(N:: NatK) Type) J funKK(N:: NatK) caseK N of 0K => Bool; succK(M) => Bool -> F(M);  let and2: Prop(2K) = & fun(a: Bool) fun(b: Bool) a & b; EHere 0K and 2K are type-level numerals of the kind NatK; recK is the G type-level fix-point combinator. The computed type Prop(2) then gives  the type to the term and2. .In our system, this example looks as follows: GWe can do better, with the help of higher-order type functions. First F we declare a few standard Haskell type constants as constants in our ) calculus, with trivial evaluation rules "#$ "Parameterized types: cf notation:   <string,features> in the Minimalist Grammar ;One may think of the above data declaration as defining an : isomorphism between EN values and Strings. The functions < EN and unEN (what is their type?) witness the isomorphism. ( It helps to look at their composition.    % CFG1Sem with type annotations A new notation for " (which will be convenient later)   &Type annotations     /Unfortunately, the following sentence is, too,  accepted by the type checker. 9We shall later see how to build terms that correspond to ! all and only valid derivations. , Invalid derivations will become ill-typed.             ' ,Semantic interpretation of a CFG derivation In conventional notation:  D_e = {John, Mary}     =(We can now see the examples 0The displayed difference between lsen4 and lsen4' 1 shows that beta-redices have been reduced. NBE. 7Normalizing the terms: performing the apparent redices Running the examples 9We now interpret Lambda terms as Strings, so we can show  our formulas. : Actually, not quite strings: we need a bit of _context_: J the precedence and the number of variables already bound in the context. ; The latter number lets us generate unique variable names. Syntactic sugar CThe first interpretation: evaluating in the world with John, Mary,  and Bool as truth values. B Lambda functions are interpreted as Haskell functions and Lambda 7 applications are interpreted as Haskell applications. 8 The interpreter R is metacircular (and so, efficient). :We define the grammar of the target language the same way 3 we have defined the grammar for (source) fragment  !"#$%&'(Here we encode the target language, the language ' to express denotations (or, meanings) 2 Following Montague, our language for denotations  is essentially Church's Simple Theory of Types , also known as simply-typed lambda-calculus 1 It is a form of a higher-order predicate logic. )*> !"#$%&'()*     (*) !"#$%&'  !"#$%&' !"#$%&'(*))*)+,-.Show the English form of sen1 0We now define semantics of a phrase represented 3 by a derivation. It is a different interpretation  of the phrase and its types. 1We first interpret syntactic types (NP, VP, etc) * in terms of the types of the language of  logic formulas. , The type class Lambda defines the language 0 of logic formulas (STT, or higher-order logic) * with types Entity, Bool, and the arrows. /;show the inferred types, as well as the inferred types for  the phrases like -The first sample sentence, or CFG derivation 6 The inferred type is S. So, sen1 is a derivations of  a complete sentence. =We now define the first interpretation of a CFG derivations: 8 We interpret the derivation to give the parsed string. 3 That is, we generate a yield of a CFG derivation,  in English. .We represent each node in the derivation tree  by an English phrase 012<This class defines the syntax of our fragment (the grammar, 7 essentially). Its instances will show interpretations  of the grammar, or  semantics 4The names r1, r2, etc. are the labels of CFG rules. ' These names are evocative of Montague 3456789:;<+Syntactic categories: non-terminals of CFG +,-./0123456789:;<<;:92345678/01.+,-+,-,-./010123456783456789:;<* =>(The type family TJ defines the types of 9 sentential forms corresponding to syntactic categories. 2As we shall see in QCFGJ.hs, we are going to need ! high (raised) types of our NP. 4 A verb will ask its argument to turn itself to the  desired case. ?:A verb or a verb-like word (e.g., an i-adjective) require 9 arguments of particular cases. We need a way for a verb / to specify the desired case of its arguments. @ABC.We represent each node in the derivation tree $ by a Japanese phrase or a Japanese sentential form 6 (that is, a phrase with holes). Contrast with the EN  interpreter in CFG.hs DEFG'Auxiliary functions for the code below H =>?@ABCDEFGH CDE?BA@F>=GH =>?BA@@ABCDEDEFGH+ IDWe extend our earlier fragment with common nouns farmer and donkey, A and quantifiers everyone, someone, every farmer, a donkey, etc. F Since we added two new categories (CN and QNP), we need to add rules = to our CFG to be able to use the categories in derivations. (The numbers 4 and 5 are due to Montague JKLMNOPQRST Additional syntactic categories !'Sample sentences (or, CFG derivations) / We stress that the inferred type of sen2-sen4 ( is S. So, these are the derivations of  complete sentences. -We extend our EN interpreter (interpreter of ) derivations as English phrases) to deal  with QNP. IJKLMNOPQRST"#$%&'()*+,-./ TSIJKLMNOPQR I JKLMNOPQRJKLMNOPQRST,UVWXYZ[\]^_`abc=We extend the Lambda language with state (of the type State) 0=We correspondingly extend our R, C, P intrepreters of Lambda UVWXYZ[\]^_`abc1234c`ab_\]^YZ[WXUVUVVWXXYZ[Z[\]^]^_`ababc>5/The expression for quantifiers ensures that no 3 inverse reading is possible. Only linear reading. 6789-d3No longer any need in a new syntactic category QNP  We leave out CN as an exercise  = data CN -- Common noun CWe extend our earlier fragment with quantifiers everyone, someone. C In contrast to QCFG.hs, we do not add any new syntactic category,  so we don'$t need to add any rules to our CFG. ef:*We can now see the English sentences that * correspond to the derivations sen2-sen4. *We also extend the semantics interpreter: ( the interpreter of a derivation into a % formula of STT, or Lambda-calculus.  We reconstruct Montague's `` pronoun trick'' ;(Sample sentences (or, CFG derivations):  compare with those in QCFG.hs / We stress that the inferred type of sen2-sen4 ( is S. So, these are the derivations of  complete sentences. -We extend our EN interpreter (interpreter of ) derivations as English phrases) to deal  with quantifiers. def<=>?@ABCDEFGdefdefef.gBWe extend our earlier fragment with quantifiers everyone, someone A We also add a combinator for raising the first argument of a TV hijk(The translation is certainly different: like corresponds  to an adjective in Japanese. Adding quantification; one way lm%We can now see the semantics of sen1  Computing the yield in Japanese (The type family TJ defines the types of 9 sentential forms corresponding to syntactic categories. .We represent each node in the derivation tree $ by a Japanese phrase or a Japanese sentential form 6 (that is, a phrase with holes). Contrast with the EN  interpreter above. nopqrsShow the English form of sen1 0We now define semantics of a phrase represented 3 by a derivation. It is a different interpretation  of the phrase and its types. 6We first interpret syntactic types (NP, slashes, etc) * in terms of the types of the language of  logic formulas. , The type class Lambda defines the language 0 of logic formulas (STT, or higher-order logic) * with types Entity, Bool, and the arrows. t;show the inferred types, as well as the inferred types for  phrases like -The first sample sentence, or CCG derivation 6 The inferred type is S. So, sen1 is a derivations of  a complete sentence. =We now define the first interpretation of a CCG derivations: 8 We interpret the derivation to give the parsed string. 3 That is, we generate a yield of a CCG derivation,  in English. .We represent each node in the derivation tree  by an English phrase uvw<This class defines the syntax of our fragment (the grammar, 7 essentially). Its instances will show interpretations  of the grammar, or  semantics xyz{|}~+Syntactic categories: non-terminals of CCG H(Japanese is challenging: like semantics /The expression for quantifiers ensures that no 3 inverse reading is possible. Only linear reading. I3But how to put a quantifier in an object position? J3The following works but is unsatisfactory: we wish 2 slashes to be interpreted only as concatenation! .ghijklmnopqrstuvwxyz{|}~KLMNOPQRSTUVWXYZ[\]^~}wxyz{|tuvspqrmnolkghijghijhijklmnonopqrqrstuvuvwxyz{|xyz{|}~/- Enumerators ; Each enumerator takes an iteratee and returns an iteratee + an Enumerator is an iteratee transformer. = The enumerator normally stops when the stream is terminated F or when the iteratee moves to the done state, whichever comes first. 3 When to stop is of course up to the enumerator... AWe have two choices of composition: compose iteratees or compose 5 enumerators. The latter is useful when one iteratee 3 reads from the concatenation of two data sources. @Combining the primitive iteratees to solve the running problem: : Reading headers and the content from an HTTP-like stream )Iteratee converters for stream embedding A The converters show a different way of composing two iteratees:  vertical rather than  horizontal AThe type of the converter from the stream with elements el_outer A to the stream with element el_inner. The result is the iteratee $ for the outer stream that uses an `IterateeG el_inner m a' E to process the embedded, inner stream as it reads the outer stream. BIteratee -- a generic stream processor, what is being folded over  a stream  When Iteratee is in the done! state, it contains the computed . result and the remaining part of the stream.  In the cont6 state, the iteratee has not finished the computation  and needs more input. " We assume that all iteratees are good -- given bounded input, G they do the bounded amount of computation and take the bounded amount C of resources. The monad m describes the sort of computations done B by the iteratee as it processes the stream. The monad m could be < the identity monad (for pure computations) or the IO monad B (to let the iteratee store the stream processing results as they  are computed). < We also assume that given a terminated stream, an iteratee L moves to the done state, so the results computed so far could be returned. IWe could have used existentials instead, by doing the closure conversion <A particular instance of StreamG: the stream of characters. , This stream is used by many input parsers. CA stream is a (continuing) sequence of elements bundled in Chunks. < The first two variants indicate termination of the stream.  Chunk [a]3 gives the currently available part of the stream. # The stream is not terminated yet.  The case (Chunk []1) signifies a stream with no currently available @ data but which is still continuing. A stream processor should,  informally speaking, ``suspend itself'' and wait for more data  to arrive. B Later on, we can add another variant: IE_block (Ptr CChar) CSize * so we could parse right from the buffer. >Useful combinators for implementing iteratees and enumerators :Just like bind (at run-time, this is indeed exactly bind) =Just like an application -- a call-by-value-like application The following is a variant' of join in the IterateeGM el m monad.  When el'8 is the same as el, the type of joinI is indeed that of > true monadic join. However, joinI is subtly different: since  generally el', is different from el, it makes no sense to * continue using the internal, IterateeG el' m a: we no longer  have elements of the type el' to feed to that iteratee. E We thus send EOF to the internal Iteratee and propagate its result. 0 This join function is useful when dealing with `derived iteratees'  for embedded/2nested streams. In particular, joinI is useful to @ process the result of stake, map_stream, or conv_stream below. BRead a stream to the end and return all of its elements as a list 'Check to see if the stream is in error The analogue of List.break 3 It takes an element predicate and returns a pair:  (str, Just c) -- the element c$ is the first element of the stream 3 satisfying the break predicate; ? The list str is the prefix of the stream up $ to but including c E (str,Nothing) -- The stream is terminated with EOF or error before I any element satisfying the break predicate was found. : str is the scanned part of the stream. 9 None of the element in str satisfy the break predicate. JA particular optimized case of the above: skip all elements of the stream ; satisfying the given predicate -- until the first element @ that does not satisfy the predicate, or the end of the stream. ( This is the analogue of List.dropWhile /Attempt to read the next element of the stream @ Return (Just c) if successful, return Nothing if the stream is ! terminated (by EOF or an error) ?Look ahead at the next element of the stream, without removing  it from the stream. @ Return (Just c) if successful, return Nothing if the stream is ! terminated (by EOF or an error) Skip the rest of the stream 6Skip n elements of the stream, if there are that many # This is the analogue of List.drop BRead n elements from a stream and apply the given iteratee to the H stream of the read elements. Unless the stream is terminated early, we D read exactly n elements (even if the iteratee has accepted fewer). 1Map the stream: yet another iteratee transformer D Given the stream of elements of the type el and the function el->el', 1 build a nested stream of elements of the type el' and apply the  given iteratee to it.  Note the contravariance 4Convert one stream into another, not necessarily in lockstep A The transformer map_stream maps one element of the outer stream D to one element of the nested stream. The transformer below is more F general: it may take several elements of the outer stream to produce ; one element of the inner stream, or the other way around. A The transformation from one stream to the other is specified as  IterateeGM el m (Maybe [el']). The _ type reflects the & possibility of the conversion error. &Read the line of text from the stream / The line can be terminated by CR, LF or CRLF. A Return (Right Line) if successful. Return (Left Line) if EOF or @ a stream error were encountered before the terminator is seen. . The returned line is the string read so far. BThe code is the same as that of pure Iteratee, only the signature  has changed. 3 Compare the code below with GHCBufferIO.line_lazy HLine iteratees: processors of a stream whose elements are made of Lines 1Collect all read lines and return them as a list  see stream2list 4Print lines as they are received. This is the first impure iteratee 2 with non-trivial actions during chunk processing =Convert the stream of characters to the stream of lines, and 3 apply the given iteratee to enumerate the latter. ? The stream of lines is normally terminated by the empty line. B When the stream of characters is terminated, the stream of lines ! is also terminated, abnormally. I This is the first proper iteratee-enumerator: it is the iteratee of the 9 character stream and the enumerator of the line stream. I More generally, we could have used conv_stream to implement enum_lines. =Convert the stream of characters to the stream of words, and 3 apply the given iteratee to enumerate the latter. % Words are delimited by white space. $ This is the analogue of List.words > It is instructive to compare the code below with the code of  List.words, which is:  .words :: String -> [String] 7words s = case dropWhile isSpace s of ) "" -> [] 4 s' -> w : words s'' 7 where (w, s'') = = break isSpace s' COne should keep in mind that enum_words is a more general, monadic  function. I More generally, we could have used conv_stream to implement enum_words. FThe most primitive enumerator: applies the iteratee to the terminated ? stream. The result is the iteratee usually in the done state. .Another primitive enumerator: report an error KThe composition of two enumerators: essentially the functional composition H It is convenient to flip the order of the arguments of the composition + though: in e1 >. e2, e1 is executed first The pure 1-chunk enumerator A It passes a given list of elements to the iteratee in one chunk F This enumerator does no IO and is useful for testing of base parsing The pure n-chunk enumerator @ It passes a given lift of elements to the iteratee in n chunks F This enumerator does no IO and is useful for testing of base parsing " and handling of chunk boundaries The enumerator of a POSIX Fd 0 Unlike fdRead (which allocates a new buffer on 9 each invocation), we use the same buffer all throughout HTTP chunk decoding & Each chunk has the following format:  * <chunk-size> CRLF <chunk-data> CRLF where  chunk-size is the hexadecimal number;  chunk-data is a  sequence of  chunk-size bytes. 5 The last chunk (so-called EOF chunk) has the format O 0 CRLF CRLF (where 0 is an ASCII zero, a character with the decimal code 48).  For more detail, see Chunked Transfer Coding, Sec 3.6.1 of  the HTTP/1.1 standard:   >http://www.w3.org/Protocols/rfc2616/rfc2616-sec3.html#sec3.6.1 EThe following enum_chunk_decoded has the signature of the enumerator D of the nested (encapsulated and chunk-encoded) stream. It receives B an iteratee for the embedded stream and returns the iteratee for A the base, embedding stream. Thus what is an enumerator and what 0 is an iteratee may be a matter of perspective. MWe have a decision to make: Suppose an iteratee has finished (either because H it obtained all needed data or encountered an error that makes further ? processing meaningless). While skipping the rest of the stream/ the trailer, G we encountered a framing error (e.g., missing CRLF after chunk data). : What do we do? We chose to disregard the latter problem. B Rationale: when the iteratee has finished, we are in the process 2 of skipping up to the EOF (draining the source). ( Disregarding the errors seems OK then. I Also, the iteratee may have found an error and decided to abort further E processing. Flushing the remainder of the input is reasonable then. $ One can make a different choice... `BIt turns out, IterateeGM form a monad. We can use the familiar do " notation for composing Iteratees Dabcdefghijklmnopqrstuvwx,,09Generally, RBState is opaque and should not be exported. AThe type of the IO monad supporting seek requests and endianness 4 The seek_request is not-quite a state, more like a `communication channel' ? set by the iteratee and answered by the enumerator. Since the A base monad is IO, it seems simpler to implement both endianness J and seek requests as IORef cells. Their names are grouped in a structure % RBState, which is propagated as the `environment.' :The programmer should use the following functions instead HTo request seeking, the iteratee sets seek_req to (Just desired_offset) @ When the enumerator answers the request, it sets seek_req back  to Nothing A useful combinator. 1 Perhaps a better idea would have been to define ? Iteratee to have (Maybe a) in IE_done? In that case, we could 1 make IterateeGM to be the instance of MonadPlus &We discard all available input first. F We keep discarding the stream s until we determine that our request  has been answered: = rb_seek_set sets the state seek_req to (Just off). When the 6 request is answered, the state goes back to Nothing. ; The above features remind one of delimited continuations. 1An iteratee that reports and propagates an error 8 We disregard the input first and then propagate error.  It is reminiscent of abort BRead n elements from a stream and apply the given iteratee to the C stream of the read elements. If the given iteratee accepted fewer  elements, we stop.  This is the variation of  with the early termination K of processing of the outer stream once the processing of the inner stream E finished early. This variation is particularly useful for randomIO, ! where we do not have to care to `drain the input stream'. JIteratees to read unsigned integers written in Big- or Little-endian ways :The enumerator of a POSIX Fd: a variation of enum_fd that # supports RandomIO (seek requests) yz{|}~1\Standard TIFF tags Standard TIFF data types    =A TIFF directory is a finite map associating a TIFF tag with  a record TIFFDE  BAnother sample processor of the pixel matrix: verifying values of  some pixels A This processor does not read the whole matrix; it stops as soon 4 as everything is verified or the error is detected TIFF library code =We need a more general enumerator type: enumerator that maps 1 streams (not necessarily in lock-step). This is  a flattened ( `joinI-ed') EnumeratorN elfrom elto m a  Sample TIFF user code K The following is sample code using the TIFF library (whose implementation & is in the second part of this file). > Our sample code prints interesting information from the TIFF A dictionary (such as the dimensions, the resolution and the name  of the image) )The sample file is a GNU logo (from http: www.gnu.org) . converted from JPG to TIFF. Copyleft by GNU. =The main user function. tiff_reader is the library function, # which builds the TIFF dictionary. ; process_tiff is the user function, to extract useful data  from the dictionary  Sample TIFF processing function ?sample processing of the pixel matrix: computing the histogram 1The library function to read the TIFF dictionary A few conversion procedures HAn internal function to load the dictionary. It assumes that the stream & is positioned to read the dictionary Reading the pixel matrix ; For simplicity, we assume no compression and 8-bit pixels 4A few helpers for getting data from TIFF dictionary b     \     \3        2,We can now run (interpret) our sample terms Eterm2 denoted the action of negating the current state and returning  the original state >Now, we show that our term representation of the state monad  is an instance of MonadState >Interpretation of the Bind action requires an auxiliary class E This is due to the polymorphism of the monadic bind, which has the  type   m a -> (a -> m b) -> m b Note the polymorphism both in a" (value type of the input monadic  action) and b& (value type of the resulting action)  examples of terms !An example of an ill-formed term  An example of an ill-typed term C The following term is ill-typed because it attempts to store both K a boolean and a character in the state. Our state can have only one type. #The interpreter of monadic actions  It takes the term t# and the initial state of the type s ? and returns the final state and the resulting value. The type  of the result, a3, is uniquely determined by the term and the state !"#$%&'(CMonadic actions are terms composed from the following constructors )*=We can write computations expressed by term1 and term2 using  the normal monadic syntax DThe following identity function is to resolve polymorphism, to tell F that monadic terms below should use our representation of MonadState  !"#$%&'()*()&'$%"# !* !!"##$%%&''())*34+,-./0123456789:;<=>?@AB9The main test: approximate equality. See the article for  the description. CAA generic function that tests if its argument is a member of Eqs DEFGHIJK$The guard that always succeeds (cf.  in Haskell) L3A type class for instance guards and back-tracking 9 Here, pred and f are labels and n is of a kind numeral. M1we avoid defining a new class like MemApp above.  I guess, after Apply, we don't need a single class ever? NO5Deciding the membership in a closed class, specified & by enumeration, union and difference P=Classifies if the type x belongs to the open class labeled l ( The result r is either HTrue or HFalse QRSTU;Why we call Nums etc. a type class rather than a type set? / The following does not work: type synonyms can't be recursive.  + type Russel = AllOfBut () Russel :*: HNil ?But the more elaborate version does, with the expected result: VAThe Fractionals, Nums and Ords above are closed. But Eqs is open + (i.e., extensible), due to the following: WXYZ0The classes of types used in the examples below 5Augment the above function, to test for pairs of Eqs G We could have added an instance to TypeCls OpenEqs above. But we wish E to show off the recursive invocation of a second-order polymorphic  function the default instance <Each case of a 2-poly function is defined by two instances,  of GFN and or Apply classes. (the default instance: x does not belong ;+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ0ZYXWVUTSRQPONMLKIJGHEFCDB@A>?<=:;9867452301./-+,0+,,-.//01123345567789:;;<==>??@AABCDDEFFGHHIJJKLMNOPQRSTUVWXYZ4C[\]^_Now we need a storage admin 8 It is treated as an expression in the source language! `abcdenew expressions fg@a better idea is Loc -> Maybe Value, so that when lookup fails, @ we can re-throw that Deref or Set message. That would make the  storage extensible... ; The first component of the pair is the allocation counter hijk&Extension: State: see Fig. 5 of EDLS lmnopq2Extension: Arithmetic: see a part Fig. 4 of EDLS rstuvwxyz{|The meaning of a program AExtension: Call-by-Value: see a part Fig. 4 of EDLS (or, Fig. 8) )We add closures (procedures) to the Base }~<The base language has only two expressions: omega and error  See Fig. 3 (p. 7) of EDLS *Note that inV is essentially the identity partial continuation  The error  action and its tag !The universal handler of actions + It propagates the action request InFX up. A Since we do case-analysis on the first argument, v, the handler A is strict in that argument. That is, handler bottom ==> bottom,  as required by Fig. 3 of EDLS. 4 The last clause is essentially the denotation of a `control channel' &Expressions and their interpretations E This is an open data type and an open function. Haskell typeclasses  are ideal for that. This is the function curlyM of EDLS Auxiliary functions  Computations: just like in EDLS ? The strictness of inV guarantees that inV bottom = bottom, as  on Fig. 3 of EDLS + Error is always a part of the computation The universal domain B Yes, it is untyped... But Denot semantics is like this anyway... / Bottom is the implicit member of this domain. +Create a few variables for use in examples #Denotations of the new actions (injproj tofrom the Universal Domain)  inject and project computations #Denotations of the new actions (injproj tofrom the Universal Domain) Test of the extension < Instantiate this extension on the top of the CBV evaluator m[\]^_`abcdefghijklmnopqrstuvwxyz{|}~A}~|yz{xvwtuqrsopmnklhijgefcdab_`]^[\A[\\]^^_``abbcddeffghijijkllmnnoppqrsrstuuvwwxyz{z{|}~~5BAnother example, to illustrate locking and static reasoning about  the locking state #First, use the regular Monad.State Now, wrap in MW "Introduce the variable-type state 0Inject regular monads to be monadish things too A parameterized monad +Try polymorphic recursion, over the state. > crec1 invokes itself, and changes the type of the state from  some si to Bool. 6some syntactic sugar 9The continuation monad parameterized by two answer types < We represent the the effectful expression e, whose type is  characterized by the judgement   Gamma; a |- e:tau; b Gas a parameterized monad C a b tau. We represent an effectful function  type sigmaa -> tau$b of the calculus as an arrow type  sigma -> C a b tau.  Incidentally, this notational  convention expresses the rule fun in AK07 0Inject regular monads to be monadish things too <Parameterized monad. This is almost the same monad used in  the Region-IO and TFP07 paper  See also  ? Robert Atkey, Parameterised Notions of Computation, Msfp2006 9 http://homepages.inf.ed.ac.uk/ratkey/param-notions.pdf and E http://www.haskell.org/pipermail/haskell/2006-December/018917.html ,The rules from AK07 as they are (see Fig 3) shift. *The append example from AK07, section 2.1 "The sprintf test: Sec 2.3 of AK07 J The paper argues this test requires both the changing of the answer type : and polymorphism (fmt is used polymorphically in stest3) =Fortunately, the rule app in AK07 (Fig 3) is expressible as  the composition of two binds 7%The implementation is quite trivial. AThe following instances presume that an exception that occurs in  m6 discard the state accumulated since the beginning of m s execution.  If that is not desired -- don't use StateT. Rather, allocate F IORef and carry that _immutable_ value in a ReaderT. The accumulated ; state will thus persist. One can always use IORefs within  any MonadIO. &The following is almost verbatim from Control.Monad.Error  Section 1MonadError instances for other monad transformers 8)Simpler illustrations of impredicativity 91We are defining a super-set of monads, so called `restricted monads'. D Restricted monads include all ordinary monads; in addition, we can  define a SET monad. See   <http://okmij.org/ftp/Haskell/types.html#restricted-datatypes FFinally, we demonstrate overloading of non-functional values, such as & minBound and maxBound. These are not methods in the classical sense. IWe can define generic function at will, using already defined overloaded  functions. For example, DWe now illustrate overloading over datatypes other than basic ones. ( We define dual numbers (see Wikipedia) GExample 1: Building overloaded numeric functions, the analogue of Num. 4 The following defines overloaded numeric functions ` a la carte'. We @ shall see how to bundle such methods into what Haskell98 calls classes 0The one and only type class present in Haskell1 @We can now define the generic addition. We use the operation +$ ) to avoid the confusion with Prelude.(+) DIn H98, the overloaded addition was a method. In Haskell1, it is an ) ordinary (bounded polymorphic) function # The signature looks a bit ugly; we' ll see how to simplify it a bit DHere is a different, perhaps simpler, way of defining signatures of F overloaded functions. The constraint C is inferred and no longer has  to be mentioned explicitly Land the corresponding overloaded function (which in Haskell98 was a method) G Again, we chose a slightly different name to avoid the confusion with  the Prelude :An example of using monads and other overloaded functions fromInteger conversion ? This numeric operation is different from the previous in that C the overloading is resolved on the result type only. The function   is another example of such a producer DThe following test uses the previously defined +$ operation, which ( now accounts for duals automatically. ; As in Haskell98, our overloaded functions are extensible. .Likewise define the overloaded multiplication DWe define the addition of Duals inductively, with the addition over  base types as the base case. K We could have eliminated the mentioning (a->a->a) and replaced with some F type t. But then we would need the undecidable instance extension... Let'!s define the addition for floats   :#7Some functional dependencies: implementing Monad Error G As it turns out, some functional dependencies are expressible already 9 in Haskell1. The example is MonadError, which in Haskell' has the form   ,          #  #  ; Because DList contains the pointer to the current element, DList  is also a Zipper   )Representation of the double-linked list Operations on the DList a =In a well-formed list, dl_current must point to a valid node / All operations below preserve well-formedness auxiliary function /The insert operation below makes a cyclic list  The other operations don't care 4 Insert to the right of the current element, if any : Return the DL where the inserted node is the current one 1Delete the current element from a non-empty list 0 We can handle both cyclic and terminated lists * The right node becomes the current node. B If the right node does not exists, the left node becomes current If no right, just stay inplace  If no left, just stay inplace !"8The following does not anticipate cycles (deliberately) #Reverse taking: we move left $Update the current node inplace %@This one watches for a cycle and terminates when it detects one A    !"#$%                   ! " # $ % & ' ( ) * + , - . / 0    !"#$%      !"#$% 1?@A?@A?BC?BD?BE?BF?BGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdeefghhiijjklmnopqrstuvwwjjxyz{|}q~rstu                                    f  m                                       fmxxm     fm  !"?#$$%&&'(()**+,-m ./01"2345m     3456m 78   9::;<=>?@ABCDEFGHIJKLMNOPQRSTUVW::;<=>?@ABCDEFGHIXYZJKLMNOPQRS[VW::;<=>?@ABCDEFGHIJKLMNOPQRSVW9::;<\=>?@AB]]CDEFGHIJKLM^_NOPQRS`abcdVWe9::;<\=>?@ABCDEFGHIJKLMNOPQRSaVWfg;<=>?@ABEFGHIhijW;<=>?@ABEFGHIW<=>?@ABklmmnopqrsk4tuv<>?@ABGHIwxyz{|}~wP                       @ x           !!!!!!!!!!!!!!!""""6"6""""""""""""D"""####6#6###D#########$$$$D$$$$$$$$$%%%%%%%%%&&&&&&&'''(((((((((((f(((((((((((((((()6)6)))))))))))))D)))************+++++++p+++++,,,,,,,,m,m,,,,,,---..........6.6.............../////////// / / / / /////////////////// /!/"/#/$/%/&/'/(/)/*0+0+0,0-0.0.0/000102030405060708090:0;1<1=1>1?1@1A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P1Q1R1S1T1U1V1W1X1Y1Z1[1\1]1^1_1`1a1b1c1d1e1f1g1h1i1j1k1l1m1n1o1p1q1r1s1t1u1v1w1x1y1z1{1|1}1~111111111111111111111111122222222222222233333333333333333333333333333333333333333333333344444444444444444444444444444444444444444v4B4B444444444444u444444444445555555555555555555555566666666666j66m677 7 7 7 8 8 8 8888888888889999999999999 9!9"9#9$99:::::::%:%:&:':':(:):*:+:,:-:.:/: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;;TUVWHXYZ[\]]J^_`abcdefghijklmnopqrstuvwxyz{|}~`abguvtplmnxyz{|}~                       <<     w                                         w    w  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEF  aGHIJKLMNOPQRSTUVWXYZ[\]^_`abcGHIJKLMNOPQRSTUdeVWXYZ[\]^_`abcGHIJKLMNOPQRSTUVWXYZ[\]^_`abcGHIJKLMNOPQRSTUVWXYZ[\]^fghijklmnopqrstuvwxyz{|}~`abcGHIJKLMNOPQRSTUVWXYZ[\]^fghjklmrstuvwxyz{|}~`abcHJMNOPVWXYZ\]^HJMNOPSTVWXYZ\]^_HKLMVZfhmrstuwyz{|}~`abcHKLMVZfhmrstyz{|}`abcHOQSTVWZJPR                    !!!!!!!!!!"""'''''''======((((((((((((((((((((((((((((((((((())))*+++++++++++++ + + , ,,,, >>>>>--------------................... ....?///// /!////////"/#/$/%/&////'/(/W/0)0J00P0R0*0+0,0-0.1/10111213142H225262728292:2;2<?=>3?3@3A3B3W33C3J33D3E3F3G3P3R4H4I4J4K4L4M4N4O4P4Q4R4S4J4T4U44V4W4X4Y4Z4[4\4]4^4_4`4a4b4P4444c4d4e4f4g4444h4i4j4k4l5J55P5R55m5n5o6p6q6r6s6t6J6p6u6q6r6v6w6x6y7z7{7|7}7J78~8J888899?9999999999y99:::::::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;f;;;g;;;;h;;liboleg-2010.1.7.1System.LowLevelIOSystem.SafeHandlesSystem.SysOpenText.GenPrintFText.PrintScanFText.TotalPrintF Text.TFTestText.PrintScanLogic.DynEpistemology Language.TypLanguage.TTFdBLanguage.TypeCheckLanguage.Symantics1Language.LinearLC Language.CB98 Language.TTF Language.TDPE Language.CPSLanguage.CBAny Language.CBLanguage.TEval.TInfTMLanguage.TEval.TInfTEnvLanguage.TEval.TInfTLanguage.TEval.TInfLetPLanguage.TEval.TInfLetILanguage.TEval.TEvalNRLanguage.TEval.TEvalNCLanguage.TEval.EvalTaglessILanguage.TEval.EvalTaglessFLanguage.TEval.EvalNLanguage.DefinitionTreeLanguage.TypeLCLanguage.TypeFN Lambda.CFG4Lambda.CFG3Sem Lambda.CFG3ENLambda.CFG2Sem Lambda.CFG2ENLambda.CFG1SemLambda.Semantics Lambda.CFG Lambda.CFGJ Lambda.QCFGLambda.Dynamics Lambda.QHCFG Lambda.CCGSystem.IterateeMSystem.RandomIOCodec.Image.TiffControl.StateAlgebra Control.Poly2Control.ExtensibleDSControl.VarStateMControl.ShiftResetGenuineControl.CaughtMonadIO Data.Numerals Data.Class1 Data.Class2 Data.FDListLanguage.ToTDPE Lambda.CFG1EN Lambda.QCFGJbaseForeign.C.ErrorErrno GHC.IO.IOModeReadMode WriteMode AppendMode ReadWriteModeIOModeSHandleSIOIORTliftSIOnewRgnrunSIO newSHandle shGetLine shPutStrLnshIsEOFshDupshThrowshCatchshReport sNewIORef sReadIORef sWriteIORefmyfdReadmyfdSeekselect'read'pending mysysOpenFd mysysCloseFd mysysCloseOut read_lineFDescFD_strFD_litSPrintFpr_auxRStringunRconvert_to_fdescFScFPr PrinterParserFormattingSpeclitintcharfpp^fmtsprintfsscanfshowreadprefixspecFPrIOF:^FPPFChrFIntFLitintpintsP2WorldP1Worldp1_annep1_billp1worldsprob1prob1aprob1a'p2_anne p2_anne_keysp2_bill p2_bill_keysp2_cath p2_cath_keysp2worldsprob2choosenatiota nonuniqueuniqueIdDynamicSafeCastAsArrowAsIntF2unF2F1unF1FSunFSEQUequ_castTCOPYTypShowAsTQunTQShowTTSYMtinttarrview_tshow_asrefltransymmeq_arras_intas_arrow safe_gcastSunSR SymanticsaddzslamappviewCLunCLVarfindvarVarDescVarNameDynTermTreeNodeLeafread_t asTypeRepr typecheckSemMSemEnvpunipexi quant_orderpcnt QuantOrder Exi_over_Uni Uni_over_ExiVarnameTForallExistsImplyAndLoveSeeWomanManEIndLStringAbstractjohnbillmanwomanseeloveeverysomedotISMNPNccatunSemrunSemgenvarshiftPGZgzGenLglamGHiHohihoLinearL LSymanticsUUsedSLazySLunSLSValueSVunSVSNameSNunSNEDSLsubArrlet_trunNamet1t2vnnvrunValuesharelnnlrunLazyFixSYMfixBoolSYMboolleqif_MulSYMmul VarCounterRRreifyreflect-->CPS1cps1rCPScpsrLgunLgExtSymunExtSymGenArr ESymanticslegacycpskappkcpsvcps1vLazyValueNameSem:->IntTTVEMTVETEnvTermFixIFZ:+ALVTVarNameTV:>TIntenv0lkupextnewtvtve0tvlkuptvexttvsubtvchaseunifyunify'unifyvoccurs>>=returnteval'tevalunextenv_mapenv_fold_merge merge_envLetTypS tvdomainptvfreetvdependentsetunifyM instantiate generalizefreevarstevalngTyps TermIndextoptermtoptypshiftevaldevaloDVarCountlai+:ifzVCVIEnvevalUNUSUZUNv UnifiableclassifybuildBody:*:FactClauseFormula:+:FailSubstLogicVarVStackpruneprunecevalibvinssappsolvegenuNatfromNatCombTwoCombSuCombZTest_skkCombSCombKFibFib'N3N2N1N0FSumFSum'RecTestb:<FAndFNotSuZeroHFalseHTruetest_sumtest_fib test_ctwoTreeDNSSPropN'FlipSPropN'ATC2PropN'ATC1Ntimes StrangePropProp2PropProp'oddand4tEntityMaryJohnTrENunENmaryliker2r1VPsentence bad_sentencePunPknownKnownCunCLambdajohn'mary'like'own'farmer'donkey'truenegconjexistsownTJSKCaseAcc NomStrongNomJAunJA case_particlemake_npmake_tv Quantifierfarmerdonkeyeveryonesomeonewhor5r4QNPCNPronounit_Dynamicsit' PredicatedynamicstaticunDStatesupdateselectStatelift_vt/\\:\\:/ EnumeratorM EnumeratorGMLine EnumeratorN IterateeMIteratee IterateeGMIMunIM IterateeGIE_contIE_doneStreamStreamGChunkErrEOFliftI>>====<<joinI stream2listiter_report_errsbreak sdropWhilesnextspeek skip_till_eofsdropstake map_stream conv_streamline print_lines enum_lines enum_wordsenum_eofenum_err>.enum_pure_1chunkenum_pure_nchunkenum_fd enum_fileenum_chunk_decodedRBState msb_firstseek_reqRBIOunRBIO rb_seek_setrb_seek_answered rb_msb_firstrb_msb_first_setrunRBbindmsseekiter_errstakeR endian_read2 endian_read4enum_fd_randomTIFF_TAG TG_MATTEINGTG_CONSECUTIVEBADFAXLINESTG_CLEANFAXDATATG_BADFAXLINES TG_COLORMAPTG_PRIMARYCHROMATICITIES TG_WHITEPOINT TG_PREDICTORTG_HOSTCOMPUTER TG_ARTIST TG_DATETIME TG_SOFTWARETG_COLORRESPONSECURVETG_COLORRESPONSEUNIT TG_PAGENUMBERTG_RESOLUTIONUNITTG_GROUP4OPTIONSTG_GROUP3OPTIONSTG_GRAYRESPONSECURVETG_GRAYRESPONSEUNITTG_FREEBYTECOUNTSTG_FREEOFFSETS TG_YPOSITION TG_XPOSITION TG_PAGENAMETG_PLANARCONFIGTG_YRESOLUTIONTG_XRESOLUTIONTG_MAXSAMPLEVALUETG_MINSAMPLEVALUETG_STRIPBYTECOUNTSTG_ROWSPERSTRIPTG_SAMPLESPERPIXELTG_ORIENTATIONTG_STRIPOFFSETSTG_MODELTG_MAKETG_IMAGEDESCRIPTIONTG_DOCUMENTNAME TG_FILLORDER TG_CELLLENGTH TG_CELLWIDTHTG_THRESHOLDINGTG_PHOTOMETRICTG_COMPRESSIONTG_BITSPERSAMPLETG_IMAGELENGTH TG_IMAGEWIDTHTG_OSUBFILETYPETG_SUBFILETYPETG_other TIFF_TYPE TT_doubleTT_float TT_srationalTT_slong TT_sshort TT_undefinedTT_sbyte TT_rationalTT_longTT_shortTT_asciiTT_byteTT_NONE TIFFDE_ENUMTEN_RATTEN_INTTEN_BYTETEN_CHARTIFFDE tiffde_count tiffde_enumTIFFDict EnumeratorGMM compute_hist tag_to_int int_to_tag tiff_reader u32_to_float u32_to_s32 u16_to_s16u8_to_s8note load_dictpixel_matrix_enum dict_read_intdict_read_ints dict_read_ratdict_read_stringStatteRunBindrunbindRunStaterunstPutGetReturnBind as_statteApplyapplyTypeEq TypeCast'' typeCast'' TypeCast' typeCast'TypeCasttypeCastZHNil ApproxEq'ApproxEqPairOfIsAnEqGFnTestGFnAGFn OtherwiseGFNMemCase2MemAppMemberTypeClsTypeClAllOfButAllOfRusselRusselCOpenEqsEqsOrdsNums Fractionals ControlAdminControlStoAdminSetDerefRefStoPLinLprLLocAdd1IntCPNinNprNApp:@LamPVinPprPProcBE_omegaBE_err Interpretor interpretCompInFXInVActionTagVTVFVSvxvyvrvfinCompprCompinStoprStoinit_sto inControl prControlLIOunLIOUnlockedLockedVSTrunVSTMWunMWMonadishgretgbindvsgetvsputcrec1lputlgetlockunlockretbindresetrunstr CaughtMonadIOgcatch MyExceptioncatchDynWunWzerosucconeexpexp2f1foof2BINDRETMinBoundSHOWDual FromIntegerMulAddac+$mul_sigmul_as frmIntegershwmnBoundPACKCLSNUMnm_addnm_mulnm_fromIntegernm_showIndexFromListFC3FC2FC1 CatchError ThrowErrorERRORstrMsg throwError catchErrorfc1fc2fc3fromListindexA+$$*$$nshwnfromIDList dl_counter dl_currentdl_memnode_val node_left node_rightempty well_formedis_empty get_curr_node insert_rightdeleteget_curr move_right move_right' move_left move_left'takeDL takeDLrevtoList TypeCast2'' TypeCast2' TypeCast2RMonadIObracesnaglIO MonadRaiseHandleRunIORTclose_hrnew_hreq_hrcatch'bracket' sanitizeExc$fMonadRaisemmfcntlc_selectcLSeekstrerrorcReadTIMEVALFDSETfd2fdsfds2mfdunFd c_shutdown c_mysysClose c_mysysOpen$fSPrintFRStringprintft3t4test_cvftp1ts1tp2ts2fmt3tp3ts3tp4ts4fmt50fmt5tp5ts5FD_anyFD_intanys fdesc_to_codet1st31t4st5spec71spec72t7t3ioandthen isNothing$fTSYMTQtt1tt2tt1_viewtt2_viewtt0_showtt1_showtdn1tdn2tdn3tdn_show tdn_eval1 tdn_eval2 tdn1_show tdn2_show tdn3_show tdn1_eval tdn2_eval tdn2_eval' tdn3_evalmainbbf1bbf2td1td2td2otd3td1_evaltd2_eval td2_eval'td3_evaltd1_viewtd2_viewtd3_viewmain'tdyn1 tdyn1_eval tdyn1_viewtx1tx2tx3tx4tx_viewtx1_viewtx4_view tc_evalviewtr_inttr_addtr_apptr_lamtr_vartr_tinttr_tarrdt1dt2dt4dt41dt5dt6exp_n2dt7dt8term43term43Smake_ind_quantterm43L1term43L2 $fGenLRhihotl1tl2otl3tl4tl5tl1_evaltl3_eval tl3_eval'tl4_eval tl4_eval'tl5_eval tl5_eval'tl1_viewtl3_viewtl4_viewtl5_viewtg2tgktgk'tg4tg5tg71tg72tg73tg74tg2_evaltgk_eval tgk'_evaltg4_evaltg5_eval tg72_eval tg73_eval tg74_evaltg2_viewtgk_view tgk'_viewtg4_viewtg5_view $fMonadSLazy $fMonadSValue $fEDSLSName $fMonadSNamet0SNt1SNt2SNt0SVt1SVt2SVt0SLt1SLt2SLth1th2th3th1_evalth2_eval th2_eval'th3_evalth1_viewth2_viewth3_viewtpowtpow7tpow72 tpow_eval tpow72_eval tpow_viewtb1tb1_viewtb2tb2_evaltb2_viewte1te2te3te4te3_eval te3_eval'te3_viewte4_evalte4_viewtec1 tec1_eval tec1_viewtec2 tec2_eval tec2_eval' tec2_eval'' tec2_viewtec4 tec4_eval tec4_viewtecc1 tecc1_eval tecc1_eval' tecc1_viewcps1tek1 tek1_eval tek1_viewtek2 tek2_eval tek2_eval'' tek2_viewtek4 tek4_eval tek4_viewtekk1 tekk1_eval tekk1_eval' tekk1_view$fEDSLS1test0term1test10test1termidtestidterm2atest2aterm3test3term4test4term6test61test62tmul1testm1deltatestdtmultestm21'testm21testm22testm23testm24term2idtest2idtermlettestlettest63test64testl1testl2testl3testl40testl4testl42testl43testl5terml51testl51terml52testl52testl61testl62testl63testl66testl67testl69testl6atestl71testl72testl73testl74testl75testl76testl77term2btest2bterm4atest4aterm4btest4b $fShowTermtest0dtest0otest11dtest11otest12dtest12oterm2test21test22test23dtest23otestm1dtestm1otestm21dtestm21otestm23dtestm23oevalstshowtest11stest11test12test13test14test23test31test32test33test41test42test43termYtestm2termfibtestfib $fUnifiableUNprunebevalcevalbevalicevalib interleaveadd_marktest2mul_marktest5proj_xyz $fShowHTrue$fESuSu$fE:>>==appndappnd123$$stest1stest2stest3stest3'$fCaughtMonadIOWriterT$fCaughtMonadIOReaderTtestfntestcuntestf1testf2testf2' $fCSHOW(->)$fCFromInteger(->)1 Text.Readread $fCMul(->)1 $fCAdd(->) $fCAdd(->)0__ta1ta2*$genftm1tmbtmote1rtfc12tfc2tfc3tfc31testartestarrt1dtest1ltest1l_rtest1l_ltest1l_ctest2ltest2l_rtest2l_l test2l_l'test2l_ctest3ltest3l_rtest3l_l test3l_l'test3l_ctest31l test31l_r test31l_l test31l_ctest32l test32l_r test32l_l test32l_ctest33l test33l_rtestltestl_rtestl_ltestl_ctestl1_rtestl1_ctestl2_rtestl2_ltestl2_ctestl3_rtestl3_c