Transcript 00-intro - NUS School of Computing

CS5205: Foundation in Programming
Languages
Lecture 0 : Overview
“Language Foundation,
Extensions and Reasoning
Lecturer : Chin Wei Ngan
Email : [email protected]
Office : COM2 4-32
CS5205
Introduction
1
Course Objectives
- graduate-level course with foundation focus
- languages as tools for programming
- foundations for reasoning about programs
- explore various language innovations
CS5205
Introduction
2
Course Outline
• Lecture Topics (13 weeks)
• Advanced Typed Language (Haskell)
http://www.haskell.org
• Lambda Calculus (Core Language)
• Interpreters
• Untyped Scripting Language (Python)
http://www.python.org
• Type System for Lightweight Analysis
http://www.cs.cmu.edu/~rwh/plbook/book.pdf
• Semantics
CS5205
Introduction
3
Administrative Matters
- mainly IVLE
- Reading Materials (mostly online):
www.haskell.org
Robert Harper : Foundations of Practical Programming Languages.
Free PL books : http://freeprogrammingbooks.com
- Lectures + Assignments + Paper Reading+ Exam
- Assignment/Project (35%)
- Paper Reading (10%)
- Quiz (10%)
- Exam (45%)
CS5205
Introduction
4
Paper Presentation
•
•
•
•
Focus on Language Innovation/Application
Select A Paper (Week 2)
Give Presentation (Week 4/5)
Possible Topics
•
• Concurrent and MultiCore Programming
• Software Transaction Memory
• GUI Programming
• Testing with QuickCheck
• IDE for Haskell
• SELinks (OCaml)
• etc
A List of Papers/Conferences will be given next week.
CS5205
Introduction
5
Assignments/Project (35%)
•
•
CS5205
Small Exercises
Mini-Project
• List of possible projects (Week 5)
• Your own project
• A useful tool
• Use advanced languages, such as
Haskell, Ocaml, F#, Python, Boo, etc
• Evaluation
(i) presentation/demo
(ii) draft report/paper
Introduction
6
Why Study Foundations of PL?
•
Language used to organize programming thoughts.
•
Language can describe and organize computation.
•
Language features affect how ideas are expressed.
•
Foundation needed to support the design of good
language features
CS5205
Introduction
7
Benefits of Good PL Features
•
Readability
•
Extensible Software.
•
Modifiability.
•
Reusability.
•
Correctness.
CS5205
Introduction
8
Benefits of Studying Foundations of PL
•
Design new languages for your work/research?
•
Inside any successful software system is a PL
Emacs : Elisp
Word, PPT : VBScript
Quake : QuakeC
Facebook : FBML, FBJS
Twitter : Ruby on Rails/Scala
Also: Latex, XML, SQL, PS/PDF
CS5205
Introduction
9
Benefits of Studying Foundations of PL
•
Different language paradigm can support different
approaches to a given problem.
•
Can choose a solution that is best (or good
enough) for the given problem.
•
PL is the primary tool of choice for programmers.
If properly selected, it can amplify your
programming capability.
•
Era of domain-specific programming languages.
CS5205
Introduction
10
Many Dimensions of PL
•
•
•
•
•
•
CS5205
Syntax – verbose vs succint. prefix vs distfix.
Computational model : functional, imperative, OO
or constraint-based.
Memory Model : explicit deallocation, garbage
collection or region-based.
Typing : static vs dynamic typing; strong vs weak
typing.
Execution Model : compiled (C/C++), interpreted
(Perl), hybrid (Java).
Scoping : static vs dynamic scoping.
Introduction
11
Advanced Language - Haskell
•
•
•
•
•
•
•
Strongly-typed with polymorphism
Higher-order functions
Pure Lazy Language.
Algebraic data types + records
Exceptions
Type classes, Monads, Arrows, etc
Advantages : concise, abstract, reuse
• Why use Haskell ?
CS5205
cool & greater
productivity
Introduction
12
Some Applications of FP/Haskell
• Hoogle – search in code library
• Darcs – distributed version control
• Programming user interface with arrows..
• How to program multicore?
• map/reduce and Cloud computing
• Bioinformatics
• Cryptography
CS5205
Introduction
13
Example - Haskell Program
• Apply a function to every element of a list.
a type variable
data List a = Nil | Cons a (List a)
type is : (a  b)  (List a)  (List b)
map f
Nil
= Nil
map f (Cons x xs) = Cons (f x) (map f xs)
map sqr(Cons 1 (Cons 2 (Cons 3 Nil)))
==> (Cons 1 (Cons 4 (Cons 9 Nil)))
CS5205
Introduction
14
Example - Haskell Program
• Built-in List Type with syntactic sugar
data [a] = [] | a:[a]
map :: (a  b)  [a]  [b]
map f []
= []
map f (x:xs) = (f x):(map f xs)
map sqr 1:(2:(3:[]))
==> 1:(4:(9:[]))
map sqr [1,2,3]
==> [1,4,9]
CS5205
Introduction
15
Paradigm : Functional Expression
Problem : sum the square of a list of numbers
sumsq [1,2,3,4] = 1*1 +2*2 +3*3 + 4*4.
Problem : sum the square of a list of numbers
sumsq [] = 0
sumsq (x:xs) = (sqr x) + (sumsq xs)
CS5205
Introduction
16
Paradigm : Imperative Loop
Problem : sum the square of a list of numbers
sumsq [1,2,3,4] = 1*1 +2*2 +3*3 + 4*4.
In F# (Ocaml dialect)
sumsq :: [Int] = Int
sumsq xs = let s = ref 0 in
for x in xs
s := !s + x ;
s
CS5205
Introduction
17
Paradigm : Function-Level Composition
•
Sum a list:
sum [] = 0
sum (x:xs) = x + (sum xs)
•
Square a list:
square xs = map sqr xs
•
Sum a square of list:
square
= sum o (map sqr)
square
= (map sqr) | sum
square xs
CS5205
= xs |> (map sqr) |> sum
Introduction
18