Haskell and Web

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

2012-02-06T09:52:00.000+01:00

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.

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

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.

{-# 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

New version of the package Workflow

2011-11-07T08:03:00.000+01:00

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

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.

Modules

Control
- Workflow

The Transient monad

2009-12-08T13:46:00.004+01:00

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.

Workflow: an Haskell package for transparent support of interruptible computations

2009-11-21T00:48:00.012+01:00

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.

The future of Haskell

2009-09-29T12:23:00.004+01:00

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

Declarative vs imperative: Math, Algoritms, the universe and everything

2009-01-17T23:31:00.002+01:00

The question of imperative versus pure declarative coding has brought to my mind some may be off-topic speculations. (so please don´t read it if you have no time to waste): I´m interested in the misterious relation bentween mathematics, algoritms and reality (see this for example). Functional programming is declarative, you can model the entire world functionally with no concern for the order of calculations. The world is mathematical. The laws of physics have no concern for sequencing.

But CPUs and communications are basically sequential. Life is sequential, and programs run along the time coordinate. Whenever you have to run a program, you or your compiler must sequence it. The sequentiation must be done by you or your compiler or both. The functional declarative code can be sequenced on-the-run by the compiler in the CPU by the runtime. but IO is different.

You have to create, explicitly or implicitly the sequence of IO actions because the external events in the external world are not controlled by you or the compiler. So you, the programmer are the responsible of sequencing effects in coordination with the external world. so every language must give you ways to express sequencing of actions. that is why, to interact with the external world you must think in terms of algorithms, that is , imperatively, no matter if you make the imperative-sequence (relatively) explicit with monads or if you make it trough pairs (state, value) or unsafePerformIO or whatever. You have to think imperatively either way, because yo HAVE TO construct a sequence. I think that the elegant option is to recognize this different algorithmic nature of IO by using the IO monad.

In other terms, the appearance of input-output in a problem means that you modelize just a part of the whole system. the interaction with the part of the system that the program do not control appears as input output. if the program includes the model of the environment that give the input output (including perhaps a model of yourself), then, all the code may be side effects free and unobservable. Thus, input output is a measure of the lack of a priori information. Because this information is given and demanded at precide points in the time dimension with a quantitative (real time) or ordered (sequential) measure, then these impure considerations must be taken into account in the program. However, the above is nonsensical, because if you know everithing a priory, then you don´t have a problem, so you don´t need a program. Because problem solving is to cope with unknow data that appears AFTER the program has been created, in oder to produce output at the corrrect time, then the program must have timing on it. has an algoritmic nature, is not pure mathemathical. This applies indeed to all living beings, that respond to the environment, and this creates the notion of time.

Concerning monadic code with no side effects, In mathematical terms, sequenced (monadic) code are mathematically different from declarative code: A function describes what in mathematics is called a "manifold" with a number of dimensions equal to the number of parameters. In the other side, a sequence describe a particular trayectory in a manifold, a ordered set of points in a wider manyfold surface. For this reason the latter must be described algorithmically. The former can be said that include all possible trajectories, and can be expressed declaratively. The latter is a sequence . You can use the former to construct the later, but you must express the sequence because you are defining the concrete trajectory in the general manifold that solve your concrete problem, not other infinite sets of related problems. This essentially applies also to IO.

Well this does not imply that you must use monads for it. For example, a way to express a sequence is a list where each element is a function of the previous. The complier is forced to sequence it in the way you whant, but this happens also with monad evaluation.

This can be exemplified with the laws of Newton: they are declarative. Like any phisical formula. has no concern for sequencing. But when you need to simulate the behaviour of a ballistic weapon, you must use a sequence of instructions( that include the l newton laws). (well, in this case the trajectory is continuous integrable and can be expressed in a single function. In this case, the manifold includes a unique trajectory, but this is not the case in ordinary discrete problems,) . So any language need declarative as well as imperative elements to program mathematical models as well as algorithms.

About programming and design

2009-01-11T14:13:00.000+01:00

As a physicist, I think that programming, like any design in general, is all about making as little use of brain resources as possible at the time of solving problems and to transmit the solution to others. This is the reason why it is pervasive in all kinds of engineering the concepts of modularity, isolation, clean interfacing (for which referential transparency is part of) etc. To decompose a problem in parts each one with simple solutions and with as little uncontrolled interaction with other parts is a rule of good design simply because we can not think in nothing but around seven concepts at the same time (By the way, an evolutionary psychologist would say that the beatifulness of simplicity is related with this release of brain resources). As a matter of fact, these rules of "good" design do not apply to the design of living beings simply because the process of Natural Selection has not these limitations. that is indeed the reason because natural designs are so difficult for reverse engineering.

Because such kid of human brain limitations and our lack of knowledge, design has a lot of trial and error. The danger of this is to get lost in the explosion of unfruitful alternatives due to low level issues outside of our high level problem, because the limitation of the tools we are using for it. In this sense, things like the strong type inference is superb for cutting the explosion of erroneous paths that the process of software development can generate. If designing solutions is sculpting order from chaos and against chaos, intelligent tools are the thing needed to keep us concentrated in fruitful courses of action. A physicist would say that design is to lower the entropic balance by progressively lowering the number of microstates until the only ones permitted correspond with the desired outcomes, called "solutions" and a few bugs, of course.

For me, syntactic sugar is one more of this features that make haskell so great. Once we discover that a solution general enough has a correspondence with something already know, such are monads for imperative languages, then, why not make this similarity explicit ,with the do notation, in order to communicate it better with other people making use of this common knowledge?.

I have to say also that, without Haskell, I never dream to have the confidence to play simultaneously with concurrence, transactions, internet communications, parsing and, at the time, keeping the code clean enough to understand it after a month of inactivity. This is for me the big picture that matters for real programming.

A new version of TCache (0.5.5)

2009-01-09T20:51:00.005+01:00

has been uploaded to hackage.
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/TCache

The main addition of this versión is the capablity to safely handle transact, and serialize to permanent storage many datatypes simultaneously in the same piece of code and incrementally.

Just register each new datatype (with registerType :: ). So it is not necessary to glue all types in advance in a single algebraic datatype. I suppose taht "enhanced composablility" applies to this feature.

In this release:
Added a Data.TCache.Dynamic. (SEE dynamicsample.hs)
- Can handle, transact, and serialize to disk many datatypes simultaneously and incrementally
- Dynamic uses the same interface than TCache and add *DResource(s) calls for handling many
datatypes simultaneously
- Safe dynamic data handling trough a lighter, indexable and serializable version of Data.Dynamic
- Added KEY object for retrieving any object of any type.

Data.Tcache is a transactional cache with configurable persistence. It tries to simulate Hibernate
for Java or Rails for Ruby. The main difference is that transactions are done in memory trough STM.
There are transactional cache implementations for some J2EE servers like JBOSS.

TCache uses STM. It can atomically apply a function to a list of cached objects. The resulting
objects go back to the cache (withResources). It also can retrieve these objects (getResources).
Persistence can be syncronous (syncCache) or asyncronous, wtih configurable time between cache
writes and configurable cache clearance strategy. the size of the cache can be configured too .
All of this can be done trough clearSyncCacheProc. Even the TVar variables can be accessed
directly (getTVar) to acceess all the semantic of atomic blocks while maintaining the persistence of the
TVar updates.

Persistence can be defined for each object: Each object must have a defined key, a default filename
path (if applicable). Persistence is pre-defined in files, but the readResource writeResource and
delResource methods can be redefined to persist in databases or whatever.

There are Samples in the package that explain the main features.

axioms-properties for haskell classes

2008-10-23T22:01:00.001+01:00

Axioms and properties for haskell classes

Alberto Gómez Corona agocorona (at) gmail.com

NOTE: added changes to avoid error due to duplicated instances. See code below.

Eureka!!!

. I found someting interesting that have something in the middle
of the heaven of universal algebras and the firm ground of quickcheck:

This is a way to express axioms in pure Haskell and make practical use of them at the same time:

First, I start by defining a special class called Axioms that contains list of different properties with different arities.

data Axiom a= Axiom String a

class Axioms a where
unaryAxioms :: [Axiom (a -> Bool)]
unaryAxioms = []

binaryAxioms :: [Axiom ((a,a) -> Bool)]
binaryAxioms = []

ternaryAxioms :: [Axiom ((a,a,a) -> Bool)]

ternaryAxioms = []

For properties involving relations between two or many classes, a similar multiparameter type class is also possible (see code below).

If I need to define axioms/properties for the the methods of a
class, I just make the class a instance of Axioms:. For example, for a
Ring:

class Eq a => Ring a  where
  op1 :: a -> a -> a
  op2 :: a -> a -> a
  zero :: a
  inverse :: a -> a

You see that the kind of both op1 and op2 say very little about the structure of the ring. Anyone can instantiate a Num class without respecting the nature of * and + operations.
What gives a Class the meaning and structure of the Class for which he was designed are the axioms.

I want to express that whenever a Ring a is defined, it
must agree with some Axioms. I think that this way of defining
properties is fairly meaningful to say in haskell:

instance  Ring a => Axioms a where
  unaryAxioms   = [Axiom "identity" (\x -> zero `op2` x == zero)
                  ,Axiom "inverse element" (\x -> x `op1` (inverse x) == zero)
                  ]

  binaryAxioms  = [Axiom "commutative"   (\(x, y) -> x `op1` y == y `op1` x)]

  ternaryAxioms = [Axiom "associative `op1`" (\(x,y,z) -> (x `op1` y) `op1` z== x `op1` (y `op1` z))
                  ,Axiom "associative `op2`" (\(x,y,z) -> (x `op2` y) `op2` z== x `op2` (y `op2` z))
                  ,Axiom "distributive"  (\(x,y,z) -> x `op2` (y `op1` z)== (x `op2` y) `op1` (x `op2` z))
                  ,Axiom "distributive2" (\(x,y,z) -> (x `op1` y) `op2` z== (x `op2` z) `op1` (y `op2` z))
                  ]

What practical use can I extract from this stuff?

Lets define any object of the class Num as a Ring

instance  Num a  => Ring a where
  op1= (+)
  op2= (*)
  zero = 0
  inverse= negate

Now we will see te return of all of this stuff. We have Num, We have the operators of Num and we have the meaning, the semantic that glue all pieces togeter captured in the Ring axioms. Now, in a Galaxy far away, someone define a new data type as member of the class Num. Because Num is a Ring , It can test the compliance with the axioms of this new Ring candidate:

instance Num N where
  (+) (N x) (N y)= N (x + y)  `verify`  binaryAxioms `with` ((N x), (N y))
  (-) (N x) (N y)= N (x - y)
  (*) (N x) (N y)= N (x * y)
  negate (N x)= N (-x)
  abs (N x) = N (abs x)
  signum (N x)= N (signum x)
  fromInteger i= N (fromInteger i)



main= do

  let x= N 5
  let y= N 3           `verify`  unaryAxioms `with` x
  let z= x + y
  print z
  let t= N 7
  print t              `verify`  ternaryAxioms `with` (x,y,z)

Here I show two different ways to test axioms/ properties: Either in the instance definition or in the middle of the code

With "verify axiom data" inserted in strategic parts of the
code i have a cheap quickcheck with the advantage that I can test the
real data of my aplication. you can play with the class definitions and see the violated axioms.

Note that with the Ring properties I can define subtractions in a counterintuitive way, since the ring properties say nothing practical
about substraction. Here we can see the difference between axiom and
the more practical concept of "property". although both can have the
same shape.

Note that for this ring is fairly straighforward to realize that
it is a ring since it is a small modification of Number. This would be
not so obvous for more complicated datatypes, maybe this is a way to add confidence for
managing complicated pieces of code with unsafe IO operations and other beasts as Rings or other mathematical structures!.

This can be applied of course for anything you may think that may have a property to check.

I´m excited!

NOTE : I had to eliminate the separate Axioms class and put the properties directly inside the class definitions due to some limitations. that makes thigs a little less flexible. Here is the code:

The complete code:


Copyright (c) Alberto Gómez Corona 2008 agocorona@gmail.com
see http://docs.google.com/Doc?id=dd5rm7qq_165rshp74gf&hl=en

version 2.0
corrected some instantiation problems

All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
3. Neither the name of the author nor the names of his contributors
   may be used to endorse or promote products derived from this software
   without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.

{-# OPTIONS -fglasgow-exts  -fallow-undecidable-instances  #-}
import Debug.Trace
import Control.Concurrent.MVar
import System.IO.Unsafe
import Control.Exception(evaluate)
import Data.Maybe(catMaybes)
import Control.Monad(when)


import Debug.Trace

debug a b= trace b a
data Axiom a= Axiom String a


data Axioms a= 
 Axioms{unary   :: [Axiom (a -> Bool)]
       ,binary  :: [Axiom ((a,a) -> Bool)]
       ,ternary :: [Axiom ((a,a,a) -> Bool)]

 }

axioms= Axioms [] [] []

type Relations a b = [Axiom ((a,b) -> Bool)]
  
type TermaryRelation a b c = [Axiom ((a,b,c) -> Bool)] 

inTest= unsafePerformIO $ newMVar True  


with= ($)


verify :: Show b => a ->[Axiom (b -> Bool)] -> b -> a
verify res axioms  v = check `seq`res where
 check =unsafePerformIO $  
    do
        int <- tryTakeMVar inTest
        if int == Nothing then return ()
         else do
         errors <- evaluate$  unlines $ catMaybes $ map ( test  v) axioms 
         when (not $ null  errors) ( putTraceMsg errors) 
         putMVar inTest False
         return ()    
   where 
   test v (Axiom n f) = if  f v then  Nothing
                       else  Just $ "violated axiom "++n ++ " with value/s: " ++ show v 
    
    
    
--------------------------- Example for a Ring  -------    

  
class Eq a => Ring a  where
  op1 :: a -> a -> a
  op2 :: a -> a -> a
  zero :: a
  inverse :: a -> a
  
  ringAxioms :: Axioms a
  ringAxioms= axioms{
 
     unary=   [Axiom "identity"          (\x -> zero `op2` x == zero)
              ,Axiom "inverse element"   (\x -> x `op1` (inverse x) == zero)]
                  


     ,binary=  [Axiom "commutative"       (\(x, y) -> x `op1` y == y `op1` x)]
  


     ,ternary= [Axiom "associative `op1`" (\(x,y,z) -> (x `op1` y) `op1` z== x `op1` (y `op1` z))
              ,Axiom "associative `op2`" (\(x,y,z) -> (x `op2` y) `op2` z== x `op2` (y `op2` z))
              ,Axiom "distributive"      (\(x,y,z) -> x `op2` (y `op1` z)== (x `op2` y) `op1` (x `op2` z))
              ,Axiom "distributive2"     (\(x,y,z) -> (x `op1` y) `op2` z== (x `op2` z) `op1` (y `op2` z))
              ]

  }

----------------Define a simple Ring set --------------

instance  Num a  => Ring a where
  op1= (+)
  op2= (*)
  zero = 0
  inverse= negate




data N= N Int deriving ( Eq, Show)





instance Show N => Num N where

  (+) (N x) (N y)= N (x + y)                 `verify`  (binary ringAxioms) `with` ((N x), (N y))

  (-) (N x) (N y)= N (x - y)
  (*) (N x) (N y)= N (x * y)
  negate (N x)= N (-x)
  abs (N x) = N (abs x)
  signum (N x)= N (signum x)
  fromInteger i= N (fromInteger i)






class (Eq a) =>String1 a where
  (+++) :: a -> a -> a
  len :: a -> Int
  
  stringAxioms :: Axioms a
  stringAxioms= 
    axioms {binary=[Axiom "length" (\(x, y)-> (len (x+++y))== ((len x) + (len y)))]}
  
data A= A String deriving Eq

instance String1 A where
  (+++) (A x) (A y)= A (x++y++"hola")
  len (A x)= length x





 

main= do


  let x= N 5

  let y= N 3                                `verify`  (unary ringAxioms) `with` x

  let z= x + y

  print z
  let t= N 7
  print t                                   `verify`  (ternary ringAxioms) `with` (x,y,z)
  let

  print x

New version of the Transactiona Cache (not tested)

2007-11-17T22:26:00.001+01:00

NOTE: last version download at: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/TCache

I created a new version of the Transactional Cache See the original post where I describe the idea. (download this version ). Some interesting additions are:

Default persistence in files (both strict file reads and fail safe reads/writes are needed, because reads and writes can collide).
Direct handling of TVars with full atomic semantic without loosing transparent persistence (getTVars)
No repeated hashtable lookups in case of atomic rollbacks
insertResources
readFileStrict - to be used for instantiate custom persistence in files.
Not only addings but also deletes of objects within single atomic operations. (withResourcesID)

Also, a minimal description of existing primitives has been added.

This is the header:

module TCache ( IResource(..) -- class interface to be instantiated by the user ,DefaultPersistResource(..) --instance of IResource with default definitions, except defkeyResource ,Serializable(..) --instances of DefaultPersistResource must be instances of Serializable as well ,Operation (Insert,Delete) -- data definition used to communicate object Inserts and Deletes to the cache ,Cache -- :: IORef (Ht a,Int, Integer) --The cache definition ,withResourcesID -- :: (IResource a)=> [a]-> --list of resources to be extracted for the user function -- ([Maybe a]->[Operation a]) --user function that get the retrieved resources -- ->IO () --and return a list of objects to be inserted/modified or deleted ,withResources -- :: (IResource a)=> [a] --list of resources to be retrieve -- ->([Maybe a]->[a]) ----function that get the retrieved resources -- ->IO () --and return a list of objects to be inserted/modified ,withResource -- :: (IResource a)=> a --same as withResources , but for one only object -- ->([Maybe a]->a) -- -- ->IO () -- ,insertResources -- :: (IResource a)=> [a] ->IO () -- create resources in the cache. if there are resources with -- the same key, they will be updated. -- getMVars give the transactional variables (TVar´s) to be handled directly by the user. This allows the full -- semantics of "atomic" blocks. Because the TVars are referenced also by the hashtable, the resources inside these TVars -- are saved to disk,transparently for the user, on every sync. Also, they are not deleted from the cache until released. -- getMVars put a high value in the access time an modif. time to avoid the swap process to delete from memory -- getMVars is also useful when the same resources are frequently accessed. This avoid frequent hashtable lookups. ,getTVars -- :: (IResource a)=> [a] -- the list of resources to be retrieved -- -> IO [Maybe (TVar a)] -- The Transactional variables (See Data.TVar documentation) -- releaseMVars allows the release of the resources taken by takeMVars so that them can be swapped to disk if needed. ,releaseTVars -- :: (IResource a)=> [a]-> IO() ,getResources -- :: (IResource a)=>[a] --resources [a] are read from cache and returned -- -> IO [Maybe a] ,getResource -- :: :: (IResource a)=>a --to retrieve one object instead of a list -- -> IO [Maybe a] ,deleteResources -- :: (IResource a)=>[a]-> IO() -- delete the list of resources from cache and from persistent storage ,deleteResource -- :: (IResource a)=>a-> IO() -- delete the resource from cache and from persistent storage --cache handling ,refcache -- :: Cache a --the reference to the cache (see data definition below) ,syncCache -- :: (IResource a) =>Cache a -> IO() --force the atomic write of all the cache objects into permanent storage --useful for termination --start the thread that clean and writes on the persistent storage trough syncCache ,clearSyncCacheProc -- :: (IResource a) =>Cache a --The cache reference -- -> Int --number of seconds betwen checks -- -> (Integer->Integer-> Bool) --The user-defined check-for-cleanup-from-cache for each object --(when True, the object is removed from cache) -- -> Int --The max number of objects in the cache, if more, the cleanup start -- -> >IO ThreadId --Identifier of the thread created -- the default check procedure ,defaultCheck -- :: Integer --last access time for a given object -- ->Integer --last cache syncronization (with the persisten storage) -- ->Bool --return true for all the elems not accesed since --half the time between now and the last sync -- auxiliary ,readFileStrict -- :: String -> IO String -- Strict file read, needed for persistence trough files

Some ideas in progress

2006-12-13T01:31:00.001+01:00

I´m wondering about how the search engine and the transactional cache can be used together in new ways. The transactional cache has only access by unique index, there is no freedom to access objects by arbitrary expressións with boolean conditions and field values a la SQL.

In the other side, the search engine has no relevance and is not enough flexible for some needs. Can I inprove the search engine to provide both functionalities?.

I found that it is possible:

To improve the relevance of the search engine results
Search queries with arbitrary boolean expressions
Query for haskell objects with certain field values.
To use the query language to retrieve sets of haskell registers and perform atomic operations with these registers.

A search engine written in Haskell. Part two

2006-11-24T03:07:00.002+01:00

In
the first post of this Blog , I described what would be the
core or a search engine. Now it´s time to extend it a little more. Up to now,
the search return a list of URI strings (unique keys in the case of database
records, file-names in the case of files on a file-system, URL´s in
the case of Web pages.

But it is meaningless to present this list to the user. An excerpt of
each object, with the paragraphs that contains the keywords searched
for may be something very valuable. At the end, if I take a little
more effort and runtime resources to present something with meaning, it is
probable that the user will not repeat the search many times and browse many
files. This is something that, no doubt, would be far more
costly in every aspect.

So the purpose is to extract an excerpt from the list of URIs returned
by the core search procedure.

showExcerpts:: [String]-> String-> [(String,Int)] showExcerpts xs r= se xs text [] 0 [] where text= show r se:: [String]->String->String->Int->[(String,Int)]->[(String,Int)] se _ [] _ _ fr= fr se qs t@(x:xs) f hasKeys fr \| (not.null) $ filter (==True)$ map ((flip isPrefixOf) t) qs= se qs xs (append f x) (hasKeys+1) fr --some word found \| x `elem` ".,"= -- limit of fragment case hasKeys of 0 -> se qs xs [] 0 fr --the previous fragment was `--void of keys _ -> se qs xs [] 0 ((f,hasKeys):fr) --added the old,` `--new fragment starts \| otherwise= se qs xs (append f x) hasKeys fr append l c= l ++ [c]`

ShowExcerpts take a set of keywords, a Show-able something and return
the paragraphs that contains at least one of the
keywords and the number of keywords found in each paragraphs.

for example, In this test I use text from
Paul
Graham the genius :

main= print $ showExcerpts ["Daddy","model"] text where text= "When people care enough about something to do it well, those who do it best tend to be far better than everyone else. There's a huge gap between Leonardo and second-rate contemporaries like Borgognone. You see the same gap between Raymond Chandler and the average writer of detective novels. A top-ranked professional chess player could play ten thousand games against an ordinary club player without losing once.Like chess or painting or writing novels, making money is a very specialized skill. But for some reason we treat this skill differently. No one complains when a few people surpass all the rest at playing chess or writing novels, but when a few people make more money than the rest, we get editorials saying this is wrong.Why? The pattern of variation seems no different than for any other skill. What causes people to react so strongly when the skill is making money?I think there are three reasons we treat making money as different: the misleading model of wealth we learn as children; the disreputable way in which, till recently, most fortunes were accumulated; and the worry that great variations in income are somehow bad for society. As far as I can tell, the first is mistaken, the second outdated, and the third empirically false. Could it be that, in a modern democracy, variation in income is actually a sign of health?The Daddy Model of WealthBecause kids are unable to create wealth, whatever they have has to be given to them. And when wealth is something you're given, then of course it seems that it should be distributed equally. [2] As in most families it is. The kids see to that. \"Unfair,\" they cry, when one sibling gets more than another.In the real world, you can't keep living off your parents. If you want something, you either have to make it, or do something of equivalent value for someone else, in order to get them to give you enough money to buy it. In the real world, wealth is (except for a few specialists like thieves and speculators) something you have to create, not something that's distributed by Daddy. And since the ability and desire to create it vary from person to person, it's not made equally.It may seem unlikely in principle that one individual could really generate so much more wealth than another. The key to this mystery is to revisit that question, are they really worth 100 of us? Would a basketball team trade one of their players for 100 random people? What would Apple's next product look like if you replaced Steve Jobs with a committee of 100 random people? [6] These things don't scale linearly. Perhaps the CEO or the professional athlete has only ten times (whatever that means) the skill and determination of an ordinary person. But it makes all the difference that it's concentrated in one individual. When we say that one kind of work is overpaid and another underpaid, what are we really saying? In a free market, prices are determined by what buyers want. People like baseball more than poetry, so baseball players make more than poets. To say that a certain kind of work is

the results are:

C:\Documents and Settings\Propietario\Escritorio\haskell>main

[(" Why else would this idea occur in this odd context? Whereas if the
speaker were still operating on the Daddy Model",2),(" The appearance of the
word unjust here is the unmistakable
spectral signature of the Daddy Model",2),(" not something that's distributed
by Daddy",1),(" variation in income is actually a sign of health?The Daddy
Model of Wealth Because kids are unable to create wealth",2)]

Things to note:

The paragraphs are not sorted by relevance, but the relevance is
calculated (the numbers attached to each paragraph).
There is no limit in the number of paragraphs to return

This is by design. It is a task of the consumer to decide either to
sort it, limit the number of paragraphs or whatever. That is so
because this algorithm do it all in one single pass, so that the
lazy nature of Haskell permit getExcerpts stop wasting resources when
the consumer decides that there are enough paragraphs extracted. Great!.

there are many many cases like this in web programming where
laziness pays a lot: HTML Pagination for example. This is something that
happens too in the presentation of search results.

Note that there are hard coded thinks, for example, I take
the dot and the comma as the only separators of paragraphs. By
the way, How the object can be obtained realistically ?. This
is a mook-up. it is certainly not general and hardly reusable.

For that matter I have enhanced
the Type class Indexable for retrieving, convert to
string and give the separators to split the text in words and paragraphs.

class Indexable a where listIze :: a -> [String] getFromURI:: String -> IO a --get the object as s String toString :: a-> String expSeparators :: [Char] wordSeparators:: [Char]

The additions are not orthogonal with listIze, but at
this moment, it is enough

So how looks like the integration of this stuff with the previous search
engine described in
the
first post ?

-- return a list of URIs and excerpts for each document that match the search criteria

searchResults keys= do let xs=listIze $ Words str uris<- search xs rs <- map getFromURI uris return $ zip uris (map (showExcerpts xs) rs)

searchResults is, basically, a map to call showExcerpts
for each URI returned by search.

Again, there is no limit in the number of the results
returned. The lazy nature of Haskell permits me to give to the
consumer total freedom and responsibility,
without complicating the code with clumsy parameters and
buffering.

The caching of document content for extracting excerpts is not the search
engine responsibility up to now. Google do it, so it may
be a good idea to cache the content if possible.
The
transactional cache can be a good candidate for this role.
Specially when the objects indexed are being updated
transactionally and the index engine has to take care of the changes. I´m
working on it.

Haskell Transactional Cache

2006-11-16T17:21:00.001+01:00

NOTE: last version download at: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/TCache

I was impressed by Haskell since I started to learn it a year ago. I was looking for a language that can be used for genetic programming, and haskell eases the creation custom languages such is the one I needed.

Soon I was fascinated by the pure functional approach. I was also attracted by the concept of referential transparency, that makes life easier for code clarity and maintainability. The smart type system also was impressive on avoiding common errors at compilation time that plagued other languages. For these reason and a lot more I though that Haskell has reasonable perspectives to be the future Java. Concerning Web
programming, despite the timid effort done up to now, surprisingly, Haskell is in the best track to win the race for the best Web engine. Haskell Server Pages has a quite good web framework with unique capabilities. HSP Client-side has the best approach for Ajax programming.

But Haskell still has many holes for rapid application development, something that is vital for escalating Haskell from naive, fun driven web projects to industrial acceptance. It lacks a MVC (Model View Controller) framework. Haskell has not something like Rails for Rubi or Hibernate for Java.

One of the problems of Web development is the three tier programming problems. It is about how to keep low the impedance between layers when each layer has his own architectural requirements so that they are designed around different paradigms. With impedance I refer to the additional problems introduced within each layer, at every stage of the software life-cycle, produced by the mismatch with other layers.

Typically, the data layer is constructed around a database and a relational language. The business layer uses a object oriented language, while the presentation layer uses HTML, Javascript and some other web technologies. Depending on the framework chosen, more often than not, the middle layer end with a mess of relational, business and presentation code.

That happens even when the framework explicitly forbid that, unless some
clear configurable interfaces are defined to isolate them. By using the
natural data on each layer and providing mapping mechanisms between
the idiosyncrasies of the respective layers avoids the middle layer
contamination. This keep the impedance low not only at the design
and development time but also in test, integration and
maintenance. Each layer expert can perform his work with little care
about the technologies configurations, design decisions
and changes in the other layers. Such kind of mappings are
exemplified, in the case of the Business-Data layer boundary, by
storage-independent data persistence mechanisms, such is Hibernate
for Java and Rails for Rubi. In the case of the
Business-Presentation Layer boundary, something like the Custom Tags
of JSP and ASP.NET do the same role into isolating the presentation from
the logic of the business layer . They are also mapping mechanisms. XSLT
also play this role.

In the other side, I HATE designing and programming databases (database record
and field access is so low level that it can ruin the readability and elegance
of any algorithm). I want to use my own defined objects, not the pieces
of information defined to accomplish with low level data requirements. I want
not to take care about on every single access to the data I need.

So i need to:

Abstract myself from the physical data structure
and rather use the data definitions that fit with the nature of the
problem to solve
I need Transaction-aware data objects, because in the
multi-threaded world of Internet servers, two clients may want to buy
the same Item at the same time and I want to decrease the stock of this
item two times instead of one, for example (if there are two items
at least).
I also need a way to define mappings between the
objects I use and the physical storage, no matter that it is a
file-system or a Database.
should be abstract to work with any
kind of data definitions.

Once the database is just a persistence mechanism for a web application the
transactionality can not be provided by the database because the updates do
not go directly to the database. The data has to be transactional in memory.
It is very important to have a general mechanism of transactions for this
reason.

I created TCache.hs
(download
), a transactional cache that abstract the user from physical data and
transactional plumbing. The data access uses a very simple semantics: to
access a data object I use just the data
object itself updated with just the fields necessary for composing a
unique key.

The transactional cache takes care of transactions, synchronization
with the physical data ( one way, from the cache to the PD up to
now) and maintenance of the cache size by dropping the data with
older access.

The transaction uses STM (Software Transactional Memory) so that no
blocking is used, and the resulting application is faster at doing
transactions. For this reason it only compiles in GHC.

The cache is implemented in a Hash Table
(Data.HashTable) so that many thread may be doing
transactions at the same time.

Below you can find an example of use:

module Main where ------------------------------------------------- -- A example of Transactional cache usage (TCache.hs) -- (Something like the Java Hibernate) -- Author: Alberto Gómez Corona Nov 2006 -- Language: Haskell -- Terms of use: you can do whatever you want -- with this code as long as you keep this notice ------------------------------------------------ import TCache import Control.Concurrent import System.Directory

--1 and 4: The data elements to be used in the example: A user will repeatedly buy Items. data Data=   User{uname::String, uid::String, spent:: Int} |               Item{iname::String, iid::String, price::Int, stock::Int}               deriving (Read, Show) --3 The mappings between the cache and the phisical storage are defined by the interface IResource

--      to extract the resource unique key,

--      to read the resource from the physical storage,

--      to store it and

--      to delete the resource from the physical storage.

instance IResource Data where         keyResource         User{uid=id}= id         keyResource         Item{iid=id}= id                readResource    e= do s<- readFile$ keyResource e                               return$ Just $ read s                                           writeResource   e= writeFile (keyResource e) $ show e         delResource     e= removeFile $ keyResource e -- buy is the operation to be performed in the example

--4 withResources gets a partial definition of each resource necessary for extracting the key, fill all the rest of the data structures (if found ) and return a list of Maybe Data. BuyIt is part of the domain problem. it receive this list and generates a new list of dat objects that are updated in the cache. buyIt is executed atomically.

user `buy` item=     withResources[user,item] buyIt where     buyIt[Just us,Just it]        | stock it > 0= [us',it'] `debug1` "john buy a PC"        | otherwise   = error "stock is empty for this product"     buyIt[_,_] = error "either the user or the item does not exist"     us'= us{spent=spent us + price it}     it'= it{stock= stock it-1} main= do         -- create resources (acces no resources and return two new Data objects defined in items)         withResources[]items         --11 PCs are charged to the John´s account in paralel, to show transactionality         --because there are only 10 PCs in stock, the last thread must return an error         for 11 $ forkIO $ User{uid="U12345"} `buy` Item{iid="I54321"}                 --wait 5 seconds                 threadDelay 5000000         -- write the cache content in a persistent store (invoque writeResource for each resource)         -- in a real application clearSyncCache can be used instead to adjust size and write the cache periodically         syncCache (refcache :: Cache Data)         -- the files have been created. the files U12345 and I54321 must contain the result of the 11 iterations   where         items _=               [User "John" "U12345" 0               ,Item "PC" "I54321" 6000 10]

Here follows is a typical output. I printed a trace with the text atomic try as the first statement of the atomic transaction. You can se how the first transaction initiated blocks the rest and even some retry. That is so because all the updates go to the same registers. Overall, STM is faster than blocking and far easier. My first version used blocking and the code were far more complicated.

"atomic try"
"atomic try"
john buy a PC
"atomic try""atomic try""atomic try""atomic try""atomic try""atomic try""atomic
try""atomic try""atomic try""atomic try"
john buy a PC

john buy a PC

john buy a PC

john buy a PC
john buy a PC

john buy a PC
john buy a PC

john buy a PC

john buy a PC
john buy a PC
"atomic try""atomic try"
john buy a PC

john buy a PC
"atomic try"
john buy a PC"atomic try"
main: stock is empty for this product

The final content of the files are:

U12345: User {uname = "John", uid = "U12345", spent = 60000}

I54321: Item {iname = "PC", iid = "I54321", price = 6000, stock = 0}

The amount spent by John is the sum of th prices of the ten PCs in stock and the stock is 0, so the transactions have been managed correcly.

There are other operations; getResources that simply return the data requested withour doing any transaction. clearSyncCacheProc start the process for cache maintenance and syncronization according with his passed parameters: time between checks, cache size and filtering criteria. getResourcesID permits not only update but also delete cache elements in the course of a transaction.

The module is far from finised. The syncronization mechanism must be refined for example with cache invalidation machanisms. I welcome anyone interested in to improve it.

NOTES:

I just realized that my transactional cache has been used in this excelent paper: Dissecting Transactional Executions in Haskell.

The test case used in the study is more or less the same example described above. Since all the parallel treads update the same two objects all the time, this is the worst case. TCache uses in-memory non blocking transactions . Each transaction do not block, but instead he try to perform the task and rollback at the very end if things have been changed by other thread in the meantime. Just like databases. The bad thing is that the more CPU cores are executing the example, the more work being rolled back is done.

Fortunately this is not the case in real life. TCache and the STM transactions are designed with the assumption that the application manages many objects and the threads update simultaneously different objects most of the time. A user does not buy eleven times simultaneously the same product. And non blocking transactions scale better than blocking ones in real life scenarios, just because they don´t block.

A search engine written in Haskell

2006-11-14T17:30:00.000+01:00

It is so easy to transform ideas into programs using Haskell.

I was bored in a conference. The conferences excite my
imagination in the same way than walking fast. I started to
think about how the core of a search engine would look like. I also need one
for my portal
http://www.FreeChooser.com (more on
this portal coming soon). I needed to index not only web pages, but also
Haskell data records.

My search engine needed a compact index database, well designed so that
the the search should be fast, even when searching for many words at the
same time, it would return a short set of documents that contains all the
words requested. This is the way to achieve a compromise between simplicity,
speed, ease of use and resource waste. I didn't realize that the core
idea could have been achieved in less than 50 lines of Haskell code!!!

I heard time ago about a search engine
www.alltheweb.com that
used bit maps to achieve the fastest search results six years ago.

During the conference, I figured out a way to use bitmaps. For each word, the
index must store a set of bits. each bit correspond to a document identified
by the position in the bitmap (an Inte(ger)) and the association of this
Int(eger) with the URL of the document. the bit will have a 1 when the
document has this word and 0 when not. Very simple.

To search for the documents that contain term1 AND term2 ... AND
TermN is just a bitwise AND of the respective bitmap terms.

So I started to code it as soon as I returned home. Here is the code:

Module Search where ------------------------------------------------- -- The Core of a Search Engine -- Author: Alberto Gómez Corona -- Language: Haskell -- Terms of use: you can do whatever you want -- with this code as long as you keep this notice ------------------------------------------------

--store the URI list of indexed objects (reverse to intKey) keyInt= unsafePerformIO $ new (==) hashString :: HashTable String Int --store the bitmaps for each word hs= unsafePerformIO $ new (==) hashString :: HashTable String Integer --store the URN for each bit position intKey= unsafePerformIO $ new (==) hashInt:: HashTable Int String --store the last bit position/las int id of the last object indexed indexRef =unsafePerformIO $ newMVar 0 :: MVar Int -- add the content of an object, identified by the uri string: addObject:: (Indexable a)=> String->a->IO() addObject uri content= do mk<- HT.lookup keyInt uri case mk of Just k -> return () --to avoid repeated indexing of documents Nothing-> addObject1 uri content where addObject1 uri content=do n <- takeMVar indexRef add n (k n) $ listIze content update keyInt uri n update intKey n uri putMVar indexRef (n+1) where add n k []= return () add n k (x:xs)= do mv<- HT.lookup hs x case mv of Just v -> update hs x (v .|. k) Nothing-> update hs x k add n k xs k n= shiftL 1 n -- search for a set of ANDed keywords and return the list of URIs That contain all of them search xs = do n <- readMVar indexRef print n mbi<- mapM (HT.lookup hs)xs let bi = catMaybes mbi -- if a word has not been found then return empty results if length bi/= length mbi then return [] else do let r= foldr (.&.) (head bi) bi -- select te doc bits that have all the words --r has the bits of the objects that match print r getObjecURIs n 0 r [] where getObjecURIs :: Int->Int->Integer->[String]->IO [String] getObjecURIs 0 _ _ rs= return rs getObjecURIs n i r rs= case (testBit r 0) of True -> do urn <- HT.lookup intKey i getObjecURIs (n-1)(i+1) (shiftR r 1) (fromJust urn:rs) False-> getObjecURIs (n-1)(i+1) (shiftR r 1) rs

Of course, it is necessary to add persistence for the index database
hs and the rest of the associated HashTables and so on.

There are two procedures
addObject
(to add a new object URI and his string content) to the index
database. The other method is Search.
It takes a list of words as arguments and return the list of documents
that have all the words.

To feed addObject, I also started to define filters for
special kind of objects: (text files, Haskell registers, XML/HTML files).
The code below shows an early attemp to do so. Note the type signature of
adObject.

I have defined a Class Indexable that has a function that convert
the object into a list of strings:

--a is indexable if it can be serialized into a list of word strings class Indexable a where listIze:: a->[String] data Words= Words String instance Indexable Words where listIze (Words s)= str2List s (\c ->isAlphaNum c || c=='@') where str2List [] _ = [] str2List s f = h:r where (h,t) = myreads2 s f r = str2List t f myreads2 [] _=([],[]) myreads2 (c:rest) f | not(f c) = ([], rest) | otherwise = (c:r, skipspaces s f) where (r,s) = myreads2 rest f skipspaces [] _ = [] skipspaces (c:rest) f | not(f c) = skipspaces rest f | otherwise = c:rest data XMLText= XMLText String instance Indexable XMLText where listIze (XMLText s)= str2List s (\c ->isAlphaNum c || c=='@') where str2List "" _ = [] str2List ('<':rs) f = str2List (tail $ dropWhile(/='>') rs) f str2List s f = h:r where (h,t) = myreads2 s f r = str2List t f myreads2 [] _=([],[]) myreads2 (c:rest) f | not(f c) = ([], rest) | otherwise = (c:r, skipspaces s f) where (r,s) = myreads2 rest f skipspaces [] _ = [] skipspaces ('<':rs) f = skipspaces (tail $ dropWhile(/='>') rs) f skipspaces (c:rest) f | not(f c) = skipspaces rest f | otherwise = c:rest data Idx a= Idx a instance Show a => Indexable (Idx a) where listIze a = listIze $ Words $ show a instance Show a=> Show(Idx a) where show (Idx a)= show a

With this quick and dirty filter definitions for Text, XML/HTML and
Haskell registers, we can do this:

data Register=Reg String Integer deriving Show main=do addObject "input1.txt" $ Words "John, 18" addObject "input2.html" $ XMLText "<html><body><p>John</p><body>18</body></html>" addObject "HaskelReg.hs" $ Idx $ Reg "John" 18 r<- search ["John","18"] print r

The source of Search.hs can be found
here

See
part
2 of the search engine