Thursday, June 28, 2012

An intuitive view of Algorithms in terms of Category Theory


Inspired by this wonderful article : Why do monads matter?

A function gives one only value of the codomain for each element of the domain set (and thus it can be evaluated a single time for each input value, get its result and forgetting about doing this computation again, that is called graph reduction), 

A category (forget about laws and properties for a moment) is made of a "function generalization" that admita many arrows  from each element of the domain to many elements in the codomain. this wider concept is called a morphism (If I´m not wrong). for that matter, an statement like"getChar", that returns a different output each time can be understood mathematically only using category theory. This is the reason why Category Theory is so important for a mathematical understanding of any algorithm in any  programming language. Because an algorithm is a chain of statements, mathematically it is a chain of morphisms. Generally an algorithm has many statements like getChar that are impure , because it does something with the external world) so the algorithm when executed trough these morphisms travels different graphs on each execution.  To discover where the chain of arrows goes each time, it is necessary to execute the chain of sentences every time.

Imperative languages works "categorically" ever, so they don´t need an special syntax for doing so. It an imperative language find a pure function he will execute it again and again.. It does not know what is pure and what is not.. Haskell permits to discriminate functional code from "normal" "categorical/imperative" code, so the programmer and the compiler can make use of the mathematical properties of pure code with unique paths of execution. That permits equational reasoning and some optimizations. For example, graph reduction, explained above (equational reasoning may be considered as a mental form of graph reduction).


Because a function can not give a different result  haskell can execute it later in time in case it is needed, lazines is another optimization possible as result of the separation of pure functional code from impure code. Something that is not said about laziness is that it permits optimal coarse grained interfaces without losing performance. You can make a deserialized of a  database query result  and only the fields that you use will be deserialized when used.

Because haskell is lazy by default, it needs an special syntax for chaining impure morphisms of the type of getChar where the sequence of execution matters for the resulting output. This imperative execution model is not hardcoded in the language, but it is defined in the Monad instance, defined by a library programmer. And this execution model is not unique, but it is different for each category. The "Monad" instance of each category tell haskell how to compose morphisms for this category in order to traverse the path of execution. 

