25
$\begingroup$

The master programmer sat at his desk, gazing into the distance, his eyes seeing, and yet unseeing.

The lunch had been heavy.

His reverie was interrupted by the appearance of his close colleague, Ananda.

"Ah, Ananda, it is you," spake the master programmer, his very words oozing wisdom, "How fares your Tcl program to classify a list of file names based on their extensions?"

"The code is written, O master, and the output created," Ananda replied, "But strange are the lines of the output, for they are in reverse order of those in the input."

The master smiled. "Doubtless, Ananda, you have been storing your lines in a list, and then iterating over its elements in reverse order."

"No, master. My program simply takes a line from the input, processes it, outputs the result, and then moves on to the next, like the eternal soul that moves from one body to another ..."

The master shook his head. "If such be your code, Ananda, then it can only mean that you have scripted somewhere a seek command on one of your files."

"My program does not seek, O wise one. It is only I who seek an answer to this great mystery."

The master laughed. "Come now, Ananda. It is no mean task to reverse the order of lines even intentionally, and you would have me believe that you have done so by accident? Was it not just a few days ago that I explained to you: how the insertion of a line at the start of a document is merely an illusion perpetuated by text editors, while reality requires the entire file to be rewritten on disk?"

"Indeed, I do remember your teaching, master. But if theory and practice be in contradiction with each other, then which should one regard as reality, and which as illusion, O learned one?"

The master frowned. "I find your insistence both annoying and disturbing. Come, show me this magical program of yours, that I may rid you of this delusion once and for all."

"Gladly, master. ... In preparation for your visit, I have already cleansed my directory of all save my program and the input file. ... Here you see these 10 lines of input ... and here I run the program before your eyes ... and now see here in this output file that has appeared those 10 lines processed, but in reverse order."

The master blinked.

"Shall I open the program now, master?"

The master cleared his throat. "Unveil it, that I too may lift the veil from your eyes."

"As you wish - or tclsh - O master. Here it is."

The master breathed deeply. "Let's see... Your file is named output.txt ... search ... and this name appears only once here in this open command, whose result is assigned to this variable ofp ... search ... and this ofp is used only in this puts command ... that prints this variable ... which is the result of this string processing ... on this variable ... which is set by this gets command, reading from your input file handle ... inside this loop ... which ... ... ... does ... nothing else ... ... ... ?!"

Ananda sat silent. It was the first time that he had heard the master say, "?!". The punctuation marks rang in his ears.

The master scratched his head. He deleted the output file. He changed the contents of the input file. He ran the program. He saw the output. He cursed silently.

Ananda watched patiently.

The master closed his eyes.

"Are you meditating, master?"

"Be quiet and let me think!"

Where is the fault?

Continued:

After a few moments, the master opened his eyes. "One only has to inquire within, Ananda," he said. And then without a further word, his fingers moved swiftly across the keyboard.

"O great wielder of the keyboard," said Ananda, "I could only discern two presses of the Enter key amidst a blur. Pray tell me what two lines of code you did add."

The master smiled compassionately. "It is the self-analysis technique of the ancients, Ananda. Both the lines are simple puts commands to the console. One after the gets $ifp sInput saying puts "here 11111 reading ....... $sInput", and one before the puts $ofp $sOutput saying puts "here 11111 writing ....... $sOutput". The output of these two lines shall transcend the structure and logic of your program, and tell us what really it is attempting to do. Then either we shall know it to be reading backwards, or to be writing backwards, or perchance we shall find the numbering and sequence of reading and writing to be as it should not be, and thusly shall we realize where to look next."

Ananda watched in awe as the master ran the program, whose consciousness level had just been raised.

And lo! There appeared on the screen 20 lines in all: 10 for reading and 10 for writing, the reading and writing being in exact alternation with each other, and both sets in precisely the same order as the input! The only reversal to be seen was on the face of the master.

After a pause, the master smiled knowingly, as one smiles when one has truly known nothingness. "Such a perfect harmony between the reading and the writing," he murmured, "And yet, somewhere there is a disturbance in the yin and yang of this program. For though the writing on the console be in order, yet the contents of the output file are reversed."

"Ummm... master?" Ananda interjected, "I was thinking ... Maybe we should revisit that theory of inserting a line at the start of a file ..."

The master gave Ananda a stern glance. "It is no theory Ananda, it is verily the way of nature. One can only read, overwrite or append; one cannot insert. These are the three modes of nature: 'r', 'w' and 'a'. There is no 'i'."

Ananda sulked.

The master patted him. "No, Ananda, there are subtler forces at play here ..."


Notes:
1. This is based on an actual incident that happened with me at work last year. The dialogue, of course, is exaggerated, somewhat in the style of The Tao of Programming.
2. This originally occurred in a Tcl program on Linux, but I've confirmed that it also happens in equivalent C programs run on Linux or Solaris.

$\endgroup$
  • 10
    $\begingroup$ Have you opened a ticket for this? :-) It's definitely a bug! $\endgroup$ – Techidiot Apr 1 '17 at 11:39
  • $\begingroup$ Did the master check what "this string processing" really is? $\endgroup$ – EKons Apr 1 '17 at 14:23
  • $\begingroup$ @ΈρικΚωνσταντόπουλος: Yes, the string processing was fine. $\endgroup$ – KeyboardWielder Apr 1 '17 at 16:03
  • $\begingroup$ Is reversal independent of the number of lines? $\endgroup$ – humn Apr 1 '17 at 21:07
  • 1
    $\begingroup$ Is the master's little stream of consciousness intended to indicate (correctly) that the gets, the string processing, and the puts are all inside the loop? May we (correctly) make other assumptions about the structure of the code, such as that there isn't some other loop containing this one, that the file-opening happens outside the loop, etc.? $\endgroup$ – Gareth McCaughan Apr 2 '17 at 1:10

14 Answers 14

9
$\begingroup$

As requested by @KeyboardWielder in a comment on my earlier answer

After much back and forth, and investigation of the structure of the code using the print-to-console debugging technique passed down through the ages, Ananda and the Master had come to the following conclusions:

  1. The lines of the input file were being read in the correct order.
  2. The input strings were being appropriately "processed."
  3. The output was printed to the console in the correct order.
  4. Nonetheless, the order of the lines was reversed in the output file.
  5. No memory corruption/undefined behavior was occurring.

Such a mystery! The behavior of a program debugged by printing to console differs from the behavior seen in writing to file. Returning to the wisdom of the programming ancients, the answer in this situation often lies in the output buffer - that is, in order to improve efficiency of expensive file IO operations, output is not immediately written to a file, but is written to a buffer in memory until some future time.

Such buffers operate on a "first-in-first-out" (FIFO) order... but was it possible that Ananda had inadvertently changed a setting somehow that made the buffer act as a "last-in-first-out" stack instead? This thought was quickly dismissed, however, since the order of the characters itself was not reversed, merely the order of the lines. The behavior of the program was instead mimicking a situation where each line of input was pushed onto a stack, and then written to the file in the order they would be popped off the stack. How could this be so?

Closer inspection of the code revealed that instead of opening the output file a single time, Ananda had inadvertently included the open statement inside the loop: a new file object was created for each line of the input. Thus, each line to be written by puts was written into a separate output buffer, and writing to the file was delayed until some future point - specifically, on termination of the program, when the open file objects had their buffers flushed as they were closed in reverse order of creation.

Ananda's mistake, as so many mistakes are, lay in not managing his resources appropriately!

For consistent, predictable behavior when using files, obtain a single reference to the file, rather than opening multiple independent references.

$\endgroup$
  • $\begingroup$ More details, including program fragments and further ruminations, can be found in the wrap-up below. $\endgroup$ – KeyboardWielder Apr 5 '17 at 20:46
6
$\begingroup$

Another possibility, because the wording of the master's description of the code structure is (more than) a bit ambiguous:

If the file was opened accidentally inside the loop, then puts writes each line into a different output buffer, one for each file object. After program completion, the buffers are flushed in reverse order of creation as the stack is unwound, so even though the puts calls happened in the appropriate order, they actually write to disk in the reverse order.

Original thought
Does the same thing happen with fgets?

Buffer overruns are notorious for causing undefined behavior, and gets is not good practice for exactly this reason! I'd be surprised if UB causes a printed list to be reversed, but... UB gonna UB, so who knows...

$\endgroup$
  • $\begingroup$ gets, puts, open, etc. in Tcl are equivalent to fgets, fputs, fopen, etc. in C. So it is already the Tcl equivalent of C's fgets being used here. $\endgroup$ – KeyboardWielder Apr 2 '17 at 16:04
  • $\begingroup$ Great follow-up idea/edit! It comes close enough to working in gcc to believe it could work perfectly in Tcl. $\endgroup$ – humn Apr 5 '17 at 1:44
  • $\begingroup$ @tmpearce: You have been enlightened! The edit provides the correct answer. Please consider making it a separate answer and expanding on it. In any case, I'll accept your answer and post a wrap-up later in the day. $\endgroup$ – KeyboardWielder Apr 5 '17 at 4:49
  • $\begingroup$ @humn: Does work perfectly in gcc (on Linux/Solaris) too. Perhaps the file mode needs to be changed? $\endgroup$ – KeyboardWielder Apr 5 '17 at 4:55
  • $\begingroup$ I tried all kinds of variations, @KeyboardWielder, but the flushes always paralleled the order of fopens, which was validating enough to convince me. Another mystical mystery? $\endgroup$ – humn Apr 5 '17 at 4:58
4
$\begingroup$

Conclusion:

Kudos to @tmpearce for figuring out the correct answer, and saving me the trouble of posting a final hint describing the master's invocation of the magical strace -ewrite incantation.

Here is a minimal C program that captures the essence of the problem:

#include <stdio.h> int main() { FILE * ifp, * ofp; char szLine[1024]; ifp = fopen("input.txt", "r"); while (fgets(szLine, 1024, ifp)) { ofp = fopen("output.txt", "a"); fputs(szLine, ofp); } return 0; }

Note that it is necessary to open the output file in "a" mode to make each of the closing flushes seek to (the changing) EOF before writing.

While it's quite easy to see what's wrong here (although not so easy to realize what it leads to), it wasn't as easy in the original ~200 line Tcl program (all identifiers have been renamed to protect their identity):

# ... # ... lots of code in procedures ... # ... proc WriteOutput {sFileName and_other_params} { # ... # ... code to setup classification rules ... # ... set ofp [open "output.txt" "a"] # ... # ... some code ... # ... # ... loop over classification rules ... { # ... # ... some code ... # ... with conditions to check for a matching rule ... # ... set sOutput "$sFileName - some_info" puts $ofp $sOutput # ... } } # ... # ... more code ... # ... set ifp [open "input.txt" "r"] while {[gets $ifp sInput] > 0} {
# ... # ... some code ... # ... set sFileName [string trim $sInput] # ... more string processing ... WriteOutput $sFileName and_other_stuff }

The incident could have remained as just another debugging war story, but I was enamoured by how a minimal read-write program could achieve something complex unintentionally just by moving one line of code, and so decided to weave it into a puzzle.

In my experiments, both the above programs (the C program being compiled in GCC) reversed the output on Linux/Solaris systems, but neither the MSVC nor MinGW versions did so on Windows. It appears that the order of closing abandoned file objects is implementation defined.

Could there be a plausible version of the program that suffers equally on all platforms? Possibly. Consider a hypothetical framework that defines these misguided "best practices" functions:

# Sometimes files don't get closed due to exceptions being thrown and stuff. # Therefore, ALL file opening MUST be done through this SAFE function. # DON'T use "open" directly! proc OpenFile {sName sMode} { global g_lstOpenFiles set fp [open $sName $sMode] lappend g_lstOpenFiles $fp return $fp } # Now DON'T call "close", use one of the functions below proc CloseLastFile {} { global g_lstOpenFiles close [lindex $g_lstOpenFiles end] set g_lstOpenFiles [lreplace $g_lstOpenFiles end end] } # JUST call this at the end of the program and don't worry proc CloseAllFiles {} { global g_lstOpenFiles while {[llength $g_lstOpenFiles] > 0} {CloseLastFile} }
Now replace the calls to open with OpenFile, call CloseAllFiles at the end, and the seemingly "robust" program reverses its output on all platforms, despite being extra careful to close all files.

opens with unmatched closes certainly create a disturbance in the yin and yang.

As an aside: A couple of other philosophical concepts jokingly referenced in the question are "the three modes of nature" and "There is no I".

