summaryrefslogtreecommitdiff
path: root/web/spiderweb/src/larch/lists.web
blob: 8a1f2bca2799f88a294114bc385063f7817fffab (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
@*Theory of sequences.
The theory of sequences is built on the theory of stacks. 
The stack theory provides most of the machinery needed for the elementary
operations on lists:  |insert|, |head|, |tail|, and |is_empty|.
The sequence trait includes
additional machinery that allows easy specification of concatenation.
@c
sequence: trait
    imports Stack_theory with [nil for empty_stack,
		cons for push, first for top, rest for pop]
    introduces
         enter: C,E -> C        % adds e to back of c 
         last:  C -> E
         prefix:  C -> C        % c with last deleted 
         #.[#]:C, Card -> E      % indexed selection (starts at 1) 
         append: C,C -> C       % concatenation 

    constrains [C] so that C is generated by [new, insert]
                           C is generated by [new, enter]
                           C is partitioned by [first, rest, isEmpty]
                           C is partitioned by [last, prefix, isEmpty]

      for all [e:E] 
         last(enter(new,e)) = e
         prefix(enter(new,e)) = new

      for all [c:C, e:E] 
         not isEmpty(enter(c,e))
         last(enter(c,e)) = e
         prefix(enter(c,e)) = stk

     for  all [c:C, e, e1: E] 
          insert(new,e) = enter(new,e)
          insert(enter(c,e),e1) = enter(insert(c,e1),e)

       for all [c:C, i:Card] 
          c.[1] = first(c)
          c.[i+1] = rest(c).[i]

      for all [c,c1:C, e:E] 
         append(c,new) = c
         append(c,insert(c1,e)) = insert(append(c,c1), e)

 implies
       converts [insert, first, last, rest, prefix],
                [enter, first, last, rest, prefix],
                [append],
                [isEmpty],
                [size],
                [#.[#]]


      exempts last(new), prefix(new), first(new), rest(new) 
%              for all [c:C], c(0)  

@*Index.