編程語(yǔ)言的設(shè)計(jì)原理PPT課件

1、編程語(yǔ)言的設(shè)計(jì)原理Design Principles of Programming LanguagesZhenjiang Hu, Yingfei Xiong, Haiyan Zhao, 胡振江 熊英飛 趙海燕Peking University, Spring, 2019Chapter 0+: ImplementationA quick tour of OCamlUtilities in Ocaml systemAn Implementation for Arithmetic Expression A Quick Tour of OCaml Part IResources Overview ht

2、tp://learn/tutorials/basics.html Tutorials /learn/tutorials/ Download http:/caml.inria.fr/download.en.html2020/2/26Design Principle of Programming Language4 Why OCaml? What we learn in this course, is mostly conceptual and mathematical. However: Some of the ideas are easier t

3、o grasp if you can see them work; Experimenting with small implementations of programming languages is an excellent way to deepen intuitions.OCaml language is chosen for these purposes General programming language with an emphasis on expressiveness and safety. 2020/2/26Design Principle of Programmin

4、g Language5OCaml used in the CourseConcentrates just on the “core” of the language, ignoring most of its features, like modules or objects. For some of the ideas in the course are easier to grasp if you can “see them work” experimenting with small implementations of programming languages is an excel

5、lent way to deepen intuitions2020/2/26Design Principle of Programming Language6Quick fact sheet Some facts about Caml (Categorical Abstract Machine Language ) Created in 1987 by INRIA - Frances national research institute for computer science (Haskell 1.0 is from 1990) Originated from ML but was int

6、ended for in house projects of INRIA Short timeline: Caml (1987) Caml Light (1990) OCaml (1995) Currently at version 4.09.0 (released on 2019-09-18)2020/2/26Design Principle of Programming Language7OCamlA large and powerful language (safety and reliability ) the most popular variant of the Caml lang

7、uage Collaborative Application Markup Language ? (協(xié)作應(yīng)用程序標(biāo)記語(yǔ)言) extending the core Caml language with a fully-fledged object-oriented layer powerful module system a sound, polymorphic type system featuring type inference. a functional programming language i.e., a language in which the functional progr

8、amming style is the dominant idiomOCaml system is open source software2020/2/26Design Principle of Programming Language8Functional ProgrammingFunctional style can be described as a combination of persistent data structures (which, once built, are never changed) recursion as a primary control structu

9、re heavy use of higher-order functions (that take functions as arguments and/or return functions as results) Imperative languages, by contrast, emphasize mutable data structures looping rather than recursion first-order rather than higher-order programming (though many object-oriented design pattern

10、s involve higher-order idioms e.g., Subscribe/Notify, Visitor, etc. .2020/2/26Design Principle of Programming Language9The Top LevelOcaml, as most functional programming implementation, provides both an interactive top level , and a compiler that produces standard executable binaries. The top level

11、provides a convenient way of experimenting with small programs.2020/2/26Design Principle of Programming Language10The Top LevelThe mode of interacting with the top level is typing in a series of expressions; Ocaml evaluates them as they are typed, and displays the results (and their types). In the i

12、nteraction , lines beginning with # are inputs lines beginning with - are the systems responses. Note that inputs are always terminated by a double semicolon ;2020/2/26Design Principle of Programming Language11ExpressionsOCaml is an expression language. A program is an expression. The “meaning” of p

13、rogram is the value of the expression.# 16 + 18;- : int = 34# 2*8 + 3*6;- : int = 34Every expression has exactly one type (no pure command, even assignment, unitunit) When an expression is evaluated, one of 4 things may happen:1. evaluate to a value of the same type as the expression.2. raise an exc

14、eption (discussed later)3. not terminate4. exit.2020/2/26Design Principle of Programming Language12ExpressionsWhat will happen? # if 1 2 then 1 else 1.6; # if 1 = 3;- : bool = truenotnot is a unary operation on booleans# not (5 = 10);- : bool = false# not (2 = 2);- : bool = false2020/2/26Design Prin

15、ciple of Programming Language16Conditional expressionsThe result of the conditional expression if B then E1 else E2 if B then E1 else E2 is either the result of E1E1 or that of E2E2, depending on whether the result of B B is true or false.# if 3 4 then 7 else 100;- : int = 7 # if 3 int = # cube 9;-

16、: int = 729We call x the parameter of the function cube; the expression x*x*x is its body. The expression cube 9 is an application of cube to the argument 9. ( How about C/C+?)2020/2/26Design Principle of Programming Language21Functions# let cube (x: int) = x*x*x;val cube : int - int = # cube 9;- :

17、int = 729Here, int-int (pronounced “int arrow int”) indicates that cube is a function that should be applied to an integer argument and that returns an integer. Note that OCaml responds to a function declaration by printing just as the functions value. The precedence of function application is highe

18、r than most operators.2020/2/26Design Principle of Programming Language22FunctionsA function with two parameters:The type printed for sumsq is intint-intint-intint, indicating that it should be applied to two integer arguments and yields an integer as its result. Note that the syntax for invoking fu

19、nction declarations in OCaml is slightly different from languages in the C/C+/Java family: use cube 3 and sumsq 3 4 rather than cube(3) and sumsq(3, 4), since multiple-parameter functions are implemented as nested functions (called Currying)# let sumsq (x: int) (y: int) = x*x + y*y;val sumsq : int -

20、 int - int = # sumsq 3 4;- : int = 252020/2/26Design Principle of Programming Language23Recursive functionsWe can translate inductive definitions directly into recursive functions.# let recrec sum(n:int) = if n = 0 then 0 else n + sum(n-1);val sum : int - int = # sum 6;- : int = 21# let rec fact(n:i

21、nt) = if n = 0 then 1 else n * fact(n-1);val fact : int - int = # fact 6;- : int = 720The recrec after the letlet tells Ocaml that this is a recursive function one that needs to refer to itself in its own body.What will happen if dropping the rec ?2020/2/26Design Principle of Programming Language24R