$\endgroup$
2
$\begingroup$

I think the file is opened (and closed) each time a line needs to be written, but for some reason the file-position indicator is set at the beginning of the file instead of the end of it.

I haven't written a line of c code in over 13 years, so be gentle if I say something stupid.

$\endgroup$
  • $\begingroup$ That theory is what the master was dismissing when he said that "the insertion of a line at the start of a document is merely an illusion ...". If the file-position indicator is set to BOF, existing contents get overwritten, there is no "insert" mode. ... But anyway, it's still possible that your answer is of some help to others. :) $\endgroup$ – KeyboardWielder Apr 1 '17 at 20:39
2
$\begingroup$

Well, @Donelle says that their answer is a joke... I don't think it necessarily should be.

I don't know much about Tcl regexes, but I'll assume they work the same way as python.

Then consider the following regex:

^.*\n([^\n]*)\.([^\n\.]*)\n

This gives two groups, one with the filename and one with the extension.

Deregexification for those who don't understand:

  • ^ From the start of the string
  • .* Anything (including the empty string)
  • \n Newline
  • ([^\n]*) Anything but a newline - this is stored by the brackets as group 1
  • \. A period
  • ([^\n\.]*) Anything but a newline or a period - this is stored as group 2
  • \n A newline

So what this is supposed to do:

Regex

We can add the beginning and trailing newlines as part of the program.

Now surely we can set the regex with the flag -all (which gives all the matches), then loop through the matches and puts them to the screen. It should match the first file first, then the next (because the first line has already been done), etc., right?

Nope.

That's not how regexes work.

.* is what is known as greedy. So it takes as much as it can to start off, then backs off character by character.

So once it backs off all the way to the x at the end of Someth.ng.docx, it matches, and gives Presentation as well as pptx.

Then the next time it has to back off to the end of Document.txt, and gives Someth.ng and docx.

If we puts the matches in the order that they are found, we get the filenames and extensions in reverse order, because of the way the .* works.


The ^.* is not *very* plausible, so if we want a more consistent coding style, we can have the following:

^.*\n([^\n]*)\.([^\n\.]*)\n.*$

where the .*$ matches anything followed by the end of the string.

More consistent version as visual:

Regex again

$\endgroup$
  • $\begingroup$ +1 for the regex golfing and the stunning visual presentation. :) However, (a) gets reads line by line, and (b) regexp -all in Tcl doesn't "back off" to return overlapping matches. (So even without the .* greedy stuff, you'd need to have pairs of newlines between lines to get all the matches.) $\endgroup$ – KeyboardWielder Apr 3 '17 at 17:23
  • $\begingroup$ Does your comment, both here and in other answers, that gets reads line by line indicate that the "string processing" also happens line by line at the time of gets? If processed at the time of reading in the line, how is the processed string stored until the puts output? $\endgroup$ – tmpearce Apr 3 '17 at 17:41
  • $\begingroup$ @tmpearce: Hint added. :) $\endgroup$ – KeyboardWielder Apr 3 '17 at 19:32
  • 3
    $\begingroup$ BTW, @boboquack, great effort -- I would never have thought of this. Perhaps material for another puzzle? $\endgroup$ – KeyboardWielder Apr 3 '17 at 19:35
  • $\begingroup$ @KeyboardWielder Maybe about the horrors of parsing HTML with regex (aka The Answer), perhaps... $\endgroup$ – boboquack Apr 3 '17 at 22:08
1
$\begingroup$

Could this be the answer?

The puts command is outside the loop, and is called once with the result of the string processing. The string process somehow goes wrong by assigning the result of gets in front of the old stirng.

$\endgroup$
  • $\begingroup$ Good try. But the gets sets, i.e. assigns to the variable; it does not accumulate across iterations in any way, nor does the variable resulting from the string processing. $\endgroup$ – KeyboardWielder Apr 1 '17 at 16:06
1
$\begingroup$

(Disclaimer: It wasn’t easy to read Tcl documentation and type while chuckling from the puzzle’s narrative.)

A rude passerby might interrupt the programmers’ trance and cast disbelief on some deceptively arranged cutlery that could produce the mystically described material result.

