Re: Lambda calculus numerals book recommendation?
From: HERC777 (herc777_at_hotmail.com)
Date: 12/07/04
 Next message: Christopher A. Lee: "Re: What guarantee do we have of scientific method?"
 Previous message: paul: "Re: Tautologies Then and Now"
 In reply to: H. J. Sander Bruggink: "Re: Lambda calculus numerals book recommendation?"
 Next in thread: H. J. Sander Bruggink: "Re: Lambda calculus numerals book recommendation?"
 Reply: H. J. Sander Bruggink: "Re: Lambda calculus numerals book recommendation?"
 Messages sorted by: [ date ] [ thread ]
Date: 6 Dec 2004 21:06:48 0800
I haven't heard of 'numerals', mentioned in some sites though
http://www.bath.ac.uk/~cs1spw/notes/Lisp/notes45.html
Church Numerals
Typed Church numerals are peculiar  you get the whole range of Church
numerals for each type, giving you an eventually infinite set.
Polymorphic Church Numerals are more flexible:
n = Λt.λxt > tyt.xny
One kind of numeral can apply to anything as long as the type
structures match. They behave exactly the same as normal Church
numerals in pure lambda calculus.
Polymorphic Combinators
K = Λst.λxsyt.x
Type: ∀st. s>t>s
S = Λrst.λxr>s>tyr>szr.xz(yz)
Type: ∀rst.(r>s>t)>(r>s)>r>t
but I'm familiar with S and K combinators, they are used in the Miranda
compiler and should have more extensive literature.
I don't know why Sander is talking about function Y here, recursion is
taken for granted in application oriented lambda calculus, unless you
are interested in recursion itself but Y is inefficient.
Yf = fYf
something like that, a trick of lambda calculus to get multiple
versions of the one function instantiated. There's other bizzare
functions aswell that handle construction of lists and peano axioms
with pure functions, but aren't used.
Lambda Calculus + recursion + list constructors + primitive data
structure = useful language
though lambda calculus can do it all itself if you want.
Herc
 Next message: Christopher A. Lee: "Re: What guarantee do we have of scientific method?"
 Previous message: paul: "Re: Tautologies Then and Now"
 In reply to: H. J. Sander Bruggink: "Re: Lambda calculus numerals book recommendation?"
 Next in thread: H. J. Sander Bruggink: "Re: Lambda calculus numerals book recommendation?"
 Reply: H. J. Sander Bruggink: "Re: Lambda calculus numerals book recommendation?"
 Messages sorted by: [ date ] [ thread ]
Relevant Pages