22、ecursive functions# let rec power k x = if k = 0 then 1.0 else x *. (power (k-1) x) ;val power : int - float - float = # power 5 2.0; ; -: float = 32# let b_power k x = (float_of_int k) *. x;val b_power : int - float - float = # let b_power k x = if k = 0 then 1.0 else x *. (b_power (k-1) x) ;val b_

23、power : int - float - float = # b_power 5 2.0; ; -: float = ? -: float = 162020/2/26Design Principle of Programming Language25Recursive functions: Making changeAnother example of recursion on integer arguments: Suppose a bank has an “infinite” supply of coins (pennies, nickles, dimes, and quarters,

24、and silver dollars), and it has to give a customer a certain sum. How many ways are there of doing this?For example, there are 4 ways of making change for 12 cents: 12 pennies 1 nickle and 7 pennies 2 nickles and 2 pennies 1 dime and 2 penniesWe want to write a function change that, when applied to

25、12,returns 4.2020/2/26Design Principle of Programming Language26Recursive functions: Making change Lets first consider a simplified variant of the problem where the bank only has one kind of coin: pennies.In this case, there is only one way to make change for a given amount: pay the whole sum in pen

26、nies!# (* No. of ways of paying a in pennies *)let rec changeP (a: int) = 1;That wasnt very hard. Note: Comments starts with (* and end with *)2020/2/26Design Principle of Programming Language27Recursive functions: Making change Now suppose the bank has both nickels and pennies.If a is less than 5 t

27、hen we can only pay with pennies. If not, we can do one of two things: Pay in pennies; we already know how to do this. Pay with at least one nickel. The number of ways of doing this is the number of ways of making change (with nickels and pennies) for a-5.# (* No. of ways of paying in pennies and ni

28、ckels *)let rec changePN (a:int) = if a 5 then changeP aelse changeP a + changePN (a-5);2020/2/26Design Principle of Programming Language28Recursive functions: Making changeContinuing the idea for dimes and quarters:# (* . pennies, nickels, dimes *)let rec changePND (a:int) =if a 10 then changePN ae

29、lse changePN a + changePND (a-10);# (* . pennies, nickels, dimes, quarters *)let rec changePNDQ (a:int) =if a 25 then changePND aelse changePND a + changePNDQ (a-25);2020/2/26Design Principle of Programming Language29Recursive functions: Making change# (* Pennies, nickels, dimes, quarters, dollars *

30、)let rec change (a:int) =if a int list = # add123 5; 6; 7;- : int list = 1; 2; 3; 5; 6; 7# add123 ;- : int list = 1; 2; 32020/2/26Design Principle of Programming Language35Constructing ListsAny list can be built by “consing” its elements together: In fact, e1; e2; . . . ; en is simply a shorthand fo