Cutlery being a fork command to create recursively nested child /progeny forks /processes that read and print subsequent input lines before each parent fork has a chance to print its own line.

 set ifp [open "input.txt"  r]
 set ofp [open "output.txt" w]
                                            |
 while { ! [eof $ifp] }                     $  Progeny forks will trigger eof before a
 {                                          $  fork tries to read its own second $line.
                                            |
   gets $ifp line                           |  (Advances $ifp for ancestor forks too,
                                            $   because $ifp is shared by all forks.)
                                            |
   set lineP [pid]                          $  Remember which fork owns this $line.
                                            |
   ... process $line ...                    $
                                            |
   set forkP [fork]                         $  Spawn a child fork that shares $ifp.
                                            |
   if {[pid] != $forkP} {[wait $forkP]}     $  If this is the parent fork,
                                            |  wait for progeny forks to finish.
                                            |  If this is the just-spawned fork,
                                            |  proceed so that the while loop
                                            $  reads this fork's own $line.
                                            |
   if {[pid] == $lineP} {[puts $ofp $line]} |  Write only if $line is from this fork.
 } 

Complications.   The puzzle’s poser has mentioned that the suggested cutlery is not necessary. And wait is not a Tcl command after all, anyway, although the same effect is attainable.

$\endgroup$
  • $\begingroup$ (a) The student was still new to Tcl, so such advanced cutlery was not yet part of his armoury. (b) The mistake was accidental, meaning that the code demonstrating such behaviour would have to be plausible, and such as would indeed leave the master baffled. $\endgroup$ – KeyboardWielder Apr 1 '17 at 20:45
  • $\begingroup$ Thanks for the guardrail, @KeyboardWielder, I'll post my latent edits anyway but stop looking for a clean implementation of wait, which Tcl apparently lacks in direct form. $\endgroup$ – humn Apr 1 '17 at 20:49
  • 1
    $\begingroup$ Worth mentioning that the highest voted programming-puzzle on PPCG.SE is also about executing prints backwards, and your answer is reminiscent of some of those. (I waded through all its answers to check that mine wasn't already in there.) $\endgroup$ – KeyboardWielder Apr 1 '17 at 20:50
  • $\begingroup$ Still would be good to know, @KeyboardWielder, does the code here violate any narrated structural aspects, such as ... does ... nothing else ... ?!? $\endgroup$ – humn Apr 2 '17 at 0:31
  • 1
    $\begingroup$ As of the current edit, it would surely have elicited a "what the fork?" reaction from the master. :) Subtly tucking the forking code away out of immediate sight into a procedure, could make it appear more innocent, but the if before the puts would still be a red flag. $\endgroup$ – KeyboardWielder Apr 2 '17 at 10:59
1
$\begingroup$

While considering the test file, it occured to me that...

...there are 10 kinds of programmers. Those who know TCL and those who don't. I am of the latter group. In any language it's much easier to accidently reverse a list of 10 items than a list of 11 or 100 items.

Since I'm no expert on the quirks of TCL, this is a just a guess:

The puzzle seems to imply there is only one line of code that writes to the file. But, perhaps the Master missed where olp was assigned to a 2nd variable. And that 2nd variable was used in a puts after the loop to write the first line read from the file.

$\endgroup$
  • $\begingroup$ +1 for pointing out a mistake often made during impact analysis (searching for uses of a variable, but not variables that it was assigned to). But the master's search clearly revealed that "ofp is only used in this puts". Also, as mentioned in the question, the behavior also happens in C, it's not specific to Tcl. $\endgroup$ – KeyboardWielder Apr 2 '17 at 10:50
  • $\begingroup$ The "10" is in decimal, there is no wordplay or number-play here. :) $\endgroup$ – KeyboardWielder Apr 2 '17 at 11:10
1
$\begingroup$

This is an at-most-half-baked answer, but I begin to suspect that the trouble lies

not in the program the master and Ananda are looking at, but in the way they are checking the contents of the output file.

For a (ridiculous) example,

suppose Ananda is playing a trick on the master, as follows. The input file is in a text editor open on the screen, and the master can see what's in it there. The master is known to be an old Unix guru who would never inspect the contents of a short text file with anything fancier than cat. And Ananda has done mv /bin/cat /bin/cat.orig; ln -s /bin/tac /bin/cat or something of the sort.

