Basic Lambda calculus - Syntax,Semantics,Programming

Outline
•Syntax of the lambda calculus
–abstraction over variables
•Operational semantics
–beta reduction
–substitution
•Programming in the lambda calculus
–representation tricks

Basic ideas

•introduce variables ranging over values
•define functions by (lambda-) abstracting over variables
•apply functions to values

• x + 1 

• lx. x + 1 

• (lx. x + 1) 2

Abstract syntax
Pure lambda calculus: start with nothing but variables.

Lambda terms
t ::=
       x variable
       lx . t abstraction
       t t application

Scope, free and bound occurences

Occurences of x in the body t are bound. Nonbound variable occurrences are called free.

(lx . ly. zx(yx))x

Beta reduction
Computation in the lambda calculus takes the form of beta-reduction:
     (lx. t1) t2 --> [x --> t2]t1

where [x --> t2]t1 denotes the result of substituting t2 for all free occurrences of x in t1.

A term of the form (lx. t1) t2 is called a beta-redex (or b-redex).

A (beta) normal form is a term containing no beta-redexes.


Beta reduction: Examples

• (lx.ly.y x)(lz.u) --> ly.y(lz.u) 

• (lx. x x)(lz.u) --> (lz.u) (lz.u) 

• (ly.y a)((lx. x)(lz.(lu.u) z)) --> (ly.y a)(lz.(lu.u) z) 

• (ly.y a)((lx. x)(lz.(lu.u) z)) --> (ly.y a)((lx. x)(lz. z)) 

• (ly.y a)((lx. x)(lz.(lu.u) z)) --> ((lx. x)(lz.(lu.u) z)) a

Evaluation strategies

•Full beta-reduction
–any beta-redex can be reduced
•Normal order
–reduce the leftmost-outermost redex
•Call by name
–reduce the leftmost-outermost redex, but not inside abstractions
–abstractions are normal forms
•Call by value
–reduce leftmost-outermost redex where argument is a value
–no reduction inside abstractions (abstractions are values) 

Programming in the lambda calculus

•multiple parameters through currying
•booleans
•pairs
•Church numerals and arithmetic
•lists
•recursion
–call by name and call by value versions

Computation in the lambda calculus takes the form of beta-reduction:

(lx. t1) t2 --> [x --> t2]t1

where [x --> t2]t1 denotes the result of substituting t2 for all free occurrences of x in t1.

A term of the form (lx. t1) t2 is called a beta-redex (or b-redex).

A (beta) normal form is a term containing no beta-redexes.


Symbols

Symbols   l ® b a ð Ô Ù ú

All root finding algorithms with pseudo code - Simple guide to easily understand

PSEUDO-CODE

We present basic pseudo-code for some of the algorithms, discussed in the Steps. In our experience, students do benefit by studying the pseudo-code of a method at the same time as they learn it in a Step. If they are familiar with a programming language, they should attempt to convert at least some of the pseudo-codes into computer programs, and apply them to the set Exercises.

Bisection Method 

The equation is f (x ) = 0.

Points for study:

1. What is the input used for?
   
2. Explain the purpose of Lines 8 - 12.
3. Amend the speudo-code, so that the process will always stop after preset M iterations.
4. Amend the pseudo-code so that the process will stop as soon as 
5. Write a computer program, based on this speudo-code.
6. Use your program to solve Exercises 1 and 2 in the Applied Exercises.

Method of False position 

The equation is f (x ) = 0.

Points for study

1. What are the input values used for?
2. Under what circumstances may the process stop with a large error in x?
3. Amend the pseudo-code so that the process will stop after M iterations, if the condition in Line 13 is not satisfied.
4. Write a computer Program based on the pseudo-code.
5. Use your program to solve Exercises 1 and 2 in the Applied Exercises.

Newton-Raphson iterative method 

The equation is f (x ) = 0.

Points for study

1. 8
2. How are the input values used?
3. Why is M given in the output of Line 10?
4. What happens if f'(a) is very small?
5. Amend the pseudo-code to take suitable action if f'(a) is very small.
6. Write a computer program based on the pseudo-code.
7. Use your program to solve Exercises 1 and 2 in the Applied Exercises.

Gauss Elimination

The system is:

*

Points for study

1. Explain what happens in Lines 2 - 10.
2. What process is implemented in Lines 11 - 18`?
3. Amend the pseudo-code so that the program terminates with an informative message when a zero pivot element is found.
4. Write a program based on the pseudo-code.
5. Use your program to solve Exercises 3 and 4 in the Applied Exercises.

Gauss-Seidel Iteration 

The system is:

Points for study

1. What is the purpose of the number s?
2. What are the y₁, y_{2 1}, . . ., y_n used for?
3. Why is it possible to replace the y_j in Line 13 by x_j?
4. Amend the pseudo-code to allow a maximum of M iterations.
5. Write a program based on the pseudo-code.
6. Use thc computer program to solve the system:
7. Use your program to solve Exercises 3 and 4 in the Applied Exercises
8. 

Newton divided difference formula 

You are to calculate for given data x₀, x₁, . . . , x_n, f(x₀), f(x₁), . . ., f(x_n), and for given  the interpolating polynomial P_n(x> of degree n. (The algorithm is based on divided differences.)

Points for study

1. Follow the pseudo-code through with the data n = 2, .x = 1.5, x₀ = 0, f (.x₀) = 2.5,.x₁ = 1, f (x₁) = 4.7, xSS₂ = 3, and f x₂) = 3.1. Verify that the values d_iicalculated are the divided differences f (x₀, . . .,.x_I).
2. What quantity (in algebraic terms) is calculated in Lines 10 - 15?
3. Amend the pseudo-code so that the values P₁(x), P₂(x)P&127;(x), . . ., P_n-1(x)are also printed out.
4. Write a computer program based on the pseudo-code.
5. Use your program to estimate f(2) for the data given in 1 above.
6. For the data, given in Exercise 6 of the Applied Exercises, use the program to obtain an estimate of J₀(0.25).

Trapezoidal Rule

The integral is:

Points for study

1. What are the input values used for?
2. What value (in algebraic terms) does T have after Line 11?
3. What is the purpose of Lines 12-17?
4. Write a program based on the pseudo-code.
5. Apply your program to Exercises 7 and 8 of the Applied Exercises.

Gauss integration formula 

The integral is:

Use the Gauss two-point formula.

Points for study

1. What is the purpose of Lines 2 and 3?
2. What changes are required to produce an algorithm based on the Gauss three-point formula?
3. Write a computer program based on this pseudo-code.
4. Use your program to solve Exercises 7 and 8 of the Applied Exercises.

5. Runge-Kutta method 

   Process the equation y' = f (x,y) and use the usual fourth-order method.
   
   

   Points for study

   1. What are the input values used for?
   2. How many times is the function f evaluated between Lines 4 and 17?
   3. Amend the pseudo-code for use with the second-order Runge-Kutta method.
   4. Write a computer program based on the pseudo-code.
   5. Use the computer program to solve Exercises 9 and 10 of the Applied Exercises.