# 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

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

## Access the best Study Guides, Lecture Notes and Practice Exams Unlocking...