[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [ProgSoc] CSS and Divs



On Wed, Jul 05, 2006 at 03:04:54AM +0000, John Elliot wrote:
> I intend to further that discussion, however it will take me some time 
> to respond. Won't happen today.

Sorry I just realised that Google does not return many relevant results
on this topic, so I will reproduce for you here the essential
definitions of the Lambda Calculus and its evaluation rules, essentially
as they were defined by Church (although he used slighly different
symbol names).

The BNF of the language is:

t ::= x | \x.t | t t

A term (meta-variable "t") is either a variable (meta-variable "x"), a
lambda abstraction \x.t (lambda x dot t) of a term t by a variable x, or
an application of one term to another.

The basic reductions (>) are:

(\x.t1) t2 > t1[t2/x]

where t1[t2/x] means "t1 with t2 substituted for occurrences of x".

A one-step reduction (>1) is a basic reduction applied to any subterm of
a term.

A reduction (>*) is a series of one-step reductions.



Example of reduction (by a series of one-step reductions):

let f = function(x,y) => x+y in f(2,3)

This translates into the lambda calculus term:

(\f.(f 2) 3) (\x.\y.x+y)

where 2, 3 and + are assumed (look up "Church Numerals" for definitions
of these). Reduction of this program works as follows:


   (\f.(f 2) 3) (\x.\y.x+y)
>1 ((\x.\y.x+y) 2) 3
>1 (\y.2+y) 3
>1 2+3
>* 5

Where 2+3 >* 5 is a series of one-step reductions based on the
definitions of 2, 3 and +.

Notice that reduction is context-free. A term stands on its own and can
be reduced without looking up information in a context.


Other equivalent reduction rules are possible that do make use of a
context (e.g. look up "closures"), those are typically used in the
implementation of compilers. But the basic underlying theory does not
require context to drive evaluation.

-- 
Ryan Heise
http://www.ryanheise.com/

-
You are subscribed to the progsoc mailing list. To unsubscribe, send a
message containing "unsubscribe" to progsoc-request@xxxxxxxxxxxxxxxxxxx
If you are having trouble, ask owner-progsoc@xxxxxxxxxxxxxxxxxx for help.