mu - Soul of a tiny new machine. More thorough tests → More comprehensible and rewrite-friendly software → More resilient society.

diff options

Diffstat (limited to 'apps/factorial.subx')

0 files changed, 0 insertions, 0 deletions

# A doubly linked list permits bidirectional traversal. container duplex-list:_elem [ value:_elem next:&:duplex-list:_elem prev:&:duplex-list:_elem ] def push x:_elem, in:&:duplex-list:_elem/contained-in:result -> result:&:duplex-list:_elem [ local-scope load-inputs result:&:duplex-list:_elem <- new {(duplex-list _elem): type} *result <- merge x, in, null return-unless in put *in, prev:offset, result ] def first in:&:duplex-list:_elem -> result:_elem [ local-scope load-inputs { break-if in zero:&:_elem <- new _elem:type zero-result:_elem <- copy *zero abandon zero return zero-result } result <- get *in, value:offset ] def next in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [ local-scope load-inputs return-unless in, null result <- get *in, next:offset ] def prev in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [ local-scope load-inputs return-unless in, null result <- get *in, prev:offset return result ] scenario duplex-list-handling [ run [ local-scope # reserve locations 0-9 to check for missing null check 10:num/raw <- copy 34 11:num/raw <- copy 35 list:&:duplex-list:num <- push 3, null list <- push 4, list list <- push 5, list list2:&:duplex-list:num <- copy list 20:num/raw <- first list2 list2 <- next list2 21:num/raw <- first list2 list2 <- next list2 22:num/raw <- first list2 30:&:duplex-list:num/raw <- next list2 31:num/raw <- first 30:&:duplex-list:num/raw 32:&:duplex-list:num/raw <- next 30:&:duplex-list:num/raw 33:&:duplex-list:num/raw <- prev 30:&:duplex-list:num/raw list2 <- prev list2 40:num/raw <- first list2 list2 <- prev list2 41:num/raw <- first list2 50:bool/raw <- equal list, list2 ] memory-should-contain [ 0 <- 0 # no modifications to null pointers 10 <- 34 11 <- 35 20 <- 5 # scanning next 21 <- 4 22 <- 3 30 <- 0 # null 31 <- 0 # first of null 32 <- 0 # next of null 33 <- 0 # prev of null 40 <- 4 # then start scanning prev 41 <- 5 50 <- 1 # list back at start ] ] def length l:&:duplex-list:_elem -> result:num [ local-scope load-inputs result <- copy 0 { break-unless l result <- add result, 1 l <- next l loop } ] # insert 'x' after 'in' def insert x:_elem, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [ local-scope load-inputs new-node:&:duplex-list:_elem <- new {(duplex-list _elem): type} *new-node <- put *new-node, value:offset, x # save old next before changing it next-node:&:duplex-list:_elem <- get *in, next:offset *in <- put *in, next:offset, new-node *new-node <- put *new-node, prev:offset, in *new-node <- put *new-node, next:offset, next-node return-unless next-node *next-node <- put *next-node, prev:offset, new-node ] scenario inserting-into-duplex-list [ local-scope list:&:duplex-list:num <- push 3, null list <- push 4, list list <- push 5, list run [ list2:&:duplex-list:num <- next list # inside list list2 <- insert 6, list2 # check structure like before list2 <- copy list 10:num/raw <- first list2 list2 <- next list2 11:num/raw <- first list2 list2 <- next list2 12:num/raw <- first list2 list2 <- next list2 13:num/raw <- first list2 list2 <- prev list2 20:num/raw <- first list2 list2 <- prev list2 21:num/raw <- first list2 list2 <- prev list2 22:num/raw <- first list2 30:bool/raw <- equal list, list2 ] memory-should-contain [ 10 <- 5 # scanning next 11 <- 4 12 <- 6 # inserted element 13 <- 3 20 <- 6 # then prev 21 <- 4 22 <- 5 30 <- 1 # list back at start ] ] scenario inserting-at-end-of-duplex-list [ local-scope list:&:duplex-list:num <- push 3, null list <- push 4, list list <- push 5, list run [ list2:&:duplex-list:num <- next list # inside list list2 <- next list2 # now at end of list list2 <- insert 6, list2 # check structure like before list2 <- copy list 10:num/raw <- first list2 list2 <- next list2 11:num/raw <- first list2 list2 <- next list2 12:num/raw <- first list2 list2 <- next list2 13:num/raw <- first list2 list2 <- prev list2 20:num/raw <- first list2 list2 <- prev list2 21:num/raw <- first list2 list2 <- prev list2 22:num/raw <- first list2 30:bool/raw <- equal list, list2 ] memory-should-contain [ 10 <- 5 # scanning next 11 <- 4 12 <- 3 13 <- 6 # inserted element 20 <- 3 # then prev 21 <- 4 22 <- 5 30 <- 1 # list back at start ] ] scenario inserting-after-start-of-duplex-list [ local-scope list:&:duplex-list:num <- push 3, null list <- push 4, list list <- push 5, list run [ list <- insert 6, list # check structure like before list2:&:duplex-list:num <- copy list 10:num/raw <- first list2 list2 <- next list2 11:num/raw <- first list2 list2 <- next list2 12:num/raw <- first list2 list2 <- next list2 13:num/raw <- first list2 list2 <- prev list2 20:num/raw <- first list2 list2 <- prev list2 21:num/raw <- first list2 list2 <- prev list2 22:num/raw <- first list2 30:bool/raw <- equal list, list2 ] memory-should-contain [ 10 <- 5 # scanning next 11 <- 6 # inserted element 12 <- 4 13 <- 3 20 <- 4 # then prev 21 <- 6 22 <- 5 30 <- 1 # list back at start ] ] # remove 'x' from its surrounding list 'in' # # Returns null if and only if list is empty. Beware: in that case any other # pointers to the head are now invalid. def remove x:&:duplex-list:_elem/contained-in:in, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [ local-scope load-inputs # if 'x' is null, return return-unless x next-node:&:duplex-list:_elem <- get *x, next:offset prev-node:&:duplex-list:_elem <- get *x, prev:offset # null x's pointers *x <- put *x, next:offset, null *x <- put *x, prev:offset, null # if next-node is not null, set its prev pointer { break-unless next-node *next-node <- put *next-node, prev:offset, prev-node } # if prev-node is not null, set its next pointer and return { break-unless prev-node *prev-node <- put *prev-node, next:offset, next-node return } # if prev-node is null, then we removed the head node at 'in' # return the new head rather than the old 'in' return next-node ] scenario removing-from-duplex-list [ local-scope list:&:duplex-list:num <- push 3, null list <- push 4, list list <- push 5, list run [ list2:&:duplex-list:num <- next list # second element list <- remove list2, list 10:bool/raw <- equal list2, null # check structure like before list2 <- copy list 11:num/raw <- first list2 list2 <- next list2 12:num/raw <- first list2 20:&:duplex-list:num/raw <- next list2 list2 <- prev list2 30:num/raw <- first list2 40:bool/raw <- equal list, list2 ] memory-should-contain [ 10 <- 0 # remove returned non-null 11 <- 5 # scanning next, skipping deleted element 12 <- 3 20 <- 0 # no more elements 30 <- 5 # prev of final element 40 <- 1 # list back at start ] ] scenario removing-from-start-of-duplex-list [ local-scope list:&:duplex-list:num <- push 3, null list <- push 4, list list <- push 5, list run [ list <- remove list, list # check structure like before list2:&:duplex-list:num <- copy list 10:num/raw <- first list2 list2 <- next list2 11:num/raw <- first list2 20:&:duplex-list:num/raw <- next list2 list2 <- prev list2 30:num/raw <- first list2 40:bool/raw <- equal list, list2 ] memory-should-contain [ 10 <- 4 # scanning next, skipping deleted element 11 <- 3 20 <- 0 # no more elements 30 <- 4 # prev of final element 40 <- 1 # list back at start ] ] scenario removing-from-end-of-duplex-list [ local-scope list:&:duplex-list:num <- push 3, null list <- push 4, list list <- push 5, list run [ # delete last element list2:&:duplex-list:num <- next list list2 <- next list2 list <- remove list2, list 10:bool/raw <- equal list2, null # check structure like before list2 <- copy list 11:num/raw <- first list2 list2 <- next list2 12:num/raw <- first list2 20:&:duplex-list:num/raw <- next list2 list2 <- prev list2 30:num/raw <- first list2 40:bool/raw <- equal list, list2 ] memory-should-contain [ 10 <- 0 # remove returned non-null 11 <- 5 # scanning next, skipping deleted element 12 <- 4 20 <- 0 # no more elements 30 <- 5 # prev of final element 40 <- 1 # list back at start ] ] scenario removing-from-singleton-duplex-list [ local-scope list:&:duplex-list:num <- push 3, null run [ list <- remove list, list 1:num/raw <- deaddress list ] memory-should-contain [ 1 <- 0 # back to an empty list ] ] def remove x:&:duplex-list:_elem/contained-in:in, n:num, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [ local-scope load-inputs i:num <- copy 0 curr:&:duplex-list:_elem <- copy x { done?:bool <- greater-or-equal i, n break-if done? break-unless curr next:&:duplex-list:_elem <- next curr in <- remove curr, in curr <- copy next i <- add i, 1 loop } ] scenario removing-multiple-from-duplex-list [ local-scope list:&:duplex-list:num <- push 3, null list <- push 4, list list <- push 5, list run [ list2:&:duplex-list:num <- next list # second element list <- remove list2, 2, list stash list ] trace-should-contain [ app: 5 ] ] # remove values between 'start' and 'end' (both exclusive). # also clear pointers back out from start/end for hygiene. # set end to 0 to delete everything past start. # can't set start to 0 to delete everything before end, because there's no # clean way to return the new head pointer. def remove-between start:&:duplex-list:_elem, end:&:duplex-list:_elem/contained-in:start -> start:&:duplex-list:_elem [ local-scope load-inputs next:&:duplex-list:_elem <- get *start, next:offset nothing-to-delete?:bool <- equal next, end return-if nothing-to-delete? assert next, [malformed duplex list] # start->next->prev = 0 # start->next = end *next <- put *next, prev:offset, null *start <- put *start, next:offset, end { break-if end stash [spliced:] next return } # end->prev->next = 0 # end->prev = start prev:&:duplex-list:_elem <- get *end, prev:offset assert prev, [malformed duplex list - 2] *prev <- put *prev, next:offset, null stash [spliced:] next *end <- put *end, prev:offset, start ] scenario remove-range [ # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] local-scope list:&:duplex-list:num <- push 18, null list <- push 17, list list <- push 16, list list <- push 15, list list <- push 14, list list <- push 13, list run [ # delete 16 onwards # first pointer: to the third element list2:&:duplex-list:num <- next list list2 <- next list2 list2 <- remove-between list2, null # now check the list 10:num/raw <- get *list, value:offset list <- next list 11:num/raw <- get *list, value:offset list <- next list 12:num/raw <- get *list, value:offset 20:&:duplex-list:num/raw <- next list ] memory-should-contain [ 10 <- 13 11 <- 14 12 <- 15 20 <- 0 ] trace-should-contain [ app: spliced: 16 <-> 17 <-> 18 ] ] scenario remove-range-to-final [ local-scope # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] list:&:duplex-list:num <- push 18, null list <- push 17, list list <- push 16, list list <- push 15, list list <- push 14, list list <- push 13, list run [ # delete 15, 16 and 17 # start pointer: to the second element list2:&:duplex-list:num <- next list # end pointer: to the last (sixth) element end:&:duplex-list:num <- next list2 end <- next end end <- next end end <- next end remove-between list2, end # now check the list 10:num/raw <- get *list, value:offset list <- next list 11:num/raw <- get *list, value:offset list <- next list 12:num/raw <- get *list, value:offset 20:&:duplex-list:num/raw <- next list ] memory-should-contain [ 10 <- 13 11 <- 14 12 <- 18 20 <- 0 # no more elements ] trace-should-contain [ app: spliced: 15 <-> 16 <-> 17 ] ] scenario remove-range-to-penultimate [ local-scope # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] list:&:duplex-list:num <- push 18, null list <- push 17, list list <- push 16, list list <- push 15, list list <- push 14, list list <- push 13, list run [ # delete 15 and 16 # start pointer: to the second element list2:&:duplex-list:num <- next list # end pointer: to the last (sixth) element end:&:duplex-list:num <- next list2 end <- next end end <- next end remove-between list2, end # now check the list 10:num/raw <- get *list, value:offset list <- next list 11:num/raw <- get *list, value:offset list <- next list 12:num/raw <- get *list, value:offset list <- next list 13:num/raw <- get *list, value:offset 20:&:duplex-list:num/raw <- next list ] memory-should-contain [ 10 <- 13 11 <- 14 12 <- 17 13 <- 18 20 <- 0 # no more elements ] trace-should-contain [ app: spliced: 15 <-> 16 ] ] scenario remove-range-empty [ local-scope # construct a duplex list with three elements [13, 14, 15] list:&:duplex-list:num <- push 15, null list <- push 14, list list <- push 13, list run [ # delete between first and second element (i.e. nothing) list2:&:duplex-list:num <- next list remove-between list, list2 # now check the list 10:num/raw <- get *list, value:offset list <- next list 11:num/raw <- get *list, value:offset list <- next list 12:num/raw <- get *list, value:offset 20:&:duplex-list:num/raw <- next list ] # no change memory-should-contain [ 10 <- 13 11 <- 14 12 <- 15 20 <- 0 ] ] scenario remove-range-to-end [ local-scope # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] list:&:duplex-list:num <- push 18, null list <- push 17, list list <- push 16, list list <- push 15, list list <- push 14, list list <- push 13, list run [ # remove the third element and beyond list2:&:duplex-list:num <- next list remove-between list2, null # now check the list 10:num/raw <- get *list, value:offset list <- next list 11:num/raw <- get *list, value:offset 20:&:duplex-list:num/raw <- next list ] memory-should-contain [ 10 <- 13 11 <- 14 20 <- 0 ] ] # insert list beginning at 'start' after 'in' def splice in:&:duplex-list:_elem, start:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [ local-scope load-inputs return-unless in return-unless start end:&:duplex-list:_elem <- last start next:&:duplex-list:_elem <- next in { break-unless next *end <- put *end, next:offset, next *next <- put *next, prev:offset, end } *in <- put *in, next:offset, start *start <- put *start, prev:offset, in ] # insert contents of 'new' after 'in' def insert in:&:duplex-list:_elem, new:&:@:_elem -> in:&:duplex-list:_elem [ local-scope load-inputs return-unless in return-unless new len:num <- length *new return-unless len curr:&:duplex-list:_elem <- copy in idx:num <- copy 0 { done?:bool <- greater-or-equal idx, len break-if done? c:_elem <- index *new, idx insert c, curr # next iter curr <- next curr idx <- add idx, 1 loop } ] def append in:&:duplex-list:_elem, new:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [ local-scope load-inputs last:&:duplex-list:_elem <- last in *last <- put *last, next:offset, new return-unless new *new <- put *new, prev:offset, last ] def last in:&:duplex-list:_elem -> result:&:duplex-list:_elem [ local-scope load-inputs result <- copy in { next:&:duplex-list:_elem <- next result break-unless next result <- copy next loop } ] # does a duplex list start with a certain sequence of elements? def match x:&:duplex-list:_elem, y:&:@:_elem -> result:bool [ local-scope load-inputs i:num <- copy 0 max:num <- length *y { done?:bool <- greater-or-equal i, max break-if done? expected:_elem <- index *y, i return-unless x, false/no-match curr:_elem <- first x curr-matches?:bool <- equal curr, expected return-unless curr-matches?, false/no-match x <- next x i <- add i, 1 loop } return true/successful-match ] scenario duplex-list-match [ local-scope list:&:duplex-list:char <- push 97/a, null list <- push 98/b, list list <- push 99/c, list list <- push 100/d, list run [ 10:bool/raw <- match list, [] 11:bool/raw <- match list, [d] 12:bool/raw <- match list, [dc] 13:bool/raw <- match list, [dcba] 14:bool/raw <- match list, [dd] 15:bool/raw <- match list, [dcbax] ] memory-should-contain [ 10 <- 1 # matches [] 11 <- 1 # matches [d] 12 <- 1 # matches [dc] 13 <- 1 # matches [dcba] 14 <- 0 # does not match [dd] 15 <- 0 # does not match [dcbax] ] ] # helper for debugging def dump-from x:&:duplex-list:_elem [ local-scope load-inputs $print x, [: ] { break-unless x c:_elem <- get *x, value:offset $print c, [ ] x <- next x { is-newline?:bool <- equal c, 10/newline break-unless is-newline? $print 10/newline $print x, [: ] } loop } $print 10/newline, [---], 10/newline ] scenario stash-duplex-list [ local-scope list:&:duplex-list:num <- push 1, null list <- push 2, list list <- push 3, list run [ stash [list:], list ] trace-should-contain [ app: list: 3 <-> 2 <-> 1 ] ] def to-text in:&:duplex-list:_elem -> result:text [ local-scope load-inputs buf:&:buffer:char <- new-buffer 80 buf <- to-buffer in, buf result <- buffer-to-array buf ] # variant of 'to-text' which stops printing after a few elements (and so is robust to cycles) def to-text-line in:&:duplex-list:_elem -> result:text [ local-scope load-inputs buf:&:buffer:char <- new-buffer 80 buf <- to-buffer in, buf, 6 # max elements to display result <- buffer-to-array buf ] def to-buffer in:&:duplex-list:_elem, buf:&:buffer:char -> buf:&:buffer:char [ local-scope load-inputs { break-if in buf <- append buf, [[]] return } # append in.value to buf val:_elem <- get *in, value:offset buf <- append buf, val # now prepare next next:&:duplex-list:_elem <- next in nextn:num <- deaddress next return-unless next buf <- append buf, [ <-> ] # and recurse remaining:num, optional-input-found?:bool <- next-input { break-if optional-input-found? # unlimited recursion buf <- to-buffer next, buf return } { break-unless remaining # limited recursion remaining <- subtract remaining, 1 buf <- to-buffer next, buf, remaining return } # past recursion depth; insert ellipses and stop append buf, [...] ] scenario stash-empty-duplex-list [ local-scope x:&:duplex-list:num <- copy null run [ stash x ] trace-should-contain [ app: [] ] ]


context:
space:
mode: