Gosh Darn Function Pointers | Hacker News Reader

Gosh Darn Function Pointers

goshdarnfunctionpointers.com

80 pointsstriking63 comments

Whatever happened to cdecl?

  : fred@dejah sql $; cdecl
  Type `help' or `?' for help
  cdecl> declare x as pointer to function returning int
  int (*x)()
  cdecl> declare x as pointer to function returning pointer to function returning int
  int (*(*x)())()
  cdecl>

It's also available online https://cdecl.org/

While we are on the topic of cdecl, does anyone know where I can find a succinct algorithm for producing valid C declarations from a structured description of the type? Basically, what the examples in the parent post are doing (and NOT the other way around, which is parsing valid C declarations).

I tried looking at cdecl's source code but everything is implemented as a big yacc grammar, which obscures the control flow of the algorithm. While this is necessary for the parsing feature, I suspect that for producing declarations it might be possible to use a simple recursive algorithm instead...

There's no "algorithm" in that it's the same way you traverse over any tree to produce output, a la compilers.

Sure, but I already spent a whole day trying to write said tree traversal, and failed miserably. Eventually I had to give up and find another way to solve my original problem, which annoys me to this day.

If anyone can help me find a way to convert a tree representing a C data type into a string with a syntactically valid C declaration for it I would be very grateful. I suspect that it should be possible to do this via a clean recursive algorithm, but the only implementation of this I could find so far was cdecl's LALR-based one.

It entirely depends on how you structure your data, so asking for help in this regard is essentially asking someone to do it for you.

