COP-5555 PROGRAMMING LANGUAGEPRINCIPLESNOTES ON RPAL1. IntroductionRPAL is a subset of PAL, the ‘‘Pedagogic Algorithmic Language’’. There are three versions of PAL:RPAL, LPAL, and JPAL. The only one of interest here is RPAL. The ‘‘R’’inRPALstands for ‘‘right-ref-erence’’, as opposed to ‘‘L’’ (LPAL) which stands for ‘‘left-reference’’. The logic behind this conventioncomes from a tradition in programming languages, in which an identifier,when occurring on the left side ofan assignment, denotes the ‘‘left-value’’, i.e. its address, whereas if it occurs on the right side of the assign-ment, it denotes the ‘‘right-value’’, i.e. the value stored at that address. An RPAL program is simply anexpression. RPAL has no concept of ‘‘assignment’’, nor evenone of ‘‘memory’’. There are no loops, onlyrecursion. RPAL programs, as we shall see, consist exclusively of twonotions: function definition andfunction application. LPAL is essentially RPAL plus assignments, memory aliasing, and other issues.JPAL, finally,isLPALplus jump statements. To repeat, we will only deal with RPAL.RPAL is a functional language. Every RPAL program is nothing more than an expression, and ‘‘run-ning’’anRPALprogram consists of nothing more than evaluating the expression, yielding one result. Thisseems superfluous at first, but the catch is that in RPAL functions are much more important than in otherlanguages. In fact, the single most important construct in RPAL is the function. From nowon, we willsimply say PAL instead of RPAL. Functions in PAL are so-called ‘‘first-class’’objects. This means thatunliketraditional languages such as Pascal and C, the programmer can do anything he/she wants to with afunction in PAL, including sending a function as a parameter to a function and returning a function from afunction.We first give some examples of PAL programs:1) let X=3inPrint(X,X**2)2) let Abs(N) =(N ls 0 −>-N|N)inPrint(Abs(-3))The values printed by each of these programs are (3,9) and (3), respectively.The actual value of each pro-gram is dummy.PALhas operators (a.k.a. functors), function definitions, constant definitions, conditional expressions, func-tion application, and recursion. The first example above illustrates a constant definition of X as 3, andfunction application: the function Print is applied to the pair (X,X**2). The definition of X as 3 holds inthe expression Print(X,X**2); thus the result (3,9). The second example illustrates function definitions andconditional expressions: Abs is defined as a function, that takes a parameter N and returns either -N or N,depending on whether N is less than zero.PLP Notes RPAL-2-PALisadynamically typed language. This means that unlikestrongly typed languages such as Pascal orC, theytype of a variable is determined at run-time, and not earlier.For example, consider the definition(not a complete PAL program)let Funny=(B−>1|’January’)In this definition Funnyisdefined as the integer 1 or the string ’January’, depending on the current value ofB.PALhas six major types of values: integer,truthvalue (boolean), string, tuples, functions, anddummy.Since the language is dynamically typed, there are several functions available to find out whattype of object is being dealt with. These are: Isinteger,Istruthvalue, Isstring, Istuple, Isfunction, andIsdummy.All of these are functions that takeanarbitrary object, and return either true or false, dependingon the type of that object.Other features of the language:Truthvalue operations or,&,not, eq, neInteger operations +,-,*,/,**,eq,ne,ls,gr,le,geString operations eq, ne, Stem S, Stern S, Conc S T2. Definitions.Definitions in PAL are of the form ‘‘let <defn> in <expn>’’. For example:let Name = ’Dolly’ in Print (’Hello’,Name)Definitions can be nested arbitrarily,inwhich case the issue of scope appears. Forexample:let X = 3inlet Sqr X = X**2inPrint (X, Sqr X, X * Sqr X, Sqr X ** 2)The scope of X (the value 3) is the entire expression following the first ‘‘in’’. The scope of the Sqr functionis only the expression following the second ‘‘in’’.Another form of definition is the ‘‘where’’definition, which is similar to the ‘‘let’’definition, exceptthat the order is reversed. For example, the above PAL program might be re-written as:(Print (X, Sqr X, X * Sqr X, Sqr X ** 2)whereSqr X = X**2)whereX=3Simultaneous definitions are also allowed, using the keyword ‘‘and’’. For example:let X=3 and Y=5 in Print(X+Y)Note that because of this use of the keyword ‘‘and’’, the boolean (truthvalue) conjunction operator of thesame name is represented using the symbol ‘‘&’’.PLP Notes RPAL-3-Finally,definitions can hold within one another,using the ‘‘within’’clause. Normally,the scope of a ‘‘let’’or ‘‘where’’definition is an expression. The scope of a ‘‘within’’definition is another definition, not anexpression. For example:let c=3 within f x = x + c in Print(f 3)3. FunctionsIn PAL, functions are first-class objects. This means that there no silly restrictions on the circum-stances in which one can use a function, as there are in manyother languages. In PAL, functions can begivenaname using an ordinary definition, passed as parameters to other functions, returned from functions,selected from other objects in conditional expressions, and entered into data structures. Of course, func-tions can also be applied to actual values. Functions can be used arbitrarily in expressions, anywhere, say,an integer could be used. Every function has a so-called bound variable (its parameter) and a body (anexpression). For example:fn X. X ls 0 −>-X|XAfunction can be givenaname using an ordinary definition:let Abs = fn X. X ls 0 −>-X|XinPrint (Abs(3))Afunction can be passed as parameter:let f g = g 3 in let h x = x + 1 in Print(f h)Afunction can be returned from a function:let f x = fn y.x+y in Print (f 3 2)Afunction can be selected from other objects using the conditional:let B=true in let f = (B −>(fn y.y+1) | (fn y.y+2) ) in Print (f 3)Afunction can be entered into a tuple (more on tuples later):let T=((fn x.x+1),(fn x.x+2)) in Print (T 1 3, T 2 3)N-ary functions are allowed, by using tuples:let Add (x,y) = x+y in Print (Add (3,4) )In general, a function (fn x.B) is applied to an argument A by juxtaposition, i.e. by forming the expression(fn x.B)A. There are twoways in which