"Le Chaud Lapin" <unoriginal_username@yahoo.com> wrote in message 
news:1149685713.011841.53460@h76g2000cwa.googlegroups.com...
> Tom Lucas wrote:
>> I see little point in graduating knowing how to write a compiler or 
>> design
>> an FM radio unless you are directly going into Sony's Radio Compiler
>> division. Knowing what a compiler does and the sort of tricks current
>> optimisers play will be more useful in the real world than knowing how to
>> parse an arithmetic expression. Similarly knowing about RF, demodulation 
>> and
>> amplifiers is more useful to the real world than an rudimentary FM radio
>> kit.
>
> There seems to be a bit of a contradiction here.  You seem to be saying
> that shallow practice is not good (FM kit), but you also seem to be
> saying that basic theory (being able to parse arithmetic expressions)
> is not good either.

What I'm saying is actually implementing a solution is not necessary and 
moves away from the theoretical into the practical. I would also class the 
mechanics of parsing an expression as an implementation challange and not 
part of the theory of a compiler (although it is an important part of the 
solution.)

> A person cannot design an FM radio without understanding many aspects
> of electronic theory.  In the case I was speaking of, the electronics
> course gives a bag of components, and a lot of theory.  You're expected
> to make everything, including the amplifiers, filters, phase-lock loop
> (from a pre-packaged VCO), etc.  Anyone who had not been paying
> attention to the theory would simply not be able to make the radio.
> The same course (or the next one) introduces Kalman filtering.  It's
> not a connect-the-dots type project.

There is certainly value to prove the knowledge gained on the course but 
this is simply a practical way of verifying that the exams are setting the 
correct questions. My point is that I would regard the radio (and compiler) 
construction as a polytechnic activity whereas the universities will be 
happy to impart the knowledge academically and test it by exams.

> For the compiler, I think it is very important to be able to parse
> arithmetic expressions.  Knowledge of automata theory can be
> invaluable.  For my current job, I recently had to make a small
> compiler for a stack machine.  Here's the tokenizer for lexical
> analysis:

Again, I think it's important to understand what the compiler is going to do 
and have an idea about how you would approach an expression parser but very 
few people actually write a compiler. I would say that for the majority of 
graduates the theory behind an abstract generic compiler is enough and 
actually writing one is time that could be spent on something else (although 
there is some merit in taking on a complex software design task)

<snip code>

> I  have no clue about optimization, but what I needed to know to make
> this compiler can be found in the first few chapters of any compiler
> book.

Hence why there isn't a lot of value in writing one unless you actually need 
to.

> Self-reliance is achieved by focusing on a small bit and
> learning that well, than reading the whole book casually and not
> remembering anything.

I agree that's true for me but people learn in different ways. I learn by 
doing but I know people who can read the book while I do the examples and we 
both end up with the same knowledge.

> I started dong this long ago after a
> converstation I had with a professor just before my graduation.  I
> asked, "There is so much to learn in the world...is it better to hurry
> up and grab what you can and depend on other people for deep insight or
> is it bet..."  he finished my sentenced quickly and said, "It's better
> for you to know."  I asked, "But does one person have time in his life
> to...?" he says, "Yes."  I asked, "Are you sure?" he said, "Yes."

Sure a professor will have plenty of time to know it all - he doesn't have a 
manager baying for blood because products in the field crash every 12532th 
time they are turned on :-) Philosophically it is better to know the answers 
yourself but often it is sufficient to know where you will find the answers. 
The more you know the more complete a solution you will find but realism 
will always intrude and take away your learning time.

Le Chaud Lapin wrote:
> Tom Lucas wrote:
> 
>> I see little point in graduating knowing how to write a compiler
>> or design an FM radio unless you are directly going into Sony's
>> Radio Compiler division. Knowing what a compiler does and the
>> sort of tricks current optimisers play will be more useful in the
>> real world than knowing how to parse an arithmetic expression.
>> Similarly knowing about RF, demodulation and amplifiers is more
>> useful to the real world than an rudimentary FM radio kit.
> 
> There seems to be a bit of a contradiction here.  You seem to be
> saying that shallow practice is not good (FM kit), but you also
> seem to be saying that basic theory (being able to parse
> arithmetic expressions) is not good either.
> 
... snip ...
> 
> For the compiler, I think it is very important to be able to
> parse arithmetic expressions.  Knowledge of automata theory can
> be invaluable.  For my current job, I recently had to make a
> small compiler for a stack machine.  Here's the tokenizer for
> lexical analysis:

