Backtracking control flow

[aksr]

TECO true beginner here, anyway:

1. run sciteco
2. type, for example, n=
3. Segmentation fault

(Version: r1060.0f740ee)

[rhaberkorn]

Nice catch. Should be fixed now in HEAD. I retriggered a nightly build in case you would like to try one of these.

Let me know of any other problems you encounter. Or ask questions in the "Discussions" section. Or write in the alt.lang.teco newsgroup if you're old-school.

PS: N= is actually nonsensical on a fresh buffer. It does not print anything (= command), but instead starts a search across all buffers for the string =.

[aksr]

I typed something accidentally and got segfault.., then I tried to reproduce it...

Let me know of any other problems you encounter. Or ask questions in the "Discussions" section. Or write in the alt.lang.teco newsgroup if you're old-school.

Thank you, will do.

[rhaberkorn]

I typed something accidentally and got segfault.., then I tried to reproduce it...

Thanks. I appreciate the effort it probably took to reproduce this "something". And I hope you didn't loose any important data.

I am already thinking how to improve test coverage even further. Perhaps I should generate random character sequences (with some heuristics, so they look more like TECO code) and bombard the parser. Let that run in a sandbox (FreeBSD jail) overnight and let's see what happens.

And of course - it's been for ages on TODO - we still need a backup mechanism.

[aksr]

You're carrying here an interesting experiment.

You could/should make an elaborate video in which you demonstrate
(1) speed, (2) efficiency, and some interesting use-cases as to awake a breadth of possibilities with this way of editing.
Something similar what rsc had done with acme editor. It should be carefully thought out...

I'll report every problem I find and I'm gonna try my best to see (and learn) about this editing paradigm...

PS: After discovering a brilliant! SNOBOL4, I'm wondering what else got lost in time...

[rhaberkorn]

You could/should make an elaborate video in which you demonstrate
(1) speed, (2) efficiency, and some interesting use-cases as to awake a breadth of possibilities with this way of editing.

I was hoping to attract some sort of community and that somebody else would do that for me eventually. I am not really into video editing.

PS: After discovering a brilliant! SNOBOL4, I'm wondering what else got lost in time...

I also had that SNOBOL-phase in my life. ;-)

[aksr]

I was hoping to attract some sort of community and that somebody else would do that for me eventually. I am not really into video editing.

Just your regular workflow, should be interesting enough...

I also had that SNOBOL-phase in my life. ;-)

I was hoping it would be just a phase by me.|

Edit: ..it WOULDN'T be...

[rhaberkorn]

Just your regular workflow, should be interesting enough...

Agreed. Will see to it.

I was hoping it would be just a phase by me.

You are doing some serious work in SNOBOL4? I was put off by its goto-based flow control. Never wrote more than a few scripts. (Object) Icon is in principle much more viable, but you know how it is: You can use obscure languages only for your own private projects and even there you have to weigh availability of the software and libraries against your own wishes.

[rhaberkorn]

I thought about writing the "Monkey on a typewriter"-test for SciTECO in CSNOBOL4, but it doesn't cut it either. I need both read-with-timeout (select(), poll()...) and UTF-8 support. That alone restricts me to more mainstream languages like Python or Perl. Perhaps Lua 5.3 with lposix. GNU APL actually has select(). A good chance to put another obscure language into the SciTECO repo! ;-)

Well actually, if I just wrap the calls to sciteco in timeout(1), I could write it in almost any language.

[aksr]

You are doing some serious work in SNOBOL4? I was put off by its goto-based flow control.

Everything I do is serious...at least for me. ;) Especially trivial everyday things with all their idiosyncrasy and my own idiosyncratic use of them, which can be scripted to make life more easy and to be more fun in general.

I caught myself recently doing the same sequence of things, almost daily, at least for a few years now, and it never occurred to me it should/could be scripted.

Unbelievable.

As for the goto in SNOBOL4, now, for me, SNOBOL4-program looks like a kind of dance (not to sound too romantic). :P

It gives a feel of more possibilities than recipe-like procedural languages, since you could in the instant, change the direction of the program to be/go wherever you want it to be/go. Especially with a SNOBOL4s easy, fast to type, in a word—frugal, :S(...)F(...) construct. In that moment it doesn't matter if what you wrote is hard to read or spaghetti code or whatever.

If in something is easy to write, you don't care about readability (of it).

You wanted to script something very fast (usually to elude something very boring), and it's there, it works. If we were honest, much of everyday code which we made and/or use, is not (very) pretty and we don't care since we are not (usually) publishing it and we don't care enough to polish it. It's in a way a throwaway-code which we (ironically) use for years.

In one paper (Rebus — A SNOBOL4/Icon Hybrid), Griswold quotes Mark Emmer (of SPITBOL fame):

Programming languages such as PASCAL, BASIC, C, and Assembler, with their IF . . . THEN . . . ELSE, REPEAT . . . WHILE mentality, are serial, sequential, ploddingly left-brained. [Pattern matching in] SNOBOL4 seems to be parallel, associative, intuitive, right-brained. This is the crux of the matter. Certainly we use our left brain for problem solving, but how many of us really think exclusively in terms of IF . . . THEN . . . ELSE? Imagination, creativity, great leaps of conception seem to originate in the inductive, parallel-functioning right brain. And this is precisely where SNOBOL4s pattern-matching abilities lie.

I think Iain McGilchrist (The Master and His Emissary) would agree with him, and, TBH, I would, too, now. (I wonder what (book?) sources Emmer used to get to this conclusion.) I turned off puritan inside me when I saw (and felt) what is the price.

You can use obscure languages only for your own private projects and even there you have to weigh availability of the software and libraries against your own wishes.

That's true, it depends on how complex project is. I don't build nothing large ATM. I concentrate on books, on content, that's why I need something which handles strings very well... When I first found out (years, years ago) about regular expressions I was amazed, I was struck as by lighting (if you don't mind my epic-like storytelling). I coudn't imagine (for a long time) that there is an another (SNOBOL4s) way to do the same (or something more powerful).

I used C for years dismissing all other languages, but that was ignorant, prejudiced (Perlis was right). I don't care anymore. String handling in C is awful and hard and/or awfully hard.., and time is precious. I was very happy when I learned it, not just that but every other idiosyncratic thing about C..., it feels now as Pyrrhic victory. (We all defend our hard-won knowledge, even though there are better ways to do the same.., that's why we disparage other approaches...[Pike said something similar.]) I love C still, but my love is not exclusive anymore. ;)

BTW, what do you think about sams editor language?

I'm sorry for this long, uncalled-for response.

[rhaberkorn]

You wanted to script something very fast (usually to elude something very boring), and it's there, it works. If we were honest, much of everyday code which we made and/or use, is not (very) pretty and we don't care since we are not (usually) publishing it and we don't care enough to polish it.

Well actually, at the same time, almost every piece of software you will write, is buggy and will have to be fixed. So, "write once" software doesn't really exist. I had my problems understanding and debugging some of my SNOBOL scripts even very simple ones. Nothing would prevent you from supporting both GOTO and structured programming constructs. I mean theoretically, you can restrict yourself to a certain style of GOTO-programming, that is in effect structured, but you never do that.

I think Iain McGilchrist (The Master and His Emissary) would agree with him, and, TBH, I would, too, now. (I wonder what (book?) sources Emmer used to get to this conclusion.) I turned off puritan inside me when I saw (and felt) what is the price.

You will like Icon as they took the backtracking algorithm and generalized it.
I always wondered how a pure backtracking-based language would look like. It needs to undo side effects during backtracking. Languages like SNOBOL, Icon or Prolog restrict that to very small parts of the program state (like the pointer into the matched string). For more, you would need... something like SciTECO's undo stack! For a long time I therefore have the dream of adding SNOBOL-style backtracking to SciTECO in a special execution mode, that essentially eliminates the difference between pattern matching constructs and all regular commands. Imagine the possibilities! Transform your text while you are matching it...

I love C still, but my love is not exclusive anymore. ;)

I use C often because it is kind of the lingua franca of computing. It's everywhere, it's portable, it's rock solid, it has direct access to all OS APIs and the largest number of libraries without any wrappers; and usually it's more flexible than people think. C++ would also tick these boxes due to its C compatibility (more or less), but is just a horrible language. Take SciTECO, sure I could have written it in a number of more hipster-languages like Rust or Zig or Go or whatever, but at the cost of restricting portability, of struggling with poorly written wrappers, with increased memory usage. And some features like it's memory limiting would be impossible at least without some C. I sometimes fear other languages, yes, I fear the bloat, the increased overall complexity of the system. If it's not some kind of experiment or optional script, I'll usually write in C.

BTW, what do you think about sams editor language?

I suppose you mean structural regexp? Can't really say much about that, as I never fully understood it. As a UI, these editors are of course interesting and I appreciate that they tried things differently. I personally do not like heavy mouse-centered approaches, though.

I'm sorry for this long, uncalled-for response.

Never mind, I like this kind of exchange as well. Although private mail or alt.lang.teco, would probably be a better place for it.

[aksr]

I always wondered how a pure backtracking-based language would look like. It needs to undo side effects during backtracking. Languages like SNOBOL, Icon or Prolog restrict that to very small parts of the program state (like the pointer into the matched string). For more, you would need... something like SciTECO's undo stack! For a long time I therefore have the dream of adding SNOBOL-style backtracking to SciTECO in a special execution mode, that essentially eliminates the difference between pattern matching constructs and all regular commands. Imagine the possibilities! Transform your text while you are matching it...

Sounds very, very interesting.., don't forget about it...

I use C often because it is kind of the lingua franca of computing. It's everywhere, it's portable, it's rock solid, it has direct access to all OS APIs and the largest number of libraries without any wrappers; and usually it's more flexible than people think. [...] I sometimes fear other languages, yes, I fear the bloat, the increased overall complexity of the system. If it's not some kind of experiment or optional script, I'll usually write in C.

Just to not be misunderstood: I like it when something is written in C, just ..., it isn't needed for everything. (For some reason I don't like python (ruby...), code looks too sterile for me.)

I suppose you mean structural regexp? Can't really say much about that, as I never fully understood it.

