[cwn] Attn: Development Editor, Latest Caml Weekly News
Alan Schmitt
alan.schmitt at polytechnique.org
Tue Oct 16 00:14:46 PDT 2007
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
========================================================================
1) 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.
========================================================================
2) 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/>
========================================================================
3) 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!
========================================================================
4) 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
========================================================================
5) 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 at microsoft.com
Closing date for applications is Friday, 30 November 2007.
Microsoft Research is an equal opportunities employer
========================================================================
6) 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.
========================================================================
7) 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}$'?'<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
(alan.schmitt at polytechnique.org) and I'll mail it to you, or go take
a look at
the archive (<http://alan.petitepomme.net/cwn/>) or the RSS feed of the
archives (<http://alan.petitepomme.net/cwn/cwn.rss>). If you also wish
to receive it every week by mail, you may subscribe online at
<http://lists.idyll.org/listinfo/caml-news-weekly/> .
========================================================================
--
Alan Schmitt <http://alan.petitepomme.net/>
The hacker: someone who figured things out and made something cool
happen.
.O.
..O
OOO
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://lists.idyll.org/pipermail/caml-news-weekly/attachments/20071016/deeb9ac0/attachment.pgp
More information about the caml-news-weekly
mailing list