Notes on Programming in C (1989)(doc.cat-v.org)
doc.cat-v.org
Notes on Programming in C (1989)
http://doc.cat-v.org/bell_labs/pikestyle
29 comments
>This is my favorite sentence. He's hinting at functional programming!
The biggest (perhaps the only) way that C was actually ahead of its time was its support for "functional" programming: pass-by-value, higher-order functions,[1] macros[2] and even having functions at all.[3]
[1] 40 years before Java, and before any other mainstream non-Lisp.[1b]
[1b] Algol 68 supported function pointers first, but it was, famously, too ahead-of-its-time to implement. Pascal had limited support for function parameters but didn't support returning them or specifying their parameter types or arity.
[2] An advanced feature for the time.
[3] Fortran, Cobol, PL/I, etc still only supported procedures, which were themselves considered a somewhat advanced feature at the time.
The biggest (perhaps the only) way that C was actually ahead of its time was its support for "functional" programming: pass-by-value, higher-order functions,[1] macros[2] and even having functions at all.[3]
[1] 40 years before Java, and before any other mainstream non-Lisp.[1b]
[1b] Algol 68 supported function pointers first, but it was, famously, too ahead-of-its-time to implement. Pascal had limited support for function parameters but didn't support returning them or specifying their parameter types or arity.
[2] An advanced feature for the time.
[3] Fortran, Cobol, PL/I, etc still only supported procedures, which were themselves considered a somewhat advanced feature at the time.
>I learned this fairly well working in games, where it's frequently faster to do a linear search or to use a linked list.
To be a bit of a quibbler, a dynamic array is almost always going to be faster than a linked list, especially when N is small, and unless you're writing C (or, for somewhat different reasons, a FP lang) the code will be simpler too.
But of course, with small Ns, outside of the tightest of inner loops or the most resource-constrained embedded targets, most any halfway-reasonable data structure is going to be (and has been for 20+ years) easily fast enough. So it is a bit of a tomato tomahto thing.
To be a bit of a quibbler, a dynamic array is almost always going to be faster than a linked list, especially when N is small, and unless you're writing C (or, for somewhat different reasons, a FP lang) the code will be simpler too.
But of course, with small Ns, outside of the tightest of inner loops or the most resource-constrained embedded targets, most any halfway-reasonable data structure is going to be (and has been for 20+ years) easily fast enough. So it is a bit of a tomato tomahto thing.
> To be a bit of a quibbler, a dynamic array is almost always going to be faster than a linked list
Nope, you're assuming that you're allocating in order to create the list. That's not always the case! :) It's very common in games and embedded systems to have the nodes in memory, pre-allocated, pre-loaded, baked into executable or game data, etc. If space for list pointers is baked in advance, you can use linked lists without the separate allocation costs of a dynamic array or other container class.
Also, a dynamic array can be slower than a linked list because you realloc larger chunks than 1 node. You pay larger costs for larger allocations, and it can also cause more fragmentation in a custom size-pooled allocator.
It's also common to forget that a dynamic array of pointers is two allocations per node (one of them potentially amortized... except for small N). It's a single allocation if you're storing the node struct directly in the array. But that's less common than people creating a dynamic array of pointers.
Nope, you're assuming that you're allocating in order to create the list. That's not always the case! :) It's very common in games and embedded systems to have the nodes in memory, pre-allocated, pre-loaded, baked into executable or game data, etc. If space for list pointers is baked in advance, you can use linked lists without the separate allocation costs of a dynamic array or other container class.
Also, a dynamic array can be slower than a linked list because you realloc larger chunks than 1 node. You pay larger costs for larger allocations, and it can also cause more fragmentation in a custom size-pooled allocator.
It's also common to forget that a dynamic array of pointers is two allocations per node (one of them potentially amortized... except for small N). It's a single allocation if you're storing the node struct directly in the array. But that's less common than people creating a dynamic array of pointers.
> I can't even keep track of how many times I've tried to read code and comments I wrote from more than 6 months ago, and thought to myself "this doesn't make sense" or "how can this possibly work?"
I guess I'm an outlier-- while I have read misleading/wrong comments in C code, I can't think of a single time where I've had my time significantly wasted by a misleading comment in C code.
I can think of several times where I've been slapped by a wrongly named function. Oops, turns out "check_width" doesn't merely return an int but instead mutates something deep in the bowels of the program.
I guess I'm an outlier-- while I have read misleading/wrong comments in C code, I can't think of a single time where I've had my time significantly wasted by a misleading comment in C code.
I can think of several times where I've been slapped by a wrongly named function. Oops, turns out "check_width" doesn't merely return an int but instead mutates something deep in the bowels of the program.
>> if your code needs a comment to be understood, it would be better to rewrite it so it's easier to understand.
I both agree and disagree with this... C is a small language, and it shouldn't take a huge amount of time to parse the source code to find out what's going on if variables / function names are self-documenting etc.
However, if you're dealing with a large code base and trying to track down where a variable is declared (and subsequently defined) for the purposes of maintenance or updating legacy code, comments hinting the what the structure underneath that label represents are incredibly useful (and more importantly, time and energy saving)
I both agree and disagree with this... C is a small language, and it shouldn't take a huge amount of time to parse the source code to find out what's going on if variables / function names are self-documenting etc.
However, if you're dealing with a large code base and trying to track down where a variable is declared (and subsequently defined) for the purposes of maintenance or updating legacy code, comments hinting the what the structure underneath that label represents are incredibly useful (and more importantly, time and energy saving)
I've been burned by bad comments enough times that I implicitly don't trust them. I wish this weren't the case but I think it's just human psychology. I'd rather unravel a mystery myself than deal with an unreliable narrator.
IDK, if you have self-documenting names, that sort of implies that they're close to unique/disambiguated. Which means that grep does a great job tracking down use (and declaration). And grep doesn't lie like out of date comments will.
I generally comment when I'm doing something really goofy because the 'obvious' method has some subtle flaw. A documentation for the next guy (who has a chance of being me, having forgotten some of the context six months form now) as a "I know you want to refactor this, but it's more complex than you think" warning.
I generally comment when I'm doing something really goofy because the 'obvious' method has some subtle flaw. A documentation for the next guy (who has a chance of being me, having forgotten some of the context six months form now) as a "I know you want to refactor this, but it's more complex than you think" warning.
This goes to "comments shouldn't describe the code, they should describe the reasoning". Especially if there are external reasons why the code is structured that way. On straightforward programs you should need hardly any comments at all.
Function pointers are interesting in C only because they solve certain problems that you wouldn't have to care about if you used another language. They make the language more expressive, but with great power comes great danger. These days, unless we really have to (supporting legacy systems etc.) we shouldn't use C but rather one of these (still to few IMO) modern languages that give you even more power while being close in efficiency to C.
I occasionally see someone older than me refer to C as a high-level language and get really confused for a second. (I'm employed as a JS developer (although most of my expertise is centered around C#).)
Back in the 80s, C was a high level language on your typical home computer. I recall in the 90s it was common to argue about the trade offs between writing an application in C vs. Assembly. Today, it's Java (Rust or Go) vs C.
I'm just scared at what's coming down the pike that makes Javascript a "low level language."
I'm just scared at what's coming down the pike that makes Javascript a "low level language."
Espruino
Past discussions created a lot of interesting comments, https://hn.algolia.com/?query=pikestyle&sort=byDate&dateRang...
> I argue that clear use of function pointers is the heart of object-oriented programming. Given a set of operations you want to perform on data, and a set of data types you want to respond to those operations, the easiest way to put the program together is with a group of function pointers for each type. This, in a nutshell, defines class and method. The O-O languages give you more of course - prettier syntax, derived types and so on - but conceptually they provide little extra.
I think that this might be an early hint at Go's interface system and its lack of of "complete" OOP support.
I think that this might be an early hint at Go's interface system and its lack of of "complete" OOP support.
Well, it's more like the "C with Classes" approach that was the precursor to C++; "group of function pointers for each type" is basically a vtable.
this guide/book from inria is pretty good: http://icube-icps.unistra.fr/img_auth.php/d/db/ModernC.pdf
edit-001: this was previously discussed here as well. ref: https://news.ycombinator.com/item?id=9018247
edit-001: this was previously discussed here as well. ref: https://news.ycombinator.com/item?id=9018247
I just skimmed through this. Page 3 says Rule 0.1.2.1 C is a compiled programming language.
I never understood the phrase compiled language in the context of C and also in general. C interpreters exist. I happen to have an official copy of the ISO/IEC 9899:1999 standard. The word "compiler" appears only once in a footnote. Other languages have both compilers and interpreters (e.g. Common Lisp, OCaml).
I never understood the phrase compiled language in the context of C and also in general. C interpreters exist. I happen to have an official copy of the ISO/IEC 9899:1999 standard. The word "compiler" appears only once in a footnote. Other languages have both compilers and interpreters (e.g. Common Lisp, OCaml).
C being a "compiled language" refers to a cluster of concepts which goes perhaps something like this:
* The semantics is simple. For instance, local variables vaporize when a block terminates; compiling a lexical scope in C means not even having to know what "closure" means, and thus not having to deal with a whole class of code generation problems like treating optimizing trivial closures, and non-escaping ones.
* A correct binary call to a C function can be generated if we just parse and analyze a simple prototype declaration. Very little information is needed to generate the calls to functions in a separately compiled file.
* The declaration of any complete data type specifies how it is laid out in memory and accessed.
* In general, anything which would make compiling difficult is either off limits to the programmer entirely, or "undefined behavior". For instance, functions aren't objects and cannot be manipulated at run time in any portable way. There are almost no introspective features whatsoever. A C interpreter can easily have all sorts of introspection features as extensions, but those are kept out of the language because they would interfere with the concept of it being a "compiled language".
* The type system is static and supports type erasure: most C implementations throw away all type info (except as part of "debug info") when translating C programs. No requirement in the standard requires any type info to be retained. Even though anything can be interpreted, static typing with erasure tends to make languages geared toward compiling.
* The semantics is simple. For instance, local variables vaporize when a block terminates; compiling a lexical scope in C means not even having to know what "closure" means, and thus not having to deal with a whole class of code generation problems like treating optimizing trivial closures, and non-escaping ones.
* A correct binary call to a C function can be generated if we just parse and analyze a simple prototype declaration. Very little information is needed to generate the calls to functions in a separately compiled file.
* The declaration of any complete data type specifies how it is laid out in memory and accessed.
* In general, anything which would make compiling difficult is either off limits to the programmer entirely, or "undefined behavior". For instance, functions aren't objects and cannot be manipulated at run time in any portable way. There are almost no introspective features whatsoever. A C interpreter can easily have all sorts of introspection features as extensions, but those are kept out of the language because they would interfere with the concept of it being a "compiled language".
* The type system is static and supports type erasure: most C implementations throw away all type info (except as part of "debug info") when translating C programs. No requirement in the standard requires any type info to be retained. Even though anything can be interpreted, static typing with erasure tends to make languages geared toward compiling.
I always read that as the default behaviour for the language. C is usually compiled but there are exceptions. Perl (<=5) is almost always interpreted but there are tools to turn Perl code into an executable. I agree it's a somewhat arbitrary distinction given the above but when I first learned any programming at all having it explained this way helped my understanding of how languages can differ from each other.
>Perl (<=5) is almost always interpreted but there are tools to turn Perl code into an executable.
IIRC those tools (of which similar ones exist for Java, Python, Ruby, Node.js, Lua and so on) just package together the sources (precompiled to bytecode) and an instance of the Perl[5] interpreter.
IIRC those tools (of which similar ones exist for Java, Python, Ruby, Node.js, Lua and so on) just package together the sources (precompiled to bytecode) and an instance of the Perl[5] interpreter.
I also remember tools that simply converted Perl code to C. The argument against being that the advantages of an executable would be outweighed by the disadvantages of transpiled C being very inefficient.
"Transpile" is not a real and meaningful word. Can we stop using it please? Btw, if you have relevant citations stating otherwise (Wikipedia isn't it), I am happy to be proven wrong. Thanks!
Here's Java getting compiled to actual x86-64 code (mov $0x2a,%edx; add %edx,%eax).
$ cat FortyTwo.java
public class FortyTwo
{
public static int fortytwo(int x) {
return x + 42;
}
}
$ gcj-4.9 -c FortyTwo.java
FortyTwo.o: file format elf64-x86-64
Disassembly of section .text:
<snip>
0000000000000022 <_ZN8FortyTwo8fortytwoEJii>:
{
public static int fortytwo(int x) {
return x + 42;
22: 55 push %rbp
23: 48 89 e5 mov %rsp,%rbp
26: 48 83 ec 20 sub $0x20,%rsp
2a: 89 7d ec mov %edi,-0x14(%rbp)
2d: b8 00 00 00 00 mov $0x0,%eax
32: 48 89 c7 mov %rax,%rdi
35: b8 00 00 00 00 mov $0x0,%eax
3a: e8 00 00 00 00 callq 3f <_ZN8FortyTwo8fortytwoEJii+0x1d>
3f: 8b 45 ec mov -0x14(%rbp),%eax
42: 89 45 fc mov %eax,-0x4(%rbp)
45: 8b 45 fc mov -0x4(%rbp),%eax
48: ba 2a 00 00 00 mov $0x2a,%edx
4d: 01 d0 add %edx,%eax
4f: c9 leaveq
50: c3 retqWhy would anyone want to run C in an interpreter though? Seems kinda pointless other than for educational purposes. I guess compiled/interpreted is arbitrary, but on a practical level most languages are one or the other (im not going to count JIT as compiled)
If you have a C compiler written in C and you want to bootstrap it from assembly then you need either a compiler or an interpreter. Writing a simple interpreter in assembly is far easier.
Good to see cat-v getting some coverage again. The archive they keep is fantastic.
>> Procedure names should reflect what they do; function names should reflect what they return. Functions are used in expressions, often in things like if's, so they need to read appropriately.
This never occured to me, but makes perfect sense, I usually know what I want a function to return, no need to make the name more generic than it needs to be.
This never occured to me, but makes perfect sense, I usually know what I want a function to return, no need to make the name more generic than it needs to be.
[deleted]
This is my favorite sentence. He's hinting at functional programming!
> I tend to err on the side of eliminating comments. [...] A misleading comment can be very confusing.
I can't even keep track of how many times I've tried to read code and comments I wrote from more than 6 months ago, and thought to myself "this doesn't make sense" or "how can this possibly work?" Or "this is impenetrable, I wish the idiot who wrote this would have used a little self-constraint and tried to simplify rather than show off and make everything complicated."
I'm getting more and more aware every year of how insanely hard it is to write or say things that are both clear and unambiguous. Every time I think I'm being clear and unambiguous, I find out later I was neither by a mile.
> Fancy algorithms are slow when n is small, and n is usually small.
I learned this fairly well working in games, where it's frequently faster to do a linear search or to use a linked list. The really basic stuff I was taught to avoid in school. But even now I have a hard time not using a hash table or tree or something at first, even when I know the data set will probably be small.