CS计算机代考程序代写 algorithm data structure Haskell Java Lecture 5. FuncLang – Functions

Lecture 5. FuncLang – Functions
February 23, 2021

Overview
􏰉 FuncLang: writing programs in functional programming languages 􏰉 lambda expression
􏰉 recursion
􏰉 high-order functions
􏰉 build-in functions (list, pair) 􏰉 control structures
􏰉 Syntax
􏰉 Semantics
􏰉 Implementation

Abstraction in Programming Languages
􏰉 Variable in imperative programming languages
􏰉 fixed abstraction – you cannot change computation 􏰉 representing values
􏰉 Function (procedure, method):
􏰉 parameterization for computation
􏰉 you can reuse the functionality for different concrete input
􏰉 language features that can define a procedure and call a procedure

Lambda Expression
􏰉 Defining anonymous function
􏰉 Compare to ALGOL family languages: C, C++, Java … (syntax): 􏰉 not specify the name of the function
􏰉 formal parameter name only, no types precede or follow 􏰉 no explicit return is needed
􏰉 Compare to ALGOL family languages: C, C++, Java … (semantics): Procedures and methods: proxy of the location of a section of code
􏰉 adjust the environment
􏰉 jump to the location Lambda abstraction:
􏰉 generate runtime values
􏰉 each of the runtime values can be used multiple times

Examples: Lambda Expression

Examples: Calling the Lambda function

Examples: Combine with Let and Define

Exercise: Lambda Expression
Write some Lambda Expressions with Let and Define

Exercise: Lambda Expression
$ (define identity (lambda (x) x))
$ (identity 2) 2
$ (define test (lambda (x y z ) (* x y z)))
$ (test 1 2 3)
6
$ (let ((x (lambda (x) (+x 1)))) (x 3)) 4
Note. lambda is the function definition keyword.

Control Structure
􏰉 if expression: three mandatory expressions – the condition, then, and else expressions
􏰉 comparison expression: >, <, = Control Structure: Grammar Note. (1 1) is a valid expression from grammar point of view, but, it will throw a semantic error. More on this later! Exercise: Lambda Expression Write some Lambda Expressions with if then else (if (= x 10) (let ((x 20)) ((lambda (y) (* y y)) x )) 0) Pair and List 1. pair: 2 tuple (fst, snd) 2. list: empty list, or 2 tuple 3. a list is a pair, a pair is not necessarily a list List and its built-in functions in FuncLang 􏰉 list: creating a list, e.g., (list 1 1 1 1 1) 􏰉 null?: check if a list is a null, returns #t if that argument is an emptylist else return #f 􏰉 car: get the first element of a pair, e.g., (car (list 11 1)) 􏰉 cdr: get the second element of a pair, e.g., (cdr (list 342, 331, 327)) 􏰉 cons: 􏰉 constructing a pair, e.g., (cons 2 3) (cons 541 (list 342)) 􏰉 lists can also be constructed by using the cons keyword, as is shown here: > (cons 1 (list)) (1)

Examples: list with functions

Examples: list and its built-in functions in FuncLang
$ (list 1 2 3) (1 2 3)
$ (cons 1 2) (1 2)
$ (cons 1 (list 2)) (1 2)
$ (define L (list 1 2 3))
$ (car L) 1
$ (cdr L) (2 3)

Examples: list and its built-in functions in FuncLang
$ (car (list))
funclang.Value$Null cannot be cast to funclang.Value$pairVal $ (cdr (list))
funclang.Value$Null cannot be cast to funclang.Value$pairVal $ (list)
$ (cdr (list 1))
()
$ (car (list 1)) 1
$ (null? (list)) #t

Grammar with List

Exercise: functions, list and control structure
Write programs with list, functions and control structures

Examples : all together
$(if (null? l) (car l) (cdr l)) $ (cdr (cdr (list 1 2 3))) (3)
$ (car (cdr (list 1 2 3)))
2
$ (cdr (cdr (cdr (list 1 2 3))))
()
$ (cdr (list))
funclang.Value$Null cannot be cast to funclang.Value$PairVal $ (car (list))
funclang.Value$Null cannot be cast to funclang.Value$PairVal $ (cdr (cdr (cdr (cdr (list 1 2 3)))))
funclang.Value$Null cannot be cast to funclang.Value$PairVal $ (cons 3 (list))
(3)
$ (define f (lambda (x) (* x x)))
$ (list 1 2 f)
(1 2 (lambda ( x ) (* x x )))
$ (list 1 2 (f 5))
(1 2 25)

Recursive Function
􏰉 Recursive function mirror the definition of the input data type

Define a function sum that sums the number 1 to n.
$ (define sum (lambda (n) (if (= n 1) 1 (+ n (sum (- n 1))))))
$ (sum 1) 1
$ (sum 2)
3
$ (sum 3) 6

FuncLang Programming Exercise
􏰉 Define a function that computes the factorial of a given integer n
􏰉 Define a function sumsquares that takes two integers as a parameter and computes the sum of square of numbers from the first number to the second number.

Solution
􏰉 (define fac (lambda (n) (if (= n 1) 1 (* n (fac (- n 1))))))
􏰉 $(definef(lambda(nm)(if(>nm)0(+(*nn)(f(+n1)m)))))
$ (f 0 2)
5
$ (f 1 2) 5
$ (f 2 3) 13

