unix.select + camlp4

unix.select + camlp4

[Anastasia Gornostaeva]

Hello.

Is it possible to use camlp4-based parser with data which comes from
Unix.select input? Read a line, parse it, if a line was incomplete to parse
then save a state, continue.... How do to do it?

ermine

Re: [Caml-list] unix.select + camlp4

[Jon Harrop]

On Sunday 01 July 2007 21:30:44 Anastasia Gornostaeva wrote:
> Is it possible to use camlp4-based parser with data which comes from
> Unix.select input? Read a line, parse it, if a line was incomplete to parse
> then save a state, continue.... How do to do it?

Bruno gave an excellent example of parsing strings using camlp4, posted on 
22/06/2007:

# open Camlp4.PreCast ;;
# let expr = Gram.Entry.mk "expr" ;;
val expr : '_a Camlp4.PreCast.Gram.Entry.t = <abstr>
# EXTEND Gram
     expr:
       [ "add" LEFTA
         [ e1 = expr; "+"; e2 = expr -> e1 +: e2
         | e1 = expr; "-"; e2 = expr -> e1 -: e2 ]
       | "mult" LEFTA
         [ e1 = expr; "*"; e2 = expr -> e1 *: e2 ]
       | "simple" NONA
         [ n = INT -> Num(int_of_string n)
         | "("; e = expr; ")" -> e ] ]
       ;
   END ;;
- : unit = ()
# Gram.parse expr Loc.ghost (Stream.of_string "1-2+3*4") ;;
- : expr = Add (Sub (Num 1, Num 2), Mult (Num 3, Num 4))

If you can read a line from Unix.select then you should be able to feed it 
into this.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e

Re: [Caml-list] unix.select + camlp4

[Anastasia Gornostaeva]

On Sun, Jul 01, 2007 at 09:37:46PM +0100, Jon Harrop wrote:

> > Is it possible to use camlp4-based parser with data which comes from
> > Unix.select input? Read a line, parse it, if a line was incomplete to parse
> > then save a state, continue.... How do to do it?
> 
> Bruno gave an excellent example of parsing strings using camlp4, posted on 
> 22/06/2007:
> 
> # open Camlp4.PreCast ;;
> # let expr = Gram.Entry.mk "expr" ;;
> val expr : '_a Camlp4.PreCast.Gram.Entry.t = <abstr>
> # EXTEND Gram
>      expr:
>        [ "add" LEFTA
>          [ e1 = expr; "+"; e2 = expr -> e1 +: e2
>          | e1 = expr; "-"; e2 = expr -> e1 -: e2 ]
>        | "mult" LEFTA
>          [ e1 = expr; "*"; e2 = expr -> e1 *: e2 ]
>        | "simple" NONA
>          [ n = INT -> Num(int_of_string n)
>          | "("; e = expr; ")" -> e ] ]
>        ;
>    END ;;
> - : unit = ()
> # Gram.parse expr Loc.ghost (Stream.of_string "1-2+3*4") ;;
> - : expr = Add (Sub (Num 1, Num 2), Mult (Num 3, Num 4))
> 
> If you can read a line from Unix.select then you should be able to feed it 
> into this.

I dont understand: Try:
1) It receives "1-2+3*" and parses it. 
2) Later it receives "4" and continues parsing.

I want to get non-blocking parser. How to implement?

ermine

Re: [Caml-list] unix.select + camlp4

[skaller]

On Mon, 2007-07-02 at 01:01 +0400, Anastasia Gornostaeva wrote:
> On Sun, Jul 01, 2007 at 09:37:46PM +0100, Jon Harrop wrote:

> I dont understand: Try:
> 1) It receives "1-2+3*" and parses it. 
> 2) Later it receives "4" and continues parsing.
> 
> I want to get non-blocking parser. How to implement?

Put the parser in a thread, select in another thread.
Use Stream.from f for the parser. Write f to get characters
using the Event module, send the characters from the other thread
after select makes a channel active.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Phd position at LACL, University of Paris 12

[Frédéric Gava]

Dear Caml-list,

sorry for the noise, here the subject in plain text:

Frédéric Gava



Doctoral research project:
Parallel verification of a high-level Petri net algebra
=======================================================

Keywords: verification, modularity, high-level parallelism, Petri nets

I. Host laboratory, funding and contacts
----------------------------------------

Funding: Paris regional doctoral scholarship, value of approximately
1570 Euros/month for a duration of 3 years.

Laboratory: Laboratory for Algorithmics, Complexity and Logic (LACL),
University Paris-12
  a. Director: Pr Gaëtan Hains
  b. Email: gaetan@hains.org
  c. Team: ``communicating systems'' directed by Pr Elisabeth Pelz
  d. Postal address: LACL, Université Paris XII--Val de Marne,
                     UFR de Sciences et Technologie, Bâtiment P2, 2ème étage
                     61 avenue du Général de Gaulle, 94010 Créteil
  e. Phone: +33 (0)1 45 17 65 95
  f. Fax: +33 (0)1 45 17 66 01
  g. Web site: http://www.univ-paris12.fr/lacl/

