From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: ** X-Spam-Status: No, score=2.3 required=5.0 tests=AWL,DNS_FROM_RFC_POST, SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 83EA4BC37 for ; Wed, 30 Sep 2009 14:54:11 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqUBAIzxwkrRVdvckGdsb2JhbACaQD8BAQEBCQkMBxMDrT2QCAEDAwWCMoFwBIgd X-IronPort-AV: E=Sophos;i="4.44,480,1249250400"; d="scan'208";a="37175214" Received: from mail-ew0-f220.google.com ([209.85.219.220]) by mail1-smtp-roc.national.inria.fr with ESMTP; 30 Sep 2009 14:54:11 +0200 Received: by ewy20 with SMTP id 20so6127655ewy.44 for ; Wed, 30 Sep 2009 05:54:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:sender:received:in-reply-to :references:date:x-google-sender-auth:message-id:subject:from:to:cc :content-type:content-transfer-encoding; bh=Cmi33li0RnwVB+8LF8IWcHHvY10cuPA2X1o1DRC5lJI=; b=doBXH44lyabRCroEwYeuz7RNYsVoXA2yOYWE96JFLkfEWHfndsZ6n5/k5THwHqPct+ Pi7rxubehFKOJxvCsWYgMnvCGvDQkRRPk/JA50tiWKFhoq1VZRoJ77Dl2y5NlkWS2Q2R D0pxlgU2ThkRsxu0OpgSPqGv3FSfhuoqCZzzI= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type :content-transfer-encoding; b=kbuQuJEvXZ6HHOnPxYvuBar1XdXN49ubGDGgfWjoQXLAg/N59Ijq42p64ftYO2ENmD lgdkYwRf0QkRNbm+XwLxr6qcIebTfj+C2a7EHVzm72DAj2bSXQE/XE/aKuxveTZgHJ3/ yN0fW01rY0F/ehHhMuZAw0dSiEIOXyjhfEogM= MIME-Version: 1.0 Sender: mikkelfj@gmail.com Received: by 10.216.47.206 with SMTP id t56mr1525833web.73.1254315250430; Wed, 30 Sep 2009 05:54:10 -0700 (PDT) In-Reply-To: <4AC34792.8050103@glondu.net> References: <4E6F3027-5745-462D-AF10-30C868285D28@refined-audiometrics.com> <4ABFB7DE.2050108@gmail.com> <60282.70.26.46.231.1254079393.squirrel@pegasus.carleton.ca> <200909272210.19130.jon@ffconsultancy.com> <4AC34792.8050103@glondu.net> Date: Wed, 30 Sep 2009 14:54:10 +0200 X-Google-Sender-Auth: 455d38b9a3ed79e5 Message-ID: Subject: Re: [Caml-list] JIT & HLVM, LLVM From: =?UTF-8?Q?Mikkel_Fahn=C3=B8e_J=C3=B8rgensen?= To: =?UTF-8?Q?St=C3=A9phane_Glondu?= Cc: caml-list@yquem.inria.fr Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Spam: no; 0.00; mikkel:01 rgensen:01 mikkel:01 ocaml:01 buffer:01 monadic:01 parsers:01 parsers:01 recursive:01 monadic:01 ocaml:01 doable:01 rgensen:01 suspended:98 analog:98 First, sorry for the rough post (it was late), I see some typos and slightly more confusing mistakes, but hopefully not too bad, or please ask. >> A function can push other functions to the global queue. This in >> effect creates a continuation, and the concept is similar to >> continuation passing style or LWT threads, *but requires no >> continuation arguments to drag around*. > Could you elaborate? Yes, I'm probably not the best to explain continuation passing style, but I'll give it a shot. In OCaml you do not have continuations, but you do have partial evaluation. This means the function let sum a b =3D a + b can be called partially like let sum_creator a =3D sum a This won't execute the sum code, but will have it pending until we get the last argument b. In this sense the sum_creator function is a sleeping thread waiting to execute. We can combine several functions in this way to get a complex calculation which won't evaluate until the continuation argument b is supplied. For example we can create a complex boolean expression combining several primitive and / or functions that take a variable x as argument. The entire expression is suspended until x is given, and in principle the OR subexpressions could execute in parallel. We can also build parse expressions where it is not a variable x, but the rest of the input string that is missing. Instead of evaluating a sum or boolean expression, the function could do something else, like filling a buffer from a socket. The k argument does not need to be used at all, we just use it to avoid computation before we need it. We can use this to create threads by having an extra dummy argument that we will call k. We don't really need k we just need the expression to not evaluate before we say so. This is the continuation being dragged (passed) around. (In monadic stream parsers, the k continuation is replaced by io state which is dragged around, and contrary to k it provides useful information. These parsers allow parsing to sleep when the input stream dries up temporarily, and the parsers can explore several parse paths concurrently (useful for error reporting), so there is an analog to concurrent threads consuming i/o). A function can also return a recursive call to itself supplying new state such as bytes left to read, or a partial call to another function, in both cases supplying new state information, but failing to supply to the k argument such that "the next task to execute" is returned instead of actually executing this task. A now it starts to get complex, but you get a hold of an entire tree of partially evaluated functions that are parked waiting for the last argument. A clean way to put one function after another so they execute in sequence as dependent tasks is to use a monadic bind operation: http://ocsigen.org/docu/last/Lwt.html#VALbind But this requires the function to be designed in a clean way and conform to certain monadic rules, and getting it wrong creates a mess in the type errors. What we effectively achieve is a lot of functions queued up on a the call stack in the form of closures allocated to hold the partially evaluated parameters. Now, we might as well just push a closure onto a queue instead of on the call stack. This avoid a lot of complexity in the function type design, and we get a lot more flexibility in how we dispatch the tasks (arguably we could do the same or possibly more, in continuation passing style, but it will give you a headache). We might loose some type safety by using queues, but I'm sure one could dream up some queue type system to enforce certain conditions. More importantly, it is much simpler to understand a closure on a queue, than continuation passing style. And finally, with queues you have an elegant way of extending this to multiple OS threads (or ocaml green threads), although again this is also doable in continuation passing style. Someone could probably argue that a queue is also just a continuation state or something, but we a dealing with making threaded abstractions that are easy to use and implement, not mathematical equivalence relations. 2009/9/30 St=C3=A9phane Glondu : > Mikkel Fahn=C3=B8e J=C3=B8rgensen a =C3=A9crit : >> A function can push other functions to the global queue. This in >> effect creates a continuation, and the concept is similar to >> continuation passing style or LWT threads, *but requires no >> continuation arguments to drag around*. > > Could you elaborate? > > > Best regards, > > -- > St=C3=A9phane > >