You don't have to go to school to learn those things.  But it
helps, as does the ability to read.  On c.l.c we see many newbies
totally confused about how to handle interactive input, when all
they need is to build some sort of primitive lexer.  I have even
had relatively experienced people argue over the need for one char
lookahead.

-- 
 "Our enemies are innovative and resourceful, and so are we. 
  They never stop thinking about new ways to harm our country
  and our people, and neither do we."          -- G. W. Bush.
 "The people can always be brought to the bidding of the
  leaders.  All you have to do is tell them they are being
  attacked and denounce the pacifists for lack of patriotism
  and exposing the country to danger. It works the same way
  in any country."                         --Hermann Goering.

Tom Lucas wrote:
> I see little point in graduating knowing how to write a compiler or design
> an FM radio unless you are directly going into Sony's Radio Compiler
> division. Knowing what a compiler does and the sort of tricks current
> optimisers play will be more useful in the real world than knowing how to
> parse an arithmetic expression. Similarly knowing about RF, demodulation and
> amplifiers is more useful to the real world than an rudimentary FM radio
> kit.

There seems to be a bit of a contradiction here.  You seem to be saying
that shallow practice is not good (FM kit), but you also seem to be
saying that basic theory (being able to parse arithmetic expressions)
is not good either.

A person cannot design an FM radio without understanding many aspects
of electronic theory.  In the case I was speaking of, the electronics
course gives a bag of components, and a lot of theory.  You're expected
to make everything, including the amplifiers, filters, phase-lock loop
(from a pre-packaged VCO), etc.  Anyone who had not been paying
attention to the theory would simply not be able to make the radio.
The same course (or the next one) introduces Kalman filtering.  It's
not a connect-the-dots type project.

For the compiler, I think it is very important to be able to parse
arithmetic expressions.  Knowledge of automata theory can be
invaluable.  For my current job, I recently had to make a small
compiler for a stack machine.  Here's the tokenizer for lexical
analysis:

bool next_token (Token &token)
    {
        // Advance past any white space that might be present:
        while (isspace(operator[](index)))
            ++index;

        // If we encounter the end of the string after consuming white
space, there are no more tokens to read.
        if (operator[](index) == 0)
            return false;

        switch (operator[](index))
        {
        case '(' :
            token.type = Token::TYPE_LEFT_PARENTHESIS;
            token.offset = index++;
            token.length = 1;
            break;

        case ')' :
            token.type = Token::TYPE_RIGHT_PARENTHESIS;
            token.offset = index++;
            token.length = 1;
            break;

        case '!' :
            token.type = Token::TYPE_OPERATOR_NOT;
            token.offset = index++;
            token.length = 1;
            break;

And simple piece of compiler:

  case Token::TYPE_PREDICATE :
            if (typename
Infectable::predicate_functions.locate(operator ()(token.offset,
token.length)))
                instructions.suffix (Instruction(typename
Object::predicate_functions.RHE()));
            else
                instructions.suffix(Instruction(0)); // DEFECT: Need to
figure out semantics of not finding the predicate.
            break;

I  have no clue about optimization, but what I needed to know to make
this compiler can be found in the first few chapters of any compiler
book.  Self-reliance is achieved by focusing on a small bit and
learning that well, than reading the whole book casually and not
remembering anything.  I started dong this long ago after a
converstation I had with a professor just before my graduation.  I
asked, "There is so much to learn in the world...is it better to hurry
up and grab what you can and depend on other people for deep insight or
is it bet..."  he finished my sentenced quickly and said, "It's better
for you to know."  I asked, "But does one person have time in his life
to...?" he says, "Yes."  I asked, "Are you sure?" he said, "Yes."

-Le Chaud Lapin-

"Le Chaud Lapin" <unoriginal_username@yahoo.com> wrote in message 
news:1149611490.357297.11420@i39g2000cwa.googlegroups.com...

> I know of at least 3 technical universities that will not let you get a
> B.S.E.E. without knowing how to write a compiler, and will not let you
> get a B.S.C.S without knowing how to design an FM radio.  The idea is
> to quash any possibility that you might subsequently misrepresent your
> university as an idiot who cannot divide a number by 32 using
> bit-shifting.

I did a compiler design module as part of my course but the lecturer was a 
bit horny for lexical analysis and the entire course was spent on English 
linguistics. Of course, I'd heard this before hand and the only reason I 
took the course is because the same exam questions are asked year after year 
;-)

I see little point in graduating knowing how to write a compiler or design 
an FM radio unless you are directly going into Sony's Radio Compiler 
division. Knowing what a compiler does and the sort of tricks current 
optimisers play will be more useful in the real world than knowing how to 
parse an arithmetic expression. Similarly knowing about RF, demodulation and 
amplifiers is more useful to the real world than an rudimentary FM radio 
kit.

I think it is more important for someone to leave university understanding 
why it is important to optimise integer division rather than just have a 
tool box of techniques - they will learn those on the job. Of course, if the 
chap then fails to understand how the shifting works once he's been shown it 
then he has probably not grasped the most important skill from university - 
learning how to learn.

On Wed, 07 Jun 2006 01:07:12 +0300, the renowned Paul Keinanen
<keinanen@sci.fi> wrote:

>On Tue, 06 Jun 2006 15:23:50 -0400, Spehro Pefhany
><speffSNIP@interlogDOTyou.knowwhat> wrote:
>
>>On Tue, 06 Jun 2006 21:54:59 +0300, the renowned Paul Keinanen
>><keinanen@sci.fi> wrote:
>>
>>>On 6 Jun 2006 09:31:30 -0700, "Le Chaud Lapin"
>>><unoriginal_username@yahoo.com> wrote:
>>>
>>>>I just had a protracted argument about hiring someone who claimed to
>>>>have device driver writing experience, but did not know how to divide
>>>>and integer by 32 using bit shifting.
>>>
>>>How do you elegantly divide a _signed_ integer by 32 using shifts in
>>>systems that are using 2's complement representation ?
>>>
>>>Paul
>>
>>You use arithmetic shifts where the MSB is duplicated rather than
>>using a logical shift. 
>
>Any decent compiler (for any language) should do that for a signed
>data type.

But it's *not* guaranteed. 

ISO/IEC 9899:1999 (E) 3.4.1
1 implementation-defined behavior
unspecified behavior where each implementation documents how the
choice is made
2 EXAMPLE An example of implementation-defined behavior is the
propagation of the high-order bit
when a signed integer is shifted right.


>>In C and C++ the >> operator has implementation-defined results on a
>>signed integer, so it isn't going to be very elegant if it is written
>>to be portable. So I guess you could use Java which uses >> for
>>arithmetic and >>> for logical.
>
>That does not solve the problem. 
>
>What do you get even with MSB duplication in 2's complement notation,
>when you shift -3 one position to the right ? I got -2. 
>
>Now we have to discuss, what INT(-3/2) should be. At least I learned
>in primary school that this should be -1, not -2.
>
>Paul

In this case, both answers have an |error| = 0.5

If you take INT(-7/4) you get -1 using the division operator, and -2
using two arithmetic shifts. The former has an |error| of 0.75 vs 0.25
for the >> operator. In enjineering school I learned that smaller
errors are better. ;-) 



Best regards, 
Spehro Pefhany
-- 
"it's the network..."                          "The Journey is the reward"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com

CBFalconer wrote:
> Le Chaud Lapin wrote:
> > I know of at least 3 technical universities that will not let you
> > get a B.S.E.E. without knowing how to write a compiler, and will
> > not let you get a B.S.C.S without knowing how to design an FM
> > radio.  The idea is to quash any possibility that you might
> > subsequently misrepresent your university as an idiot who cannot
> > divide a number by 32 using bit-shifting.
>
> Well, the primary function of a university is to teach how to
> learn.  The details of what to learn are somewhat secondary.  The
> emphasis in a technical school is somewhat more concentrated on
> subject matter.  So the key thing in an interview is how fast does
> the interviewee catch on, rather than the detailed knowledge.

I certainly agree.

That's why I interview people on multiple axes to give them an
opportunity to show their value. I look for

1. intelligence
2. knowledge
3. passion

If a person seems to be lacking in knowledge, I attempt to check
intelligence/passion by asking questions that the person should know.
For example, one recent candidate had studied geophysics for
undergraduate (not electrical engineering or computer science), and was
having trouble with his knowledge domain on Windows.  So I asked him
questions about geophysics (based on what little I knew).  Because he
did not answer these questions very well, I had to conclude that he was
just looking for a job to have a salary.

I also started making generic exams to be used during interviews in our
(multi-billion $US) company (yes, strange, i know).  The idea is to
create a separation between the interviewer and the interviewee.  Some
candidates have cling - they cling to you like a charged sock - when
you try to get them to answer a question.  With paper exams, some
degree of objectivity can be maintained.

Incidentally, this person who did not know how to divide by 32 using >>
scored the lowest on the C++ exam of all candidates I interviewed.
During a heated post-interview discussion with HR, the HR rep implied
that the introduction of paper exams is less objective than what we
were doing before - ad hoc, hand-waiving qualifications with no notes
whatsover, just personal opinions.

-Le Chaud Lapin-

On Tue, 06 Jun 2006 15:23:50 -0400, Spehro Pefhany
<speffSNIP@interlogDOTyou.knowwhat> wrote:

>On Tue, 06 Jun 2006 21:54:59 +0300, the renowned Paul Keinanen
><keinanen@sci.fi> wrote:
>
>>On 6 Jun 2006 09:31:30 -0700, "Le Chaud Lapin"
>><unoriginal_username@yahoo.com> wrote:
>>
>>>I just had a protracted argument about hiring someone who claimed to
>>>have device driver writing experience, but did not know how to divide
>>>and integer by 32 using bit shifting.
>>
>>How do you elegantly divide a _signed_ integer by 32 using shifts in
>>systems that are using 2's complement representation ?
>>
>>Paul
>
>You use arithmetic shifts where the MSB is duplicated rather than
>using a logical shift. 

Any decent compiler (for any language) should do that for a signed
data type.

>In C and C++ the >> operator has implementation-defined results on a
>signed integer, so it isn't going to be very elegant if it is written
>to be portable. So I guess you could use Java which uses >> for
>arithmetic and >>> for logical.

That does not solve the problem. 

What do you get even with MSB duplication in 2's complement notation,
when you shift -3 one position to the right ? I got -2. 

Now we have to discuss, what INT(-3/2) should be. At least I learned
in primary school that this should be -1, not -2.

Paul

Spehro Pefhany wrote:
> On Tue, 06 Jun 2006 21:54:59 +0300, the renowned Paul Keinanen
> <keinanen@sci.fi> wrote:
>
> >On 6 Jun 2006 09:31:30 -0700, "Le Chaud Lapin"
> ><unoriginal_username@yahoo.com> wrote:
> >
> >>I just had a protracted argument about hiring someone who claimed to
> >>have device driver writing experience, but did not know how to divide
> >>and integer by 32 using bit shifting.
> >
> >How do you elegantly divide a _signed_ integer by 32 using shifts in
> >systems that are using 2's complement representation ?
> >

Not sure if this is elegant or correct (no time to check), but I would
just shift if the value is non-negative and shift-plus-or-in-1's if it
is negative:

 x = x & (1 << (sizeof(x) * 8 - 1)) ? ((x >> 5) | ~((~0U) >> 5)) : (x
>> 5) ;

Also I guess I failed to mention - in the exam that I gave the
interviewee, I told him up front that the value to be divided was
unsigned, and that he could ignore any round-off errors.

> You use arithmetic shifts where the MSB is duplicated rather than
> using a logical shift.
>
> In C and C++ the >> operator has implementation-defined results on a
> signed integer, so it isn't going to be very elegant if it is written
> to be portable. So I guess you could use Java which uses >> for
> arithmetic and >>> for logical.

You braved Java. I'm impressed. :)

-Le Chaud Lapin-

On Tue, 06 Jun 2006 21:54:59 +0300, the renowned Paul Keinanen
<keinanen@sci.fi> wrote:

>On 6 Jun 2006 09:31:30 -0700, "Le Chaud Lapin"
><unoriginal_username@yahoo.com> wrote:
>
>>I just had a protracted argument about hiring someone who claimed to
>>have device driver writing experience, but did not know how to divide
>>and integer by 32 using bit shifting.
>
>How do you elegantly divide a _signed_ integer by 32 using shifts in
>systems that are using 2's complement representation ?
>
>Paul

You use arithmetic shifts where the MSB is duplicated rather than
using a logical shift. 

In C and C++ the >> operator has implementation-defined results on a
signed integer, so it isn't going to be very elegant if it is written
to be portable. So I guess you could use Java which uses >> for
arithmetic and >>> for logical. 


Best regards, 
Spehro Pefhany
-- 
"it's the network..."                          "The Journey is the reward"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com