Transcript PPT

SML
0, 1, 2, ..., +, -, ...
true, false, if e then e else e
variables
patterns
exceptions
functors
structures
fun f x = e
e1 e 2
fn x => e
datatypes
1
What lies in the core of SML?
0, 1, 2, ..., +, -, ...
true, false, if e then e else e
variables
patterns
?
exceptions
functors
structures
fun f x = e
e1 e 2
fn x => e
datatypes
2
Candidates?
•
•
•
•
•
•
•
•
•
•
booleans and if/then/else
integers
lists
variables
functions and function applications
datatypes
patterns
structures
functors
...
3
Core of SML
x
fn x => e
e1 e2
4
-calculus
5
CSE-321 Programming Languages
-Calculus
박성우
POSTECH
March 21, 2007
Outline
•
•
•
•
Abstract syntax of the -calculus
Operational semantics of the -calculus
Substitutions
Programming in the -calculus
8
Syntax for a Programming Language
Concrete syntax
• program =
string of characters
• specifies rules for parsing.
– operator precedence
– associativity
– keywords, ...
Abstract syntax
• abstracts away from details
of parsing.
• focuses on the high-level
structure of programs.
• suitable for studying the
semantics
1 + 2 * 3
1 + (2 * 3)
1 + (2 * (3))
9
Abstract Syntax of the -Calculus
• x
– variable
– z, s, t, f, arg, accum, ...
•
x. e
– -abstraction
– x = formal argument, e = body
– ¼ fn x => e
• e1 e2
– application
– left-associative (as in SML):
• e1 e2 e3 = (e1 e2 ) e3
• e1 e2 e3  e1 (e2 e3 )
10
Examples
11
Outline
•
•
•
•
Abstract syntax of the -calculus V
Operational semantics of the -calculus
Substitutions
Programming in the -calculus
12
Semantics of Languages
• Answers "what is the meaning of a given program?"
– SML has a formal semantics.
– What about C?
• Three styles
– denotational semantics
– axiomatic semantics
– operational semantics
• The 1990s saw the renaissance of
operational semantics.
13
Operational Semantics
• Specifies how to transform a program into a value
via a sequence of operations
Program
operation
P2
let
fun fac 1 = 1
| fac n = n * fac (n - 1)
in
fac 4
end
operation
...
operation
Pn
operation
Value
24
14
Operational Semantics of -Calculus
• Specifies how to transform an expression into a
value via a sequence of reductions
Expr
reduction
E2
reduction
...
reduction
En
reduction
Value
15
Values and Reductions
16
Reductions
: -reduction
redex = reducible expression
17
_____ = Redex
19
-Reduction Not Unique
So we need a reduction strategy.
21
Call-by-name
Call-by-value
22
Call-by-name
Call-by-value
23
25
Call-by-name
Call-by-value
• Used in Haskell
• Lazy or non-strict
functional languages
• The implementation uses
call-by-need.
• Used in SML
• Eager or strict
functional languages
• Superb!
• Superb!
(fn x => 0) <some horrible computation>
(fn x => 0) <non-terminating computation>
26
Assignments
• Assignment 2
– average 86.68
– Be sure to take a look at the sample solution.
• Assignment 3
– to be out by midnight tonight.
• ???
– due on April 2
– Start early! ( Start coding early!)
27
Quiz 1
• Next Monday
• Read Chapter 2 of Course Notes.
– 'fill in the blank' problems (i.e., easy)
• 15 minutes
– Please show up on time.
Otherwise you might miss the quiz!
28
Anonymous Feedback
• To be set up sometime today (hopefully)
– http://pl.postech.ac.kr/~gla/feedback/
• I will appreciate your feedback on this course.
– lectures
– assignments
– schedule
– topics
• It is you who will improve this course!
29