CS131: Programming Languages
DIS 1D Week 1 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
• Course Information
• Introduction to OCaml • Homework 1
Course Resources
• Course website: https://web.cs.ucla.edu/classes/winter22/cs131/ • BruinLearn: https://bruinlearn.ucla.edu/courses/109764
• Q&AonPiazza:https://piazza.com/ucla/winter22/cs131
• SEASnetaccount:https://www.seas.ucla.edu/acctapp/
• Course book:
– Modern Programming Languages – A Practical Introduction – by Webber
• 6 homework assignments + a project – First homework due: Jan. 14 11:55pm
– Tentative schedule on the course website
• Advice: start early, some homework may take a long time
• Some homework will be automatically graded with scripts – Code doesn’t compile -> (perhaps) no credit 🙁
– To get full credit, code must behave exactly as the specs say
– Make sure your code runs on SEASnet server before submission
• Correctnessismoreimportantthanperformance
– But you might lose points if your solution is too inefficient
• HomeworkwillbesubmittedtoBruinLearn
• DO NOT copy solutions
– Discuss general ideas with others is okay, sharing code or details is not.
• Homework 32%
– Each homework of equal weight, project twice as much • i.e. 1 homework = 4%, project = 8%
– Penalty for late homework submission doubles every day • 1 day = 1%, 2 days = 2%, 3 days = 4%, 4 days = 8%, …
– Must receive a passing grade in homework to pass the course
• Midterm 24%, Feb. 2 (tentative)
• Final 44%, on Mar. 14
– Midterm: 2 hours. Final: 3 hours – Open books/notes
Discussion Sections
• Focus on skills that are needed to solve homework problems
– Basics of programming languages that appears in homework • e.g. For the first 2-3 weeks, OCaml will be the focus
– Provide clarifications for homework
Functional Programming & OCaml
Functional Programming
Major Characteristics of Functional Programming Languages
• No side-effect, the value of “variable” never changes
– Calling a function twice with the same arguments gives identical result – “Pure function”, behaving similarly to mathematical functions
• First-class, higher-order functions
– Functions can take other functions as arguments or return them as result (much like other variables)
• Iteration usually implemented with recursion
Why Learning Functional Programming
• Similar ideas can be found in most modern programming languages – e.g. Python, C++, Java, Swift, Scala, Kotlin, and many more
– We will see examples later when we cover other languages
• Functional programming makes compiling and testing easier – Function without side effect makes reasoning on the code easier
• Easy to build scalable systems
– Computing can be distributed on multiple machines more easily when there is no shared states or side effects
The OCaml Language
• Functional programming language
• Statically typed
– Every value (including function) has a type – Type checking at compile time
• Type infererence
– In many cases, you don’t need to specify types
• Garbage collection
• Compiled language
– But includes an interactive interpreter
Setting up OCaml
• Installinginstructions:https://ocaml.org/docs/install.html – Be sure to install the latest version
• You can also use SEASnet servers:
– lnxsrv11.seas.ucla.edu or 12, 13, 15
– If you don’t have a SEASnet account, create one ASAP:
https://www.seas.ucla.edu/acctapp/
– Make sure the version is 4.13.1
• If not, check that /usr/local/cs/bin is in your path • Instructions on Homework #1 on course website
Running OCaml
• Launch OCaml interpreter: type “ocaml” in terminal
• Options for better command line interface:
– Use “rlwrap ocaml”: history and correction with arrow keys – utop: https://github.com/ocaml-community/utop
– Not necessary, but can make your life much easier.
“Hello World” in OCaml
• First line: calling function “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), which conveys no information in this case
“Variables”
• Not really variables, the value cannot be changed
• Use‘let’keywordtocreatebindingbetweenvalueandname.
• Note: OCaml supports mutable variables too. But they shouldn’t be used in the homework
– Our purpose is to learn the functional programming paradigm
Simple Types
• Functionscanalsobecreatedwith‘let’keyword – let
• Function,justasothervalues,hastype(int->int->int), and can be used as parameters or return values
– About function type:
• The type after last “->” is return type • Previous ones are argument type(s)
• “=
– Note: Do not add parentheses or commas for the arguments.
• Operators are also functions:
– Adding a pair of parentheses converts infix operator to prefix
• Calling a function
Recursive functions • Recursive functions are specified with “let rec”
• If you happen to forget “rec”…
Defining local bindings
• Add keyword “in” after “let” to make the value available in the following expression
– We can also create helper functions with “let … in”
– Use “and” for multiple bindings, or chain multiple “let … in” together.
• Defining a list:
• All elements are of same type – Why? Take a look at the type name.
• Under the hood, lists can be regarded as immutable singly-linked lists
– Iteration on them is fast, random access is slow
Basic list operations
• Non-empty List consists of a head and a tail – Head: the first element; tail: the rest of the list
• We can add an element to the beginning of the list with cons “operator” (::)
– 0 :: [1; 2; 3] gives us [0; 1; 2; 3]
– 0 :: 1 :: 2 :: [3] also gives us [0; 1; 2; 3] • :: is right-associative
– But, 1 :: 2 or [1] :: [2] is not correct.
Exercise: Function and List
• Write a function, is_member x list, which returns true if x is a
member of list, and returns false otherwise
– In fact, this is exactly what OCaml’s List.mem function does
Pattern Matching
• In fact, a better way to implement is_member in OCaml is to use “pattern matching”
– Compare the following two equivalent programs
– This is a common pattern for writing recursive algorithms on lists. Try to remember it and use it often!
– More powerful usages of pattern matching next time.
Exercise: Pattern Matching
• Write an OCaml function list_len list, that returns the length of argument list.
– Can you tell its type before typing the function into OCaml?
Lambda functions
• Lambda functions (aka anonymous functions) are defined with keyword ‘fun’
– Useful when supplying a (small) routine as a function argument
• In fact, the following two are equivalent:
Useful List Operations
• map: transforms each element with a function
• filter: returns a list that contains elements that matches 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
– Lambda functions can be useful in these operations
• Examples:
Useful List Operations
More on types
• Every value in OCaml has a type
• Recap: The type we have learned
– Basic types: int, float, bool, char, string, unit – Functions: e.g. int -> int -> int
– List: e.g. int list
• We’ll learn two more: tuple and variant
• Acollectionofvalues,canbeofdifferenttypes – Values separated by commas
– Often surrounded by parentheses
• Typerepresentation:individualelementtypes,seperatedwith‘*’
• Accessing tuple elements:
– Tuples with two elements: fst my_tuple; snd my_tuple
– Pattern matching (even without “match”, which can get quite versatile):
• One of user-defined types in OCaml • Example 1: “enumeration”
• Example 2: “union” in C/C++
• Using variants with pattern matching – Continuing with “my_type” example
• Question: Can you create a function rem_AB to “get rid of” the “A” and “B” and return the value inside?
– rem_AB (A 3) would return 3; rem_AB (B “hi”) would return “hi”
• Create a function filter_A list, where list is a list of my_type – The return value is an integer list that contains all the integers in “A”
elements of the original list.
– For example, filter_A [A 1; B “foo”; A 3] should return [1; 3]
Homework #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 -> –
Unreachable Rules
• A slightly modified grammar
• The nonterminal symbol INCROP can never be reached from EXPR (starting symbol)
– Thus, rules with INCROP on the left are unreachable rules in this grammar
– In this homework, you need to remove all the unreachable rules according to grammar and starting point
Example Grammar:
EXPR -> NUM
EXPR -> NUM BINOP NUM BINOP -> +
BINOP -> –
INCROP -> ++
Homework #1: Hints
• Read through and understand the test cases
– If problem definition seems unclear, the test cases may help you understand what the expected behavior is
• Read through documentation of List and Stdlib modules
– Most problem can be solved with little code if you properly use existing tools.
• Try to reuse the functions you wrote earlier
Homework #1: Hints
• Q1–Q5: Lists are used to represent sets
– Understand the relationship between them by looking at samples
• Q6-8: Fixed point x, where x = f(x)
– You can assume a fixed point can be obtained by repeatedly applying the function: f(x), f(f(x)), f(f(f(x))), …
• Q9: Copy the following type definition into your code
Homework #1: submission
• You are expected to submit 3 files:
– hw1.ml: The functions you implemented – hw1test.ml: Test cases for your functions
– hw1.txt: Written assessment of how you ended up solving the problems the way you did. See course website for details
• Go to ?
– TAs or your classmates can answer your questions, perhaps the best channel if you are stuck
• Come to office hours
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com