From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id BBE80BBBB for ; Tue, 28 Mar 2006 02:56:08 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id k2S0u8X2025772 for ; Tue, 28 Mar 2006 02:56:08 +0200 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id CAA22631 for ; Tue, 28 Mar 2006 02:56:07 +0200 (MET DST) Received: from tebo.cs.washington.edu (tebo.cs.washington.edu [128.208.6.74]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k2S0u5gA028548 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Tue, 28 Mar 2006 02:56:07 +0200 Received: from [128.208.7.129] (sadie.dyn.cs.washington.edu [128.208.7.129]) (authenticated bits=0) by tebo.cs.washington.edu (8.13.6/8.13.5/1.5) with ESMTP id k2S0tx9V028334 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Mon, 27 Mar 2006 16:56:00 -0800 (envelope-from marius@cs.washington.edu) Message-ID: <4428899A.9090803@cs.washington.edu> Date: Mon, 27 Mar 2006 16:55:54 -0800 From: Marius Nita User-Agent: Thunderbird 1.5 (Macintosh/20051201) MIME-Version: 1.0 To: padator@wanadoo.fr Cc: Oliver Bandel , caml-list@inria.fr Subject: Re: [Caml-list] Lambda-Term (f x) (x f) translated to Ocaml? References: <24000351.1143506695382.JavaMail.www@wwinf1608> In-Reply-To: <24000351.1143506695382.JavaMail.www@wwinf1608> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 442889A8.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 442889A5.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; translated:01 ocaml:01 lambda:01 translated:01 ocaml:01 lambda:01 combinator:01 nita:98 wrote:01 caml-list:01 expression:01 calculus:01 calculus:01 namely:02 guess:03 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 yoann padioleau wrote: >> Hello, >> >> I'm not firm in lambda calculus, what is the lambda-term >> in the subject translated to OCaml? >> >> Is this possible? > > the ocaml interpreter dont want this definition > > let g f x = (f x) (x f) > > and shout: > this expression has type ('a -> 'b) -> 'c -> 'd but is here used with type 'a > > I guess that this is not a lambda term that can be typed. > There are many of them. A famous one is the Y combinator. > The _typed_ lambda calculus does not allow all the lambda terms > of the (normal) lambda calculus. g can't be written, but (f x) (x f) works for suitable values for f and x :) Namely if f = x = id. There's probably some deep parametricity property at the heart of it. -marius