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
Records
val x = {bar=(3,true),baz=(false,9),foo=8}
#bar x
#bi x -> TypeErrorTuples are just
syntactic sugar for records
Datatype binding
datatype mytype = TwoInts of int * int | Str of string
1) adds a new type mytype
2) adds constructors to the environment: TwoInts, Str
3) constructor is a function that makes values of the new type
Example
datatype id = StudentNum of int
| Name of string * (string option) * string
Using datatypes
1) Check what variant it is
2) Extract the data
Case expressions
fun f x =
case x of
Pizza => 3
| Str s => 8
| TwoInts(i1, i2) => i1 + i2enumerations in datatypes
datatype suit = Club | Diamond | Heart | Spade
datatype rank = Jack | Queen | King | Ace | Num of int
Expression trees
datatype exp = Constant of int
| Negate of exp
| Add of exp * exp
| Multiply of exp * exp
Usage:
Add (Constant(10), Negate(Constant 4))
fun eval e =
case e of
Constant i => i
| Negate e2 => ~ (eval e2)
| Add(e1,e2) => (eval e1) + (eval e2)
| Multiply(e1,e2) => (eval e1) * (eval e2)
Type synonim
type aname = t
Recursive datatypes
datatype my_int_list = Empty | Cons of int * my_int_list
val x = Cons(4, Cons(23, Cons(1988,Empty)))
Options are datatypes
fun inc_or_zero intoption =
case intoption of
NONE => 0
| SOME i => i + 1
null
fun mystery x =
case x of
[] => true
x::xs => false
polymorphic datatypes
datatype a option = NONE | SOME of a
datatype a mylist = Empty | Cons of a * a mylist
datatype (a,b) tree = Node of a * (a,b) tree * (a,b) tree | Leaf of `b
fun num_leaves tr =
case tr of
Leaf i => 1
| Node(i,lft,rgt) => num_leaves lft + num_leaves rgt
Pattern matching
fun sum_triple triple =
case triple of
(x, y, z) => x + y + z
fun full_name r =
case r of
{first=x, middle=y, last=z} => x ^ “ “ ^ y ^ “ “ ^ z
Function-argument pattern
fun sum_triple(x, y, z) =
x + y + z
fun full_name{first=x,middle=y,last=z} =
x ^ “ “ ^ y ^ “ “ ^ z
“Zero arguments” is a
unit pattern () matching the unit value
Unexpected polymorphism
(* int * 'a * int -> int *) fun partial_sum(x,y,z) = x + z
Polymorphic and Equality types
(* 'a list * 'a list -> 'a list *)
fun append(xs,ys) =
case xs of
[] => xs
| x::xs' => x :: append(xs', ys)
(* ''a list * ''a list -> string *)
fun same_thing(x, y) =
if x=y then "yes" else "no
Fun patterns
fun eval(Constant i) = i
| eval(Negate e2) = ~ (eval e2)
| eval(Add(e1,e2)) = (eval e1) + (eval e2)
| eval(Multiply(e1,e2)) = (eval e1) * (eval e2)
just syntactic sugar for case expression
Exceptions
exception MyException
exception MyExceptionTwo of int * int
e1 handle p => e2
fun hd xs =
case xs of
[] => raise List.Empty
| x::_ => xTail recursion example
fun fact n =
let fun aux(n,acc) =
if n=0
then acc
else aux(n-1, acc*n)
in
aux(n, 1)
endWhat is the result of evaluating this expression, in SML/NJ?
#h {f=3,g=12}TypeError
This will result in a type error, as the type checker can tell statically that there is no field named h within a record with field names f and g.
Фу́нкция вы́сшего поря́дка
функция, принимающая в качестве аргументов другие функции или возвращающая другую функцию в качестве результата. Основная идея состоит в том, что функции имеют тот же статус, что и другие объекты данных.
Замыкание
функция первого класса, в теле которой присутствуют ссылки на переменные, объявленные вне тела этой функции в окружающем коде и не являющиеся её параметрами. Говоря другим языком, замыкание — функция, которая ссылается на свободные переменные в своей области видимости.
Пример передачи в функцию функцию-аргумент
fun double x = x + x fun n_times(f,n,x) = if n=0 then x else f (n_times(f, n-1, x))
n_times(double, 1, 1)
Anonymous functions
fun triple_n_times(n, x) =
n_times(fn x => 3 * x, n, x)
(* minuses => cannot call recursively *)
Lexical scope(example)
(* 1 *) val x = 1 (* x maps to 1 *) (* 2 *) fun f y = x + y (* f maps to a function that adds 1 to its argument *) (* 3 *) val x = 2 (* x maps to 2 *) (* 4 *) val y = 3 (* y maps to 3 *) (* 5 *) val z = f (x + y) (* call the function defined on line 2 with 5 *) (* z maps to 6 *)
Closures and recomputation
(* Not bad *) fun allShorterThan1(xs, s) = filter(fn x => String.size x < String.size s, xs) (* Good - i not evaluate for every element *) fun allShorterThan2(xs, s) = let val i = String.size s in filter(fn x => String.size x < i, xs) end
function composition
fun compose(f,g) = fn x => f(g, x)
infix !>
fun x !> f = f x
fun sqrt_of_abs i = i !> abs !> Real.fromInt !> Math.sqrt
currying
val sorted3 = fn x => fn y => fn z => z >= y andalso y >= x;
sorted3 1 2 3 (* return true *)
Mutable references
t ref (* where t is type *) ref e (* to create a reference with initial contents e *) e1 := e2 (* to update contents *) !e (* to retrieve contents *)
Type inference
правила как выводится тип передаваемого принимаемого значения
Mutual Recursion
Allow f to call g and g to call f
Mutually recursive functions
fun f1 p1 = e1
and f2 p2 = e2
and f3 p3 = e3
Mutually recursive datatype bindings
datatype t1 = …
and t2 = …
and t3 = …
Namespace management
structure MyMathLib = struct fun fact x = if x=0 then 1 else x * fact(x-1) val half_pi = Math.pi / 2.0 fun doubler y = y + y end
val pi = MyMathLib.half_pi + MyMathLib.half_pi
val twenty_eight = MyMathLib.doubler 14
Example of State Machines
fun match xs = let fun s_need_one xs = let fun s_need_two xs = case xs of [] => false | 2::xs' => s_need_one xs' | _ => false in case xs of [] => true | 1::xs' => s_need_two xs' | _ => false end in s_need_one xs end
