Debian Codegraph @

library/explanation.markdown

raw
1 # Library Format Discussion
2
3 I now started writing new libraries. I started with the list-library as a comparably
4 simple example. As discussed, I mainly follow the Haskell library. Attached you find
5 a file called "list.lem" with my attempt. The file "basic_classes.lem" contains class
6 definitions used by "list.lem".
7
8 In the following, I will try to talk you through "list.lem" explaining some of the problems
9 and design decisions.
10
11
12 ## Basic structure
13
14 Let's use the length function of lists as an example, on how I would like to write
15 simple functions in the library. As before, it all starts with a val-declaration:
16
17 val length : forall 'a. list 'a -> num
18
19 Then, I would like in many cases to have a Lem-definition of the function. This
20 definition is used as a reference implementation for explaining the semantics. Moreover,
21 it is used for backends, for which no other representation is provided.
22 For `length`, giving such a reference implementation is straightforward.
23 Notice the use of ``declare termination_argument`` though. Moreover, notice
24 that these definitions should be clean and straighforward. Since mappings
25 to native backend represenations are very likely, efficient execution
26 is a minor concern.
27
28 let rec length l = match l with
29 | [] -> 0
30 | x :: xs -> length xs + 1
31 end
32
33 declare termination_argument length = automatic
34
35 Then the mapping to targets is done. Before, a
36 separate constant was defined in a backend specific hierarchy.
37 Then, `let inline` statements were used to perform the mapping
38 to these target-specific constants. In contrast, I propose
39 using `declare targetrep` statements:
40
41 declare targetrep hol length = 'LENGTH'
42 declare targetrep ocaml length = 'List.length'
43 declare targetrep isabelle length = 'List.length'
44 declare targetrep coq length = 'List.length'
45
46 These `declare targetrep` statements are similar to `let inline` ones.
47 However, they deliberately allow mappings for exactly one target. Moreover,
48 the right-hand side is an expression that can contain quotations like `'LENGTH'`.
49 These parts are literally used by the backend, but not type-checked. For simple
50 functions like `length`, this is in my opinion not a problem. The benefit is that
51 it is very easy to extend the library. More complicated examples are discussed
52 below.
53
54 Finally, I also think some simple tests are useful. They serve both as documentation
55 of the intended semantics and can be used to check semi-automatically, whether the
56 provided target-mappings are really sensible.
57
58 assert length_0: (length [] = 0)
59 assert length_1: (length [2] = 1)
60 assert length_2: (length [2;3] = 2)
61
62 lemma length_spec: ((length [] = 0) && (forall x xs. length (x :: xs) = length xs + 1))
63
64
65 ### Infix operations
66
67 `length` is a particularly simple example. Infix operations like
68 `append` are slightly more tricky. The `declare targetrep` syntax
69 allows to map to infix operators, specifying the associativity as well.
70 Moreover, the `declare ascii_rep` syntax is used to map `++` to a
71 simple identifier for backends that have trouble handling `++` directly.
72
73 val (++) : forall 'a. list 'a -> list 'a -> list 'a
74 let rec (++) xs ys = match xs with
75 | [] -> ys
76 | x :: xs' -> x :: (xs' ++ ys)
77 end
78 declare ascii_rep function (++) = append
79 declare termination_argument append = automatic
80
81 declare targetrep hol append = infix (right-assoc 32) '++'
82 declare targetrep ocaml append = 'List.append'
83 declare targetrep isabelle append = infix (left-assoc 13) '@'
84 declare targetrep coq append = 'List.app'
85 declare targetrep html append = infix (right-assoc 32) "++"
86
87 assert append_1: ([0;1;2;3] ++ [4;5] = [0;1;2;3;4;5])
88 lemma append_nil_1: (forall l. l ++ [] = l)
89 lemma append_nil_2: (forall l. [] ++ l = l)
90
91
92 ### Argument order
93
94 Some functions like fold-right are provided by all backends, but with slightly
95 different signatures. The syntax of `declare targetrep` is flexible enough to
96 allow for example swapping arguments. Compared with the old library-format, less typechecking
97 is done here. However, I believe this is justifiable for the benefit of simpler
98 mappings. The old way is still possible by declaring an auxiliary fold function with
99 different argument order and using `let inline` to map to this function.
100
101 val foldr : forall 'a 'b. ('a -> 'b -> 'b) -> 'b -> list 'a -> 'b
102 let rec foldr f b l = match l with
103 | [] -> b
104 | x :: xs -> f x (foldr f b xs)
105 end
106 declare termination_argument foldr = automatic
107
108 declare targetrep hol foldr = 'FOLDR'
109 declare targetrep ocaml foldr f b l = 'List.fold_right' f l b
110 declare targetrep isabelle foldr f b l = 'List.foldr' f l b
111 declare targetrep coq foldr = 'List.fold_right'
112
113 assert fold_right_0: (foldr (+) 0 [] = 0)
114 assert fold_right_1: (foldr (+) 1 [4] = 5)
115 assert fold_right_4: (foldr (fun e l -> e::l) [] [1;2;3;4] = [1;2;3;4])
116
117
118 ### Fancy mappings
119
120 `declare targetrep` is powerful enough to allow also fancy mappings.
121 Consider the following predicate `all` that checks whether all elements
122 of a list satisfy a certain property:
123
124 val all : forall 'a. ('a -> bool) -> list 'a -> bool
125 let all P l = foldl (fun r e = P e && r) true l
126
127 Mappings for `hol`, `ocaml` and `coq` are straightforward
128
129 declare targetrep hol all = 'EVERY'
130 declare targetrep ocaml all = 'List.all'
131 declare targetrep coq all = 'List.forallb'
132
133 However, for Isabelle, there is a minor problem. The idiomatic way
134 in Isabelle would be to convert the list into a set using `set` and
135 use bounded quantification over this set. However, if not done
136 carefully, this introduces an undesired dependency between
137 the set and list libraries. The `targetrep` syntax circumvents
138 this problem, by not typechecking `set`:
139
140 declare targetrep isabelle all P l = (forall (x IN ('set' l)). P x)
141
142
143 ## Representing equality
144
145
146 In `basic_classes.lem`, there is a typeclass `Eq` for equality. It defines
147 the infix operation `=`, i.e. the standard equality used by Lem. All types,
148 we can perform an equality check on, should be instances of the `Eq` type class.
149 In order to allow easy structural equality checks, there is also the function
150 `unsafe_structural_equality`. It plays the role of the old `=`. The name is
151 deliberately long to discourage it's direct usage. However, it is handy to
152 instantiate the type-class `Eq` for simple types. The prefix `unsafe` indicates
153 that this equality check might fail (e.g. when comparing functions in OCaml).
154
155 class ( Eq 'a )
156 val (=) : 'a -> 'a -> bool
157 end
158
159 type ordering = LT | EQ | GT
160
161 instance (Eq ordering)
162 let (=) = unsafe_structural_equality
163 end
164
165
166
167 ### Problems with type classes / equality
168
169
170 With a type-class for equality present, all functions should use this equality.
171 An example is the membership test for lists. The membership
172 test is essentially an instance of the existential quantification over
173 lists, where we check, whether an element equal to the given one exists.
174
175 val elem : forall 'a. Eq 'a => 'a -> list 'a -> bool
176 let inline elem e l = any ((=) e) l
177
178 However, this is not really what we want. We would like to use the backends
179 native membership functions to avoid unnecessary complicated output.
180 This is however only correct, if the equality provided provided by the type-class
181 is for a concrete type equal to the one used by the backend, i.e. the structural one.
182
183 I propose solving this problem, by adding an additional, raw element check
184 function to the library. A simple rewrite mechanism could then be used to perform the mapping
185 for us.
186
187 val elem_raw : forall 'a. 'a -> list 'a -> bool
188 declare targetrep hol elem_raw = 'MEM'
189 declare targetrep ocaml elem_raw = 'List.mem'
190 declare targetrep isabelle elem_raw e l = e IN ('set' l)
191 declare targetrep coq elem_raw = 'List.forallb'
192
193 rewrite {HOL} elem_raw_intro: (forall e l. (any (unsafe_structural_equality e) l) = (elem_raw e l))
194
195 This is a simple, pragmatic solution. The `rewrite` construct is similar to existing `lemma` statements.
196 It should be therefore easy to add to the parser. It essentially defines an expression of type bool,
197 which could be handed to an expression macro to perform the actual rewrite.
198
199
200