d66 · HackerTrans

w zeszłym rokudiscuss

It wouldn't be idiomatic Uxntal but there's a relatively simple modification where load/store is from RAM space but jump/pc is from ROM space. For a subset of existing programs it would work fine, although the assembler would need some modifications to make the memory layout(s) a bit clearer.

d66

w zeszłym rokudiscuss

That's a fair point.

A few of us have been discussing a modified Varvara spec that limits the system to a smaller amount of memory (e.g. 32k, 16k, or 8k). I think with a spec like that it would unlock many implementations that are not currently practical.

d66

w zeszłym rokudiscuss

I'm not sure that's true. I have an eZ80-based emulator for the AgonLight2 that is already running well enough to run some real (console-based) ROMs: https://git.phial.org/d6/uxn-ez80/

(I'm new to eZ80 assembly so the project is going slower than it otherwise might.)

The AgonLight2 has 512K of RAM and a 20 MHz CPU which is more than enough for Varvara.

I agree that 8-bit computers of the era (e.g. Pet, Apple 2, C64, TI/99a, etc.) don't have enough RAM to give Varvara its own 64k of memory (though it wouldn't be hard to design a Varvara variant with a smaller memory space) but otherwise there really aren't major barriers. As far as permacomputing goes though, there are plenty of hosts out there with enough memory to comfortably run Varvara (anything 32-bit will be fine, most 16-bit computers would also be fine).

Based on my eZ80-based implementation I think any of the eZ80-based TI calculators with 128k or more of user-accessible memory could implement Varvara without major problems.

d66

2 lata temudiscuss

There's no requirement that stacks grow upwards in Varvara.

If your stacks grew downwards then you could use LE instructions to operate on 16-bit values on the stack. You'd still need to support loading from BE memory into the LE stack but that might not be too bad (two 8-bit operations instead of one 16-bit operation).

The device ports are also specified as BE so in theory you'd need to split those reads/writes up too. However, in almost all cases those are done directly from the stack values so I bet most ROMs would work fine with LE devices and LE stacks. LE devices would only cause issues when someone used 8-bit reads/writes from part of a 16-bit port.

d66

3 lata temudiscuss

yes, that is the actual construction: the disjunction data type only supports a lhs and rhs, so that is the only possible way to represent it.

i wrote it the way i did for clarity in the comments.

d66

3 lata temudiscuss

  negation (~α): strings not matched by α
  difference (α - β): strings matched by α but not β
  intersection (α & β): strings matched by α and β
  exclusive-or (α ^ β): strings matched by α or β but not both
  inclusion (α > β): does α matches all strings β matches?
  equality (α = β): do α and β match exactly the same strings?

d66

3 lata temudiscuss

you're right. inclusion/intersection/etc. aren't actually computed via DFA but instead are computed directly on the regular expression representation itself. and large disjunctions (with 256 branches) are what is very heavy.

(it's possible to instead do these operations on DFAs but at the time i found it hard to get from an automata back to a reasonable-looking regular expression.)

d66

3 lata temudiscuss

the library uses a fairly simple data representation where x{m,n} is compiled using conjunction and disjunction. so x{1,4} ends up being represented as x|xx|xxx|xxxx.

this simplifies the code for testing equality and inclusion, since logically x{n} is just xx... (n times) and x{m,n} is just x{m}|x{m+1}|...|x{n}.

but when you have x{m,n} and n-m is large you can imagine what kind of problems that causes.

d66

3 lata temudiscuss

interesting!

what would [ab]* be? for computing an ordinal number the only real difficulty is how to handle kleene star: given ord(X) how do we calculate ord(X*)?

but as you probably noticed i'm a bit out of my depth when dealing with ordinals.

d66

3 lata temudiscuss

expressions like (...){1,256} are very heavyweight and the scala JS code ends up timing out or crashing the browser.

if you replace that with (...)+ then it seems to work (at least for me). smaller expressions like (...){1,6} should be fine.

d66

3 lata temudiscuss

normally you would use an ordinal number [1] to label individual elements of an infinite set while using a cardinal number [2] to measure the size of the set.

i believe the cardinality of a set of words from a finite alphabet (with more than one member) is equivalent to the cardinality of the real numbers. this means that the cardinality of .* is c.

unfortunately, i don't think that cardinality gets us very far when trying to differentiate the "complexity" of expressions like [ab]* from ([ab]*c[de]*)*[x-z]*. probably some other metric should be used (maybe something like kolmogorov complexity).

[1] https://en.wikipedia.org/wiki/Ordinal_number

[2] https://en.wikipedia.org/wiki/Cardinal_number

d66

3 lata temudiscuss

the page actually does give these. for α := [a-z]{2,4} the page gives |α| = 475228.

however, as others have pointed out any non-trivial use of the kleene star means the result will be ∞. in this case the page will list numbers that roughly correspond to "number of strings with N applications of kleene star" in addition to infinity.