OPL 01.1COSC 382 Organization of Programming Languages SyllabusMessiah College Fall Term 2006Catalog DescriptionStudy of features of programming languages and of the methods used to specify and translate them. Topics include LISP, virtual machines, syntax and semantics, binding times, scoping rules,implementation choices, procedure calling, and parameter passing. COSC 282 Data Structures andAlgorithms is a prerequisite for this course.InstructorDr. Gene B. Chase. Office, Frey 123. Phones: office 766-2511, ext. 2770; home 766-7904. Electronicmail: [email protected] Home page: www.GeneBChase.com. My office hours are posted on myoffice door, where you may sign for an automatic appointment.ObjectiveI have two objectives for this course.1. To present computer science as a mathematically rigorous discipline.2. To equip your to understand the spectrum of programming languages so that you can choose the rightlanguage for the job or create the right language for the job if no appropriate one exists.Outcomes1. You will program in C++, Lisp, and Prolog.2. You will compare the features of these and other languages (Java, Perl, APL, XSLT, and ML forexample) in three closed-book exams.3. You will prove small program segments to be correct.4. You will write a paper that uses multiple sources and specific program code to defend or to critiqueyour choice of a programming language for a specific task.Materials Needed1. This notebook.2. Robert W. Sebesta. Concepts of Programming Languages, seventh edition. Pearson/Addison-Wesley,2006.3. Possibly other source books depending on the language you choose to study, if there are no good on-line tutorials for your topic area.Americans with Disabilities ActMessiah College welcomes students with disabilities. If you have a documented disability and wish todiscuss academic accommodations for this specific course, please contact me as soon as possible. Alldisability accommodations must be pre-approved through Dr. Keith Drahn, in the Office of DisabilityServices, telephone x7258.Academic IntegrityPlagiarism—representing another's work as your own, copying another person’s work without credit, orallowing your work to be copied—will surely result in a lower grade in this course, and may result infailing the course depending on its severity. You must document any sources that you use, whether fromOPL 01.2the internet, another person, or printed materials. This includes especially the work of other students whoare currently taking this course or who have taken this course before. Academic integrity is broader thanplagiarism. It includes such things as returning library materials promptly so that you are not keepinganother student from completing his or her work.All students at Messiah College must read and abide by the College's policy on academic integrity, whichis found in the 2004–2005 edition of the Student Handbook on pages 108–110. The handbook isavailable on the Internet atwww.messiah.edu/offices/student_affairs/student_handbook/resources/policies.pdfYour signature on the second day of class certifies that you have read and understood and intend tocomply with this policy.Grading45% Exams. Three closed-book tests are worth 15% each. The third—although scheduled during theregularly scheduled final examination week—is not comprehensive30% Labs. Three lab reports are weighted 10% each: Turing machines, C++, and Lisp & Prolog.25% project. A project topic is chosen by date as scheduled (2%), and a list of three sources that youhave read for your project is due as scheduled (3%). You will give a 10-min. report on yourproject on the assigned date (8%). An 8-10 page paper analyzing your project topic is due at 5:30p.m. on the assigned date (12%). Lateness except for emergency is not acceptable.Absences/participation. Keep up with daily readings from your text and discuss them in class. Reportanticipated absences beforehand unless an emergency. Report emergency absences as soon aspossible. Unexcused absences are a 1% deduction of the course grade per absence. Unannouncedquizzes worth 1% on assigned readings are my way to find out if you are participating by keepingup with the readings. Extra credit small class presentations on Wednesdays can earn 1% bonus. In our course, unlike extra credit Wednesdays in some of my other courses, the presentation mustbe related to the topic of our course, but may not be from your textbook.Overview of TopicsThis list of topics includes everything that this course could be about. We will not do all of it. When wereview for exams, we will check off which topics relate to that exam.G Programming languages typesG General: Functional, imperative, object-oriented, other (dataflow, visual, ...)G Purity vs. convenience: E.g. assignment as expression, ternary ifG Special-purpose: SQL, process control, graphics, gaming, ...G Criteria for judging a good programming language (Sebesta, Chapter 1)G Semantic fit to problem domainG Chapter 1 criteriaG History of programming languages (Sebesta, Chapter 2)People: 1 John Backus & team, 2 Grace Murray Hopper & team, 3 John McCarthy, 4 JohnKemeny & Thomas Kurtz, 5 Nikolas Wirth, 6 Ken Iverson, 7 Ralph Griswold, 8 KenThompson & Dennis Ritchie, 9 Bjarne Stroustrup, 10 James Gosling, 11 Larry WallLanguages: 1 Fortran, 2 Cobol, 3 Lisp, 4 Basic, 5 Algol and Pascal and Modula, 6 APL, 7 Snoboland Icon, 8 C, 9 C++, 10 Java, 11 PerlOPL 01.3G Compiler theory, general (Sebesta, Chapters 1 & 4 in part)G Syntax (Sebesta, Chapters 3, and 4.1)G Tokens, lexemesG Recognition, generation, derivationsG Chomsky Hierarchy of GrammarsG FSG, FA, and regular expressions; CSG, BNF, EBNF and parse trees; PDA and LBA;Turing MachinesG ParsingG Top down parsers, e.g. recursive descent as an LL parserG Bottom up (shift-reduce parsers), e.g. LR table parsingG Ambiguous grammarsG Semantics (Sebesta, Chapter 3)G Static semantics, e.g. attribute grammarsG Dynamic semantics to prove program correctnessG OperationalG AxiomaticG Assertions: Preconditions, postconditions, loop invariants, weakest preconditionsG DenotationalG E.g. short-circuit evaluationG E.g. scope of index in a loopG TranslationG Preprocess, compile, link, load, executeG InterpretG Eager vs. lazy evaluationG Learning PerlG Learning C++G Terms to knowG side effects, operator overloading, orthogonality, aliasing, object-based vs. object-orientedG Binding times and lifetimeG Times: Language definition time, compile time,