Programming Languages I
Programming Languages I COP 4020
University of Central Florida
Popular in Course
Popular in Computer Programming
This 26 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 63 views. For similar materials see /class/227469/cop-4020-university-of-central-florida in Computer Programming at University of Central Florida.
Reviews for Programming Languages I
Report this Material
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
USER S GUIDE BACI C Compiler and Concurrent PCODE Interpreter Bill BynumTracy Camp College of William and MaryColorado School of Mines July 14 2003 BACI C77 User s Guide Contents 1 Introduction 2 C77 Compiler Syntax 3 J 5 6 Concurrency Constructs 31 cobeginBlock 32 Semaphores 321 InitializingaSemaphore 322 por wait andvorsigr1al Functions 323 Examples of Semaphore Usage 33 Monitors 331 Condition Variables 332 waitc and signalc Functions 333 Immediate Resumption Requirement 334 An Example ofa Monitor 34 Other Concurrency Constructs atomic Keyword 342 void suspend void 343 void revive int processmumber 344 int whichproc void 345 int random int range Built in String Handling Functions 41 void stringCopystring dest string src 42 void stringConcatstrir1g dest string src 43 int stringComparestring X string y 44 int stringLengthstring X 45 int sscanf string X rawstring fmt 46 void sprintf string X rawstring fmt Using the BACI C77 Compiler and PCODE Interpreter Sample program and output BACI C77 User s Guide 2 1 Introduction The purpose of this document is to provide a brief description of the C77 BACI Compiler and Concurrent PCODE Interpreter programs and a description of how to use them The C77 compiler rst compiles the user s program into an intermediate object code called PCODE which the interpreter then executes The C77 compiler supports binary and counting semaphores and Hoare monitors The interpreter simulates concurrent process execution Programs of the BACI System program function I described in bacc BACI C77 to PCODE Compiler this guide cmimips bapas BACI Pascal to PCODE Compiler guidepasps bainterp commandline PCODE Interpreter cmimips guidepasps disasmps bagui Graphical user interface to the guiguideps PCODE Interpreter UNIX systems only badi s PCODE decompiler disasmps baar PCODE archiver sepcompps bald PCODE linker sepcompps The Pascal version of the compiler and the interpreter were originally procedures in a program written by M BenAri based on the original Pascal compiler by Niklaus Wirth The program source was included as an appendix in BenAri s book Principles of Concurrent Programming The original version of the BACI compiler and interpreter was created from that source code Eventually the Pascal compiler and interpreter were split into two separate programs and the C77 compiler was developed to compile source programs written in a restricted subset of C into PCODE executable by the interpreter The syntax for the C77 compiler is explained below This guide is applicable only to the C77 compiler and not to the BACI Concurrent Pascal compiler Users interested in the Pascal compiler should consult its user guide see the le guidepasps 2 C Compiler Syntax 1 As in C comments can be delimited with and or 2 There are no les other than standard input and output cout cirr and endl behave in C77 BACI as in standard C The main program must have one of the following forms int main void main main 3 The only simple CC types available in C77 BACI are int and char There are also other types related to the control of concurrency these will be discussed below All variables must be declared at the beginning of the code block in which they appear In particular the index variable of a for loop cannot be declared in the loop header but instead must be declared at the beginning of the block containing the for loop 4 A string type is supported To declare a string the length of the string must be speci ed The following declaration de nes a string of length 20 string20 stringmame BACI C77 User s Guide V39 9 gt1 9 0 O The length speci er should be the number of characters that the string should have and should not include space for the termination byte The compiler takes care of reserving space for the termination byte The length speci er must be either a literal constant or a program constant The s tr ing keyword is used in the declaration of a function for declaring a parameter of type st ring void proc string formalparm This declaration asserts that formalparm is oftype string n for some positive value of n Param eters of type string are passed by reference No check for string overrun is performed Arrays of any valid type are supported Array declaration follows the usual C syntax elementtype arrayname indexl index2 index3 indexN The keyword typedef is supported in C77 BACI For example to make the variable name length synonym with int typedef int length Constants const of simple types are supported const int m 5 In the declaration of variables of int and char types initializers are supported The value of the initializer must be a literal or program constant const int m 5 int j m int k 3 char c a Procedures and functions are supported Standard scope rules apply Recursion is supported Param eter declarations are passbyvalue or passby reference int afunc int a intamp b pass by value pass by reference Each program must have a main function of type int or void and this function must be the last function in the source le Execution begins with a call to main The executable statements are if else switchcase for while do while break and continue The syntax of these statements are as in standard CC Bracketing of code is standard ie Standard CC le inclusion is supported include lt gt include quot Both styles of include statement have the same semantics because there is no system include directory BACI C77 User s Guide 4 12 The extern keyword for de ning external variables is supported An external variable can be of any valid C77 type Initializers cannot be used with external variables The extern keyword can only occur at the global outer level Typical examples extern int i extern char alZO extern stringl30 b lnitializers are not allowed quot77gt extern int i 30 initialization if present must occur where i is defined extern int func int k extern monitor monSemaphore see Section 3 Only externally void monP visible details of the monitor void monV need be given here The c option must be used with bacc to compile source les that contain external references See the BACI System Separate Compilation Guide for more information about the use of external variables 3 Concurrency Constructs 31 cobegin Block A C77 process is a void function In the BACI system the term concurrent process is synonymous with the term concurrent thread A list of processes to be run concurrently is enclosed in a cobegin block Such blocks cannot be nested and must appear in the main program cobegin procl proc2 procN The PCODE statements belonging to the listed procedures are interleaved by the interpreter in an ar bitrary random order so that multiple executions of the same program containing a cobegin block will appear to be nondeterministic The main program is suspended until all of the processes in the cobegin block terminate at which time execution of the main program resumes at the statement following the ending of the block 32 Semaphores The interpreter has a predeclared semaphore type That is a semaphore in C77 is a nonnegativevalued int variable see de nition below that can be accessed only in restricted ways The binary semaphore one that only assumes the values 0 and l is supported by the binarysem subtype of the semaphore type During compilation and execution the compiler and interpreter enforce the restrictions that a binarysem variable can only have the values 0 or 1 and that semaphore type can only be nonnegative 321 Initializing a Semaphore Assignment to a semaphore or binarysem variable is allowed only when the variable is de ned For example either of the following declarations is valid semaphore s 17 binarysem b 0 The builtin procedure BACI C77 User s Guide 5 initialsem semaphore integerexpression is the only method available for initializing a semaphore of either type at runtime In the call integerexpression can be any expression that evaluates to an integer and is valid for the semaphore type non negative for a semaphore type 0 or 1 for a binarysem type For example the following two initialsem calls show an alternative way to initialize the two semaphores declared above initialsem s 17 initialsem b 0 322 p or wait and v or signal Functions The p function or synonymously wait and the v function or synonymously s ignal are used by concur rently executing processes to synchronize their actions These functions provide the user with the only way to change a semaphore s value The prototypes of the two functions are as follows void p semaphoreamp s or equivalently void wait semaphoreamp s void v semaphoreamp s or equivalently void signal semaphoreamp s The semaphore argument of each function is shown as a reference parameter because the function modi es the value of the semaphore The semantics of the p and v function calls are as follows p sem If sem gt 0 then decrement sem by l and return allowing p s caller to continue If sem 0 then put p s caller to sleep These actions are atomic in that they are noninterruptible and execute from start to nish v sem If sem 0 and one or more processes are sleeping on sem then awake one of these processes If no processes are waiting on sem then increment sem by one In any event v s caller is allowed to continue These actions are atomic in that they are noninterruptible and execute from start to nish Some implementations of v require that processes waiting on a semaphore be awakened in FIFO order queuing semaphores but BACI conforms to Dijkstra s original proposal by randomly choosing which process to reawaken when a signal arrives BACI C77 User s Guide 323 Examples of Semaphore Usage To help to explain semaphore usage we offer the following brief example BACI System Cquot to PCODE Compiler 0924 2 May 2002 Source file semexamplecm Sun Apr 28 204012 2002 line 29 pc example of Cquot semaphore usage semaphore count a quotgeneralquot semaphore binarysem output void increment poutput obtain exclusive access cout ltlt quotbefore vcount value of count is voutput vcount increment the semaphore increment void decrement poutput obtain exclusive access cout ltlt quotbefore pcount value of count is voutput pcount decrement the semaphore decrement main initialsemcount 0 initialsemoutputl cobegin decrement increment l main a binary 0 or 1 semaphore to lt t lt lt o lt or for unscrambling output s tandard output count ltlt endl s tandard output count ltlt endl stop H see manual text The program uses two semaphores One semaphore count is of semaphore type which indicates to the BACI system that the semaphore will be allowed to have any nonnegative value The two con current procedures increment and decrement signal each other through the count semaphore The other semaphore output is of binarysem type which indicates to the BACI system that the semaphore should always have the value zero or one any other value causes a runtime exception This semaphore is used to keep the output from the two concurrently executing procedures increment and decrement from interrningling We produced the above compiler listing with the command prompt bacc semexample Pcode and tables are stored in semexamplepco Compilation listing is stored in semexamplelst The semexampl e pco le can then be executed with the BACI PCODE interpreter prompt bainterp semexample Source file semexamplecm Sun Apr 28 204012 2002 Executing PCODE before vcount value of count is 0 before pcount value of count is 1 This execution of the PCODE le is one of the three possible outputs that the program can produce The other two possible program outputs are BACI C77 User s Guide 7 prompt bainterp semexample Source file semexamplecm Sun Apr 28 204012 2002 Executing PCODE before pcount value of count is 0 before vcount value of count is 0 prompt bainterp semexample Source file semexamplecm Sun Apr 28 204012 2002 Executing PCODE before vcount value of count is 0 before pcount value of count is 0 An interested reader might nd it instructive to supply explanations for ways in which these three pro gram outputs are generated and to show that these three outputs are the only outputs possible 33 Monitors The monitor concept as proposed by Hoare is supported with some restrictions A monitor is a C77 block like a block de ned by a procedure or function with some additional properties All functions in the monitor block are visible that is are callable entry procedures from the outside of the block but the monitor variables are not accessible outside of the block and can only be accessed by the monitor functions In C77 a monitor can be declared only at the outermost global level Monitors can not be nested A monitor can have an optional init block as its last block for initializing the values of the monitor s variables This code is run when the main program is started Only one procedure or function of the monitor block can execute at any one time This feature makes it possible to use monitors to implement mutual exclusion Use of monitors to control concurrency is advantageous because all of the code controlling concurrency is located in the monitor and not distributed widely across callers as is the case when semaphores are used Three constructs are used by the procedures and functions of a monitor to control concurrency condition variables waitc wait on a condition and signalc signal a condition 331 Condition Variables A condition variable can only be de ned in a monitor and thus can only be accessed by the monitor s processes A conditionvariable never actually has avalue it is somewhere to wait or something to signal A monitor process can wait for a condition to hold or signal that a given condition now holds through the waitc and signalc calls 332 waitc and signalc Functions waitc and s ignal c calls have the following syntax and semantics void waitc condition cond int prio The monitor process and hence also the outside process calling the monitor process is blocked and assigned the priority prio for being reawakened see signalc below Note that this blocking action allows some other monitor process to execute if one is ready void waitc condition cond This call has the same semantics as the waitc call above but the wait is assigned a default priority of 10 void signalc condition cond Wake some process waiting on cond with the smallest highest priority otherwise do nothing Note that this is quite unlike the semaphore v or signal because signalc is a noop if no one is waiting BACI C77 User s Guide 8 whereas v sem increments sem if no one is waiting thus remembering the action when future p sem s occur The priority scheme can be used to implement a FIFO discipline in reawakening waiters If each monitor process increments a monitor variable associated with the current priority assigned to a condition then successive signal c s to the condition will awaken the sleeping processes in a FIFO order The C77 compiler provides an int function empty cond that returns 1 if there are no processes waiting in the queue of the condition cond and 0 otherwise 333 Immediate Resumption Requirement This is the requirement that a process waiting on a condition that has just been signaled should have priority in reentering the monitor over new calls to monitor processes those wanting to enter from the top The requirement rests on the assumption that the condition that has just been signaled has more urgent business to perform than a new entry into the monitor The Immediate Resumption Requirement is implemented in BACI by suspending the signaller of a condition and picking at random one of the waiters on the condition with the appropriate priority to run Because of this monitor procedures that s ignal c a condition typically do so as their last instruction When the process reawakened by the signalc leaves the monitor a process executing in the monitor that has been suspended after issuing a signalc call is allowed to resume execution in the monitor in preference to processes attempting to enter the monitor from the top 334 An Example ofa Monitor The following example of an implementation of a general semaphore with a monitor illustrates the monitor syntax moni tor monSemaphore int semvalue condi tion notbusy void monP if semvalue O waitc notbusy else semvalue void monV if emptynotbusy semvalue else signalc notbusy init semvalue l end of monSemaphore monitor 34 Other Concurrency Constructs BACI C77 provides several lowlevel concurrency constructs that can be used to create new concurrency control primitives These functions can be used to create a fair FIFO queued semaphore The code to accomplish this is beyond the scope of this user s guide BACI C77 User s Guide 9 341 atomic Keyword If a function is de ned as atomic then the function is non preemptible The interpreter will not interrupt an atomic function with a context switch This provides the user with a method for de ning new primitives The following program illustrates how a te standset primitive can be de ned and used to enforce mutual exclusion atomic int testiandisemintsr target re turn u int lock 0 void procint id int i 0 whilei lt 10 while testiandiset cout ltlt id lock 0 i lock wait l main cobegin procl proc2 proc3 342 void suspend void The suspend functions puts the calling thread to sleep 343 void revive int processmumber The revive function revives the process with the given number 344 int whichproc void The whichproc function returns the process number of the current thread 345 int random int range The random function returns a randomly chosen integer between 0 and range l inclusive It uses a different random number generator stream than the one used by the interpreter that is random calls do not affect interpreter execution 4 Builtin String Handling Functions 41 void stringCopystring dest string src The stringCopy function copies the src string into the dest string No check for string overrun is per formed For example BACI C77 User s Guide 10 string20 X stringCopyXquotHello worldlquot stringCopyxquotquot will initialize the string x to a wellknown value The second stringCopy resets the string x to a zerolength string 42 void stringConcatstring dest string src The stringConcat function concatenates the src string to the end of the dest No check for string overrun is performed 43 int stringComparestring x string y The stringCompare function has the same semantics as the strcmp function from the C string library a positive number is returned if string x is leXicographically after the string y zero is returned if the strings are equal and a negative number is returned if string x is leXicographically before the string y 44 int stringLengthstring x The stringLength function returns the length of the string X not including the termination byte 45 int sscanf string x rawstring fmt Like the rea sscanf the sscanf function scans the string x according to the format string fmt storing the values scanned into the variables supplied in the parameter list and returns the number of items scanned Only the d X and s format speci ers of the real sscanf are supported An additional format speci er q quoted string unique to BACI is supported For this speci er all characters delimited by a pair of double quotes quot will be scanned into the corresponding string variable When the q speci er is encountered in the format string if the neXt nonwhitespace character of the string being scanned is not a double quote then the q scan fails and scanning of the string terminates The variables appearing after the format string are reference variables that is the ampersand amp is not required In the following example the value of i returned by the sscanf call will be 4 the value stored in the variable j will be 202 the value stored in the string stored in string x will be alongstring the value stored in the variable k will be Ox3c03 and the string stored in the string y will be a long string string50 Xy int ijk stringCopyXquot202 alongstring 3c03 quota long stringquotquot i sscanfxquotd s 96X qquotjXkY7 46 void sprintfstring x rawstring fmt Like the real sprintf function in the C library the sprintf function creates a string stored in the variable X using the format string fmt and the variables following the format string The d o X X c and s format speci ers are supported in the full generality of the real sprintf In addition the q format speci er will insert a doublyquoted string into the output string The q format speci er is equivalent to the quot squot speci er For example in the following code fragment BACI C77 User s Guide 11 stringl80 x stringllS yz stringCopyyquotalongstringquot stringCopyz a long string s printfx 12d 720s q 08X 202yz0x3c03 the string x becomes 202 alongstring quota long stringquot 00003C03 5 Using the BACI C Compiler and PCODE Interpreter There are two steps to executing a program with the BACI system 1 Compile a cm le to obtain a pco le Usage bacc optionalflags sourcefi lename Optional ags 7h show this help 7c make a pob object file for subsequent linking 77 The name of the source le is required If missing you will be prompted for it The le suf x cm will be appended if you don t supply it Equot Interpret a pco le to execute the program Usage baininterp optionalflags pcodefi lename Optional ags 7d enter the debugger single step set breakpoints 7e show the activation record AR on entry to each process 7x show the AR on exit from each process announce process termination show this help 7p show PCODE instructions as they are executed rr r The name of the PCODE le is required If missing you will be prompted for it The le suf x pco will be appended to the lename you give It is not necessary to recompile the source le each time that you execute the pco le with bainterp There is a shell script baccint that will call the compiler and then call the interpreter for you It passes the options that you give it see above along to the interpreter 6 Sample program and output The following listing was produced by the C if BACI compiler The number to the right of the line number is the PCODE offset of the instruction that begins that line The BACI compiler creates this listing from the le incremen cm The listing is placed in the le incremen 1st An incremenpco le is also created this le is used by the interpreter BACI C77 User s Guide 12 BACI System Cquot to PCODE Compiler 0924 2 May 2002 Source file incremencm Wed Oct 22 211802 1997 line pc 1 0 const int m 5 2 0 int n 3 0 4 0 Void incrchar id 5 0 6 0 int i 7 0 8 0 fori1iltmii1 9 14 10 14 n n 1 11 19 cout ltlt id ltlt n ltlt n ltlt i 12 25 cout ltlt i ltlt ltlt id ltlt endl 13 31 14 32 15 33 16 33 main 17 34 18 34 11 0 19 37 cobegin 20 38 21 38 incr A incr B incr C 22 50 23 51 cout ltlt quotThe sum is ltlt n ltlt endl 24 55 The following listing was produced by the BACI interpreter The interpreter executes the program that was compiled into the le incremenpco Source file incremencm Wed Oct 22 211802 1997 Executing PCODE C111iA111C2 i C 114 i2C B 1114 115 i24A AC 11 116 i3C6 i3 7 i4C 9i2BA 118 Cm i5An9C i B1111 i B1112i Thesumisl2 muw wove The functional programming language paradigm is based upon mathematical function theory A mathematical function is a mapping of members of a domain set onto the members of a second set called the range set The function yields or returns an element of the range set domain set range set Figure 1 A mathematical function A fundamental characteristic of mathematical functions is that the evaluation order of the mapping expressions is controlled by recursion and conditional expressions composition of functions rather than by sequencing and iterative repetition which is common to imperative languages A purely functional language does not use variables or assignment statements A functional language should provide a A set of primitive functions a A set of functional forms a A function application operation 1 Structures for storing data Table 2 illustrates some of the primary differences between imperative languages and functional languages Chapter 15 7 Functional Programming Languages 1 Imperative Languages Functional Languages Programmers must deal with variables Programmers are not concerned with and the assignment ofvalue variables or assignment of value Decreased execution ef ciency See below Program construction is less laborious It is a higher level of programming Increased execution ef ciency Program construction is more laborious Syntax is complex Simple syntactic structure Semantics are complex Semantics are simple Concurrent execution is dif cult to Concurrency can be determined by the design and utilize execution system Less ef cient on uniprocessor machines but may be more ef cient on multiprocessor machines Table 2 Comparison of imperative and functional languages Another important characteristic of mathematical functions is that because they have no side effects they always return the same value given the same set of arguments Side effects in programming languages are connected to variables which model memory locations A mathematical function defines a value rather than specifying a sequence of operations on values in memory to produce a value Since there are no variables in functional languages in the sense that there are variables in an imperative language there can be no side effects The functional model of programming languages as well as the imperative model grew out of the work undertaken by mathematicians Alan Turing Alonzo Church Stephen Kleene and Emil Post among others in the 1930s Working independently these individuals developed several very different formalizations of the notion of an algorithms or effective procedure based on automata symbolic manipulation recursive function definitions and combinatorics Over time these various formalizations were shown to be equally powerful anything that could be computed in one could be computed in the others This result led Church to conjecture that any intuitively appealing model of computing would be equally powerful as well this conjecture is known as Church s thesis Turing s model of computation was the Turing machine an automaton reminiscent of a finite or pushdown automaton but with the ability to access arbitrary cells of an unbounded storage tape The Turing machine computes in an imperative way by changing the values of cells in its tape just as a highlevel imperative program computes by changing the values of variables Church s model of computing is called the lambda calculus It is based on the notion of Chapter 15 7 Functional Programming Languages 2 parameterized expressions with each parameter introduced by an occurrence of the letter k hence the notations name Lambda calculus was the inspiration for functional programming one uses it to compute by substituting parameters into expressions just as one computes in a highlevel functional program by passing arguments to functions The computing models of Kleene and Post are more abstract and do not lend themselves directly to implementation as programming languages Functional languages typically contain simple functions as well as higherorder functions or functional forms A higherorder function is one that either takes functions as parameters andor yields a function as a result Simple functions you should be quite familiar with and are often written as a function name followed by a list of parameters in parentheses followed by the mapping expression For example cubex E x x x where x is a real number In this definition the domain and range sets are defined to be real numbers The parameter x can represent any member ofthe domain set but is restricted to represent one specific member of the domain set during evaluation of the function expression In other words during evaluation the mapping of a function contains no unbound parameters where a bound parameter is a name for a particular value Every occurrence of a parameter is bound to a value from the domain set and is considered a constant during evaluation Early theoretical work on functions separated the task of defining a function from that of naming a function Alonzo Church devised lambda notation as a method for defining nameless functions A lambda expression specifies the parameter and the mapping of a function The lambda expression is the function itself The earlier example of the cubex function expressed as a lambda expression is Mx x x x When a lambda expression is evaluated for a given parameter the expression is said to be applied to that parameter The mechanics of such an application are the same as for any function evaluation Application of the lambda expression shown above to the parameter 3 is Mx x x x 3 which results in a value of 27 Chapter 15 7 Functional Programming Languages 3 There are many different functional forms but the three illustrated in the textbook are representative of the various types form h E f g semantics hx fgx examples let fx EX X and gx h3 fgx f33 f 99 18 h2 f gx f22 f 4 f44 16 form f g i semantics fx gx ix examples let fx E xx and gx E xx f 915 10 25 letfxExx gx22x and hXEX2 f g h 4 16 8 2 I to All form or semantics apply each parameter in a parameter list to a single function to produce a list of values that is the result ofthe function examples let fx Chapter 15 7 Functional Programming Languages 4 Lambda calculus has a small syntax consisting of only three constructs variables function application and function creation This makes it particularly wellsuited for studying types in programming languages Since its inception in the 1930 s developed by Alonzo Church primarily as a tool for studying computation with functions it has had a profound influence on the design and analysis of many programming languages The general form of a kcalculus expression is kxM where X is the parameter and M is the body of the lambda function In kcalculus functions are written next to their arguments so fa represents the application of function fto argument a as in sin Hor log n The following are all kexpressions Xxx this is a function which takes a single argument and simply returns the value of that argument Ax x x this is a function which takes a single argument and returns the value of the argument multiplied by itself XX X x 5 defined above this function returns the value 25 XX x x 5 is also a frequently used syntax for kcalculus expressions Formulas like XX X x 5 are called terms A grammar for terms in the pure lambda calculus is given by M x M1 M2 kxM Commonly letters 2 x y 2 denote variables and M N P Q represent terms A term is either a variable x an application M N of function M to N or an abstraction kxM In an applied lambda calculus a constant c can be added as an option which represents values like integers and operations on data structures like lists Thus 0 can stand for basic constants like true and nil as well as constant functions like and rst The lambda calculi are therefore a family of languages for computation with functions Chapter 15 7 Functional Programming Languages 5 qutisciiiiivv ruff w Betaequality deals with the result of applying an abstraction kxM to an argument N In other words betaequality deals with the notions of function calling and parameter passing in programming languages An abstraction corresponds to a function definition and an application corresponds to a function call If M 3 N then M and N are betaequal informally this means that M and N have the same value Thus Xx X x 5 3 5 5 Lambda calculus uses a prefix notation Thus the function x2 3x 5 is written as lX X X 3 X 5 An example call to this function with a parameter with value 3 would be as follows KXXX3X5 3 33333 539953185 313 The following abbreviations are often used to make terms more readable o Parentheses may be dropped from M N and kxM In the absence of parentheses function application groups from left to right Examples x y 2 can be abbreviated as x y z The parentheses in x y z are necessary to ensure that x is applied to y 2 Function application has higher precedence than abstraction so ix y z is abbreviated as ix y z A sequence of consecutive abstractions such as ix 1y 22 M can be written with a single lambda as in kxsz Therefore ixlyx is abbreviated as ixyx Abstractions of the form kxM are also referred to as bindings because they constrain the role of x in kxM Variable x is said to be bound in kxM The set freeM the free variables of M are those variables which appear unbound in M The set freeM is given by Chapter 15 7 Functional Programming Languages 6 1 freex x 2 freeM N freeM u freeN 3 free txM freeM x Rule 1 states that variable X is free in the term X Rule 2 states that a variable is free in M N if it is either free in M or free in N Rule 3 states that with the exception of x all other free variables of M are free in kxM Example In the term kyz kzz z is a free variable in the subterm kyz because 2 is a free variable The occurrence of X to the right of k in kxM is called a binding occurrence or simply a binding of X All occurrences ofx in kxM are bound within the scope of this binding All unbound occurrences of a variable in a term are free Each occurrence of a variable is either free or bound it cannot be both Example The only occurrence ofx in kxy is bound within its own scope Consider the term kykzxzy z The following diagram the lines go from a binding to a bound occurrence 7 yvzxEyz Recall that this term can also be written as kyzxzyz which might make the above a bit easier to comprehend kexpressions have only one reduction operation which is substitution lf FA is a kexpression where F kxM then A an argument to the function can be substituted for all free occurrences of x in M This is written as kxM A 2 M it is also common to see this written as A x M This operation is analogous to substituting an argument for a formal parameter in a function call In general substitution will replace variables by terms thus the substitution of a term N for a variable x in M written as N x M proceeds according to the following two cases Chapter 15 7 Functional Programming Languages 7 1 If the free variables of N have no bound occurrences in M then the term N x M is formed by replacing all free occurrences of X in M by l Othenvise suppose that variable y is free in N and bound in M Consistently replace the binding and corresponding bound occurrences of y in M by some new variable 2 Repeat the renaming of bound variables in M until case 1 applies then proceed as in case 1 above The keyaxiom of betaequality is MM N 3 N x M Therefore MX u 3 u and My u 3 y The ocaxiom is MM 3 M z X M provided that z is not free in M Therefore M X 3 ky y and My X 3 luv u Figure 2 summarizes the axioms and rules for betaequality Xx M 5 M z x M provided that z is not free in M 0c axiom KxM N 5 N x M B axiom M 9 M idempotence axiom M 23 N c0mmutat1v1ty rule N 23 M M 239 N N 23 P M P tran51t1V1ty rule congruence rule MN 3 M N M M 393 congruence rule Xx M 2 x M Figure 2 Axioms and rules for BetaEquality Chapter 15 7 Functional Programming Languages 8 The following are a few examples ofthe various equivalences that are possible in kcalculus Xxx y 2 y equivalent to xxx y 2 y AXXy y 2 yy equivalent to xxxy y 2 yy AXXV KXX 3 Xxx y 2 y equivalent to xxxy xxx 2 Xxxy 2 y 7vXXX XXXX 2 7vXXX XXXX 2 equivalent to XXXX XXXX 2 7vXXX vxxx 2 Note the reduction operation does not always yield a kexpression which is simpler than the original expression Example d above is such a case it does not terminate of In each of the following cases M has no bound occurrences so A replaces all occurrences ofX in M to form AX M wl xu u X x u kx x X X XX x In each of the following cases M has no free occurrences of X so A x M is simply M itself uXyy uXyZ yZ uX7y V7y Y uXkx x XX x KXXXyy In each of the following cases free variable u in A has bound occurrences in M so AX M is formed by first renaming the bound occurrences of u in M u X XX x u X k2 x u x ku u u x l2 2 Chapter 15 7 Functional Programming Languages 9 If two different reductions of a xexpression terminate then they are both members of the same value class In other words if kexpression M has the reductions M 2 P and M 2 Q then there is a unique kexpression R such that P 2 R and Q 2 R R is then called the normal form for the value class represented by M There are two standard approaches to the reduction of kexpressions 1 reduce the outermost left term first or 2 reduce the innermost left term first Suppose we have the kexpression kyyy lxxx a 1Reduction by the outermost left term first In this case the outermost left term is the entire kexpression MIW XXXX agt7XXX 8 XXXX a 3 aaaa This technique substituted the function lxxx a for parameter y and evaluated this function for each occurrence of y there are two such occurrences in this outermost function Note this is basically a quotpassbynamequot type of parameter passing 2Reduction by the innermost left term first In this case the innermost left term is lxxx a MIW XXXX agt MlW aa gt aaaa This technique evaluated the constant aa before substituting for y Thus the inner kexpression AXXX a was evaluated yielding the constant aa first and this was then passed as the parameter to the Chapter 15 7 Functional Programming Languages 10 outermost left term Note this is basically a quotpassbyvaluequot type of parameter passing If a keXpression has a normal form then reduction by the innermost left term first will find the normal form Passbyname is a form of quotlazy evaluationquot thus only expressions which are used in the final solution need to be evaluated Passbyvalue however always evaluates arguments so nonterminating arguments are evaluated even if they are not ultimately needed This information can be utilized to create examples of terms that terminate via passbyname and do not terminate via passbyvalue Need to compose a nonterminating keXpression as an argument that is never referenced Since we already know that the 7teXpression MXX MXX does not terminate since in the 7teXpression kyz the parameter y is never referenced we can generate the following 7teXpression kyz MX X MX X which has the normal form 2 which is easily determined if passbyname is used but represents a nonterminating kexpression if passbyvalue is used Boolean Values Boolean values can be modeled as keXpressions Define True to be M kyx E MyX Define False to be M kyy E Myy In this manner True can be interpreted as of a pair of values pick the first Similarly False can be interpreted as of a pair of values pick the second TRUE MvyX MvyXT T MyX T T MvyXT F MyX T F MvyXF T MyX F T MvyXF F MyX F F v T equivalent to My X T T 2 T T equivalent to My X T F 2 T F equivalent to My X F T 2 F F equivalent to My X F F 2 F vvv FALSE Mvyy MvyyT T Myy T T T equivalent to My y T T 2 T MvyyT F Myy T F F equivalent to My y T F 2 F MvyyF T Myy F T T equivalent to My y F T 2 T MvyyF F Myy F F F equivalent to My y F F 2 F Chapter 15 7 Functional Programming Languages 11 Given these definitions for True and False the following properties hold T P Q 2 P ie T P Q 2 kxyx P Q 2 MyP Q 2 P outermost left term reduced first means that P is substituted for X in XX kyx P which yields kyP then Q is substituted for y in this term but y is never referenced in this function which simply returns F P Q 2 Q ie F P Q 2 kx kyy P Q 2 kyy Q 2 Q outermost left term reduced first means that P is substituted for X in XX kyy P which yields kyy then Q is substituted for y in this term which yields Q Thus the value Q is returned Given the definitions for the constants True and False the Boolean operators and or and not can be defined in a similar fashion as follows not 7tXX F T equivalent to x xFT and AX kyx y F equivalent to kxy xyF or Ax kyx T y equivalent to kxy XTy Given these definitions do they produce interpretations that are consistent with the rules of predicate logic For example when not is applied to True is False returned Shown below are the proofs that these definitions do produce interpretations that are consistent with predicate logic Recall that kcalculus uses prefix notation mt not 139 xxx F T T 2 T F T 2 F equivalent to Ax xFT T 2 T F T 2 F not F Axx F T F 2 F F T 2 T equivalent to Ax xFT F 2 F F T gt T M T and T and T T AX Ayx y F T T 2 T T F 2 T Axy xyF T T 2 T T F 2 T T and F and T F AX Ayx y F T F 2 T F F 2 F Axy xyF T F 2 T F F 2 F F and T and F T AX Ayx y F F T 2 F T F 2 F Axy xyF F T 2 F T F 2 F F and F and F F AX Ayx y F F F 2 F F F 2 F Axy xyF F F 2 F F F 2 F or T or T or T T AX Ayx T y T T 2 T T T 2 T hxy XTy T T 2 T T T 2 T T or F or T F AX Ayx T y T F 2 T T F 2 T 7vxy XTy T F 2 T T F 2 T F or T or F T AX Ayx T y F T 2 F T T 2 T hxy XTy F T 2 F T T 2 T F or F or F F AX Ayx T y F F 2 F T F 2 F hxy XTy F F 2 F T F 2 F Chapter 15 7 Functional Programming Languages 12 Despite their relative simplicity throughout the historyevolution of highlevel programming languages only a very few functional languages have gained any widespread use Lisp has been far and away the most popular of the functional languages APL is also considered a functional language even though it makes heavy use of the assignment operation Lisp is a versatile and powerful language which has been both despised and loved by different programmers throughout the years Lisp was originally designed for symbolic computations and listprocessing applications Both of these areas fall within the domain of artificial intelligence Al ln Al Lisp and some of its derivatives are still the dominant languages Most of the existing expert systems were developed in Lisp although this is one area in Al that has seen a fair amount of develop occur with logic based languages such as Prolog Lisp dominates the areas of knowledge representation machine learning natural language processing intelligent training systems and the modeling of speech and vision Lisp has also be successfully applied to areas outside of Al The EMACS text editor is written in Lisp so too is the symbolic mathematics system MACSYMA There are three popular dialects of Lisp that you may run across Scheme is perhaps the most popular of these followed by ML and Haskell ML and Haskell have been most widely used in research and university teaching environments Other functional languages include Sisal and Backus s FP proposal Chapter 15 7 Functional Programming Languages 13
Are you sure you want to buy this material for
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'