CS考试辅导 COMP302: Programming Languages and Paradigms

COMP302: Programming Languages and Paradigms
Prof. (Sec 01) Francisco Ferreira (Sec 02)

School of Computer Science Mc

Week 1-2, Fall 2017

Functional Tidbit: . Curry
• Logician and Mathematician
• 12 Sept 1900 – 1 Sept 1982
• Most known for the Curry-Howard-Isomorphism
i.e.direct relationship between programs and proofs
• Prog. language Haskell is named after him.
COMP302: Programming Languages and Paradigms 2 / 18

What is OCaml?
Statically Typed Functional Programming Language
COMP302: Programming Languages and Paradigms 3 / 18

What is OCaml?
Statically Typed Functional Programming Language
• Types approximate runtime
• Analyze programs before executing them
• Find and fix bugs before testing
COMP302: Programming Languages and Paradigms

What is OCaml?
Statically Typed Functional Programming Language
• Types approximate runtime behaviour
• Analyze programs before executing them
• Find and fix bugs before testing
• Primary expressions are functions!
• Functions are first-class!
• Pure vs Not Pure
• Call-By-Value vs Lazy
COMP302: Programming Languages and Paradigms

Concepts for Today
• Writing and executing basic expressions • Learn how to read error message
• Names, Values, Basic Types
• Variable, Bindings, Scope of Variables • Simple Functions
COMP302: Programming Languages and Paradigms

Step 1:Basic Expressions
COMP302: Programming Languages and Paradigms 5 / 18

Step 2:Variables and Bindings
COMP302: Programming Languages and Paradigms 6 / 18

Step 2:Variables and Bindings
• Variable binding is not an assignment
• Variables cannot be updated – we can only overshadow a previous
• Variable bindings persist
• Garbage collection disposes off variable bindings that are not needed anymore
• Variable bindings are local – they exist within a scope
• Variables are bound to a value – not an expression
COMP302: Programming Languages and Paradigms 6 / 18

Function Tidbit:
• Professor at MIT
• John von [2014]
• Turing Award for her work in the design of programming languages and software methodology [2008]
“The motivation behind the work in very-high-level languages is to ease the programming task by providing the programmer with a language containing primitives or abstractions suitable to his problem area. The programmer is then able to spend his effort in the right place; he concentrates on solving his problem, and the resulting program will be more reliable as a result. Clearly, this is a worthwhile goal.” B. Liskov [1974]
COMP302: Programming Languages and Paradigms

Function Tidbit: (in the 70’s)
COMP302: Programming Languages and Paradigms 8 / 18

COMP302: Programming Languages and Paradigms 9 / 18

• Functions are values
• Function names establish a binding of the function name to its body
let area (r:float) =pi ∗. r ∗. r;;
COMP302: Programming Languages and Paradigms 9 / 18

• Functions are values
• Function names establish a binding of the function name to its body
let area (r:float) =pi ∗. r ∗. r;;
• Recursive functions are declared using the keyword let rec
letrecfactn= if n = 0 then 1
else n ∗ fact (n−1)
COMP302: Programming Languages and Paradigms

COMP302: Programming Languages and Paradigms 10 / 18

Tail-recursive Functions
A function is said to be ”tail-recursive”, if there is nothing to do except return the final value. Since the execution of the function is done, saving its stack frame (i.e. where we remember the work we still in general need to do), is redundant.
• Write efficient code
• All recursive functions can be translated into tail-recursive form!
COMP302: Programming Languages and Paradigms

Example: Rewriting Factorial
COMP302: Programming Languages and Paradigms 13 / 18

Example: Rewriting Factorial
1 2 3 4 5 6 7
letrecfacttr1n= let rec f (n, m) =
if n=0 then m
else f(n−1, n∗m) in
• Second parameter to accumulate the result; in the base case we simply return its result
• Avoids having to return a value from the recursive call and subsequently doing further computation.
• Avoids building up a runtime stack to memoize what needs to be done once the recursive call returns a value
COMP302: Programming Languages and Paradigms

Passing Arguments
• Passing all arguments at the same time
’a * ’b -> ’c
• Passing one argument at a time
’a -> ’b -> ’c
• Remark: We can translate any function of type ’a -> ’b -> ’c to a function of type ’a * ’b -> ’c and vice versa. This is called currying (uncurrying resp.)
COMP302: Programming Languages and Paradigms 14 / 18

Data Types and Pattern Matching
COMP302: Programming Languages and Paradigms 15 / 18

Playing Cards
How can we model a collection of cards?
COMP302: Programming Languages and Paradigms 16 / 18

Playing Cards
How can we model a collection of cards?
Declare a new type together with its elements
1 type suit = Clubs | Spades | Hearts | Diamonds
COMP302: Programming Languages and Paradigms 16 / 18

User-Defined (Non-Recursive) Data Type
1 type suit = Clubs | Spades | Hearts | Diamonds
COMP302: Programming Languages and Paradigms 17 / 18

User-Defined (Non-Recursive) Data Type
1 type suit = Clubs | Spades | Hearts | Diamonds
• The order in which we declare these elements does not matter
COMP302: Programming Languages and Paradigms 17 / 18

User-Defined (Non-Recursive) Data Type
1 type suit = Clubs | Spades | Hearts | Diamonds
• The order in which we declare these elements does not matter
• We call Clubs, Spades, Hearts, Diamonds constructors.
• Constructors must begin with a capital letter in OCaml.
• Use pattern matching to analyze elements of a given type.
match with
| −> | −>
| −>
A pattern is either a variable, underscore (wild card), or a constructor.
COMP302: Programming Languages and Paradigms 17 / 18

Comparing Suits
Write a function dom of type suit∗suit −> bool
dom(s1,s2) = true iff suit s1 beats or is equal to suit s2 relative to the ordering
Spades > Hearts > Diamods > Clubs
COMP302: Programming Languages and Paradigms 18 / 18

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts