### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Programming Languages I COP 4020

University of Central Florida

GPA 3.78

### View Full Document

## 28

## 0

## Popular in Course

## Popular in Computer Programming

This 40 page Class Notes was uploaded by Luisa Beer on Thursday October 22, 2015. The Class Notes belongs to COP 4020 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 28 views. For similar materials see /class/227469/cop-4020-university-of-central-florida in Computer Programming at University of Central Florida.

## Similar to COP 4020 at University of Central Florida

## Popular in Computer Programming

## Reviews for Programming Languages I

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15

Group 2 Notes Brett Downs amp Ignacio Garcia Turing machines are eXtremely basic symbolmanipulating devices which can be adapted to recreate the logic of any computer that could be built These machines were described by Alan Turing in 1936 Von Neumann Architecture refers to a computer design model that uses a single storage structure to hold both instructions and data this kind of computer implements a Turing Machine There are different ways one can calculate functions Alonzo Church The ChurchiTuring thesis stated that Turing machines and recursive functions are equivalent quotEvery 39function which would naturally be regarded as computable39 can be computed by a Turing machine quotAlonzo Church Because any computer program can be translated into a Turing machine and any Turing machine can be translated into any generalpurpose programming language we know that any generalpurpose programming language is sufficient to express any algorithm Primitive Recursive Functions F N gt N l l Natural Natural Number Numbers Initial functions rimitive recursive functions Zero function ZX 0 VX N Successor function SX X l VX N Projection lnction PquotkX1 X2 X3 X4 Xn1 Xn Xk l k n n of arguments k one in which is selected Using these functions we can create recursive functions Rules Composition Suppose the functions g1 g2 g3 gm and h are primitive recursive where the domain of gl is Nquot and the domain of h is Nm T arguments X X1 X2 X3 xn Then fX hglX g2X g3X gmX is primitive recursive Recursion Suppose g and h are primitive recursive functions where the domain of g is in NH and the domain of h is Nmz Then the pair of equations 1 fX 0 gX Boundary ConditionStop 2 fX yl hX y fX y Recursion equation 1 Defines a pr1m1t1ve recurs1ve function w1th doma1n Nn amp ADDXY X Y Formal De nition ADDX0 IX P11X X ADDXY1 H X Y ADDXY HXYZ SP33X Y ADDXY ADD23 SP3323ADD22 033303 033302 ADD21 8033303 8033302 SP3321 ADD20 8033303 8033302 sP33212 033303 033302 Sam 8033303 8033023 8033303 83 SP33234 34 5 Multiplication MULX0 ZX MULX Y1 HXYMULXY HXYZ ADDP31XYZ P33XYZ ADDXYMULXY Factorial FACX X FAC0 l FACX1 MULX1FACX Pred PREDO Z0 PREDY1 P21Y PREDY l Calculus The goal of Xcalculus is to simplify the notion of computable functions A calculus is a notation that can be manipulated mechanically to achieve some end One reason for developing a calculus is that by reducing some process to a set of simple mechanical rules one decreases the chance of making errors Scope Scope where a variable is visible to a range of statements or where the variable can be accessed Binding declared in accessible etc Bound Identi ers are often called bound variables EX 221 i2 1 is the bound identi er bound identi ers can change without altering the meaning of a formula If we change a free variable we change the meaning of the expression The binding site for an identi er determines the scope of the identi er Q XlX20iYlYE0 vXx1gtxVyy1gty Q 12quot1 jz 17 9 bound Identi er is j free variable is i j is bound by the summation operation2 which is called the binding state Q j is free inj2 17 9 but bound in Zquotj1 aizj2 Scope EX Scope ofX L X l X gt y l l l l l Free occurrence of y l Bound occurrence of X Binding site of X Q Program l Var X l Brocedure 7 l l Var y l l l l Scope of y l l l L J l End Nested Scopes Ex Zm1112nj1j1 a l l 1 Scope ofj l l l 1 Scope ofI l Calculus It is a theory of functions developed by Alonzo Church In 1920 Moses Schonfinkel developed a theory of functions base of combinations From that in 1930 Haskell curry rediscovered and extended schonfinkel s theory and showed that it was equivalent to XCalculus From there in 1930 Alonzo Church developed XCalculus From there in 1950 SC Kleene showed that kCalculus was a universal computing systemany computable function can be expressed and evaluated using XCalculus From there in 1950 John Mccarthy who was inspired by XCalculus invented the programming language LISP kCalculus is equivalent to Turing machines but kCalculus emphasizes the use of transformation rules and doesn t care about the actual machine 39 39 ino them kCalculus is more related to software than hardware The kCalculus is a notation for de ning functions Any computable function can be expressed and evaluated using XCalculus The central concept in XCalculus is the expression Each 7 expression denotes a function 0 is a Xexpression to represent the number zero There are just 3 kinds of Xexpression and using BNF the syntax of Xexpressions are lt Xexpressiongt ltvariablegt llt Xexpressiongtlt kexpressiongt l Mvariablegtlt kexpressiongt If V ranges over the class of ltvariablegt and E El E2 range over the syntax of class lt 7 expressiongt then the BNF simpli es to E V Variable lElE2 Application combinati0nProcedure call l AVE Abstraction Q 7txx denotes the identity function Functions can be applied to expressions XxxE Xxxx5 3 5xxx 3 55 Function applications are evaluated by substituting the value of the argument 7 xxE 3 Exx y E Xx max LffXEX 3 LffE Ifwe apply XffEE 3 fEE f 3 E E kCalculus was the basis for LISP The meaning of Ex all occurrences of x are substituted by E in the expression to the right Q Xxxy 3 yxx 3 y Xxxy 3 Xyy 3 y kx7tyxy 23 2 Xyxy 2 3x 2 Xy3y 2 2 3y2y 2 32 2 5 Conversion Rules An arithmetic expression like 235 can be represent as a kexpression and its value 25 can also be represented as a Xexpression The process of simplifying 235 is called conversion or reduction l Renaming Rule 0cconversion or xreduction one expression may be replace to another by changing a bound identi er throughout its scope to any other identi er that doesn t occur within that scope One Abstraction of the form AVE can be converted to XvEv v provided that the substitution v for v is valid in E Q hxx22xl 3a Xmmz2ml E XXX 3 1 haa 3a ng 3 7thh E XX7tyXy 3 ha7tyay Substitution Rule BReduction or BConversion Any application ofthe form 7 VE1E2 can be converted to E1 EzV provided the substitution of V in E1 is valid BReduction is like the evaluation of a function call in a programming language in 7 VE1Ez the body of the function XVE1 is evaluated in an environment in which the formal parameter V is bound to the actual parameter E2 m XXFXE 2 FE E 7 X7tyadd xy3 3 kyadd X3 E kyadd 3y4 3 add 34 3 7 Nonvalid EX 7 X7tyadd xySquare y 3 kyadd Square yy kyadd xySquare yX is not valid because y is free in Square y but becomes bound after substitution for X in XXJty add xy E 7 X7tyxy12 3 ky1y2 3 12 3 3 EX LXLyX2yZZ15 3 ky7tzzl2y5 3 kzzl25 3 Xzzl10 3 101 3 11 Ex XX7tyyX3 4 701 2 3 Xyy3 4 701 2 3 791 23 4 3 3 42 3 7 2 3 9 In Xexpressions all functions have one variable Functions of several variables may be expressed as a function of one variable through carrying HXy Xy comes from Hzxz gt z With carrying we can input one variable at a time into separate functions The rst function takes the rst argument X and returns a function that will take the second variable y and will in turn provide the desired output to create the same function by carrying Fz gt z gtz Gz gtz o F maps integers to a function while G maps integers to integers o FX returns a function GX that provides the appropriate result when supplied with y I F2 3 G2 when G2y 3 2y I F23 3 G23 3 23 3 5 o In Xcalculus this function is described as XX7tyxy o For function applications XX7tyxy23 3 ky2y3 3 23 3 5 To be able to program significant function in kcalculus it is convenient to have a way to attach names to Xexpressions amp Plusp 3 XXX 2 0 Minusp 3 XXX lt 0 Succ 3 hxxl Square 3 7LXXX MinuspSucc2 3 XXX lt 0Succ2 3 Succ2 lt 0 3 XXX12 lt 0321lt 0 3 3 lt 0 3 False l Expressions to handle truth values if c TF Selects T if c is true 3 LTFT we always select True Selects F ifc is false 3 7 TFF we always select False E Less2626 3 True26 3 7 TFT26 3 2 True gt E1E2 3 True ElEz 3 LTFTE1E2 3 E1 False gt E1E2 3 False ElEz 3 KTFFE1E2 3 E2 Concurrency Chapter 13 1 e 13 3 Cnnclln39entl rngxams m1 Inlss 7 example 7 Program Prncedure T1 Prncedure T2 task T1 rew aeuvauor reeord task T2 rew aeuvauor reeord Program ume T10 T20 ume m reahty there 15 only one program m exeeuuor m a smgle CPU setup Progam T1 T20 ume contextg39 We Prat esses ImponantTerm Prueess e A program m execuuon ereue pracess m m N mm D V usmg threads ImponantTerm Thread 7 A umt of exeeuuor of a process rs neededto complete the context svmch The TCB Thread Control Block s the part ofthe PCB that athread consists of mxt pruness anew mxt pruness Critical Seetinns thread mes to aeeess the same data ea11ed sharedData ImportantTerm Shared Data 7 Data that more then one process or thread has aeeess to ImportantTerm Critical Seednhe Code that aeeesses andmuses SharedData seetron may be drtrereht rexampler sharedvu ecer ymcessl El grams PCEZ land x land x add lEEIquot add lEEIquot stare x stare x r h or x If x0 at the start then x should equal 200 when the 2 processes eomplete exeeuaor Ihrs rs not always the ease though shared var 1m x 1m x ma mu ma mu stare x stare x m r information from the CPst savedto the PCB Pcm E 1 51m V y 2 Pcaz muss El muss 1m x ma mu stare x prrocessZ then starts and completes 1 m P0132 PCB shared var mm El pvtwet land x land x mannaquot annulnnquot sme x sme x shared var pracessl praces PCEZ PCB land x land x mannaquot mannaquot sme x nun x cpu then when processl 15 eontext smtehed baek Into the CPU the reglster values wlll be loaded from the PcBl from when they were saved shared var PCB pracessl HmcessZ PCEZ land x land x mannaquot mannaquot sme x sme x When processl eonanues to eneeute the nal value ofx ls only 100 not 200 has sww39 mas 39 39 139 139 land x add mu sme x shared var mmol Mme land x land x add lEEIquot add lEEIquot nun x slore x threads it 15 ealled aRaee condlhon ImponantTerm Race Cnnditinn 7 When the behavlor of a program depends on the order threadsprocesses execute than ntlcal sectlons Hardware Snllltinn one method for deallng wlth raee condlnons developed by IBM ls a hardware lnstxucnon called test amp setquot whlch ls executed atomlcally 1t ls done ln one step lt cannoth lntermpted mldway no and nl eall y ady When aproeess has n n sectlon ltlmggt y lF m V Wamn ImponantTerm Busy Waitin rW hen aproeess ls stuckln aloop warang for another proeess to leave a enaeal seeaon semaphore has a value and a pormer Semaphures semuphore test a setquot busy Wamng m r n w r process A process a process 0 P5 P5 P5 u cm seeuoh u cm seeuoh u cm seeuoh Vs Vs Vs 12 and v ruheu39uhs Psem aphore s lt 5 d eurrem proee adouo semaphore q anowrmo erruea1 seeuoh Vsemaphore s 5H xf s lt 0 adouo ready queue ags that mxghthappen ss remove from proeess queue ueue dequeue proeess from semaphore queue Example mmal state pr cnucal secuon Process can conunue semaphnxe s D Mwwd semaphnxe s PrndncerCnnmmer Emblem consumer or consumers that rs usmg that something Ins an acumcy m amajor subject of sharedresources Synchromzauon can pxckxtup nrouucer buffershelf ms Hpmdnce H Mk rrom buffer H mm W1 Home consumer takes another nem mouucer buffershelf gamma Hpmdnce H Mk rrom buffer H mu o buffer Hconsume unul the producer places anothentem on the shelf nrouucer buffershelf mmm Hpmdnce H Mk rrom buffer murmurquot Home quotm r r r buffer 15 empty m m r r takes prooluet from the buffer The solutroh to thrs problem ls to have 3 semaphores r buffer at atrme It therefore ls set to l llke aregular shareolresouree semaphore The proolueer auol eohsumer both eall Pmutex before aeeessmg the buffer and Vmutex upoh leavlng the buffer pmdncex buffershelf gamma llproeluee Pmnex Pmnex H lakz mm buffer H addm buffer Wmulex Vmnex lcansnme p auu ah WM r t t t r auolthe proolueerrs allowedto make auotherprooluet prouueer hurrershelr gamma Hpmdnce Pmnex Wm H lure mm hurrer Pmnex vltmutex u mu m hurrer WM Wmmex Hcansnme It starts at 0 p makes an rtem rt ealls VEmpty mdreatmg that there ls another rtem oh the buffer Before taklng L L wle m r l V mdreate that the eohsumerrs taluhg rt off w buffershelf WNW llprouuee Pe l Mull Pmnex Pmnex H lure from hurrer H uuulo hurrer Wmme Wmme Wm Vempty lleohsume Therefore V2mpty eohsumer takes another rtem off the buffer and ealls Vfuu u um r buffer Example As an example lf we haol 2 eohsumers and we wauteolto prooluee 100 umts ofprooluet we need some way for the eohsumers to know when to stop ymdncex buffershelf Mam canm1nn mam lamp mu umes pmdnce 1 Wmmex vumpw gt smp cansnmex gt 2152 lt Hcansume Notes on recurive functions Euripides Montagne School of Electrical Engineering and Computer Science University of Central Florida COP 4020 Programming Languages Primitive recursive functions 0 A Turing machine is a symbol manipulating device proposed by Alan Turing in 1936 as a model of computation o The Von Neumann architecture is a concrete rep resentation of the Turing model of computation 0 Another approach to carry out computation is by means of recursive function theory The Church Thesis states that as computation mod els Turing machines and recursive functions are equiv alent Initial functions 0 Recursive function theory is the study of a small initial class of primitive functions which can be used to build a large class of computable func tions 0 We can consider that any computable function f can be expressed as a function from N to N where N stands for nonnegative integers f WY gt W where nm N The initial functions are a set of primitive recursive functions which are accepted as selfevidently com putable functions These functions are The zero function The successor function and the projec tion function Zero Function The Zero function is a function that always return zero and is defined as Z1O VxEN Successor function The Successorfunction when applied to 13 returns 33 1 and is defined as Sax I 1 WEN Projection function The projection function selects one of the arguments from the argument list and is defined as Hga1x2x3xk13n Zxk withl S k n where n stands for the number of arguments and k represents the selected argument Computing with functions Using the initial functions one can build other more complex primitive recursive functions by applying the following rules Combination let us f and g be primitive recursive functions defined as fNk gtNm and gNk gtNn Withkn N The combination of these two functions is expressed as f X g Nk gt Nmn and is defined by f X 9 figi where f x1 2 5133 33k Example H3x17 542 H 542H 542 42 3 Composition let us f and g be primitive recursive functions defined as fiNk gtNm and giNm gtNn with kmn e N The composition of these two functions is expressed as g o f I Nk gt N and is defined by f o 9 90 Where i 2 131 132 5133 13k Example SZ1 80 2 1 Primitive recursion let us 9 be a primitive recursive function with aritynumber of arguments n defined as gNk gtN and let us h be a primitive recursive function with arity n 2 defined as hINk2 gtN then the functionf with arity n I 1 is said to be defined by primitive recursion from g and h if KEG 9 ffy1 hfyffy where x1x2x3xk The first equation defines the boundary condition and is applied when last argument is O the second one is the recursive equation and is applied when the last argument is not 0 Examples of primitive recursion Example The ADD function can be defined using primitive recursion as ADD1O Haa ADDay1 8H xyADDxy Now we can compute ADD32 as follows ADD3 2 SH 3 1 ADD3 1 SH 3 1 SH 3 o ADD3 o 8H 318H 30H3 SH 3 1 SH 3 o 3 SH 3 1 33 2 SH 314 84 2 5 The initial functions are primitive recursive and func tions built up from the initial functions and a finite ap plication of composition combination and primitive re cursion are also primitive recursive functions 6 Constructing more primitive recursive functions Example The MULT function can be defined using primitive recursion as MULT130 2 217 32 o MULTxy1 ADDHJ3xH xy MULTay MULT can be defined as well in a concise form as MULT13 O O MULT13y 1 ADDaMULTay Using this short notation we will introduce more re cursive functions Factorial can be defined as FACTO 1 FACTy 1 MULTy 1FACTxy Predecessor can be defined as PREDO o PREDay 1 17 PREDy We can consider predecessor as the inverse of suc cessor ie PRED54 Pred00 using PRED we can define MONUS substraction overthe natural num bers Monus can be defined as MONUSO H MONUS13y 1 PREDMONUSxy Ifa 2 y MONUS13y iS a y othenvise MONUS13 y O The short notation for the function MONUS13 y is x 4 y Thus the function equality EQ13 y can be defined as EQC my 14y4x my f EQ13y 1 then 1 y othenvise EQ13y O THE PROBLEM OF NESTED MONITOR CALLS Andrew Lister Department of Computer Science University of Queensland St Lucia Queensland 4067 Australia The concept of a monitor has been developed by Hoare l and Brinch Hansen 2 3 4 into a powerful and useful tool for building well structured and reliable operating systems Some experience of the author in constructing monitor based systems 5 6 has highlighted a problem of implementation which does not seem to have been explicitly addressed in the literature This article describes the problem and discusses some inadequate solutions its aim is to solicit better solutions from workers in the field One of the fundamental attributes of a monitor is that executions of its procedures are mutually exclusive in time This restriction is a necessary condition for ensuring the integrity of the data and resources administered by a monitor Looked at from the point of view of correctness proofs the mutual exclusion attribute allows one to demonstrate that certain invariants remain true under execution of monitor procedures 1 7 To enter a monitor a process must therefore gain exclusion for that monitor the exclusion is released on monitor exit Release of exclusion is also implied by executing a wait operation if this were not the case there would be no way for another process to enter the monitor and perform the corresponding signal operation Wait and signal are the process synchronisation primitives suggested by Hoare slightly different primitives are used by Brinch Hansen Strictly speaking execution of a signal operation should also imply release of exclusion since the process which is signalled is immediately resumed However it seems to be common universal practice to place all signal operations at the end of procedure bodies so that exclusion is released in any case by exit from the monitor Acquisition and release of exclusion leads to a problem when monitor calls are nested For example suppose that a procedure procl of a monitor monl calls a procedure pPOCZ of monitor monZ If procZ contains a wait operation should exclusion be released on both monl and monZ or on monZ alone The two options are discussed below First consider the option of releasing exclusion on only the last monitor called eg on monZ alone This has the alarming implication that all monitors back to the original call are inaccessible to other processes This could have adverse effects on system performanCe in particular it could lead to deadlock if the resumption of the waiting process is dependent on some other process executing a similar sequence of monitor calls in order to effect a signal operation Such a situation might be expected in any neatly hierarchical system in which the control paths leading to matching wait and signal Operations pass through the same monitors The alternative option that of releasing exclusion at all levels requires a means of recording what exclusions a process possesses at the time it executes wait A stack seems the obvious mechanism execution of wait would cause the release of all exclusions currently stacked However the resumption of a process after a signal operation requires that all these exclusions be restored It is difficult to see how this can be achieved since some of the exclusions might at that time belong to other processes A further implication of this second option is that any monitor invariant associated with an outer level monitor must hold at the point at which a nested monitor call is made In the example above the invariant for monl must hold when monZ is called This is necessary in order to ensure that any other process which enters the outer level monitor will find the local data in the state it expects Again it is difficult to see how this can be achieved in general The above analysis shows that both Options have severe disadvantages A rather crude way of avoiding them is to implement a single global exclusion mechanism for all monitors rather than implement local exclusion for each monitor separately If a global mechanism is used then only one level of exclusion need be maintained the question of how many exclusions to release on a wait operation does not arise Of course the gain in simplicity is not without cost since the degree of potential parallelism in the system is artificially reduced This technique has been used by the author in a small pilot operating system 6 where interrupt disablement is used as a global exclusion mechanism This is successful in a small system on a single CPU machine but it is doubtful whether it would be acceptable in a more realistic situation Another even cruder way around the problem is to forbid nested monitor calls completely This is a severe restriction which is unacceptable in any system which is built hierarchically It has however been adopted in at least one implementation 8 The only implementation known to the author in which the nested call problem is tackled head on rather than being merely avoided is that by BrinchHansen 3 In this implementation a local exclusion mechanism is used for each monitor and a wait operation causes release of exclusion on only the most recently called monitor It is not clear what measures if any are taken to avoid the degradation of performance and potential for deadlock mentioned earlier The partial solutions described above are clearly far from satisfactory The author would be pleased to learn of any better solutions or is the nested monitor call problem intractable 6 REFERENCES 1 21 Monitors an operating system structuring concept Comm ACM 17 p549 1974 HOARE CAR BRINCH HANSEN P The programming language Concurrent Pascal IEEE Trans on Software Engineering 1 p199 1975 BRINCH HANSEN P Concurrent Pascal machine Technical Report Dept of Infonnation Science California Institute of Technology 1975 BRINCH HANSEN P The Solo operating system Software Practice amp Emperience 6 p139 1976 LISTER AM amp MAYNARD KJ An implementation of monitors software Practice amp Experience 6 p377 1976 LISTER AM G SAYER PJ Hierarchical monitors Proc 1976 International Conference on ParaZZeZ Processing pp 43 49 IEEE Cat No 76CH1127 OC 1976 HOWARD JH Proving monitors Comm ACM 19 p273 1976 KAUBISCH WH programming p 341 1976 PERROTT RH amp HOARE CAR Quasi parallel Software Practice amp Experience 6 L Calculus Turing machines are basic symbolmanipulating mechanisms which de ne a model of computation These machines were described by Alan Turing in 1936 Von Neumann architecture refers to a computer design model that uses a single storage structure to hold both instructions and data this kind of computer implements a Turing Machine There are different ways one can calculate functions Alonzo Church The ChurchiTuring thesis stated that Turing machines and recursive functions are equivalent quotEvery rnction which would naturally be regarded as computable can be computed by a Turing machine quotAlonzo Church Because any computer program can be translated into a Turing machine and any Turing machine can be translated into any generalpurpose programming language we know that any generalpurpose programming language is suf cient to express any algorithm A Calculus The goal of Aicalculus is to simplify the notion of computable functions A calculus is a notation that can be manipulated mechanically to achieve some end One reason for developing a calculus is that by reducing some process to a set of simple mechanical rules one decreases the chance of making errors Scope Scope where a variable is visible to a range of statements or where the variable can be accesse Ais calledthe binding operator Binding declaredin accessible etc Bound Identi ers are o en called bound variables 3 a Zr 1 41 i is the bound identi er bound identi ers can change without altering the meaning of a formula If we change a free variable we change the meaning of the expression The binding site ie 2 for an identi er determines the scope of the identi er EX Xlxiolflywiol VXX1gtXVyy1gty kn IZj2I 9 3921 J bound Identi er is j free variable is I j is bound by the summation operation 2 which is called the binding site Mr Scope of X L X l X gt y l l l l l Free occurrence of y l Bound occurrence of X Binding site ofX Q Brogram l Var X l Brocedure 7 l l Var y l l l l Scope of y l l l l L l l End l L End Nested Scopes EX I 1 1 M3 j14a 1 7 l l Scope of j l l l Scope of I 4444 K1 ll l Calculus tCalculus is a theory of functions developed by Alonzo Church In 1920 Moses Schonfinkel developed a theory of functions base of combinations In 1930 Haskell Curry rediscovered and extended Schon nkel s theory and showed that it was equivalent to XCalculus In 1930 Alonzo Church developed XCalculus In 1950 SC Kleene showed that h Calculus was a universal computing systemany computable function can be expressed and evaluated using kCalculus In 1950 John Mccarthy who was inspired by XCalculus invented the programming language LISP hCalculus is equivalent to Turing machines but hCalculus emphasizes the use of transformation rules and doesn t care about the actual machine 39 39 ino them h Calculus is more related to so ware than hardware The h Calculus is a notation for defining functions Any computable function can be expressed and evaluated using XCalculus The central concept in h Calculus is the expression Each 7 expression denotes a function 0 is a kexpression to represent the number zero There are just 3 kinds of Xexpression and using BNF the syntax of Xexpressions are lt A 7 expression gtlt variable gt lt 7 cmpressimt gtlt 7 expression gt lt variable gtlt 7 expression gt IfV ranges over the class of lt variable gt and E E1 E2 range over the syntax of class lt 5PTESSion gt then the BNF simplifies to Variable I E 1 E2 Application combination Procedure call I A V E Abstraction Q NEx denotes the identity function Functions can be applied to expressions NIL 713 Asc1 ac5 gt m gt 5 5 5x means that all occurrences of x in the expression must be replaced by the number 5 Function applications are evaluated by substituting the value of the argument MxE 3 xEx E m be kffxE AffmmEIl gt AffE Ifwe apply AffEDE39 gt fEE39fl gt E39E Arguments are taken from left to right The meaning of Ex all occurrences of x are substituted by E in the expression to the left Q X gt Mfg139 gt 11 Amy gt Ayy gt y Arguments are taken from left to right AXLAyJL39 y2 3 gt Ayn y23 A312 y3 gt 2 y3y i 2 3 gt 5 Conversion Rules An arithmetic expression like 235 can be represent as a kexpression and its value 25 can also be represented as a Xexpression The process of simplifying 235 is called conversion or reduction l Renaming Rule 0cconversion or xreduction one expression may be replace to another by changing a bound identifier throughout its scope to any other identifier that doesn t occur within that scope One Abstraction of the form XvE can be converted to 7wEv v provided that the substitution v for v is valid in E Q Agra2 2x 1 gt Amm2 2m 1 E Aarw gt AaJl gtCl Agg gt Ahh E ArtiAyw y gt AaAsz y Substitution Rule BReduction or BConversion Any application ofthe form 7 VE1E2 can be converted to E1 EzV provided the substitution of V in E1 is valid BReduction is like the evaluation of a function call in a programming language in 7 VE1Ez the body of the function XVE1 is evaluated in an environment in which the formal parameter V is bound to the actual parameter E2 EX anE gt FE J EX AmAyadd my3 4 Ay dd 1y314 gt Ayadd 3y4 gt add 3y 4 3 gt add 3 4 gt 7 Nonvalid Examples EXl XXJtyadd xySquare y 3 kyadd Square yy kyadd xySquare yX is not valid because y is free in Square y but becomes bound after substitution for X in XXJty add xy EX2 XX7ty y 2 X y y is bound in y 2 but free in the last occurrence valid ExamplesEX AmAym y1 2 gt Ava yl1J2 gt Ag1 y2 gt 1 y2y gt 12 3 EX Ayar2 yzz 15 3 Aym2 1J5 gt AgAZJ 12 y5 gt Azz 12 y5y 3 Azz 12 e 5 gt Azz U10 3 z 110z gt 10 1 gt 11 EX mAyym 3 4 Ax E 2 3 Ayyv3 41139 2 2 gt Ayy3 4L39 cc 2 gt y3 4 95 2V9 Az a 23 4 gt 3 23 4x 3 3 42 3 7 2 3 9 In Xexpressions all functions have one variable Functions of several variables may be expressed as a function of one variable through carrying With carrying we can input one variable at a time into separate functions The first function takes the first argument X and returns a function that will take the second variable y and will in turn provide the desired output to create the same function by carrying Fz gt z gtz Gz gtz o F maps integers to a function while G maps integers to integers o FX returns a function GX that provides the appropriate result when supplied with y I F2 3 G2 when Gzy 3 2y I F23 3 G23 3 23 3 5 In kcalculus this function is described as 7 X7tyxy For function applications L3939y 1 y2 3 gt y l39 y2x3 gt M2 y3 gt 2 y3y gt 2 3 gt 5 OO To be able to program significant function in kcalculus it is convenient to have a way to attach names to Xexpressions E Plusp 3 XXX 2 0 Minusp 3 XXX lt 0 Succ 3 LXX1 Square 3 AXXX MinuspSucc2 3 XXX lt 0Succ2 3 Succ2 lt 0 3 AXX12 lt 0 3 21 lt 0 3 3 lt 0 3 False l Expressions to handle truth values if c TF Selects T ifc is true 3 XTFT we always select True Selects F ifc is false 3 XTFF we always select False m Less 2 62 6 3 True2 6 3 ATFT2 6 3 2 True gt E1Ez3True E1Ez3 False gt E1E2 3 False ElEz 3 LTFFE1E2 3 E2

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.