v      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                       Darn! 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. <Convert a file descriptor to an FDSet (for use with select) ? essentially encode a file descriptor in a big-endian notation 0poll if file descriptors have something to read - Return the list of read-pending descriptors  !8Interface with my sys_open, see sys_open.c for detailed  description and comments 6Close the output direction of the bi-directional pipe   "#$%&'()*+,-.     Printerparsers (injectionprojection pairs)  !"Ha bit of syntactic sugar to avoid hitting the Shift key too many a time #The interpreter for printf  It implements Asai'"s accumulator-less alternative to  Danvy's functional unparsing $The interpreter for scanf %&'LThe 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 (A 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  !/012"#$%&3456789:;<=>?'(! "#$%&'(!  !"#$%&'(+)*+,-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 /0GFinally, we demonstrate that our calculus is combinatorially complete, $ by writing the S and K combinators 12(Finally, the standard test -- Fibonacci 34567now we tie up the knot 8#and define the sum of two numerals )At the type level, this looks as follows 91We 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: ABCDEFGFirst we define some constants HIJK@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. AOther particular rules B Familiar rules for applications C6Abstractions are values and so evaluate to themselves D!Constants evaluate to themselves EGWhen we receive the second argument, we are in the position to produce . the result. Again, we use the case analysis. FDApplying And to an argument makes a closure, waiting for the second  argument. Gby case analysis: /)*+,-./0123456789:;<=>?@ABCDEFGHHIJKLMNOIPQJRSK#GHEFCDAB@?>=<;:9876543I21J0/.-,+K)*#)**+,-./0123456789:;<=>?@ABBCDDEFFGHHIJKLM%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. NOwe make a very little change PFThe 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 QRTo generalize, SMWe 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. TUKWe introduce the combinator Ntimes: |NTimes f x n| applies f to x n times. ' This is a sort of fold over numerals. V@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. WXY%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: ZTGWe 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 LMNOPQRSTUVWXYUZVWXYZ[\]YXWVZUTSRQPOMNLLMNNOPQRSTUVWXYZ,[\ 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. _`abcdBIteratee -- 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 efg<A particular instance of StreamG: the stream of characters. , This stream is used by many input parsers. hCA 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. ijkl>Useful combinators for implementing iteratees and enumerators m:Just like bind (at run-time, this is indeed exactly bind) n=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. oBRead a stream to the end and return all of its elements as a list p'Check to see if the stream is in error qThe 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. rJA 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 s/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) t?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) uSkip the rest of the stream v6Skip n elements of the stream, if there are that many # This is the analogue of List.drop wBRead 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). x1Map 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 y4Convert 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. z&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 D[\]^_`abcdefghijklm`nopqrstuvwxyz{|}~abcdefghijklmnopqrstuvwx+hkjigdfeabc`_lmnopqrstuv^wxy]z{|}\[~+[\]^_`abcbcdfeefghkjiijklmnopqrstuvwxyz{|}~9Generally, 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 w 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{|}~ \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  %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  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                  !"#$%&'()*+ !"#,-./0123456789:;<=>?@AB$CCDDEEFFGHIJKKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                                                                 K K                 !"#$ !"#$%&'()*+,-./0123456789:;<=>?@AB CDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefgh i j k l m n o p q r ` a s t u v w x y z { | } ~                          liboleg-0.1.0.2System.LowLevelIOSystem.SysOpenText.PrintScanFText.PrintScanLanguage.TypeLCLanguage.TypeFNSystem.IterateeMSystem.RandomIOCodec.Image.TiffControl.CaughtMonadIO Data.FDListbaseForeign.C.ErrorErrnomyfdReadmyfdSeekselect'read'pending mysysOpenFd mysysCloseFd mysysCloseOut read_lineFScFPr PrinterParserFormattingSpeclitintcharfpp^fmtsprintfsscanfshowreadprefixF:^FPPFChrFIntFLitintpintsNatfromNatCombTwoCombSuCombZTest_skkCombSCombKFibFib'N3N2N1N0FSumFSum'RecTestbE:<FAndFNotASuZeroHFalseHTruetest_sumtest_fib test_ctwoTreeDNNodeSSPropN'FlipSPropN'ATC2PropN'ATC1Ntimes StrangePropProp2PropProp'oddand4t 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_string CaughtMonadIOgcatch MyExceptioncatchDynDList dl_counter dl_currentdl_memnode_val node_left node_rightRefempty well_formedis_empty get_curr_node insert_rightdeleteget_curr move_right move_right' move_left move_left'fromListtakeDL takeDLrevupdatetoListfcntlc_selectcLSeekstrerrorcReadTIMEVALFDSETfd2fdsfds2mfdunFd c_shutdown c_mysysClose c_mysysOpentp1ts1tp2ts2fmt3tp3ts3tp4ts4fmt50fmt5tp5ts5 $fShowHTrue$fESuSu$fE: