Programming Languages A(Coursera / University of Washington) Assignment 3/signature和structure

本文主要是介绍Programming Languages A(Coursera / University of Washington) Assignment 3/signature和structure，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

The best way to understand a language construct is to understand how you would code it up in terms of other language constraints in another language.

原文件已上传到GitHub,分数是80: 点这里

本节需要用到标准库，sml标准库在这里：https://smlfamily.github.io/

小结

什么是弱类型、强类型、动态类型、静态类型

Program Errorstrapped errors。导致程序终止执行，如除0，Java中数组越界访问
untrapped errors。 出错后继续执行，但可能出现任意行为。如C里的缓冲区溢出、Jump到错误地址
Forbidden Behaviours 语言设计时，可以定义一组forbidden behaviors. 它必须包括所有untrapped errors, 但可能包含trapped errors.
Well behaved、ill behavedwell behaved: 如果程序执行不可能出现forbidden behaviors, 则为well behaved。
ill behaved: 否则为ill behaved…
有了上面的概念，再讨论强、弱类型，静态、动态类型
强、弱类型
强类型strongly typed: 如果一种语言的所有程序都是well behaved——即不可能出现forbidden behaviors，则该语言为strongly typed。
弱类型weakly typed: 否则为weakly typed。比如C语言的缓冲区溢出，属于trapped errors，即属于forbidden behaviors…故C是弱类型
前面的人也说了，弱类型语言，类型检查更不严格，如偏向于容忍隐式类型转换。譬如说C语言的int可以变成double。 这样的结果是：容易产生forbidden behaviours，所以是弱类型的
动态、静态类型
静态类型 statically: 如果在编译时拒绝ill behaved程序，则是statically typed;
动态类型dynamiclly: 如果在运行时拒绝ill behaviors, 则是dynamiclly typed。
误区大家觉得C语言要写int a, int b之类的，Python不用写(可以直接写a, b)，所以C是静态，Python是动态。这么理解是不够准确的。譬如Ocaml是静态类型的，但是也可以不用明确地写出来。。Ocaml是静态隐式类型静态类型可以分为两种：如果类型是语言语法的一部分，在是explicitly typed显式类型；如果类型通过编译时推导，是implicity typed隐式类型, 比如ML和Haskell
下面是些例子
无类型： 汇编
弱类型、静态类型 ： C/C++
弱类型、动态类型检查： Perl/PHP
强类型、静态类型检查 ：Java/C#
强类型、动态类型检查 ：Python, Scheme
静态显式类型 ：Java/C
静态隐式类型 ：Ocaml, Haskell

作者：rainoftime
链接：https://www.zhihu.com/question/19918532/answer/21647195
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Feature

本节课介绍了很多feature，列举如下：
First-Class Functions
Function Wrap
Map and Filter
Scope
Closure
Fold
Curry
No mutation
Mutable References

因为都是functional language，所以和 lisp很像，这节课其实也就是讲了sicp第一章“Formulating Abstractions with Higher-Order Procedures”的内容。体会过程式编程，过程和数据的界限并没有那么严格。

SML回调

sml的回调机制，很多modern programming language也借鉴了这种特性。

(*函数事件列表*)
val cbs : (int -> unit) list ref = ref []
(*更新ref list变量cbs的值*)
fun onKeyEvent f = cbs := f :: (!cbs)
(*事件计数*)
val timesPressed = ref 0
(*注册事件回调，不关心事件是什么，给计数器+1*)
val _ = onKeyEvent(fn _ =>timesPressed := (!timesPressed)+1)
(*注册按下事件的回调*)
fun printIfPressed i =onKeyEvent(fn j =>if i=jthen print("you pressed "^Int.toString i)else ())(*循环事件回调*)
fun onEvent i = let fun loop fs = case fs of[] => ()| f::fs' => (f i; loop fs') （*循环list调用回调*）in loop(!cbs) end

Closure idioms without closures

sml版本（有 closure）

datadype 'a mylist = Cons of 'a*('a list)|Empty
fun map f xs = case xs ofEmpty => Empty| Cons(x,xs) => Cons(f x, map f xs)
fun filter f xs =case xs ofEmpty => Empty| Cons(x,xs) => if f x then Cons(x,filter f xs) else filter f xs		

Java版本（无 closure）

interface Func<B,A> { B m(A x);}
interface Pred<A> {boolean m(A x);}
class List<T>{T head;List<T> tail;List(T x,List<T> xs){head = x;tail = xs;}
}
static <A,B> List<B> map(Func<B,A> f,List<A> xs){if(xs==null)return null;return new List<B>(f.m(xs,head),map(f,xs.tail));
}
static <A> List<A> filter(Pred<A> f,List<A> xs){if(xs==null) return null;if(f.m(xs.head)) return new List<A>(xs.head,filter(f,xs.tail));return filter(f,xs.tail);
}
static <A> int length(List<A> xs){int ans = 0;while(xs!=null){++ans;xs = xs.tail;}return ans;
}

Assignment

part 1 1-8

1. Write a function only_capitals that takes a string list and returns a string list that has only
the strings in the argument that start with an uppercase letter. Assume all strings have at least 1
character. Use List.filter, Char.isUpper, and String.sub to make a 1-2 line solution.
2. Write a function longest_string1 that takes a string list and returns the longest string in the
list. If the list is empty, return "". In the case of a tie, return the string closest to the beginning of the
list. Use foldl, String.size, and no recursion (other than the implementation of foldl is recursive).
3. Write a function longest_string2 that is exactly like longest_string1 except in the case of ties
it returns the string closest to the end of the list. Your solution should be almost an exact copy of
longest_string1. Still use foldl and String.size.
4. Write functions longest_string_helper, longest_string3, and longest_string4 such that:
• longest_string3 has the same behavior as longest_string1 and longest_string4 has the
same behavior as longest_string2.
• longest_string_helper has type (int * int -> bool) -> string list -> string
(notice the currying). This function will look a lot like longest_string1 and longest_string2
but is more general because it takes a function as an argument.
• If longest_string_helper is passed a function that behaves like > (so it returns true exactly
when its first argument is stricly greater than its second), then the function returned has the same
behavior as longest_string1.
• longest_string3 and longest_string4 are defined with val-bindings and partial applications
of longest_string_helper.
5. Write a function longest_capitalized that takes a string list and returns the longest string in
the list that begins with an uppercase letter, or "" if there are no such strings. Assume all strings
have at least 1 character. Use a val-binding and the ML library’s o operator for composing functions.
Resolve ties like in problem 2.
6. Write a function rev_string that takes a string and returns the string that is the same characters in
reverse order. Use ML’s o operator, the library function rev for reversing lists, and two library functions
in the String module. (Browse the module documentation to find the most useful functions.)
The next two problems involve writing functions over lists that will be useful in later problems.
7. Write a function first_answer of type (’a -> ’b option) -> ’a list -> ’b (notice the 2 arguments are curried). The first argument should be applied to elements of the second argument in order
until the first time it returns SOME v for some v and then v is the result of the call to first_answer.
If the first argument returns NONE for all list elements, then first_answer should raise the exception
NoAnswer. Hints: Sample solution is 5 lines and does nothing fancy.
18. Write a function all_answers of type (’a -> ’b list option) -> ’a list -> ’b list option
(notice the 2 arguments are curried). The first argument should be applied to elements of the second
argument. If it returns NONE for any element, then the result for all_answers is NONE. Else the
calls to the first argument will have produced SOME lst1, SOME lst2, ... SOME lstn and the result of
all_answers is SOME lst where lst is lst1, lst2, ..., lstn appended together (order doesn’t matter).
Hints: The sample solution is 8 lines. It uses a helper function with an accumulator and uses @. Note
all_answers f [] should evaluate to SOME [].

(* Coursera Programming Languages, Homework 3, Provided Code *)exception NoAnswerdatatype pattern = Wildcard| Variable of string| UnitP| ConstP of int| TupleP of pattern list| ConstructorP of string * patterndatatype valu = Const of int| Unit| Tuple of valu list| Constructor of string * valufun g f1 f2 p =let val r = g f1 f2 incase p ofWildcard          => f1 ()| Variable x        => f2 x| TupleP ps         => List.foldl (fn (p,i) => (r p) + i) 0 ps| ConstructorP(_,p) => r p| _                 => 0end(**** for the challenge problem only ****)datatype typ = Anything| UnitT| IntT| TupleT of typ list| Datatype of string(**** you can put all your code here ****)
(*part 1 1_7*)fun only_capitals (xs : string list)  =List.filter (fn (v) => Char.isUpper(String.sub(v,0))) xsfun longest_string1 (xs : string list) =foldl (fn(x,y) => if String.size(x)>=String.size(y) then x else y ) "" xsfun longest_string2 (xs : string list) =foldl (fn(x,y) => if String.size(x)>String.size(y) then x else y ) "" xsfun longest_string_helper f ( li: string list) s =foldl(fn(x,y) => if f(String.size(x),String.size(y)) then x else y) s lifun longest_string3 (xs : string list) =longest_string_helper (fn (a:int,b:int) => if a>=b then true else false) xs ""fun longest_string4 (xs : string list) =longest_string_helper (fn (a:int,b:int) => if a>b then true else false) xs ""fun longest_capitalized (xs : string list) =(longest_string2 o only_capitals) xsfun rev_string (str : string) =(implode o rev o explode) str

part 2 9-10

The remaining problems use these type definitions, which are inspired by the type definitions an ML implementation would use to implement pattern matching:
datatype pattern = Wildcard | Variable of string | UnitP | ConstP of int
| TupleP of pattern list | ConstructorP of string * pattern
datatype valu = Const of int | Unit | Tuple of valu list | Constructor of string * valu
Given valu v and pattern p, either p matches v or not. If it does, the match produces a list of string * valu
pairs; order in the list does not matter. The rules for matching should be unsurprising:
• Wildcard matches everything and produces the empty list of bindings.
• Variable s matches any value v and produces the one-element list holding (s,v).
• UnitP matches only Unit and produces the empty list of bindings.
• ConstP 17 matches only Const 17 and produces the empty list of bindings (and similarly for other
integers).
• TupleP ps matches a value of the form Tuple vs if ps and vs have the same length and for all i, the
ith element of ps matches the ith element of vs. The list of bindings produced is all the lists from the
nested pattern matches appended together.
• ConstructorP(s1,p) matches Constructor(s2,v) if s1 and s2 are the same string (you can compare
them with =) and p matches v. The list of bindings produced is the list from the nested pattern match.
We call the strings s1 and s2 the constructor name.
• Nothing else matches.
9. (This problem uses the pattern datatype but is not really about pattern-matching.) A function g has
been provided to you.
(a) Use g to define a function count_wildcards that takes a pattern and returns how many Wildcard
patterns it contains.
(b) Use g to define a function count_wild_and_variable_lengths that takes a pattern and returns
the number of Wildcard patterns it contains plus the sum of the string lengths of all the variables
in the variable patterns it contains. (Use String.size. We care only about variable names; the
constructor names are not relevant.)
(c) Use g to define a function count_some_var that takes a string and a pattern (as a pair) and
returns the number of times the string appears as a variable in the pattern. We care only about
variable names; the constructor names are not relevant.
210. Write a function check_pat that takes a pattern and returns true if and only if all the variables
appearing in the pattern are distinct from each other (i.e., use different strings). The constructor
names are not relevant. Hints: The sample solution uses two helper functions. The first takes a
pattern and returns a list of all the strings it uses for variables. Using foldl with a function that uses
@ is useful in one case. The second takes a list of strings and decides if it has repeats. List.exists may
be useful. Sample solution is 15 lines. These are hints: We are not requiring foldl and List.exists
here, but they make it easier.
11. Write a function match that takes a valu * pattern and returns a (string * valu) list option,
namely NONE if the pattern does not match and SOME lst where lst is the list of bindings if it does.
Note that if the value matches but the pattern has no patterns of the form Variable s, then the result
is SOME []. Hints: Sample solution has one case expression with 7 branches. The branch for tuples
uses all_answers and ListPair.zip. Sample solution is 13 lines. Remember to look above for the
rules for what patterns match what values, and what bindings they produce. These are hints: We are
not requiring all_answers and ListPair.zip here, but they make it easier.
12. Write a function first_match that takes a value and a list of patterns and returns a
(string * valu) list option, namely NONE if no pattern in the list matches or SOME lst where
lst is the list of bindings for the first pattern in the list that matches. Use first_answer and a
handle-expression. Hints: Sample solution is 3 lines.

(*part 2*)fun first_answer f li =case li of[] => raise NoAnswer| x::xs' => letval tmpAns =(f x)inif isSome tmpAnsthen valOf tmpAnselse first_answer f xs'endfun all_answers f li =letfun helper f li now = case li of[] => SOME now|x::xs'  =>letval tmpAns =(f x)inif isSome tmpAnsthen helper f xs' (now@[valOf tmpAns])else helper f xs' nowendinhelper f li []endfun count_wildcards p =g (fn (x) => 1) (fn (x) => 0) pfun count_wild_and_variable_lengths p =g (fn() => 1) (fn(x)=> String.size(x)) pfun count_some_var (str,p) =g (fn() => 0) (fn(x) => if str = x then 1 else 0) pfun check_pat p =letfun helper1 p =case p ofTupleP ps => (List.foldl (fn (a,b:string list) => b@(helper1 a)) [] ps)| Variable x => [x]| ConstructorP(x,s) => [x]@(helper1 s)| _ => [] ;fun helper2 l =case l of[] => true| x::xs' =>letval result = (List.exists (fn (now) => if now = x then true else false ) xs')inif result=truethenfalseelsehelper2 xs'endinletval tmp:string list = helper1 pinhelper2 tmpendend

part3 11 12

匹配规则
给一个valu v 和一个pattern p
用p去匹配v，匹配成功的话是一个string*valu的pair

• Wildcard匹配一切并且产生一个空list
• 变量s匹配任何值v，并生成包含(s,v)的单元素列表。
• UnitP只匹配Unit，并生成空的绑定列表。
• ConstP 17只匹配Const 17并产生空的绑定列表(其他整数也类似)。
• TupleP ps匹配Tuple vs的形式，如果ps和vs有相同的长度，并且对于所有的i, ps的第i个元素匹配vs的第i个元素。生成的绑定列表是嵌套模式匹配的所有列表附加在一起
• 如果s1和s2是同一个字符串(可以用=比较它们)，而p匹配v，生成的绑定列表是嵌套模式匹配的列表。我们将字符串s1和s2称为构造函数名。

fun match(v, pat) =case (v, pat) of(_, Wildcard)	=> SOME []|(v, Variable s) => SOME [(s,v)]|(Unit , UnitP) =>SOME []|(Const i, ConstP j) => if i=j then SOME [] else NONE|(Tuple vt, TupleP pt) => if List.length vt = List.length ptthen all_answers match (ListPair.zip(vt, pt))else NONE|(Constructor(sv , vv), ConstructorP(sp , pp)) => if sv=sp then match (vv, pp) else NONE| _ => NONEfun first_match v pl =SOME (first_answer (match) (List.map(fn(x) => (v,x)) pl))handle NoAnswer => NONE

Signature和Structure

structure Digit :> DIGIT =
struct
type digit = int
exception BadDigit
exception FailTest
fun make_digit i = if i < 0 orelse i > 9 then raise BadDigit else i
fun increment d = if d=9 then 0 else d+1
fun decrement d = if d=0 then 9 else d-1
val down_and_up = increment o decrement (* recall o is composition *)
fun test d = if down_and_up d = d then () else raise FailTest
endsignature DIGIT = 
sig
type digit = int
val make_digit : int -> digit
val increment : digit -> digit
val decrement : digit -> digit
val down_and_up : digit -> digit
val test : digit -> unit
endsignature DIGIT = 
sig
type digit = int
val make_digit : int -> digit
val increment : digit -> digit
val decrement : digit -> digit
val down_and_up : digit -> digit
endsignature DIGIT = 
sig
type digit = int
val make_digit : int -> digit
val increment : digit -> digit
val decrement : digit -> digit
val test : digit -> unit
endsignature DIGIT = 
sig
type digit
val make_digit : int -> digit
val increment : digit -> digit
val decrement : digit -> digit
val down_and_up : digit -> digit
val test : digit -> unit
endsignature DIGIT = 
sig
type digit
val increment : digit -> digit
val decrement : digit -> digit
val down_and_up : digit -> digit
val test : digit -> unit
end

signature显式地决定暴露地接口，类型必须在signature里面显式定义，否则不能被外界调用。

这篇关于Programming Languages A(Coursera / University of Washington) Assignment 3/signature和structure的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---