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

Previewing page 1 of 2 page document View the full content.
View Full Document

LAMBDA CALCULUS CHEAT SHEET



Previewing page 1 of actual document.

View the full content.
View Full Document
View Full Document

LAMBDA CALCULUS CHEAT SHEET

57 views


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

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

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view LAMBDA CALCULUS CHEAT SHEET and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LAMBDA CALCULUS CHEAT SHEET and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?