In the same way that '+' or '*' compose two numbers, the 'bind' method of the Monad instance for each category tell how to compose arrows until the path of execution is complete (that is the  sense of the akward sentence "a monad is a monoid in the category of endofunctors" . A monoid define the way of composing elements of a category. An endofunctor is a particular class of morphisms, but I said from the beginning that we must leave details aside.


Because its unique execution model, imperative languages work in a single category and have an unique execution model. Haskel mimick  other imperative languages by using the monad instance of the IO category. But new categories and execution models can be defined by the programmer.  There are some other Monadic execution models defined. The List category for example, work with all the graph paths of a morphism at the same time, not only a single result (see below). There are some categories defined to handle exceptional paths in a otherwise functional computation ( with the Maybe, Exception or Error monads of each respective category). Even there are executions that can restart graps until transactional completiion (STM) and so on.


Concerning the List category, a (pure) function  

f :: a -> [a]
that return a list can be understood alternatively as a morphism that has many graphs from each element of the domain to many elements of the  codomain. So this function can be considered a morhism in the List category and his corresponding monadic execution model. The monad instance of List permits to handle all graphs resulting from each morphism simultaneously. The computation is pure and imperative at the same time. the List monad operates with (ordered) sets instead of individual results.

Let´s look at the execution model of the list category:

1
2
3

instance  Monad []  where
  m >>= k = concat (map k m)
  return x= [x]

In the bind (>>=) method, the morphism k is applied to all the results of the previous morphism m, (via map) resulting in a set for each value in m. Then these set of sets is unified in a single set with concat.


Oddy enough, the list monad is considered non-deterministic,. Actually, the List monad computes all possible graph simultaneously, while the IO monad traverse a different path of execution each time, so the IO should be the non-deterministic monad.


DISCLAIMER: Ths text is provided "as is" and any express or implied warranties of mathematical accuracy are disclaimed. In no event shall the author ve liable for any direct, indirect, incidental, parallel or sequential damages, including but not limited to loss of use, or business interruption. blah blah blah.



Posted by at 1 comment:

Sunday, March 25, 2012

A fail-back monad

MFlow can express a complete Web navigation within a simple procedure, just like a console program. The problem of this model is the back button. There is nothing like the back button in console applications.  The user can not decide to go back in a console application. but in a Web application, the user can do it.

Since I want to go back to the code of the previous user interactions, not just to the previous statement, I need a monad transformer which permits the creation of ckeckpoints form which the computation can be resumed when the received result does not match with the output expected from the last form that was sent to the user. If the user go back, what the application receives is an output corresponding to a past interaction. Then I do not receive what I expect. I need a way to go back in my code acordingly upto the user interaction step that match the output.

Since my interaction is basically similar to a console application, this example below would be a simple console translation for my problem. liftRepeat will label the checkpoint from which I want to go back and repeat the code when fail is invoked.

1
2
3
4
5
6
7
8
9

test= runBackT $ do
       lift $ print "will not return back here"
        liftBackPoint $ print "will return here"
        n2  <- lift $ getLine
        lift $ print "second input"
        n3  <- lift $  getLine
        if n3 == "back"
                   then  fail ""
                   else lift $ print  $ n2++n3

Whenever the second input is "back" The procedure will go back to where liftBackPoint is. Otherwise, it will return the concatenation of the two inputs.

Here below is the failback monad transformer.  (I will not call it "backtracking" since this term has a tradition in non-deterministic logic programming). 

The monad instance is similar to what would be an identity monad transformer  as long as NoRepeat is used. But when GoBack found, the monad roll back until a BackPoint is found and the computation start again from it. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

data FailBack a = BackPoint a | NoBack a | GoBack  
newtype BackT m a = BackT { runBackT :: m (FailBack a ) }


instance Monad m => Monad (BackT  m) where
    fail   _ = BackT $ return GoBack
    return x = BackT . return $ NoBack x
    x >>= f  = BackT $ loop
     where
     loop = do
        v <- runBackT x
        case v of
            NoBack y  ->; runBackT (f y)
            BackPoint y  ->; do
                 z <- runBackT (f y)
                 case z of
                  GoBack  ->; loop
                  other ->; return other
            GoBack -> return  GoBack


backPointReturn x= BackT . return $ BackPoint x
liftBackPoint f= BackT $ f >>= \x -> return $ BackPoint x
backPointHere :: Monad m => BackT m ()
backPointHere = backPointReturn ()

This monad does not perform exploration of alternatives as is the case of MonadPlus instances. It does not perform the kind of backtracking of "nondeterministic"  three navigations in the Prolog style. It just go back to the point where the computation can restart again in a  sequence of actions.

The chain of fail backs could go as far back as necessary, That is what I need, since the user can go back as deep in the web browser as he pleases.

In particular if the embedded monad is an state monad, the state will transport the user output back to the previous interaction 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

instance (MonadIO m, MonadState s m) =>; MonadIO (BackT  m) where
  liftIO f= BackT $ liftIO  f >>= \ x -> return $ NoBack x

instance (Monad m,Functor m) => Functor (BackT m) where
  fmap f g= BackT $ do
     mr <- runBackT g
     case mr of
      BackPoint x  -> return . BackPoint $ f x
      NoBack x     -> return . NoBack $ f x
      GoBack       -> return   GoBack

instance MonadTrans BackT where
  lift f= BackT $ f >>= \x ->  return $ NoBack x

instance MonadState s m => MonadState s (BackT m) where
   get= lift get
   put= lift . put
These are the instances that I need to lift the computations to the failback monad.

I suspect that this monad has more applications. For example it can be used to generalize exceptions for any monad

See this short mail list discussion where Oleg shows some alternatives:

http://haskell.1045720.n5.nabble.com/Fail-back-monad-td5599230.html

An important advantage of this monad is that it is tail recursive, unlike other alternatives, and captures all the semantic of the problem and the solution in a single monad, instead of a combination of monads.
Posted by at No comments:

Monday, February 06, 2012

MFlow: A Web application server with stateful server processes and simple typed widget combinators.



I Just released MFlow, a simple application server with stateful request-response flows, persistent and transparent session handling. server process management, combinators for the definition of widgets and formlets that can be mixed freely with HTML formatting and produce statically  typed web applications. Adopt and extend the best formlet/applicative Haskell traditions. Console and window oriented apps are possible.

              .
MFlow (MessageFlow) was created initially as the user interface for the Workflow package. Currently is an alpha version. It has only basic authentication but I plan to inprove it for serious applications.

 It includes Application Server features such is resource an process management and automatic recovery
           .
  Resource management: The user can define process and session timeout. The  process is automatically rerun after timeout if a new request arrive with transparent  recovery of state, at the point of the interrupted dialog  even after server crash.

The backend operation relies on the Workflow package

http://hackage.haskell.org/package/Workflow

Workflow gives transparent sessión persistence and recovery, all of this  is supported by  TCache:

http://hackage.haskell.org/package/TCache

TCache gives backend-independent transactions and can be used directly by the programmer. Persistence in files  for session and data out of the box enables  very fast prototyping.

All the plumbing is hidden to the programmer, There is no methods for session management, database query, recovery and so on. All of this is  transparent So the surface exposed to the programmer is minimal.

Includes generalized formlets that permits the mix of active widgets  in the same page while remaining statically typed and, thus the programs can verify correctness at compilation time.

Includes combinators for seamless inclusion of these widgets within  user defined HTML formatting. Bindings for Text.XHtml. The widget generation may be easy for user with familiarity with formlets/digestive functors and Text.XHtml formatting.

Currently it has bindings for the Hack  interface This module defines an integrated way to interact with the user. `ask` isa single method of user interaction. it send user interfaces and return statically typed responses. The user interface definitions are  based on the formLets interface

But additionally, unlike formLets in its current form, it permits the definition of widgets. A widget is data that, when renderized and interact with the user, return data, just like a formlet, but it hasn to be an HTML form. it can contain JavaScript, or additional Html decoration or it can use Ajax istead of form post for the interaction. There is an example of widget defined (`Selection`) widgets (and formlets) can be combined in a sigle Html page.Here is a ready-to-run example that combines a Widget (Selection) and a HTML decorated formLet in the same page.

This example show a widtget and a formlet togeter in a statically typed page defined in a declarative style. The server process has 10-15 lines. But it transparently manages user state, session timeout, shutdown the server process and restart it even after intended or unintended server shutdown.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

{-# OPTIONS -XDeriveDataTypeable
            -XMultiParamTypeClasses -XRecordWildCards

            #-}
module Test where
import MFlow.Hack.XHtml.All

import Data.Typeable
import Control.Monad.Trans
import qualified Data.Vector as V

import Data.TCache
main= do
   userRegister  "pepe" "pepe"


   putStrLn $ options messageFlows
   run 80 $ hackMessageFlow messageFlows
   where
   messageFlows=  [("main",  runFlow mainProds)
                  ,("hello", stateless hello)]

   options msgs= "in the browser choose\n\n" ++
     concat [ "http://server/"++ i ++ "\n" | (i,_) <- msgs]



-- an stateless procedure, as an example
hello :: Env -> IO String
hello env =  return  "hello, this is a stateless response"


data Prod= Prod{pname :: String, pprice :: Int} deriving (Typeable,Read,Show)

-- formLets can have Html formatting
instance FormLet Prod IO Html where
   digest mp= table <<< (
      Prod <$> tr <<< (td << "enter the name"  <++ td <<< getString (pname <$> mp))
           <*> tr <<< (td << "enter the price" <++ td <<< getInt ( pprice <$> mp)))


-- Here an example of predefined widget (`Selection`) that return an Int, combined in the same
-- page with the fromLet for the introduction of a product.
-- The result is a 2-tuple of Maybes

shopProds :: V.Vector Int -> [Prod]
          -> View Html IO  (Either Int Prod)
shopProds cart products=
  br
  <++                    -- add Html to the first widget
  p << "-----Shopping List-----"
  <++
  widget(Selection{
       stitle = bold << "choose an item",
       sheader= [ bold << "item"   , bold << "price", bold << "times chosen"],
       sbody= [([toHtml pname, toHtml $ show pprice, toHtml $ show $ cart V.! i],i )
              | (Prod{..},i ) <- zip products [1..]]})

  <+>                    -- operator to mix two wdigets

  br
  <++                    -- add Html to the second widget
  p << "---Add a new product---"
  <++
  table <<<              -- <<< encloses a widget in HTML tags
            (tr <<< td ! [valign "top"]
                          <<< widget (Form (Nothing :: Maybe Prod) )

             ++>         -- append Html after the widget

             tr << td ! [align "center"]
                          << hotlink  "hello"
                                      (bold << "Hello World"))

-- the header

appheader user forms= thehtml
         << body << dlist << (concatHtml
            [dterm <<("Hi "++ user)
            ,dterm << "This example contains two forms enclosed within user defined HTML formatting"
            ,dterm << "The first one is defined as a Widget, the second is a formlet formatted within a table"
            ,dterm << "both are defined using an extension of the FormLets concept"
            ,dterm << "the form results are statically typed"
            ,dterm << "The state is implicitly logged. No explicit handling of state"
            ,dterm << "The program logic is written as a procedure. Not    in request-response form. But request response is possible"
            ,dterm << "lifespan of the serving process and the execution state defined by the programmer"
            ,dterm << "user state is  automatically recovered after cold re-start"
            ,dterm << "transient, non persistent states possible."
            ])
            +++ forms

-- Here the procedure. It ask for either entering a new product
-- or to "buy" one of the entered products.
-- There is a timeout of ten minutes before the process is stopped
-- There is a timeout of one day for the whole session so after this, the
-- user will see the list  or prudicts erased.
-- In a real application the product list should be stored out of the session
-- using TCache's writeDBRef for example
-- The state is user specific.

mainProds ::  FlowM Html (Workflow IO) ()
mainProds   = do
   setTimeouts (10*60) (24*60*60)
--   setHeader $ \w -> bold << "Please enter user/password (pepe/pepe)" +++ br +++ w
--   us <-  getUser

   setHeader  $ appheader  "user"
   mainProds1 [] $ V.fromList [0]
   where
   mainProds1  prods cart=  do
     mr <- step . ask  $ shopProds  cart prods
     case mr of
      Right prod -> mainProds1  (prod:prods) (V.snoc cart 0)
      Left i   -> do
         let newCart= cart V.// [(i, cart V.! i + 1 )]
         mainProds1 prods newCart


Posted by at No comments:

Monday, November 07, 2011

New version of the package Workflow

A new version of Workflow is coming. I will have a surgery now, so I uploaded it to my public folder in dropbox. Just in case.

http://dl.dropbox.com/u/23415684/Workflow-0.5.8.rar

See the documentation and the demos (in  Demos directory)  included.  It admits Binary and RefSerialize serialization . This is an intermediate step to allow user-defined serializations.  RefSerialize mode does not work still. I hope to fix it soon.


Workflow-0.5.8: library for transparent execution of interruptible computations

Workflow-0.5.8: library for transparent execution of interruptible computations

Transparent support for interruptible computations. A workflow can be seen as a persistent thread that executes any monadic computation. Therefore, it can be used in very time consuming computations such are CPU intensive calculations or procedures that are most of the time waiting for the action of a process or an user, that are prone to comunication failures, timeouts or shutdowns.
The computantion can be restarted at the interrupted point because the computation is encapsulated inside a state monad transformer that transparently checkpoint the computation state. Besides that, the package also provides other services associated to workflows
New in this release, * registerType is no longer needed (made possible by the use of TCache 0.9 usage)
  • configurable state persistence (for example, in databases) (made possible by the use of TCache 0.9 usage)
  • optional binary serialization of state
  • new simpler and more ituitive workflow start(int) primitives
  • instances of classes in Control.Concurrent.MonadIO, MonadCatchIO etc
  • Patterns, an EDSL of workflow patterns. To express workflows as sequences and concurrency of actions
The main features are:
  • logging of each intermediate action results in disk.
  • resume the monadic computation at the last checkpoint after soft or hard interruption.
  • suspend a computation until the input object meet certain conditions. Useful for inter-workflow comunications.-
  • Persisten communications facilities trough persistent data objects, inspection of workflow states , persistent queues, persistent timeouts, to avoid data lost due to shutdowns
  • workflow management and monitoriing, view workflow history and intermediate results.
Posted by at No comments:

Tuesday, December 08, 2009

The Transient monad

Concerning Stable Names http://www.haskell.org/ghc/docs/6.10.4/html/libraries/base/System-Mem-StableName.html
I did not test fully my proposal, and I´m thinking aloud, Just to inspire others and fish some ideas: look at the type:
makeStableName :: a -> IO (StableName a) The IO in makeStableName suggest more side effects than the call really do. But still it isn't pure. For calls such are makeStableName that gives a different result the FIRST time they are called but return the same result every time in the same session, I suggest to use a Transient monad: makeStableName :: a -> Transient (StableName a) The key here is to maintain the programmer aware that it is not pure, but there are no IO and that the results have no meaning from session to session. Instance Monad Transient where Transient x ↠ f = f x return x = Transient x We can Transient`ize IO calls by means of an implicit memoization: liftT:: IO a -> Transient a liftT= liftT2=.... liftT3=.... Memorization then is embedded in the monad transformation.
This may be more elegant than IO plus unsafePerformIO and is more informative for the programmer. Instead of unsafePerformIO, we can use: unsafePurifyTransient :: Transient a -> a unsafePurifyTransient (Transient x) = x for the inherently transient calls
The transition form IO to pure can be done in two steps trough Transient: A safer version of unsafePerformIO using implicit memoization could be:
unsafePerformIOT :: IO a -> a unsafePerformIOT = unsafePurifyTransient . liftT unsafePerformIOT guarantee that it returns the same value in the same session
Twan van Laarhoven objected that makeStableName return different values before and after evaluation of an expression. True, makeStableName does not return the same value ever. This is the second time that I forget that. Still I think that Transient or something similar is worth the pain for making a less unsafe transition from IO to pure trough memoization, That was my goal.
For this reason, I want something more narrow than IO to make the programmer aware of the higuer level of safety, rather than something more general.
Stable names are good for memoization however, since memoization of IO procedures can be implemente by hashing their stable names. I think that it is possible to force the evaluation of an expression, then it is possible to have a Transient version of makeStableName.
Transient means that something has been cached and fixed. This can be generalized also for temporary valid computations:
data Time= Session | Time Integer
data Transient a= Trans (Time, a)
instance Monad Transient where
Trans( t,x) ↠ f =
let Trans (t2, y) = f x
in Trans ((min1 t t2) , y)
return x = Trans (Session, x)
min1 :: Time → Time → Time
min1 Session x= x
min1 x Session= x
min1 (Time x) (Time y)=Time $ min x y
This monad will calculate the time that the result remain valid given the time validity of each computation involved.
Well, more fine calculation is needed since the computation takes time too. Perhaps the bind operation can abort the compuitation and send an error when the time is zero. this can be catched to restart the computation again or whatever else.
Posted by at No comments:

Saturday, November 21, 2009

Workflow: an Haskell package for transparent support of interruptible computations

A month ago i uploaded the package Workflow to hackage, the repository of Haskell libraries. I added an hopefully self suficient documentations and examples.
Here follows a few remarks, a simple example and a more sophsticated example:

The main features are:

  • Transparent state logging trough a monad transformer: step :: m a -> Workflow m a.
  • Resume the computation state after an accidental o planned program shutdown (restartWorkflows).
  • Event handling (waithFor, waitForData).
  • Monitoring of workflows with state change display and other auxiliary features.
  • Communications with other processes including other workflows trough persistent data objects, inspecttion of intermediate workflow results , Queues so that no data is lost due to shutdowns

Here is a complete example:

This is a counter that shows a sequence of numbers, one a second:

module Main where 
import Control.Concurrent(threadDelay) 
import System.IO (hFlush,stdout)  
count n= putStr (show n ++  ) >> hFlush stdout >> threadDelay 1000000 >> count (n+1) 
main= count 0

This is the same program, with the added feature of remembering the last count after interrupted:

module Main where 
import Control.Workflow 
import Control.Concurrent(threadDelay) 
import System.IO (hFlush,stdout)  
mcount n= step $  putStr (show n ++  ) >> hFlush stdout >> threadDelay 1000000 >> mcount (n+1)  
main= do    
   registerType :: IO ()    
   registerType :: IO Int    
   let start= 0 :: Int    
   startWF  count  start   [(count, mcount)] :: IO ()
This is the execution log:
Worflow-0.5.5demos>runghc sequence.hs 
0 1 2 3 4 5 6 7 sequence.hs: win32ConsoleHandler sequence.hs: sequence.hs: interrupted 
Worflow-0.5.5demos> 
Worflow-0.5.5demos>runghc sequence.hs 
7 8 9 10 11 ....




Here is the complete documentation iof the package






And here is a more sophisticated example, at pastebin.org. The code is also documented.










Posted by



at





No comments:
  






































          

        

          

        

Tuesday, September 29, 2009


          

        









The future of Haskell














Most successful languages spread because they are part of a platform which solves an IT problem. C was part of Unix, both brougth CPU independence when this was necessary. Java is part of the Java platform, that brougth OS independence and interoperability at the right time. Download-execution on the client was also a reason for the initial success of Java in the Internet era.  Javascript is part of the web browser. The .NET languages are part of NET.  Rubi and Pyton came with libraries targeted to Rapid development of Internet applications.



What is the vehicle that haskell can use to enter the mainstream?. I think that the mere interest of the ideas in the language is not enough.  Many people will play with Haskell in the spare time, and many of them will be permitted to develop some non critical applications at work. But that is all.  Java was not designed for the Internet but it was re-targeted to it because some needed features where already implemented in Java. Maybe something like that will happen to Haskell.



I think that all the current niches are filled, but new niches  are coming. specially with higher level programming that is made on top of current software infrastructure such are BPM, workflows, more flexible scientific applicatins, creation of  models in business intelligence, as part of ERPs,.Data mining too.  And higuer levels of netwrok communications( for example, Google Wave robots) etc.



About the last point, sometimes a basically identical infrastructure is re-engineered to a higher level, and a new language takes over. For example, the  architecture of many Internet applications in the 80s was client-server based, where C, C++ was the king. This was substituted by  the web architecture with Java because Java was involved in the gradual change by filling the holes of the new architecture.  It could be that in a few years, instead of Web sites people could develop interoperable gadgets for aggregators such are netvibes or IGoogle or, even more radical, robots and gadgets in google Wave. Anyway, for sure, people will think and develop at a higher level.



Financial applications are an example of higher level programming where tasks usually performed by humans are now automatized and there is no or few traditions about that. The need to think at a higher level without being worried by side effects and other details are specially needed in such kind of areas. That's where haskell could have its own niche.



Regards










Posted by



at





No comments:
  






































        

      









Subscribe to:
Posts (Atom)