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.
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:
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 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.
: 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>
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...
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.
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.
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 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");
/* 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. */
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).
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)
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.
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'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);
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
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:
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")
> 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".
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.
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].
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.
"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.
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.
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
64 comments
[ 0.23 ms ] story [ 66.9 ms ] thread* [1]: http://www.jeffreykegler.com/Home/perl-and-undecidability
* [2]: https://programmingisterrible.com/post/42432568185/how-to-pa...
(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)
It has nothing to do with language keywords, it is just too far away from operational behavior to be very readable or debuggable.
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.
Kind of thing which isn't a pipeline at all, and could be written: and arguably should.For example this Perl 6 code:
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.
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.
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...
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.
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?
(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
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.
http://c-faq.com/decl/spiral.anderson.html
I found that to be trickier than it sounds.
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).
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)
For instance:
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.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.
std::function syntax in C++ sure is nice though.
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
So the type of all 5-element arrays is defined byThis pattern is common in well-structured applications, and is especially useful for clarifying external and internal APIs. e.g. from the Dovecot IMAP server:
You can now define a function pointer or declare a parameter using event_callback_t. This is both concise and intention revealing."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)
...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:
"x is an array <bounce-left> of pointers <bounce-right> to a function that expects (char pointer) <bounce-right> and returns int".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.
So you can write
instead of having to write When writing C++ you should use function references when possible, as references cannot be null. Function references unfortunately require the more complex syntax, but fortunately C++11 `using`-style typedefs are quite simple to use with function types.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
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].
[1] https://godbolt.org/g/1oUnNt"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.
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.
[1] https://godbolt.org/g/TjexTp[2] https://godbolt.org/g/eeXAnn
You can also drop all the 'a business in that definition, it's superfluous.
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.
This style is useful for de-cluttering code that has a lot of functional parameters all over the place.