KIMIA UNSUR
A.KELIMPAHAN UNSUR DI ALAM
Kelimpahan Karbon
Karbon di alam terdapat dalam bentuk unsure karbon,senyawa karbon organic dan anorganik
1.Unsur karbon
Unsur karbon terdapat dalam 3 bentuk,yaitu bentuk amorft,grafit dan intan.Unsur karbon dalam amorf,selain juga terdapat dialam juga dihasilkan dari pembakaran terbatas minyak bumi(jumlah oksigen terbatas sekitar 50% dari jumlah oksigen yang diperlukan untuk pembakaran sempurna).Secara alami,karbon amorf terdapat dalam serbuk gergaji,lignit batubara ,gambut,kayu,batok kelapa,dan biji-bijian.
Bentuk unsure karbon yang lain yaitu grafit,terdapat dalam bentuk padatan yang memiliki ukuran kristal dan tingkat kemurnian yang berbeda2.Grafit dapat dibuat dari kokas,menurut reaksi sebagai berikut:
C(amorf) C(grafit)
Bentuk karbon yang ketiga adalah intan.Intan secara alami diperoleh dari karbon yang dikenal tekanan dan suhu tinggi dalam perut bumi.Intan juga dapat dibuat dari grafit yang diolah pada suhu 3.000K dan tekanan lebih dari 125Kbar.Proses ini menggunakan katalis logam transisi,seperti kromium(Cr),besi(Fe),dan platina(Pt).
2.Senyawa Karbon Organik
Karbon organic merupakan penyusun makromolekul,seperti karbohydrat,protein,dan lemak.Makromolekul ini merupakan komponen penting dalam tubuh makhluk hidup.Oleh karena itu,semua jasad makhluk hidup pasti mengandung senyawa karbon organic.
3.Senyawa Karbon Anorganik
Senyawa anorganik terdiri atas karbondioksida dan garam2 karbonat.Senyawa karbondioksida merupakan komponen penyusun udara.Senyawa ini dihasilkan dari dan hewan,dan ditemukan juga pada mata air mineral
KELIMPAHAN NITROGEN
1.Unsur Nitrogen
Nitrogen merupakan komponen gas terbesar dalam udara.Nitrogen merupakan gas yang tidak reaktif serta memiliki titik didih.
Nitrogen juga merupakan unsure makro yang sangat diperlukan makhluk hidup.Perubahan dari unsure nitrogen menjadi senyawa nitrogen terjadi melalui siklus nitrogen yang berlangsung melalui 2 cara
a).Dengan adanya kilat,gas nitrogen dan oksigen dapat bereaksi dan membentuk oksida nitrogen.kemudian,oksida nitrogen ini akan larut dan terbawa oleh airhujan sehingga membentuk senyawa nitrat yang kemudian diserap oleh tumbuhan.
b).Gas nitrogen difiksasi oleh suatu bakteri yang hidup bebas atau bersimbiosis dengan akar tanaman kacang2an,seperti kacang merah
KELIMPAHAN OKSIGEN
1)Kelimpahan Oksigen
kandungan oksogen di udara sekitar 21%.Diatmosfer,terdapat oksogen dalam bentuk molekul diatomic,adapun yang terletak dia tas lapisan atmosfer terdapat dalam bentuk monoatomik dan triatomik.Gejala perubahan benruk molekul ini disebut alotropi,Gas oksigen bersifat tidak berwarna,tidak berbau,tidak beasa,serta memiliki titik didih-183’C.Dengan pengruh tekanan yang besar(135atm),oksigen dapat disimpan didalam tabung yang terbuat dari baja.Oksigen bersifat nonpolar,tetapi dapat larut dalam air.
2)Senyawa Oksigen
Air merupakan senyawa yang mengandung atom oksigen dan hydrogen yag sangat berperandalam kehidupan.Air merupakan senyawa yang palingbanyak terdapat dialam sehingga unsure oksigen pun merupakan unsur yang terdapat paling banyakdialam,yaitu54,8%.Senyawa lain yang mengandung oksigen yaitu silikat,sulfat,nitrat,atau fosfat.Selain itu,oksigenjuga terdapat dalam senyawa organic yaitu karbohidrat,protein,lemak,vitamin dan hormon.
Kegunaan Karbon
1)Unsur Karbon
Unsur karbon yang sering digunakan dlam kehidupan sehari2 merupakan karbon dlam bentuk intan,grafit dan amorf
a.)Intan.
Intan merupakan kristal karbon tetrahedral yang khas.Intan berwujud padatanyang sangat keras sehingga digunakan sebagai alat pemotongdan mata bor dalam penambangn minyak.Selain keras,Intan juga memiliki keundahan yang luar biasa,terutama setelah diasah oleh ahlinya.Intan yang diasahini dikenal sebagai berlian yang serring kit gunakan.
b.)Grafit
Grafit memiliki struktur kristal karbon dengan pola berlapis2 dan berbentuk heksagonal simetris.grafit memiliki banyak kegunaan,diantaranya unutk bahan pembuatan pensil,zat warna untuk cat hitam dan sebagai pelumas kering.Grafit juga digunakansebagai electrode pada batu baterai karema kemampuanya menghantarkan arus listrik.Selain itu,grafit juga digunakan dlam pembuatan baja dan batu bata tahan api.
c.)Bentuk Amorf
karbon dlam bentuk amorf,seperti arang,kokas,batubara dankarbon hitam memiliki sifat yang rapuh.Karbon amorf ini,antara lain digunakan sebagai bahan baker(batubara),zat warna hitam,tinta cetak,dan sebagai produksI pada proses peleburan logam.Karbon amorf yang diaktifkan digunakan sebagai adsorben yang dapat menyerap bau-bauan,gas beracun,mikroorganisme,dan kotoran dalam larutan.Obat sakit perut dan norit merupakan contoh karbon amorf yang dapat menyerap mikroorganisme.
Kegunaan nitrogen
1)Unsur Nitrogen
Nitrogen digunakan dalam industri farmasi untul mengusir gas oksigen dalam larutan injeksi.Nitrogen juga digunakan untuk mengusir gas oksigen dlam makanan berlemak atau berminyak agar tidak cepat tengik,ditambahkandlam roti agar tidak cepat berjamur serta digunakan untuk mengisi bola lampu.dll lihat hal 153
Kegunaan oksigen
Gas oksigen digunakan dalam pengolahan besi menjadi baja di tnur terbuka.Oksigen dlam bentuk oksiasetilena digunakan untuk membersihkan kerak besi dan menghaluskan tonjolan2 pada produk baja.selain itu,oksigen juga berperan dalam pembakaran logam,pengobatan RS dan aerasi limba
Rabu, 21 April 2010
Matematika
A Tutorial Introduction to the Lambda Calculus
Ra_ul Rojas_
FU Berlin, WS-97/98
Abstract
This paper is a short and painless introduction to the _ calculus. Originally developed in order to study some mathematical properties of ectively computable functions, this formalism has provided a strong theoretical foundation for the family of functional programming languages. We show how to perform some arithmetical computations using the _ calculus and how to de_ne recursive functions, even though functions in _ calculus are not given names and thus cannot refer explicitly to themselves.
1 De_nition
The _ calculus can be called the smallest universal programming language of the world. The _ calculus consists of a single transformation rule (variable substitution) and a single function de_nition scheme. It was introduced in the 1930s by Alonzo Church as a way of formalizing the concept of e_ective computability. The _ calculus is universal in the sense that any computable function can be expressed and evaluated using this formalism. It is thus equivalent to Turing machines. However, the _ calculus emphasizes the use of transformation rules and does not care about the actual machine implementing them. It is an approach more related to software than to hardware.The central concept in _ calculus is the \expression". A \name", also called a \variable", is an identi_er which, for our purposes, can be any of the letters a; b; c; : : :
An expression is de_ned recursively as follows:
:= j j
:= _ .
:=
An expression can be surrounded with parenthesis for clarity, that is, if E is an expression, (E) is the same expression. The only keywords used in the language are _and the dot. In order to avoid cluttering expressions with parenthesis, we adopt the convention that function application associates from the left, that is, the expression E1E2E3 : : :En
_Send corrections or suggestions to rojas@inf.fu-berlin.de
is evaluated applying the expressions as follows:
(: : : ((E1E2)E3) : : :En)
As can be seen from the de_nition of _ expressions given above, a single identi_er
is a _ expression. An example of a function is the following:
_x:x
This expression de_nes the identity function. The name after the _ is the identi_er of the argument of this function. The expression after the point (in this case a single x) is called the \body" of the de_nition.
Functions can be applied to expressions. An example of an application is
(_x:x)y This is the identity function applied to y. Parenthesis are used for clarity in order to avoid ambiguity. Function applications are evaluated by substituting the value of the argument x (in this case y) in the body of the function de_nition, i.e.
(_x:x)y = [y=x]x = y
In this transformation the notation [y=x] is used to indicate that all occurrences of x are substituted by y in the expression to the right.
The names of the arguments in function de_nitions do not carry any meaning by themselves. They are just \place holders", that is, they are used to indicate how to rearrange the arguments of the function when it is evaluated. Therefore (_z:z) _ (_y:y) _ (_t:t) _ (_u:u)
and so forth. We use the symbol \_" to indicate that when A _ B, A is just a
synonym of B.
1.1 Free and bound variables
In _ calculus all names are local to de_nitions. In the function _x:x we say that x is \bound" since its occurrence in the body of the de_nition is preceded by _x. A name not preceded by a _ is called a \free variable". In the expression (_x:xy) the variable x is bound and y is free. In the expression (_x:x)(_y:yx) the x in the body of the _rst expression from the left is bound to the _rst _. The y in the body of the second expression is bound to the second _ and the x is free. It is very important to notice that the x in the second expression is totally independent
of the x in the _rst expression. Formally we say that a variable is free in an expression if one of the
following three cases holds:
_ is free in .
_ is free in _ : if the identi_er 6=
and is free in .
_ is free in E1E2 if is free in E1 or if it is free in E2.
A variable is bound if one of two cases holds:
_ is bound in _ : if the identi_er =
or if is bound in .
_ is bound in E1E2 if is bound in E1 or if it is bound in E2.
It should be emphasized that the same identi_er can occur free and bound in the
same expression. In the expression
(_x:xy)(_y:y)
the _rst y is free in the parenthesized subexpression to the left. It is bound in the
subexpression to the right. It occurs therefore free as well as bound in the whole expression.
1.2 Substitutions
The more confusing part of standard _ calculus, when _rst approaching it, is the fact that we do not give names to functions. Any time we want to apply a function, we write the whole function de_nition and then procede to evaluate it. To simplify the notation, however, we will use capital letters, digits and other symbols as synonyms for some function de_nitions. The identity function, for example, can be denoted with
I which is a synonym for (_x:x).
The identity function applied to itself is the application
II _ (_x:x)(_x:x)
In this expression the _rst x in the body of the _rst expression in parenthesis is independent of the x in the body of the second expression. We can in fact rewrite the above expression as
II _ (_x:x)(_z:z)
The identity function applied to itself
II _ (_x:x)(_z:z)
yields therefore
[_z:z=x]x = _z:z _ I
that is, the identity function again.
We should be careful when performing substitutions to avoid mixing up free occurrences of an identi_er with bound ones. In the expression
(_x:(_y:xy))y
The function to the left contains a bound y, whereas the y at the right is free. An incorrect substitution would mix the two identi_ers in the erroneous result (_y:yy)
Simply by renaming the bound y to t we obtain
(_x:(_t:xt))y = (_t:yt)
which is a completely di_erent result but nevertheless the correct one.
Therefore, if the function _x: is applied to E, we substitute all free occurrences
of x in with E. If the substitution would bring a free variable of E in
an expression where this variable occurs bound, we rename the bound variable before
performing the substitution. For example, in the expression
(_x:(_y:(x(_x:xy))))y
we associate the argument x with y. In the body
(_y:(x(_x:xy)))
only the _rst x is free and can be substituted. Before substituting though, we have to rename the variable y to avoid mixing its bound with is free occurrence:
[y=x](_t:(x(_x:xt))) = (_t:(y(_x:xt)))
In normal order reduction we try to reduce always the left most expression of a
series of applications. We continue until no further reductions are possible.
2 Arithmetic
We expect from a programming language that it should be capable of doing arithmetical
calculations. Numbers can be represented in lambda calculus starting from zero and writing \suc(zero)" to represent 1, \suc(suc(zero))" to represent 2, and so on. In the lambda calculus we can only de_ne new functions. Numbers will be de_ned as functions using the following approach: zero can be de_ned as _s:(_z:z)
This is a function of two arguments s and z. We will abbreviate such expressions with more than one argument as
_sz:z It is understood here that s is the _rst argument to be substituted during the evaluation and z the second. Using this notation, the _rst natural numbers can be de_ned as
1 _ _sz:s(z)
2 _ _sz:s(s(z))
3 _ _sz:s(s(s(z))) and so on.
Our _rst interesting function is the successor function. This can be de_ned as S _ _wyx:y(wyx)
The successor function applied to our representation for zero yields
S0 _ (_wyx:y(wyx))(_sz:z)
In the body of the _rst expression we substitute all occurrences of w with (_sz:z) and this yields
_yx:y((_sz:z)yx) = _yx:y((_z:z)x) = _yx:y(x) _ 1
That is, we obtain the representation of the number 1 (remember that variable names are \dummies").
Successor applied to 1 yields:
S1 _ (_wyx:y(wyx))(_sz:s(z)) = _yx:y((_sz:s(z))yx) = _yx:y(y(x)) _ 2
Notice that the only purpose of applying the number (_sz:s(z)) to the arguments y and x is to \rename" the variables used in the de_nition of our number.
2.1 Addition
Addition can be obtained immediately by noting that the body sz of our de_nition of the number 1, for example, can be interpreted as the application of the function s
on z. If we want to add say 2 and 3, we just apply the successor function two times to 3.
Let us try the following in order to compute 2+3:
2S3 _ (_sz:s(sz))(_wyx:y(wyx))(_uv:u(u(uv)))
The _rst expression on the right side is a 2, the second is the successor function, the
third is a 3 (we have renamed the variables for clarity). The expression above reduces
to (_wyx:y((wy)x))((_wyx:y((wy)x))(_uv:u(u(uv)))) _ SS3
The reader can verify that SS3 reduces to S4 = 5.
2.2 Multiplication
The multiplication of two numbers x and y can be computed using the following
function:
(_xyz:x(yz))
The product of 2 by 2 is then:
(_xyz:x(yz))22
which reduces to
(_z:2(2z))
The reader can verify that by further reducing this expression, we can obtain the
expected result 4.
5
3 Conditionals
We introduce the following two functions which we call the values \true"
T _ _xy:x
and \false"
F _ _xy:y
The _rst function takes two arguments and returns the _rst one, the second function
returns the second of two arguments.
3.1 Logical operations
It is now possible to de_ne logical operations using this representation of the truth
values.
The AND function of two arguments can be de_ned as
^ _ _xy:xy(_uv:v) _ _xy:xyF
The OR function of two arguments can be de_ned as
_ _ _xy:x(_uv:u)y _ _xy:xTy
Negation of one argument can be de_ned as
: _ _x:x(_uv:v)(_ab:a) _ _x:xFT
The negation function applied to \true" is
:T _ _x:x(_uv:v)(_ab:a)(_cd:c)
which reduces to
TFT _ (_cd:c)(_uv:v)(_ab:a) = (_uv:v) _ F
that is, the truth value \false".
3.2 A conditional test
It is very convenient in a programming language to have a function which is true if
a number is zero and false otherwise. The following function Z complies with this
requirement
Z _ _x:xF:F
To understand how this function works, note that
0fa _ (_sz:z)fa = a
that is, the function f applied zero times to the argument a yields a. On the other
hand, F applied to any argument yields the identity function
Fa _ (_xy:y)a = _y:y _ I
6
We can now test if the function Z works correctly. The function applied to zero yields
Z0 _ (_x:xF:F)0 = 0F:F = :F = T
because F applied 0 times to : yields :. The function Z applied to any other number
N yields
ZN _ (_x:xF:F)N = NF:F
The function F is then applied N times to :. But F applied to anything is the identity, so that the above expression reduces for any number N greater than zero to
IF = F
3.3 The predecessor function
We can now de_ne the predecessor function combining some of the functions introduced above. When looking for the predecessor of n, the general strategy will be to create a pair (n; n 1) and then pick the second element of the pair as the result.
A pair (a; b) can be represented in _-calculus using the function
(_z:zab)
We can extract the _rst element of the pair from the expression applying this function
to T (_z:zab)T = Tab = a
and the second applying the function to F
(_z:zab)F = Fab = b
The following function generates from the pair (n; n1) (which is the argument p in
the function) the pair (n + 1; n 1):
_ _ (_pz:z(S(pT))(pT))
The subexpression pT extracts the _rst element from the pair p. A new pair is formed using this element, which is incremented for the _rst position of the new pair and just copied for the second position of the new pair. The predecessor of a number n is obtained by applying n times the function _ to the pair (_:z00) and then selecting the second member of the new pair:
P _ (_n:n_(_z:z00)F
Notice that using this approach the predecessor of zero is zero. This property is useful
for the de_nition of other functions.
3.4 Equality and inequalities
With the predecessor function as the building block, we can now de_ne a function which tests if a number x is greater than or equal to a number y:
G _ (_xy:Z(xPy))
7
If the predecessor function applied x times to y yields zero, then it is true that x _ y.
If x _ y and y _ x, then x = y. This leads to the following de_nition of the
function E which tests if two numbers are equal:
E _ (_xy: ^ (Z(xPy))(Z(yPx)))
In a similar manner we can de_ne functions to test whether x > y, x < y or x 6= y.
4 Recursion
Recursive functions can be de_ned in the _ calculus using a function which calls a function y and then regenerates itself. This can be better understood by considering
the following function Y:
Y _ (_y:(_x:y(xx))(_x:y(xx)))
This function applied to a function R yields:
YR = (_x:R(xx))(_x:R(xx))
which further reduced yields:
R((_x:R(xx))(_x:R(xx))))
but this means that YR = R(YR), that is, the function R is evaluated using the recursive call YR as the _rst argument.
Assume, for example, that we want to de_ne a function which adds up the _rst n
natural numbers. We can use a recursive de_nition, since Pn
i=0 i = n +Pn1
i=0 i. Let
us use the following de_nition for R:
R _ (_rn:Zn0(nS(r(Pn))))
This de_nition tells us that the number n is tested: if it is zero the result of the sum is zero. If n is not zero, then the successor function is applied n times to the recursive call (the argument r) of the function applied to the predecessor of n.
How do we know that r in the expression above is the recursive call to R, since functions in _ calculus do not have names? We do not know and that is precisely
why we have to use the recursion operator Y. Assume for example that we want to add the numbers from 0 to 3. The necessary operations are performed by the call: YR3 = R(YR)3 = Z30(3S(YR(P3)))
Since 3 is not equal to zero, the evaluation reduces to
3S(YR2) that is, the sum of the numbers from 0 to 3 is equal to 3 plus the sum of the numbers from 0 to 2. Successive recursive evaluations of YR will lead to the correct _nal result. Notice that in the function de_ned above the recursion will be broken when the argument becomes 0. The _nal result will be
3S2S1S0
that is, the number 6.
8
5 Projects for the reader
1. De_ne the functions \less than" and \greater than" of two numerical arguments.
2. De_ne the positive and negative integers using pairs of natural numbers.
3. De_ne addition and subtraction of integers.
4. De_ne the division of positive integers recursively.
5. De_ne the function n! = n _ (n 1) _ _ _ 1 recursively.
6. De_ne the rational numbers as pairs of integers.
7. De_ne functions for the addition, subtraction, multiplication and division of
rationals.
8. De_ne a data structure to represent a list of numbers.
9. De_ne a function which extracts the _rst element from a list.
10. De_ne a recursive function which counts the number of elements in a list.
11. Can you simulate a Turing machine using _ calculus?
References
[1] P. M, Kogge, The Architecture of Symbolic Computers, McGraw-Hill, New York,
1991, chapter 4.
[2] G. Michaelson, An Introduction to Functional Programming through Lambda Calculus,
Addison-Wesley, Wokingham, 1988.
[3] G. Revesz, Lambda-Calculus Combinators and Functional Programming, Cambridge
University Press, Cambridge, 1988, chapters 1{3.
Ra_ul Rojas_
FU Berlin, WS-97/98
Abstract
This paper is a short and painless introduction to the _ calculus. Originally developed in order to study some mathematical properties of ectively computable functions, this formalism has provided a strong theoretical foundation for the family of functional programming languages. We show how to perform some arithmetical computations using the _ calculus and how to de_ne recursive functions, even though functions in _ calculus are not given names and thus cannot refer explicitly to themselves.
1 De_nition
The _ calculus can be called the smallest universal programming language of the world. The _ calculus consists of a single transformation rule (variable substitution) and a single function de_nition scheme. It was introduced in the 1930s by Alonzo Church as a way of formalizing the concept of e_ective computability. The _ calculus is universal in the sense that any computable function can be expressed and evaluated using this formalism. It is thus equivalent to Turing machines. However, the _ calculus emphasizes the use of transformation rules and does not care about the actual machine implementing them. It is an approach more related to software than to hardware.The central concept in _ calculus is the \expression". A \name", also called a \variable", is an identi_er which, for our purposes, can be any of the letters a; b; c; : : :
An expression is de_ned recursively as follows:
An expression can be surrounded with parenthesis for clarity, that is, if E is an expression, (E) is the same expression. The only keywords used in the language are _and the dot. In order to avoid cluttering expressions with parenthesis, we adopt the convention that function application associates from the left, that is, the expression E1E2E3 : : :En
_Send corrections or suggestions to rojas@inf.fu-berlin.de
is evaluated applying the expressions as follows:
(: : : ((E1E2)E3) : : :En)
As can be seen from the de_nition of _ expressions given above, a single identi_er
is a _ expression. An example of a function is the following:
_x:x
This expression de_nes the identity function. The name after the _ is the identi_er of the argument of this function. The expression after the point (in this case a single x) is called the \body" of the de_nition.
Functions can be applied to expressions. An example of an application is
(_x:x)y This is the identity function applied to y. Parenthesis are used for clarity in order to avoid ambiguity. Function applications are evaluated by substituting the value of the argument x (in this case y) in the body of the function de_nition, i.e.
(_x:x)y = [y=x]x = y
In this transformation the notation [y=x] is used to indicate that all occurrences of x are substituted by y in the expression to the right.
The names of the arguments in function de_nitions do not carry any meaning by themselves. They are just \place holders", that is, they are used to indicate how to rearrange the arguments of the function when it is evaluated. Therefore (_z:z) _ (_y:y) _ (_t:t) _ (_u:u)
and so forth. We use the symbol \_" to indicate that when A _ B, A is just a
synonym of B.
1.1 Free and bound variables
In _ calculus all names are local to de_nitions. In the function _x:x we say that x is \bound" since its occurrence in the body of the de_nition is preceded by _x. A name not preceded by a _ is called a \free variable". In the expression (_x:xy) the variable x is bound and y is free. In the expression (_x:x)(_y:yx) the x in the body of the _rst expression from the left is bound to the _rst _. The y in the body of the second expression is bound to the second _ and the x is free. It is very important to notice that the x in the second expression is totally independent
of the x in the _rst expression. Formally we say that a variable
following three cases holds:
_
_
and
_
A variable
_
or if
_
It should be emphasized that the same identi_er can occur free and bound in the
same expression. In the expression
(_x:xy)(_y:y)
the _rst y is free in the parenthesized subexpression to the left. It is bound in the
subexpression to the right. It occurs therefore free as well as bound in the whole expression.
1.2 Substitutions
The more confusing part of standard _ calculus, when _rst approaching it, is the fact that we do not give names to functions. Any time we want to apply a function, we write the whole function de_nition and then procede to evaluate it. To simplify the notation, however, we will use capital letters, digits and other symbols as synonyms for some function de_nitions. The identity function, for example, can be denoted with
I which is a synonym for (_x:x).
The identity function applied to itself is the application
II _ (_x:x)(_x:x)
In this expression the _rst x in the body of the _rst expression in parenthesis is independent of the x in the body of the second expression. We can in fact rewrite the above expression as
II _ (_x:x)(_z:z)
The identity function applied to itself
II _ (_x:x)(_z:z)
yields therefore
[_z:z=x]x = _z:z _ I
that is, the identity function again.
We should be careful when performing substitutions to avoid mixing up free occurrences of an identi_er with bound ones. In the expression
(_x:(_y:xy))y
The function to the left contains a bound y, whereas the y at the right is free. An incorrect substitution would mix the two identi_ers in the erroneous result (_y:yy)
Simply by renaming the bound y to t we obtain
(_x:(_t:xt))y = (_t:yt)
which is a completely di_erent result but nevertheless the correct one.
Therefore, if the function _x:
of x in
an expression where this variable occurs bound, we rename the bound variable before
performing the substitution. For example, in the expression
(_x:(_y:(x(_x:xy))))y
we associate the argument x with y. In the body
(_y:(x(_x:xy)))
only the _rst x is free and can be substituted. Before substituting though, we have to rename the variable y to avoid mixing its bound with is free occurrence:
[y=x](_t:(x(_x:xt))) = (_t:(y(_x:xt)))
In normal order reduction we try to reduce always the left most expression of a
series of applications. We continue until no further reductions are possible.
2 Arithmetic
We expect from a programming language that it should be capable of doing arithmetical
calculations. Numbers can be represented in lambda calculus starting from zero and writing \suc(zero)" to represent 1, \suc(suc(zero))" to represent 2, and so on. In the lambda calculus we can only de_ne new functions. Numbers will be de_ned as functions using the following approach: zero can be de_ned as _s:(_z:z)
This is a function of two arguments s and z. We will abbreviate such expressions with more than one argument as
_sz:z It is understood here that s is the _rst argument to be substituted during the evaluation and z the second. Using this notation, the _rst natural numbers can be de_ned as
1 _ _sz:s(z)
2 _ _sz:s(s(z))
3 _ _sz:s(s(s(z))) and so on.
Our _rst interesting function is the successor function. This can be de_ned as S _ _wyx:y(wyx)
The successor function applied to our representation for zero yields
S0 _ (_wyx:y(wyx))(_sz:z)
In the body of the _rst expression we substitute all occurrences of w with (_sz:z) and this yields
_yx:y((_sz:z)yx) = _yx:y((_z:z)x) = _yx:y(x) _ 1
That is, we obtain the representation of the number 1 (remember that variable names are \dummies").
Successor applied to 1 yields:
S1 _ (_wyx:y(wyx))(_sz:s(z)) = _yx:y((_sz:s(z))yx) = _yx:y(y(x)) _ 2
Notice that the only purpose of applying the number (_sz:s(z)) to the arguments y and x is to \rename" the variables used in the de_nition of our number.
2.1 Addition
Addition can be obtained immediately by noting that the body sz of our de_nition of the number 1, for example, can be interpreted as the application of the function s
on z. If we want to add say 2 and 3, we just apply the successor function two times to 3.
Let us try the following in order to compute 2+3:
2S3 _ (_sz:s(sz))(_wyx:y(wyx))(_uv:u(u(uv)))
The _rst expression on the right side is a 2, the second is the successor function, the
third is a 3 (we have renamed the variables for clarity). The expression above reduces
to (_wyx:y((wy)x))((_wyx:y((wy)x))(_uv:u(u(uv)))) _ SS3
The reader can verify that SS3 reduces to S4 = 5.
2.2 Multiplication
The multiplication of two numbers x and y can be computed using the following
function:
(_xyz:x(yz))
The product of 2 by 2 is then:
(_xyz:x(yz))22
which reduces to
(_z:2(2z))
The reader can verify that by further reducing this expression, we can obtain the
expected result 4.
5
3 Conditionals
We introduce the following two functions which we call the values \true"
T _ _xy:x
and \false"
F _ _xy:y
The _rst function takes two arguments and returns the _rst one, the second function
returns the second of two arguments.
3.1 Logical operations
It is now possible to de_ne logical operations using this representation of the truth
values.
The AND function of two arguments can be de_ned as
^ _ _xy:xy(_uv:v) _ _xy:xyF
The OR function of two arguments can be de_ned as
_ _ _xy:x(_uv:u)y _ _xy:xTy
Negation of one argument can be de_ned as
: _ _x:x(_uv:v)(_ab:a) _ _x:xFT
The negation function applied to \true" is
:T _ _x:x(_uv:v)(_ab:a)(_cd:c)
which reduces to
TFT _ (_cd:c)(_uv:v)(_ab:a) = (_uv:v) _ F
that is, the truth value \false".
3.2 A conditional test
It is very convenient in a programming language to have a function which is true if
a number is zero and false otherwise. The following function Z complies with this
requirement
Z _ _x:xF:F
To understand how this function works, note that
0fa _ (_sz:z)fa = a
that is, the function f applied zero times to the argument a yields a. On the other
hand, F applied to any argument yields the identity function
Fa _ (_xy:y)a = _y:y _ I
6
We can now test if the function Z works correctly. The function applied to zero yields
Z0 _ (_x:xF:F)0 = 0F:F = :F = T
because F applied 0 times to : yields :. The function Z applied to any other number
N yields
ZN _ (_x:xF:F)N = NF:F
The function F is then applied N times to :. But F applied to anything is the identity, so that the above expression reduces for any number N greater than zero to
IF = F
3.3 The predecessor function
We can now de_ne the predecessor function combining some of the functions introduced above. When looking for the predecessor of n, the general strategy will be to create a pair (n; n 1) and then pick the second element of the pair as the result.
A pair (a; b) can be represented in _-calculus using the function
(_z:zab)
We can extract the _rst element of the pair from the expression applying this function
to T (_z:zab)T = Tab = a
and the second applying the function to F
(_z:zab)F = Fab = b
The following function generates from the pair (n; n1) (which is the argument p in
the function) the pair (n + 1; n 1):
_ _ (_pz:z(S(pT))(pT))
The subexpression pT extracts the _rst element from the pair p. A new pair is formed using this element, which is incremented for the _rst position of the new pair and just copied for the second position of the new pair. The predecessor of a number n is obtained by applying n times the function _ to the pair (_:z00) and then selecting the second member of the new pair:
P _ (_n:n_(_z:z00)F
Notice that using this approach the predecessor of zero is zero. This property is useful
for the de_nition of other functions.
3.4 Equality and inequalities
With the predecessor function as the building block, we can now de_ne a function which tests if a number x is greater than or equal to a number y:
G _ (_xy:Z(xPy))
7
If the predecessor function applied x times to y yields zero, then it is true that x _ y.
If x _ y and y _ x, then x = y. This leads to the following de_nition of the
function E which tests if two numbers are equal:
E _ (_xy: ^ (Z(xPy))(Z(yPx)))
In a similar manner we can de_ne functions to test whether x > y, x < y or x 6= y.
4 Recursion
Recursive functions can be de_ned in the _ calculus using a function which calls a function y and then regenerates itself. This can be better understood by considering
the following function Y:
Y _ (_y:(_x:y(xx))(_x:y(xx)))
This function applied to a function R yields:
YR = (_x:R(xx))(_x:R(xx))
which further reduced yields:
R((_x:R(xx))(_x:R(xx))))
but this means that YR = R(YR), that is, the function R is evaluated using the recursive call YR as the _rst argument.
Assume, for example, that we want to de_ne a function which adds up the _rst n
natural numbers. We can use a recursive de_nition, since Pn
i=0 i = n +Pn1
i=0 i. Let
us use the following de_nition for R:
R _ (_rn:Zn0(nS(r(Pn))))
This de_nition tells us that the number n is tested: if it is zero the result of the sum is zero. If n is not zero, then the successor function is applied n times to the recursive call (the argument r) of the function applied to the predecessor of n.
How do we know that r in the expression above is the recursive call to R, since functions in _ calculus do not have names? We do not know and that is precisely
why we have to use the recursion operator Y. Assume for example that we want to add the numbers from 0 to 3. The necessary operations are performed by the call: YR3 = R(YR)3 = Z30(3S(YR(P3)))
Since 3 is not equal to zero, the evaluation reduces to
3S(YR2) that is, the sum of the numbers from 0 to 3 is equal to 3 plus the sum of the numbers from 0 to 2. Successive recursive evaluations of YR will lead to the correct _nal result. Notice that in the function de_ned above the recursion will be broken when the argument becomes 0. The _nal result will be
3S2S1S0
that is, the number 6.
8
5 Projects for the reader
1. De_ne the functions \less than" and \greater than" of two numerical arguments.
2. De_ne the positive and negative integers using pairs of natural numbers.
3. De_ne addition and subtraction of integers.
4. De_ne the division of positive integers recursively.
5. De_ne the function n! = n _ (n 1) _ _ _ 1 recursively.
6. De_ne the rational numbers as pairs of integers.
7. De_ne functions for the addition, subtraction, multiplication and division of
rationals.
8. De_ne a data structure to represent a list of numbers.
9. De_ne a function which extracts the _rst element from a list.
10. De_ne a recursive function which counts the number of elements in a list.
11. Can you simulate a Turing machine using _ calculus?
References
[1] P. M, Kogge, The Architecture of Symbolic Computers, McGraw-Hill, New York,
1991, chapter 4.
[2] G. Michaelson, An Introduction to Functional Programming through Lambda Calculus,
Addison-Wesley, Wokingham, 1988.
[3] G. Revesz, Lambda-Calculus Combinators and Functional Programming, Cambridge
University Press, Cambridge, 1988, chapters 1{3.
Langganan:
Postingan (Atom)