annotate lab4/test/choices3.p @ 1:b5139af1a420 tip basis

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