Previous week Up Next week

Hello

Here is the latest Caml Weekly News, for the week of October 09 to 16, 2007.

  1. Data structure for a directed bipartite graph
  2. ocamljs 0.1, OCaml to Javascript compiler
  3. Adding new architecture to ocamlopt
  4. OCamlScripting project
  5. Microsoft Research Cambridge Lab Vacancy - Research Software Development Engineer
  6. Some commercial software written in OCaml
  7. SDFlow: combinatorial dataflow programming library

Data structure for a directed bipartite graph

Archive: http://groups.google.com/group/fa.caml/browse_frm/thread/3f3e198522f65c15/e68d8e75270f1c75#e68d8e75270f1c75

Orlin Grigorov asked and Jean-Christophe Filliatre answered:
> A bipartite graph is a graph, which has two kinds of nodes, and every node 
> is connected only to nodes from the other kind.  In other words, if the two 
> types of nodes are A and B, then there can be an edge between nodes of type 
> A to nodes of type B (resp. edge from B to A), but never an edge between A 
> and A, or B and B. 
> 
> So, I was thinking about a data structure in OCaml, in which I want to store 
> such graph, and also to allow me easy access to elements, as well as adding 
> new nodes and edges (therefore, the structure would be imperative, that is, 
> will have a state).

As already mentionned by somebody else, there exists at least one 
graph library for ocaml at http://ocamlgraph.lri.fr/ 

It provides several data structures for graph, including matrix 
representations as the one you are mentioning, but also others more 
suitable for sparse graphs. 

Note that the ability to add new nodes and new edges does not enforce 
the use of an imperative data structure. A persistent one is equally 
fine; you simply get a new graph when you add a node or an edge, the 
previous one being unchanged (with a logarithmic time and space 
overhead, typically). 

