Lecture 5. FuncLang – Functions
Lecture 5. FuncLang – Functions
February 23, 2021
Overview
I FuncLang: writing programs in functional programming languages
I lambda expression
I recursion
I high-order functions
I build-in functions (list, pair)
I control structures
I Syntax
I Semantics
I Implementation
Abstraction in Programming Languages
I Variable in imperative programming languages
I fixed abstraction – you cannot change computation
I representing values
I Function (procedure, method):
I parameterization for computation
I you can reuse the functionality for different concrete input
I language features that can define a procedure and call a procedure
Lambda Expression
I Defining anonymous function
I Compare to ALGOL family languages: C, C++, Java … (syntax):
I not specify the name of the function
I formal parameter name only, no types precede or follow
I no explicit return is needed
I Compare to ALGOL family languages: C, C++, Java … (semantics):
Procedures and methods: proxy of the location of a section of code
I adjust the environment
I jump to the location
Lambda abstraction:
I generate runtime values
I 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
I if expression: three mandatory expressions – the condition, then, and
else expressions
I 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
I list: creating a list, e.g., (list 1 1 1 1 1)
I null?: check if a list is a null, returns #t if that argument is an
emptylist else return #f
I car: get the first element of a pair, e.g., (car (list 11 1))
I cdr: get the second element of a pair, e.g., (cdr (list 342, 331, 327))
I cons:
I constructing a pair, e.g., (cons 2 3) (cons 541 (list 342))
I 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
I 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
I Define a function that computes the factorial of a given integer n
I 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
I (define fac (lambda (n) (if (= n 1) 1 (* n (fac (- n 1))))))
I $ (define f (lambda (n m) (if (> n m) 0 (+ (* n n) (f (+ n 1) m)))))
$ (f 0 2)
5
$ (f 1 2)
5
$ (f 2 3)
13
High Order Function – take function as an input
I 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)
I what is apair?
I what is first?
High order function: problem solving
I 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.
I 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?
I high order function will (repeatedly) apply op on its other parameters
I if the high order function is recursive, what is the initial condition,
and what is the subproblem of n-1.
I 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)
$ ( filter gt5? ( list 1 6 2 7))
(6 7)
$ ( filter gt5? ( list 1 6 2 7 5 9))
(6 7 9)
Solution: High Order Function
I (define gt5? (lambda (x) (if (> x 5) #t #f)))
I (define filter (lambda (op l) (if (null? l) (list) (if (op (car l)) (cons
(car l) (filter op (cdr l))) (filter op (cdr l))))))
I // Try applying filter with similar function as gt5?
(define iszero (lambda (x) (if (= x 0) #t #f)))
Currying
[the term Currying is from ] 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
I Lambda expression
I Call expression
I Function with a name
I High order function, including currying
I List and built-in functions
I cons
I list
I car
I cdr
I null?
I if cond truestmt falsestmt
I #t, #f
I < Exp Exp
I = Exp Exp
I < Exp Exp
Language design decisions for functions
I Do we require a function name? or do we allow anonymous
functions? (first-class function functions are variables of the
function type)
I Do we require an explicit return?
I Do we allow to write a function in the function body (nested
function)?
I Do we allow high order functions? (Consider C function pointers)
I Do we allow default values in the parameters?
I Do we support variant parameters? foo(int x, ...)
I An alternative syntax for CallExp:
(LambdaExp Exp+)
Should we perform syntactic or semantic checks to report an invalid
expression (1 1)?
I 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?
I Any new types of values to be added?
I Semantic rules?
I How to implement it?
for FuncLang
I Lambda expression is function, it has values, and can be passed as
parameters, return from a function and stored in the environment
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:
I number of formal parameters and actual parameters do not match
(context-sensitivity part of the language, cannot been find by the
grammar)
I 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
I Abstraction, parameterize computations
I Lambda Expression, Call Expression
I Combine with Let and Define: functions are also variables
I if then else: Condition >, >, =
I list: (car, cdr, null?, cons, list)
Understanding of pair and list: List is a pair, pair is not a list
I syntax: CFG, semantic: operational
I recursive function, high order function, currying
I Values: NumVal, FunVal, PairVal, NullVal, BoolVal, UnitVal,
Dynamic Errors