| 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 |
|