This sort of possibility is maybe made more plausible by

the date on which the puzzle was posted.

$\endgroup$
  • $\begingroup$ mv /bin/cat ... would require Ananda to have root privileges. But he could manage much more easily with an alias. But then that would apply to the input file as well. Which could be more intelligently worked around by writing a script named cat, prioritizing it in $PATH, and making it run cat or tac depending on $1. ... But Ananda knew better than to try such tricks on the master. $\endgroup$ – KeyboardWielder Apr 4 '17 at 17:18
  • $\begingroup$ In general (in response to the first block and to your comment in the question section), there is no problem in the way any of the files are being examined. $\endgroup$ – KeyboardWielder Apr 4 '17 at 17:44
1
$\begingroup$

I hope this is not the correct answer, but perhaps

the solution is simply to observe that the puzzle was posted in the morning on April Fools' Day.

In which case,

perhaps KeyboardWielder has no actually-consistent solution in mind at all, and is just screwing with us.

$\endgroup$
  • $\begingroup$ Is there a button to say "Good thinking but I really hope you're wrong"? $\endgroup$ – tmpearce Apr 4 '17 at 16:30
  • $\begingroup$ Well, as you see, I hope I'm wrong too :-). $\endgroup$ – Gareth McCaughan Apr 4 '17 at 16:35
  • 1
    $\begingroup$ Finally! Someone noticed... ;-) ... But my preferred technique of screwing with people on April Fools' Day is to double bluff by posting something that seems impossible, but is actually true. So: thankfully, you're wrong, and yes, the real tag is for real. $\endgroup$ – KeyboardWielder Apr 4 '17 at 17:14
0
$\begingroup$

I am not familiar with tcl. But if there are no arrays being stored and fiddled with, which it seems there are not, the either the input file is read backwards or the output file had the answers inserted at the top. Previous answers eliminated the latter, so somehow the input file is being read backwards.

But this is easily checked. It seems that you have a print out of each line as it is done. What order does it print out in?

$\endgroup$
  • $\begingroup$ It's pretty hard to read a file backwards. You'd have to roll your own gets to read a chunk of data and scan it for newline characters. There was no print out of each line to stdout (but I might add a hint later in which the master tries exactly that). $\endgroup$ – KeyboardWielder Apr 2 '17 at 11:04
0
$\begingroup$

Things went wrong because

the string processing used regular expressions. And you know the old saying:

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

$\endgroup$
  • $\begingroup$ Can you please explain? I don't quite get why regex would make the output backwards. $\endgroup$ – boboquack Apr 2 '17 at 23:53
  • 1
    $\begingroup$ It's mostly a joke about regular expressions being mystifying. $\endgroup$ – Donnelle Apr 2 '17 at 23:55
  • 2
    $\begingroup$ Obligatory xkcd: xkcd.com/1171 $\endgroup$ – boboquack Apr 3 '17 at 6:26
0
$\begingroup$

My guess is that there was only one iteration through the loop, because the gets returned all the lines in one string, and it is the string processing the reversed the order.

Perhaps gets did this because of an encoding issue, or because the file did not have the newline character at the end of each line just a l carriage return or other char that made it seem like the lines were terminated by newline.

$\endgroup$
  • $\begingroup$ Yes, a file from a Mac coming to a UNIX system would break the gets line-by-line reading. But it's hard to conceive a plausible string processing function that wasn't expecting multiple lines, yet produces the right output for each line, though in reverse. $\endgroup$ – KeyboardWielder Apr 3 '17 at 20:11
  • $\begingroup$ If we actually saw the code (as you and the story's guru did), would it be a lot easier? $\endgroup$ – Oliver Apr 3 '17 at 20:13
  • $\begingroup$ Well, yes. See my earlier comment. It probably wouldn't take too long to find something wrong and fix it. But explaining why it was causing a reversal would be harder. $\endgroup$ – KeyboardWielder Apr 3 '17 at 20:25
0
$\begingroup$

Perhaps the pointer-to-string given to gets() is modified by the string processing due to a stack overflow...

$\endgroup$
  • $\begingroup$ No. There are no stack or buffer overflows or memory corruption of any sort. $\endgroup$ – KeyboardWielder Apr 4 '17 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.