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