Popular in Course
Popular in ComputerScienence
This 51 page Class Notes was uploaded by Vito Kilback on Wednesday September 23, 2015. The Class Notes belongs to CS360 at Drexel University taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/212459/cs360-drexel-university in ComputerScienence at Drexel University.
Reviews for ProgrammingLanguageConcepts
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: 09/23/15
Programming Languages Announcements Homework4 7 due June 439 ll 59pm May saw is a University Holiday NO CLASS g 7 Next Week s class is uptluncll Fur uther sectlun 7 Read cuurse nutes fur review sheet fur final Final Exam a s r WILL BECUMMULATIVE quotEmil Pytlxml 39 r Munde June w a U pm mis mom 7 TuesdayThursday June w a aura anpn kandell 32a Any questions Dr Arnie Souter What are the Agenda Fundamental Concepts in GOP 39 What is OOP 39 Encapsula on Fundamental Concepts ilnfomamn mde rThe notion of class and object 39 Inheritance 7 Code reusabtltty ilsravs hasra relationships Polymorphism Dynamtc method bmdmg 5232995 3 What do we know about inheritance based on C Create a set of classes provide a set ofoperations for those classes make commonality explicit using inheritance Multiple inheritance is possible Abstract classes are possible A child class inherits behavior and attributes from parents It enables reuse of existing classes we can specialize a derive class Anything else Inheritance Encapsulation improves code reusability 7 Abstract Data Types However it is generally the case that the code a programmer wants to reuse is close but not exactly what the programmer needs Inheritance prov39des a mechanism to extend or re ne units of encapsulation 7 By adding or overriding methods 7 By adding attributes Subtype Principle An object of a subtype may be used anywhere its supertype is legal Also called The principle of substitution 1 A child class inherits all the data elds in the parent class 2 A child class must reco nize all the behaviors associated wi e parent class either inheriting them directly or overriding them but preserving the type signature Th f e an instance ofa child class can be used in any situation where an instance of the parent class is expected Polymorphism purposes variable names function names class names and meanings can be de ned in a number of different ways Different Kinds of Polymorphism L39 L39IJ namc as mc parent class is declared as one type but in fact holds avalue ofa different type pure polymorphism when a polymorphic variable is used as an mnnm m quot 39 39 quot quotquot quot parametericpolymorphism a function cypcz or class de nidonis r actual parameter type to be selected by mc user when mc type or function is instantiated Can you give a concrete example for cach kind Ad hoc Polymorphism ad hoc polymorphism is usedto describe the situation Where a single function name or method name has several alternative implementations overloading ad hoc polymorphism class overloader public void exampleint x public void exampleint x double y public void examplestring x Inclusion Polymorphism inclusion polymorphism When a child class has a function vvitll the same name as the parent class overriding inclusion polymorphism 55 Parent ublic void exampleint x class Child extends Parent public void exampleint x Assignment Polymorphism assignment polymorphism or polymorphic variable is a variable that is declared as one type but in fact holds a value ofa different type assignment polymorphism Parent p new ChildO Pure Polymorphism pure polymorphism When a polymorphic variable is used as an ar ument the resulting function is said to exhibit pure polymorphism void inParent x Parent p new ChildO JHP Parametric Polymorphism parametric polymorphism a function type or class de nition is parameterized by one or more types Parametric polymorphism allows the actual parameter type to be selected by the user When the type or function is instantiated template ltclass Tgt T maxT le T right arg or if le lt right class StringBuffer retum right String append Object value Femm le retum appendvaluetostring How are they related C Inheritance Polymorphism Dynamic Binding Some good decisions OPublic private protected levels of visibility 0 Public visible evenwhere 0 Protected within class and subclass declarations 0 Private visible only in class where declared OFriend functions and classes 0 Careful attention to visibility and data abstraction OAllow inheritance without subtyping 0 Better control of subtyping than without private base classes Some problem areas 9 Casts Sometimes noop sometimes not esp multiple inher 9 Lack of garbage collection Memoryl management is error prone e Constructtms destructors are helplul ihougri QObjects allocated on stack r ef 39 cy interaction with exceptions BUT assignment works badly possible dangling ph39s Q Overloading T many code selection mechanisms 9 Multiple inheritance Efforis at efficiency lead to complicated behavior 5 m 3 Sample class onedimen points class Pt public Ptint XV Overloactd constructs PtPt pv int geDlt Mac read access to pmaiz data virtual void moveint dx Vnhnl Imctlon protected void setXint xv Protected write access private int x Private quot ber data Virtual functions OMem ber functions are either 0 Virtual if explicitly declared or inherited as virtual o Nonvirtual otherwise OVirtual members 0 Are accessed by indirection through ptr in object 0 May be rede ned in derived sub classes ONonvirtual functions 0 Are called in the usual way Just ard nay Mittans 0 Cannot rede ne in derived classes except overloading OPay overhead only if you use virtual functions Sample derived class Runtime representation class ColorPt public Pt Pith base class qlvs supevtwe Pom abject Point vtmie Code to move public VP 7 39 ColorPtint xvint cv I ColorPtPt pvint cv Overloaded corsauctm ColorPtCoIorPt up I int getCo or Nonwtmi runctim ColorPoint men ColorPoInt mole Code for move virtual void moveint dgtlt l quotMl Wm m Virtual vaid darlltenint tint f x i39otected c Code for darken void setCoIorint cv Panacea wrme Icctss n39vate fint 5039 quotm quotm39 1 quot Data at same offset Function pointers at same offset Calls to virtual functions OOne member function may call another class A public virtual int fint x virtual int gint y int Afint x gi int Aginty fj OHow does body of f call the right 9 o Ifg is rede ned in derived class B then inherited f must call Bzzg This pointer analogous to sef in Smalltalk OCode is compiled so that member function takes object itself as first argument Code intAfintxlquot 90 V compiled as int AfA unis int x thisgt90 O this pointer may be used in member function 0 Can be used to return pointer to object itself pass pointer to object itself to another function Nonvirtual functions OHow is code for nonvirtual function found OSame way as ordinary nonmember functions 0 Compiler generates function code and assigns address 0 Address of code is placed in symbol table 0 At call site address is taken from symbol table and placed in compiled code 0 But some special scoping rules for classes OOverloading 0 Remember overloading is resolved at compile time o This is different from runtime lookup of virtual function Virtual vs Overloaded Functions class parent public void printclasso printfquotp quot virtual void printvirtualO printf p quot class child public parent public virtual void printvirmalo print c quot mainO parent p child c parent q pprntclass pprintvirmal c printclasso cprintvirtual q w qgtprintclass qgtprintvirmal q ampc qgtprlntclass qgtprintvirl1lal 0utputppccpppc Multiple Inheritance Inherit independent functionality from independent classes Problem Name Clashes class A public void virtual f same name cl39ass B In 2 base publir classes void virtual f class C public A public B C p pgtf error Possible solutions to name clash OThree general approaches 0 Implicit resolution n uage resolves name conflicls wilh arbitrary rule 0 Explicit resolution Prog er must explicitly resolve name conflicts o Disallow name clashes Hograrns are not allowed in contain name clashes ONO solution is always best OC uses explicit resolution Repair to previous example ORewrite class C to call Af explicitly class C public A public B public void virtual f Af Call Af not Bf OReasonable solution 0 This eliminates ambiguity o Presenes dependence on A Changes to A f will change Cf vtable for Multiple Inheritance class A class C public A public B public public int x 39 virtual void f virtual void f class B public C pc new C int y B pb pc virtual void 90 A pa pc virtual void f Three pointers to same object I but different static types Object and classes V C ObJECl gt A object lt CasB vth gt B object QOffset B in vtbl is used in call to pbgtf since Cf may refer to A data that is above the point 9 Call to pcgtg can proceed through CasB vtbl Multiple Inheritance Diamond Window D aphle Windaw lS class Animal virtual void speakO cant ltlt quotAnimal speakl virtual void replyO cout ltlt quotAnimal speakl class Dog public Animal virtual void speakO cout ltlt Woof void replyO cout ltlt quotwoofwoofl quot class Bird public Animal virtual void speakO cout ltlt quottweedquot Animal a Dog b Animal d bspe d ampb a b d ampc a speako dgtspeak0 Blrd c Animal g ampb 015 interface or implementation inherited twice Cipef m g 8 OWhat if definitions conflict gpgko bgtrep1yo C Summary Java OObjects 0 Created by classes 0 Contain member data and pointer to class OClasses OInheritance 0 Public and private base classes multiple inheritance OSubtyping OEncapsulation 0 member can be declared public private protected 0 object initialization partly enforced History OJames Gosling and others at Sun 1990 95 OOak language for settop box 0 small networked device with television display graphics execution of simple programs communication between local program and remote site no expert programmer to deal with crash etc OInternet application 0 simple language for writing programs that can be transmitted over network Gates Saw Java as Real Threat Publicly Microsoft chief Bill Gates was nearly dismissive when he talked in 1996 about Sun Microsystems39 Java programming language But in internal company discussions he wrote to staff members that Java and the threat the cross platform technology posed to his company39s Windows operating systems quotscares the hell out of mequot Wired yews Report 8 09 a m 22 Oct 98 PDT Design Goals 0 Portability o Intemetwide distribution PC Unix Mac OReliability 0 Avoid program crashes and error messages OSafety o Programmer may be malicious OSimplicity and familiarity 0 Appeal to average programmer less complex than C OEfficiency 0 Important but secondaw General design decisions OAlmost everything is an object OAII objects on heap accessed through pointers ONo functions no multiple inheritance no go to no operator overloading no automatic coercions OBytecode interpreter on many platforms ORuntime type and bounds checks OGarbage collection OType safe OConcurrency support Java System OThe Java programming language OCompiler and runtime system 0 Programmer compiles code 0 Compiled code transmitted on network 0 Receiver executes on interpreter JVM 0 Safety checks made beforeduring execution OLibrary including graphics security etc 0 Large libraw made it easier for projects to adopt Java 0 Interoperability Provision for native methods Java Implementation OCompiler and Virtual Machine 0 Compiler produces bytecode 0 Virtual machine loads classes on demand veri es bytecode properties interprets bytecode OWhy this design 0 Bytecode interpretercompilers used before Pascal pcode39 Smalltalk compilers use bytecode o Minimize machinedependent part of implementation Do optimization on bybecode when possi le Keep bytecode interpreter simple 0 For Java this gives portability Transmit bytecode across network Java Virtual Machine Architecture Compile source code Verifier OBytecode may not come from standard compiler 0 Evil hacker may write dangerous bytecode OVerifier checks correctness of bytecode 0 Every instruction must have a valid operation code 0 Every branch instruction must branch to the start of some other instruction not middle of instruction 0 Every method must have a structurally correct signature 0 Every instruction obeys the Java type discipline Last condition is fairly complicated Bytecode interpreter JVM memory areas OStandard virtual machine interprets instructions 0 Perform runtime checks such as array bounds 0 Possible to compile bytecode class le to native code OJava programs can call native methods 0 Typically functions written in C OMultiple bytecodes for method lookup o invokevirtual when class of object known 0 invokeinterface when interface of object known 0 invokestatic static methods 0 invokespecial some special cases OJava program has one or more threads OEach thread has its own stack OAII threads share same heap JVM uses stack machine Example OJava JVM Activation Record class Consta ntPooI Class A extends Object in i i void fint val i i val1 local public Void Souter 5 variables int X 0 OBytecode SystemoutprintnquotME39HOD SOUTER Method void fint o objectrefb 1is opera39icl X Am39eo39 iload 1 int val stack iconst 1 7 iadd add val 1 putfield 4 ltField int igt Rpm In PUbIlC Int AmIeO return 1010 return 39 met pool 1 refers to const pool public void Souter o e Stack2 Locals2 Argsisize1 0 iconst70 1 istore71 2 getstatic 2 Field 5 Idc 3 String METHOD SOUTER invokevirtual 439 Method javaioPrintStreamprintln LjavalangStn39ngV d 0 10 aoa 7 11 invokevirtual 5 Method AmieI 14 istore71 15 return Constant Pool Table Compiled 39om quotConstantPool39avaquot class ConstantPool extends javalang0bject SourceFile quotConstantPooLjavaquot minor version major version 49 Constant pool const 1 Method 717 JayalangOoject ltmgt 0y const 2 Field 1819 lliavslanqlsyshem auttyayamPvintstveaw const 18 class 26 javalangSystem const 19 NameAndType 728 outLjavaioH39intSh39eam const 26 Asciz javalangSystem const 27 Asciz out const 28 Asciz LjavaioH intStream const 29 Asciz javaioH intstream const 30 Asciz println const 31 Asci LjavalangSh39ingv Constant Pool Table Compiled from Constanti ool Java class ConstantfPool extends Java lang Object SourceFile CmsbantfPool Java mlnorversl n major version 49 Constantpool const5 Method 5 23 CDnsbantPool Amie l Consmrmmoi ceF e soz consmnwoonaya ameAnd fype 13 14 Amie 1 JavalangObject Javalangsysuem soz out soz Ljava oPrintsoeamH z JavaioPrimstream soz soz soz prln n const 31 Asoz LJayaiangsmngv Type Safety of JVM ORuntime type checking o All casts are checked to make sure type safe 0 All array references are checked to make sure the array index is within the array bounds 0 References are tested to make sure they are not null before t ey are dereferenced OAdditional features 0 Automatic garbage collection 0 NO pointer arithmetic If program accesses memory the memory is allocated to the program and declared with correct type Field and method access OInstruction includes index into constant pool 0 Constant pool stores symbolic names 0 Store once instead of each instruction to save space OFirst execution 0 Use symbolic name to nd eld or method OSecond execution 0 Use modi ed quick instruction to simplify search invokevirtual ltmethodspecgt OUsed when superclass of object is known OSearch for method 0 search the method table for this class 0 ind method with the given name and signature OCan we use static type for efficiency 0 Each execution of an instruction will be to object from subclass of staticallyknown class 0 Constant offset into vtable like C but dynamic linking makes search useful first time 0 See next slide Bytecode rewriting invokevirtual Bytecode Constant pool Ai oo39 j OAfter search rewrite bytcode to use fixed offset into the vtable No search on second execution Constant Pool Exercise Java Summary OObjects 0 have elds and methods 0 alloc on heap access by pointer garbage collected OCIasses 0 Public Private Protected Package not exactly C 0 Can have static class members 0 Constructors and nalize methods OInheritance 0 Single inheritance 0 Final classes and methods Java Summary II OSubtyping o Determined from inheritance hierarchy 0 Class may Implement multiple Interfaces OVirtual machine 0 Load bytecode for classes at run time o Veri er checks bytecode o Interpreter also makes runtime checks type casts array bounds o Portability and security are main considerations Comparison with C OAlmost everything is object Simplicity Ef ciency 0 except for values from primitive types OType safe Safety Code complexity Efficiency 0 Arrays are bounds checked 0 No pointer arithmetic no unchecked type casts 0 Garbage collected OInterpreted Portability Safety Ef ciency 0 Compiled to byte code a generalized form of assembly language designed to interpret quickly 0 Byte codes contain type information Com parison cont d OObjects accessed by ptr simplicity Ef ciency 0 No problems with direct manipulation of objects OGarbage collection Safety Simplicity Ef ciency 0 Needed to support type safety OBuilt in concurrency support Portability 0 Used for concurrent garbage collection avoid waiting 0 Concurrency control Via synchronous methods 0 Part of network support download data while executing O Exceptions 0 As in C integral part oflanguage design Done CS 360 Programming Language Concepts Lecture 15 Logic Programming Reference Ch 121 125 ll Logic Programming Generally o What is logic programming 7 A logic program is a collection of declarations7 iiei things that are true 7 A logic program is executed by running queries against the program 7 Most logic programing languages incorporate uni cation and back tracking 0 What are some examples of logic programming languages 7 Mercury httpwwwcsmuozauresearchmercury 0 Why would anyone program in a logic programming language 7 Many complex problems can be expressed as a queries against a set of declarations 7 Uni cation and backtracking are applicable to a Wide range of prob ems 7 Example the pegs game httpshopcrackerbanecomonhneshoppnyProductasp7sku606154 ll Prolog 0 Overview of Prolog 7 Untyped 7 Uses topdown resolution7 or backwardchaining 7 Uses depth rst search o Syntax clauseseq A clause A opt clausetail A termlist A l term A opt args A l exprlz39st A l expr a l l l l opt exprlz39st A optlisttaz39l A LIT VAR CONST SIGN DIGIT UCHAR LCHAR clause clauseseq 6 term opt clausetail termlist 6 term termlist term CONST opt args exprlz39st e expr expr lz39st expr I optexprlz39st optlisttail L T 0 ONE T VAR exprlz39st e I expr e SIGN e DIGIT DIGIT UCHAR UCHAR LCHAR LCHAR UCHAR LCHAR OlwlS AlwlZ alul The above is actually the syntax of programs A query is just a term followed by a period 0 Loading the le examplep1 examplep1 o The Simpsons personbart personbart 7 yes person1isa quot0 no 0 personX o X a 7 yes 0 Fathers and mothers fathergrampahomer fatherhomerbart fatherhomer1isa fatherhomermaggie mother margebart mother marge1isa mother margemaggie fatherhomerX quot0 X bart quot0 yes motherXbart quot0 X marge 7 yes 0 Parents parentXY fatherXY parentXY motherXY parent Xbart quot0 X homer quot0 X marge s o Mates slightly broken matedXY fatherXZ motherYZ matedhomerX quot0 X marge quot0 X marge quot0 X marge quot0 yes matedbartX quot0 no matedmargeX no o Mates slightly broken7 but in a different way matedXY parentXZ parentYZ matedhomerX quot0 X homer quot0 yes 0 Mates very broken matedXY fatherXZ motherYZ matedXY matedYX matedhomerX quot0 X marge quot0 yes matedmargeX quot0 X homer quot0 yes matedbartX quot0 lthangsgt o Mates xed matedXY fatherXZ motherYZ matedXY motherXZ fatherYZ matedhomerX quot0 X marge quot0 yes matedmargeX quot0 X homer quot0 yes matedbartX oono o Ancestors broken ancestorXY parentXY ancestorXY ancestorXZ parentZY ancestorgrampabart ancestorgrampamarge quot0 Fatal Error local stack overfloww o Ancestors xed ancestorXY parentXY ancestorXY parentZY ancestorXZ ancestorgrampabart quot0 true 7 yes ancestorgrampamarge quot0 no 0 Lists memberX X I memberX I YSJ memberXYS memberb abcd 7 yes membere abcd quot0 no append YSYS appendX I XS YSX I ZS appendXSYSZS append cd XS quot0 XS cd 7 yes appendab cd XS quot0 XS abcd quot0 YS abcd quot0 XS a quot0 YS bcd quot0 XS ab quot0 YS cd 00 XS abc quot0 Y5 d quot0 XS abcd quot0 YS J 7 quot0 no INSERT 1 insertXYSX YSJ INSERT 2 insertXY I YSY I ZSJ insertXYSZS insertabcd XS quot0 XS abcd quot0 XS bacd 7 quot0 XS bcad quot0 XS bcda insertXYSabcd quot0 X a quot0 YS bcd quot0 YS acd quot0 c quot0 YS abd Xd oYS abc oono o Arithmetic Predicates lt7 lt7 gt7 gt 1lt2 yes Xlt2 quot0 uncaught exception errorinstantiationerrorlt2 o Permutations PERMUTE l permute J 1 PERMUTE 2 permute X I XS YS permuteXSZS insert X ZS YS o Derivation tree for permute ab ba on following page o Sorting inefficient sorted sorted L sortedXAXB I XSJ XA lt XB sortedXB I XSJ sort XSYS permuteXSYS sortedYS sort73159XS 00 XS 13579 7 yes 0 Quick Sort qsort J qsortX I XS YS partitionXXSVSlWS1 qsort VSlVSZ qsort WS1WS2 appendVS2 X I W52 YS partition partitionWX I XSX I YSZS K lt w partitionwXSYSZS partitionWX I XSYSX I ZSJ X gt w partitionwXSYSZS 0 Merge Sort msort J msort X X msortXAXB xsYs splitXAXB xsvs1ws1 msort VSlVSZ msort WS1WS2 merge VSZWS2YS split splitXX SplitxAxB I XSXA I YSXB I ZSJ splitXSYSZS merge YSYS merge XS 1 XS mergeX I XSY I YSX I ZSJ K lt Y mergeXSY I YSZS mergeX I XSY I YSY I ZSJ X gt Y mergeX I XSYSZS 0 Cut assocXXY I Y assocX I YSZ assocXYSZ lookupXY assoc X breakstatement doub1etype int type returnstatement Y lookup ident if ier lookupdoub1e X lookupreturnX quot0 X statement 7 yes lookupfi1enameX quot0 X identifier 7 yes lookupXstatement quot0 X break 7 yes What happened to return Welcome To C5360 Programming Language Concest Slimb r w p 1 DRIP mll it Dr Amie SouTer 472995 AnnouncemenTs 39 AssignmenT 1 39 Mailing lisT 39 Reading ChapTer 4 12 and 1113 Exercise 39 Given The following program wriTe own a descripTion of The synTax for The program 39 QuesTions 1 Is This a difficulT Task 2 WhaT would make iT 39 r 3 How are languages Typically specified 472995 Class This Week 39 How do we specify Tokens 39 Recognizing a Token 39 How do we specify grammars 39 Using grammars 39 FuncTional languages 472017 4 SpecificaTion of Programming Languages PLs require precise definiTions ie no ambiguity Language farm SynTaX Language meanHg SemanTics Consequenle PLs are specified using formal noTaTion Formal synTaX Formal semanTics 4V72005 Lexical STrucTure of a PL WhaT do we mean by lexical sTrucTure The words or Tokens of The program WhaT caTegories of Tokens exisT How do we idenTify Tokens 472005 Principle of LongesT SubsTring How many Tokens should The following be broken inTo WhaT are The possibiliTies doif x12 456y 4V72005 Classic ForTran Example DO 99 I 110 same as D0991 11o VZY SUS DO 991 110 same as forI 1 I lt 10 I How many Tokens 472005 Regular Expressions A regular expression RE is a descrip rion of a pa r rern of characTers Formally defined as A single characfer The empty sfring 2 The concatenafion of two regular expressions NaramnREt REZ 2 RE followed by REZ The alfernafion of two regular expressions Nufafiun39RE REZ The closure of a regular expression 39 NufafiunrREquot 39 quot is known as the Keene star represents the concatenation of 0 or more strings 472005 Examples Wha r Toolslanguages exist The use RE grep emacs perl awk sed Java PHP 39 Example grep e The39 paper grep e in rfloa r39 fooc aI bc Wha r sTring does This re ma rch ababaac aac c ab Which do no r hnn iava ttn mm Java Example impor r javau ri lregex Pa r rern pa i39139ern Ma rcher ma i39cher rry S rring REGEX brreadLine S rring INPUT brreadLine ca rch IOExcep rion ioe pa ern Pa erncompileRE6EX ma i39cher pa139139ernma139cherINPUT Wri i39ing regular expressions WriTe a regular expression for each of The following se rs of binary s rrings all binary sTrings all binary sTrings excepT empTy sTring begins wi rh 1 ends wi rh 1 ends wi rh OO 472005 12 Recognizing Tokens Scanner Example Tools lexflexjlex QuesTions Hand coded scanners FSM 1 WhaT Tokens are parT of The language 2 Given The inpuT 42 345 WhaT is The oquuT 472005 13 472005 SynTax Analysis 39 SynTax ConTexT Free Grammars WebsTer39s definiTion 1 a 39 The way in NoTaTion which 39I7L395397 39C eemem s as words are expression idenfifier I number I expression pur rage ier39 7 0 farm phrases expression The Synfax of a programming I expression operafor expression language operaforgt I I it I Describes iTs form Terminal symbols 39 15 Organizaflon of Tokens eemenfs Formal noTaTion 39 Nonterminalxym 015 39 ProducTions ie grammar rule 39 ConTexT Free Grammars CF65 472005 15 472005 16 Context Fr39ee Grammars gtlt2y What tokens are recognized by the following input stream idx num2 idY 472005 17 CFG In general a context ee grammar CF G has a finite set of terminals tokens a nite set of nonterminals from Which one is the start symbol and a nite set of productiom of the form A X1 X2 Xn Where A is a nonterminal and each Xi is either a terminal or nonterminal symbol 472005 1E Derivations A derivation shows how to generate a syntactically valid string Example TF1 gtltgtTFF1gtlt 472005 19 E3 ET Derivation Example Derivation of x 2 y gt idx num2 idy 472005 20 Why is a grammar conTexT free EgtET IET T 4V72005 2 WhaT are grammars used for 1 Specifying synTax 2 Recognizing valid sTrings Recursive decenT parser 472005 22 Changing Gears 4V72005 23 Examples in Three languages Euclid39s gcd algoriThm CompuTe The greaTesT common divisor of Two inTegers inpuT by The user and prinT The resulT For example The gcd of 15 and 10 is 5 472005 C Figure 17 p 26 1nclude ltStd10hgt 1m gcd1nt u 1m v functlonal Verslon 1f v 0 return u else return gcd v ma1n IO drlver int u a v tall recurslon V X Y prlntfquotInput two 1ntegersnquot scanfquotddquotampxampy7 prlntfquotThe gcd of ad and ad 15 dnquot xygcdxy return 0 472005 25 Java Figure 19 p 27 mport java1o class lntwitthd publlc IntW1tthd 1m val value val publlc lnt getvalue publlc 1m gcd 1m v 1m 2 value return value 1mperat1ve verslon z yzt return 2 prlvate int value 472005 26 Java con nued class chProg drlver public stat1c VOld maln Strlng args Systemoutprlntlnquot1nput two 1ntegersquot BufferedReader 1n new BufferedReader new lnputstreamReadersystemin try must handle IO exceptlons Inthtthd x a create an Object V new InthtthdIntegerparselnt1nreadL1ne int y Integerparselnt1nreadL1ne systemoutpr1ntquotTne gcd of quot xgetvalue lquot and quot yquot1squot Systemoutprlntlnxgcdy catch Exceptlon e systemoutpr1ntlne Systemex1tl 472005 27 define gcd u V if v O u Scheme Figure 15 p 17 gcd v modulo u v 472005 23 Scheme Figure 117 p 486 define euclid sequentiall display quotenter two integersquot newline goes to next line on screen let u read v read display quotthe gcd of quot display u display quot and quot display quot is quot display V display gcd u v 472005 29 Paradigm use is rarely quotpurequot The C program defined the gcd function in a purely functional style even though C is mainly imperative The Java program used some imperative code to compute the gcd and was not completely object oriented integers aren39t objects The Scheme code used sequencing to do IO an imperative feature 472005 3 0 Examples of languages that are pure mostly Imperative old FORTRAN Functional Haskell Ob 39ectoriented Smalltalk 4V72005 3 Scheme started as an experiment in It emerged from MIT in the mid 197039s The language was designed to have very Introduction to Scheme programming language deSIgn few regular constructs which compose well to support a variet of programming styles including functiona object oriented and imperative 472005 3 2 Evalua ng Sche me Expressions quot 3 4 5 fuc 6 even 6 cond Tesi condition Result to return n 10 m gt n 10 quot n m lt n 10 0 define pi 3 14 define square x quot X X 472005 3 3 Scheme Cor39e Vocabulary ltvargt x I areaofdisk I perime rer39 I ltcongt True I false 39a I 39doll I 39sum I 1I1 I 35 I 122 I ltprmgt 472005 3 4 Scheme Cor39e Grammar ltdefgt define ltvargt ltvargt ltvargtltegtltpgt I define ltvargt ltegtltpgt I define sTruc r ltvarOgt ltvar 1gt ltvar ngt ltegtltpgt ltvargt ltcongt ltprmgt ltegtltpgt ltegtltpgt ltvargt ltegtltpgt ltegtltpgt I cond ltexpgt ltegtltpgt ltegtltpgt ltegtltpgt I cond ltexpgt ltegtltpgt ese ltegtltpgt I and ltegtltpgt ltegtltpgt or ltegtltpgt ltegtltpgt 472005 35 Scheme Expression Exercise Handou r 472005 3 6 dcons 39d cdr39 cdr 39a b c car cdr39 Iis r 17 5 bcons guo re cdr39 quo re b c I 39a b C ccdr c d 8 f econs 39212Is l 39313 394 14 472005 a 12x21387 b 23 49511 43 c 1 12 1112 d1gtlt2gtlt3gtlt4gtlt5gtlt6gtlt7 472005 3 E Lists in Scheme Lists are essentially the only data structure in Scheme However lists are very versatile and can be used to model any other data structure Lists are constructed recursively using the empty list 39 and the cons binary operator 1 2 3 cons 1 cons 2 cons 3 0 The rst element ofa list its head is returned by the car operator car 39 1 2 3 1 The tail of a list is returned by the cdr operator Cdr 391 2 3 2 3 4mm 39 Liss CONS Takes Two arguments and re rurns a pair a isT cons 391 392 3 4 9 1 2 3 4 cons 391 2 3 394 5 6 9 1 2 3 4 5 6 cons 391 392 9 1 2 472005 40 LisT FuncTions 39 CCII39I reTurns The firsT member of a isT or doTTed pair car 39123 245 564 898 9 123 car 39firsT second Third 9firsT car 39This is no more difficulT 9 This 4V72005 4 1 More LisT FuncTions cdr reTurns The isT wiThouT iTs firsT iTem or The second member of a doTTed pair cdr 397 6 5 9 6 5 cdr 39iT rains every day 9 rains every GY cdr cdr 39a b c d e f 9 c d e 1 car cdr 39a b c d e f 9 b 472005 42 Even More LisT FuncTions null reTurns T if The objecT is The empTy isT 0 IT reTurns The null isT which is The same as f if The objecT is anyThing ese lengTh reTurns The lengTh of a isT lengTh 3913 5 911 5 4V72005 43 More LisT FuncTions isT reTurns a isT consTrucTed from iTs argumenTs isT 39a 9 a lisT 39a 39b 39c 39d 39e39f 9a bcdef isT 39a b c 9 a b c isT 39a b c 39d e f 39g h i 9 a b Cd e f9 h i 472005 44 List Functions 39 reverse returns the list reversed reverse 391 3 5 911119 5 31 append returns the concatenation of two lists append 3913 5 399 11 1 3 5 911 472005 45 Functional Programming Examples 0 Write a recursive function to compute the length of an arbitrary list 0 Write a function to compute the max of a list of integers 0 Write a function that reverses the contents of a list 4mm K Landau PragmmmgLanguagzs List Examples car down define append L M if null L M cons car L append cdr L M Predicate function define reverse L cons up if null L 390 append reverse cdr L list car L 39 define alter list L if null L 390 cons car L car L Cdr L alter list Anznns What does mystery compute define mystery Ist cond null Ist O pai r car Ist mystery car Ist mystery cdr st else car Ist mystery cdr st 472005 4E Some Func rional Language Concep rs Referen rial Transparency Me l39acircular In rerpre rer Highorder Func rions Garbage Collection Delayed Evalua rion Lambda Calculus 472005 49 Welcome 1390 C5360 Programming Language oncepfs n ll l 9 l m gt i 1 man C 3quot VishnuJ 39 gt H ll 39 Urirel Pyrlmu H 1 Dr Amie Soufer sszzm Announcemen rs 39 Homework 1 posfed nexf week 39 Lecfure notes on course web page 39 Reading chapfers 1 3 39 Mailing list did everyone gel mail 331217l75 Some Ex rra Bi rs nllgawwwoneillyeomnewsgnagniesggnog lang goslengar p on anguageisalangugg y assoclahon with computers Often the form Is use synonymously with n nnun lan a e but n genenal acompufor lan age need not be rogramming language For oxgam pie man angugges like HTML are general yn nel to be programming languages ul they are computer anguages Wikipodia sszzm Wha r is a programming language 39 Break info groups of 5 39 Define programming language 39 List as many programming languages as you can 331217l75 What is a programming language Louden39s Defintion A notational system for describin com utation in machinereadable and humanrea able or Bruce MacLellan39s definition A language that is intended for the expression of computer programs an that is capable of expressing any computer program Ravi Sethi39s definition Notations used for specifying organizing and reasoning about computations 3312005 5 Why Are There So Many Programming Languages Evolution We have learned better ways of doing Things over time Socioeconomic factors Proprietary interests commercial advantage Special purposes 39 Personal preference 3312005 6 What Makes a Language Successful Easy to learn Basic Pascal Easy to express Things Powerful Easy to use once known C Lisp Easy to implement Small machines limited resources Basic Fort 3312005 7 Efficient compilers Backing of a powerful sponsor Wide dissemination at a minimal cost Inertia What Makes a Language Successful Generate small fast code Fortran Ada Visual Basic Pascal Java Fortran Cobol 3312005 E TIOBE Programming Community Index for March 2005 httpwwwtiobecomtiobeindexte ksthtm 3312005 9 Why Study Programming Languages Help you choose a language Systems programming a C Modula 3 Scientific computations a Fortran Ada Embedded systems a C Ada Modula Z Symbolic computing a Lisp Scheme ML Make it easier to learn new languages Some languages are similar Some concepts are even more similar iteration recursion abstraction 3312005 10 Why Study Programming Languages Make better use of the languages you know Improve ability to develop effective algorithms Understand obscure features Understand implementation costs Simulate useful features in languages that do not support t em Prepare for further study in language design and implementation compilers Help understand other system software assemblers linkers debuggers 3312005 1 1 Course Description Introduces the design and implementation of modern programming languages formal theory underlying lan uage implementation concerns in naming bin ing storage allocation and typing semantics of expressions and operators control flow and subprograms procedural and data abstraction functional logic and object oriented lan uages Students wi l construct an interpreter or a non trivial language 3312005 12 Course Information Instructor Dr Amie Souter E rnail Office Office Hours soutercsdregtlteledu 106 Crossings 500 600 Monday and 230 330 Thursday or by appoint Teaching assistant Yogi Mehta ypm23dregtlteedLl Class web page httpwwwcsdregtlteledLlsothercs360spO5 3312005 13 Comfortable with an have seen at least two Course Prerequisites as 171 Prog I 172 Prog II and 260 Data structures obljectoriented language ideally siould anguages Ideal s 231 Systems Architecture I underslanding of lle C underlying of basc compuler arc leclure assembly language macl ne organization as 270 Foundations of Computer Sc ence slould be comforlable will lle mallemal cal lools used lo descr be and analyze programming languages lo c recursion malerial on finile slalemaclnes and grammars use ul bul will be covered n llis c ass 3312005 14 Course ObJectlves Undersland low lo com re and evaluale differenl programming languages and know wla faclors need lo be taken inlo accounl Be comforlable will lle major programming paradigms and be able lo use al leasl one language from eacl paradigm N 5quot Un e land some of lle issues involved n implemenlalion of pro ramming languages llis slould lelpllem program mor ef c enll Be familiar will elemenlaryconcepls of formal language lleory sucl as contextfree grammar Be le lo formallyspecifylne syntax of programming languages Be familiar will lne essenlials of lexical analysis and elemenlary sing procedures Understand dynamic and slal c scope dynamic and slalic bind ng and lne issues lley give rise lo Understand lle advanlages and disadvanlages of strongweak lype checkin Understand lle differenl melnods of parameler pass ng and low lney ngnl be implemenled and unders and some oflle issues invo ve n calling subroulines 10Understand implementation issues associated with 00 hroaramminn n o 99quot 9 939 3312005 15 Assignments and Exams Programming assignments 35 Interpreter project Homework assignments 20 4 written assignments or short programming assignments 2 Midterm exams 20 Closed book closed notes Final exam 20 Closed book closed notes relien Comp slve Attendance and Class Participation 5 Attendance is expected Active participation is also excepted 3312005 16 La139e Submission Policy 39 YOU ARE GRANTED 2 LATE DAYS Use Them as you see fif Send email To TA To lef him know After 2 days are used up assignmenfs will no be accepted Read course syllabus for detailsll 331217175 Required Textbook 39 Programming Languages Principles and Pracfice 2quotd edition Kennefh Louden 2003 FHUWAMMWE l HES nnnlli mine 33120 Why do we have programming languages Wha r is a language for Way of thinking 7 Way uf expressing algurllhms 7 languages frum lne user s pulrll uf View Abstraction of virtual machine 7 Wu uf Specl indg Whalyuu Wanl lne hardware in dB Wll uulgemng a nl lulheblls 7 languages min lne lmplemenlur s pulrll uf View This course tries to balance coverage oftnese two angles We will talkabout language features for their own sake and about how they can e implemented 331217175 Wha r differenT caTegories of languages exis r 39 hHgenwikigediaorgwikiCafegori al lisf of grogramming languages 33120 2n What programming paradigms exist Imperative procedural Algol C FORTRAN Pascal 39 Object Oriented Simula 67 Smalltalk CH java Ada 95 Eiffel 39 Functional Lisp Scheme ML Haskell 39 Logic declarative rule based Prolog 3312005 21 Historic Perspective 39 When did the earliest highlevel languages appear Continuous evolution since the 19505 Fortran Cobol When the Department of Defense did a survey as part of its efforts to develop Ada in the 19705 how many languages did it find in use Over 500 languages were being used in various defense projects 3312005 22 Faun i Foml u u Cabal Algal 58 was mo was Attributes of a Good Language 39 Clarity simplicity and unity All are desirable but in conjunction Using a very simple language in an application for whic it is not well suited may produce lack of clarity 39 Orthogonality Every combination of features is meaningful Example data types and return values are not orthogonal in C but are in 39 Naturalness program structure reflects the logical structure of algorithm 3312005 24 Attributes of a Good Language Support for abstraction p ogram data reflects problem being solved Reliability of programs Does the program behave the same way every time it is run with the same input data Cost of use Cost of program creation Cost of program translation Cost of program execut39 ion Cost of program maintenance 3312005 25 What does a programming language need to be useful 3312005 2 5 Compilation and Interpretation A compiler is a program that translates high level source programs into target program Mien ngei png hipvi 0viphi 39 An interpreter is a program that executes another program o w hipii Mixing Compilation and Interpretation 39 Fuzzy difference A angua e is interpreted when the initial translation is s e A language is compiled when the translation process is compItafed hmm Wm V uul machine W gt In gt Oulpul 3312005 3312005 27 Summit 28 Grou ps Compiled Interpreted Where do languages fall on the following spectrum Class discussion Half The class will represenT The advanTages of inTerpreTaTion The oThers The advanTages of compilafion Which is beTTer 3312555 29 Com pi laTion and InTerpreTaTion InTerpreTaTion GreaTer flexibiliTy beTTer diagnosTics Allow program feaTures daTa Types or sizes To depend on The inpuT Lisp Prolog program can wriTe new pieces of iTself and execuTe Them on The fly Java compilaTion Then inTerpreTaTion JIT CompilaTion BeTTer performance any decisions are made only once aT compile Time noT aT every run Time ForTran C 3312555 3 o Phases of CompilaTion Chunciersllum Scanner lieml analysn Tokcnslream Palserlsyn39ax alulysls Pmseuee Semamic Analysis 1nd memedinewde enemaquot Abslmclsymnxlmeor l g gtth minmzdlzle mm Manhinzindzpendzm cod lm ovemzm uplmunl Momma Imcrmediale lonn Target Codi genelauon Assemny ox machine language 4 or uh L39r ms language Machine speci c code Implovcmenr ropnonal Modi ed mgel language Symbol ublz 31 l Example Example program read A read B sum A B write sum write sum 2 3312555 3 2 Lexical Analysis Tokens scanner ex i39r ac rs Token smalles r meaningful uni rs 10 ietter letter digit w except quotreadquot and quotwritequot end of file Syn i39ax Analysis Grammar in EBNF ltpgmgt gt ltstatement 115tgt sss lt5tmt 115tgt 7gt lt5tmt 115cgt lt5tmtgt i E lt5tmtgt 7gt 1d lttermgt i ltexprgt ltadd opgt lttermgt ltexprgt i read lt1dgt i wrlte ltexprgt lttermgt sgt ltfactorgt i lttermgt ltmult opgt ltfactorgt ltfactorgt sgt ltexprgt i 1d i llteral ltadd opgt egt i e ltmult Opgt egt i 3312005 33 3312005 34 Seman i39ic Analysus code Genericrmquot 39 Discovers meaning in a program 39 InTermediaTe code 39 Siaiic semantic analysis ai compile Time read Identifiers declared before use 10010 A Subroutine calls provide correct number and type of read arguments P0P E read A 2 2 read B Dynamic semanhcs cannoi be checked at compile add sum AB Time so gen raie code To check at run Time pop sum write sum Pointers dereferenced only when refer to a valid object push sun n Array subscript expressions lie within bounds ounce Wme Sum Simplifies The parse free a s niax free Push Sum 39 Mainiains symbol fable aHaclies aHribLiies 2 2 wrlte 3312005 35 3312005 36 Code Genera l39ion Targe l39 code data movl E 2 A long u addl oiloi2 E long u movl dlysum sum long u vl sumydl ext movl d1 dEI naln 35 read 35 w e l d ydl mov sumydl movl dlyA movl 2oi 35 read dlvsl oiloi2 ovl d ydl movl dlydEI movl dlyE 35 wrlte movl Aoil 3312005 Backend Targe r code generaTion Generate assembly or machine language Traverses The synfax free To generafe elemenfary operafions loads and sfores arifhmefic operations Tests and branches Code improvemenT op rional Ak a op mizafion Transform program info a new version wifh 39 if Y same funchona buf more efficienf fasfer uses less memor 3312005 3 E Error classuflca hon Lexical charac rer level error such as illegal charac rer hard To disTinguish from s nTaX 39 Syn rax error in s rruc rure eg missing semicolon or keyword S ra ric semanTic non synTaX error prior To execu rion eg undefined vars Type errors Dynamic semanTic non synTaX error during execu rion eg division b O Logic programmer error program no r a r faul r 3312005 0 Sample Errors Java publlc lnt myexample lnt V lexlcal lnl z Value Syntax mlsslng y v statlc semantlc y undeflned whlle y gt O dynamlc semantlc 7 dlvlslon by zero lnt t zy return y loglc 7 should return t 3312005 40 Examples in Three languages Euclid39s gcd algor39iThm CompuTe The greaTesT common divisor of Two inTegers inpuT by The user and prinT The resuIT For example The gcd of 15 and 10 is 5 3312005 3 C Figure 17 p 26 lnclude ltStd10hgt lnt gcdlnt u 1f v 0 else return gcd v u a v lnt v functlonal verslon V return u tall recurslon V ma1n IO drlver V int x y prlntfquotlnput two 1ntegersnquot scanfquotddquotampxampy prlntf The gcd of d and d 1s dnquot xygcdxy return 0 3312005 42 Java Figure 19 p 27 lmport javalo C1355 Inthtthd publlc Inthtthd lnt val publlc 1m getvalue l publlc 1m gcd 1m v value val return value l l 1m 2 value 1mperat1ve verslon V int y v whlle y lnt t s rz yz t return 2 private lnt value 3312005 43 class chProg drlver V public statlc Java conTinued VOld maln strlng args systemoutprlntlnquotlnput two lntegersquot BufferedReader 1n new BufferedReader lnputstreamReadersystem in try must handle IO exceptlons V Inthtthd new x create an Object V new lnthtthdlntegerparselnt lnreadLlne int y lntegerparselntlnreadLlne systemoutprlntquotThe gcd of quot xgetvalue quot and quot y quot ls quot systemoutprlntlnxgcdy catch Exceptlon e systemoutprlntlne Systemexltl 3312005 44 Scheme Figure 15 p 17 define gcd u v if v O u gcd V modulo u v 3312005 45 Scheme Figure 117 p 486 define euclid sequentiall display quotenter two integersquot newline goes to next line on screen let u read V read display quotthe gcd of quot display u display quot and quot display quot is quot display gcd u v display V newline 3312005 46 Paradigm use is rarely quotpurequot The C program defined The gcd funcTion in a purely funcTional sTyle even Though C is mainly imperaTive The Java program used some imperaTive code To compuTe The gcd and was noT compleTer objecT orienTed inTegers aren39T objecTs The Scheme code used sequencing To do IO an imperaTive feaTure 3312005 Examples of languages ThaT are pure mosle ImperaTive old FORTRAN FuncTional Haskell Ob 39ecTorienTed SmallTalk 3312005 4E Summary Who is a programming language Why study programming languages 39 What kinds of programming languages exis r How is a programming language implemen red Different programming paradigms 3312005 49
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'