comparison lab4/test/choices3.p @ 0:bfdcc3820b32

Basis
author Mike Spivey <mike@cs.ox.ac.uk>
date Thu, 05 Oct 2017 08:04:15 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:bfdcc3820b32
1 (* Enumerate (n choose k) choices with linked list *)
2
3 const letters = "abcdef";
4
5 type list = pointer to cell; cell = record head: char; tail: list end;
6
7 proc cons(head: char; tail: list): list;
8 var p: list;
9 begin
10 new(p);
11 p^.head := head; p^.tail := tail;
12 return p
13 end;
14
15 proc print(p: list);
16 var q: list;
17 begin
18 q := p;
19 while q <> nil do
20 print_char(q^.head);
21 q := q^.tail
22 end
23 end;
24
25 (* Complete choice with k items chosen from [0..n) *)
26 proc choose(k, n: integer; suffix: list);
27 begin
28 if k <= n then
29 if k = 0 then
30 print(suffix); newline()
31 else
32 choose(k, n-1, suffix);
33 choose(k-1, n-1, cons(letters[n-1], suffix))
34 end
35 end
36 end;
37
38 begin
39 choose(3, 6, nil)
40 end.
41
42 (*<<
43 abc
44 abd
45 acd
46 bcd
47 abe
48 ace
49 bce
50 ade
51 bde
52 cde
53 abf
54 acf
55 bcf
56 adf
57 bdf
58 cdf
59 aef
60 bef
61 cef
62 def
63 >>*)
64
65 (*[[
66 @ picoPascal compiler output
67 .include "fixup.s"
68 .global pmain
69
70 @ proc cons(head: char; tail: list): list;
71 .text
72 _cons:
73 mov ip, sp
74 stmfd sp!, {r0-r1}
75 stmfd sp!, {r4-r10, fp, ip, lr}
76 mov fp, sp
77 @ new(p);
78 mov r0, #8
79 bl new
80 mov r4, r0
81 @ p^.head := head; p^.tail := tail;
82 ldrb r0, [fp, #40]
83 strb r0, [r4]
84 ldr r0, [fp, #44]
85 str r0, [r4, #4]
86 @ return p
87 mov r0, r4
88 ldmfd fp, {r4-r10, fp, sp, pc}
89 .ltorg
90
91 @ proc print(p: list);
92 _print:
93 mov ip, sp
94 stmfd sp!, {r0-r1}
95 stmfd sp!, {r4-r10, fp, ip, lr}
96 mov fp, sp
97 @ q := p;
98 ldr r4, [fp, #40]
99 .L4:
100 @ while q <> nil do
101 cmp r4, #0
102 beq .L3
103 @ print_char(q^.head);
104 ldrb r0, [r4]
105 bl print_char
106 @ q := q^.tail
107 ldr r4, [r4, #4]
108 b .L4
109 .L3:
110 ldmfd fp, {r4-r10, fp, sp, pc}
111 .ltorg
112
113 @ proc choose(k, n: integer; suffix: list);
114 _choose:
115 mov ip, sp
116 stmfd sp!, {r0-r3}
117 stmfd sp!, {r4-r10, fp, ip, lr}
118 mov fp, sp
119 @ if k <= n then
120 ldr r4, [fp, #40]
121 ldr r0, [fp, #44]
122 cmp r4, r0
123 bgt .L7
124 @ if k = 0 then
125 cmp r4, #0
126 bne .L12
127 @ print(suffix); newline()
128 ldr r0, [fp, #48]
129 bl _print
130 bl newline
131 b .L7
132 .L12:
133 @ choose(k, n-1, suffix);
134 ldr r2, [fp, #48]
135 ldr r0, [fp, #44]
136 sub r1, r0, #1
137 ldr r0, [fp, #40]
138 bl _choose
139 @ choose(k-1, n-1, cons(letters[n-1], suffix))
140 ldr r4, [fp, #44]
141 ldr r1, [fp, #48]
142 set r0, g1
143 add r0, r0, r4
144 ldrb r0, [r0, #-1]
145 bl _cons
146 mov r2, r0
147 sub r1, r4, #1
148 ldr r0, [fp, #40]
149 sub r0, r0, #1
150 bl _choose
151 .L7:
152 ldmfd fp, {r4-r10, fp, sp, pc}
153 .ltorg
154
155 pmain:
156 mov ip, sp
157 stmfd sp!, {r4-r10, fp, ip, lr}
158 mov fp, sp
159 @ choose(3, 6, nil)
160 mov r2, #0
161 mov r1, #6
162 mov r0, #3
163 bl _choose
164 ldmfd fp, {r4-r10, fp, sp, pc}
165 .ltorg
166
167 .data
168 g1:
169 .byte 97, 98, 99, 100, 101, 102
170 .byte 0
171 @ End
172 ]]*)