Transcript Programming Language Concepts - Department of Computer Science

Programming Language Concepts
(CS 360)
Lecture 1: Overview, Grammars, and Little Languages
Jeremy R. Johnson
(Guest Lecturer)
Summer 02-03
Programming Language Concepts
1
Basic Info
• Instructor
– Sam Moelius
– Email: [email protected]
– Office Hours: TBD
• Text
– Concepts of Programming Languages, 5th Ed.
– Robert W. Sebesta
– Addison Wesley
• Web Page
– TBD
• Mailing List
– TBD
Summer 02-03
Programming Language Concepts
2
Course Description
Introduces the design and implementation of modern
programming languages: formal theory underlying language
implementation; concerns in naming, binding, storage allocation
and typing; semantics of expressions and operators, control
flow, and subprograms; procedural and data abstraction;
functional, logic, and object-oriented languages. Students will
construct an interpreter for a non-trivial language.
Summer 02-03
Programming Language Concepts
3
Course Prerequisites
• CS 171 (Prog. I), 172 (Prog. II), and 260 (Data structures)
• Comfortable with an object-oriented language (ideally should
have seen at least two languages)
• Ideal:
– CS 281 (Systems Architecture I) – understanding of the underlying of
basic computer architecture (assembly language, machine organization)
– CS 270 (Foundations of Computer Science) – should be comfortable with
the mathematical tools used to describe and analyze programming
languages (logic, recursion – material on finite state machines and
grammars useful but will be covered in this class)
Summer 02-03
Programming Language Concepts
4
Course Themes
• Tools to evaluate design of languages
• Tools for describing and analyzing languages
– syntax
– semantics
• Tools to design new languages
• Programming Paradigms
• Implementation of programming languages
Summer 02-03
Programming Language Concepts
5
Course Objectives
1. Understand how to compare and evaluate different programming languages and
know what factors need to be taken into account.
2. Be comfortable with the major programming paradigms and be able to use at least
one language from each paradigm.
3. Understand some of the issues involved in implementation of programming
languages; this should help them program more efficiently.
4. Be familiar with elementary concepts of formal language theory such as context-free
grammar.
5. Be able to formally specify the syntax of programming languages.
6. Be familiar with the essentials of lexical analysis and elementary parsing
procedures.
7. Understand dynamic and static scope, dynamic and static binding and the issues
they give rise to.
8. Understand the advantages and disadvantages of strong/weak type checking.
9. Understand the different methods of parameter passing and how they might be
implemented and understand some of the issues involved in calling subroutines.
10. Understand generic programming.
Summer 02-03
Programming Language Concepts
6
Tentative Topics
1.
2.
3.
4.
5.
6.
7.
8.
Week 1: Overview and introductions to grammars (ch. 1 & 3)
Week 2: Functional Languages (ch. 15)
Week 3: Logic Programming Languages (ch. 16)
Week 4: Syntax, Types, Scanning, and Parsing (ch. 3-5)
Week 5: Midterm (more on types and type checking)
Week 6: Data types and Memory allocation (ch. 6)
Week 7: Program semantics and interpreters (ch. 3)
Week 8: Control Structures. Iteration versus Recursion and their
implementation. Templates in C++ and generic programming and its
advantages and pitfalls (ch. 7-9).
9. Week 9: Subroutines and Parameter Passing Methods, Implementing
subroutines (ch. 9-10).
10. Week 10: Abstract data types and object-oriented programming (ch.
11-12)
Summer 02-03
Programming Language Concepts
7
Course Benefits
•
•
•
•
Easier to express ideas
Improved background for selecting appropriate languages
Easier to learn new languages
Understand the significance and impact of language choices
and constructs
• Design new languages (little languages, interface
specifications, protocols)
• Overall advancement of computing
Summer 02-03
Programming Language Concepts
8
Grading Policy
•
Assignments (Programming & Description & Evaluation)
–
•
Midterm Exam
–
•
5 @ 10% each
25%
Final Exam
–
25%
Grades will be determined using a curve with the weighted average
equal to a B provided the average shows understanding of the
material.
All work must be completed independently unless explicitly stated other
wise. Not following this rule is subject to receiving a 0 for the first
offense and subsequent offenses may lead to a lower or failing
grade.
Summer 02-03
Programming Language Concepts
9
Outline (Ch. 1)
•
•
•
Programming Domains
Programming Paradigms
Language Evaluation Criteria
–
–
–
–
•
Influences on language design
–
–
•
Computer architecture
Programming methodologies
Language categories
–
–
–
–
•
Readability
Writability
Reliability
Cost
Imperative
Functional
Logic
Object-oriented
Implementation methods
–
–
–
Interpreter
Compiler
Hybrid
Summer 02-03
Programming Language Concepts
10
Programming Domains
•
Scientific Computing
–
–
–
•
Business Applications
–
–
•
sh, ksh, bash
awk, perl, python
Artificial Intelligence
–
•
assembly
PL/S, BLISS, C
Scripting Languages
–
–
•
COBOL
Spreadsheet, DB, SAP
Systems Programming
–
–
•
FORTRAN
C, C++
Matlab, Maple, Mathematica
lisp, prolog
Special-purpose languages
Summer 02-03
Programming Language Concepts
11
Programming Paradigms
•
Imperative (procedural)
–
•
Data Abstraction
–
•
Lisp, Scheme, ML
Logic (declarative – rule based)
–
•
•
•
•
Simula 67, Smalltalk, C++, java, Ada 95, Eiffel
Functional
–
•
Modula-2
Object Oriented
–
•
Algol, C, FORTRAN, Pascal
prolog
Parallel
Hardware Description Languages
Markup
Special-purpose
Summer 02-03
Programming Language Concepts
12
Evaluation Criteria
•
Readability
–
–
–
–
–
•
Writability
–
–
–
•
Simplicity and orthogonality
Support for abstraction
Expressivity
Reliability
–
–
–
•
Simplicity
Orthogonality
Control statements
Appropriate data types
Syntax considerations
type checking
exception handling
Aliasing
Cost
–
–
–
readability and the learning curve
writability and naturalness of the language for the application
compilation and execution time
Summer 02-03
Programming Language Concepts
13
Source Program
Compilation
Results
Lexical
Analyzer
Lexical Units
Syntax
Analyzer
User Inputs
Machine Language
Code
Generator
Parse Tree
Symbol
Table
Intermediate
Code
Generation
Computer
Optimizer
Intermediate Code
Summer 02-03
Programming Language Concepts
14
von Neumann Architecture
Fetch-Execute Cycle
Memory
1.
2.
Initialize PC, Registers
Repeat
1. Fetch Instruction
2. Increment PC
3. Decode Instruction
4. Execute Instruction
Control
ALU
I/O
CPU
Summer 02-03
Programming Language Concepts
15
Interpretation
Source Program
User Inputs
Interpreter
Results
Summer 02-03
Programming Language Concepts
16