Transcript Document
FUNCTIONAL PROGRAMMING IN ERLANG Christian Schulte [email protected] Software and Computer Systems School of Information and Communication Technology KTH – Royal Institute of Technology Stockholm, Sweden ID1218 Lecture 02 2009-10-28 2 Reminder & Overview ID1218, Christian Schulte L02, 2008-10-29 Functional Programming 3 Compute by evaluating functions returning results Techniques recursion with last-call-optimization pattern matching list processing higher-order programming accumulators ID1218, Christian Schulte L02, 2008-10-29 Functional Programming in Erlang 4 Data types: values primitive: integers, floats, atoms compound: tuples, lists Programs consist of functions identified by atom and arity defined by several clauses arguments are passed by value clauses are evaluated evaluation returns value ID1218, Christian Schulte L02, 2008-10-29 Function Definition 5 Function defined by several clauses clauses separated by ; last clause terminated by . variable scope is per clause (anonymous variable _) Clause consists of head and body separated by -> head can contain guard after when clauses tried in textual order until matching clause is found (pattern matches and guard is true) Guards: tests, comparisons, conjunction, disjunction ID1218, Christian Schulte L02, 2008-10-29 Program Organization 6 Programs consists of several modules Module are named export functions import other modules Function calls either locally defined or imported functions or functions qualified by module name ID1218, Christian Schulte L02, 2008-10-29 Overview 7 Introduction to Erlang second look: lists and tuples, pattern matching third look: what do we need to understand How do Erlang programs compute make programs simple how exactly does computation proceed Next lecture accumulators higher-order programming ID1218, Christian Schulte L02, 2008-10-29 8 A Second Look ID1218, Christian Schulte L02, 2008-10-29 Tuples 9 {} {1,a,2} 1 a 2 Combine several values here: 1, a, 2 position is significant! ID1218, Christian Schulte L02, 2008-10-29 Lists 10 A list contains a sequence of elements A list is the empty list [], or consists of a cons (or list pair) with head and tail head contains an element tail contains a list ID1218, Christian Schulte L02, 2008-10-29 An Example List 11 [|] [|] | a [|] | b After evaluation of c [a|[b|[c|[]]]] Can also be written as [a,b,c] [a|[b,c]] [] [a,b|[c|[]]] ID1218, Christian Schulte L02, 2008-10-29 Head And Tail 12 The head and tail can be accessed by builtin functions (BIFs) hd/1 and tl/1 hd([X|Xr]) evaluates to X tl([X|Xr]) evaluates to Xr ID1218, Christian Schulte L02, 2008-10-29 Example of Head and Tail 13 hd([a,b,c]) evaluates to a tl([a,b,c]) evaluates to [b,c] hd(tl(tl([a,b,c]))) evaluates to c Draw the trees! ID1218, Christian Schulte L02, 2008-10-29 How to Process Lists 14 Given: list of integers Wanted: sum of its elements implement function sum Inductive definition over list structure Sum of empty list is 0 Sum of non-empty list Xs is hd(Xs) + sum(tl(Xs)) ID1218, Christian Schulte L02, 2008-10-29 Sum of a List 15 sum(Xs) when Xs==[] -> 0; sum(Xs) -> hd(Xs)+sum(tl(Xs)). ID1218, Christian Schulte L02, 2008-10-29 General Method 16 Lists are processed recursively base case: list is empty ([]) inductive case: list is cons access head, access tail Powerful and convenient technique pattern matching matches patterns of values and provides access to fields of compound data structures ID1218, Christian Schulte L02, 2008-10-29 Sum with Pattern Matching 17 sum([]) -> 0; sum([X|Xr]) -> X+sum(Xr). ID1218, Christian Schulte L02, 2008-10-29 Pattern Matching 18 A pattern is constructed like a value but also allows variables in the pattern A pattern matches a value, if the types agree (tuple matches tuple, list matches list, …) for tuples, the arity (number of fields must agree) the values agree When a pattern matches, the variables are assigned to the matched values ID1218, Christian Schulte L02, 2008-10-29 Pattern Matching 19 Can be used with the assignment operator = For example {[X|Xr],4,{A,B}} = {[1],4,{b,a}} matches with X=1, Xr=[], A=b, B=a But [] does not match [_|_], … ID1218, Christian Schulte L02, 2008-10-29 Single Assignment Variables 20 A variable can be assigned only to the same value X=[1,2],X=[1,2] otherwise runtime error Major difference to Java, C, C++, … variables change over time also: stateful variables and programs Single assignment variables simplify reasoning over programs concurrent programming ID1218, Christian Schulte L02, 2008-10-29 Length of a List 21 Inductive definition length of empty list is 0 length of cons is 1 + length of tail len([]) -> 0; len([_|Xr]) -> 1+len(Xr). ID1218, Christian Schulte L02, 2008-10-29 Case Expression 22 len(Xs) -> case Xs of [] -> 0; [_|Xr] -> 1+len(Xr) end. Like new function defined with several clauses Functions with a single clause are sufficient Scope rule: if variable X introduced in clause and used after end X must be introduced in all clauses ID1218, Christian Schulte L02, 2008-10-29 If Expression 23 fac(N) -> if N==0 -> 1; N>0 -> N*fac(N-1) end. Scoping as with case ID1218, Christian Schulte L02, 2008-10-29 Look Two: Summary 24 List is either empty or cons with head and tail List processing is recursive processing Useful for this is pattern matching Clauses can be replaced by case expression ID1218, Christian Schulte L02, 2008-10-29 25 A Third Look ID1218, Christian Schulte L02, 2008-10-29 A Better Length? 26 len(Xs) -> len(Xs,0). len([],N) -> N; len([_|Xr],N) -> len(Xr,N+1). Two different functions: len/1 and len/2 Better, because much faster (but it has one more argument?) uses less memory (what memory? heap? stack?) ID1218, Christian Schulte L02, 2008-10-29 Appending Two Lists 27 app([],Ys) -> Ys; app([X|Xr],Ys) -> [X|app(Xr,Ys)]. How much memory needed? Stack space… in the length of the first list… Why? ID1218, Christian Schulte L02, 2008-10-29 Reversing a List 28 rev([]) -> []; rev([X|Xr]) -> app(rev(Xr),[X]). How much time needed? grows quadratic with the length of the input list… why? how can one find out? ID1218, Christian Schulte L02, 2008-10-29 Reversing a List: Better 29 rev(Xs) -> rev(Xs,[]). rev([],Ys) -> Ys; rev([X|Xr],Ys) -> rev(Xr,[X|Ys]). How much time needed? grows only linear with the length of the input list… how does this work? can we do that mechanically? The same as len/2… ID1218, Christian Schulte L02, 2008-10-29 30 How Programs Compute The MiniErlang Machine ID1218, Christian Schulte L02, 2008-10-29 Erlang Semantics 31 Semantics will define how programs compute operational semantics abstract machine (implementation blueprint) Strategy define semantics for very simple Erlang programs captures the essence of how programs compute explains in particular how much stack space is needed ID1218, Christian Schulte L02, 2008-10-29 The MiniErlang Machine 32 Executes MiniErlang programs Uses two stacks expression stack: what needs to be evaluated value stack: was has already been evaluated Starts with a single expression to be evaluated Finishes with a single value (the result) the value stack is empty all expressions have been evaluated Executes expressions and instructions instructions perform operations after all required arguments have been evaluated ID1218, Christian Schulte L02, 2008-10-29 Roadmap: MiniErlang 33 What to compute with MiniErlang What are the results MiniErlang Values What are the instructions for expressions and programs compound value construction and function call How are functions called parameters are passed by substitution considers only matching clauses clauses have patterns (we ignore guards) ID1218, Christian Schulte L02, 2008-10-29 34 Evaluating Values ID1218, Christian Schulte L02, 2008-10-29 MiniErlang Values 35 A MiniErlang value is an integer or a list other values are similar In short notation V := int | [] | [ V1 | V2 ] known as BNF notation: discussed later so: values are referred to by V (possibly subscripted) can be: any integer, the empty list, a cons consisting of two values V1 and V2 ID1218, Christian Schulte L02, 2008-10-29 MiniErlang Expressions 36 A MiniErlang expression is a value, a variable, or a function call E := int | [] | [ E1 | E2 ] | X | F(E1,…, En) expressions referred to by E variables referred to by X function names referred to by F ID1218, Christian Schulte L02, 2008-10-29 MiniErlang Machine 37 MiniErlang machine Es ; Vs → Es’ ; Vs’ transforms a pair (separated by ;) of expression stack Es and value stack Vs into a new pair of expression Initial configuration: expression stack Es’ and value stack Vs’ we want to evaluate on expression stack Final configuration: single value as result on value stack ID1218, Christian Schulte L02, 2008-10-29 Stacks 38 We write stacks as X1 … Xn Xr top of stack n-th element more elements Xr empty stack X1 Xn Pushing X to stack Xr: X Xr Popping X from stack X Xr: Xr ID1218, Christian Schulte L02, 2008-10-29 MiniErlang Execution Idea 39 Simple case: an integer evaluates to itself the result of an integer expression… …is an integer value MiniErlang machine i Er ; Vs → Er ; i Vs if the expression stack has the integer i as top of stack… execution yields: the expression i is popped from the expression stack and pushed on to the value stack same for empty list ID1218, Christian Schulte L02, 2008-10-29 MiniErlang Instruction Idea 40 How to evaluate a list expression [ E1 | E2 ] first evaluate E1 , to a value V1, … then evaluate E2 , to a value V2, … then construct a new value [ V1 | V2 ] Use an instruction that says: build a list makes the assumption that values needed are on the value stack execution will pop two values, push a new list value when [ E1 | E2 ] is executed, E1 and E2 and the instruction CONS are pushed on the expression stack ID1218, Christian Schulte L02, 2008-10-29 Evaluating a List Expression 41 Evaluate a list expression [E1|E2]Er ; Vs → E1E2CONSEr ; Vs Execute a CONS instruction CONSEr ; V1V2Vs → Er ; [V2|V1]Vs ID1218, Christian Schulte L02, 2008-10-29 Example 42 We want to evaluate the expression [1|[]] (that is, just the list [1]) Start configuration of our machine [1|[]] ; expression stack: empty value stack: [1|[]] What should be the end configuration: ; [1|[]] empty expression stack: result on value stack: [1|[]] ID1218, Christian Schulte L02, 2008-10-29 Let’s Do It! 43 [1|[]] ; → … [E1|E2]Er ; Vs → E1E2CONSEr ; Vs ID1218, Christian Schulte L02, 2008-10-29 Let’s Do It! 44 [1|[]] ; → 1 []CONS ; → … i Er ; Vs → ID1218, Christian Schulte Er ; i Vs L02, 2008-10-29 Let’s Do It! 45 [1|[]] ; → 1 []CONS ; → []CONS ; 1 → … i Er ; Vs → ID1218, Christian Schulte Er ; i Vs L02, 2008-10-29 Let’s Do It! 46 [1|[]] ; → 1 []CONS ; → []CONS ; 1 → CONS ; []1 → … CONSEr ; V1V2Vs → Er ; [V2|V1]Vs ID1218, Christian Schulte L02, 2008-10-29 Let’s Do It! 47 [1|[]] ; → 1 []CONS ; → []CONS ; 1 → CONS ; []1 → ; [1|[]] ID1218, Christian Schulte L02, 2008-10-29 Summary 48 MiniErlang values expressions MiniErlang machine operates on expression and value stack evaluates topmost expression on expr stack executes topmost instruction on expr stack Start state: single expr on expr stack Final state: single value on value stack ID1218, Christian Schulte L02, 2008-10-29 49 Summary & Homework ID1218, Christian Schulte L02, 2008-10-29 Summary: MiniErlang 50 Stack-based operational semantics expressions, values, patterns, substitutions, matching What did we learn how to describe how programs compute semi-gentle introduction to semantics better understanding of Erlang programs blueprint of a stack-based implementation What will we use it for tool for analyzing how Erlang programs compute ID1218, Christian Schulte L02, 2008-10-29 Homework 51 Take some expressions execute them by hand ID1218, Christian Schulte L02, 2008-10-29