New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Miss Emery VonRueden


Miss Emery VonRueden
GPA 3.55


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 121 page Class Notes was uploaded by Miss Emery VonRueden on Tuesday October 13, 2015. The Class Notes belongs to CSC 4101 at Louisiana State University taught by Staff in Fall. Since its upload, it has received 13 views. For similar materials see /class/222869/csc-4101-louisiana-state-university in ComputerScienence at Louisiana State University.




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/13/15
Programming Languages Tev k Kogsar Lecture XXVI April 27 2006 Road map o Shared Memory o Synchronization Spin Locks Barriers Semaphores Monitors Memory Architectures Distributed Memory Shared Memory Distributed Shared Memory Distributed Memory Each processtask has access to its own memory Shared Memory Each processTask has access To The same memory Distributed Shared Memory Memory is physically dis rr ibu red bu r concep rually shared Synchronization Major challenge for shared memory and distributed shared memory architectures Two forms Mutual exclusion ensures that only one process thread is executing a critical section at any time o Never read or write shared data while it s being modified by another processthread Conditional synchronization ensures that a processthread does not proceed until some specific condition holds o eg until a given variable has a given value More synchronization 9 Less parallelism Do not do synchronization unless critical Spin Locks Lock mechanism for enforcing limits on access to a resourceshared data in a concurrent environment Spin Lock A lock where a threadprocess waits in a loop quotspinsquot repeatedly checking until the lock becomes available As the thread remains active but isn39t performing a useful task the use of such a lock is called busy waiting Once acquired spin locks will usually be held until they are released in some implementations they may be automatically released if the thread blocks aka quotgoes to sleepquot Spin Locks Typedef bool lock bool testandset lock l needs to be an atomic HW instructionl if l false l true return true else return false void acquirelock lock l while ltestandset l wait void releaselock lockl l false Spin Locks Spin locks are efficient if threadsprocesses are only likely to be blocked for a short period of time they avoid the overhead of operating system process re schedu 39 often used within operating system kernels Spin locks are wasteful if the lock is held for a long period of time they do not allow other threads processes to run while a thread process is waiting for the lock to be released contention always inefficient if used on systems with only one processor as no other thread would be able to make progress while the waiting thread process spun Barriers A point in the control flow where each threadprocess must stop until all other processesthreads reach this point Require consensus among all threadsprocessors Fundamental to dataparallel computing Barriers set a global counter n where n is of threadsprocessors Each threadprocess reaching its barrier decrements counter by 1 and stops atomic fetchanddecrement loop until counter If counter becomes 0 all threads continue execution Semaphores protected variables classical method to restrict access to shared resources invented by Edsger Disjkstra and first used in THE operating system 1968 basically a counter with two associated operations P Wait decrement counter and wait until positive o Probeer try V Signal increment counter and wake up a waiting thread o Verhoog increase Semaphores The value of a semaphore is the number of units of the resource which are free If there is only one resource a quotbinary semaphorequot with values 0 or 1 is used The P operation busywaits or maybe sleeps until a resource is available whereupon it immediately claims one V is the inverse it simply makes a resource available again after the process has finished using it Init is only used to initialize the semaphore before any requests are made The P and V operations must be atomic which means that no process may ever be preempted in the middle of one of those operations to run another operation on the same semaphore Semap hores P2maphure s awaits gt a then s 54 must be atumic urine 5 gt o is detected v 2maphure s s m must be atumic v init2maphure s integer v Dining Philosophers Problem rFive phiiosophevs speho iheh ihhe eawvg aha ihihhhg rThey ave Si ng m iyohi oi a Yound iaoie Wiih spagheiii sew gtTheye ave iwe piaies ai ihe iaoie aha iiveiovks sei beiweeh ihe piaies 39Eaimgihe spagheiii veqwesthe use oi Mo iovks whioh ihe phiiosophevs pioh up one ai a ihhe 39possibiiity oi deadiook ii every phiiosophev hoios a ieii iovk and mi pevpeiuaiiy iov a hghi iovk 0 Vice vevsa may iead io starvation Disjkstra s Solution For each philosopher i Think Waitroomsemaphore max value 4 Waitleftforki Waitrightforki Eat spaghetti Signalleftforki Signalrightforki Signalroomsemaphore Repeat 1 p9 gt 9 quot5 lquot Only four philosophers would be able to enter the room simultaneously and no deadlock can occur ChandyMisra Solution 1984 For every pair of philosophers contending for a resource create a fork and give it to the philosopher with the lower ID Each fork can either be dirty or clean Initially all forks are dirty When a philosopher wants to use a set of resources i 9 eat it must obtain the forks from its contending neighbors For all such forks it does not have it sends a request message When a philosopher with a fork receives a request message it keeps the fork if it is clean but gives it up when it is dirty If it sends the fork over it cleans the fork before doing so After a philosopher is done eating all its forks become dirty If another philosopher had previously requested one of the forks it cleans the fork and sends it Sleeping Barber Problem Based upon a hypothetical barber shop with one barber one barber chair and a number of chairs for waiting customers When there are no customers the barber sits in his chair and sleeps As soon as a customer arrives he either awakens the barber or if the barber is cutting someone else39s hair sits down in one of the vacant chairs If all of the chairs are occupied the newly arrived customer simply leaves Possible Problems The barber could end up waiting on a customer and a customer waiting on the barber resulting in deadlock The customers may not decide to approach the barber in an orderly manner leading to process starvation as some customers never get the chance for a hair cut even though they have been waiting Solution Use three semaphores one for any waiting customers one for the barber to see if he is idle and a mutegtlt When a customer arrives he attempts to acquire the muteX and waits until he has succeeded The customer then checks to see if there is an empty chair for him either one in the waiting room or the barber chair and if none of these are empty leaves Otherwise the customer takes a seat thus reducing the number available a critical section The customer then signals the barber to awaken through his semaphore and the mutegtlt is released to allow other customers or the barber the ability to acquire it If the barber is not free the customer then waits The barber sits in a perpetual waiting loop being awakened by any waiting customers Once he is awoken he signals the waiting customers through their semaphore allowing them to get their hair cut one at a time Implementation Semaphore Customers Semaphore Barber Semaphore accessSeats mutex int NumberOfFreeSeats The BarberThread whiletrue runs in an infitie loop Customersp tries to acquire a customer if none is available he39s going to sleep accessSeatsp at this time he has been awaken gt want to modify the number of a ts NumberOfFreeSeats Hone chair gets free Barberv the barber is ready to cut accessSeatsv we don39t need the lock on the chairs anymore here the barber is cutting hair The CustomerThread while notCut as long as the customer is not cut accessSeatsp tries to get access to the chairs if NumberOfFreeSeatsgt0 if there are any free seats NumberOfFreeSeats sitting down on a chair Customersv notify the barber who39s waiting that there is a customer accessSeatsv don39t need to lock the chairs anymore Barberp now it39s this customers turn but wait if the barber is busy notCut false else there are no free seats tough luck accessSeatsv but don39t forget to release the lock on the seats Semaphores inadequate in dealing with deadlocks do not protect the programmer from the easy mistakes of taking a semaphore that is already held by the same process and forgetting to release a semaphore that has been taken mostly used in low level code eg operating systems the trend in programming language development though is towards more structured forms of synchronization such as monitors and channels Programming Languages Tev k Kosar Lecture XI February 21 2006 Road map o Control Flow Basic Paradigms o Expression Evaluation Control Flow or Ordering Control flowordering is fundamental in most models of computing Basic paradigms for control flowordering Sequencing the order in which statements appear in code Selection making choices depending on a runtime condition Iteration executing a fragment of code repeatedly Procedural abstraction subroutines functions Recursion Defining an expression in terms of itself Concurrency Execution of two or more program fragments at the same time Nondeterminacy the ordering is unspecified Expression Evaluation Different styles Infix a b quot c Prefix a b c eg Lisp In Ada ab is short for quotab In C ab is short for aoperatorb Precedence associativity see Figure 61 C has 15 levels too many to remember Pascal has 4 levels too few for good semantics Fortran has 8 Ada has 6 Ada puts and 8 or at same level Lesson when unsure use parentheses Expression Evaluation Furl m U I asr zll 39 Alla 7 MthIrIlll39 llw am not W lpr 1N abs IJIINIIIIII39 mlml IIIHHI I D013 Sc x IIHI llrllll39lllh uI Illl Irilrwiwliwl lunar l mod rem div mod and quotn llilnrllilu lul39IAIHII e iillill39V 7 mmr lJIllI 7 Mil llv 7 IIILIH mll lrmIsl Ill39lmn or ltlt gtgt 7 binary loll illlI l39ILLllI IrIl hlIIII amp lIIL IIIUHIIIIHII eqne 1t ltltgtgt ltltgtgt ltltgtgt 1e ge 0 IN illl llllllIIIV lmls lkulllpzlliwllel not r lplulilv lmlsi Kc lIiilrllisll MINI lIlilrwi t39 L39X 1llI39r or i IIlilrWl VO llli39IlKin llll andv ampamp IIHgis rl null liucllal niwl rlluis or II iluglm my eqv neqv IIll IIlIM39 lquImI columnmp mitlllt lll lllg Flglll v ul Operator precedence levels in Formal Pascal cl and Ada Ulr frlrt l39illHE ill lhl top of rho glll l ul ullp lllsh l lightly Expression Evaluation Precedence o If AltB and CltD then Causes an error in Pascal since it is grouped as IfAlt B and C ltD then Associativity 0 Basic arithmetic expressions almost always associate from left to right 932 is 4 not 8 o In Fortran exponentiation operator associates from right to left 232 is 512 2quot9 not 64 3quot2 0 In Ada exponentiation does not associate You have to write I2quot3I2 or 2 3quot2I o In C assignment associates from right to left abac Expression Evaluation 0 Shortcircuiting Consider a lt b ampamp b lt c Ifa gt bthere is no point evaluating whetherb lt c because a lt b M b lt c is automatically false Other similar situations if b 1 0 ampamp ab c if p ampamp p7gtfoo if f H messy Expression Evaluation 0 Orthogonality Features that can be used in any combination Meaning is consistent if if b I 0 then ab 0 else false then if if f then true else messy then o First example Algol 68 a1 begin fb gc end 0 InC Expression Evaluation Combination of Assignment Operators In C aa1 a or a oaab 9 ab o Ai b Ai b difference t1p p p1 t2q q q1 t1 t2 p q Expression Evaluation In languages like Clu ML Perl Pyton it is possible Multiway Assignment ab c d 9 ac bd ab ba 9 tempa ab btemp Expression Evaluation 0 Assignment statement or expression executed for its side effect assignment operators etc handy avoid redundant work or need for optimization perform side effects exactly once C postfix form Expression Evaluation Applying Mathematical Identities a bc d ceb Will be rearranged by some compilers as a bc a bce Then code is generated for a bc d ae Flow Unstructured Flow Go To Structured Flow While loop For loop Sequencing o Sequencing specifies a linear ordering on statements one statement follows another very imperative VonNeuman Selection 0 Selection sequential if statements lf then else lf then elsif else 7 In Lisp cond ClEl quot2E2 Caseswitch statements eg PascalC Casequot 1 clauseiA 23 clauseJ En Selection 0 Code generated wo shortcircuiting Pascal W load gtr3 ampr2 39 ltgt r3 Ll then clause W label not actually used goto L2 elseiclause L3 Selection 0 Code generated w shortcircuiting C r1 1 A r2 1 B if r1 lt r2 goto L4 r1 1 C r2 D 1f r1 gt r2 goto L1 L4 r1 1 E r2 1 F ii rl r2 goto L2 L1 theniclause goto L3 L2 elseiclause L3 Programming Languages Tevfik Kosar Lecture V February 939 2006 Road map o Allocation techniques Static Allocation Stackbased Allocation Heapbased Allocation o Scope Rules Static Scopes Dynamic Scopes Storage Management o Object lifetimes correspond to one of three storage allocation mechanisms Static o absolute address retained throughout program s execution Stack o Allocated amp deallocated in lastin firstout order with subroutine calls and returns Heap o Allocated and deallocated at arbitrary times Stack and heap is used for dynamic allocation Static Allocation Static allocation for Machine language translation of the source code Global variables Local but static variables explicit constants including strings sets etc scalars may be stored in the instructions Static Allocation 39lleniporaries 39l39eniporaries 39l eiuporaries Local Local 4 Vqrhlr leg Variables J quot Local variables Miscellaneous bookkeeping Miscellaneous Miscellaneous bookkeeping bookkeeping Return address Return address Return address Arguments Ar 0 un tents Ar u39unients 1 b and returns and returns and returns Subroutine l Subroutine 2 Subroutine 3 Figure 31 Static allocation of space for subroutines in a language or program Without recursion Stackbased Allocation 0 Why a stack If there is recursion in the language static allocation is no more possible allocate space for recursive routines not necessary in FORTRAN no recursion reuse space in all programming languages Central stack for parameters local variables temporaries Stackbased Allocation spa Amniinvnl minimum D W mm ngb minim 39J39ltimmaim minimum c mar minim Dimmu Hi r Miwnnnmm Mack mm W H WM 1W summum B WWW nplilimwci f MW lolin39n maim mlummm c nlunnlinv A WNW lulllrn rm mm pmm aini Figure 32 Stackbased allocation of space for subroutines I zi hllllll here llmi snln39oniiun A has inn11 wide by the main program and Thnl ii thvn Mills M n niiflul39 B glllrl lrllfhll B slilqunenrlv nulls C which in mm walls D Al sz given llllK thv stark 39srvr 1min m l he rst nimle lomtion on the muck or rhv lust nsml lmznion regisrnr l 611 in a known Lwariuu within in r pointer sp n mnl ihe mum pointer fp on rimmil of the lurrmi snln39oniino my from lum him m nunhilil39 null luulpili r in mnndlur nw unlvr of elds Wit him on Some mailhi1 ih framv uni 39anw enr Stackbased Allocation Contents of a stack frame arguments and returns local variables temporaries bookkeeping saved registers line number static link etc Local variables and arguments are assigned fixed OFFSETS from the stack pointer or frame pointer at compile time Heapbased Allocation Allocation amp deallocation can be done in random order Space management issues Internal fragmentation A block that is larger than required is allocated Extra space is wasted External fragmentation Although there is sufficient space the unused space is scattered and no one piece is large enough to satisfy a request External Fragmentation Allocation request Figure 33 External fragmentation The shaded blocks are in use the clear bloaks are free While there is more than enough total free space remaining to satisfy an allocation request of the illustrated size no single remaining block is large enough Storage Management Techniques First fit select the first block on the list that is large enough to satisfy the request Best fit search the entire list to find the smallest block large enough to satisfy the request Does a better job in preventing external fragmentation Higher allocation cost 9 needs to search the entire list Divide large free blocks into smaller pieces Merge coalesce adjacent free blocks Use n fixed sized lists eg for k1n use 2k size blocks Decrease the search time Scope Rules A scope is a program section of maximal size in which no bindings change or at least in which no redeclarations are permitted see below In most languages with subroutines we OPEN a new scope on subroutine entry create bindings for new local variables deactivate bindings for global variables that are re declared theses variable are said to have a quotholequot in their scope make references to variables Scope Rules o On subroutine exit destroy bindings for local variables reactivate bindings for global variables that were deactivated Scope Example include ltstdiohgt int A 5 void subfunc int A 4 printfquotdquot A Output 43 void main int A 3 subfunc printfquotdquot A Scope Example Procedure A Procedure B Procedure C begin end Procedure D begin end a Static Scope RUIGS begin end Procedure E begin end begin end Static Chains l U l O Figure 35 Static chains Subroutines A B C D and E are nested as shown on the left If the sequence of nested calls at run time is A E B D and C then the static links in the stack will look as shown on the right The code for sulin39outine C can find local objects at known offsets from the franie pointer It can find local objects of the surrounding scope B by clereferencing its static chain once and then applying an o set It can find local objects in B s surrounding scope A by dereferencing its static chain twice and then applying an offset Scope Rules o The key idea in static scope rules is that bindings are defined by the physical lexical structure of the program o With dynamic scope rules bindings depend on the current state of program execution They cannot always be resolved by examining the program because they are dependent on calling sequences To resolve a reference we use the most recent active binding made at run time Scope Rules o Dynamic scope rules are usually encountered in interpreted languages early LISP dialects assumed dynamic scope rules o Such languages do not normally have type checking at compile time because type determination isn39t always possible when dynamic scope rules are in effect Scope Rules Example Static vs Dynamic program scopes input output var a integer procedure first begin end procedure second var a integer begin first a 2 second writea Scope Rules Example Static vs Dynamic o If static scope rules are in effect as would be the case in Pascal the program prints a 1 o If dynamic scope rules are in effect the program prints a 2 o Why the difference The issue is whether the assignment to the variable a in procedure first changes the variable a declared in the main program or the variable a declared in procedure second Scope Rules Example Static vs Dynamic o Static scope rules require that the reference resolve to the most recent compiletime binding namely the global variable a o Dynamic scope rules on the other hand require that we choose the most recent active binding at run time Perhaps the most common use of dynamic scope rules is to provide implicit parameters to subroutines This is generally considered bad programming practice nowadays o Alternative mechanisms exist static variables that can be modified by auxiliaw routines default and optional parameters Scope Rules Example Static vs Dynamic Dynamic cont o At run time we create a binding for a when we enter the main program o Then we create another binding for a when we enter procedure second This is the most recent active binding when procedure first is executed Thus we modify the variable local to procedure second not the global variable However we write the global variable because the variable a local to procedure second is no longer active Programming Languages Tevfik Kosar Lecture January 17th 2006 Contact Information Prof Tevfik Kosar Office 292 Coates Phone 5789483 Email kosarlsuedu Web httQ wwwcctlsuedukosar Office hours Tue amp Thu 130pm 230pm Course web page httpwwwcctlsuedukosarcsc4101 Provide me with your active email address to be added to the class mailing list Road map o Meet the Professor Background Teaching philosophy o Motivation for the Course What expect to learn o Introduction to the Course Material o Administrative details o Take Photos Tevfik Kosar o Joined LSU in August 2005 o Education PhD University of WisconsinMadison CS MS Rensselaer Polytechnic Institute NY CS BS Bosporus University Turkey CompE o Teaching This semester CSC 4101 Programming Languages Next year CSC 4103 Operating Systems CSC 7700 Data Intensive Distributed Computing Research Grid Computing Analogy to the Power Grid A special case for Distributed Computing Spans wide area networks and multiple administrative domains The Center for Computation amp Technology Spend half of my time there Office Johnston 333 Multidisciplinary research httpwwwcctlsuedu The Imminent Data deluge Growth of GenBank Exponential growth of scientific data 2000 05 Petabyte 2005 10 Petabytes 2010 100 Petabytes 2015 1000 Petabytes Sequence millions Ban Palm dDNA mununs I am terrified by terabytesquot Anonymous I am petrified by petabytesquot 9 995 W W 139 9 1quot a Jim Gray 39 I Compuiauonal man I Genome DEE BX GILWVU I IS months Moore s Law outpaced by growth of I Maore39sLaw scientific data 2x Growth l5 monms x Multiplier A High Energy Physics Project LHC The detectors at the LHC will probe fundamental forces in our Universe such as search for the yetundetected Higgs Boson Starting in 2006 the LHC accelerator will produce proton proton collisions with a rate of 109 eventss Four detectors ATLAs cms ALICE LHCB LHC Challenges 11 Petabytes of data per year 100000 CPUs 5000 physicists in 300 institutes in 50 countries The Large Hadron Collider LHC ATLAS From LEPla LHC Superconducting magnets CMS Compact Muon Solenoid A Bioinformatics Project BLAST Goal decode genetic information and map the genomes of humans and other species Uses comparative genomics compares unknown genetic sequences billions to known genomes in search of similarities Current dataset Several Petabytes Future Exponential Growth SCARY Sequencesmiiiian n a as 1995 1935 m1 1m 1997 new An Educational Technology Project WCER Educational Video Processing Build histories of student learning for use in education research and instruction relying on video data Analyze and share large amount of video 1 hour DV video is 13 GB A typical educational research video uses 3 cameras gt 39 GB for 1 hour Current data set gt 500 Terabytes Future Several Petabytes Astro no my MACHO Mapping of Universe 2MASS 2MASSW 217 03 detection of new gtIhane T type dwarfin the constellation Virgo DPOSS galaxies and stars current Datasets Project Data Volume DPOSS 3 TB 2MASS 12 TB SDSS 40 TB Future Productions Project Data Volume WFCAM 20 TByear VISTA 100 TByear LSST 1000 TByear ear infrared View The Optical View GSCII COBE MAP NVSS FIRST GALEX ROSAT How to access and process distributed data Interested 5 nd an email to kosar lsuedu Register for a independent study csc 4999 Take 3 credits for doing research in one of these interesting topics during one zmester Teaching Philosophy Goal For instructor teaching the material For student learning and applying the material in real life Grades are of second degree importance Do not memorize understand the material Exams may be openbook You are only responsible from material Covered in the class Part of projects or homework assignments Programming Languages How many different programming languages are there More than 200 Can you name some of them Which ones have you used before Java C C LispScheme Prolog Language of the Computer Machine Language Consists of 0 s and 1 s Which refers to high and low voltage states 00100111 1010 1101 1111 1111 1101 0000 27bdffd0 afbf0014 0c1002a8 Assembly Language push bx mov bx div bx add dx Direct mapping to machine language Higher Level Languages C C Java Pascal Scheme Prolog First one Fortran Why are there so many programming languages Special Purposes Each language is designed to solve a certain problem o Perl for string parsing and manipulation o CC for systems programming o Java for platform independent programs o Prolog for logic programming and AI o Fortran for numerical computations Personal Preferences Evolution Learn better ways of doing things over time eg from go to to while loops case statements What makes a language successful easy to learn BASIC Pascal LOGO Scheme easy to express things easy use once fluent powerful C Common Lisp APL Algol68 Perl easy to implement BASIC Forth possible to compile to very good fastsmall code Fortran backing of a powerful sponsor COBOL PL1 Ada Visual Basic wide dissemination at minimal cost Pascal Turing Java Programming Paradigms o Group languages as declarative functional Scheme ML pure Lisp FP logic constraintbased Prolog VisiCalc RPG imperative o von Neumann Fortran Pascal Basic C o objectoriented Smalltalk Eiffel C o scripting languages Perl Python JavaScript PHP Why study programming languages Help you choose a language Make it easier to learn new languages Syntactic similarities o C vs Java Conceptual siilarities o C vs Pascal Help you make better use of whatever language you use Choose among alternative ways o Using arrays vs pointers o Loops vs Recursion Simulate useful features in languages that lack them o Faking pointers o Faking modularity Textbooks Required text Programming Language Pragmatics 2nd edition by Michael Scott Morgan Kauffman Publishers 2005 Recommended text Concepts of Programming Languages 6th edition Robert W Sebesta AddisonWesley 2003 There will be additional links for supplementary course material on the course web page Grading The endofsemester grades will be composed of Popup Quizzes 25 Active Contribution 25 Homework 15 Projects 30 Midterm 20 Final Reading Assignment Read chapter 1 from Programming Language Pragmatics PLP Any Questions Hmm 23gt Programming Languages Tevfi k Kosar Lecture XIX March 28 2006 Road map o Logic Languages Predicate Calculus o Prolog Programming Language Basics Queries Resolution Unification Lists Running Prolog Programs Logic Programming 0 Based on predicate calculus Functional lang were based on Lambda Calculus o Predicates buildingblocks Pa1a2aK Define relationships between entities Eg enrolledjohn cs4101 taughtbycs4101 drkosar Logic Programming Axioms define logic rules between predicates H 6 B1 82 B3 Bn Eg takesclassfromXY enrolled XZ taughtbyZY enrolledjohn cs4101 taughtbycs4101 drkosar takesclassfromjohn drkosar Logic Programming Eg green X 6 rainy X rainy batonrouge green batonrouge Prolog Atoms constants foo myConst Baton Rouge Variables Foo Myvar X No variable declarations Variables can be instantiated to arbitrary values at runtime Type checking occurs only when a variable value is used at runtime The scope of each variable is limited to the clause in which it appears Prolog Prolog predicatesfacts rainybatonrouge teachesdrkosar csc4101 Predicatesclauses end with Predicates are called facts and axioms are called rules Prolog axiomsrules snowyX rainyX coldX is the implication symbol indicates and Prolog Queries rainyseattle rainynewyork rainyX X seattle X newyork no Prolog Queries rainyseattle rainyrochester coldrochester snowyX rainyX coldX snowyX X rochester no Resolution ceAB Dec Resolution D 6 A B takes jane csc4101 classmatesXY takesXZ takesYZ Resolution classmatesjane Y takesY csc4101 Unification Patternmatching process used to associate variables with their values studentjoe studentX X joe Unification Rules A constant unifies only with itself Two structures unify iff same functor and same of arguments and corresponding arguments unify recursively A variable unifies with anything Unification a a yes a b no fooa b fooa b yes X a X a no fooa b fooX b a No A B 123 Unification takeslabS takesS C haslabC haslabD meetsinD R islabR takeslabS takesS C meetsinC R islabR Lists a b c can be expressed as using vertical bar notation a b C a b C1 a b C 1 memberX XIT memberX HIT memberX T sorted sorted X sortedA B T A lt B sortedB T Lists appendL A A appendH T A H L appendT A L appenda b c d e L Labcde appendX d e a b c d e X a b c appenda b c Y a b c d e Y d e Prolog predicates do not have a clear distinction between input and output arguments Arithmetic o Builtin is predicate unifies its first argument with the arithmetic value of its second argument isX 12 X 3 X is 12 X 3 3 is 12 yes 12 is 3 no Xis Y lterrorgt Yis12 Xis Y X 3 Y 3 Running Prolog Programs GNU Prolog is already installed on byte rbash7205b gprolog GNU Prolog 1216 By Daniel Dlaz Copyright C 199972002 Daniel Dlaz Starts in Query mode You need to do consultfilename or consultuser to enter the facts and rules into the knowledgebase Multidimensional Arrays as Parameters ammwmammwm o In CIC Vold fun mt matrlX 10 l mt mam mt mat 5 10 fun mat Multidimensional Arrays as Parameters wmmmwmmm o In Ada type MTYPE 1s array INTEGER range 0 INTEGER range ltgt of FLOAT MAT MTYPE l100 1207 functlon FOO M 1n MTYPE return FLOAT ls for ROW 1n M range1 loop Implementation of Subprograms 0 Activation record local variables parameters return value dynamic link static link return address CSC 4101 Programming Languages FORTRAN Activation Record W A m o Allocated statically 0 Needs only local variables parameters return address Static and Dynamic Links 0 Static Link activation record of enclosing scope needed to access nonlocal variables 0 Dynamic Link activation record of caller needed to pop the activation record needed for finding exception handler Displays mwmm mm 0 Alternative old implementation for accessing static information 0 Instead of static link 0 Maintained outside stack 0 Contains pointers to activation records of all active nesting levels 0 Old values are spilled onto stack 0 No traversal of static links CSC 4101 Programming Languages Implementation of Functional Lan ua es WWW V Wmme 0 Activation record must be on heap if function returns a local function if a function escapes its scope 0 Optimized implementations on heap if absolutely necessary in registers if possible otherwise on stack 0 Garbage collection Implementation on RISC 0 Activation record in registers o On SPARC 6 parameters in registers o On MIPS 4 parameters in registers o If registers are exhausted spill an old activation record onto stack 0 On SPARC 8 register windows spilling needed after 8 calls 0 Inefficient for recursion Exception Handling mmammmi 0 Alternative mechanism for returning from function 0 In c mt maln i try foo 42 catch mt x l mt foo mt 1 throw mt throw 17 CSC 4101 Programming Languages Exception Handling in Java class Ex extends Exception Vold Mam Strlngii args try foo427 catch EX e i flnally mt foo mt 1 1f throws EX some thlngTe rr 1bleHappenS 0 1 row new Exception Handling 0 Handler searched for along call chain 0 Jumps out across multiple functions 0 May require destructor calls in intermediate 5 opes o Conceptually Return address is continuation param Exception is error continuation Continuation is function to compute the rest of the program CSC 4101 Programming Languages Programming Languages Tev k Kosar Lecture XVI March 16 2006 Road map o Type Inference o Records Structures o Variant Records Unions Type Inference Suppose the following operation type Atype 020 Btype 1020 var a Atype b Btype What will be the type of ab Possible values range from 10 to 40 So will the type 040 In usual cases the result of an arithmetic operation on a subrange has the subrange s base type eg integer Records Structures o In C struct element char name2 int atomicnumber double atromicweight Bool metallic o In Pascal type element record name twochars atomicnumber integer atomicweight real metallic Boolean end Records Structures 4 bytes32 bits I type element record name twoichars Micnumber atomicinumber integer atomice atomiciweight real metallic Boolean end Figure 71 Likely layout in 111ernory for objects of type element on a 32bit machine Alignment restrictions lead to the shaded quotholesquot Fields of a record are stored in adjacent locations in memory Compiler keeps track of the offset of each field within each record type The element record occupies 20 bytes of memory 5 bytes are wasted In an array of elements compiler will denote 20 bytes for each member Records Structures gt1 lgt39tlt 32 hits type element packed record I name twoichars name atomlc atomlcinumber Integer I atomiciweight real atomic Weight metallic Boolean metallic end Figure 72 Likely memory layout for packed element records The atomicnumber number and atomicweight elds are nonaligned and 111 only he road 1 writtmr 011 Miami 11m Chihes Via rnulti instruction sequences Space optimization by pushing fields together To access a nonaligned field compiler has to issue a multi instruction sequence retrieve multiple pieces and reassemble Now element record consumes only 15 bytes Records Structures type element record name twoichars metallic Boolean atomicinumber integer atomiciweight real 4 bytes32 bits l name I metallic atomicmumber atomicweight end Figure 73 Rearranging record elds to minimize holes By sorting elds according to the size of their alignment constraint a compiler can minimize the space devoted to holes While keeping the elds aligned An alternative way would be rearranging record s fields Some compilers do this automatically t Now element record consumes 16 bytes only 1 byte wasted Variant Records Unions Provide two or more alternative fields only one is valid at a given time type element record name twoichars atomicinumber integer atomiciweight real metallic Boolean case naturallyioccuring Boolean of true source stringiptr prevalence real false lifetime real Variant Records Unions l bytes3392 bits I I 7 Al bytes32 bits 7 I name name I I atomicnumber atomicnumber atomlC atomi cweight metallic source lifetime Figure 4 Likely memory layouts for element variants The value of the naturallyoccurring eld shown here with a double border determines Which of the interpretations of the remaining space is valid Type stringptr is assumed to he repre sented by a four byte pointer to dynamically allocated storage Variant Records Unions type tag isint isreal isbool var test record case which tag of isint i integer isreal rzreal isbool szoolean testwhich isreal testr 30 writelntestr Output 30 Variant Records Unions type tag isint isreal isbool var test record case which tag of isint i integer isreal rzreal isbool szoolean end testwhich isreal testr 30 writelntesti Dynamic semantic error Variant Records Unions type tag isint isreal isbool var test record isbool szoolean testwhich isreal testr 30 testwhich isint writelntesti Not an error but the output will be junk Variant Records Unions type tag isint isreal isbool var test record isint i integer is real rzreal isbool szoolean X test which isreal 9nd required testr 30 writelntesti Not an error but the output will be junk Variant Records Unions Variant records with tags discriminated unons Variant records without tags nondiscriminated unions Variant Records Unions 39l bytes32 hits l l 44 bytes32 bits I metallic name I metallic source lifetime atomic number atomi cnumber atomic atomicJIeigbt Figure 75 Likely memory layout for a variant record in Modula Z Here the variant portion of the record is not required to lie at the end Every field has a fixed offset from the beginning of the record with internal holes necessary following small size variants Subroutines and Control Abstraction Textbook Chapter 8 Subroutines and Control Abstraction o Mechanisms for process abstraction 0 Single entry except FORTRAN PLII o Caller is suspended 0 Control returns to caller Design Issues 0 Syntax type checking 0 Parameter passing mechanism 0 Static or dynamic allocation of locals 0 Static or dynamic scope 0 Environment of parameter functions 0 Overloading o Generics 0 Separate compilation CSC 4101 Programming Languages Syntax W EWWWWW o FORTRAN SUBROUTINE ADDER parameters 0 Ada procedure ADDER parameters 0 C Vold ADDER parameters More Syntax WWW o Positional or keyword parameters 0 Default values 0 Ada example functlon F X FLOAT Y INTEGER 1 Z FLOAT RETURN FLOAT I 1 F 314 Z gt 271 Type Checking Wmammm o Are argument types checked against parameter types 0 If functions are passed as arguments is the function type checked Kernighan amp Richie C 1nt foo mt f mt bar mt 1 mt j l foo bar CSC 4101 Programming Languages ParameterPassing Methods ammw o CallbyValue CopyIn Eager Eval o CallbyResult CopyOut o CopylnCopyOut o CallbyReference o CallbyName o CallbyNeed Lazy Evaluation CallbyValue WWW WWWW o Allocate memory for parameter 0 Evaluate argument 0 Initialize parameter with value 0 Call procedure 0 Nothing happens on return 0 Used in C C Pascal Lisp ML etc CallbyValue Example int a 1 Vold foo mt x l a and K have same Value changes to a or x don t affect other Varlable argument can be expresslon foo a a no modlflcatlons to a CSC 4101 Programming Languages CallbyResult o Argument must be variable 0 Allocate memory for parameter 0 Don t initialize parameter 0 Call Procedure 0 0 Copy parameter into argument var 0 Return from procedure CallbyResult Example Vold foo 1nt x i x 1s not 1n1tlallzed changes to a or x don t affect other Varlable argument must be Varlable foo a a was modlfled CallbyValueResult mgggggggggggo 0 Combination of previous two 0 Copy argument value on call 0 Copy result on return 0 Used by Ada for parameters of primitive type in inout mode CSC 4101 Programming Languages CallbyValueResult Example 111 Vold foo mt x l a and K have same Value changes to a or x don t affect each other argument must he Varlable foo a a nught be modlfled CallbyReference 0 Evaluate argument into temporary 0 Parameter is alias for location of tmp 0 Call procedure 0 Nothing happens on return 0 Used by FORTRAN before 1977 Pascal var parameter CallbyReference Example 11139 a 47 Vold foo mt x l a and x reference same locatlon changes to a and x affect each other argument can he an expresslon foo a a nught be modlfled CSC 4101 Programming Languages CallbyRef in FORTRAN IV Im plementations W WMWW WW SUBROUTINE FOO I RETURN FOO 10 J gets value 5 CallbyName Wzmmm mi 0 Don t evaluate argument 0 Create closure to evaluate argument 0 Call procedure 0 Eval arg by calling parameter closure 0 Nothing happens on return 0 Used by ALGOL60 Simula67 0 Similar to macro expansion eg TeX n CallbyName Example vold foo mt x l x 1s a functlon to get value of argument evaluate x0 when value 15 needed argument can be an expresslon foo a a no modlflcatlons to a CSC 4101 Programming Languages CallbyNeed Lazy Evaluation 0 Similar to Callby Name o Argument evaluated only once 0 Result kept in temporary 0 Behavior differs with side effects 0 Used by Haskell Miranda Example Lazy Evaluation mt dlverge i return diverge mt 1f7thenielse mt c mt t mt e e mt 1 1f7then7elsel 42 d1verge Static vs Dynamic Locals mmmmmmmmm 0 Static efficient no time for deaocation required retain value across function calls 0 Dynamic on the stack required for recursive functions on modern hardware cheap access let compiler do the optimizations CSC 4101 Programming Languages Implementation of Parameter mama WWW o Allocate activation record in registers or on the stack 0 Copy values into activation record 0 Copy pointers for Callby Reference o Encapsulate lazy args in closure 0 Branch to function code Environment of Function Parameters Warsaw am 0 Function is passed down int x 1 static scoping int foo return x int bar int f 0 int x dynamic scoping int i bar foo Static vs Dynamic Scope WngWsm 0 Static scope nonlocal variables are looked up in statically enclosing scope Need static link for nested functions i gets value 1 0 Dynamic scope nonlocals are looked up along dynamic call chain i gets value 2 CSC 4101 Programming Languages Environment of Function Parameters 0 Function is passed up deflne add D lambda m lt n m deflne addl add 1 deflne addS add 5 deflne 1 addl 10 deflne addS 10 Implementation of Closures mmmmmmm 0 Functions are represented as pair pointer to code pointer to environment 0 Activation records might be on heap 0 Needs garbage collection Eg e don t knowwhen to reclaim the activation record of add Garbage Collection WWMWWWMW o No explicit free or delete c When memory runs out GC traverses life data structures starting with global variables and s ack marks reachable data scans heap to find unreachable data collects unreachable data in free list may com pact heap CSC 4101 Programming Languages Overloading vs Multimethods mw m mmm 0 Multiple methodsfunctions with same name different arg types mt foo mt mt foo float o Overloading method selection at compile time o Multimethods method selection at run time Overloaded Operators Wammmmam 0 Allow redefining operators 0 Ada function 0 C u operatorquot allows redefinition of u gt 0 etc Generlc Functlons 0 Functions with type parameter template ltclass Typegt Type max Type 11 Type m returnngtmn m l o lnstantiated at compile time o Betterthan using preprocessor CSC 4101 Programming Languages Separate Compilation o Compiler needs type information of other compilation units 0 C use include 0 Java search in current directory CSC 4101 Programming Languages Programming Languages Tevfik Kosar Lecture XX April 4 2006 Road map Subroutines Allocation Strategies Calling Sequences Parameter Passing Generic Subroutines Exception Handling Coroutines Review Of Stack Layout Allocation strategies Static 0 Code 0 Globals 0 Own variables 0 Explicit constants including strings sets other aggregates 0 Small scalars may be stored in the instructions themselves Review Of Stack Layout C D L Sta Lic Dynamic Links n 39s Figure 81 Example of subroutine nesting taken from Figure 35 Within B C and D all ve routines are Visible Within A and E routines A B and E are Visible but C and D are not Given the calling sequence A E B D C in that order frames Will be allocated on the stack as shown at right with the indicated static and dynamic links Review Of Stack Layout 0 Allocation strategies 2 Stack parameters 0 local variables 0 temporaries o bookkeeping information Heap dynamic allocation Review Of Stack Layout 0 Contents of a stack frame bookkeeping return PC dynamic link saved registers line number saved display entries static link arguments and returns local variables temporaries Calling Sequences 0 Maintenance of stack is responsibility of calling sequence and subroutine prolog and epilog space is saved by putting as much in the prolog and epilog as possible time may be saved by putting stuff in the caller instead where more information may be known eg there may be fewer registers IN USE at the point of call than are used SOMEWHERE in the callee Calling Sequences 0 Common strategy is to divide registers into callersaves and calleesaves sets caller uses the quotcalleesavesquot registers first quotcallersavesquot registers if necessary Local variables and arguments are assigned fixed OFFSETS from the stack pointer or frame pointer at compile time some storage layouts use a separate arguments pointer the VAX architecture encouraged this Calling Sequences 4 5 Arguments tn called routines Temporaries Local Direction of stack growth variables ower addresses Saved regs static link Saved fp Return address Arguments 39oni caller Figure 82 A typical stack frame Though we draw it growing upward on the page the stack actually grows downward toward lower addresses on most machines Arguments are accessed at positive offsets from the fp Local variables and temporaries are accessed at negative offsets from the fp Arguments to be passed to called routines are assembled at the top of the frame using positive offsets from the sp 9 Calling Sequences C on MIPS o Caller saves into the temporaries and locals area any callersaves registers whose values will be needed after the call puts up to 4 small arguments into registers 4S7 aOa3 it depends on the types of the parameters and the order in which they appear in the argument list puts the rest of the arguments into the arg build area at the top of the stack frame does jal which puts return address into register ra and branches 0 note that jal like all branches has a delay slot Calling Sequences C on MIPS o In prolog Callee subtracts framesize from sp saves calleesaves registers used anywhere inside callee copies sp to fp In epilog Callee puts return value into registers mem if large copies fp into sp see below for rationale restores saved registers using sp as base adds to sp to deallocate frame does jra Calling Sequences C on MIPS After call Caller moves return value from register to wherever it39s needed if appropriate restores callersaves registers lazily over time as their values are needed 0 All arguments have space in the stack whether passed in registers or not 0 The subroutine just begins with some of the arguments already cached in registers and 39stale39 values in memory Calling Sequences C on MIPS o This is a normal state of affairs optimizing compilers keep things in registers whenever possible flushing to memory only when they run out of registers or when code may attempt to access the data through a pointer or from an inner scope Calling Sequences C on MIPS 0 Many parts of the calling sequence prologue andor epilogue can be omitted in common cases particularly LEAF routines those that don39t call other routines leaving things out saves time simple leaf routines don39t use the stack don39t even use memory and are exceptionally fast Parameter Passing 0 Parameter passing mechanisms have three basic implementations value valueresult copying reference aliasing closurename 0 Many languages eg Pascal provide value and reference directly Parameter Passing o CC functions parameters passed by value C parameters passed by reference can be simulated with pointers C void procint Xint y X Xy proc ampab or directly passed by reference C void procintamp X int y X X y procab Parameter Passing o Ada goes for semantics who can do what In callee reads only Out callee writes and can then read formal not initialized actual modified In out callee reads and writes actual modified 0 Ada inout is always implemented as valueresult for scalars and either valueresult or reference for structured objects Parameter Passing o In a language with a reference model of variables Lisp Clu pass by reference sharing is the obvious approach 0 It39s also the only option in Fortran o If you pass a constant the compiler creates a temporary location to hold it o If you modify the temporary who cares o Callby name is an old Algol technique 0 Think of it as call by textual substitution procedure with all name parameters works like macro what you pass are hidden procedures called THUNKS value in const out Ada val ue result var ref sharing in out Ada name Algol 6390 Parameter Passing implementation mechanism value value or reference value or reference value reference value or reference value or reference closiu e thunk permissible operations read write read only write only read write read write read write 2 gt1 Fr m read read write change to actual no no yes yes yes yes yes yes alias no mayh e mayl e no yes yes mayl 6 yes Figure 83 Parameter passing modes Column 1 indicates common names for modes Column 2 indicates implementation Via passing of values references or closures Column 3 indicates whether the callee can read or write the formal parameter Column 4 indicates whether changes to the formal parameter affect the actual parameter Column 5 indicates whether changes to the formal or actual parameter during the execution of the subroutine may be visible through the other Generic Subroutines and Modules Generic modules or classes are particularly valuable for creating containers data abstractions that hold a collection of objects Generic subroutines methods are needed in generic modules classes and may also be useful in their own right Exception Handling 0 What is an exception a hardwaredetected runtime error or unusual condition detected by software 0 Examples arithmetic overflow endoffile on input wrong type for input data userdefined conditions not necessarily e TO rs Exception Handling 0 What is an exception handler code executed when exception occurs may need exception a different handler for each type of 0 Why design in exception handling facilities allow user to explicitly handle errors in a uniform manner allow user to handle errors without having to check these conditions explicitly in the program everywhere they might occur Coroutines Coroutines are execution contexts that exist concurrently but that execute one at a time and that transfer control to each other explicitly by name Coroutines can be used to implement iterators Section 653 threads to be discussed in Chapter 12 Because they are concurrent ie simultaneously started but not completed coroutines cannot share a single stack 23 A h R C M B A to Q S Q M c R Figure 85 A cactus stack Each branch to the side represents the creation of a coroutine A B C and D The static nesting of blocks is shown at right Static links are shown with arrows Dynamic links are indicated simply by vertical arrangement each routine has called the one above it 24 12 Programming Languages Tevfi k Kogsar Lecture XV March 14 2006 Road map Data Types Type Checking Polymorphism Type Equivalence Polymorphism Data Types Types provide implicit context for many operations ab Types of a and b determine which addition function to use eg integer addition or floating point addition new p will allocate storage from the heap right size to hold the object pointed by p Data Types Types limit set of operations prevents illegal or meaningless operations adding a record and a char passing a file as parameter to a functions which expects an int taking sinus of a pointer Type Checking Process of ensuring a program obeys the language s type compatibility rules Strongly typed language prohibits application of any operation to any object that is not intended to support that operation Statically typed language if it is strongly typed and type checking can be performed at compile time In practice most type checking is performed at compile time and the rest at runtime Polymorphism Allows same code to work with objects of multiple types p1 p2 p3 p1 can be int char pointer array list record the compiler does not need to know whether addition function is implemented for all of these types Type Checking Every definition of an object must specify the object s type statically types long In type checking three important notions type equivalence type compatibility type inference Type Equ1valence Two principal ways of defining type equivalence Structural equivalence Two types are equal if they consist of the same components 1 type 001 record a b integer end 2 type 002 record a b integer en 3 type 003 record b integer 4 type 004 record b integer a integer end The last one is equal to the rest in most languages but not in ML Type Equivalence o Structural equivalence Example 2 1 type str1 array 1 10 of char 2 type str2 array 1 25 of char 3 type str3 array 09 of char The second one is equal to the first one but not the third one length of the array is same but index values are different Type Equivalence Name equivalence Each definition introduces a new type 1 type foo1 record a b integer end 2 type fooZ record a b integer end foo1 and fooZ are considered as different types Type Compatibility Most languages require type compatibility instead of type equivalence depending on the context Eg Assignment statement ab The type of the right hand side must be compatible with that of the left hand side Eg Addition ab The types of both operators must be compatible with either integer or with floating point type Coersion Automatic implicit conversion of types Eg int a float b float c b a c a b Programming Languages Tev k Kogsar Lecture V February 739 2006 Road map o Names o Scopes o Binding Binding Times Static vs Dynamic Binding Object Lifetime amp Storage Management Name Scope and Binding o A name is exactly what you think it is Most names are identifiers o Constants variables functions symbols like 3939 can also be names o A binding is an association between two things such as a name and the thing it names o The scope of a binding is the part of the program textuallyin which the binding is active Binding Time o Binding Time is the point at which a binding is created or more generally the point at which any implementation decision is made language design time program structure control flow possible types language implementation time Coupling of HO to 05 o arithmetic overflow o Maximum sizes of stack and heap o Precision of the number of bits of fundamental types Binding Time o Implementation decisions continued program writing time o algorithms names compile time o Mapping of high level code to machine language link time o layout of whole program in memory A name in one module refers to an object in another module load time o 05 loads the program into memory before running o choice of physical addresses Binding Time o Implementation decisions continued run time o valuevariable bindings sizes of strings o subsumes program startup time module entry time elaboration time point at which a declaration is first quotseenquot procedure entry time block entry time statement execution time Static vs Dynamic Binding o The terms STATIC and DYNAMIC are generally used to refer to things bound before run time and at run time respectively static 9 binding before run time quotdynamic 9 binding at run time Binding In general early binding times are associated with greater efficiency Later binding times are associated with greater flexibility Compiled languages tend to have early binding times Interpreted languages tend to have later binding times Object Lifetime Key events creation of objects creation of bindings references to variables which use bindings temporary deactivation of bindings reactivation of bindings destruction of bindings destruction of objects Object Lifetime The period of time from creation to destruction is called the LIFETIME of a binding If object outlives binding it39s garbage If binding outlives object it39s a dangling reference The textual region of the program in which the binding is active is its scope In addition to talking about the scope of a binding we sometimes use the word scope as a noun all by itself without an indirect object Storage Management o Object lifetimes correspond to one of three storage allocation mechanisms Static o absolute address retained throughout program s execution Stack o Allocated amp deallocated in lastin firstout order with subroutine calls and returns Heap o Allocated and deallocated at arbitrary times Stack and heap is used for dynamic allocation Static Allocation Static allocation for Machine language translation of the source code Global variables Local but static variables explicit constants including strings sets etc scalars may be stored in the instructions Programming Languages Tevfi k Kogsar Lecture XII February 23rd 2006 Road map o Iteration Loops Iterator Objects o Recursion Tail Recursion o Evaluation Order Iteration amp Recursion Mechanism that allow a computer to perform similar operations repeatedly Iteration is used more often than recursion Iteration Loops Enumeration controlled Loop o Executed once for even value in a given finite set o Number of iterations known Logically controlled loop o Executed until some Boolean condition met o Depend on a runtime value Loop implementations FOR i first TO last BY step DO 0 Implementation 1 r2 step r3 last L1 if r1 gt r3 goto L2 r1 r1r2 Goto L1 L2 Implementaion 2 r1 r1r2 L2 139 r1 lt r3 goto L1 Iterator Objects Instead of a simple arithmetic sequence they allow us to iterate on any welldefined set eg pointers For Iteratorltntegergt it myTreeiterator ithasNeXt Integerl itnegtltt Systemoutprintlni Iterating without Iterators treenode mytree treeiter TI for ticreatemytree ampti tidoneti treenode n tivalti tideleteampti Logically Controlled Loops Terminate the condition somewhere in the loop o Where Pretest Loops Terminating condition before each iteration readlnline While line1 ltgt 5 do readln line Posttest L00 5 Terminating condition at the bottom of the loop repeat readln line until line1 5 Logically Controlled Loops Midtest Loops Terminating condition in the middle of the loop while true do begin readlnline if line1 5 exit end o Recursion A subroutine calling itself Requires no special syntagtlt Iteration is generally more efficient than recursion But optimized compilers can generate more excellent code for recursive functions Tail Recursion Additional computation never follows a recursive call int gcdint a int b i a b return a else if agtb return gcdab b else return gcda ba Dynamically allocated stack space is unnecessary can be reused Evaluation Order When to evaluate the arguments of a function fint a int b main fXy Zt Applicativeorder evaluation Evaluate arguments before passing them to subroutine Normalorder evaluation Evaluate them only when it is needed Applicative order Generally more clear and efficient Normal order Can generate faster code in some cases Can generate code that works when applicative order would lead to runtime error Lazy Evaluation Similar to normalorder evaluation Keeps track of which expressions have already been evaluated and reuses them whenever needed Programming Languages Tev k Kosar Lecture XVIII March 23rd 2006 Road map Arrays Pointers Lists Files and IO Arrays Two layout strategies for arrays Contiguous elements Row pointers Row pointers an option in C allows rows to be put anywhere nice for big arrays on machines with segmentation problems avoids multiplication nice for matrices whose rows are of different lengths o eg an array of strings requires extra space for the pointers Arrays Figure 710 Contiguous array allocation V row pointers in C The declaration on the left is a true tVyo dimensional array The slashed boxes are NUL bytes the shaded areas are holes The declaration on the right is an array of pointers to arrays of characters In both cases we have omitted bounds in the declaration that can be deduced from the size of the initializer aggregate Both data structures permit individual characters to be accessed using double subscripts but the memory layout and correspondng address arithmetic is quite di erent Arrays 0 Example Suppose A array Ll Ul of array L2U2 of array L3U3 of elem D1 Ul Lll D2 U2 L2l D3 U3 L3l Let S3 size of elem 82 D3 S3 81 2 D2 82 Address of Figure 7ll Virtual location of an array with nonzero lower bounds By computing the constant portions of an array index at compile time we e ectively index into an array Whose starting address is o set in memory but whose lower bounds are all zero Arrays 0 Example continued We could compute all that at run time but we can make do with fewer subtractions i t 81 j t 32 k 3 address of A 7 L1 r 31 L2 r 32 L3 83 The stuff in square brackets is compiletime constant that depends only on the type of A Strings 0 Strings are really just arrays of characters 0 They are often specialcased to give them flexibility like polymorphism or dynamic sizing that is not available for arrays in general It39s easier to provide these things for strings than for arrays in general because strings are one dimensional and more important noncircular Sets 0 We learned about a lot of possible implementations Bitsets are what usually get built into programming languages Things like intersection union membership etc can be implemented efficiently with bitwise logical instructions Some languages place limits on the sizes of sets to make it easier for the implementor There is really no excuse for this Pointers And Recursive Types 0 Pointers serve two purposes efficient and sometimes intuitive access to elaborated objects as in C dynamic creation of linked data structures in conjunction with a heap storage manager 0 Several languages eg Pascal restrict pointers to accessing things in the heap Pointers are used with a value model of variables They aren39t needed with a reference model Pointers And Recursive Types Figure 7413 Implementation of a tree in Lisp A diagonal slash through a box indicates a nil pointer The C and A tags serve to distinguish the two kinds of memory blocks cons cells and blocks containing atoms Pointers And Recursive Types Figure 714 Typical implementation of a tree in a language with explicit pointers As in Figure 713 a diagonal slash through a box indicates a nil pointer Pointers And Recursive Types o C pointers and arrays int a int a int ta int a o BUT equivalences don39t always hold Specifically a declaration allocates an array if it specifies a size for the first dimension otherwise it allocates a pointer int a int a int an pointer to pointer to int neelement array of row pointers int anm 27d array Pointers And Recursive Types o Compiler has to be able to tell the size of the things to which you point So the following aren39t valid int a bad int a bad C declaration rule read right as far as you can subject to parentheses then left then out a level and repeat int an neelement array of pointers to integer an pointer to neelement array of integers int Pointers And Recursive Types 0 Problems with dangling pointers are due to explicit deallocation of heap objects 0 only in languages that have explicit deallocation implicit deallocation of elaborated objects 0 Two implementation mechanisms to catch dangling pointers Tombstones Locks and Keys Pointers And Recursive Types newmyptr ptr myptr myptr ptr2 deleteltmyptr Potentially reused Figure 715 Tombstones A valid pointer refers to a tombstone that in turn refers to an object A dangling reference refers to an quotexpiredquot tombstone Pointers And Recursive Types newmyptr myptr 135942 135942 ptr2 myptr mm 135942 135942 a delete myptr myptr 35942 0 quot Potentially reused ptr2 35942 Figure 716 Locks and Keys A valid pointer contains a key that matches the lock on an object in the heap A dangling reference is unlikely to match Pointers And Recursive Types 0 Problems with garbage collection many languages leave it up to the programmer to design without garbage creation this is VERY hard others arrange for automatic garbage collection reference counting does not work for circular structures works great for strings should also work to collect unneeded tombstones Pointers And Recursive Types Garbage collection with reference counts Stack Heap l 2 l larryquot 1 l quotmoequot l stooges nil Figure 717 Reference counts and circular lists The list shown here cannot be found Via any program variable but because it is circular every cell contains a nonzero count Pointers And Recursive Types Markandsweep commonplace in Lisp dialects complicated in languages with rich type structure but possible if language is strongly typed achieved successfully in Cedar Ada Java Modula3 ML complete solution impossible in languages that are not strongly typed conservative approximation possible in almost any language Xerox Portable Common Runtime approach Pointers And Recursive Types Garbage collection with pointer reversal Figurr39 Tlb Heap exploration via pointer reversal 39l39lu block lurrmiilv uurler wxnnr xation is lullicniml by the largo grey arrow Till39 previous ibilX39k is indilaiwl by the small prov arrow As 1110 garbage lollm39mr mom s from om bind in tho noxt ir rlmug rhu point or ii follows to rvt vr back w ill previous block When it rmurus m blmk it mi 111 illv pointer Eatl1 l39l l39l39l39h L ll pulml l must in39 murkwl lo distinguish it from other forward pointxrs in ill mum blurk Vv ismnw in this gurc that fill39 root umlo R is outside rlw limp so 1mm of iis pumw u c rrwrsotl 21 Lists A list is defined recursively as either the empty list or a pair consisting of an object which may be either a list or an atom and another shorter list Lists are ideally suited to programming in functional and logic languages o In Lisp in fact a program is a list and can extend itself at run time by constructing a list and executing it Lists can also be used in imperative programs 22 Files and InputOutput Inputoutput IO facilities allow a program to communicate with the outside world interactive IO and HQ with files Interactive O generally implies communication with human users or physical devices Files generally refer to offline storage implemented by the operating system Files may be further categorized into temporary persistent Programming Languages Tevfi k Kogsar Lecture XXIV April 2039 2006 Road map Object Oriented Programming Key Features Encapsulation Inheritance Data Abstraction Polymorphism Initialization amp Finalization Static vs Dynamic Method Binding Object Oriented Programming Object any object in real world or an instance of a class in a program Object oriented languages and programming techniques based on objects classes instead of procedures or functions Objects Capable of receiving messages processing data sending messages o via object specific functions called methods Each object can be viewed as an independent little machine with a distinct role or responsibility 3 Object Oriented Programming Goals Reduce conceptual load minimize amount of detail programmer must think at one time Provide fault containment prevent programmer from using a program component in appropriate ways Provide independence between program components modify internal implementation without changing external code or vice versa


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

"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."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.