Ocamlgraph makes heavy use of ocaml module system to provide great 
genericity and thus may appear as somewhat heavy for a newcomer. You 
should start by having a look at module Pack, which provides an easy 
access to the library (imperative data structure with nodes and edges 
labeled with integers; see http://ocamlgraph.lri.fr/doc/Pack.html 

Regarding the ability to attach information to nodes (or edges) you 
may indeed use an additional data structure for that purpose (a hash 
table, typically) but you may also use ocamlgraph to define your own 
graph data structure with any kind of information associated to nodes 
and edges. That is precisely why ocamlgraph was designed in a highly 
generic way. See ocamlgraph's FAQ for an example of such instantiation. 

Note that Ocamlgraph's documentation includes an article "Designing a 
Generic Graph Library using ML Functors" which can be seen as an 
introduction to ocamlgraph's design.
			

ocamljs 0.1, OCaml to Javascript compiler

Archive: http://groups.google.com/group/fa.caml/browse_frm/thread/c6d7c3b639f400fb/04ab54767c62ac93#04ab54767c62ac93

Jake Donham announced:
We are pleased to announce a preliminary version of ocamljs, a back-end 
to ocamlc that produces Javascript. It needs a lot of work still, but we 
are using it for production work at Skydeck. We hope that you will find 
it useful. More at:

  http://skydeck.com/blog/programming/ocamljs-ocaml-to-javascript-compiler/
			

Adding new architecture to ocamlopt

Archive: http://groups.google.com/group/fa.caml/browse_frm/thread/ba3e102af7816c2d/bd6a793c35299d6c#bd6a793c35299d6c

Christoph Sieghart asked and Gordon Henriksen answered:
> Is there any documentation for adding a new architecture to   
> ocamlopt? I would like to do a crosscompiler from one of the   
> existing architectures to an embedded microcontroller. 
>
> I have searched the mailinglist archives and the documenation, but   
> have not found anything. Any pointers are welcome? Is my assumption   
> that the major codegeneration work is done by the code in $caml/ 
> asmcomp? 

Christoph, 

Yes, asmcomp contains both the middle-end and the back-end code   
generators. Note that the architecture-specific features are injected   
by configure creating various symlinks of the form asmcomp/<foo>.ml - 
 > asmcomp/<arch>/<foo>.ml. On one hand, this means you should be   
able to clone the contents of one of the asmcomp/<arch>   
subdirectories and get your project off to a start pretty quickly. On   
the other, ocamlopt is not a cross-compiler, so you may have a bit of   
a challenge just getting the paths to the cross tools into the right   
places without breaking ocamlc. 

I'm sure you'll get more detailed pointers, but here's a quick   
overview... 

ocamlc and ocamlopt share code through the "Lambda" representation   
(bytecomp/lambda.mli). After this point, ocamlopt transfers control   
into asmcomp/asmgen.ml, which has a fairly straightforward pass   
pipeline in Asmgen.compile_implementation. 

The Lambda representation is first translated into Closed Lambda   
(asmcomp/clambda.mli), which is similar except that closures are   
explicit. 

Next, ocamlopt transforms Clambda into its middle-end representation,   
C--. This form is somewhat well documented at http://cminusminus.org/   
and in various academic papers. The C-- representation is   
architecture-neutral in form, but not content. Target dependencies   
are injected through the Arch module, which specifies address sizes,   
endianness, etc. This is the point where displacement calculations   
are performed, etc. 

The C-- representation is the input to the architecture-specific back- 
end code generators, which are driven by the architecture-neutral   
Asmgen.compile_phrase and Asmgen.compile_fundecl. In particular, this   
pipeline is pleasantly self-documenting: 

let (++) x f = f x 

let compile_fundecl (ppf : formatter) fd_cmm = 
   Reg.reset(); 
   fd_cmm (* <-- The C-- representation for the function *) 
   ++ Selection.fundecl 
   ++ pass_dump_if ppf dump_selection "After instruction selection" 
   ++ Comballoc.fundecl 
   ++ pass_dump_if ppf dump_combine "After allocation combining" 
   ++ liveness ppf 
   ++ pass_dump_if ppf dump_live "Liveness analysis" 
   ++ Spill.fundecl 
   ++ liveness ppf 
   ++ pass_dump_if ppf dump_spill "After spilling" 
   ++ Split.fundecl 
   ++ pass_dump_if ppf dump_split "After live range splitting" 
   ++ liveness ppf 
   ++ regalloc ppf 1 
   ++ Linearize.fundecl 
   ++ pass_dump_linear_if ppf dump_linear "Linearized code" 
   ++ Scheduling.fundecl 
   ++ pass_dump_linear_if ppf dump_scheduling "After instruction   
scheduling" 
   ++ Emit.fundecl 

You can identify the target-dependent phases by correlating the   
passes with the contents of a target subdirectory.  Have fun!
			

OCamlScripting project

Archive: http://groups.google.com/group/fa.caml/browse_frm/thread/7b4e4da1ef4cc765/ff72f770fab280a1#ff72f770fab280a1

Xavier Clerc announced:
This post announces the first public release of the OCamlScripting   
project. 
OCamlScripting is a scripting engine for Java (javax.script package). 
OCamlScripting is released under the LGPL v3. 
OCamlScripting is part of the ocamljava project (http://ocamljava.x9c.fr). 

Home page: http://ocamlscripting.x9c.fr 

Features: 
   - runs Objective Caml scripts in a Java application 
   - supports bindings 
   - supports script compilation 

Requirements: 
   - Objective Caml 3.10.0 or higher 
   - Cadmium 1.0 
   - Cafesterol 1.0 
   - Java 1.5 with script-api.jar or Java 1.6
			

Microsoft Research Cambridge Lab Vacancy - Research Software Development Engineer

Archive: http://groups.google.com/group/fa.caml/browse_frm/thread/9be6d32eb82bf5b7/8a53caf0db2c77ac#8a53caf0db2c77ac

Don Syme announced:
Job Title: Research Software Development Engineer (RSDE) 
Group: Terminator and SLAyer team / Programming Principles and Tools 
Location: Microsoft Research, Cambridge (UK) 
Start date: Flexible 

Description: 
SLAyer is a software analysis tool that automatically proves properties about 
the data-structures constructed/modified by concurrent systems-level code.  
Terminator is an additional componenet designed to prove termination and 
liveness properties.  The joint SLAyer/Terminator team is looking for a 
developer interested in building the first production version of these tools. 
This position is in Microsoft's Research division. It will involve a close 
partnership with Windows Static Driver Verifier team in Redmond, WA. 

This position will include: 
* Developing the internal components within Terminator and SLAyer 
* Integrating Terminator and SLAyer with the Static Driver Verifier product 
* Developing additional infrastructure for future program verification tools 

For more information about Terminator and SLAyer see: 
* http://research.microsoft.com/TERMINATOR 
* http://research.microsoft.com/SLAyer 

Candidates should have the following technical qualifications: 
* MS. or Ph.D. in Computer Science 
* 2+ years development experience highly desirable (e.g. experience shipping 
software) 
* Knowledge of algorithms and techniques of program analysis is necessary, at 
least, from one of the two angles: formal verification or compiler design. It 
is expected to be based on college education or 2+ years of industrial 
experience. 
* Experience with ML-like programming language (F#, OCaml) is highly desirable 
* Knowledge of and experience with OS internals or driver development is a 
plus 
* Good communication and inter-personal skills 
* Leadership abilities and cross-team collaboration skills 

To apply or request further details, please contact our Human Resources 
Department by email: cambhr@microsoft.com

Closing date for applications is Friday, 30 November 2007. 
Microsoft Research is an equal opportunities employer
			

Some commercial software written in OCaml

Archive: http://groups.google.com/group/fa.caml/browse_frm/thread/aa77eeb50c5e3664/d515fb97b23e2bb6#d515fb97b23e2bb6

John Whitington announced:
Commercial software written in OCaml being somewhat rare, I hope you'll 
forgive this advertisement. 

I've released some command line tools for manipulating PDF files, based 
on the open-source library CamlPDF, which I announced here some time   
ago. 

Demo and Manual at http://www.coherentpdf.com/ 

A new version of CamlPDF will be released soon, reflecting the updated 
facilities used  by the commercial tools.
			

SDFlow: combinatorial dataflow programming library

Archive: http://groups.google.com/group/fa.caml/browse_frm/thread/101aba9d659bd3e2/41aa74c3a3d9ecb9#41aa74c3a3d9ecb9

Zheng Li announced:
The recent discussion [1] reminds me of some previous exploration on related 
topics. By making some clean up to the old code, I'd like to announce the 
availability of SDFlow, a small library for high-level combinatorial dataflow 
programming in OCaml. 

The library is licensed under LGPL+linking exception. You can get everything 
related at http://www.pps.jussieu.fr/~li/software/index.html#sdflow 

Note that the code is still experimental, and poorly documented for the 
moment. 

[1] http://groups.google.com/group/fa.caml/browse_frm/thread/e4a5674c28233a0b/012d1433d5053ce1?lnk=raot#012d1433d5053ce1

The following part is extracted from README: 

---------------------------------------------------------------------------

== Description == 

SDFlow stands for Structured Data Flow. It's a high-level combinatorial 
dataflow programming library based upon destructive(*) lazy streams. Its base 
type is compatible with stream of standard OCaml. 

== Introduction == 

Besides the only kind of practical applications we have in mind --- to help 
constructing alternative dataflow interfaces for other libraries, the main 
functionality of the library is just "for fun". You can experience the 
following programming paradigms with SDFlow in plain OCaml: 

  * combinatorial dataflow programming 
  * programming with lazy sequence 
  * deterministic non-strict evaluation 
  * pointfree programming (or one-liner programming) 

Primitives provided: 

  * conversion: 
      of_fun, of_list, of_string, of_channel 
      to_fun, to_list, to_string, to_channel 
  * flow creation: 
      seq, enum, repeat, cycle, (--) 
  * flow consuming: 
      peek, next, iter, foldl/foldr/fold 
  * flow arithmetic: 
      cons, apnd, is_empty, filter, concat, 
      take/drop, take_/drop_while, span/break, group 
  * flows pair arithmetic: 
      dup, comb/split, merge/switch 
  * flows array arithmetic: 
      dupn, combn/splitn, mergen/switchn 
  * computation over flow 
      map, map2, scanl, scan, map_fold 
  * circular flow 
      feedl/feelr, circ 
  * high-level flow combinator 
      while_do/do_while, farm, pipe(///), pardo(//) 
  * shorthand operator and helper 
      |>, @., |-, -|, //, curry/uncurry, id 

The library is currently short of documentation, you'd better refer to the 
manual page. 

== Example == 

* sum(n) sequence 

# let sums = enum 1 |> scan (+);; 
val sums : int flow = <abstr> 
# sums |> take_while ((>) 100) |> to_list;; 
- : int list = [1; 3; 6; 10; 15; 21; 28; 36; 45; 55; 66; 78; 91] 

* Fibonacci number sequence 

# let fibs = map2 (+) |- circ [<'1>] |> circ [<'0;'0>];; 
val fibs : int flow = <abstr> 
# fibs |> take 10 |> to_list;; 
- : int list = [1; 1; 2; 3; 5; 8; 13; 21; 34; 55] 

* stupid computation 

      3+33  6+33  9+33  12+33  15+33  18+33 
c = [ ----, ----, ----, -----, -----, -----, ... ) 
        2     4     8     10     14     16 

# let modv v x = x mod v = 0;; 
# let cl = uncurry (map2(/)) -| map((+)33) // filter(modv 2) -| switch(modv 3);; 
val cl : int flow -> int flow = <fun> 
# enum 1 |> cl |> take_while ((<) 1) |> iter print_int;; 
1895433222222- : unit = () 

* remove every 3th 

# let mv3 = cycle [<'true;'true;'false>] |> curry comb |- filter fst |- map snd;; 
val mv3 : '_a flow -> '_a flow = <fun> 
# enum 1 |> mv3 |> take 15 |> to_list;; 
- : int list = [1; 2; 4; 5; 7; 8; 10; 11; 13; 14; 16; 17; 19; 20; 22] 

* group sum 

group and sum when (sum mod 6) = 0 
e.g. [ 1+2+3, 4+5+6+7+8, 9+10+11, 12+13+14+15, 16+17+18+19+20, 21+22+23, ... ] 

# let f a x = let r = a+x in r, if modv 6 r then Some true else None;; 
# enum 1 |> map_fold f |> take 10 |> to_list;; 
- : int list = [6; 30; 30; 54; 90; 66; 102; 150; 102; 150] 

* non-strict evaluation 

Strict computation over 5 loops forever, all the rest computation is blocked. 

# 1--9 |> (while_do ((=)5) (map id) |- iter (print_int |- flush_all));; 
1234  C-c C-cInterrupted. 

We can still evaluate the rest if we increase the capacity of do_while's sub 
dataflow network. Note that the evaluation is non-strict but deterministic. 

# 1--9 |> (while_do ~size:2 ((=)5) (map id) |- iter (print_int |- flush_all));; 
12346789 
  C-c C-cInterrupted. 

(*) It won't be particularly difficult to implement another persistent version, 
like lazy list. But for now I haven't seen enough reason to do so.
			

Using folding to read the cwn in vim 6+

Here is a quick trick to help you read this CWN if you are viewing it using vim (version 6 or greater).

:set foldmethod=expr
:set foldexpr=getline(v:lnum)=~'^=\\{78}$'?'&lt;1':1
zM

If you know of a better way, please let me know.


Old cwn

If you happen to miss a CWN, you can send me a message and I'll mail it to you, or go take a look at the archive or the RSS feed of the archives.

If you also wish to receive it every week by mail, you may subscribe online.


Alan Schmitt