Lecture 4: Functions

목차

 

Learning Objectives

- Explain what a higher-order function is; motivate usefulness

- Explain what a lambda(λ) is; motivate usefulness

- Explain the difference between val and def in Scala

- Write simple programs involving lambdas

- Explain how function application works by substituting parameters for arguments

- Execute simple programs involvnig lambdas

 

 

Why Higher-Order Functions?

Higher-Order Functions: A function for which one of the parameters is a function itself (e.g. map, fold)

Powerful and concise patterns of programming

There are in all modern programming languages

Functions are a framework for analyzing and understanding a wide range of programming language constructs

 

 

Lambdas (λs)

Lambdas are function definitions that is not bound to an identifier.

Lambdas are useful when passed to higher order functions, such as map and filter.

→ Lambdas can also be directly used without the need to declare them in advance.

→ Lambdas can also be passed to methods as input parameters and used inside.

 

 

Scala Syntax

 

 

Generic Operations Over Lists

 

 

 

Generic Operations Over Lists: Fold

 

 

 

Functions in Scala

Syntax

Lambda expression: x => x

Function application: f(x)

 

Example

 

 

 

Semantics

Lambda expression constructs a function value

Invoking functions like f(e) evaluate by:

- Evaluating f to a function value

- Evaluating e to a value v

- Executing f with all occurrences of its parameter replaced by the corresponding value (substitution)

 

 

Functions vs Variables (defs vs. vals)

 

→ 즉, val은 computed at definition time but def is computed each time we call it.

 

 

Functions in Paret

Functions and Function Application

 

 

 

Bindings (/ Variables) and Identifiers

let allows us to name things

Let: Programming abstraction which allows one to bind a particular value to a particular name. With (basic) let, bindings defined together in one let are not allowed to refer to each other. Let can be implemented using functions and function application.

 

 

 

Syntax 

 

 

 

 

 

1. ID does not have a parenthesis so it does not parse

2. hello Parses, it's IdC in the context-free syntax

3. (1 2) parses because it's AppC so it's in the syntax/grammar

4. ( (1 2)  3) parses because it's two nested AppC.

5. (let  (f  f)  f) parses because it's in the LetC and Expressions can be an IdC so it parses (in the gramamar)

6. (λ  (x  y)  (+  x  y) does not parse because in FdC, there should be only one ID, not two.

7. Parses  → 우선 LetC로 시작. 그리고 (<ID>  <Expr>)이 들어가는데, 여기서 <ID>는 f, 그리고 <Expr>은 (λ  (x)  (+  x  1))가 된다. 그리고 그 다음에  <Expr>이 필요한데 이거는 AppC인, (f  2)가 된다. 따라서 parse.

8. Parses →  우선 AppC로 시작. AppC는 (<Expr>  <Expr>) 이 들어오는데 첫 <Expr>은 FdC이고 두 번째는 IdC인 2가 된다. 따라서 parse.