NYU CSCI-GA 2110 - Design, Specification, and Implementation (23 pages)

Previewing pages 1, 2, 22, 23 of 23 page document View the full content.
View Full Document

Design, Specification, and Implementation



Previewing pages 1, 2, 22, 23 of actual document.

View the full content.
View Full Document
View Full Document

Design, Specification, and Implementation

55 views


Pages:
23
School:
New York University
Course:
Csci-Ga 2110 - Programming Languages
Unformatted text preview:

Programming Languages Design Specification and Implementation G22 2210 001 Rob Strom December 7 2006 Programming Languages Core Exam Syntactic issues regular expressions context free grammars CFG BNF Imperative languages program organization control structures exceptions Types in imperative languages strong typing type equivalence unions and discriminated types in C and Ada Block structure visibility and scoping issues parameter passing Systems programming and weak typing exposing machine characteristics type coercion pointers arrays in C Run time organization of block structured languages static scoping activation records dynamic and static chains displays Programming in the large abstract data types modules packages and namespaces in Ada Java and C Functional programming list structures higher order functions lambda expressions garbage collection metainterpreters in Lisp and Scheme Type inference and ML Object Oriented programming classes inheritance polymorphism dynamic dispatching Constructors destructors and multiple inheritance in C interfaces in Java Generic programming parametrized units and classes in C Ada and Java Concurrent programming threads and tasks communication race conditions and deadlocks protected methods and types in Ada and Java Readings optional Regular expressions http www regular expressions info Prolog Giannesini et al Prolog Addison Wesley 1986 SQL C J Date An Introduction to Database Systems Addison Wesley 2000 chapters 3 4 Hermes Strom et al Hermes A Language for Distributed Computing Prentice Hall 1991 Java RMI http java sun com docs books tutorial rmi overview html Guava s Component Model M1 M2 V1 O1 O3 V11 O2 X O4 O5 X V2 O6 O9 O8 O10 O7 Java and Guava types Referenced Objects classes methods access by reference synchronized or not Values built in primitive types no classes methods no references sharing copy by value Referenced always synchronized Referenced Monitors Objects never synchronized restricted references Values may be user definable classes methods move copy by value Guava changes summary Instance toString clone hashCode equals getClass synchronized volatile Local Annotations Mobile Reference copy Annotations read update local global lent kept in Region new Value Object Monitor wait finalize notify notifyAll Monitors Values Objects M1 X BucketList X 0 X 1 A 3 D 9 B 3 C 8 E M2 An object has at most one owning monitor value M3 Y BucketList Y 0 A 3 Y 1 Y 1 D 9 E G 1 G G 1 1 Z B 3 C 8 B 3 GG 1C 1 8 Region Analysis lent kept M1 X M2 foo X M2 Y this N P1 Z bar P1 Y Z bar Y P1 Z this A P1 this A P2 P1 op P2 N this class M2type extends Monitor void foo lent Bucket P1 class Ztype extends Object void bar lent Bucket P1 kept Bucket P2 lent An unknown region Default for parameters of non objects kept Same region as this Default for parameters of objects Region Analysis new in R M1 A B C D M2 E E E class M2type extends Monitor new Bucket m Bucket P1 in R1 E M2 m Bucket P2 in R1 A B C D Bucket P3 in R2 Bucket P4 in R2 P1 N P2 P4 N P3 P2 N P4 return new Bucket 3 null new No region in R Same region as other parameters labeled in R Other paradigms String processing lexx yacc SableCC regular expressions Logic programming Prolog Transactional Programming CLU SQL XQuery Distributed Hermes Java and other RMI tools Regular expressions Distinguish between the syntax of the pattern and the semantics Different engines will have slightly different syntax A regular expression is a pattern that you apply to a text in order to determine a match and sometimes to parse the components of the match e g for search replacement A regular language is one that can be parsed with a regular expression Patterns Exact character a Any character Zero or more repetitions of a pattern Patterns can be grouped with parentheses Concatenation pat1 pat2 Alternation pat1 pat2 Zero or 1 x same as x One or more x same as x x Any character not in the set a z a z Other special matches that match positions rather than characters e g start of line end of line b word Modern extensions x y between x and y occurrences Examples txt matches a filename ending with txt b A Z0 9 A Z0 9 A Z 2 4 b matches an email address like robstrom us ibm com A Za z A Za z0 9 matches a tag like Foo More examples applied to the string Here is a test test hello test now what Matches test hello test That s because and are greedy Suppose you wanted to match only test You should do one of the following Select lazy matching Replace dot with something more restrictive e g Logic Programming Prolog from Gelernter et al Facts relationships that are true female annette female marilyn female audrey parents annette fred marilyn parents audrey fred marilyn parents marilyn john liz sister X Y female X female Y parents X M F parents Y M F two females having the same parents are sisters Rules inferences that can be made Queries sister annette audrey are annette and audrey sisters sister audrey does audrey have a sister sister X audrey for what X are X and audrey sisters i e who are audrey s sisters Examples Data types integers strings lists Append example append L L an empty list appended by L yields L append X L1 L2 X L3 append L1 L2 L3 if given that L3 L1 appended by L2 then X followed by L3 is X followed by L1 appended by L2 append a b c d e f X asks what is a b c appended by d e f answer is a b c d e f append a b c X a b c d e f asks what should I append a b c by to get a b c d e f Notice the query is just as easy to express How does it work Our old friend unification Remember that means find a substitution of variables that makes two expressions the same A goal is satisfied if A fact unifies with the goal A rule s head unifies with the goal and then each clause in that rule s body is satisfied these clauses then recursively become goals If there are multiple possible unifications then they must all be tried backtracking on failure To speed up search and to inhibit multiple paths Prolog introduces a cut operator The trouble with cut is that it spoils the abstraction of Prolog the user has to know the order in which goals are evaluated Transactional Programming with SQL Actually transactions and SQL are logically independent Transactions means executing a set of operations reads and or updates atomically Remember that Atomically means that if T1 includes a b c and T2 includes d e f the only possible results are a b c d e f and d e f a b c and no interleavings Whereas SQL means using a relational model of data whether


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Design, Specification, and Implementation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Design, Specification, and Implementation and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?