←back to thread

Show HN: Term-Lisp – A Lisp, based on pattern matching and term rewriting

(github.com)
83 points boris_m | 1 comments | 06 Nov 24 14:53 UTC | HN request time: 0.211s | source
Show context
BoiledCabbage ◴[06 Nov 24 18:07 UTC] No.42066515[source]▶
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.

replies(3): >>42066655 #>>42066678 #>>42067446 #
llm_trw ◴[06 Nov 24 18:17 UTC] No.42066678[source]▶
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.

replies(1): >>42067199 #
entaloneralie ◴[06 Nov 24 18:45 UTC] No.42067199[source]▶
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.

https://wiki.xxiivv.com/site/pocket_rewriting

replies(1): >>42069293 #
BoiledCabbage ◴[06 Nov 24 20:59 UTC] No.42069293[source]▶
I'm somewhat surprised there isn't a semi-mainstream language for it. It's incredibly simple, with very few core concepts yet very powerful.

Similar to LISP in that sense.

replies(5): >>42069569 #>>42069855 #>>42070879 #>>42071115 #>>42072164 #
alxmng ◴[06 Nov 24 23:21 UTC] No.42071115[source]▶
I think the issue is performance. A true term rewriting system has to essentially operate on text, right?
replies(2): >>42071220 #>>42071290 #
Jtsummers ◴[06 Nov 24 23:30 UTC] No.42071220[source]▶
No, it can operate on a data structure as well. There's string rewriting which does operate on text (but this can be stored in a structure amenable to applying rewrite rules versus brute force copying it or something silly). For term rewriting, there are plenty of efficient ways to store and operate on the information besides just textually.
replies(1): >>42073942 #
alxmng ◴[07 Nov 24 06:18 UTC] No.42073942[source]▶
Hmm maybe I misunderstand. All the rules must be applied to fixpoint or elimination, for every input right? And the larger the program (rule set) the worse the performance since more rules must be evaluated at each “tick” of the program, unless you play tricks with ordering rules.
replies(1): >>42076922 #
1. Jtsummers ◴[07 Nov 24 14:30 UTC] No.42076922[source]▶
Yes, that's often the objective. If they're properly written they will terminate, but not all sets of rules may terminate. It's possible for rules to cause divergence or cycles.

  A -> A B (1)

  A -> B   (2)
  B -> A
(1) never terminates, always adding a new B on application but not removing the A. (2) doesn't grow, but never terminates since each term is replaced with the other.