Quick Compiler Question

So I was thinking about C programs a short while ago, and a problem occurred to me.

Let's say that I have a function in which, say, we define a variable. It might look something like this:

int dicks (int cocks)
{
    int wangs;
    /* Do stuff to wangs and cocks here */
    return wangs;
}

Looking at int wangs; it seems that the compiler translates that line into "allocate space for an integer and return a pointer to it." If this is a case, is the compiler setting aside space for a new integer every time I run the function, or does it optimize by assuming that I'm only going to have one instance of it and just set aside space for a single int?

Whatever the answer to that previous question is, how would the compiler handle a recursive function? How would

Never mind, I'm an idiot. I forgot about registers and the stack for a second. I revoke my previous questions.

NEW QUESTION: What is the point of tail-call optimization? If all it does is convert recursive functions into iterative ones, why not just program them that way in the first place?

It doesn't convert them into iterative ones directly. The "iteration" is an illusion, caused by not having to use additional stack frames. The point is that it allows you to (in some cases) write cleaner code without having to worry about overflowing the stack.

Looking at int wangs; it seems that the compiler translates that line into "allocate space for an integer and return a pointer to it." If this is a case, is the compiler setting aside space for a new integer every time I run the function, or does it optimize by assuming that I'm only going to have one instance of it and just set aside space for a single int?
It could be alloced in the stack or in a register. You can even try to force the compiler to use a register, however you can always get the reference of a variable with & in C, so if you do, it would be stack allocated, however functions will always return a value (which could be a pointer if you wish). Try disassembling some functions if it's still not clear or reading a good compiler book.

