Stack-consumption-on-error headscratch in comparison to other `dc`s

[exikyut]

Was just playing around and happened to get my stack out of sync:

1
+

Runtime error: stack has too few elements
    0: (main)

But I noticed this cleared the stack:

f
(no output)

Trying to improve my edge-case-fu spidey sense :) I thought I'd check how other dc implementations behave.

GNU dc immediately showed me something might be up:

1
+
dc: stack empty
f
1
q
$ _

Huh.

OpenBSD dc produced byte-identical output to the above.

OK... what should arbitrate as reference here? I guess some form of going back to the beginning.

How far can we go back?

Apparently the first version of dc was written in B while UNIX was being ported. Man that would be fun to play with. Perhaps there's a printout of it starting on page 9,576 of an OCR-averse PDF on bitsavers just waiting to be found :smile:

http://takahirox.github.io/pdp11-js/unixv6.html and http://pdp11.aiju.de/ both emulate UNIX v6 in-browser, which is nice and accessible. The dc in both of these has the same size and timestamp; copying from the second emulator for fun, which emulates an uppercase teletype, we get:

# DC
1
+
( +) ?
F
1
Q
# # 

Hrm. That's V6 UNIX. Can we go further back?

Yes and no, as far as I can manage.

It looks like a V1+V2 amalgamation was put together using surviving source code and tape dumps: https://www.in-ulm.de/~mascheck/various/ancient/

The project appears to have been quietly migrated to https://github.com/DoctorWkt/unix-jun72, with terrifying instructions to "now run make" underneath a wall of "last modified: 16 years ago" :melting_face:, but I discovered some pre-built SIMH images at https://code.google.com/archive/p/unix-jun72/downloads, which is where the project previously lived (and is what the page in the previous paragraph links to), which still work perfectly - you just run pdp11 simh.cfg.

Unfortunately, while the system is already saying :login: before you can even blink and figure out whether it worked, and the distribution includes dc, its f command appears to be broken... even though I see references to support for an f command on line 949 in dc1.s (the source is distributed across dc2.s, dc3.s, dc4.s and dc5.s, presumably due to memory constraints). I'm not sure if I'm falling through a default: exit(0);, a segfault, or a case of mismatching binary/source.

The path forward there would be figuring out how to recompile the dc implementation; I think this might be possible but it's beyond the scope of the cursory level of interest I approached this with.

If anyone wants a rainy day project, I would be really interested to learn more about the result of others' digging around to get the earliest surviving copies of dc running.

Zooming back out to the topic, it would seem that current consensus is that errors of this type don't consume the stack; they leave it alone. But it would be nice to formally qualify this situation better. How should that be framed? Parser consumption expectations? Stack effects by errors in general?

This bugreport is somewhat of a thought experiment. I don't have any authoritative ideas or suggestions myself.

[gavinhoward]

Thank you for digging up the history!

You are correct that my dc clears the stack. When I was implementing bc and dc, I wanted to minimize the possibility that an error could screw up code later.

Hence, my bc and dc both "reset" on error, which means they clear everything and try to start completely fresh.

That said, the documentation could be clearer on that; I could make it say that errors clear the stack too. (And they do clear the stack because they have to clear the stack in bc since the stack is implicit.)

However, this could go both ways:

• I could declare this as a mere documentation bug, since dc is not standardized. In that case, I would just update the manual.
• Or I could declare this a conformance bug, because while there is no standard, all other dc implementations do the opposite. In this case, I would make the change and fix the bugs that pop up.

Quite frankly, I'm not looking forward to doing a full release cycle, which includes 2 weeks of fuzzing (during which my machine is unusable) and 24 hours of tests, possibly repeated. This means I want to fix the docs and call it a day, but going off of what I want to do is not rational.

I don't know if anyone watches this repo, but this is one case where I'd like to hear comments from users.

[exikyut]

You are correct that my dc clears the stack. When I was implementing bc and dc, I wanted to minimize the possibility that an error could screw up code later.

Hence, my bc and dc both "reset" on error, which means they clear everything and try to start completely fresh.

Huh. That makes pedagogical sense, upon consideration.

That said, the documentation could be clearer on that; I could make it say that errors clear the stack too.

That would probably be a good idea, both because gh-dc deviates from the norm, and because there is no norm; this would be the first point at which this particular graph edge / state machine transition is properly documented. Until now it's lived as an edge case in UB land.

(And they do clear the stack because they have to clear the stack in bc since the stack is implicit.)

Huh. I wonder how other bc->dc architectural approaches have handled this situation?

However, this could go both ways:

• I could declare this as a mere documentation bug, since dc is not standardized. In that case, I would just update the manual.
• Or I could declare this a conformance bug, because while there is no standard, all other dc implementations do the opposite. In this case, I would make the change and fix the bugs that pop up.

Quite frankly, I'm not looking forward to doing a full release cycle, which includes 2 weeks of fuzzing (during which my machine is unusable) and 24 hours of tests, possibly repeated. This means I want to fix the docs and call it a day, but going off of what I want to do is not rational.

Good net question. Hmm.

I don't know if anyone watches this repo, but this is one case where I'd like to hear comments from users.

I am too.

But I'll add my 2¢:

• Nobody has screamed until now, but gh-dc adoption is still rising.

• Taking on the complexity of making this a ./configureable option doesn't sound reasonable in practice.

• I can only imagine a dc script generating different results after being switched to this implementation after some sort of upgrade process that presumably has capable humans involved in it. It would follow that said humans would presumably classify the deviation in output as the result of logic bugs and then fix them, so keeping this architectural approach is theoretically a net positive.

• Applying to make dc a POSIX standard would make for an interesting 180-season TV series that would be excellent mid-afternoon watching while having a nap (and dreaming of how to make dc count to infinity twice). I'd definitely seed all 4,961 episodes.

• Given that gh-dc is now in FreeBSD, it may well meet the theoretical/implicational interpretation (and possibly beyond) of "significant user base" required to apply for OSS-Fuzz which would subject it to continual analysis and, if accepted, probably provide a slow trickle of genuinely interesting feedback. It also sounds like it would unblock a significant burnout barrier to commoditizing the process of cutting new releases - opting to letting new versions sit in OSS-Fuzz for a fortnight before releasing them (a cool strategy, and if only everything was architecturally simple enough that this could be applied everywhere) would no longer have a local performance impact.

[gavinhoward]

Nobody has screamed until now, but gh-dc adoption is still rising.

Yes, I agree. In fact, I initially wanted to dismiss your report as "only one user," but I did not for this reason.

Taking on the complexity of making this a ./configureable option doesn't sound reasonable in practice.

I do not want that to be a build-time option. I have too many as it is.

I can only imagine a dc script generating different results after being switched to this implementation after some sort of upgrade process that presumably has capable humans involved in it. It would follow that said humans would presumably classify the deviation in output as the result of logic bugs and then fix them, so keeping this architectural approach is theoretically a net positive.

True, although people would be better served to switch to bc since it's standard and portable.

Applying to make dc a POSIX standard would make for an interesting 180-season TV series that would be excellent mid-afternoon watching while having a nap (and dreaming of how to make dc count to infinity twice). I'd definitely seed all 4,961 episodes.

The rationale in the bc standard says these two things:

dc was not selected to be part of this volume of POSIX.1-2017 because bc was thought to have a more intuitive programmatic interface.

The consensus of the standard developers was that dc is a fundamentally less usable language and that that would be far too severe a penalty for avoiding the issue of being similar to but incompatible with C.

Yes, that is from the 2017 standard, but that language goes back to the beginning, I believe. This means that standardizing dc will not happen, barring some rich fellow deciding that it's his life mission to make it happen.

Given that gh-dc is now in FreeBSD, it may well meet the theoretical/implicational interpretation (and possibly beyond) of "significant user base" required to apply for OSS-Fuzz which would subject it to continual analysis and, if accepted, probably provide a slow trickle of genuinely interesting feedback. It also sounds like it would unblock a significant burnout barrier to commoditizing the process of cutting new releases - opting to letting new versions sit in OSS-Fuzz for a fortnight before releasing them (a cool strategy, and if only everything was architecturally simple enough that this could be applied everywhere) would no longer have a local performance impact.

I agree with this, so I have applied. We'll see where that goes.

[exikyut]

Nobody has screamed until now, but gh-dc adoption is still rising.

Yes, I agree. In fact, I initially wanted to dismiss your report as "only one user," but I did not for this reason.

(Sentiment of appreciation)

Taking on the complexity of making this a ./configureable option doesn't sound reasonable in practice.

I do not want that to be a build-time option. I have too many as it is.

I was genuinely surprised at the number of configurable options :) completely agree there haha

I can only imagine a dc script generating different results after being switched to this implementation after some sort of upgrade process that presumably has capable humans involved in it. It would follow that said humans would presumably classify the deviation in output as the result of logic bugs and then fix them, so keeping this architectural approach is theoretically a net positive.

True, although people would be better served to switch to bc since it's standard and portable.

Applying to make dc a POSIX standard would make for an interesting 180-season TV series that would be excellent mid-afternoon watching while having a nap (and dreaming of how to make dc count to infinity twice). I'd definitely seed all 4,961 episodes.

The rationale in the bc standard says these two things:

dc was not selected to be part of this volume of POSIX.1-2017 because bc was thought to have a more intuitive programmatic interface.

Thanks for the TIL! I should have expected there to be extant discussion on the matter...

The consensus of the standard developers was that dc is a fundamentally less usable language and that that would be far too severe a penalty for avoiding the issue of being similar to but incompatible with C.

Yes, that is from the 2017 standard, but that language goes back to the beginning, I believe. This means that standardizing dc will not happen, barring some rich fellow deciding that it's his life mission to make it happen.

I see. Thanks very much for the insight.

Given that gh-dc is now in FreeBSD, it may well meet the theoretical/implicational interpretation (and possibly beyond) of "significant user base" required to apply for OSS-Fuzz which would subject it to continual analysis and, if accepted, probably provide a slow trickle of genuinely interesting feedback. It also sounds like it would unblock a significant burnout barrier to commoditizing the process of cutting new releases - opting to letting new versions sit in OSS-Fuzz for a fortnight before releasing them (a cool strategy, and if only everything was architecturally simple enough that this could be applied everywhere) would no longer have a local performance impact.

I agree with this, so I have applied. We'll see where that goes.

YOU GOT ACCEPTED :D :face_holding_back_tears:

I forgot that it ships in macOS, and TIL it ships in Android as well. OSS-Fuzz's scope tries to extend beyond Google-immediate interests, so this broader status quo (incl. FreeBSD) constitutes a meaningful precedent of relevance – potentially represented by the speed with which the project was accepted without further question (basically 45 minutes).

[gavinhoward]

YOU GOT ACCEPTED :D 🥹

Yes, unfortunately, I ran into problems integrating fuzzers, and I don't know what to do next, so I have to put OSS-Fuzz on the back plate. Thus, we're back to where we started.

Thank you for the suggestion, though.

[spatula75]

I also noticed this behavioral change, because on occasion I need to add a long list of numbers in dc, and rather than count how many numbers I have and issuing the right number of + operators, I have a habit of just entering way more + operators than I need and then grabbing the stack top value afterward. e.g.:

1 7 8 6 4 9 1 2 3 6 4 + + + + + + + + + + + + + + + + + + p

Historically, and with other implementations of dc, this would result in a lot of dc: stack empty messages followed by the sum at the end. Now it results in a clear stack with no result.

I can certainly see the merit of returning to a clean slate on an error condition when running in an "automated" fashion - blowing the stack in this case would generally mean you did something wrong and the results might not be trustworthy.

I guess what frustrates me is that in interactive mode, this is a significant change from historical behavior that caught me off-guard and also blows up my use case, requiring me to now count how many numbers I have on the stack, and then to supply N-1 operators to get to the result I want. It's also making my stack more "fragile" in the sense that I now have to be very careful about my interactions with dc.

I agree that changing behavior based on configuration-time options sounds like overkill and a lot of added complexity, especially when some users of a system might find the new behavior desirable.

I see a few other possibilities:

• A command line switch to either enable or disable stack clearing when running in dc mode, so a user can be explicit about whether they want the new behavior or the historical behavior. Whether the switch enables the old behavior, or enables the new behavior doesn't matter much to me; I'd just add a shell alias if I needed to always supply a switch.
• A rule that when running in interactive mode (ie, from a keyboard not from a pipe or a file), you get the historical (non-clearing) behavior, but in non-interactive mode you always get the new (stack-clearing) behavior.
• Some hybrid of the two: maybe in interactive mode you get the historical behavior unless you supply a command-line switch

Of course I realize that all of these options add complexity too, but hopefully not altogether too much. Any one of them would make me a happy camper.

[gavinhoward]

I am not a fan of having different behavior in interative mode vs non-interactive mode.

However, I think dc implementations tend to exit on any error in non-interactive mode anyway. At least GNU dc does, IIRC. This one definitely does, and this behavior is documented.

So this change would only affect interactive uses anyway.

I will go ahead and make the change. I will start fuzzing as well. If few or no problems appear, I will make a release.

[gavinhoward]

Okay, it took me a long time to have the time for fuzzing and testing, but this change made it into 7.0.0.

I think I can close this report now, but if there are still problems, feel free to reopen.