DARTMOUTH COSC 068 - LAMBDA CALCULUS CHEAT SHEET (2 pages)

Previewing page 1 of 2 page document
View Full Document

LAMBDA CALCULUS CHEAT SHEET

Previewing page 1 of actual document.

View Full Document
View Full Document

LAMBDA CALCULUS CHEAT SHEET

73 views

Pages:
2
School:
Dartmouth College
Course:
Cosc 068 - Principles Programming Lang
Principles Programming Lang Documents
• 6 pages

Unformatted text preview:

Lambda Calculus Cheat Sheet CS 68 April 3 2011 1 Lambda calculus syntax Lambda calculus terms are variables function applications or function definitions M v M M v M where v represents a variable symbol Computation takes place by substituting in actual parameters for free occurrences of formal parameters which are defined by induction on the structure of lambda calculus terms as follows Definition 1 1 If M is a term then FV M the collection of free variables of M is defined as follows 1 FV x x 2 FV M N FV M FV N Lambe 3 FV v M FV M v Definition 1 2 We write N x M to denote the result of replacing all free occurrences of identifier x by N in expression M 1 N x x N 2 N x y y if y 6 x 3 N x L M N x L N x M 4 N x y M y N x M if y 6 x and y 6 FV N 5 N x x M x M 1 2 Rules of Computation Definition 2 1 The reduction rules for the lambda calculus are given by x M y y x M if y 6 FV M x M N N x M x M x M 2

View Full Document

Unlocking...