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

Previewing page*1*of 2 page document

**View the full content.**## LAMBDA CALCULUS CHEAT SHEET

Previewing page *1*
of
actual document.

**View the full content.**View Full Document

## LAMBDA CALCULUS CHEAT SHEET

0 0 57 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