NEW QUESTION: What is the point of tail-call optimization? If all it does is convert recursive functions into iterative ones, why not just program them that way in the first place?
While tailcalls + TCO means you can emulate iteration with them, it doesn't mean you have to. On the other hand, there are many legit uses of using tailcalls for things like stack machines, mutually recursive functions and things like networks of closures which can get compiled down to lovely jmps/gotos without wasting stack space. Just because in some languages like Scheme, they think that LAMBDA and TCO lead to the ultimate iteration construct, doesn't mean that's its only usage, or that you absolutely have to use tail-recursion to implement iteration. For example in another Lisp, CL, we have plenty of iteration constructs, and if those aren't enough, you can very easily define more using macros( you can do thte same in Scheme, though I don't think they ever had real macros properly standardized, though most implementations support them, and they were defined in the R4RS^? appendix as well).

Another thing is that LAMBDA+TCO is also the ultimate GOTO, unlike normal GOTO, it can be used to do computed GOTO and some really crazy macros. It really takes a while until this sinks in, but you can do some really crazy tricks and optimizations using it.

>>3
you can do thte same in Scheme, though I don't think they ever had real macros properly standardized, though most implementations support them, and they were defined in the R4RS? appendix as well
What, is syntax-case not real enough for you? It's been around since '92^[1] and was standardized in R6RS^[2]. It's hygienic by default, but you are allowed to explicitly break hygiene. Having syntax-case also gives you the higher-level macro systems like syntax-rules and extend-syntax for free as they are both about 8 lines of code.

We also have iteration constructs (no really, real ones). First there is the ugly 'do' which you should be familiar with. Also, SRFI 42^[3] gives you eager comprehensions and SRFI 41^[4] gives you lazy comprehensions. There has been lots of other work on iteration in Scheme, notably Olin Shivers' "Anatomy of a loop"^[5] which the bastard hasn't released code for, and Alex Shinn wrote a nice but really long post on c.l.s a few years back^[6].

The problem with general iteration, not special cases like comprehensions, is that it is difficult to create a set of iteration constructs that are powerful, that make what you are doing explicit on a high level, and which get the semantics just right. CLs loop macro is a good start, but it's far from perfect and lower level iteration is just as much a chore as writing it out with TCO and recursion

[sub]--
1. Writing hygienic macros in Scheme with syntax-case, http://www.cs.indiana.edu/~dyb/pubs/tr356.pdf
2. Revised[sup]6[/sup Report on the Algorithmic Language Scheme,Standard Libraries, Chapter 12 http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-13.html
3. SRFI 42: Eager Comprehensions, http://srfi.schemers.org/srfi-42/srfi-42.html
4. SRFI 41: Streams, http://srfi.schemers.org/srfi-41/srfi-41.html
5. Anatomy of a Loop, http://www.cc.gatech.edu/~shivers/papers/loop.pdf
6. Yow! LOOP macros are LOOPY! http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/0cb91974bc35a86c/060dcac5ea812398?#060dcac5ea812398[sub]

>>5
I hate it when I BBCode fail :(

>>6
[code]
// ==UserScript==
// @name          EXPERT BBCODE FRAMEWORK
// @namespace     http://userscripts.org/GetEnterpriseContent.jsp?EID=983298183&cd=china&page=EnterpriseRenderer1
// @description   Advanced Shiichan BBCode Previewer Integration Suite.
// @include       http://dis.4chan.org/read/*
// ==/UserScript==


// EXPECT THESE FEATURES IN NEXT VERSIONS:
// - Improved scalability (working on all textareas, not only in threads).



////////////////////////////////////////////////////////////////////////////////////
//////
//////
//////   )   ___      ___   __     __)  _____     _____     _       _____) _____  
//////  (__/_____)  /(,  ) (, /|  /|   (, /   )  (, /   ___/__)   /       (, /   )
//////    /        /    /    / | / |    _/__ /     /   (, /       )__       /__ / 
//////   /        /    /  ) /  |/  |_   /      ___/__    /      /        ) /   \_ 
//////  (______) (___ /  (_/   '     ) /     (__ /      (_____ (_____)  (_/       
//////                              (_/                        )                  
//////
////// 
//////



/

>>7
I have it installed
Improved scalability (working on all textareas, not only in threads).
and I was posting from the front page.

>>7

Oh the ironing.

>>7
I tried this script before, it didn't work.

NEW QUESTION: What is the point of tail-call optimization? If all it does is convert recursive functions into iterative ones, why not just program them that way in the first place?
Because iterative syntax doesn't compose, i.e. you can't put things together without losing iteration. For example, say I have this for debugging:

(define-syntax trace (syntax-rules () ((trace op . args) (tracer 'op op . args))))
(define (tracer name op . args)
  (write (cons name args)) (newline)
  (apply op args))

Then this is still iterative:
(define (fib n)
  (let loop ((a 0) (b 1) (n n))
    (if (zero? n)
        b
        (trace loop b (+ a b) (- n 1)))))

Of course that's just the tip of the iceberg, this applies to lots of wrappers, mutually recursive procedures, state machines ( http://www.cs.brown.edu/~sk/Publications/Talks/SwineBeforePerl/ ), parsers...

Once you have tasted the freedom of TCO, everything without it feels like a bondage-and-discipline language.

>>9
I WAS TYPING FAST, OK?

By real macros, I just meant what is known in Scheme as low-level macro. In its most basic form it's a function which is applied on a form whose CAR matches the macro name, and it returns a new expression which will be used in its place (macroexpansion is obviously recursive) when compiling or evaling. Using low-level macros in Scheme is less common since it's a Lisp-1, and that comes with its associated problems when dealing with low-level macros^[1] (this is a non-problem in Lisp-n's), which is why hygienic macros are preferred in Scheme.

---
^[1] - http://www.nhplace.com/kent/Papers/Technical-Issues.html

>>11
I think they should add define-syntax-rule to r7rs. For small examples, like yours, they make the code much less crufty.

>>13
I'd say that syntax-case would suffice for your definition, although it returns a "syntax object" instead of a plain expression; the only real difference is some additional lexical information. If you are wanting something more CL-like, perhaps Syntactic Closures or Explicit Renaming macros?

syntactic-closures:
(define-syntax swap!
  (sc-macro-transformer
   (lambda (form environment)
     (let ((a (close-syntax (cadr form) environment))
           (b (close-syntax (caddr form) environment)))
       `(let ((temp ,a))
          (set! ,a ,b)
          (set! ,b temp))))))

explicit renaming:
(define-syntax swap!
  (er-macro-transformer
   (lambda (form rename compare)
     (let ((a (cadr form))
           (b (caddr form))
           (temp (rename 'temp)))
       `(,(rename 'let) ((,temp ,a))
            (,(rename 'set!) ,a ,b)
            (,(rename 'set!) ,b ,temp))))))
Neither of these are standardised, and unlikely to be unless they change the mechanism for defining macro transformers.

this is a non-problem in Lisp-n's
I'll need to look at that paper, but I'm not convinced that there are no problems with low-level macros just because you have n namespaces. There is still the issue of shadowing builtins (you can in CL, right?), and other functions and the CL solution seems to be "don't do it, bad little lisper".

btw, what is the equivalent of make-variable-transformer in CL? It allows for identifers that may or may not be in the CAR position to be macros.
Example:
(define-syntax define-list-macro
   (syntax-rules ()
     [(_ name value)
      (begin
        (define tmp value)
        (define-syntax name
          (make-variable-transformer
            (lambda (stx)
              (syntax-case stx (len set!)
                [(x len)             #'(length tmp)]
                [(set! x v)          #'(set! tmp v)]
                [(x e* (... ...))    #'(tmp e* (... ...))]
                [x (identifier? #'x) #'tmp])))))]))

(define-list-macro foo (list 1 2 3))

(printf "~s ~s\n" foo (foo len)) ;=> (1 2 3) 3

(set! foo (list 2 3))

(printf "~s ~s\n" foo (foo len)) ;=> (2 3) 2

(foo 1 2 3) ;=> &assertion in apply: (2 3) not a procedure.


Example shamelessly taken from http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/96b07d431f1a66de/fb7f559e2f7b5243?#fb7f559e2f7b5243

>>14
Also, I think that hygiene by default is just a more reasonable default. Not having to worry about what is being redefined and where makes writing macros easier, and this is especially true when you start layering macros on top of one another, or you are generating them.

I'll need to look at that paper, but I'm not convinced that there are no problems with low-level macros just because you have n namespaces. There is still the issue of shadowing builtins (you can in CL, right?), and other functions and the CL solution seems to be "don't do it, bad little lisper".
You can achieve hygiene with gensyms and symbol-macros¹. As for shadowing built-ins, that can only happen if the user explicitly wants to do that (and that would be an error, unless you shadow the symbols in the package via defpackage or shadow): so you could only shadow a built-in, if you're explicitly trying to cause the macro to bind said built-in function or macro via flet/labels/macrolet.

btw, what is the equivalent of make-variable-transformer in CL? It allows for identifers that may or may not be in the CAR position to be macros.

You have symbol macros (define-symbol-macro (global), symbol-macrolet (local)) which let you expand symbols to random expressions, and normal macros for identifiers in the CAR position.


---
¹ - http://p-cos.net/documents/hygiene.pdf

>>16
I never meant to imply that you couldn't have hygiene in CL, merely that I didn't see how the separate namespaces got rid of the problem. The Pitman paper seems to suggest that I'm right, that it doesn't completely solve the problem, only lessens it.

I only really use TCO for state machines. Writing them without recursion is about as much fun as mountain climbing with a bicycle strapped to your back.

http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion

... suggest that I'm right, that it doesn't ...
Reading over my post again, I'm pretty certain that that comma should be a semicolon. Any Grammar Nazis want to confirm that?

>>20
i think that your post shouldnt have punctuation at all and also no capital letters
correct grammer turns people into tripfags
off to /b/ with you

>>21

I'm not sure how I feel about this post.
I disagree, and yet on some level I think he has a point.

>>16
You can achieve hygiene with gensyms and symbol-macros¹
To achieve this, all binding forms (defvar, defun, defmacro, let, let*, flet, macrolet, and so on) have to be reimplemented

Issue LISP-SYMBOL-REDEFINITION: http://www.lispworks.com/documentation/HyperSpec/Issues/iss214_w.htm

(let ((let '`(let ((let ',let)) ,let)))
  `(let ((let ',let)) ,let))

VALID CL CODE


`'.
   `.'````.
   .  @  \@
   s     _\'
    .  .---'
   ,.  /
 '`\\   \        LISPFAG
' |  \ \|        -------
| |   \ \
| |    \ \
| |   . \ \
| |  / ` \ \
| |=/ /=====
| `/ /     /
\  \/     /
'````    /
//  | |  |
    | |  |
    | |  |
    | |_ |____
    |===| ====|

>>24
valid yes, useful no

Personally, I achieve hygiene with a bar of soap and a tub of water, but hey, different strokes.