Not just structural regexp in general, but the way it is implemented in sam (even the way it's implemented: 1,$x/.../ x/../ y/../ x/../ c//), even its idioms (Idiomatik). It's a thing of beauty, very powerful. After I learned about it, I found myself thinking about most things through it. (It's contagious in that way.) I wouldn't want for it to be forgotten. Other regexp implementations don't come even close. It's very simple, you just didn't give it a chance ... ;)

As a UI, these editors are of course interesting and I appreciate that they tried things differently. I personally do not like heavy mouse-centered approaches, though.

Neither do I, still, some things are easier with mouse. (They all talk about speed, but it's not as relevant as ensuing fatigue from (continuous) jumping to mouse from keyboard...)

[rhaberkorn]

I wanted to add an error handling facility anyway.
Let's say "E !A! | !B! | !C! '

If branch !A! fails, we will skip to !B! and so on, without backtracking. With a special command or register (or both), you can read the internal SciTECO error code. Voila, we've got "try-catch".

Now let's say, we extend that a bit: :"E !A! | !B! | !C! '

In this construct, we activate undo token generation and keep a stack of macro PCs (program counters) to the beginning of the current branch. When catching an error, we undo till the PC from the stack top and then skip to the next branch. Upon reaching it, we update our macro PC.
Should a branch succeed (not throw any error), we skip till ' and restore the previous parser mode (backtracking or non-backtracking and we must also store that on the stack along with the PC). Should we reach ' in search of the next branch after a failure, the previous parser mode from the stack is restored, the stack pointer decreased and we throw an error, ie. forward the error that caused the branch failing.
Voila! We've got backtracking control flow in SciTECO. You could write context sensitive grammars along with arbitrary modifications of the text - in effect grammars and compilers in one. And it integrates nicely into SciTECO's existing syntax. :-)

[rhaberkorn]

With backtracking constructs, macros turn into named grammar rules. And they will of course take arguments and return values, effectively turning them into feature grammars. Actually every branch can of course return values as well. Logical programming should also be possible that way. Or Icon-style generators. It will be extremely powerful. With the right design, it could be useful in interactive editing as well.

[rhaberkorn]

Thinking some more about it, I realize it's not that easy. Actually, successful backtracking branches must not pop the backtracking stack as it may be necessary to back track into them later on and try another branch (unless we have already reached ' of course). If you use macros as "named" grammar rules, it must be possible to backtrack into already completed macro frames as well. This is not possible in the current design, but may be possible once I manage the macro frames more explicitly (which is planned anyway). The devil lies in the details...

[aksr]

Sounds really, really interesting...

Maybe we should rename this issue: "Backtracking and TECO" or "SNOBOL4 and TECO"?

[rhaberkorn]

I converted it into a discussion.

[rhaberkorn]

Some more brainstorming. How could Icon's "i to j" generator look like in backtracking-TECO:

@^U[ItoJ]{U.j "~0'U.i
  !next! :^E %.i-1 | Q.i-Q.j"< Onext$ ' '
}

Which of course demonstrates another problem: If you we need to backtrack into a macro frame, we would have to restore the macro frame, along with the local Q-Registers and the goto-label-table. So basically, in backtracking mode, the entire macro state must not be freed when a macro returns, but instead transferred to the backtracking stack. This is not even done in interactive mode since you canot rub out part of a macro call - when you rub out Mq, the entire side effect of the macro execution are undone, so SciTECO does not have to store and undo macro frame data.

How could backtracking be useful during interactive usage? Suppose we do a search-replace, but would like to restrict the the places where we replace, without just updating the search pattern or adding complicated if-statements before the search-replace command. This could be solved with Icon-style goal directed programming. Further suppose that that search commands behave differently in backtracking mode and automatically find the next occurrence when backtracking - this could be coded similarly to ItoJ, but is not practical in interactive mode: !next! :"E FRfoo$bar$ | Onext$ ' or 1<:"E FRfoo$bar$ | F< '>
Suppose that's done automatically.
Now, you can check eg. that the line ends with ;: :"E FRfoo$bar$ L2R ::S;$ '
If the anchored search on ; fails, we backtrack into FR and search for the next occurrence of foo.

[rhaberkorn]

btw. commands implemented in C like FR could not internally add backtracking behavior, as is hoped above, since the suggested implementation would completely depend on driving the parser to realize backtracking. That is unless, we allow some kind of "micro macro", analogous to micro programs in CISC CPUs, where built-in commands can internally be implemented as inlined TECO macros. This however would create a whole bunch of its own problems, beginning with error reporting and keeping state of these "micro macros". Even constructing them would be tricky and costly. Alternatively, the SciTECO parser would have to add a byte code phase, which would also complicate everything significantly. I don't think it will be done that way.

[rhaberkorn]

BTW, what do you think about sams editor language?

I read Pike's paper on structural regexp. That would of course be a nice thing to have in SciTECO. And in fact, some of it can be done in TECO with ^S and ^Y (return the length of the last pattern match). I just haven't implemented these commands yet. It is one of the next things I will do!

E.g. Sam's x/{[^}]*}/ g/foo/ c/bar/ could be translated to <S{^EM^N}$; ^YU.tU.f <Q.f,Q.tFRfoo$bar$;>> in SciTECO (once we got ^Y).

Unfortunately, it's not that easy to realize Sam's y// or v// constructs unless you integrate them into the first pattern, exposing more of the underlying PCREs. Or you write a loop that matches character-wise (NOTE: ::S also isn't implemented yet): <::Sdon't match me$"F ::Sbut this one$"S !...! ' ' :C;>

Also, you cannot currently get and use the positions of matched subpatterns (^E[...]). Although that might be prime candidate for overloading ^Y. Suppose that ^Y == 0^Y and returns the buffer positions of the entire matched pattern. 1^Y could give you the first subpattern, etc. TECO-11 didn't have that. But it's nice, I think I will implement that.

[rhaberkorn]

Btw, don't just read, try it in practice. ;)

I tried it a bit, but it's really a torture. Beginning with the total lack of file browsing. The text view is poorly customizable. The command language is underpowered. I mean, it's elegant in a lot of situations - thanks to the implied loops - and sometimes even more elegant than TECO (but not always). It will totally fail in lots of other situations. As far as I can see, there is no scripting. Impossible to do stuff like this.

[aksr]

Customization, at least for p9p sam, is almost nonexistent I give you that.

Have you read this? (just 14 pages): https://doc.cat-v.org/bell_labs/sam_lang_tutorial/sam_tut.pdf

[aksr]

These are some simple examples (from sam quick reference card) of sam usage.

Format selected text: | fmt

Capitalize every word: ,x/[a-zA-Z0-9]+/ -#0;+#1 | tr a-z A-Z

Replace two occurrences of words (word1, word2) with one another:

,x[a-zA-Z]+/{
	g/word1/ v/...../ c/word2/
	g/word2/ v/...../ c/word1/
}

Copy current file to start of the file test.c: ,t "test.c" 0

Go to the 10th column in the current line -/^/+#10

Leave indentation, but replace two or more spaces to one space: ,x/ +/ v/^/ c/ /

Select current paragraph (in roff): -/.PP/,/.PP/-

Also, there are very useful examples of combinations with move m, copy t and mark '

[rhaberkorn]

E.g. Sam's x/{[^}]*}/ g/foo/ c/bar/ could be translated to <S{^EM^N}$; ^YU.tU.f <Q.f,Q.tFRfoo$bar$;>> in SciTECO (once we got ^Y).

That's actually not true. The problem is that FR could change the length of the substring that has been "extracted" - to use Sam's terms - earlier. The example would only work if you find-replace without adding or removing characters.
Therefore I suggest to introduce a construct, that allows you to stash away a part of the current buffer recursively, do operations on it and then replace the the corresponding part of the source buffer. This can actually be done in SciTECO macros M{ and M}:

0U[structs.len]
@^U{{
  "~ !^Y! 0U.f ZU.t |
  U.t "~ .U.f ^E@ES/LINEFROMPOSITION//+Q.t@ES/POSITIONFROMLINE//^EU.t | U.f ' '

  Q.fU[structs.^E\[structs.len].from] Q.tU[structs.^E\[structs.len].to]
  Q.f,Q.tX[structs.^E\[structs.len]] @EQ[structs.^E\[structs.len]]//
  %[structs.len]$
}

@^U}{
  -%[structs.len]"=
    !* FIXME: What if we start from a Q-Register? *!
    Q*U*
  |
    -%[structs.len]$ @EQ[structs.^E\[structs.len]]// %[structs.len]$
  '
  .U..
    Q[structs.^E\[structs.len].from]J
    .-Q.."< :Q[structs.^E\[structs.len]]-Q[structs.^E\[structs.len].to]+Q[structs.^E\[structs.len].from]%..$ '
    Q[structs.^E\[structs.len].from],Q[structs.^E\[structs.len].to]D
    G[structs.^E\[structs.len]]
  Q..J
  !:FQ[structs.^E\[structs.len].] FQ[structs.^E\[structs.len]]!
}

M{ takes a line or buffer range. Without arguments it would default to ^Y (not implemented yet). Once ^Y is implemented, you could write <S{^EM^N}$; M{ <FRfoo$bar$;> M}>. In other words, the code between M{ and M} can be read as "to be applied on the previously matched range". Multiple M{/M} can be nested.

These macros are actually already handy in their current form since often you want to do something on a number of lines as well and it's not always easy to bound that operation, especially once you involve search-replace. (In most other cases, just loop over the lines.)

Once I implement ^Y, I might include this in the standard library.

[rhaberkorn]

Unlike Sam's command language you will not be bound by whatever can be expressed as a regexp, line or character address. You could very well for instance write <S{$; 1U.n .,(<S^E[{,}]$ -A-^^{"=1|-'%.n"=1;'>.)M{ <FR^I$ $;> M}> to iterate all curly balanced braces and replace tab with 4 spaces in them.

[rhaberkorn]

I added ^Y and ^S in the master branch. You can download nightly builds if you want to try it out.

Please read this section in the Wiki about structural patterns: https://github.com/rhaberkorn/sciteco/wiki/Useful-Macros#structural-patterns-apply-operations-to-part-of-buffer

Not as elegant as Sam's language, but certainly more flexible. Is there anything from Sam's command language, I cannot yet model in SciTECO?