I thought that I was making myself very clear that I was asking for someone to help me, either by pointing me to the solution or just outright stating it (I suspect that it shouldn't be very long) :)

I don't think it would depend very much on how the data is structured though. How many different ways are there to represent C types using tagged unions?

I understand, but there's a difference between doing work for you and helping you get there. Imagine a sexpression representing C data types the following two ways:

(pointer-to (integer))

(integer (pointed-to))

We could very easily print a decl for the second example by printing the two atoms seen in order:

int *

But if we want to print the first correctly, we will have to prepend to a string in order to correctly display the decl. That is, we will have to change our traversal order: https://en.wikipedia.org/wiki/Tree_traversal

Come on, that is a trivial difference that doesn't change anything in the grand scheme of things. At this point needlessly restricting the input format would just serve to make it harder for other people to help me find the solution I need.

And it is fine if you don't want to help me with this but sheesh, I am not trying to get someone else to do my homework here. I am trying to share a fun (and hopefully short) problem I couldnt solve myself yet.

The algorithm is the "spiral rule".

http://c-faq.com/decl/spiral.anderson.html

Thanks, but I actually want the other way around. Instead of parsing an existing C declaration, I want to produce one when given a structured tree representing the C datatype.

I found that to be trickier than it sounds.

Nothing happened to it.

  apt install cdecl

I've always found a typedef of the function and doing the pointer in the variable declaration the clearest since it doesn't need funky parentheses or dereferences anywhere:

    typedef int func(int arg);
    int foo(int a) { return a * 10; }
    ...
    func *f = foo;
    ...
    int x = f(10);

I am a little lost. What effect does `typedef int func(int arg);` have on the code?

It says that `func` is a type whose values are all functions with the signature `int foo(into arg)`.

The way to read a typedef (in general) is when you strip off the word "typedef", instead of declaring a type, it declares a value of that type. This applies to all types, not just function types. For example, an array of 5 ints is declared as

  int foo[5];

So the type of all 5-element arrays is defined by

  typedef int FiveLongIntArray[5];

It allows the later definition of func * f which is more readable and maintainable than int (* f)(int arg)

This pattern is common in well-structured applications, and is especially useful for clarifying external and internal APIs. e.g. from the Dovecot IMAP server:

    typedef bool event_callback_t(struct event *event,
    			      enum event_callback_type type,
    			      struct failure_context *ctx,
    			      const char *fmt, va_list args);

You can now define a function pointer or declare a parameter using event_callback_t. This is both concise and intention revealing.

A professor in college explained it in a way that works for me: C is about the type. When you say "int x" then "x" is an int. When you say "int * x", then "* x" is an int. Humans figure out the type of x by inverting the operations in the declaration:

"int (* x[])(char * )" means that x is something you can index into and call with a string to get an int. OTOH, "int (* x)(char * )[]" is something you can call with a string and then index into to get an int.

The only gotcha is that function pointers and function names are very stubble and the compiler lets you be a little fuzzy on saying x[0]("hello, world") or (*x[0])("hello world")

(forgive spacing. Trying to avoid the formatter)

> OTOH, "int (* x)(char * )[]" is something you can call with a string and then index into to get an int.

...would be something you can call if it was a correct declaration. I don't think it's valid, and certainly GCC in gnu99 mode rejects it (function returning an array).

The rule I heard is that you start reading the declaration from the variable name and go right to boundary (parenthesis, comma, or semicolon), then bounce left and bounce right until all tokens were seen. Then this reads as:

  int (*x[])(char *)

"x is an array <bounce-left> of pointers <bounce-right> to a function that expects (char pointer) <bounce-right> and returns int".

I've heard that rule too, but I've also heard it doesn't work always.

My solution: memorize the "function pointer typedef" syntax (second-to-last element in this list) and use typedefs whenever I use function pointers.

std::function syntax in C++ sure is nice though.

NB: If an argument to a function is a function pointer, you can write it like a normal function declaration.

So you can write

  void transform_string(char s[], char transform(char));

instead of having to write

  void transform_string(char s[], char(*transform)(char));

When writing C++ you should use function references when possible, as references cannot be null.

  void transform_string(char s[], char(&transform)(char));

Function references unfortunately require the more complex syntax, but fortunately C++11 `using`-style typedefs are quite simple to use with function types.

  using TransformFunc = char(char, char);
  typedef char TransformFunc(char, char); // C-style typedef, same as above

  // Function pointer
  TransformFunc fptr = /* ... */

  // Function reference
  TransformFunc &fref = /* ... */

"When writing C++ you should use function references when possible, as references cannot be null."

Not true. You can still pass a dereference of a null pointer, which will create a null reference. The null is detected only when (if) the reference is used, not when the dereference expression is evaluated as an lvalue for its address to initialize the reference.

char (transform_ptr)(char) = NULL; transform_string(s, transform_ptr); // no exception // ... later, in transform_string() ... transform(...); // exception

Yes, that's technically true, but you have to admit a little contrived, especially as pertaining to function pointers/references.

I'll amend my statement to "unlike pointers, valid references cannot point to a null address."

This is also true of any other language which has both nullable and non-nullable references, and a way to convert the former to the latter without accounting for the null case, such as Rust[1].

  fn pass_null_reference() {
  	unsafe { print_i32(&*std::ptr::null()) }
  }

  fn print_i32(n: &i32) {
  	println!("{}", n) // segfault
  }

[1] https://godbolt.org/g/1oUnNt

Ah, but what makes it an invalid reference, apart from convention? You could just as easily say that a null pointer is an invalid pointer in a context where a non-null value is expected. After all, a reference is just a constant pointer which is automatically dereferenced. Any program which may contain a null pointer may also contain a null reference.

"This is also true of any other language which has both nullable and non-nullable references, and a way to convert the former to the latter without accounting for the null case, such as Rust."

Indeed, though in Rust (like most other safe-by-default languages) you do need that glaringly obvious "unsafe" keyword to perform the conversion, which is a hint that you should be checking for null at that point.

> Ah, but what makes it an invalid reference, apart from convention?

It's an invalid reference in that a reference which does not refer to an object is either dead code, or an unrecoverable error.

There's no point in checking if a reference refers to null, because (unlike pointers) it cannot then be assigned a useful value, and also because any such check will be removed by the optimizer, because null references are undefined behavior (in both C++[1] and Rust[2]).

> Indeed, though in Rust (like most other safe-by-default languages) you do need that glaringly obvious "unsafe" keyword to perform the conversion, which is a hint that you should be checking for null at that point.

It is an improvement but (obviously) the unsafety in this case escapes from the "unsafe" block into the surrounding "safe" code and other "safe" functions.

It's also possible, even in entirely-"safe" code, to crash a Rust program by attempting to dereference a null pointer.

  fn dereference(nullable_ref: Option<&i32>) -> &i32 {
  	nullable_ref.unwrap()
  }

  fn crash() {
  	dereference(None);
  }

[1] https://godbolt.org/g/TjexTp

[2] https://godbolt.org/g/eeXAnn

Panics are absolutey safe compared to segfault. “Memory safety” does not mean “this program never terminates unexpectedly.”

You can also drop all the 'a business in that definition, it's superfluous.

"There's no point in checking if a reference refers to null, because (unlike pointers) it cannot then be assigned a useful value, and also because any such check will be removed by the optimizer, because null references are undefined behavior (in both C++ and Rust)."

That is a good point; I did not realize it was considered undefined behavior, which does make it substantially different from a null pointer. (Of course, that means the compiler remains free to check for null when the reference is created, which would have been the safer approach. The check would only be needed when creating a reference from a pointer, and even then it could be optimized out if the pointer is known to be non-null.)

"It is an improvement but (obviously) the unsafety in this case escapes from the "unsafe" block into the surrounding "safe" code and other "safe" functions."

Right. Despite the name, the "unsafe" keyword is not really meant to say that the code inside the block is unsafe, but rather that the compiler is not responsible for its safety—it is up to the programmer to expose a safe interface. This code breaks that rule, and the result is undefined behavior. The constraint does help in narrowing down the source of the problem to a small core of functions explicitly marked as unsafe, rather than the entire codebase.

As steveklabnik pointed out, the safe version (unwrapping a None value) results in a panic call rather than actually dereferencing a null pointer, meaning that you can reliably intercept it with std::panic::set_hook—it is not undefined behavior.

Simply declaring a function gives you a pointer to that function. Which reminds me of the time I wrote this in a PR to FreeBSD:

    if ((Lflag ? chown : lchown)(p->fts_accpath, -1, s->st_gid))
      /* .. */

a line that turned out to be incredibly polarising amongst code reviewers.

Explanation for those not well versed in C: the ternary in the left-hand parentheses is selecting which syscall wrapper function will be dereferenced and called with the arguments in the right-hand parentheses. It relies on the chown(2) and lchown(2) syscall wrappers having identical function signatures.

That is fancy, but not very readable. I would have been on the side of the code review which would favor readability over conciseness. Cool trick though.

I've found using a macro makes function pointers really easy. Learnt this from Handmade Hero:

  #define SOME_FUNCTION(name) void name(int Arg0, float Arg1)

  typedef SOME_FUNCTION(some_function);

  SOME_FUNCTION(SomeFunction)
  {  
  }

  struct some_functions
  {
      some_function* Foo;
      some_function* Bar; 
  };


  // Either works here.
  some_functions SomeFunctions;
  SomeFunctions.Foo = &SomeFunction;
  SomeFunctions.Bar = SomeFunction;

Hi HN! You found my site again. Here's the previous discussion from almost exactly year ago (warning, this links to the profane version): https://news.ycombinator.com/item?id=13437182

This is how I learned to read function pointer declarations: http://cseweb.ucsd.edu/~ricko/CSE131/rt_lt.rule.html

Also, as a parameter to a function, alternative:

  int my_function(returnType parameterName (parameterTypes));

When you apparently declare a function parameter of function type, the type is adjusted to pointer-to-function, similarly to the way array types as parameters are pointers.

This style is useful for de-cluttering code that has a lot of functional parameters all over the place.

"(but try not to cast functions)". Try not to cast at all, of course, but especially not functions.

I was going to post something about how you need to cast function pointers to use dlsym(), which returns a void * (since it doesn't know statically what the type of function you're asking for is, let alone that it's a function at all). You'd do something like

    void *mylib = dlopen("mylib.so");
    int (*myfn)(int) = (int (*)(int))dlsym(mylib, "myfn");

And I was also going to comment on how casts between data pointers (including void * ) and function pointers are undefined behavior in the C spec, but conformance to POSIX requires that to work because how else are you going to use dlsym. But then I looked up the example in the POSIX.1-2004 dlsym manpage, which does this bizarre thing instead: http://pubs.opengroup.org/onlinepubs/009695399/functions/dls...

    int (*fptr)(int);
    *(void **)(&fptr) = dlsym(handle, "my_function");

and there's a RATIONALE section in that man page explaining why, and the Linux dlsym man page calls it out too: http://man7.org/linux/man-pages/man3/dlopen.3.html#EXAMPLE

   /* According to the ISO C standard, casting between function
      pointers and 'void *', as done above, produces undefined results.
      POSIX.1-2003 and POSIX.1-2008 accepted this state of affairs and
      proposed the following workaround:
    
          *(void **) (&cosine) = dlsym(handle, "cos");
    
      This (clumsy) cast conforms with the ISO C standard and will
      avoid any compiler warnings.
    
      The 2013 Technical Corrigendum to POSIX.1-2008 (a.k.a.
      POSIX.1-2013) improved matters by requiring that conforming
      implementations support casting 'void *' to a function pointer.
      Nevertheless, some compilers (e.g., gcc with the '-pedantic'
      option) may complain about the cast used in this program. */

and indeed, the POSIX.1-2013 man page does the natural thing, saying "This standard requires this conversion to work correctly on conforming implementations": http://pubs.opengroup.org/onlinepubs/9699919799/functions/dl...

I wonder if there are any C compilers that actually optimize casts between data and function pointers as if they could be undefined (not counting hardware architectures where such casts literally don't work because they're in different address spaces).

What sort of optimization might be possible? Also, is there any active development today on separate instruction and data address space architectures?

It probably no longer makes sense to use AVRs instead of ARMs (or MIPS or whatever) for cost reasons, but there are still a lot of things out there that use them for backward-compatibility reasons — most notably most Arduinos — and lots of people are still doing active development for those things, and probably will be until the mid-2020s, if not later. People are still building new 8051-based systems, for heaven's sake, although not using discrete 8051 chips.

Atmel's AVRs are harward architecture (separate data and code address space) and are almost exclusively programmed using gcc. They are widely used too.

The reason for casts between data and function pointers is not about separate data and code spaces (that much), but about:

1) supporting architectures where code and data pointers have different size. One might think of various Hardvard architecture microcontrollers, but most C memory models for real mode x86 have this feature.

2) environments where code pointers essentially convey capability and thus have to be created by the OS in order to be usable (this typically involves indirect call instructions reading from some part of memory that is not otherwise accessible to user space at all)

Interestingly, this hack has caused problems with gcc4 on s390: https://git.gnome.org/browse/libxml2/tree/include/libxml/has... . The comment claims it violates C's aliasing rules.

I had the idea, years ago when I still thought some day I'd write a programming language, that somewhere between type inference and programmatic type inspection that there is space for promoting a type based on your inspection. Especially if you're using Static Single Assignment inside of your compiler.

For instance:

    Object foo = inputArgument1;
    
    if (foo typeof function) {
        // in this block foo is a function.
        foo(bar);
    }

Where this breaks down on legibility is when people rely too much on inductive reasoning (you can only get into this block if three other things are true... except now there's a bug so that's no longer true) or they keep reassigning to 'foo' willy nilly through their code. But if those are the sorts of people who lose out to the benefit of everyone else, I'm not even sad.

Kotlin does that with it's smart cast feature: https://kotlinlang.org/docs/reference/typecasts.html

It's really great actually, and the IDE also helps by marking foo slightly different inside the block, and if you mouseover to check for it's type it says what it is, and that it's because of a smart cast.

I have a suspicion that the Jetbrains guys were reading the same language design sources that I was. There are several other features like the ? operator that I saw in a small language first (called Nice). Daniel Bonnoit did a good job of articulating some of his design choices, especially optional types.

I cannot imagine how complex a parser for C must look like.

Much much less than a C++ parser.

I don't think there is a PL that is harder to parse than C++.

Perl [1] (at least pre-6) and Ruby [2] have good claims too.

* [1]: http://www.jeffreykegler.com/Home/perl-and-undecidability

* [2]: https://programmingisterrible.com/post/42432568185/how-to-pa...

I can imagine that parsing Coq is pretty dang difficult since the user is able to essentially define and use their own syntax in the code. Also parsing Agda seems non-trivial, though likely not as hard as C++.

I don’t know whether it is really hard to parse for a computer, but PL/1 may be a good candidate. Its idea that you can’t expect programmers to know every keyword of the language and, hence, the language cannot have reserved words can lead to programs that humans have trouble parsing. A simple example:

  IF x THEN y = z; ELSE = w;

Here, the parser can’t know that ELSE is a variable until it sees the second equal sign. For a more involved example, take a look at http://multicians.org/proc-proc.html

(the idea that one cannot expect programmers to know all keywords isn’t a bad one; http://www.cs.vu.nl/grammarware/browsable/os-pli-v2r3/, which claims to be incomplete, has 310 keywords. Drawing the conclusion that one should not have reserved words _is_ a bad idea)

Older language designers seem to have held natural language as their ultimate syntax, so reserving keywords would be anathema to that goal. It's probably also in direct conflict with efficient parsing. And you still see some people thinking along the same lines when they obsessively over-value "DSL"s and

    like().writing(all.their.code()).like(*this)

In which case, the programmer doesn't have to memorize keywords, but they do have to memorize these obscure, unpredictable, and noncommunicable features of where to properly put their dots and parens. Which is far worse, in my opinion.

That is called a fluent interface (https://en.wikipedia.org/wiki/Fluent_interface) and is generally frowned on by experienced language and API designers (even of the OO variety).

It has nothing to do with language keywords, it is just too far away from operational behavior to be very readable or debuggable.

It looks like "fluent interface" resembles "point-free" programming:

https://en.wikipedia.org/wiki/Tacit_programming

However, there seems to be a key difference. Under "fluent interface", it looks like the object context is pointlessly being chained and the operations are just side-effecting on it, whereas "point free" programming implements a transformation pipeline by chaining side-effect-free operations.

E.g.

  turtle.rotate(90).pen_down().forward(5);

Kind of thing which isn't a pipeline at all, and could be written:

  turtle.rotate(90);
  turtle.pen_down();
  turtle.forward(5);

and arguably should.

I think using some sort of construct that topicallizes the object is a good middle ground between the two.

For example this Perl 6 code:

  with turtle {     # store in topic variable $_ (if it's defined)

    .rotate(90);    # implicit method call on $_
    .pen_down();
    .forward(5);

  }

No it's not about keywords, but about jumping through fiery hoops to create code that sounds like natural language when you read it out loud.

Not yet, but the C++ committee is hard at work at creating the next C++ revision.

It’s the inverse: simple parser, complex results.

The grammar is relatively simple. In general having syntactic constructs that are seen as complex by humans (on the grounds of unreadability or counterintuitiveness) says nothing about complexity of the formal language that describes such constructs (and in fact for most practical languages often ugly constructs are the effect of the grammar being simple, not the other way around, for somewhat extreme example of this try comparing say SQL and RPN).

C in 4 functions: https://github.com/rswier/c4

Parsing c is almost trivial. It is the explanations, such as the article, through disjointed examples instead of the method.

A simple way for a human to parse a c type is to start at the identifier, go to the right as long as you can, then go to the left if you must.

They are not that hairy. I did a recursive-descent one as a Common Lisp reader macro in less than 1k loc:

https://github.com/vsedach/Vacietis/blob/master/compiler/rea...

C is ok in that you can handle everything (including typedefs) in a single pass with only one character lookahead. This includes the preprocessor. Common Lisp has concatenated streams (http://www.lispworks.com/documentation/HyperSpec/Body/t_conc...) which made handling the preprocessor really easy, but tcc (https://bellard.org/tcc/) and I think pcc also do the preprocessing as part of the parser.

C's type expressions can actually be parsed by a simple operator-precedence parser, and implementing one is very helpful in understanding C expressions. As they say, to understand a language, write a compiler (or at least a parser) for it.

Years ago, after I wrote an emulator for the MC68000 (68010 actually), I suddenly became very good at coding in MC68K assembly language. Not necessarily in better in organizing big assembly language programs, but just the raw coding of small blocks of code well.

Reply on news.ycombinator.com