News for hackers. Stuff that matters.

c0nstantine

Re:Ask HN: What are you working on? (May 2025) on Monday May 26, 2025 @02:21PM (#44100099)
Working on trre - extension of regex for text editing. I'm redesigning the underlying engine to operate on deterministic automata (transducers) for most expressions. Theoretically, it should outperform AWK in complex text-processing tasks.

https://github.com/c0stya/trre

I have a minimalistic one (7 lines in Python) using convolutions:

https://c0stya.github.io/articles/game_of_life.html

### The code ###

  import numpy as np
  from scipy.signal import convolve2d

  field = np.random.randint(0, 2, size=(100, 100)) # 100x100 field size
  kernel = np.ones((3, 3))
  
  for i in range(1000): # 1000 steps
      new_field = convolve2d(field, kernel, mode="same")
      field = (new_field == 3) + (new_field == 4) * field
Re:Show HN: Transductive regular expressions for text editing on Tuesday February 11, 2025 @02:16PM (#43017036)
Thank you for your feedback. There is a bunch of deterministic methods to infer regex from samples (positive and negative). There are ml-based as well. But it is a different story.
Re:Show HN: Transductive regular expressions for text editing on Monday February 10, 2025 @01:50PM (#43003701)
Let me know if you need any help. Not it is still raw but I hope I'll polish it soon.
Re:Show HN: Transductive regular expressions for text editing on Monday February 10, 2025 @11:31AM (#43002116)
Hi. Missed your message initially. Helix is a great project. Let me know if/how I can help. The trre is a bit raw. But hope I can polish it within a month or two.
Re:Show HN: Transductive regular expressions for text editing on Monday February 10, 2025 @02:03AM (#42997642)
Did it solve the problem? I guess the issue is the process substitution construction of bash "<()". Not all shells support this.
Re:Show HN: Transductive regular expressions for text editing on Sunday February 09, 2025 @06:37AM (#42990025)
Epsilon injection appears whenever right or left side of ':' has no operand. E.g.

(:a)

(a:)

a:|b

a|b:

etc

I will try to change the precedence and see how it works. Btw what do you think about explicit operators '>' '<' where '<' works as usual regex matcher, and '>' as a generator. For example to change 'cat' to 'dog' there could be something like '<cat>dog' where '<cat' part is a parser and '>dog' is a generator. Thanks.

Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @02:22PM (#42985442)
Thank you for the detailed comment.

So Unicode is something on a top of my TODO list. Boundaries is a very interesting topic. Maybe I'll extend the doc to include the details.

> what's your driver? curiosity? or some itch?

It's an itch :). 8 years ago I explored automata theory and found finite transducers to be a handy and natural way to transform texts. And as regex corresponds to FSA (finite state acceptors) I wanted to create a language that corresponds to FST (finite state transducers). There is a lesser-known algorithm for FST determinization and I want to applied it to make the transformation fast and efficient. It turned out to be not that simple as I expected initially.

Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @02:07PM (#42985326)
I agree with the point that precedence is arbitrary. The current version looks like this:

1 Escaped characters

2 []

3 ()

4 * + ? {m,n}

5 :

6 . (implicit concatenation)

7 |

I have some reasons to put it that way. I want : to be somewhat 'atomic'. If you think about '*' or '+' they can be lower in the table as well. Anyway, I will try to put : lower in the next version and see how it goes.

Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @09:58AM (#42983330)
Thank you for doing my work! :)
Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @09:57AM (#42983325)
Hi,

If I understand it correctly you want to change something inside the "..." block and change the quotas to single '.

It can be done by this expression:

echo '"hello world" "hello again!"' | ./trre "\":'.+?:-\":'"

'-' '-'

So I substitute the text inside "" by symbol - using this expression ".+?:-" and simultaneously changing the surrounding quota.

Question mark means non-greedy mode.

Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @09:35AM (#42983192)
Oh, I've learnt a lot. Initially wanted to complete the whole project in two weeks and it took a few months. The hardest part was the DFT determinization algorithm design.

Thanks for your feedback!

Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @05:59AM (#42982090)
The right side is a normal regex language syntactically. Semantically it is a generator instead of a parser (consumer).

But I got your point. Maybe there could be some ways to do it in consistent way. Just straight tr-like syntax won't work, e.g I really want it something like this to be valid:

[a-b]:(x|y) (pairs a:x, b:x, a:y, b:y)

and I prefer not handle these in some ad-hoc way.

Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @05:01AM (#42981873)
Thank you! Still a lot of work to do. I really like the jq style.
Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @04:59AM (#42981866)
The grammar is underspecified. The full grammar is more complex. I guess I need just remove the current version from docs. Now it is confusing indeed.

> Why is "c" not being replaced with "da"?

It is all about precedence. According to the discussion I think I've chosen a wrong one and it raises confusion. Current version of precedence table is this:

| 1 | Escaped characters | \<special character> | | 2 | Bracket expression | [] | | 3 | Grouping | () | | 4 | Single-character-ERE duplication | * + ? {m,n} | | 5 | Transduction | : | | 6 | Concatenation | . (implicit) | | 8 | Alternation | | |

So the ':' is stronger then '.' (implicit concatenation).

Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @04:53AM (#42981833)
The '-g' flag is obsolete. Somehow it got into my new docs. The right way is to use '-ma' flags where '-m' is for matching the whole string and '-a' stands for all the outputs.

You got the idea correctly. E.g. to generate all strings of length 5 over alphabet 10 (and truncate to 10000) you can do:

echo '' | ./trre -am ':[a-c]{5}' | head -n 1000

The docs are fixed now. Thanks for pointing this out.

The infinite generators is something nice to have, I agree. Just didn't wrap my hand around how to do this in 'ergonomically' correct way.

Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @02:32AM (#42981202)
That's true. Thank you for elaborating.

There is a hidden operator of concatenation as for usual regular expressions. In the code I denote it as lower dot '.' (as in the old Thompson's implementation).

Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @02:28AM (#42981181)
[a-z] is equivalent to 'a|b|...|z' in the normal regex language.

So if we do [a-z]:[A-Z] it should be expanded to:

(a|b|...|z):(A|B|...|Z)

which is pretty legal in trre but has different meaning of mapping any a-z to ALL the A-Z (generating A-Z on each occurrence of lowercase letter).

Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @01:56AM (#42981023)
Thank you for the link. I think I came across it some years ago. They implement weighted transducers. Nice tool for things like morphology from the era before the LLMs. I've implemented something similar 8 years ago: https://github.com/c0stya/fslib
Re:Show HN: Transductive regular expressions for text editing on Saturday February 08, 2025 @01:52AM (#42981009)
I guess folks generally more interested in searching for the pattern then modifying it.

> Tools like sed build a transducer around the whole automaton: s/this/that/g.

That sounds reasonable. Could you provide any links on sed internals? Thanks.

Re:Show HN: Transductive regular expressions for text editing on Friday February 07, 2025 @02:39PM (#42976603)
Hey, I didn't claim it is something groundbreaking. The idea is quite old, indeed. You don not need AI or LLMs here.

The sed is superior, actually. I do not cover all the functions sed provides. I think of it more like 'tr' + regexp. But it has different underlying engine and might be faster and more expressive for some use cases (e.g. tokenization, morphology).

Re:Show HN: Transductive regular expressions for text editing on Friday February 07, 2025 @02:29PM (#42976501)
Are you using MAC? For tests please try:

$ make && bash test.sh

with 'bash' instead.

For the second part it is a bug in the README. Thank you for pointing this out! I had to be more careful before the publication. Fixed. Try '-ma' flags instead.

$echo '' | trre -ma ':(0|1){,3}?'

Re:Show HN: Transductive regular expressions for text editing on Friday February 07, 2025 @02:18PM (#42976368)
Thank you for the feedback. Yes, the precedence is a question for me. Maybe I will change this.

If I shift it behind concatenation there could be another problem. E.g. with non-associative : should be illegal. And I am not sure how to treat this:

cat:dog:mouse

In the current version I inject the epsilon (empty string). It looks natural E.g. to remove every second letter I could run '..:' which is technically '.(.:eps)':

echo 'abcde' | ./trre '..:'

result: 'ace'

actually ':' association could have a meaning as a composition of regular relations; but I found it too complicated for now.

Re:Show HN: Transductive regular expressions for text editing on Friday February 07, 2025 @01:42PM (#42975997)
Can't reproduce.

I have the following:

> echo 'cat dog' | ./trre 'c:bat|d:hog'

bat hog

Re:Show HN: Transductive regular expressions for text editing on Friday February 07, 2025 @01:39PM (#42975972)
>> E.g. what if I want to turn xyz into zYx?

echo 'zyx' | ./trre 'xy:Yz|zy:Yx'

It is still a regular language. I do not introduce references.

You are right in sense the `sed` is far superior editor. But here I see some advantages: - the current implementation is super small; it is direct translation to an automaton - the complex patterns may be compiled in a more efficient way using deterministic transducer. I can't defend this claim now but I have some evidences - there are some tricks you can do using 'generative' part of it, e.g. and you even can find levenshtein distance of 1 between two strings just by generating substitutions/insertions/deletions and implement a simple spell checker.

Overall, I think you have a good point. Maybe it is just marginal improvement (if any). It was more comfortable to write in this style instead of group usage. I used it for some time and found it handy (especially as extended `tr`).

Re:Show HN: Transductive regular expressions for text editing on Friday February 07, 2025 @01:12PM (#42975658)
Thank you! For the feedback and pointing to the typo. Fixed. Actually my C is very rusty and I am bit uncomfortable about this.
Re:Show HN: Transductive regular expressions for text editing on Friday February 07, 2025 @01:06PM (#42975606)
yeah. Transducers are very old topic. For some reason they were not connected to a specific language like regex.

> wrt syntax, are you sure you want ':' to bind stronger than concatenation 'ab' ?

That's something I am still not sure about. I took a hundred examples and it looked more natural this way (: lower then .). But I can change it with the change of one digit in the code, literally. That's why I'm posting here. I need some real feedback.

Re:Show HN: Transductive regular expressions for text editing on Friday February 07, 2025 @01:00PM (#42975543)
Fair point. I agree. Now it is better to disable it.

The rationale was to implement a fun operation called transducer composition. It is possible to do simple operation on strings and compose trre's like filters. But I haven't finished it yet. So again, a fair point.

Re:Show HN: Transductive regular expressions for text editing on Friday February 07, 2025 @12:54PM (#42975468)
Fair point. The most explicit example if you need to change something in context. For example if we need to change 'y' to 'Y' only if it occurs between x and y you would do something like this in python.

pattern = r'(x)y(z)'

replacement = r'\1Y\2'

result = re.sub(pattern, replacement, text)

I would like to replace it with 'xy:Yz' pattern:

result = re.trre('xy:Yz', text)

If you need your x, z to be more complicated patterns or even regex themselves it can be more handy using this approach.

Re:Show HN: Transductive regular expressions for text editing on Friday February 07, 2025 @11:37AM (#42974625)
The second line actually is an output. I've modified the README. The last example is a typo. Fixed. Thanks!

Older »