31、r e1 : e2 : . . . : en : Note that, when omitting parentheses from an expression involving several uses of :, we associate to the right i.e., 1:2:3: means the same thing as 1:(2:(3:) By contrast, arithmetic operators like + and - associate to the left: 1-2-3-4 means (1-2)-3)-4.# 1 : 2 : 3 : 2 : 1 :

32、; : int list = 1; 2; 3; 2; 12020/2/26Design Principle of Programming Language36Taking Lists ApartOCaml provides two basic operations for extracting the parts of a list (i.e., deconstruction). List.hd (pronounced “head”) returns the first element of a list.# List.hd 1; 2; 3;- : int = 1 List.tl (prono

33、unced “tail”) returns everything but the first element.# List.tl 1; 2; 3;- : int list = 2; 32020/2/26Design Principle of Programming Language37More list examples# List.tl (List.tl 1; 2; 3);- : int list = 3# List.tl (List.tl (List.tl 1; 2; 3);- : int list = # List.hd (List.tl (List.tl 1; 2; 3);- : in

34、t = 32020/2/26Design Principle of Programming Language38Recursion on listsLots of useful functions on lists can be written using recursion. Heres one that sums the elements of a list of numbers:# let rec listSum (l: int list) =if l = then 0else List.hd l + listSum (List.tl l);val listSum : int list

35、- int = # listSum 5; 4; 3; 2; 1;- : int = 152020/2/26Design Principle of Programming Language39Consing on the right# let rec snoc (l: int list) (x: int) =if l = then x:else List.hd l : snoc(List.tl l) x;val snoc : int list - int - int list = # snoc 5; 4; 3; 2 1;- : int list = 5; 4; 3; 2; 12020/2/26D

36、esign Principle of Programming Language40A better rev# (* Adds the elements of l to res in reverse order *)let rec revaux (l: int list) (res: int list) =if l = then reselse revaux (List.tl l) (List.hd l : res);val revaux : int list - int list - int list = # revaux 1; 2; 3 4; 5; 6;- : int list = 3; 2

37、; 1; 4; 5; 6# let rev (l: int list) = revaux l ;val rev : int list - int list = 2020/2/26Design Principle of Programming Language41Tail recursionIt is usually fairly easy to rewrite a recursive function in tail-recursive style. e.g., the usual factorial function is not tail recursive (because one mu

38、ltiplication remains to be done after the recursive call returns): # let rec fact (n:int) =if n = 0 then 1else n * fact(n-1);It can be transformed into a tail-recursive version by performing the multiplication before the recursive call and passing along a separate argument in which these multiplicat

39、ions “accumulate”: # let rec factaux (acc:int) (n:int) =if n = 0 then accelse factaux (acc*n) (n-1);# let fact (n:int) = factaux 1 n;2020/2/26Design Principle of Programming Language42Basic Pattern MatchingRecursive functions on lists tend to have a standard shape: test whether the list is empty, an

40、d if it is not do something involving the head element and the tail.# let rec listSum (l:int list) =if l = then 0else List.hd l + listSum (List.tl l);OCaml provides a convenient pattern-matching construct that bundles the emptiness test and the extraction of the head and tail into a single syntactic

41、 form:# let rec listSum (l: int list) =match l with - 0 |x:y - x + listSum y;2020/2/26Design Principle of Programming Language43Basic Pattern MatchingPattern matching can be used with types other than lists, like other aggregate types, and even simple types. For example, here it is used on integers:

42、# let rec fact (n:int) = match n with 0 - 1 | _ - n * fact(n-1);here _ pattern is a wildcard that matches any value.2020/2/26Design Principle of Programming Language44Complex PatternsThe basic elements (constants, variable binders, wildcards, , :, etc.) may be combined in arbitrarily complex ways in

43、 match expressions:# let silly l = match l with _; _; _ - three elements long | _:x:y:_:_:rest - if x y then foo else bar | _ - dunno;val silly : a list - string = # silly 1; 2; 3;- : string = three elements long# silly 1; 2; 3; 4;- : string = dunno# silly 1; 2; 3; 4; 5;- : string = bar2020/2/26Desi

44、gn Principle of Programming Language45Type InferenceOne pleasant feature of OCaml is its powerful type inference mechanism that allows the compiler to calculate the types of variables from the way in which they are used.The compiler can tell that fact takes an integer argument because n is used as a

45、n argument to the integer * and - functions.# let rec fact n = match n with0 - 1 | _ - n * fact (n - 1);val fact : int - int = 2020/2/26Design Principle of Programming Language46Type InferenceSimilarly:# let rec listSum l = match l with - 0 | x:y - x + listSum y;val listSum : int list - int = 2020/2

