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

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]
Prof. B. Pientka COMP302: Programming Languages and Paradigms

Function Tidbit: (in the 70’s)
Prof. B. Pientka COMP302: Programming Languages and Paradigms 3 / 18

Prof. B. Pientka COMP302: Programming Languages and Paradigms 4 / 18

• Functions are values
• Function names establish a binding of the function name to its body
let area (r:float) = pi *. r *. r;;
Prof. B. Pientka COMP302: Programming Languages and Paradigms 4 / 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
let rec fact n =
if n = 0 then 1
else n * fact (n-1)
Prof. B. Pientka COMP302: Programming Languages and Paradigms 4 / 18

Prof. B. Pientka COMP302: Programming Languages and Paradigms 5 / 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!
Prof. B. Pientka COMP302: Programming Languages and Paradigms 6 / 18

Example: Rewriting Factorial
Prof. B. Pientka COMP302: Programming Languages and Paradigms 7 / 18

Example: Rewriting Factorial
let rec fact_tr n = let rec f (n, m) =
if n=0 then
else f(n-1, n*m)
1 2 3 4 5 6 7
• 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
Prof. B. Pientka COMP302: Programming Languages and Paradigms 7 / 18

Example: Rewriting Factorial
let rec fact_tr n = let rec f (n, m) =
if n=0 then
else f(n-1, n*m)
1 2 3 4 5 6 7
• 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
What value shall we put in for the questionmark?
Prof. B. Pientka COMP302: Programming Languages and Paradigms 7 / 18

Example: Rewriting Factorial
let rec fact_tr n = let rec f (n, m) =
if n=0 then
else f(n-1, n*m)
1 2 3 4 5 6 7
• 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
What is the type of f?
Prof. B. Pientka COMP302: Programming Languages and Paradigms 8 / 18

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.)
Prof. B. Pientka COMP302: Programming Languages and Paradigms 9 / 18

Data Types and Pattern Matching
Prof. B. Pientka COMP302: Programming Languages and Paradigms 10 / 18

Playing Cards
How can we model a collection of cards?
Prof. B. Pientka COMP302: Programming Languages and Paradigms 11 / 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
Prof. B. Pientka COMP302: Programming Languages and Paradigms 11 / 18

User-Defined (Non-Recursive) Data Type
1 type suit = Clubs | Spades | Hearts | Diamonds
Prof. B. Pientka COMP302: Programming Languages and Paradigms 12 / 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
Prof. B. Pientka COMP302: Programming Languages and Paradigms 12 / 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.
Prof. B. Pientka COMP302: Programming Languages and Paradigms 12 / 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
Prof. B. Pientka COMP302: Programming Languages and Paradigms 13 / 18

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

Related Posts