Python Front-end to GCC

[Steven D'Aprano]

On Tue, 22 Oct 2013 16:53:07 +0000, Frank Miles wrote:

[snip C code]

What you're missing is that arr[] is an automatic variable. Put a
"static" in front of it, or move it outside the function (to become
global) and you'll see the difference.

Ah, that makes sense. Thanks to everyone who corrected my
misunderstanding.

Well, actually, no it doesn't. I wonder why C specifies such behaviour?
Why would you want non-global arrays to be filled with garbage?

 

[Steven D'Aprano]

Considering that rapiding took about 1200ms (ish - again, cold cache)
previously, adding even just 250ms is noticeable.

Please excuse my skepticism, but in my experience, that would probably
mean in practice:

.... rapiding took about 1200ms, plus or minus 200ms, plus 500ms if the
system is under load, plus 800ms if the developer vagued out for a
moment, plus 1900ms if he happened to be scratching an itch, plus 2700ms
if the anti-virus happened to be scanning something, plus 4100ms if the
dev decided this was a good time to take a sip of coffee, plus 437000ms
if he needed to make the coffee first, plus 72000000ms if he was just
taking a moment to check something on Reddit or answer an email...

I don't have a lot of sympathy for this sort of micro-optimization of
interactive software, where the random variation from run to run is often
larger than the time being optimized, and where the human element is
usually one or two orders of magnitude greater still. Yes, developers
complain when they have to wait for the computer for half a second, or at
least the one time in thirty that they *notice* that they're waiting. The
other 29 times the computer is actually waiting for them.

Still, I'm probably no better. Only instead of optimizing code, I tend to
"optimize" travel time with "short cuts" that are guaranteed[1] to shave
off a minute from a journey that takes thirty minutes, plus or minus six
minutes. Show me a way to avoid waiting at traffic lights for 30s, and
I'll take it, even if it means waiting for a break in the traffic at a
Give Way sign for three minutes. So I shouldn't mock too much

You're right, of course, that 1/4 second is noticeable. I just find it
hard to credit that it's *significant* in the circumstances you're
describing. But I could be wrong.



[1] Guarantee void in the presence of rain, fog, heavy winds, light
winds, police radar traps, industrial action, civil protests, riots,
wars, earthquakes, acts of God, or other cars.

 

[Chris Kaynor]

On Tue, Oct 22, 2013 at 10:23 AM, Steven D'Aprano <

On Tue, 22 Oct 2013 16:53:07 +0000, Frank Miles wrote:

[snip C code]

What you're missing is that arr[] is an automatic variable. Put a
"static" in front of it, or move it outside the function (to become
global) and you'll see the difference.

Ah, that makes sense. Thanks to everyone who corrected my
misunderstanding.

Well, actually, no it doesn't. I wonder why C specifies such behaviour?
Why would you want non-global arrays to be filled with garbage?

Its a performance benefit, for cases where you are going to fill the array
from other means, such as from a file or other sources such as literals.
The global and static variables are effectively free to zero due to
standard OS behaviours.

The issue is actually more general than arrays, as the same behavior exists
for all the types in C. Stack and heap variables have undefined value when
initialized, while global and static variables (which are really the same
thing, but with differing lexical scopes) are zero-filled.

 

[Neil Cerutti]

On Tue, 22 Oct 2013 16:53:07 +0000, Frank Miles wrote:

[snip C code]

What you're missing is that arr[] is an automatic variable. Put a
"static" in front of it, or move it outside the function (to become
global) and you'll see the difference.

Ah, that makes sense. Thanks to everyone who corrected my
misunderstanding.

Well, actually, no it doesn't. I wonder why C specifies such
behaviour? Why would you want non-global arrays to be filled
with garbage?

Fish(enc)ey.

 

[Oscar Benjamin]

On Tue, 22 Oct 2013 16:53:07 +0000, Frank Miles wrote:

[snip C code]

What you're missing is that arr[] is an automatic variable. Put a
"static" in front of it, or move it outside the function (to become
global) and you'll see the difference.

Ah, that makes sense. Thanks to everyone who corrected my
misunderstanding.

Well, actually, no it doesn't. I wonder why C specifies such behaviour?
Why would you want non-global arrays to be filled with garbage?

It's not that you want them filled with garbage but rather that you
know you will fill them with useful values later and you don't want to
waste time pre-filling them with zeros first. Or perhaps you have some
other way of knowing which values are to be considered initialised.
This is reasonable in some contexts.

OTOH why in particular would you want to initialise them with zeros? I
often initialise arrays to nan which is useful for debugging. It means
that you can see if you made a mistake when you were supposed to have
initialised everything to useful values. In many contexts it would be
difficult to distinguish between a valid zero and a zero because you
haven't yet inserted a value. This kind of error can show up more
quickly if you don't zero the memory since the uninitialised values
will often be out of range for what you expected and will give very
noticeable results (such as a seg-fault).


Oscar

 

[MRAB]

On Tue, 22 Oct 2013 16:53:07 +0000, Frank Miles wrote:

[snip C code]

What you're missing is that arr[] is an automatic variable. Put a
"static" in front of it, or move it outside the function (to become
global) and you'll see the difference.

Ah, that makes sense. Thanks to everyone who corrected my
misunderstanding.

Well, actually, no it doesn't. I wonder why C specifies such behaviour?
Why would you want non-global arrays to be filled with garbage?

Static variables need be initialised only once, whereas auto variables
exist on the stack, so they would need to be initialised repeatedly,
which was considered too expensive, especially as they would be
assigned to before use anyway (hopefully!).

Of course, these days, with our much faster CPUs, we're not so
bothered, and prefer to allocate on the heap.

 

[Mark Janssen]

So which of you is confused? I ask that in the inclusive (not

Could you please be less snarky? We're trying to communicate here, and it
is not at all clear yet who is confused and who is not. If you are
interested in discussing technical topics, then discuss them.

Okay. The purpose of BNF (at least as I envision it) is to
produce/specify a *context-free* "grammar". A lexer parses the tokens
specified in the BNF into an Abstract Syntax Tree. If one can produce
such a tree for any given source, the language, in theory, can be
compiled by GCC into an executable.

Boom.

 

[Ned Batchelder]

Okay. The purpose of BNF (at least as I envision it) is to
produce/specify a *context-free* "grammar". A lexer parses the tokens
specified in the BNF into an Abstract Syntax Tree. If one can produce
such a tree for any given source, the language, in theory, can be
compiled by GCC into an executable.

Boom.

Hmm, I don't hear the boom yet. An Abstract Syntax Tree is a tree
representation of a program. To use my previous example: the program
"123 *!? 456" would become a tree:

op: "*!?"
num: 123
num: 456

There's still not enough information to compile this. The operator *!?
needs to have a meaning assigned to it. That's the role of the semantic
specification of a language. That has to be provided somehow. A BNF,
or a grammar, or a syntax, or an AST can't provide the semantics. That
was the original point: syntax isn't enough.

--Ned.

 

[Skip Montanaro]

Okay. The purpose of BNF (at least as I envision it) is to
produce/specify a *context-free* "grammar". A lexer parses the tokens
specified in the BNF into an Abstract Syntax Tree. If one can produce
such a tree for any given source, the language, in theory, can be
compiled by GCC into an executable.

Well, not quite. The lexer breaks the stream of characters up into
tokens, which are fed to the parser, which produces an abstract syntax
tree. From the WIkipedia entry:

"In computer science, an abstract syntax tree (AST), or just syntax
tree, is a tree representation of the abstract syntactic structure of
source code written in a programming language. Each node of the tree
denotes a construct occurring in the source code."

Skip

 

[rusi]

Mark Janssen said:

Unattributed

Hmm, well what I'd personally find interesting from a computer science
point of view is a app that will take a language specification in BNF
(complete with keywords and all) and output C code which is then
compiled to an executable as normal. This is how a front-end should
be designed. A middle-layer for translating common language elements
like lists, sets, etc, could make it easy.

Taking this starting sortie I was going to try to justify what Mark is saying.
Somewhat along the following lines.

Things like lex and yacc (and equivalents in ecosystems other than C) give a kind of holy-grail in the following sense.

When a writer of a lex/yacc spec does his thing, he does not need to think at the C level at all. Given that executable C is produced (and ignoring mishaps/bugs like shift-reduce conflicts etc) its a very ideal situation.
The yacc-grammar (and its lex-helper) are completely declarative and yet they result in perfectly good ( O(n)) good C code.

Taking this cue from the syntax domain one can treat it as a holy grail for semantics. ie can one specify the semantics of a language completely declaratively and have a lex/yacc *analogous* magic wand and get out a compiler/interpreter etc.

Many people have pursued this holy grail but it remains elusive. Some examples:
1. Atribute grammars
2. Utrecht univs UUAG
3. Action semantics
etc

Note a key word above is "analogous"

However when I see this:

Okay. The purpose of BNF (at least as I envision it) is to
produce/specify a *context-free* "grammar". A lexer parses the tokens
specified in the BNF into an Abstract Syntax Tree. If one can produce
such a tree for any given source, the language, in theory, can be
compiled by GCC into an executable.

all I will say is "eyes-roll"

 

[MRAB]

Okay. The purpose of BNF (at least as I envision it) is to
produce/specify a *context-free* "grammar". A lexer parses the tokens
specified in the BNF into an Abstract Syntax Tree. If one can produce
such a tree for any given source, the language, in theory, can be
compiled by GCC into an executable.

Boom.

But you still need to specify the semantics.

 

[Mark Janssen]

So which of you is confused? I ask that in the inclusive (not

Hmm, I don't hear the boom yet. An Abstract Syntax Tree is a tree
representation of a program. To use my previous example: the program "123
*!? 456" would become a tree:

op: "*!?"
num: 123
num: 456

There's still not enough information to compile this.

.....Is your language Turing complete?

 

[Neil Cerutti]

Okay. The purpose of BNF (at least as I envision it) is to
produce/specify a *context-free* "grammar".

Context-sensitive grammars can be parse, too.

A lexer parses the tokens specified in the BNF into an Abstract
Syntax Tree.

A lexer traditionaly reads the text and generates a stream of
tokens to the parser.

If one can produce such a tree for any given source, the
language, in theory, can be compiled by GCC into an executable.

What executable would GCC compile from a program that matched
this grammar?

spamgram = spam1, { ', ', more_spam }, '.'
spam1 = 'Spam'
more_spam = spam, { ', ', spam }
spam = 'spam'

 

[Mark Janssen]

Okay. The purpose of BNF (at least as I envision it) is to

But you still need to specify the semantics.

In my world, like writing pseudo-code or flow-charts, the AST *is* the
semantics. What world are you guys from?

 

[Ned Batchelder]

....Is your language Turing complete?

1) No, it's not.
2) So what? That should make it easier to compile to C, if anything.
3) Don't change the subject.

A BNF doesn't provide enough information to compile a program to C.
That's all I'm trying to help you understand. If you don't agree, then
we have to talk about the meaning of the words BNF, compile, program, and C.

I applaud your interest in this topic. I think you need to learn more
before you try to claim expertise, though.

--Ned.

 

[Mark Janssen]

....Is your language Turing complete?

1) No, it's not.
2) So what? That should make it easier to compile to C, if anything.
3) Don't change the subject.

Well, if your language is not Turing complete, it is not clear that
you will be able to compile it at all. That's the difference between
a calculator and a computer.

Thank you. You may be seated.

Mark J
Tacoma, Washington

 

[rusi]

A BNF doesn't provide enough information to compile a program to C.
That's all I'm trying to help you understand. If you don't agree, then
we have to talk about the meaning of the words BNF, compile, program, and C.

I believe we need to talk about the Dunning-Kruger effect

 

[Ned Batchelder]

In my world, like writing pseudo-code or flow-charts, the AST *is* the
semantics. What world are you guys from?

Mark, you started this by describing a program that compiled to C. Now
you say you are in the world of pseudo-code and flow-charts. Which is it?

In the world where actual programs get compiled and run, you need to
have semantics, and they aren't expressed in an AST or a BNF. I think
you think that an AST is enough, but it isn't. I'm also not sure what
you actually think because we don't stay on a topic long enough to get
into the details that would shed light.

It's fun to feel like you are right, and it's easy if you change the
topic when the going gets tough. You've done this a number of times.

I've tried to be polite, and I've tried to be helpful, but I'm sorry:
either you don't understand a lot of the terms you are throwing around,
or you aren't disciplined enough to focus on a topic long enough to
explain yourself. Either way, I don't know how else to move the
discussion forward.

--Ned.

 

[MRAB]

In my world, like writing pseudo-code or flow-charts, the AST *is* the
semantics. What world are you guys from?

The real world.

So what you're saying is that you generate an AST where there are
certain pre-defined operations (primitives?) available?

 

[Grant Edwards]

On Tue, 22 Oct 2013 16:53:07 +0000, Frank Miles wrote:

[snip C code]

What you're missing is that arr[] is an automatic variable. Put a
"static" in front of it, or move it outside the function (to become
global) and you'll see the difference.

Ah, that makes sense. Thanks to everyone who corrected my
misunderstanding.

Well, actually, no it doesn't. I wonder why C specifies such behaviour?
Why would you want non-global arrays to be filled with garbage?

Firstly, it's not non-global arrays that have undefined contents.
It's _auto_ arrays that have undefined contents.

void foo(void)
{
int a[4]; // non-global, _auto_ variable and has undefined contents
}

void bar(void)
{
static int a[4]; // non-global, _static_ variable initially 0's
}

As to _why_ it's that way, you'd have to ask the guys who decided
that. I supect it's because zeroing static variables involves very
little run-time overhead, while zeroing auto variables could cause
huge amounts of overhead if that auto variable is declared inside the
innermost of nested loops. [Presumably a good optimizing compiler
would not zero an auto variable that was always set before it was
referenced, but it takes a lot of smarts for compiler to figure that
out correctly 100% of the time -- probably more smarts than a PDP-11
had room for.]