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
[Caml-list] Association lists
On Mon, Mar 12, 2012 at 7:03 PM, Xavier Leroy 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? -- 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] A js_of_ocaml equivalent for the JVM?
Thank you Xavier and Johan for the replies. 2012/3/9 fo...@x9c.fr > > Le 9 mars 2012 à 18:45, Johan Grande a écrit : > > > Le 09/03/2012 18:12, Philippe Veber a écrit : > >> Dear camlers, > >> I used js_of_ocaml several times and was really stunned of how clever > >> (notably because writing interfaces boils down to writing types) and > >> efficient this approach is. Would a similar thing work for the JVM, that > >> is a compiler from ocaml bytecode to java bytecode? > > It is not easy to envision such a tool on the JVM, because of the current > restrictions imposed on Java bytecode. As an example, the size of a method > is currently limited to 64Ko, which is clearly way too small for non > trivial > programs. I see the point. It sure is a problem to reuse the same compilation scheme than in js_of_ocaml. > > > >> I guess it wouldn't > >> provide a full interoperability with java, in the sense that creating or > >> extending classes may not be possible (well, why not after all?). > >> However, being able to run an ocaml program on the JVM reusing existing > >> java libraries would be so useful already! > > I am currently working on this for OCaml-Java (see below). > I must admit one of the most exciting feature of js_of_ocaml (beside efficiency) is the way ocaml interfaces with javascript. I remember the procedure was much heavier with nickel. In another thread ( http://www.mail-archive.com/caml-list@inria.fr/msg02094.html) you said that this has changed in the version you're currently developing. I look forward to see how it works (I'm in if you need alpha testers). > > > >> Are there known obstacles to this? Has anyone tried something in this > >> direction? > > Well, no real obstacle as OCaml-Java showed. > However, OCaml-Java 1.x is still a bare proof of concept due to both > poor design choices and JVM limitations. But then came Java 1.7 and > some limitations were removed (e. g. a garbage collector better suited > to functional languages, and an implementation of method handles). > OCaml-Java has been largely rewritten and now exhibit acceptable > performances. > This is really great. > > > >> Would there be a chance to support multicore programming that > >> way? > > Yes, it is actually working. But not released yet. > Starting from vanilla OCaml, you "only" need two things: > 1/ have a reentrant runtime; > 2/ have a parallel garbage collector. > OCaml-Java implements the former, while all modern JVMs provide the latter. > So, basically, it just works. itou > The great difficulty is then to provide the good > abstractions to make the life of the programmer as easy as possible. > I mean: who would like to program with locks? > Well I'm not much into multicore programming myself, but at least for advertisement purposes, it cannot hurt ;o). > > > >> I hope these are not silly questions (sorry if they are!) > > > > http://ocamljava.x9c.fr > > Thanks for the plug. However, OCaml-Java is quite different and provides > two tools: > - an equivalent of ocamlrun written in Java (meaning you can interpret >OCaml bytecode inside a JVM); > - an equivalent of ocamlc/ocamlopt for Java (meaning you can compile >OCaml sources to Java jar files to be executed by a JVM). > Thanks for the news and clarifications! > > > Kind regards, > > Xavier Clerc > > > > -- > 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 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] Stog: static web site and blog generator
Hello, Stog is a kind of Jekyll in OCaml: It is a static web site generator, able to handle blog posts as well as regular pages. It is based on a XML engine allowing to apply substitutions on some tags. Some substitutions are pre-defined, and others can be added by plugins. Home page: http://zoggy.github.com/stog/index.html Code on github: http://www.github.com/zoggy/stog News about stog: http://zoggy.github.com/stog/blog.html Hope you'll find it useful. Regards, Maxence -- 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] Wanted: GADT examples: string length, counting module x
Hi,
yesterday I compiled ocaml 3.13 and played around a bit with the GDAT
syntax but wasn't overly successfull. Or at least I had higher hopes for
it. So it is time to invoke the internet to come up with a better
example. :)
1) How do I write a GADT that encodes the length of a string or array?
How do I use that to create a string or array?
How do I specify a function that takes a string or array of a fixed length?
Bonus: How do I specify a function that takes a string or array of a
certain length or longer?
2) How do I write a GADT that counts an int module x? Say for an offset
into a byte stream to safeguard when access is aligned and when
unaligned.
Again with an example that creates a value and a function that uses
it.
Bonus: Have one function that only allows aligned access and one that
picks the right aligned/unaligned function to use depending on
the type.
Below I've included an example for checking aligned access (1/2/4/8 byte
aligned). First using GADT and second using old style phantom types. The
second looks much longer because it includes the signature needed to
make the type (...) off private. The t1/t2/t4/t8 types are just aliases
to make the type of the other functions shorter.
One thing I couldn't manage is to write a "bind" function with GADTs or
bind takeX to a string unless I specify the full type. "takeX s" always
switches to '_a types and then gets bound to a specific type on the
first use and fail on the second use.
On the plus side of GADTs is that you do not need a private type (and
therefore the module signature) to make them work.
MfG
Goswin
PS: Other simple examples that show the power of GADTs are welcome too.
--
(* Declare GADT type *)
type z
type u
type _ t =
| Zero : ((z * u) * (z * u * u * u) * (z * u * u * u * u * u * u * u)) t
| Succ : (('a * 'b) * ('c * 'd * 'e * 'f) * ('g * 'h * 'i * 'j * 'k * 'l * 'm
* 'n)) t -> (('b * 'a) * ('d * 'e * 'f * 'c) * ('h * 'i * 'j * 'k * 'l * 'm * 'n
* 'g)) t
(* start of stream *)
let zero = (Zero, 0)
(* advance by 1, 2, 4 or 8 *)
let succ1 x = Succ x
let succ2 x = succ1 (succ1 x)
let succ4 x = succ2 (succ2 x)
let succ8 x = x
(* take 1, 2, 4 or 8 bytes with alignment restriction *)
let take1 : type a b c d e f g h i j k l m n. string -> (((a * b) * (c * d * e *
f) * (g * h * i * j * k * l * m * n)) t * int) -> b * a) * (d * e * f * c)
* (h * i * j * k * l * m * n * g)) t * int) * string) = fun s (t, x) -> ((succ1
t, x+1), String.sub s x 1)
let take2 : type c d e f g h i j k l m n. string -> (((z * u) * (c * d * e * f)
* (g * h * i * j * k * l * m * n)) t * int) -> z * u) * (e * f * c * d) * (i
* j * k * l * m * n * g * h)) t * int) * string) = fun s (t, x) -> ((succ2 t, x
+2), String.sub s x 2)
let take4 : type g h i j k l m n. string -> (((z * u) * (z * u * u * u) * (g * h
* i * j * k * l * m * n)) t * int) -> z * u) * (z * u * u * u) * (k * l * m
* n * g * h * i * j)) t * int) * string) = fun s (t, x) -> ((succ4 t, x+4), Str
ing.sub s x 4)
let take8 : string -> (((z * u) * (z * u * u * u) * (z * u * u * u * u * u * u *
u)) t * int) -> z * u) * (z * u * u * u) * (z * u * u * u * u * u * u * u))
t * int) * string) = fun s (t, x) -> ((succ8 t, x+8), String.sub s x 8)
(* Test string *)
let s = "aabb"
(* extract things from string *)
let foo () =
let (off, a) = take1 s zero in
let (off, b) = take1 s off in
let (off, c) = take2 s off in
let (off, d) = take4 s off in
let (off, e) = take8 s off in
Printf.printf "%s %s %s %s %s\n" a b c d e
(* using take2/4/8 with an offset that isn't aligned gives a compile
time type error:
let bad () =
let (off, a) = take1 s zero in
take8 s off
*)
--
module M : sig
(* Types for aligned unaligned tracking *)
type z
type u
(* The type of an offset into a stream *)
type ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'l, 'm, 'n) off = private
int
(* Start of the stream *)
val zero : (z, u, z, u, u, u, z, u, u, u, u, u, u, u) off
(* Coercion to integer, same as (x :> int) *)
val get : ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'l, 'm, 'n) off -> int
(* Advance the position by 1, 2, 4 or 8 *)
val succ : ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'l, 'm, 'n) off ->
('b , 'a, 'd, 'e, 'f, 'c, 'h, 'i, 'j, 'k, 'l, 'm, 'n, 'g) off
val succ2 : ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'l, 'm, 'n) off ->
('a , 'b, 'e, 'f, 'c, 'd, 'i, 'j, 'k, 'l, 'm, 'n, 'g, 'h) off
val succ4 : ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'l, 'm, 'n) off ->
('a , 'b, 'c, 'd, 'e, 'f, 'k, 'l, 'm, 'n, 'g, 'h, 'i, 'j) off
val succ8 : ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'l, 'm, 'n) off ->
('a , 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'l, 'm, 'n) off
(* Aliases for shorter type names *)
type ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i,
Re: [Caml-list] OCaml Users and Developers workshop (OUD)
On Mar 9, 2012, at 14:40 , Didier Remy wrote: > - compiler developments; new backends, runtime and architectures. On a related note: My bachelor student Colin Benner almost got his LLVM backend for ocamlopt working and will be preparing a talk on his work for the OUD. Just in case you're interested. :-) greets, Benedikt -- 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] ocamldoc: Howto crossreference another library?
Maxence Guesdon writes: So the answer is: you can't. Thanks for the fast answer! I filed feature wish #5533 about this. Bye, Hendrik -- 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
