calculating a remainder of two church number on lambda calculs with ocaml

calculating a remainder of two church number on lambda calculs with ocaml

[Su Zhang]

[-- Attachment #1: Type: text/plain, Size: 376 bytes --]

Hi OCaml hackers,

I have a question about how can I write a function which can get the
remainder of two church numberials in lambda calculus. I know this is a
ocaml maillist, but this lambda calculus should use ocaml engine, so is
there anybody know how can I write this function?

Thanks!



-- 
Su Zhang
PHD Student
Computer Information and Science
Kansas State University

[-- Attachment #2: Type: text/html, Size: 502 bytes --]

Re: [Caml-list] calculating a remainder of two church number on lambdacalculs with ocaml

[Damien Guichard]

[-- Attachment #1: Type: text/plain, Size: 2083 bytes --]


Hi fellow ocaml coder,


Church numerals is a unary coding and as such is awfully inefficient.
Multiplication typically uses repeated addition.
Division/remainder also typically uses repeated substraction.
Because of the crappy unary coding there is little you can do to improve on that. 

My advice is you could gain much better efficiency via a binary coding.
Here is how you can do the easy part :

type nat =
  | Null           (* 0 *) 
  | Unit           (* 1 *)
  | Zero of nat    (* 0... *)
  | One  of nat    (* 1... *)

let rec even = function
  | Null -> true
  | Unit -> false
  | Zero n | One  n -> even n 

let rec double = function
  | Null -> Zero Null
  | Unit -> One  Null
  | Zero n -> Zero (double n)
  | One  n -> One  (double n)

let succ n = 
  let rec loop = function
    | Null -> Unit,false
    | Unit -> Null,true
    | Zero n -> let m,c = loop n in (if c then One m else Zero m),false  
    | One  n -> let m,c = loop n in (if c then Zero m else One m),c  
  in
  let m,c = loop n in if c then One m else m

let mult a b =
  let rec loop = function 
    | Null -> Null,double b
    | Unit -> b,double b
    | Zero n -> let d,c = loop n in d,double c 
    | One  n -> let d,c = loop n in add d c,double c
  in let n,_ = loop a in n


That is dirty untested code yet i hope you get the idea.
Addition/substraction and division will be somewhat trickier however.

- damien





Damien Guichard
2009-03-21



En réponse au message
de : Su Zhang
du : 2009-03-21 18:36:11
À : caml-list@yquem.inria.fr
CC : 
Sujet : [Caml-list] calculating a remainder of two church number on lambdacalculs with ocaml

Hi OCaml hackers,

I have a question about how can I write a function which can get the remainder of two church numberials in lambda calculus. I know this is a ocaml maillist, but this lambda calculus should use ocaml engine, so is there anybody know how can I write this function? 

Thanks!



-- 
Su Zhang
PHD Student 
Computer Information and Science
Kansas State University 

[-- Attachment #2: Type: text/html, Size: 5519 bytes --]