PROGRAMMING LANGUAGES CS 655
Popular in Course
Popular in ComputerScienence
This 13 page Class Notes was uploaded by Juvenal Beahan on Friday October 23, 2015. The Class Notes belongs to CS 655 at University of Kentucky taught by Raphael Finkel in Fall. Since its upload, it has received 25 views. For similar materials see /class/228211/cs-655-university-of-kentucky in ComputerScienence at University of Kentucky.
Reviews for PROGRAMMING LANGUAGES
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/23/15
C8655 class notes Raphael Finkel October 1 2009 1 Intro Lecture 1 8272009 0 Handout 1 My names 0 Mr Dr Professor o Raphael Rafi Refoyl o Finkel Goldstein o Plagiarism read aloud from handout 1 o Assignments on web and in handout 1 0 E mail list cs655001csukyedu instructor uses to reach students 0 All students will have MultiLab accounts although you may use any computer you like to do assignments o textbook all homework comes from here 0 First assignment Chapter 1 due Thursday 2 Software tools A programming language is an example of a software tool Use client Usable spec Elegant Implementation COmPilable C5655 Fall 2009 2 3 McLennan s Principles elicit rst 4 Algollike languages review 0 First generation Fortran constructs based on hardware lexical linear list of statements control sequence goto do subroutines using reference pa rameter mode 0 data arithmetic including complex arrays with a 3 d limit 0 name separate scopes common area Second generation Algol 60 o lexical free format keywords 0 control nested i f whi 1e for but baroque subroutines with value and name parameter modes 0 data generalized arrays but no complex 0 name nested scopes with inheritance and local override Third generation Pascal return to simplicity 0 data user defined types records enumerations pointers 0 control subroutines with value and reference parameter modes ca 3 e statement Fourth generation Ada abstract data types 0 lexical bracketed syntax 0 data modules with controlled export generic modules 0 control concurrency with rendezvous Fifth generation Other directions 0 data ow 0 functional We will study ML and Lisp o object oriented We will study Smalltalk o declarative logic We will study Prolog C5655 Fall 2009 3 5 0 Block structure 0 Introduced in Algol o A block is a nestable name scope o Identifiers can be local nonlocal or global with respect to a block 0 Nonlocal identifiers the language must define whether to o inherit typically allowed if there is no con ict 0 override typically true if there is a con ict 0 require explicit import and export 0 At elaboration time constants get values dynamic sized types are bound to their size space is allocated for variables 0 Definition the nonlocal referencing environment NLRE of a pro cedure or block of code is the binding of non local identifiers typi cally variables but also constants types procedures and labels to values 0 Deep binding The NLRE of P is determined bound at the time that P is elaborated and is the RE of the elaborating scope 0 Shallow binding The NLRE of P is determined at the time that P is invoked and is the RE of the calling scope o Adequately difficult example book 2421 Theme binding time 0 There is a range from early to late 0 language definition time example the fact that constants exist 0 compile time example values of constants in Pascal We call compile time bindings static 0 link time example version of printf in C o elaboration time example value of final int in Java 0 statement execution time example value of int variable We call execution time bindings dynamic 0 Early binding is most efficient 0 Late binding is most capable C5655 Fall 2009 7 Imperative languages Imperative languages involve statements that modify the current state by changing the values of variables A variable is an identifier bound usually statically to a type having a value that can change over time The Lvalue of a variable is the use of a variable on the left side of an assignment think of address the Rvalue of a variable is its use on the right side think of current value A type is a set of values associated mostly statically with opera tions defined on those values Type conversion means expressing a value of one type as a value of another type 0 coercion implicit conversion 0 cast explicit conversion 0 nonconverting cast rarely needed qua operator of Wisconsin Modula reinterpreticastltgt of C An operation is a function or an operator symbol as shorthand It can be heterogeneous o operators have arity example unary binary precedence as sociativity o operators may be infix prefix unary postfix gt o operators may have short circuit lazy semantics An operation is overloaded if its identifier or operator symbol has multiple visible definitions Overloading is resolved usually stati cally by arity operand types and return type Overloading resolu tion can be exponentially expensive A primitive type has no separately accessible components Exam ples integer character real Boolean A structured type has separately accessible components Examples pointer dereference record field select array subscript disjoint union variant select An associative array is an array whose index type is string A constant is like a variable but it has no L value and an unchanging R value C5655 Fall 2009 5 8 Parameters o Nomenclature 0 Formal parameter the identifier that the procedure uses to re fer to the parameter it is elaborated when the procedure is in voked 0 Actual parameter the expression that computes the value of the parameter it is evaluated in the environment of the caller 0 Linkage The machine oriented mechanism by which the caller A causes control to jump to the called procedure B including initializing B39s stack frame passing parameters passing results back to A and reclaiming B39s stack frame when it has com pleted o Parameter passing modes 0 value mode The formal has its own L value initialized to the R value of the actual The language design may restrict the for mal to read only use Value mode is the only mode available in result mode The formal has its own L value not initialized When B returns the formal39s L value is copied back to the ac tual which must have an L value so the actual cannot be an arbitrary expression Result mode was introduced in Algol W valueresult mode The formal has its own L value initialized to the R value of the actual As B returns its value is copied back to the actual which must have an L value Value result mode was introduced in Algol W reference mode The formal has the same L value as the ac tual which must have an L value which might be a temporary location The language may allow the programmer to specify read only use of the formal parameter Reference mode is the only mode available in Fortran name mode All accesses to the formal parameter re evaluate the actual either for L value or R value depending on the ac cess to the formal This evaluation is in the RE of the caller typ ically by means of a compiled procedure called a thunk Name mode was invented for Algol 60 and never used again C8655 Fall 2009 6 o macro mode The formal parameter is expanded as needed to the text of the actual parameter which by itself need not be syn tactically complete No modern language uses this mode 9 Iterators Lecture 2 912009 0 Iterators allow us to generalize for loops 0 The control Variable of the for loop ranges over a set of Values generated piecemeal by an iterator book 3929 10 o The iterator is like a procedure tallting parameters and return ing Values of a specified type 0 The iterator uses a yield statement to return a Value but it maintains its RE and its program counter in order to continue on demand from the for loop 0 A useful language supplied iterator is int upto low high which yields all the Values in the specified range 0 Iterators are especially useful for generating combinatorial structures 0 Algorithm for generating all binary trees of n nodes book 4111 0 Same thing in Python def binGensize if size gt O for root in rangesize for left in binGenroot for right in binGensize root l yieldquotconsquot left quotquot right quotquot else ll II for aTree in binGen3 print aTree 0 Trace of binGen3 Lecture 3 9 82009 0 Another example yield all nodes in a tree in pseudo Python C5655 Fall 2009 7 def treeNodestree if tree 1 null for element in treeNodestreeleft yield element yield treevalue for element in treeNodestreeright yield element 0 Wouldn39t it be nice to have a yieldal 1 construct def treeNodestree if tree 1 null yieldall treeNodestreeleft yield treevalue yieldall treeNodestreeright This construct might be able to use shortcuts to improve efficiency 10 Macro package to embed iterators in C o Macros are IterSTART IterFOR IterDONE IterSUB IterYIELD 0 Usage 0 Implementation 0 setjumpand longjmpforhnkagebehweaiforandthecon trolling iterator between yield and its controlled loop 0 Padding between stack frames to let longj mp be called with out harming frames higher on the stack Three integers is enough in Linux on an i686 o A Helper routine to actually call the iterator and act as padding 0 The top frame must be willing to assist in creating new frames 11 General coroutines Simula 67 0 Problem binary tree node equality test in symmetric order 0 Solution 0 Independently advance in each tree book 388 C5655 Fall 2009 12 13 o Each coroutine has its own stack main has its own stack All the stacks are joined Via static chain pointers into a cactus stack A scope must not exit until all its children exit or we must use a reference count This is an example of the dangling NLRE problem Syntax Simula 67 0 Records have initialization code that may execute detach 0 Another coroutine may resume it Via explicit ca 1 1 Ole Johann Dahl designer of Simula 67 got the Turing award in 2001 Power loops How can you get a dynamic amount of for loop nesting Application 71 queens book 5729 Usual solution single for loop with a recursive call Cannot use that solution in Fortran which does not allow recursion Solution Power loops book 5728 Implementation Only needs branches no recursion book 5931 How general is this facility Do power loops Violate principle 20 IO Attempt to strip a programming language of all non essential ele ments What39s left goto with parameters hence formal actual bindings Parameters can be integer anonymous function or continuation A function is passed by closure pointer to code pointer to NLRE C5655 Fall 2009 14 15 16 A continuation is a function whose parameters have already been bound It is passed by a closure along with the parameters Examples book 5015 and following Lecture 5 9172009 Dimensions Lecture 6 9 22 2009 book 707 Applies to reals Can be embedded into a strong type system ML ML is functional but we are particularly interested in its type sys tem with these important aspects 0 The language is strongly typed o The compiler infers the types of identifiers if possible 0 Higherorder types are easily represented 0 Types can be polymorphic that is expressed with respect to type identifiers Examples starting on How does currying work Types Lecture 9 1012009 A type is a property of an R Value or of an identifier that can hold R Values C8655 Fall 2009 10 o The property consists of a set of values 0 Strong typing means the compiler o knows the type of every R value and identifier o enforces type compatibility on assignment and formal actual binding 0 compatible means type equivalent a subtype or convert ible o A subtype consists of a subset of the values 0 Assignment and formal actual binding require a dynamic check 0 Subtype examples range of integers subclass of class 0 subTypeVar baseTypeVar 0 Type equivalence o structural equivalence expand type to a canonical string rep resentation equivalence is string equality o lax ignore field names ignore array bounds ignore index type atten records 0 pointers require that we handle recursive types and still build finite strings 0 name equivalence reduce a type to an instance of a type con structor 0 type constructors array po interTo enum struct derived 0 lax declaration equivalence multiple uses of one type constructor are equivalent 17 What does polymorphic mean People use the term polymorphic to mean various features 0 Static procedure overloading with compile time resolution Ada ava Here the type of the procedure its signature determines whether it is a viable candidate for resolving the overloading 0 Dynamic method binding Java Smalltalk C deferred binding Here the dynamic type class of the value object determines which procedure method to invoke C8655 Fall 2009 1 1 0 Types described by type identifiers perhaps with the compiler infer ring the types of values ML Here the dynamic type constraints on the parameter and return value determine the effective type of the function Passing an ADT as a parameter Russell Generic packages Ada templates C 18 Unusual rstclass values A rstclass value can be returned from a function In languages with variables a first class value can be stored in a variable 0 A secondclass value can be an actual parameter 0 A thirdclass value can be used in its ordinary way Labels and procedures 0 Usually third class values the ordinary way is in a goto statement or a procedure call statement They could be second class They must be passed as a closure For a label the closure includes the RE of its target so the stack can be unwound to the right place For a procedure the closure includes its NLRE to resolve non local references To make them first class we still need to build a closure which we can then store in a variable But the lifetime of that variable might exceed the life of the RE stored in the closure This is the danglingNLRB problem book 7611 0 To resolve the dangling NLRB problem 0 Let it happen and call the program erroneous o Prevent it from happening by restricting the language 0 Don39t let labels or procedures be first class Pascal 0 Don39t let scopes nest so there is no need for closures for procedures labels are still problematic C 0 Only allow top level procedures or labels be first class Modula 2 0 Let it happen and make it work allocate all frames from the heap and use explicit release reference counts suffice C8655 Fall 2009 12 19 Can types be second or rst class 0 Letting a type be second class is a step toward polymorphism o Second class types allow generic packages Ada templates C 0 However we only allow types to be passed at compile time dur ing generic package instantiation 0 One can restrict the range of the actual type the type of the type by a Java like interface 0 An attempt at first class types dynamic book 11268 Actually this attempt is an attempt to extend strong typing to dynamic types it is not the same as making types first class 0 Another attempt at first class types Russell 0 But what Russell calls a type we would call an ADT abstract data type which is something like a Java class 0 So a Russell actually introduces dynamic class definitions 0 We will see dynamic class definitions in Smalltalk later 20 Haskell o Haskell is a functional programming language much like ML with additional features Haskell uses indentation for grouping much like Python This de sign makes programs compact but harder to read if routines are long and very difficult for blind programmers to construct All functions are fully curried Haskell evaluates all expressions lazily Therefore one can express infinite lists naturalNumbers O ones l ones Haskell allows lists to be built using comprehensions which are like sets in Zermelo Frankel set theory C8655 Fall 2009 squares Int squares nn n lt l 5 fermat Int fermat a b c n alt 3 blt 3 Clt3 nlt 3 aAn bAn cAnHJ quicksort Int gt Int quickSort quickSort azrest quickSort b b lt rest b lt a a quickSort b b lt rest b gt a 0 List comprehensions give us an easy way to implement Lisp39s mapcar function mapcar list function function a a lt list In fact we can generally avoid using mapcar entirely 0 One can combine lazy evaluation comprehension and infinite lists to gain memoization dynamic programming cache 2 Int cache fib X X lt O fib Int gt Int fib 0 l fib l l fib n cachen l cachen 2 o Haskell has interfaces much like Java which are like types that pro vide certain operations