Re: [Caml-list] Generating coinductive elements
Hello Jean-Baptiste, Let us take an example using streams (infinite lists) of numbers: type stream = Cons of int * stream You won't go far with this type for integer streams, as the only way to construct values of this type is let rec, and it's severely restricted (because of call-by-value requirements). For instance, you can't even define the stream of all integers 0.1.2.3.4... The proper OCaml type for integer streams is type stream = Cons of int * stream Lazy.t and with this type you should be able to do pretty much everything you want to do with your equations. HTH, - Xavier Leroy -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)
On 03/10/2012 08:31 AM, Richard W.M. Jones wrote: Rather than changing every app that uses Hashtbl, I'd prefer to fix this upstream by choosing a random seed for hash tables unless the caller explicitly sets one or sets an environment variable to disable this. In Perl, the seed is a random number chosen when the Perl interpreter starts up. This is low overhead, but still leaves a (much more theoretical) attack where someone can determine the seed from a long-running process using some other method and still attack the hash table. In Python there is an environment variable you can set to disable randomized hash tables. Further Python discussion here: http://bugs.python.org/issue13703 http://mail.python.org/pipermail/python-dev/2012-January/thread.html#115465 No comment at all? This is an exploitable CVE ... As you and Gerd said, the new Hashtbl implementation in the upcoming major release has everything needed to randomize hash tables by seeding. The question at this point is whether randomization should be the default or not: some of our big users who don't do Web stuff value reproducibility highly... We (OCaml core developers) will take a decision soon. Musing: there is something strange about saying that a data structure has a DOS vulnerability. It's a bit like saying that a steak knife has homicidal intent. Web-facing applications that use the wrong data structure have vulnerabilities; the data structure does not. And, even randomized, a hashtable still has O(n) worst-case behavior... Gerd Stolpmann adds: Currently, the only way for library developers to fix their product for 3.12 is to restrict the size of the hashtables coming from untrusted sources. A much better fix is to replace your hash tables with references to AVL maps. Guaranteed O(log n) is the way to go for Web app developers to sleep soundly at night. Resignedly awaiting a CVE about association lists, - Xavier Leroy -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Association lists
On 03/12/2012 07:12 PM, Lukasz Stafiniak wrote: Resignedly awaiting a CVE about association lists, Is using association lists a lot poor style? Wouldn't it be better to use maps -- which would make it possible to throw in different implementations to tune performance? I was joking, but to answer seriously: Association lists have O(1) insertion time but O(n) lookup time. So, you can use them as long as you're sure they are pretty short. If you're not sure, e.g. if malicious users of your program can grow the a-list as much as they want, better use maps, indeed. The joke was that we don't need a CVE to know this, just basic algorithmic reasoning. - Xavier Leroy -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Custom let bindings
On 01/20/2012 01:39 PM, Mehdi Dogguy wrote: I noticed that Alain Frisch tried to add custom let bindings (see r11894 and r11906) but it was reverted later on (see r11960) because no consensus was reached (among OCaml Core team, I guess). Yes. We Caml developers spent a lot of time arguing about the merits and demerits of various syntaxes for monadic lets and other forms of generalized let bindings, discussing usability, generality, etc. There were some unexpected surprises, e.g. Lwt's concurrency monad needing a special monadic let ... and ... in ... binding, which makes sense for this particular monad but not for others. In the end, we decided that none of the proposals is something we can commit on and put (forever) in the core language. This is one of the cases that is currently best handled by Camlp4 syntax extensions, either specific to a monad (Lwt) or more general (pa_monad). Regards, - Xavier Leroy -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Hashtbl and security
On 12/30/2011 05:44 PM, Gerd Stolpmann wrote: 1) Avoid hash tables in contexts where security is relevant. The alternative is Set (actually a balanced binary tree), which does not show this problem. Highly recommended. Nothing beats guaranteed O(log n) operations. 2) Use cryptographically secure hash functions. Hopeless: with a hash size of 30 bits, as in Caml, or even 64 bits, there are no cryptographically secure hash functions. 3) Use randomized hash tables. The trick here is that there is not a single hash function h anymore, but a family h(1)...h(n). When the hash table is created, one of the functions is picked randomly. This makes it impossible to craft an attack request, because you cannot predict the function. Indeed. The optional seed parameter to Hashtbl.create does exactly this in the new implementation of Hashtbl (the one based on Murmur3). So, the question is how to do 3). I see two problems here: a) how to define the family of hash functions. Is it e.g. sufficient to introduce an initialization vector for the Murmurhash algorithm, and fill it randomly? IIRC, the Web pages for the Murmur family of hashes gives some statistical evidence that this approach works. How to get a random number that is good enough? Hmm. /dev/random is your friend on the platforms that support it. Otherwise, there's always the Random module, but Random.self_init isn't very strong. - Xavier Leroy -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] OCaml maintenance status / community fork (again)
on the PRs in Mantis, to express support or disagreement, or to ask for clarifications. 5- Before embarking on patching the core Caml distribution, it wouldn't hurt to ask (privately) where the priorities are. For instance, I don't see the point for a linear-scan allocator (Benedikt Meurer) or more efficient compilation of value let-rec (Fabrice le Fessant), but anyone who would come up with a GHC-quality function inliner would be welcome like the Messiah. Likewise, for many years I've been looking for developers to work on the Windows port(s) of OCaml and never found any. Finally, at the latest OCaml consortium meeting, the idea of splitting Camlp4 off the core distribution was floated around; volunteers to take over its maintenance would be most welcome. All right. Let me stop here and pray for constructive, non-knee-jerk reactions. - Xavier Leroy -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Some comments on recent discussions
On 12/07/2011 12:18 PM, Gabriel Scherer wrote: The French book Le langage Caml is very great, althought it is quite old, and althought examples used in the book (write a pascal compiler, a grep tool and so on) is maybe too theoristic for engineer target. Maybe a translation would be sufficient ? I have contacted Xavier Leroy and Pierre Weis a few years ago to get the TeX sources of the book. I didn't intend to translate from French to English, but only, for a start, from Caml Light to Objective Caml. Neither of them could find the sources There must have been a misunderstanding: I have the full LaTeX sources, of course. What may have been lost is Pierre's first cut at an OCaml version of the book. Alan Schmitt adds: Yes, it's a great start to write a course on Caml. (I realize that the online version is the second edition, yet it is shorter than the paper version I have here. Either some chapters were removed in the 2nd edition or they are not available online.) No, no, the online edition is identical to the 2nd edition, which has one additional chapter. It's just that pages are wider and taller than those of the 1st edition, resulting in fewer pages overall. David Mentré adds: Unfortunately, it is available under a non Free license (Non Commercial clause of CC-BY-NC-SA licence), this is a show stopper for me. I would like such a book to be included in Debian or other Free Software distributions. I stand very firmly by the NC license. If anyone wants to make money out of this book or a derived work, the original authors and all the future contributors should get their share, Debian orthodoxy notwithstanding. - Xavier Leroy -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] How to simplify an arithmetic expression ?
On Sun, Oct 2, 2011 at 10:08 AM, Gabriel Scherer wrote: One approach I like for such simplifications is the normalization by evaluation approach. NBE is neat, but I'm skeptical that it will work out of the box here: if you apply NBE to a standard evaluator for arithmetic expressions, it's not going to take advantage of associativity and distributivity the way Diego wants. On 10/02/2011 05:09 PM, Ernesto Posse wrote: In general, whenever you have an algebraic structure with normal forms, normal forms can be obtained by equational reasoning: using the algebra's laws as rewriting rules. Yes, writing down a system of equations is the first thing to do. But, to obtain a normalization procedure, you need to orient those rules and complete them (in the sense of Knuth-Bendix completion) with extra rules to derive a confluent, terminating rewriting system. Here is a good, down-to-earth introduction to Knuth-Bendix completion: A.J.J. Dick, An Introduction to Knuth-Bendix Completion http://comjnl.oxfordjournals.org/content/34/1/2.full.pdf And here is a solid textbook on rewriting systems: Franz Baader and Tobias Nipkow. Term Rewriting and All That. http://www4.in.tum.de/~nipkow/TRaAT/ Hope this helps, - Xavier Leroy -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
[Caml-list] [Ann] Zarith
Dear list, It is my pleasure to announce release 1.0 of Zarith, a new OCaml library for exact, arbitrary-precision arithmetic on integers and rationals. Zarith was written by Antoine Miné with a little help from me and feedback from Pascal Cuoq. To download: http://forge.ocamlcore.org/projects/zarith/ The implementation uses GMP (the GNU Multiple Precision arithmetic library) to compute over big integers. However, small integers are represented as unboxed Caml integers, to save space and improve performance. Big integers are allocated in the Caml heap, bypassing GMP's memory management and achieving better GC behavior than e.g. the MLGMP library. Computations on small integers use a special, faster path (coded in assembly for some platforms and functions) eschewing calls to GMP, while computations on large intergers use the low-level MPN functions from GMP. As a consequence, Zarith is much faster and more space-efficient than the Big_int module from OCaml's standard distribution. Additional niceties of Zarith include: - short function names and infix operators, allowing one to write e.g. Z.(~$2 + ~$5 * x) - polymorphic comparisons (=, , , etc) work correctly on Zarith's big integers, provided OCaml 3.12.1 or later is used. Feedback is welcome, preferably through the bug tracker at http://forge.ocamlcore.org/projects/zarith/ Enjoy, - Xavier Leroy -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Val_int vs caml_copy_nativeint
On 08/08/2011 10:03 AM, Guillaume Yziquel wrote: Then I do not see anything wrong if the code snippet you sent. However, when you change Val_int to caml_copy_nativeint, the layout of the tuple is different. [...] So if you keep the same OCaml code when reading the result value, it's no surprise that the pointer is shown in place of the integer you expected. This is good advice indeed: make sure your Caml type declaration matches the data representation that your Caml/C stub implements... /* Package up the result as a tuple. */ v_response = caml_alloc_tuple (3) ; Store_field (v_response, 0, Val_int (width)) ; Store_field (v_response, 1, Val_int (height)) ; Store_field (v_response, 2, caml_copy_string (code)) ; CAMLreturn (v_response) ; Additionally, do make sure that v_response is registered with the GC (declared with one of the CAMLlocal macros). If both conditions are met, your code should be all right. If it still misbehaves, feel free to post a repro case on the bug tracker http://caml.inria.fr/mantis - Xavier Leroy -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