High Order Function – take function as an input
􏰉 a function that accepts a function as an argument or return a function as value
(define addthree (lambda (x)(+ x 3)))
(define applyonone (lambda (f) (f 1)))
$(applyonone addthree)
4
$(addthree applyonone) //error
$ (addthree (applyonone addthree)) 7
(define addtwovalues (lambda (x y) (+ x y))) $ (applyonone addtwovalues) //error
(define applyonetwo (lambda (f) (f 1 2)) $ (applyonetwo addtwovalues)
3

High Order Function – return a function
(lambda (c)
(lambda (x) c) )
( (lambda (c)
(lambda (x) c) )
1 )
( ( (lambda (c)
(lambda (x) c) )
1 ) 2)

High Order Function – using function to represent data structure and its operations
(define pair
(lambda (fst snd)
(lambda (op) (if op fst snd)
) )
)
(define apair (pair 3 4))
(define first (lambda (p) (p #t))) $ (first apair)
􏰉 what is apair? 􏰉 what is first?

High order function: problem solving
􏰉 parameterize functions: defining reusable algorithmic structures, e.g., a higher-order function that accepts an operation and a list and applies the operation on each element of the list.
􏰉 identify: what is high order function (given by the problem)? what is op used as paramaterized algorithms? what are the parameters of high order function that op will apply to? op will perform on which data structure and paramaters? element of a list? a list?
􏰉 high order function will (repeatedly) apply op on its other parameters
􏰉 if the high order function is recursive, what is the initial condition,
and what is the subproblem of n-1.
􏰉 high order function for data structures: paramaters are members, the operators, .e.g, getfirst, getsecond, on the data structure are op: a constructor for creating pairs, an observer for getting the first element of the pair, and another observer for getting the second element of the pair.

Exercise: High Order Function
Define a function filter with the signature: (define filter (lambda (test op lst ) …) ) The function takes two inputs, an operator test op that should be a single argument function that returns a boolean, and lst that should be a list of elements. The function outputs a list containing all the elements of ”lst” for which the test op function returned #t.
$ (define gt5? (lambda (x) (if (> x 5) #t #f))) $ ( filter gt5? ( list ))
()
$ ( filter gt5? ( list 1))
()
$ ( filter gt5? ( list 1 6))
(6)
$(filtergt5? (list1627))
(6 7)
$(filtergt5? (list162759)) (6 7 9)

Solution: High Order Function
􏰉 (define gt5? (lambda (x) (if (> x 5) #t #f)))
􏰉 (define filter (lambda (op l) (if (null? l) (list) (if (op (car l)) (cons
(car l) (filter op (cdr l))) (filter op (cdr l))))))
􏰉 // Try applying filter with similar function as gt5? (define iszero (lambda (x) (if (= x 0) #t #f)))

Currying
[the term Currying is from Haskell Curry] Model multiple argument lambda abstractions as a combination of single argument lambda abstraction
(define plus
(lambda (x y) (+ x y)))
(define plusCurry (lambda (x)
(lambda (y) (+ x y)
) )
)

Revisit Syntax
What is new? Funclang – Functions
􏰉 Lambda expression
􏰉 Call expression
􏰉 Function with a name
􏰉 High order function, including currying 􏰉 List and built-in functions
􏰉 cons 􏰉 list 􏰉 car 􏰉 cdr 􏰉 null?
􏰉 if cond truestmt falsestmt 􏰉 #t, #f
􏰉 < Exp Exp 􏰉 = Exp Exp 􏰉 < Exp Exp Language design decisions for functions 􏰉 Do we require a function name? or do we allow anonymous functions? (first-class function functions are variables of the function type) 􏰉 Do we require an explicit return? 􏰉 Do we allow to write a function in the function body (nested function)? 􏰉 Do we allow high order functions? (Consider C function pointers) 􏰉 Do we allow default values in the parameters? 􏰉 Do we support variant parameters? foo(int x, ...) 􏰉 An alternative syntax for CallExp: (LambdaExp Exp+) Should we perform syntactic or semantic checks to report an invalid expression (1 1)? 􏰉 There are errors that we cannot use CFG to check but only can check them in evaluators, e.g., checking the numbers of formal paramaters and actual parameters must be equal for a CallExp. How to extend the semantics for FuncLang? 􏰉 Any new types of values to be added? 􏰉 Semantic rules? 􏰉 How to implement it? New Values for FuncLang 􏰉 Lambda expression is function, it has values, and can be passed as parameters, return from a function and stored in the environment New Values for FuncLang: Implementation Evaluate a Lambda Expression Evaluate a Call Expression (define identity (lambda (x) x) ) $(identity i) Evaluate a Call Expression Dynamic Errors in FuncLang Errors that cannot be found using grammar rules: 􏰉 number of formal parameters and actual parameters do not match (context-sensitivity part of the language, cannot been find by the grammar) 􏰉 if exp (operator) does not return a function value Implementation: Evaluating a Call Expression Control Structure: Extending Value Control Structure: Semantic Rules Control Structure: Semantic Rules Semantics of List: Extending the Values Semantics for List Operations Note. exp 0 ... lval 1 exp 1 ... lval 2 ... exp n = val n Semantics for List Operations Review FuncLang: Function 􏰉 Abstraction, parameterize computations 􏰉 Lambda Expression, Call Expression 􏰉 Combine with Let and Define: functions are also variables 􏰉 if then else: Condition >, >, =
􏰉 list: (car, cdr, null?, cons, list)
Understanding of pair and list: List is a pair, pair is not a list
􏰉 syntax: CFG, semantic: operational
􏰉 recursive function, high order function, currying
􏰉 Values: NumVal, FunVal, PairVal, NullVal, BoolVal, UnitVal, Dynamic Errors