8 ms·
Stream Ring Theory – A Turing-Complete Stream Algebra
- petters 8y agoAuthor is "Captain S/V Red Herring". I thought it strange that he would start by defining what a ring is, but I am not familiar with the intended audience.
- MeteorMarc 8y agoMarko Rodriguez is one of the main authors of Apache TinkerPop [http://tinkerpop.apache.org/ http://tinkerpop.apache.org/]. This paper is the theoretical groundwork for future, more efficient implementations of the gremlin traversal machine, as appears from the last sentence of the paper: "In general, the algebra can be used to develop both languages and underlying execution systems that are functional, universal, and can be reasoned on algebraically."
- okram 8y agoI wrote the paper for technically savvy individuals who are not versed in abstract algebra. While writing the first 5 pages, I constantly asked myself: "Will my mom be able to follow what I'm saying?" Fortunately, after reading it, she said: "I get the general idea." At page 5, the stream ring is defined as a product of the coefficient ring and the function ring and from there, the notation gets heavy and there was little I could do. Hopefully by building confidence in the reader up to page 5, they would have the patience to forge ahead because the true nuggets of value are in the latter parts of the article. Finally, to the "Captain" comment -- this article was written while in the Sea of Cortez aboard the S/V Red Herring: http://svredherring.com http://svredherring.com and https://twitter.com/SV_RedHerring https://twitter.com/SV_RedHerring.
- graycat 8y agoI can't read the Web page: If I have Firefox magnify the page, then much of the text is off the screen and with no horizontal scroll bars to put it on the screen. Without magnification, I'd need a strong magnifying glass to read the page character by character. I studied abstract algebra, including groups, rings, fields, Galois theory, integral domains, vector spaces, modules, wrote my honors paper on group representations, etc. so would like to see what benefit ring theory has for software.
- skilesare 8y agoAre these streams polynomials that can be used I. Zks(nt)arks?
- slack3r 8y agoClassic case of math envy. Ha ha ..
- okram 8y agoA colleague of mine who gets confused by "all the symbols" said that they appreciated the verbose stream notation that I build throughout the article. I would recommend giving the article a earnest try up through to page 5. Then after that, jump to page 17 and read Section 5C on Set Operations. See if the standard concepts of union, intersection, difference, etc. mixed with the verbose stream notation gives you insight and ultimately, the confidence to keep trying to tackle the work.
- slack3r 8y agosed is already Turing-complete (https://catonmat.net/proof-that-sed-is-turing-complete https://catonmat.net/proof-that-sed-is-turing-complete). I'm not sure how what you are proposing is any better than sed. I said math envy since you resorted to using algebraic ring theory when there was a much simpler solution. xD
- okram 8y agoThere are many Turing Complete languages. There are many stream-based languages. Moreover, there are many Turing Complete stream-based languages. These are instances of the presented stream ring algebra. I wanted to understand the foundation of such languages so as to have the algebraic toolkit to generate more instances.
- nimish 8y agoInteresting but there's a lot of literature in Haskell especially on streams and fusion thereof already, so I'm surprised that the references doesn't include a review of the existing state of the art.
- okram 8y agoI wrote the article on a boat with only an abstract algebra book, a LISP book, and a few articles that I had printed before I left. Thus, my references are my references. To then go back and back fill with references would not be an accurate representation of what I was truly referencing at the time. But yes, there is a lot of related work out there. Hopefully, my approach and introduced novelties can inspire in a way others have not.
- alexott 8y agoJust out of curiosity - what Lisp book it was?
- okram 8y agoIt was this book https://www.amazon.com/Common-LISP-Language-Second-Steele/dp/1555580416 https://www.amazon.com/Common-LISP-Language-Second-Steele/dp... by Guy Steele, but it had a different cover. It was silver with a 1980s like computer font on it.
- nimish 8y agoThat's fair, and I commend the effort. That said, there's richer structures: https://www.sciencedirect.com/science/article/pii/S0304397599003229 https://www.sciencedirect.com/science/article/pii/S030439759... and for the typing theorists streams are a canonical example of codata.
- okram 8y agoI read the article you recommended. It is interesting in that the authors include feedback to simulate loops and have explicit split and merge operators, where their + operator is used to create tuples in the stream. The text is dense so I haven't fully grocked their purpose, but it is nice to see the same concepts presented in a different formalism. If you have other links, please send them along.
- xiaodai 8y agoOh wow. There is so much pure maths that has applications in computer science. Loved my algebra courses in pure maths!