# 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
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 Unlocking...
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?