编程语言的设计原理 Design Principles of Programming Languages Zhenjiang Hu, Yingfei Xiong, Haiyan Zhao, 胡振江 熊英飞 赵海燕 Peking University, Spring, 2014 1 Chapter 0+: Implementation A quick tour of OCaml Utilities in Ocaml system An Implementation for Arithmetic Expression A Quick Tour of OCaml Resources • Overview – http://ocaml.org/learn/tutorials/basics.html • Tutorials – http://ocaml.org/learn/tutorials/ • Download – http://caml.html Why Ocaml? The material in this course is mostly conceptual and mathematical. However: – Some of the ideas are easier to 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 OCaml • A large and powerful language (safety and reliability ) – the most popular variant of the Caml language • Categorical Abstract Machine Language(分类抽象机语言) • Collaborative Application Markup Language(协作应用程序标记语言) – 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., a language in which the functional programming style is the dominant idiom • OCaml system is open source software Functional Programming • Functional style can be described as a combination of. – persistent data structures (which, once built, are never changed) – recursion as a primary control structure – 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 patterns involve higher-order idioms—e., Subscribe/Notify, Visitor, etc.) OCaml used in the Course • Concentrates 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 excellent way to deepen intuitions The Top Level • OCaml provides both an interactive top level and a compiler that produces standard executable binaries. – The top level provides a convenient way of experimenting with small programs. • The 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 interaction , – lines beginning with # are inputs – lines beginning with - are the system’s responses. – Note that inputs are always terminated by a double semicolon ;; Expressions OCaml is an expression language. A program is an expression. The “meaning” of the program is the value of the expression.
# 16 + 18;; - : int = 34 # 2*8 + 3*6;; - : int = 34 Giving things names The let construct gives a name to the result of an expression so that it can be used later. # let inchesPerMile = 12*3*1760;; val inchesPerMile : int = 63360 # let x = 1000000 / inchesPerMile;; val x : int = 15 Functions # let cube (x:int) = x*x*x;; val cube : int -> int = <fun> # cube 9;; - : int = 729 • We 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. • The type printed by OCaml, 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 <fun> as the function’s “value. Functions A function with two parameters: # let sumsq (x:int) (y:int) = x*x + y*y;; val sumsq : int -> int -> int = <fun> # sumsq 3 4;; - : int = 25 The type printed for sumsq is int->int->int, indicating that it should be applied to two integer arguments and yields an integer as its result. Note that the syntax for invoking function 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). Type boolean There are only two values of type boolean: true and false.
Comparison operations return boolean values. # 1 = 2;; - : bool = false # 4 >= 3;; - : bool = true not is a unary operation on booleans # not (5 <= 10);; - : bool = false # not (2 = 2);; - : bool = false Conditional expressions The result of the conditional expression if B then E1 else E2 is either the result of E1 or that of E2, depending on whether the result of B is true or false. # if 3 < 4 then 7 else 100;; - : int = 7 # if 3 < 4 then (3 + 3) else (10 * 10);; - : int = 6 # if false then (3 + 3) else (10 * 10);; - : int = 100 # if false then false else true;; - : bool = true Recursive functions We can translate inductive definitions directly into recursive functions. # let rec sum(n:int) = if n = 0 then 0 else n + sum(n-1);; val sum : int -> int = <fun> # sum(6);; - : int = 21 # let rec fact(n:int) = if n = 0 then 1 else n * fact(n-1);; val fact : int -> int = <fun> # fact(6);; - : int = 720 The rec after the let tells OCaml this is a recursive function — one that needs to refer to itself in its own body.
Recursive functions: Making change Another example of recursion on integer arguments: Suppose you are a bank and therefore have an “infinite” supply of coins (pennies, nickles, dimes, and quarters, and silver dollars), and you have 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 pennies We want to write a function change that, when applied to 12, returns 4. Recursive functions: Making change To get started, let’s 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 pennies! # (* No.
of ways of paying a in pennies *) let rec changeP (a:int) = 1;; That wasn’t very hard. Recursive functions: Making change Now suppose the bank has both nickels and pennies. If a is less than 5 then 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. of ways of paying in pennies and nickels *) let rec changePN (a:int) = if a < 5 then changeP a else changeP a + changePN (a-5); Recursive functions: Making change Continuing the idea for dimes and quarters: # (*. pennies, nickels, dimes *) let rec changePND (a:int) = if a < 10 then changePN a else changePN a + changePND (a-10);; # (*.
pennies, nickels, dimes, quarters *) let rec changePNDQ (a:int) = if a < 25 then changePND a else changePND a + changePNDQ (a-25);; Recursive functions: Making change # (* Pennies, nickels, dimes, quarters, dollars *) let rec change (a:int) = if a < 100 then changePNDQ a else changePNDQ a + change (a-100);; Recursive functions: Making change Some tests: # change 5;; - : int = 2 # change 9;; - : int = 2 # change 10;; - : int = 4 # change 29;; - : int = 13 # change 30;; - : int = 18 # change 100;; - : int = 243 # change 499;; - : int = 33995 Lists • One handy structure for storing a collection of data values is a list. – provided as a built-in type in OCaml and a number of other popular languages (e., Lisp, Scheme, and Prolog—but not, unfortunately, Java). – built in OCaml by writing out its elements, enclosed in square brackets and separated by semicolons. # [1; 3; 2; 5];; - : int list = [1; 3; 2; 5] • The type that OCaml prints for this list is pronounced either “integer list” or “list of integers”.
• The empty list, written [], is sometimes called “nil.” Lists are homogeneous • OCaml does not allow different types of elements to be mixed within the same list: # [1; 2; "dog"];; Characters 7-13: • This expression has type string list but is here used with type int list Constructing Lists OCaml provides a number of built-in operations that return lists. The most basic one creates a new list by adding an element to the front of an existing list. – written :: and pronounced “cons” (for it constructs lists ). ; xn ] is simply a shorthand for x1 :: x2 ::.
:: xn :: [] • Note that, when omitting parentheses from an expression involving several uses of ::, we associate to the right – i. Taking Lists Apart • OCaml provides two basic operations for extracting the parts of a list.hd (pronounced “head”) returns the first element of a list.hd [1; 2; 3];; - : int = 1 List.tl (pronounced “tail”) returns everything but the first element.tl [1; 2; 3];; - : int list = [2; 3] More list examples # List.tl [1; 2; 3]));; - : int = 3 Recursion on lists • Lots of useful functions on lists can be written using recursion. – Here’s one that sums the elements of a list of numbers: # let rec listSum (l:int list) = if l = [] then 0 else List.hd l + listSum (List.tl l);; # listSum [5; 4; 3; 2; 1];; - : int = 15 Consing 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 = <fun> # snoc [5; 4; 3; 2] 1;; - : int list = [5; 4; 3; 2; 1] A better rev # (* Adds the elements of l to res in reverse order *) let rec revaux (l: int list) (res: int list) = if l = [] then res else revaux (List.hd l :: res);; val revaux : int list -> int list -> int list = <fun> # revaux [1; 2; 3] [4; 5; 6];; - : int list = [3; 2; 1; 4; 5; 6] # let rev (l: int list) = revaux l [];; val rev : int list -> int list = <fun> Tail recursion • It is usually fairly easy to rewrite a recursive function in tail-recursive style., the usual factorial function is not tail recursive (because one multiplication remains to be done after the recursive call returns): # let rec fact (n:int) = if n = 0 then 1 else 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 multiplications “accumulate”: # let rec factaux (acc:int) (n:int) = if n = 0 then acc else factaux (acc*n) (n-1);; # let fact (n:int) = factaux 1 n;; Basic Pattern Matching Recursive functions on lists tend to have a standard shape: – test whether the list is empty, and if it is not – do something involving the head element and the tail.