CS131: Programming Languages
DIS 1D Week 2 Winter 2022
Office Hours:
Copyright By PowCoder代写 加微信 powcoder
Tuesday 8-9pm, Friday 9:30-10:30am Zoom Link on CCLE (Same as discussion)
Discussion Section: 1D, Fridays 2:00 – 3:50pm
• More on OCaml
– Pattern Matching
– Types (type variables, variant types, option type) – Functions: Currying
• Grammar in HW 1/2
More on OCaml
Review: Type
• (Adapted from 21F Midterm Q1)
OCaml’s ‘lxor’ operation is bitwise exclusive or, like C/C++’s ‘^’ operator. For example, ‘3 lxor 7’ yields 4.
• Q1: How to make OCaml treat lxor as a function?
• Q2: What is the type of that function? – A:int
– B:int -> int -> int =
– D:’a->’a->’a
– E: None of the above is correct
Review: Pattern Matching
• Q3: Translate the following C code into OCaml that uses lxor and pattern matching. The code should be free of side effect.
struct int_list {
struct int_list *list;
int checksum(struct int_list *p) {
int csum = 0;
for (; p; p = p -> next)
csum ^= p->val;
return csum;
Pattern Matching
• A special kind of control statements that works on “patterns”
• Key points:
– Checking patterns from top to bottom and find the first one that matches
– Checks “whether the matched value can be constructed with the pattern”. In some sense, this is the reverse process of value construction.
• Patterns can be quite flexible:
– Can be used on simple value, list, and other data structures
let is_zero x = match x with
| _ -> false
let my_func l = match l with
[] -> 0
| [x] -> x
| l0 :: l1 :: _ -> l0 + l1
Accessing Elements from Tuples
• Elements from tuples can be accessed with pattern matching:
• This can be simplified:
• And even further:
let first_of_three (a, _, _) = a
let first_of_three x = match x with
| (a, _, _) -> a
let first_of_three = function | (a, _, _) -> a
• One of user-defined types in OCaml • Example 1: “enumeration”
• Example 2: “union” in C/C++
type color = Red | Green | Blue;;
let my_blue = Blue;;
type int_or_string =
| I of int
| S of string;;
let my_i = I 15;;
let my_s = S “hello”;;
• Using variants with pattern matching – Continuing with “int_or_string” example
let print_int_or_string x = match x with
I i -> print_int i
| S s -> print_string s
# print_int_or_string (I 8);; 8
# print_int_or_string (S “foo”);;
Recursive Type with Variant
• “type” keyword can also define recursive data structures, such as trees
# type tree =
| Leaf of int
| Node of tree * tree;;
# let my_tree = Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Leaf 4))
• The “parsing tree” in Homework 2 uses this feature
Practice Questions
• Is it possible to create a function remove_IS, that “gets rids of” the I or S from int_or_string values?
– i.e. remove_IS (I 1) returns 1; remove_IS (S “abc”) returns “abc”
• Write a function extract_int, to extract all integer values from a list
containing int_or_string
– For example:
extract_int [I 1; S “foo”; I 3; S “hello”; I 4] should evaluate to [1; 3; 4]
Polymorphic Types in OCaml
• Previously mentioned:
– Given an expression, OCaml should give an unambiguous type – Type error will arise when type incompatibility occurs
• For example, with lists:
– [2; 3] is of type “int list”; [“foo”; “bar”] is of type “string list” – 1 :: [2; 3] is valid OCaml code, but “abc” :: [2; 3] is not
• Question: What is the type of an empty list ([])?
– The type is “’a list”. This is a polymorphic type.
– ‘a is a type variable. Can be replaced with any concrete type. This is OCaml’s way to do generic programming.
Polymorphic Variant Type • Example in homework1:
• Here, the ‘nonterminal and ‘terminal, are also type variables
– Reason: we want to make the definition of symbol generic. It can be applied to grammars with different types of nonterminal/terminal symbols
– One rule in grammar (type variables replaced with concrete types): – Conceptually similar to C++’s std::map
type (‘nonterminal, ‘terminal) symbol =
| N of ‘nonterminal
| T of ‘terminal
# [T “(“; N Expr; T “)”];;
– : (awksub_nonterminals, string) symbol list = [T “(“; N Expr; T “)”]
Polymorphic types
• Sometimes there isn’t enough information to get a concrete type – OCaml’s principle: make types as generic as possible
# let id x = x;;
val id : ‘a -> ‘a =
# let rec my_map f l = match l with
| hd :: tl -> (f hd) :: (my_map f tl);;
val my_map : (‘a -> ‘b) -> ‘a list -> ‘b list =
• In this case ‘a and ‘b tell us they are polymorphic
– All instances of ‘a should be of same type, so applies to ‘b.
How does OCaml infer types? (bonus) • How does OCaml “magically” finds out the type of my_map
# let rec my_map f l = match l with
| hd :: tl -> (f hd) :: (my_map f tl);;
val my_map : (‘a -> ‘b) -> ‘a list -> ‘b list =
• Answer: By certain set of rules. Conceptual steps look like
– By seeing function invocation “f hd”, f should be a function, and assign it
to the most generic type (‘a -> ‘b)
– Because hd is the argument to f, hd should be of type ‘a.
– hd is an element of l, so l is of type ‘a list
– (f hd) is an element of returned value, it has type ‘b, so the return type is ‘b list
– Check everywhere else to see if everything agrees with each other.
• Used to express possibly “invalid” values
– e.g. null pointers, divide-by-zero
– Purpose: force proper handling of invalid case
• Definition: • Example:
type ‘a option =
| Some of ‘a
let divide a b = match b with
0.0 -> None
| _ -> Some (a /. b)
• Anotherusageofoptiontype:List.filter_map
– filter_map f l applies f to every element of l, filters out the None elements and returns the list of the arguments of the Some elements
• Implement the function extract_int (slide 11) with filter_map
let extract_int l = List.filter_map
I i -> Some i
| S _ -> None) l
Functions • Recap: basic way to define function
• Parentheses: no need to add unless you want to change order of evaluation
– Example:
– Question: what happens if we add parentheses or commas when calling “add 1 2”?
# let add a b = a + b;;
val add : int -> int -> int =
# add 1 2;; – : int = 3
# add 1 2 * 3;; – : int = 9
# add 1 (2 * 3);; – : int = 7
Lambda functions
• Recap: Lambda functions (aka. anonymous functions)
# (fun x -> x + 1) 5;;
– : int = 6
• Note:Thefollowingtwoformsareequivalent.
# let add_one x = x + 1;;
val add_one : int -> int =
# let add_one = fun x -> x + 1;;
val add_one : int -> int =
Currying and Partial Application • Implementadd_onewithadd:
• In fact, OCaml allows us to omit the “x” here:
let add_one = add 1
• Thisiscalledpartialapplication:
– Supply the function with less argument it takes, and get a new function
that expects remaining arguments. – Why? How it works?
let add a b = a + b
let add_one x = add 1 x
Currying and Partial Application
• Function with multiple arguments in OCaml:
– When supplied with one argument, it returns a new function that expects remaining arguments
– For example, the “real behavior” of add with 2 arguments: let add = fun a -> (fun b -> a + b)
• This is called currying: expressing a function with multiple arguments as a series of functions that takes one argument each.
– The nature of functions in OCaml (and many other functional languages)
– The normal way of expressing and using multi-argument functions is provided for our convenience.
Currying and Partial Application • Take another angle, look at function type in OCaml
– add_one has type “int -> int”
• It means that add_one takes an int and returns an int.
– Now we observe: add takes an int (1), and returns add_one (of type int -> int)
• How should we express the type of add, according to this observation? • Answer: It should be int -> (int -> int)
– If we assume “->” is right-associative, then we get int -> int -> int, that’s how OCaml express function type.
Mutual Recursion
• Alternative between multiple functions in recursion – Defining mutual recursion in OCaml
let rec is_even x = match x with 0 -> true
| x -> is_odd (x – 1)
and is_odd x = match x with
0 -> false
| x -> is_even (x – 1)
Context-Free Grammars
• Grammar defines a language
– What strings are valid for a language
• For example, in programming language
– The grammar does not say what instructions in that language mean, it just defines the allowed syntax
– e.g. we can check if print(“Hello, World!”) is valid, without defining what it does
• There are multiple types of grammars, for this homework, you only need to know Context-Free Grammars
Context-Free Grammars
• Basic elements:
• Terminal: symbol that cannot be replaced by other symbols (e.g. +)
• Nonterminal: symbol that can be replaced by other symbols (e.g. BINOP)
• Defines how a nonterminal symbols can be replaced with other symbols
• Grammar contains a starting symbol (e.g. EXPR), and a set of rules
Possible strings of above grammar: 0, 1,
0+0, 0+1, 1+0, 1+1,
0-0, 0-1, 1-0, 1-1
Example Grammar:
EXPR -> NUM
EXPR -> NUM BINOP NUM BINOP -> +
BINOP -> –
Derivation
• One can find out if a sentence is valid by trying to derive it from the grammar
• Top-down, leftmost derivation:
– Begin with start symbol and keep trying different rules in order
– Replace the leftmost non-terminal symbol according to selected rule
• Example: Find a derivation of “1 – 0”
Example Grammar:
EXPR -> NUM BINOP NUM EXPR -> NUM
BINOP -> +
BINOP -> –
NUM -> 0 NUM -> 1
Example Grammar:
EXPR -> NUM BINOP NUM EXPR -> NUM
BINOP -> +
BINOP -> –
NUM -> 0 NUM -> 1
Current sentence:
NUM BINOP NUM 0 BINOP NUM NUM BINOP NUM 1 BINOP NUM
1 BINOP NUM
Derivation (1-0)
Applied rule:
EXPR -> NUM BINOP NUM NUM -> 0
BINOP -> +
BINOP -> – NUM -> 0
Derivation Tree / Parse Tree • The derivation we found is:
EXPR -> NUM BINOP NUM NUM -> 1
BINOP -> –
• Can be expressed as the tree on the right
• You need to implement similar process in the homework 2.
NUM BINOP NUM
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com