Doctoral advisor: Pr Gaëtan Hains

Co-advisors:
  - Dr Frédéric Gava (coordinator of the VEHICULAR project)
     a. Position: Assistant Professor at LACL
     b. Phone : +33 (0)1 45 17 65 67
     c. Email: gava@univ-paris12.fr
     d. Web page: http://www.univ-paris12.fr/lacl/gava/
  - Dr Franck Pommereau
     a. Position: Assistant Professor at LACL
     b. Phone: +33 (0)1 45 17 66 00
     c. Email: pommereau@univ-paris12.fr
     d. Web page: http://www.univ-paris12.fr/lacl/pommereau/

Application: Send a CV and cover letter to the one of the
above-mentioned advisors (in PDF format preferably).

II. Doctoral research subject
-----------------------------

   The automatic verification of models (also called model-checking
[13] ) is a useful technique for automatic software verification, but
it is generally expensive in terms of memory capacity and computing
time (one speaks of its ``state-space explosion problem''). Many works
in this field have dealt with the acceleration of computation and
reduction of the space exploration. Parallelization is one of the
possible techniques to this end. However, it is in generally
implemented with low-level models (both for its specification as
model-checker and as parallel program [5] [8] [11] ) and with a more
or less naive data distribution (such as for example
http://quasar.cnam.fr/).

   The proposed work is first of all the design of a BSP [15] [16]
parallel algorithm for the construction of the exploration of the
state-space of a high-level coloured Petri net algebra, called M-Net
[7] (or of a clearly definite subset [3] [17] ) as well as a parallel
checking of logical properties on this graph (some logics like LTL
[13] or others are often very expressive but an expressive and
effectively verifiable subset will be necessary). The use of such a
strongly structured model will enable us to determine some structural
characteristics opening the way of a high-level parallelism (more
structured) and thus more efficient (and portable) which is the BSP
model.

   Then, a modular and polymorphic implementation (data type
independent, therefore ideal for the model-cheking of symbolic system
[2] and for a high-level algebra) will be carried out with a library
for high-level parallel programming, called BSMLlib [9] BSMLlib is
based on the OCaml (http://caml.inria.fr) language [14] and wad
developed jointly by LACL and LIFO (Computer Science laboratory of the
University of Orleans). Optimizations to the algorithm will be made in
particular with the extension of techniques of load-balancing based on
BSP costs [1] or on the structure of the logical formulae with respect
to the model [12] .

   Finally, tests of our software applied to computer security problems
(federating topic for LACL research) and to properties of high
performance programs (C, Ada or FORTRAN with a parallel computation
library such as MPI or with algorithmic skeletons) will be carried out
on the various PC's clusters at LACL and LIFO. (An algorithmic
skeleton is a function which can be implemented in parallel: each kind
of parallelism, divide-and-conquer, pipeline, task farming, etc., is
realised by a skeleton; this makes possible the easy and safe
parallelisation of programs, by using suitable skeletons that closely
reflect the parallelism intrinsic in the computational problem [4].)
Adaptations and additions will thereafter (or progressively) be added
to model and check logical properties of computer science's or
biological problems [18] which will be encountered in the literature.

   More details (in French) on the VEHICULAR project can be found at:
    http://www.univ-paris12.fr/lacl/gava/vehiculaire/vehiculaire.pdf

III. Bibliography
-----------------

[1] M. Bamha and G. Hains. An Efficient equi-semi-join Algorithm for
       Distributed Architectures. In V. S. Sunderam, G. Dick van
       Albada, P. M. A. Sloot, and J. Dongarra, editors, International
       Conference on Computational Science (ICCS 2005), Part II, number
       3515 in LNCS, Springer-Verlag, 2005.
[2] B. Boigelot. Symbolic Methods for Exploring Infinite State Spaces.
       PhD Thesis, volume 189, Collection des Publications de la
       Faculté des Sciences Appliquées de l'Université de
       Liège, 1999.
[3] R. Bouroulet, H. Klaudel, and E. Pelz. A semantics of security
       protocol language using a class of composable high-level petri
       nets. In Application of Concurrency to System Design, volume 4th
       ACSD, pages 99-108. IIIE, 2004.
[4] Jan Duennweber, Sergei Gorlatch, Anne Benoit and Murray Cole
       Integrating MPI-Skeletons with Web Service in Proceedings of
       ParCo 2005.
[5] H. Garavel, R. Mateescu, C. Joubert and al. DISTRIBUTOR and
       BCG_MERGE: Tools for Distributed Explicit State Space
       Generation, March 2006.
[6] G. Gardey, O. H. Roux and O. F. Roux. State space computation and
       analysis of time Petri nets. Theory and Practice of Logic
       Programming (TPLP). Special Issue on Specification Analysis and
       Verification of Reactive Systems, 2005.
[7] Hanna Klaudel and Franck Pommereau. M-nets, a survey. Acta
       Informatica, To appear.
[8] L. Kristensen and L. Petrucci. An approach to distributed state
       space exploration for coloured Petri nets. ICATPN'2004, LNCS
       3099. Springer, 2004
[9] F. Loulergue, F. Gava, and D. Billiet. Bulk Synchronous Parallel
       ML: Modular Implementation and Performance Prediction. In,
       International Conference on Computational Science (ICCS 2005),
       Part II, number 3515 in LNCS, pages 1046-1054. Springer, 2005.
[10] M. Mäkelä. Modular reachability analyzer for high-level
       Petri nets. 5th Workshop on Discrete Event Systems. Kluwer
       Academic Publishers, 2000.
[11] D.Petcu, Parallel explicit-state reachability analysis and state
       space construction, Proceedings of Second International
       Symposium on Parallel and Distributed Computing, ISPDC 2003,
       13-14 October 2003, Ljubljana, IEEE Computer Society Press, Los
       Alamitos
[12] J.-M. Couvreur and D. Poitrenaud. Dépliage pour la
       vérification de propriétés temporelles. In
       Vérification et mise en oeuvre des réseaux de Petri - Tome
       2, chapter 3, pages 127-161. Hermès, 2003.
[13] Model Checking, Edmund M. Clarke, Jr., Orna Grumberg and Doron A.
       Peled, MIT Press, 1999
[14] D. Rémy. Using, Understanding, and Unravellling the OCaml
       Language. In G. Barthe, P. Dyjber, L. Pinto, and J. Saraiva,
       editors, Applied Semantics, number 2395 in LNCS, pages 413-536.
       Springer, 2002.
[15] R. Bisseling, Parallel Scientific Computation. A Structured
       approach using BSP and MPI, Oxford University Presse, 2004.
[16] D. B. Skillicorn, J. M. D. Hill, and W. F. McColl. Questions and
       answers about BSP. Scientific Programming, 6(3): 249-274
[17] Franck Pommereau Versatile Boxes: a Multi-Purpose Algebra of
       High-Level Petri net Proc. of DASD'07, SCS/ACM, 2007
[18] C. Chaouiya. Petri net modelling of biological networks.
       Briefings in Bioinformatics. To appear.

Re: [Caml-list] unix.select + camlp4

[Anastasia Gornostaeva]

On Mon, Jul 02, 2007 at 12:10:34PM +1000, skaller wrote:
> On Mon, 2007-07-02 at 01:01 +0400, Anastasia Gornostaeva wrote:
> > On Sun, Jul 01, 2007 at 09:37:46PM +0100, Jon Harrop wrote:
> 
> > I dont understand: Try:
> > 1) It receives "1-2+3*" and parses it. 
> > 2) Later it receives "4" and continues parsing.
> > 
> > I want to get non-blocking parser. How to implement?
> 
> Put the parser in a thread, select in another thread.
> Use Stream.from f for the parser. Write f to get characters
> using the Event module, send the characters from the other thread
> after select makes a channel active.

