CS131: Programming Languages

Cheatsheet Content

### Course Overview #### Grading (Homework) - **Homework & Project - 32%** - 6 Homeworks + 1 Project, due on BruinLearn (Gradescope) @ 11:55PM PST - **Equal weighting**, projects worth **x2** as much (e.g., 1 HW = 4% => Project = 8%) - **Late penalty:** 3% of assignment value for submission between N and N+1 days late (e.g., 1 day => 1%, 1-2 days => 3%, 2-3 days => 9%) - Must receive a **passing grade** in homework to pass the course. - Assignments will **not** be accepted after the **last day of instruction**. - Check the **Homework** tab of the website for the assignment schedule. #### Grading (Exams) - **Midterm - 24%** (2 hours in-class, TBA) - **Final - 44%** (3 hours, location TBA on MyUCLA in Week 9) - Exams are **open book/notes**. - **NO** makeups. #### More on Homework - **Start EARLY**. - Some homework is automatically graded with scripts: - Code not compiling? => Likely **no credit**. - For **full credit**, code must behave exactly as specs say. - Make sure code runs on **SEASnet server** prior to submission. - **Correctness** is more important than performance (though inefficient solutions may lose points). - **DO NOT Copy Solutions**: Discussing general ideas is okay, but sharing/GPTing code is **not**. ### Programming Paradigms #### Imperative vs. Declarative Programming - **Imperative programming:** Specifies **HOW** a task should be completed via explicit step-by-step commands and managing program state. - **Declarative programming:** Specifies **WHAT** the desired end result should be and lets the system decide what steps are needed to achieve that outcome. #### Types of Programming Paradigms | Programming Paradigm | Definition | |----------------------|------------| | **Procedural** | Organizes code into reusable units called procedures or functions. | | **Structured** | Replaces excessive use of jumps ("spaghetti code") with logical control structures (sequences, selection, iteration). | | **Object-Oriented** | Organizes software design around objects (data) and methods, emphasizing encapsulation and inheritance. | | **Functional** | Treats computation as evaluation of mathematical functions, avoids changing state or mutable data. | | **Logic** | Programs as a set of logical assertions (predicates, facts, rules); queries solved via inference engine. | ### Functional Programming Paradigm - **No side-effects nor mutability:** - Value of a "variable" **never** changes => immutable. - Calling a function twice with the **same arguments** gives **identical result**. - Functions are "pure" => behave similarly to mathematical functions. - **First-class, higher-order functions:** - Functions can take other functions as arguments or return them as a result (much like other variables). - **Iteration** usually implemented with **recursion**. #### Why Functional Programming? - **Similar ideas** in most modern programming languages (Python, C++, Java, Swift, Scala, Kotlin, etc.). - Makes compiling, debugging, and testing easier, and boosts readability: - Functions **without side effects** make reasoning on code easier. - Facilitates building scalable systems: - Computing can be **distributed on multiple machines more easily** when there are no shared states or side effects (communication between threads is annoying/costly). ### OCaml Introduction - Functional programming language created in 1996 as an extended Caml dialect of ML (meta language **NOT** machine learning) with object-oriented features. - **Statically typed:** Every value (including functions) has a type. - Type checking at **compile time**. - **Type inference:** In many cases, you **don't need to specify types**. - **Garbage collected language:** **No need for manual memory management** (unlike C/C++). - **Compiled language**, but includes an interactive interpreter. #### Setting up OCaml - **Installation Instructions:** [https://ocaml.org/docs/install.html](https://ocaml.org/docs/install.html) - Install the **latest** version. - **SEASnet servers:** `lnxsrv11.seas.ucla.edu` or 12, 13, 15. - If you **don't have** a SEASnet account, create one **ASAP**: [https://www.seasnet.ucla.edu/acctapp/](https://www.seasnet.ucla.edu/acctapp/) - Ensure version 4.13.1; check `/usr/local/cs/bin` is in your `path`. - Instructions for Homework 1 are on the website. #### Running OCaml - Launch OCaml interpreter by typing `ocaml` in the terminal. ```ocaml # print_string "Hello, world!\n";; Hello, world! - : unit = () ``` - **Options for better command line interface:** - `rlwrap ocaml`: History and correction with arrow keys. - `utop`: [https://github.com/ocaml-community/utop](https://github.com/ocaml-community/utop) - VSCode OCaml Platform extension (not necessary, but can make life easier). #### "Hello World" in OCaml ```ocaml # print_string "Hello, world!\n";; Hello, world! - : unit = () ``` - **First Line:** Calls `print_string` with argument "Hello, world!\n". - In **interactive session**, statement ends with **two semi-colons (;;)**, **not needed in code files**. - **Second Line:** Printing output. - **Last Line:** Return value (`unit`). In this case, no useful information is conveyed. #### Variables - Not really "variables" like you're used to; values are **immutable**. - Use `let` keyword to create binding between value and name. ```ocaml # let my_value = 5;; val my_value : int = 5 ``` - **Note:** OCaml supports mutable variables, but they are generally avoided in functional programming. #### Types - **Every** value in OCaml has a type. - **Recap:** - **Basic Types:** `int`, `float`, `bool`, `char`, `string`, `unit` - **Functions:** e.g., `int -> int -> int` - **List:** e.g., `int list` #### Basic Types Table | OCaml Type | Range | |------------|-------| | `int` | 31-bit signed int (32-bit processors) or 63-bit signed int (64-bit processors) | | `float` | IEEE double-precision floating point (C's double) | | `bool` | `true` or `false` | | `char` | 8-bit character | | `string` | String | | `unit` | Written as `()` | ```ocaml # 2 + 3;; - : int = 5 # 2. +. 3.;; - : float = 5. # true && false;; - : bool = false # 'c';; - : char = 'C' # "foobar";; - : string = "foobar" # ();; - : unit = () ``` #### Functions - Functions created with `let` keyword: `let = ` ```ocaml # let average a b = (a + b) / 2;; val average : int -> int -> int = ``` - Functions, like other values, have types (e.g., `int -> int -> int`) and can be used as parameters or return values. - **Function type:** The type after the last `->` is the **return type**; previous ones are **argument types**. - `"= "` is **not** part of the type. #### Calling Functions - Do **not** add parentheses or commas for arguments. ```ocaml # let my_average = average 3 5;; val my_average : int = 4 ``` - **Operators are also functions:** Adding parentheses converts infix operator to prefix. ```ocaml # (+);; - : int -> int -> int = # (+) 2 3;; - : int = 5 ``` #### Recursive Functions - Specified with `let rec`. ```ocaml # let rec factorial a = if a = 1 then 1 else a * factorial (a - 1);; val factorial : int -> int = # factorial 5;; - : int = 120 ``` - Forgetting `rec` causes "Unbound value" error. #### Local Bindings ("Let..In") - Add keyword `in` after `let` to make value available in following expression. ```ocaml # let average a b = let sum = a +. b in sum /. 2.0;; val average : float -> float -> float = ``` - Can create helper functions with `let ... in`. - Use `and` for multiple bindings, or chain multiple `let ... in`. #### Lists - **Definition:** `let numbers = [1;2;3;4;5];;` ```ocaml # let numbers = [1;2;3;4;5];; val numbers : int list = [1; 2; 3; 4; 5] ``` - All elements must be of the **same type**. - Under the hood, lists are **immutable singly-linked lists**. - Iteration is fast, random access is slow. #### Basic List Operations - **Non-empty List:** Consists of a **head** (first element) and a **tail** (rest of the list). ```ocaml # List.hd numbers;; - : int = 1 # List.tl numbers;; - : int list = [2; 3; 4; 5] ``` - **Cons operator (`::`):** Adds an element to the beginning of a list. - `0 :: [1; 2; 3]` gives `[0; 1; 2; 3]` - `0 :: 1 :: 2 :: [3]` gives `[0; 1; 2; 3]` - `::` is **right-associative**. - `1 :: 2` or `[1] :: [2]` is **not correct** => `ERROR`. #### Pattern Matching - A better way to implement `is_member` using pattern matching: ```ocaml # let rec is_member x list = match list with | [] -> false | hd :: tl -> if hd = x then true else is_member x tl ``` - This is a common pattern for writing recursive algorithms on lists. #### Exercise: Pattern Matching (list_len) - Write an OCaml function `list_len` that returns the length of an argument list. ```ocaml let rec list_len lst = match lst with | [] -> 0 (* Base case: An empty list has length 0 *) | _ :: tail -> 1 + list_len tail (* Recursive step: 1 + length of the rest *) ``` - **Type:** `'a list -> int` - `Input`: `'a list` (the argument) - `Output`: `int` (list length) - **`'a` is a type variable** (placeholder for any type). #### Polymorphic Types & Type Variables - **Type variables:** Placeholders for **any type** (useful when not enough info to get a concrete type). - Allow for **polymorphism**: Functions that work with **multiple types** (similar to generics in Java, C#, C++). - In OCaml, denoted with a **single quote (`'`)**. - **Note:** Within a single type expression, multiple occurrences of the **same type variable MUST refer to the same concrete type** (e.g., `'a * 'a` expects a tuple where elements are all of the same type). #### Useful List Operations - `map`: Transforms each element with a function. - `filter`: Returns a list containing elements that match the function. - `rev`: Reverses the list. - `for_all`: Checks if all elements satisfy the specified function. - `exists`: Checks if there exists an element that satisfies the specified function. - **Note:** Lambda functions can be useful in these operations. ```ocaml # List.map (fun x -> x * x) [1;2;3;4;5];; - : int list = [1; 4; 9; 16; 25] # List.filter (fun x -> x mod 2 = 0) [1;2;3;4;5];; - : int list = [2; 4] # List.rev [1;2;3;4;5];; - : int list = [5; 4; 3; 2; 1] # List.for_all (fun x -> x x 'a = # my_fst (3, "foo");; - : int = 3 ``` #### Variants - One of user-defined types in OCaml. - **Example 1: "enumeration"** ```ocaml # type color = Red | Green | Blue;; type color = Red | Green | Blue # let my_blue = Blue;; val my_blue : color = Blue ``` - **Example 2: "union" in C/C++** ```ocaml # type my_type = A of int | B of string;; type my_type = A of int | B of string # let my_a = A 15;; val my_a : my_type = A 15 # let my_b = B "hello";; val my_b : my_type = B "hello" ``` #### Using Variants with Pattern Matching ```ocaml # let my_print x = match x with | A a -> print_int a | B b -> print_string b;; val my_print : my_type -> unit = # my_print (A 8);; 8- : unit = () # my_print (B "foobar");; foobar- : unit = () ``` - **Exercise:** Create a function `rem_AB` to "get rid of" `A` and `B` and return the value inside (e.g., `rem_AB (A 3)` would return `3`). #### Variants: `filter_A` function - Create a function `filter_A list` that returns an integer list containing all integers from `A` elements in the original list. - Example: `filter_A [A 1; B "foo"; A 3]` should return `[1; 3]` ```ocaml # let rec filter_A list = match list with | [] -> [] | A x :: tl -> x :: (filter_A tl) | _ :: tl -> filter_A tl ``` ### Grammar Concepts #### Context-Free Grammars - Defines a language (set of valid strings, sequence of terminal symbols). - **Components:** - **Symbol:** - **Terminal:** Cannot be replaced (e.g., `+`). - **Non-terminal:** Can be replaced (e.g., `BINOP`). - **Rule:** Defines how nonterminal symbols are replaced. - **Start symbols:** Nonterminals that initiate string generation. ``` EXPR -> NUM EXPR -> NUM BINOP NUM BINOP -> + BINOP -> - NUM -> 0 NUM -> 1 ``` - **Possible strings:** 0, 1, 0+0, 0+1, 1+0, 1+1, 0-0, 0-1, 1-0, 1-1. #### Derivation - Validate a sequence by trying to derive it from the grammar. - **Top-down, left-most derivation:** - Begin with start symbol, keep trying different rules in order. - Replace left-most non-terminal symbol according to selected rule. - **Example:** Derivation of `1-0`. #### Derivation & Parse Trees - A derivation can be expressed as a parse tree. ``` EXPR / | \ NUM BINOP NUM | | | 1 - 0 ``` #### Precedence - Determines which operation is performed **first** when multiple operators with **different precedence** exist. - Operators with **higher precedence** are evaluated **before** those with **lower precedence**. #### Associativity - Defines the direction in which operators of the **same precedence** are evaluated. - Can be **left-to-right** or **right-to-left**. #### Ambiguity - A grammar is **ambiguous** if at least one string has more than one parse tree or derivation. #### Ambiguity Practice - **Grammar:** `E -> E + E | E * E | id` - **String:** `id + id * id` - This grammar is ambiguous, as shown by two distinct parse trees for the same string. #### Issues with Ambiguity - Semantic uncertainty - Parser inefficiency and complexity - Non-deterministic and unpredictable code - Challenges in formal verification of a language #### Special Case of Ambiguity (Dangling Else) - Arises when an optional `else` clause in an `if-then-else` statement makes nested conditional statements ambiguous. - More info: [https://www.geeksforgeeks.org/compiler-design/dangling-else-ambiguity/](https://www.geeksforgeeks.org/compiler-design/dangling-else-ambiguity/) #### How to Resolve Ambiguity 1. Simplify production rules. 2. Set precedence and associativity. 3. Resolve left recursion (when a rule refers to itself in a way that causes infinite loop). 4. Factor out common parts (e.g., instead of `A -> αβ` and `A -> αγ`, do `A -> αA'` and `A' -> β | γ`). - More info: [https://www.geeksforgeeks.org/theory-of-computation/removal-of-ambiguity-converting-an-ambiguos-grammar-into-unambiguos-grammar/](https://www.geeksforgeeks.org/theory-of-computation/removal-of-ambiguity-converting-an-ambiguos-grammar-into-unambiguos-grammar/) #### BNF (Backus-Naur Form) - **A BNF grammar contains:** - A set of **terminal symbols (or tokens)**. - A set of **non-terminal symbols**. - A (non-terminal) **start symbol**. - A set of **production rules**. - `LHS ::= RHS` (left-hand side ::= right-hand side) - LHS should be a **non-terminal symbol**. - RHS should be a **sequence of terminals or non-terminals**. #### EBNF (Extended Backus-Naur Form) - **Additional syntax for conciseness/readability:** - `{x}`: Zero or more repetitions of `x` (also `x*`). - `[x]`: Zero or one occurrence of `x` (also `x?`). - `+`: Kleene closure (one or more occurrences). - `( )`: Grouping/precedence. - `=`: Definition. - `(* ... *)`: Comments. #### Abstract Syntax Tree (AST) - **Abbreviated version of a parse tree**. - Details are **implementation-dependent**. - Usually a node for every operation, with subtrees being corresponding operands. #### Syntax Diagram - Visual representation of grammar rules. - **Diagram Bypasses:** Represent optional elements. - **Repetition:** Represented by loops. - **Alternatives:** Represented by branches. #### Blind-Alley Rules - Production rules that make it **impossible** to derive a string containing **only terminal symbols**. - In HW1, you need to **remove all blind-alley rules** according to the grammar and respective start symbol. ### Homework #2 Important Notes - You are writing a **parser generator** that generates a **parsing function** from a **HW1-style grammar**. - **Input:** A string whose prefix is a program to parse. - **Output:** Corresponding unmatched suffix **OR** an error. - **Key Concept:** Matcher functions. #### Prefixes & Suffixes - **Prefix:** The beginning segment of a string of terminals. - **Suffix:** The remaining segment of a string of terminals. - Example: String `["3";"+";"4";"-"]` - A possible prefix is `["3"]`, whose suffix is `["+";"4";"-"]`. #### Matcher - A function that tries to find a prefix that matches a grammar rule. - The validity of the match is based on whether an **acceptor** accepts the suffix. #### Acceptor - A function that **decides if a suffix is valid**. - The acceptor **accepts** the suffix by returning `Some s` where `s` is the tail of the input suffix. - Otherwise, the acceptor **rejects** the suffix by returning `None`. #### `make_matcher` - Old Homework #2 contains a `make_matcher` function with similar functionality. - `make_matcher pattern` returns a matcher function for `pattern`. - The returned matcher function takes a fragment (input sequence) and an acceptor. - If the matcher finds a prefix that matches the pattern, and the acceptor accepts the remaining suffix, it will return `Some suffix`. - Else, the matcher will return `None`. #### Concatenating Matchers - **Basic case:** Concatenate two matchers. - Given two matchers, `matcher1` and `matcher2`, return a matcher that matches `matcher1` and then `matcher2`. - **Hint:** Define a **new acceptor** for `matcher1`. - **Concatenating a list of matchers:** - Use `append_matchers`. - **Divide and Conquer:** If the list is **not** empty, concatenate the first one and the one formed by **recursively concatenating** the rest. #### Currying in Matcher Concatenation - **Currying:** Translating multi-argument functions to a series of single-argument functions. - **Partial Application:** Passing one argument to get a new function. #### Matching Or - Simpler: Try the matchers one by one. - **Similarities with `make_appended_matchers`:** 1. Matcher creation on the fly. 2. Leveraging currying. #### Homework #2 Hints - Tackle problem step by step, in a functional way. - Create the most **basic matcher**. - Build more complicated matchers based on simpler ones: - **Concatenation:** `A, B => A+B` - **Choice:** `A, B => A | B` - Leverage higher-order functions and currying. - Consider relationship between grammar with nucleotide pattern. - Need to implement a **parser tree builder**. #### Homework #2 Submission Expectations - Submit 3 files: - `hw2.ml`: Implemented functions. - `hw2test.ml`: Test cases for your functions. - `hw2.txt`: Written assessment of your solution process. ### Homework #1 Important Notes - **Q1-5:** Lists are used to represent sets. Understand the relationship by looking at samples. - **Q6-8:** Fixed point `x`, where `x = f(x)`. Assume a fixed point can be obtained by repeatedly applying the function: `f(x)`, `f(f(x))`, etc. - **Q9:** Copy the following type definition into your code: ```ocaml type ('nonterminal, 'terminal) symbol = | N of 'nonterminal | T of 'terminal ``` #### Homework #1 Hints - Read through and understand test cases (they help clarify unclear definitions). - Read through documentation of `List` and `Stdlib` modules. - Most problems can be solved with little code if you properly use existing tools. - Try to reuse functions you wrote earlier. #### Homework #1 Submission Expectations - Submit 3 files: - `hw1.ml`: Implemented functions. - `hw1test.ml`: Test cases for your functions. - `hw1.txt`: Written assessment of your solution process. ### Midterm Review #### Midterm Logistics - **Date, Time & Location:** April 30, 2026 (in-class). - **About Exam:** Open book, open note, & **closed** computer/human interaction. #### Midterm Coverage - **Lectures:** All thus far (types, grammars, parse trees, derivations, ambiguity, etc.). - **Homework:** 1, 2 (OCaml). - **Textbook:** 1~11 (ML for OCaml). #### Concepts to Know - Functional Programming Paradigm & Mutability - OCaml Types & Variants - OCaml Functions & Recursion - OCaml Pattern Matching - Higher Order Functions & Currying - Syntax Diagrams, Abstract Syntax Trees, Railroad Diagrams - Grammars & Parsing (BNF, EBNF, Derivations, Resolving Ambiguity) - Java Inheritance, Subtyping, & Generics #### OCaml Functions (Tips) - Have a **clear description** of the algorithm **before** writing code. - Take advantage of OCaml language features and allowed **library functions** to make code expressive. - **Clarity over efficiency** (though speed matters, it's not king). - Ensure your code **compiles**. #### Grammar (Important Things to Know) - Derivations - Grammar Definition Style (from HW1/2) - Parse & Abstract Syntax Trees - BNF & EBNF Form - Syntax Diagrams (Syntax Chart, Syntax Graph, Railroad Diagram, etc.) #### Practice: OCaml Functions - **Example:** 2020F Q7 (Write `adjdup` function). - Your implementation may use `Stdlib` and `List` modules, but no other modules. - **Similar questions:** 2017F 1a, 2008S 7a/b. #### Practice: OCaml Syntactic Sugar - `adjdup` using `List.filter` and `List.partition`. #### Practice: OCaml Functions (Open-ended) - **2020F Q1:** `mcilroy` OCaml function using objects. - **The command:** `tr -cs 'A-Za-z' '[\n*]' | sort | uniq -c | sort -rn` #### Practice: OCaml Functions (Type Specification) - **1a (8 minutes):** Give types of `mcilroy`, `sort`, `tr`, `uniq`. Base types on `char`, not `string`. - **1b (8 minutes):** Implement `mcilroy` in terms of other functions. - **Key:** Specify interface (and type) clearly. - **Considerations:** How to express command line arguments? I/O? - Multiple ways possible; acceptable as long as it makes sense. - No need to worry how "commands" are implemented. #### Practice: OCaml Typing - **2020F Q3b:** Create a higher-order function `r3` that reverses sequence of arguments of 3-argument function. - E.g., `let rf = r3 f` then `(rf c b a)` should act like `(f a b c)`. - **Answer:** `let r3 f a b c = f c b a` - Can you create a generalized version (`rn`) that works for any number of arguments? - E.g., `r3` could be `let r3 = rn 3`, similar for `r2`, `r4`. #### Practice: OCaml Matchers & Acceptors - **2017F Q6:** Rewrite code to use an altered API where acceptor comes first. - **Also:** 2020F Q4. #### Practice: Java Subtype & Inheritance - **2017Fall 3a, 3b:** - **3a:** Is Java subtype relation transitive? Explain or give counterexample. - **3b:** Is Java subtype relation graph a tree? Explain or give counterexample. #### Practice: Java Synchronization - **2021F 4:** Discuss pros and cons of Professor Smullyan's proposal to make every method synchronized by default. #### Practice: Grammar Concepts - **2017Fall 4a, 4e, 2008 3d:** - **4a:** What makes a grammar EBNF and not simply BNF? - **4e:** Draw a syntax chart for the original grammar. - **3d:** Translate rewritten grammar into a syntax diagram. #### Practice: Grammar Ambiguity - **2008 3b:** Show that a given grammar for a subset of C++ is ambiguous. - **2020F Q5a:** Show that a given grammar for a variant of ISO EBNF is ambiguous. - **Pro Tip:** If you can't easily find the answer, move on and revisit later. #### Midterm Tips n Tricks - Take the practice midterms (BruinLearn > Modules > Week 4). - Review "How to Crack Eggert Exams for Smarties" on the 2024 Sample Midterm. - Go to office hours (BruinLearn > Home). - Ask questions on Piazza. - Review past lectures (BruinLearn > Zoom - avoid using Firefox). - Review past homework and recommended resources. #### Teaching Feedback Survey - Help me, help you (yes you) 🤞 - Please complete the teaching feedback survey **after** discussion each week so I can better tailor it to your needs. Thanks! - Link: [https://forms.gle/2jYZeX4sMbUxFYFA6](https://forms.gle/2jYZeX4sMbUxFYFA6) #### Learning Assistant (LA) Feedback Survey - Help our LAs help you (yes you) 🤞 - Please complete the learning assistant feedback survey (it is worth a small part of your grade per the syllabus 😊). Thanks! - Link: [https://laprogramucla.com/feedback](https://laprogramucla.com/feedback) #### Additional (Helpful) Resources - **OCaml Programming: Correct + Efficient + Beautiful** by Michael R. Clarkson (HIGHLY RECOMMEND): [https://cs3110.github.io/textbook/cover.html#ocaml-programming-correct-efficient-beautiful](https://cs3110.github.io/textbook/cover.html#ocaml-programming-correct-efficient-beautiful) - **OCaml from the Beginning** by John Whitington: [https://ocaml-book.com/videos](https://ocaml-book.com/videos) - **Introduction to OCaml** by Jason Hickey: [https://courses.cms.caltech.edu/cs134/cs134b/book.pdf](https://courses.cms.caltech.edu/cs134/cs134b/book.pdf) - **OCaml.org (Docs):** [https://ocaml.org/](https://ocaml.org/) - **Neso Academy (HIGHLY RECOMMEND):** - **Derivations of Context Free Grammars (CFGs):** [https://www.youtube.com/watch?v=3rzTRtjUM_I](https://www.youtube.com/watch?v=3rzTRtjUM_I) - **Associativity & Precedence in CFGs:** [https://www.youtube.com/watch?v=q8uBrWsD4q4&pp=ygUWcHJlY2VkZW5jZSBpbiBncmFtYmWFycw%3D%3D](https://www.youtube.com/watch?v=q8uBrWsD4q4&pp=ygUWcHJlY2VkZW5jZSBpbiBncmFtYmWFycw%3D%3D) - **Ambiguity in CFGs:** [https://www.youtube.com/watch?v=gUaAKAj-rqA&list=PLBInK6fEyqRjT3oJxFXRgjPNzeS-LFY-q&index=15](https://www.youtube.com/watch?v=gUaAKAj-rqA&list=PLBInK6fEyqRjT3oJxFXRgjPNzeS-LFY-q&index=15)