Comments on Some fossils found in the Turing tarpit

Anonymous Coward #413 (Xilun) (2004-01-14T23:37:07Z)

Et le BrainFuck alors ?
C'est le langage ultime le brainfuck

phi (2004-01-09T16:59:06Z)

The sequel to "it's great to feel stupid in front of D.A.M"…
The USENIX article reminded me there is a generic case where you need locally, dynamically parameterized functions: iterators. I did have the problem many times when I wanted to iterate some specific actions which were dependent on local values of the calling function. When the iterator is a simple loop, one usually put it in the calling function but it might be very complex such as scanning a text with many options like expression matching.
The irony is that this extension designed for ~functional programming style is now used primarily with side-effects…
That said, the workaround I used was to set the pointer to the parameter context as the (-1)th element of the array which, of course, was not typechecked.

Ruxor (2004-01-09T01:32:52Z)

PS: Thomas Breuel's paper mentioned in the gcc doc, <URL: http://people.debian.org/~aaronl/Usenix88-lexic.pdf >, is a very interesting read on the subject.

Ruxor (2004-01-09T01:26:05Z)

phi: Certainly nested functions incur a performance penalty, and the programmer should be aware of that (and choose accordingly). gcc uses trampolines to implement them (<URL: http://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html >). They are not part of C99 (they are a GNU-specific extension), and even if they were, the standard would not define an implementation requirement, of course.

Functions have no first-class citizenship in C, but pointers to functions do, even (in gcc) in the presence of nested functions: the pointer actually points to the function's lexical closure; but since C has no garbage collection, so closures must be kept on the stack, the pointer is actually valid only so long as the corresponding frame is live on the stack (hence the "all hell will break loose" comment in the aforementioned gcc doc).

Things can also be implemented, as you point out, by explicitely constructing the closure as a C++ object (or some similar kind of structure). This is typically in essence what is achieved by pointing void* pointers in C, but these lose type safety.

phi (2004-01-08T20:16:16Z)

Nested functions could make C inefficient if used extensively, especially if many nested levels are allowed. How are they implemented in C99? Are enclosing functions fully reentrant?

I am certainly not against the availibility of ML-like functionalities! Functions should even be first-class objects that you can build and combine. With the extension proposed, it is still impossible for a such a function (or a pointer to it) to be returned as a result, is it? I think this would lead to admit assignment of functions on a par with structures.

There might be one more possibility for nested functions, clean, stanfard in C++, using a class with an inline function. I don't know if such classes duplicate the code and whether it can (it should!) involve execution time values.

Ruxor (2004-01-08T12:53:11Z)

It is very easy to write imperative code in Lisp (for example if you mean "Common Lisp"; in some other forms, like Emacs Lisp, it is in fact much easier to write in imperative style than in functional style because Emacs Lisp uses dynamical scoping rather than lexical scoping).

In Haskell it is very tedious, yes, and that annoys me somewhat: some extra syntactic sugar would be necessary beyond the "do" construction. But more importantly I am annoyed by the difficulty of writing in non-lazy-programming style in Haskell.

I think it is generally a very bad thing when a programming language imposes upon the programmer too many constraints on the style he must adopt. Ideally the language should be chosen according to the style, that is true, but in practice other considerations interfere (like some code one might want to reuse, or the existence of such-or-such a library) and the choice becomes almost rhetorical.

You can't even argue that nested functions make C inefficient or are too difficult or something like that: gcc implements them quite happily, as I point out. They're not even contrary to the spirit of the language, and they have a very natural syntax.

Ska (2004-01-08T05:40:12Z)

Your troubles, Ruxor, arise from the fact that you're naturally thinking in a "functional programming"-style, and so you want to write functional code in C, which was not designed for this. Why don't you also protest against the tediousness of writing imperative code in Lisp ?

phi (2004-01-07T23:07:31Z)

And I may add that I suffered a lot with C, but certainly not with inner functions, which occurred quite seldom among tens of thousands of lines of code. My greatest frustration was with the preprocessor, all the more as C++ was still a dream at the time.

phi (2004-01-07T22:57:36Z)

"Of course everything *can* be done": it is simply not so in Pascal etc., which allow inner functions but not (all) variable functions. There are many features that are not formalized in C, such as those found in ML. What I loved in C was that I was able to implement them where it would have been impossible in other languages. I mean that's a fundamental point: a language should offer the maximum expressive power and where it doesn't know, it should at least offer the option not to forbid it. It is simply not the case in PASCAL (worst case!) and in many languages plagued with arbitrary restrictions.

Now, one forgotten point: for dynamical functions you must use a (P)alloc() function which allocates space in the program space, which is not warranted in all systems.

Ruxor (2004-01-07T13:43:52Z)

phi: Of course everything *can* be done. I'm not arguing against that: C is undoubtedly Turing-complete. The point about the Turing tarpit is that things *can* be done, but in a painful, unnatural, inefficient, dangerous, hacky and/or ugly way.

phi (2004-01-07T13:23:45Z)

I agree your example is not unnatural. As it doesn't involve recursion, and as C code isn't supposed to be executed in parallel within the same global variable space (hum…) you could implement it easily with global variables.

If there were recursion, you'd have to use a custom stack frame, which is coherent with the philosophy of C of making the programmer aware of the costs…

There is however lack with functions: there is no mean, in the standard libraries at least, to generate a function dynamically. What is pleasant is that you could write one (though it would be highly machine-specific).

Ruxor (2004-01-07T11:41:12Z)

Oui, Ruby, comme Smalltalk, fait partie de la liste des langages qu'il faut encore que j'apprenne et qui pourraient m'intéresser.

Damien (2004-01-07T09:28:11Z)

Et Ruby ?

Ruxor (2004-01-07T05:40:17Z)

phi: I think the usefulness of inner functions and the importance of closures will be best described by simply considering the following (slightly contrived, but very typical) example, which is valid gcc but not valid C99. Pay special note to the use of n in the inner function.

#include <stdio.h>
#include <string.h>

void
map_string (char *s, char (*fn)(char))
{
  for ( ; *s ; s++ )
    *s = fn (*s);
}

char
shift_by_n (char ch, int n)
{
  if ( ch >= 'A' && ch <= 'Z' )
    return ((ch-'A')+n)%26 + 'A';
  else if ( ch >= 'a' && ch <= 'z' )
    return ((ch-'a')+n)%26 + 'a';
  else return ch;
}

void
rot_n (char *s, int n)
{
  char fn (char ch) { return shift_by_n (ch, n); }

  map_string (s, fn);
}

int
main (void)
{
  const char s0[] = "Now is the time for all good men to come "
    "to the aid of the party.";
  char s[sizeof(s0)];

  memcpy (s, s0, sizeof(s0));
  rot_n (s, 13);
  printf ("%s\n", s0);
  printf ("%s\n", s);
  return 0;
}

Anonymous Coward #393 (Gamma) (2004-01-07T00:21:50Z)

Tout de même, pouvoir écrire des choses comme
char *TitleCase(char *p)
{ if(*p>='a' && *p<='z') *p++-=32; else p++;
for(;*p;p++) if(*p>='A' && *p<='Z') *p+=32; return p; }
comme dirait Ruxor, c'est b… heu… "suçâââble", non?

phi (2004-01-06T23:10:31Z)

The function setjump() is used very scarcely in fact, and it is not recommended but to the main loop when there is big trouble. Inner functions don't add anything that you couln't do by prefixing your function names, or by segmenting into different files. What may be frustrating is the lack of preprocessing power, even in the revised norm (2.1?).

Ruxor (2004-01-06T22:46:47Z)

:-b

Ska (2004-01-06T22:40:56Z)

I was willing to post a serious answer, but your last statement made me realize that your blog entry is just a giant troll, which almost caught me. Next time you're going to write something of the kind, do me a favour: don't.

Ruxor (2004-01-06T22:32:27Z)

tehu: Yes, I mean GNU, and GNU Is Unix, as everyone knows. :-)

Ruxor (2004-01-06T22:30:47Z)

Computing problem isn't so much the problem: Lisp, after all, is the third oldest programming language after Fortran and Algol (perhaps even the second, depending on who's telling the story).

And Pascal, at least, allows inner functions, which C does not. Of course, as a counterpart, Pascal does not allow pointers to functions. Having both at once means closures can escape, and strange things can happen; but if we allow closure validity only during the lifetime of the corresponding stack frame, then there is no reason not to do so (gcc does).

Anonymous Coward #392 (tehu) (2004-01-06T22:08:41Z)

>> and among these libraries I count the operating system I use, Unix, which is sadly dependent on Unix from its inception.

you mean Linux ?

phi (2004-01-06T21:51:40Z)

In the 80's, on personal computers, the choice was between assembler (and think 6502, 8080, Z80 didn't even have multiplication hardwired) and Basic whose variables (with one or two lettered names) were all global… Then the came Pascal and C. Pascal put a lot of constraints, of verbosity (OK, Cobol was far worse) and not usable for system programming because (esp.) of inept limitations on the typing of functions. C's laxity at least allowed it.

What's great with C is that its relative conceptual powerty doesn't forbid elaborated constructions (that is, without building again an entire shell language, interpreted or (!) compiled). You can do polymorphism with C; it is simply not checked by the language. You can use arithmetic subroutines with range checks if you give up binary operators notation… However, some compilers used to provide such checking as an option (watcom C or Zortech's, which have been eliminated by MS), and many optimisations (then, MS's C was the least featured and the slowest). You have a manual escape with marginal values, that is not even allowed in Pascal (pointers).

In short, C has few features, but at least it doesn't prevent you from building more, though it may not be easy syntactically. And it is still easier than all powerful assembly language.

Ruxor (2004-01-06T20:43:36Z)

DH, arrête de troller. :-)

(Pour le Pascal, regarde le dernier lien de l'entrée.)

Anonymous Coward #391 (DH) (2004-01-06T20:01:20Z)

Et le Basic ? Et le Pascal ? Et le Fortran ? Dis dis dis ?