46、/26Design Principle of Programming Language47Polymorphism (first taste) The a in the type of length, pronounced “alpha,” is a type variable standing for an arbitrary type. The inferred type tells us that the function can take a list with elements of any type (i.e., a list with elements of type alpha

47、, for any choice of alpha).# let rec length l = match l with - 0 | _:y - 1 + length y;val length : a list - int = 2020/2/26Design Principle of Programming Language48TuplesItems connected by commas are “tuples.” (The enclosing parenthesis are optional)# age, 38;- : string * int = age, 38# professor,

48、age, 33;- : string * string * int = professor, age, 33# (children, bob;ted;alice);- : string * string list = children, bob; ted; alice# let g (x, y) = x * y;val g : int * int - int = 2020/2/26Design Principle of Programming Language49Tuples are not listsDo not confuse them!# let tuple = cow, dog, sh

49、eep;val tuple : string * string * string = cow, dog, sheep# List.hd tuple;Error: This expression has type string * string * string but an expression was expected of type a list# let tup2 = 1, cow;val tup2 : int * string = 1, cow# let l2 = 1; cow;Error: This expression has type string but an expressi

50、on was expected of type int2020/2/26Design Principle of Programming Language50Tuples and pattern matchingTuples can be “deconstructed” by pattern matching, like list:# let lastName name = match name with (n, _, _) - n;# lastName (“Zhao, “Haiyan, “PKU);- : string = “Zhao2020/2/26Design Principle of P

51、rogramming Language51Example: Finding words *Suppose we want to take a list of characters and return a list of lists of characters, where each element of the final list is a “word” from the original list.# split t;h;e; ;b;r;o;w;n; ;d;o;g;- : char list list = t; h; e; b; r; o; w; n; d; o; g(Character

52、 constants are written with single quotes.)2020/2/26Design Principle of Programming Language52An implementation of splitNote the use of both tuple patterns and nested patterns. The operator is shorthand for List.append.# let rec loop w l = match l with - w | ( :ls) - w : (loop ls) | (c:ls) - loop (w

53、 c) ls;val loop : char list - char list - char list list = # let split l = loop l;val split : char list - char list list = 2020/2/26Design Principle of Programming Language53Aside: Local function definitionsThe loop function is completely local to split: there is no reason for anybody else to use it

54、 or even for anybody else to be able to see it! It is good style in OCaml to write such definitions as local bindings:# let split l = let rec loop w l =match l with - w | ( :ls) - w : (loop ls) | (c:ls) - loop (wc) ls in loop l;2020/2/26Design Principle of Programming Language54Local function defini

55、tionsIn general, any let definition that can appear at the top level# let . ;# e;# let . in e;can also appear in a let . in . let . in . form2020/2/26Design Principle of Programming Language55A Better Split ? Our split function worked fine for the examples we tried it on so far. But here are some ot

56、her tests:# split a; ; ; b;- : char list list = a; ; b# split a; ;- : char list list = a; Could we refine split so that it would leave out these spurious empty lists in the result?2020/2/26Design Principle of Programming Language56 A Better SplitSure. First rewrite the pattern match a little (withou

57、t changing its behavior)# let split l = let rec loop w l =match w, l with _, - w | _, ( :ls) - w : (loop ls) | _, (c:ls) - loop (wc) ls in loop l;2020/2/26Design Principle of Programming Language57 A Better SplitThen add a couple of clauses:# let better_split l = let rec loop w l =match w, l with ,

58、- | _, - w | , ( :ls) - loop ls | _, ( :ls) - w : (loop ls) | _, (c:ls) - loop (wc) ls in loop l;# better_split a; b; ; ; c; ; d; ;- : char list list = a; b; c; d# better_split a; ;- : char list list = a# better_split ; ;- : char list list = 2020/2/26Design Principle of Programming Language58Basic E

59、xceptionsOCamls exception mechanism is roughly similar to that found in, for example, Java. It begins by defining an exception:# let rec fact n = if n e_1 |p_2 - e_2 | p_n - e_nExceptions are used in Ocaml as a control mechanism, either to signal errors, or to control the flow of execution. When an

60、exception is raised, the current execution is aborted, and control is thrown to the most recently entered active exception handler.2020/2/26Design Principle of Programming Language60Defining New Types of Data2020/2/26Design Principle of Programming Language61Predefined types2020/2/26Design Principle