Hello
Here is the latest Caml Weekly News, for the week of October 09 to 16, 2007.
> 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.
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/
> 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!
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
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
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.
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.
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.
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.