help needed with Lambda-Calculus

Piero Campanelli

unread,

Jun 25, 1997, 3:00:00 AM6/25/97

to

Hello

i am studing Lambda-calculus and in particular the lambda-reduction
strategies. The only one that lambda calc. can do is lazy-reduction.
Is there someone that can help me how does it work?
Can you give me some examples of reductions?
Or can you give me web references about examples and docs?

Thank you
If so drop me a mail

P.s.
probably this question doesn't relate to Lisp but it is very closed to it.

--
==================================
Piero Campanelli
E-mail: camp...@tin.it

Juergen Nickelsen

unread,

Jul 7, 1997, 3:00:00 AM7/7/97

to

Piero Campanelli <camp...@tin.it> wrote:

> i am studing Lambda-calculus and in particular the lambda-reduction
> strategies. The only one that lambda calc. can do is lazy-reduction.
> Is there someone that can help me how does it work?
> Can you give me some examples of reductions?
> Or can you give me web references about examples and docs?

In "Foundations of Theoretical Computer Science" (or the like, a large
two-volume book) is a good introductory article about the Lambda
Calculus by Barendregt. It covers the different reduction strategies.
This is from memory; I don't have the references at hand.

Sorry, no Web reference. I am afraid you'll have to go to a real library
to dig this one out.

--
Juergen Nickelsen

M J Morley

unread,

Jul 12, 1997, 3:00:00 AM7/12/97

to

... "jn" == Juergen Nickelsen <jnick...@acm.org> writes:

jn> Piero Campanelli <camp...@tin.it> wrote:
pc> i am studing Lambda-calculus and in particular the lambda-reduction
pc> strategies. The only one that lambda calc. can do is lazy-reduction.
pc> Is there someone that can help me how does it work?
pc> Can you give me some examples of reductions?
pc> Or can you give me web references about examples and docs?

i guess your studies have not progressed very far!

jn> In "Foundations of Theoretical Computer Science" (or the like, a large
jn> two-volume book) is a good introductory article about the Lambda
jn> Calculus by Barendregt. It covers the different reduction strategies.
jn> This is from memory; I don't have the references at hand.

jn> Sorry, no Web reference. I am afraid you'll have to go to a real library
jn> to dig this one out.

then the correct citation would help:

H.P. Barendergt, "Functional Programming and Lambda Calculus", Chapter
7 of "Formal Models and Semantics", Vol B of J. van Leeuwen, editor,
Handbook of Theoretical Science, Elsevier Science, 1990.

one of the most useful books in computer science.

another on the lambda calculus is

Hindley & Seldin, "Introduction to Combinators and Lambda Calculus",
CUP, 1986 (London Mathematical Society Student Texts #1).

jn> --
jn> Juergen Nickelsen

M
--
- ------------------------------------------------------------------ -
- M.J.Morley, School of Computer Studies, University of Leeds, Leeds -
- LS2 9JT. Tel: +44 (0)113 233 5477 _______ Fax: +44 (0)113 233 5468 -
- ------------------------------------------------------------------ -

Erik Naggum

unread,

Jul 13, 1997, 3:00:00 AM7/13/97

to

* M. J. Morley

| then the correct citation would help:
|
| H.P. Barendergt, "Functional Programming and Lambda Calculus", Chapter
| 7 of "Formal Models and Semantics", Vol B of J. van Leeuwen, editor,
| Handbook of Theoretical Science, Elsevier Science, 1990.
|
| one of the most useful books in computer science.

let me second that wholeheartedly. both volumes, actually. (available in
paperback at a small fraction of the cost of the hardcover edition.)

I found Barendregt's article in Handbook of Logic in Computer Science (a
series edited by Abramsky, Gabbay, and Maibaum), Volume 2, Background:
Computational Structures, entitled "Lambda Calculi with Types" to give a
better introduction to untyped lambda calculus and reduction. YMMV.

in addition, if you can still obtain the following book, it's a big win:

H.P. Barendregt: The Lambda Calculus, Its Syntax and Semantics. Volume 103
in Studies in Logic and the Foundations of Mathematics. originally
published in 1981, the revised edition was published by North Holland in
1984, reprinted 1985. ISBN 0-444-87508-5.

this is a very thorough introduction to Lambda Calculus.

#\Erik
--
if DUI is "Driving Under the Influence"
then GUI must be "Graphics Under the Influence"