It looks awful if you want to run houndreds streams/connections.
It is easier to run a connection with a parser in separate thread.
So, camlp4 cannot be nonblocking parser.. bad.

ermine

Re: [Caml-list] unix.select + camlp4

[skaller]

On Mon, 2007-07-02 at 19:39 +0400, Anastasia Gornostaeva wrote:
> On Mon, Jul 02, 2007 at 12:10:34PM +1000, skaller wrote:
> > On Mon, 2007-07-02 at 01:01 +0400, Anastasia Gornostaeva wrote:
> > > On Sun, Jul 01, 2007 at 09:37:46PM +0100, Jon Harrop wrote:
> > 
> > > I dont understand: Try:
> > > 1) It receives "1-2+3*" and parses it. 
> > > 2) Later it receives "4" and continues parsing.
> > > 
> > > I want to get non-blocking parser. How to implement?
> > 
> > Put the parser in a thread, select in another thread.
> > Use Stream.from f for the parser. Write f to get characters
> > using the Event module, send the characters from the other thread
> > after select makes a channel active.
> 
> It looks awful if you want to run houndreds streams/connections.
> It is easier to run a connection with a parser in separate thread.
> So, camlp4 cannot be nonblocking parser.. bad.

This problem is not restricted to parsers .. it's a general
problem with Ocaml and also C, C++, and most other languages.

My language Felix solves this problem for procedures with
user space threading .. but it doesn't work with functions.
[And the builtin GLR parser is purely functional:]

Other languages like Scheme and I think Haskell and MLton
have more general solutions because they're not restricted
to the archaic concept of a linear stack.

You can certainly write code using continuation passing style
to work around this deficiency in most languages, but you
can't work around someone else's code that doesn't use this
style.

The general model of using 'threads' is the only solution,
however OS threads are too general and too slow for large
numbers, and they're needlessly asynchronous when all you
often want is control inversion (though in your case,
you're using 'select' so you do want asynchronicity).

JoCaml is worth looking at for another approach.. but the
bottom line is if you're using the usual parser products
around, the only way to control invert the 'get_token'
callback is by using a pair of threads implementing
a client/server model, and allowing the OS to control
invert the threads by stack swapping.


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net