Term re-writing systems are a really interesting way of looking at computation.
It completely abstracts away the concept of a machine, and it's simply translation as computation - but equally as powerful.
simplify 3 hours ago [-]
Agreed. This reminds me – and I wonder if it could be applied – to Computational Type Theory, which relies on a similar concept of "reducing" types to their primitive forms, actually taking computation into account (something type theories normally do not!)
It's a shame the standard texts are all 20 years old or more than way too heavy mathematically.
A little book for term rewriting would be a great new addition.
entaloneralie 3 hours ago [-]
Here's a little zine on multiset rewriting(unordered term rewriting), John Conway said(about Fractran in The Book of Numbers) that it is such a simple paradigm of computation that no book is needed to learn it, and it can be taught in 10 seconds.
Mathematica is at least semi-mainstream. Not sure of any other examples though.
lo_zamoyski 3 hours ago [-]
I would argue that it is more "primordial". After all, computation is first and foremost a human activity, generally performed using pen and paper, which involves a good deal of rewriting (computers were originally people). The machine only came later as a way to simulate this human activity. Its meaning is entirely contingent on the primordial notion. It have no meaning on its own.
is that important here? it looks like semantically types as presented are no more than magic constants to match on
llm_trw 3 hours ago [-]
Yes, in term rewriting systems the only thing that matters is the lexical structure of the "program" you're running on top of the transform rules. A simple example of running a TRS is a term of a BNF grammar, a less simple one is a symbolically expanding a term in a computer algebra system.
convolvatron 2 hours ago [-]
ok. sorry, so the issue is not that some of the runtime data is being interpreted as types, its that decisions are being made based on the data and not solely on the structure of the program.
Rendered at 21:33:19 GMT+0000 (Coordinated Universal Time) with Vercel.
It completely abstracts away the concept of a machine, and it's simply translation as computation - but equally as powerful.
This lecture series goes into how it works: https://www.youtube.com/watch?v=LE0SSLizYUI
A little book for term rewriting would be a great new addition.
https://wiki.xxiivv.com/site/pocket_rewriting
Similar to LISP in that sense.
Mathematica is at least semi-mainstream. Not sure of any other examples though.