ProgrammingLanguagesA Flashcards
Syntax
is just how you write something
Semantics
is what something that you write means
for variable bindings
- type-check expression and extend static environment
- evaluate expression and extend dynamic environment
comments on ML
(* comment text *)
variables on ML
val r = 4
(* static environment: r : int )
( dynamic environment: r –> 4 *)
conditions on ML
val abs_of_z = if z < 0 then 0 - z else z;
(* static environment: abs_of_z–>int, z–>int )
( dynamic environment: abs_of_z–>70, z–>70 *)
VALUES
- all values are expressions
- not all expressions are values
- every value “evaluates to itself” in “zero steps”
conditions syntax and type-checking
if e1 then e2 else e3
where if, then, else - keywords and e1, e2, e3 - subexpressions
Type-checking:
e1 must have type bool,
e2 and e3 - may be any of type but both should have same type
Evaluation rules:
first evaluate e1 to a value call it v1
if its true - evaluate e2
else - evaluate e3
REPL
read eval print loop
Shadowing
Это когда одна переменная переобъявляется заново
val a = 5
val b = a * 10
val a = 10
Example: function binding
fun pow (x:int, y:int) =
if y=0
then 1
else x * pow(x, y-1)
FUNCTION
Syntax:
- fun x0(x1: t1, …, xn : tn) = e
Evaluation: A function is a value!(No evaluation yet)
- adds x0 to environment
- function call semantics also will also allow recursion
Type-checking:
- adds binding x0 : (t1 * … * tn) -> t if:
- can type-check body e to have type t in the static environment containing:
“Enclosing” static environment (earlier bindings)
x1 : t1, …, xn : tn (arguments with their types)
x0 : (t1 * … * tn)-> tn ( for recursion)
Tuples create
Syntax: (e1,e2) Evaluation: Evaluate e1 to v1 and e2 to v2; result is(v1, v2) - A pair of values is a value Type-checking: if e1 has type ta and e2 has type tb, then the pair expression has type ta * tb - A new kind of type
Tuples access
Syntax:
#1 e and #2 e
Evaluation:
Evaluate e to a pair of values and return first or second piece
- Example: if e is a variable x, then look up x in environment
Type-checking:
if e has type ta * tb, then #1 e has type ta and #2 e has type tb
Building lists
The empty list is a value:
[]
In general, a list of values is a value; elements separated by commas:
[v1, v2, v3,…,vn]
if e1 evaluates to v and e2 evaluates to a list [v1, …, vn], then e1::e2 evaluated to [v, …, vn]
e1::e2 (* pronounced cons *)
Accessing lists
null e evaluates to true if and only if e evaluates to []
if e evaluates to [v1, v2, …, vn] then hd e evaluates to v1
- ( raise exception if e evaluates to [])
if e evaluates to [v1, v2, …, vn] then tl e evaluates to [v2, …, vn]
- ( raise exception if e evaluates to [])
- Notice - result is a list
Type-checking list operations
For any type t, the type t list describes lists where all elements have type t
So [] list can have type t list list of any type
- SML uses type ‘a list to indicate this
List functions
fun sum_list(xs : int list) =
if null xs
then 0
else hd xs + sum_list(tl xs)
fun countdown(x : int) = if x=0 then [] else x :: countdown(x-1)
fun append(xs : int list, ys : int list) =
if null xs
then ys
else (hd xs) :: (append((tl xs), ys))
Let expressions
Syntax:
let b1 b2 … bn in e end
each bi is a binding and e is any expression
Type-checking:
Type-check each bi and e in a static environment that includes the previous bindings. Type of whole let-expression is the type of e
Evaluation:
Evaluate each bi and e in a dynamic environment that includes the previous bindings. Result of whole let-expression is result of evaluating e
Nested Functions
fun countup_from1(x : int) =
let
fun count(from : int, to : int) =
if from=to
then to::[]
else from :: count(from+1, to)
in
count(1,x)
endOptions
fun max1(xs : int list) =
if null xs
then NONE
else
let val tl_ans = max1(tl xs)
in if isSome tl_ans andalso valof tl_ans > hd xs
then tl_ans
else SOME (hd xs)
endBoolean operations
e1 andalso e2
e1 orelse e2
not e1
Comparison operations
= <> > < >= <=
Compound types
one of, each of, selfreference
