Which leads to data structures in 01_. The only data type in 01_ is the list of bits, and only pattern matching and list concatenation are the available operations. Higher-level data structures can be built on that, and that's what I'm writing about.
I had an idea on how to make lists of arbitrary (finite) data. However, 01_ programs can deal with infinite bit lists, so I came up with an idea on how to make a stack of potentially infinite bit lists as well.
An 01_ interpreter would need some dictionary datatype, so association lists can be built on top of the lists. One way would be to use nested lists. Another would be to use a pair of lists.
List of arbitrary finite data
The scheme uses a control bit, where 1 means a data bit follows, and there are more bits, and 0 means the end of the list.
== first item in the list
head 0. = _.
head 11rest = 1 head rest.
head 10rest = 0 head rest.
head _ = _.
== the list with the first item removed
tail 0rest = rest.
tail 11rest = tail rest.
tail 10rest = tail rest.
tail _ = _.
== the list with a new item added to the front (or end)
add data list = list-encode data list.
add-to-end data list = list list-encode data.
list-encode _ = 0.
list-encode 1x = 11 encode x.
list-encode 0x = 10 encode x.
Stack of potentially infinite lists
Let n = the number of items in the stack. The stack data structure starts with n 1s, followed by a 0, followed the stack data.
The stack data starts with the first bit of every item in the stack, followed by the second bit of every item in the stack, followed by the third bit, etc.
Each stack bit starts with the control bit for the top bit in the top item in the stack, where a 1 is followed by the data bit of the item, and a 0 means the item has no more bits, which is followed by next item in the stack, etc all the way to the bottom of the stack.
This implementation would undoubtedly be hugely inefficient. When dealing with the largest item yet to be in the stack, the entire history of operations on the stack will have to be unwound for the rightmost bits. The 1 item optimization in pop helps a little by limiting the history that has to be unwound to the last time the stack was empty.
== new empty stack
empty = 0_.
== number of items in the stack (in base 1)
stack-count 0stack = _.
stack-count 1stack = 1 stack-count stack.
drop-stack-count 0stack = stack.
drop-stack-count 1stack = drop-stack-count stack.
== top of the stack
top 0. = _. == stack underflow
top stack =
top' decrement-count stack-count stack
drop-stack-count stack.
top' count 0stack-data = _.
top' count 10stack-data =
0 top' count
drop-stack-bit count stack-data.
top' count 11stack-data =
1 top' count
drop-stack-bit count stack-data.
decrement-count 1count = count.
drop-stack-bit _ stack-data = stack-data.
drop-stack-bit 1count 0stack-data = drop-stack-bit count stack-data.
drop-stack-bit 1count 10stack-data = drop-stack-bit count stack-data.
drop-stack-bit 1count 11stack-data = drop-stack-bit count stack-data.
== returns stack with data pushed on top
push data stack =
1 stack-count stack 0
push' data count drop-stack-count stack.
push' _ count stack-data =
0 take-stack-bit count stack-data
push' _ count drop-stack-bit count stack-data.
push' 0data count stack-data =
10 take-stack-bit count stack-data
push' data count drop-stack-bit count stack-data.
push' 1data count stack-data =
11 take-stack-bit count stack-data
push' data count drop-stack-bit count stack-data.
take-stack-bit _ . = _.
take-stack-bit 1count 0stack-data = 0 take-stack-bit count stack-data.
take-stack-bit 1count 10stack-data = 10 take-stack-bit count stack-data.
take-stack-bit 1count 11stack-data = 11 take-stack-bit count stack-data.
== returns stack with the top item popped
pop 0. = 0_. == stack underflow
pop 10. = 0_. == 1 item optimization
pop 1stack =
stack-count stack 0
pop' stack-count stack
drop-stack-count stack.
pop' count 0stack-data =
take-stack-bit count stack-data
pop' count
drop-stack-bit count stack-data.
pop' count 10stack-data =
take-stack-bit count stack-data
pop' count
drop-stack-bit count stack-data.
pop' count 11stack-data =
take-stack-bit count stack-data
pop' count
drop-stack-bit count stack-data.
Association lists
For implementing association lists, a pair of lists would be more efficient, but more complicated and error-prone to use than nested lists. I'll include implementations of both, but I'd probably use a pair of lists.
Association list using nested lists.
lookup key alist = try-lookup key head alist lookup key tail alist.
lookup . _ = _.
try-lookup key pair fail = if-equal key head pair head tail pair fail.
add-alist key data alist = add add key add data _ alist.
Association list using a pair of lists.
lookup key klist dlist =
if-equal key head klist head dlist lookup key tail klist tail dlist.
lookup . _ . = _.
They both use if-equal, defined here.
if-equal 0x 0y true false = if-equal x y true false.
if-equal 1x 1y true false = if-equal x y true false.
if-equal _ _ true . = true.
if-equal . . . false = false.
More association lists
These will use a pair of lists, one for the keys, and one for the data.
== test if key is present
if-has-key key _ true false = false.
if-has-key key klist true false =
if-equal key head klist true if-has-key key tail klist true false.
== append to data associated with key
append-alist key data klist dlist =
if-has-key key klist
append-alist' key data klist dlist
add data dlist.
append-alist' key data klist dlist =
if-equal key head klist
append-alist-matching data dlist
append-alist-nonmatching key data klist dlist.
append-alist-matching data dlist =
add add-to-end data head dlist
tail dlist.
append-alist-nonmatching key data klist dlist =
head dlist
append-alist' key data tail klist tail dlist.
append-alist-key key klist =
if-has-key key klist
klist
add key klist.
No comments:
Post a Comment