Re: [AnyC-devel] Recursion

[Patrick E. <pa...@pa...>]

On Wednesday 18 July 2001 12:49, you wrote:
> > I would be interested in making it possible to work with both
> > situations.  I imagine it would be possible to do with some sort
> > of generic variable request system.  If you need a variable, you
> > ask it for code to get to that variable.  It decides if it's
> > going to be local or global in scope based on if the processor
> > supports local variables/recursion.  I haven't thought about it
> > that much yet.
>
>   I think you may be getting two different things confused, or else
> I don't understand what you're saying.  Since the PICs have
> separate data and code memory, there are separate data and code
> stacks.  You can still implement a data stack (up to 256 bytes)
> with the PICs.  In fact, I really don't see any other way to make a
> proper C compiler except to use a data stack.  The reason is: the
> compiler has no way to know what way the independent functions will
> be called.  Maybe function A will call function B, or C will call
> A, which will then call B.  Because of this, there are only two
> options I see for local variables:
> 1) Use a data stack for all local variables
> 2) Allocate space for all local variables on the heap at run-time. 
> This means you will be using data space for every local variable in
> every function all the time, whether that function is running or
> not.  I think I had a routine that would implement a data stack on
> the PICs in the code, although I'm not sure.

With the PIC16F877, the data memory is fragmented.  It you look on 
page 13 of the pdf for it, you can see that the largest unfragmented 
section is 112 bytes.  Using the FSR and INDF alone, you can access 
176 actual bytes of data memory.  The full amount of memory is 386 
bytes and can be accessed with the FSR and the IRP bit of the STATUS 
register.  The stack will have to know when it's going to hit a 
boundary in order to jump to the next section.  Alternatively, 
variables could be pre-allocated in order that you don't have to 
worry about hitting the end of the stack space.  It's probably 
possible to build some sort of psuedo-stack-machine in the compiler 
that will deal with this fragmented data memory issue.

>   So that data stack is not the problem.  The problem is that the
> code stack is either limited to the hardware stack, or you have to
> do an incredible amount of work to get around it and implement it
> in software.  With the PICs, this is very difficult, which is why
> no one has done it.  With the AVRs, it looks much, much easier.

It's possible to do, but I doubt it would be worth it.  With the 
chips not natively supporting it, it would be pretty lame to generate 
a slow software solution when a better idea would be for the 
programmer to rewrite their code to not use recursion.  Recursion 
certainly isn't a requirement, and probably wouldn't help with 99.5% 
of the appplications of the PIC.

Limited recursion using the hardware stack is possible on the 877, 
since it has 8 levels of stack.  I'm more worried about the data 
issues than the difficulties with the hardware stack.

>   All the work I did on the original version was centered around
> the PIC line, but seeing the AVR datasheets makes the PICs seem
> very old-fashioned. I would still like to support the PICs, I'm
> just not sure they will ever be able to do what the AVRs can.
>
>   Where do you get your chips?  The major sources for amateur
> electronics I have found are Digikey, Mouser, and Jameco.  Digikey
> now sells several of the AVR (two pages worth), including some with
> no RAM or EEPROM for $2.  Those might be interesting to implement a
> virtual machine on eventually...

I get my chips at Active Components.  It's a division of the company 
that runs www.future-active.com.  It's a local store... I generally 
just drive over and pick up the parts I want.  They happen to stock 
the 877 and the 84, so it makes it easy for me to acquire them.  I 
could always special order things, but that's another step.

>   I think I read on the Atmel site that the AVRs were designed with
> C compilers in mind... that's why they have 32 general-purpose
> registers.  I have not done optimization work, but I can see how 32
> GP registers would make optimization much more efficient.  They are
> rated at 4 or 8 Mhz, but they are designed like the Scenix chips,
> which means many of the instructions are 1 instruction per clock
> cycle.  The PICs use the traditional method which requires 4 clock
> cycles per instruction.  So actually the AVRs should be faster than
> the PICs at top speed.  If you count the reduction in overhead for
> the data stack and the 32 GP registers, I guess the AVRs should be
> 2-5 times faster for C code.

One issue is that I just got my PIC programmer to work under Linux.  
It took me a while to find something that would work to program the 
PIC16F877 under Linux.  I spent more than a week unsucessfully trying 
to program the PIC, until I finally had success with the NOPPP 
programmer and the 16F84, which then required some hardware and 
software adjustments to work with the 877.  If you want, you can read 
about what I did at http://patearl.net/pic_html

I'm not in much of a hurry to build another programmer and buy more 
chips.  I don't have a lot of money at the moment, as I'm saving up 
to buy a welder with my friend.

That said, the AVR chips sound quite delightful, and under other 
circumstances, I'd probably jump at the opportunity to use them.  As 
for now though, getting the PIC to work nicely is, to me, a fun 
challenge.  I enjoy taking limited resources and making them work 
well.

I've been studying the output from the compiler.  It's pretty icky in 
terms of speed.  I don't even understand parts of it.  I still need 
to read more of it, but I'll probably have some questions for you, if 
you think you can answer them.

>   Did you say you are in Canada?  I'm not sure where Digikey sells
> to, but I imagine you can get them through Digikey.  They are a
> little high priced, but the service is excellent (fast delivery and
> phone help if you need it).
>
> Digikey is www.digikey.com and Atmel is www.atmel.com.

Ya, I'm in Canada.  I'll have to try ordering from DigiKey sometime.  
I keep hearing about them.

Look forward to hearing from you once again.

        Patrick Earl