Programming Languages CSCI-4430
Fall 2020
www.cs.rpi.edu/~milanova/csci4430/
Ana Milanova https://rensselaer.webex.com/meet/milana2, milanova@cs.rpi.edu Konstantin Kuzmin https://rensselaer.webex.com/meet/kuzmik2, kuzmik2@rpi.edu
Lecture Outline
n Introduction: the rules! n Strangest Proglang ever
n Programming language spectrum
n Why study programming languages?
n Compilation and interpretation Read: Scott Chapter 1
2
12
Introduction
n Course webpage https://www.cs.rpi.edu/~milanova/csci4430
n Schedule, Notes, Reading
n Schedule, lecture slides, assigned reading, and homework links
n Submitty
n Homework submission and grades (Rainbow grades) n Discussion forum! Announcements!
n Please, submit your TIME ZONE!
Programming Languages CSCI 4430, A. Milanova 3
Introduction
n Required textbook
n Programming Language Pragmatics, 4th Edition, by Michael Scott, Morgan Kaufmann, 2015
n Recommended textbook
n Compilers: Principles, Techniques, and Tools, 2nd Edition, by A. Aho, M. Lam, R. Sethi and J. Ullman, Addison Wesley, 2007 (as known as “The Dragon Book”)
Programming Languages CSCI 4430, A. Milanova 4
34
Introduction
n Syllabus https://www.cs.rpi.edu/~milanova/csci4430/syllabus.html Topics, outcomes, policies, and grading
n 2 midterm exams and a final exam: 47% n 7 homework assignments: 42%
n 8 quizzes: 8%
n 3% office hours check-in
Programming Languages CSCI 4430, A. Milanova 5
Introduction
n Lectures will be WebEx Events on Tuesdays and Fridays 2:30pm – 4:20pm Eastern Time
n You will receive invitation for each lecture
n Begin with Q/A on prior topics/homework, or a quiz n Next, pre-recorded lecture and some Q/A
n Lectures will be available shortly before scheduled lecture:
n Recording:https://mediasite.mms.rpi.edu/Mediasite5/Channel/ programming_languages
n PDFnotes:https://www.cs.rpi.edu/~milanova/csci4430/schedule.html 6
56
1
Introduction
n Homework is due at 2pm on the due date n 6 late days in total
n 2 late days at most per homework
n Extensions only with a formal excuse note from
your class dean. See syllabus for details.
Programming Languages CSCI 4430, A. Milanova 8
Introduction
n Homework is due at 2pm on the due date
n Submit typed homework as a PDF electronically
in Submitty
n Submit programming homework in Submitty for
autograding
n Homework, including submission instructions, will be posted at
n https://www.cs.rpi.edu/~milanova/csci4430/schedule.html Programming Languages CSCI 4430, A. Milanova 7
78
Introduction
n Quizzes
n 8 (or so) quizzes during regularly scheduled
class hours
n Will cover material of previous weeks
n Work in groups (up to 6 people) is encouraged
n Do not post on sites/channels globally visible to class
n If you are unable to “attend” class throughout the term, email us to schedule an alternative time for quizzes and exams. (Syllabus describes
procedure.)
Programming Languages CSCI 4430, A. Milanova 9
Introduction
n Quiz or exam makeup will be arranged only after we have received an excuse note from your class dean. See syllabus for details.
Programming Languages CSCI 4430, A. Milanova 10
9 10
Introduction
n Office hours
n We plan for ample office hours on Mondays,
Wednesdays and Thursdays
n Instructor office hours right after class
n We’ll require weekly office hour “check-ins” starting at week 3 for at least 10 weeks
n TA and mentor office hours via Submitty queues Programming Languages CSCI 4430, A. Milanova 11
Other Notes
n Asking questions
n First, go to Submitty forum
n Do not post code on forum
n You cannot post code to any website n Second, go to office hours
n Sessions are individual, run through Submitty queues, so you can
n Third (last resort): proglang-help@cs.lists.rpi.edu goes to instructors
n We will not be answering questions coming in late at night or in the morning on day HW is due12
11 12
2
Other Notes
n Debugging and homework help in office hours
n Instructor, TA and mentor office hours will be finalized by beginning of next week
Programming Languages CSCI 4430, A. Milanova 14
Other Notes
n Submitty forum
n Announcements – check regularly
n Ask all non-personal questions on the forum n Check out prior messages before you post a
question – the answer is probably already there
n Mailing list proglang@cs.lists.rpi.edu (instructors)
n Personal questions (extensions, grade disputes, etc.)
n Unsolicited debugging emails to instructors or mailing list will likely go unanswered!
Programming Languages CSCI 4430, A. Milanova
13
13
Academic Integrity
n In short, do not copy and do not post your solutions/code on public forums or repos
n Excessive similarities between homework submissions will be considered cheating and handled accordingly
n I trust you. Submitty has advanced plagiarism detection tools that course stuff runs regularly
Programming Languages CSCI 4430, A. Milanova 15
How to Study
n Read textbook chapter in advance of lecture n Chapters are announced on Schedule
n Read/listen lecture and read textbook chapter immediately after class
n Lecture pdfs and recording will be available shortly before scheduled class hours
n Solve exercises in lectures n Form study groups
n ASK QUESTIONS – in class, on forum
Programming Languages CSCI 4430, A. Milanova 16
15
16
How to Study
n A 15 min presentation from the ALAC:
n https://mediasite.mms.rpi.edu/Mediasite5/Pla
y/3c69d5096dc5494eadcaba2b9c99189f1d
Programming Languages CSCI 4430, A. Milanova 17
Course Topics
n Programming language syntax: Scanning and parsing n Programming language semantics: Attribute grammars n Naming, binding and scoping
n Data abstraction and types
n Control abstraction and parameter passing n Concurrency
n Logic-oriented language: Prolog
n Functional languages: Scheme and Haskell n Imperative languages
n Anobject-orientedlanguage:Java n Adynamiclanguage:Python
18
17
18
14
3
Lecture Outline
n Introduction to the course
n Programming language spectrum
n Why study programming languages? n Compilation and interpretation
Programming Languages CSCI 4430, A. Milanova 20
Course Topics
n Schedule at www.cs.rpi.edu/~milanova/csci4430/schedule.html
n Lists major and minor topics
n Homework links, dates and due dates n Quiz and exam schedule
Programming Languages CSCI 4430, A. Milanova
19
19
The Programming Language Spectrum
n Imperative languages
n Von Neumann languages: Fortran, C,… n Object-oriented languages: Java, C++,
Smalltalk,…
n Dynamic languages: Perl, Python, PHP,…
n Declarative languages
n Functional languages: Scheme/Lisp, ML, Haskell n Logic languages: Prolog
n There are other declarative languages: e.g., dataflow languages 21
The Programming Language Spectrum
n Imperative languages
n Evolved from the von Neumann Architecture n Variable
n Assignment
Statement
Programming Languages CSCI 4430, A. Milanova. Graph: Sebesta, 2005 22
21
22
The Programming Language Spectrum
n Imperative languages
n Most widely popular programming style
n FORTRAN, C, C++, C#, Java, Python, Visual BASIC, Perl, JavaScript, Ruby, etc.
n Variable and assignment statement are central concepts
n Program is a sequence of statements: j := i – j;
k := j * l;
n Execution is a sequence of transitions on memory state
Programming Languages CSCI 4430, A. Milanova 23
The Programming Language Spectrum
n FORTRAN was invented in mid-1950
n John Backus, the inventor of FORTRAN, wrote the following paper in 1979:
“Can programming be liberated from the von Neumann style? A functional style and its algebra of programs”
n Problems with imperative languages
n Difficult to understand programs
n Difficult to reason about correctness of programs
Programming Languages CSCI 4430, A. Milanova 24
23
24
20
4
An Example: Inner Product
n Inner product in FORTRAN:
1. C := 0;
2. for I := 1 step 1 until N do 3. C:=C+a[I]*b[I];
n Illustrates state-transition semantics
Programming Languages CSCI 4430, A. Milanova 26
The Programming Language Spectrum
n Functional Programming
n Main alternative to imperative programming
n Lisp/Scheme, ML/OCaml, Haskell
n Program consists of function definitions + evaluation expr
(fun3 (fun2 (fun1 data)))
(fun3 (fun2 data2))
(fun3 data3)
data4
n Execution is a sequence of function applications (i.e., reductions)
n Logic Programming
n Perform queries against knowledge base
n Prolog, Datalog, SQL Programming Languages CSCI 4430, A. Milanova
25
25
An Example: Inner Product
n Inner product in FP:
Def IP = (Insert +) o (ApplyToAll *) o Transpose
IP <<1,2,3>,<6,5,4>> is
(Insert +) ((ApplyToAll *) (Transpose <<1,2,3>,<6,5,4>>)) (Insert +) ((ApplyToAll *) <<1,6>,<2,5>,<3,4>>)
(Insert +) <6,10,12>
28
n Illustrates reduction (applicative) semantics
27
Function composition
Why Study Programming Languages
n Goal of the course: learn to analyze programming languages
n What are the questions we ask when facing a new programming language
n Helps learn new languages, choose the right language for a problem, understand language features, design better languages!
Programming Languages CSCI 4430, A. Milanova 28
27
28
Lecture Outline
n Introduction to the course
n The programming language spectrum
n Why study programming languages
n Compilation and interpretation
Programming Languages CSCI 4430, A. Milanova 29
Compilation and Interpretation
n Compilation n Compiler
n A “high-level” program is translated into executable machine code
n Interpretation n Interpreter
n A program is translated and executed one statement at a time
n Hybrid interpretation
n Both a compiler and an interpreter
n A program is “compiled” into intermediate code;
intermediate code is “interpreted”
Programming Languages CSCI 4430, A. Milanova 30
29
30
26
5
character stream
Scanner (lexical analysis)
token stream parse tree
abstract syntax tree and/or intermediate form
Parser (syntax analysis)
Machine-independent code improvement
Semantic analysis and intermediate code generation
modified intermediate form
target language (assember)
Code Generation
Machine-dependent code improvement
modified
Compilation
position = initial + rate * 60;
Programming Languages CSCI 4430, A. Milanova
Symbol table
Scanner
Parser
1. position,… 2. initial,…
3. rate, …
Semantic analysis and intermediate code generation
32
Compilation
COMPILER
Programming Languages CSCI 4430, A. Milanova
31
31
Compilation
Semantic analysis and intermediate code generation
=
tmp1 = id3 * 60.0 tmp2 = id2 + tmp1 id1 = tmp2
60.0
Abstract Syntax Tree
Intermediate form (three-address code)
Programming Languages CSCI 4430, A. Milanova
33
Compilation
tmp1 = id3 * 60.0 id1 = id2 + tmp1
movf id3, R2 mulf #60.0, R2 movf id2, R1
addf R2, R1 movf R1, id1
Improved intermediate form
Target language
Machine-independent code improvement
Code generation
34
33
34
Interpretation
e.g. BASIC
REM COMMENT LET X = 5 LET Y = 8 PRINT X PRINT Y LET Z = X PRINT Z
…
35
Hybrid Interpretation
09 AB 19 29 99 73 09 AB 19 29 99 73 09 AB 19 29 99 73 09 AB 19 29 99 73 09 AB 19 29 99 73 09
e.g. Java byte code
e.g. Java Virtual Machine (JVM) Also Perl…. 36
35
36
target language
32
6
The End
Programming Languages CSCI 4430, A. Milanova 37 37
7