News for hackers. Stuff that matters.
Re:How recursion got into Algol 60: a comedy of errors by kabdib on Thursday August 27, 2015 @07:39PM (#10132837)
I've encountered knee-jerk negative reactions to recursion from most firmware engineers.

Then one day I got one to laugh at this byte-saving routine to do some multiplications:

    X32:    BSR X16
    X16:    BSR X8
    X8:     BSR X4
    X4:     BSR X2
    X2:     ADD A
            RET
Recursion. In assembly language. We were six bytes shy of filling our code space, but we had gobs of stack, and I got about 60 bytes back from our stupid compiler with this. When my cow-orker saw it, he thought for a moment, smiled, said "You're one sick dude, you know that?" and we checked it in.
Re:How recursion got into Algol 60: a comedy of errors by userbinator on Friday August 28, 2015 @12:05AM (#10133685)
The "calling itself inline" pattern is well known in the demoscene/sizecoding community as a way to repeat something a small fixed number of times with neither an explicit loop nor duplicating code, and probably was independently discovered by quite a few individuals.

Here is one of the more interesting applications, a function that converts a 16-bit word in a register to a string of 4 hex digits in only 24 bytes of code, and can also be called to convert bytes and nybbles (x86):

        ; output value of AX as four hex digits to ES:DI
    write_hex_word:
        xchg al, ah
        call write_hex_byte
        xchg al, ah
        ; output value of AL as two hex digits to ES:DI
    write_hex_byte:
        push ax
        shr al, 4
        call write_hex_nybble
        pop ax
        ; output lower nybble of AL as hex digit to ES:DI
    write_hex_nybble:
        and al, 15
        cmp al, 10
        sbb al, 69h
        das
        stosb
        ret
Re:How recursion got into Algol 60: a comedy of errors by kabdib on Friday August 28, 2015 @12:49AM (#10133780)
Thanks. You can learn a lot from the demoscene folks.

Of course, your cow-orkers might wish you hadn't, depending on the amount of restraint you can summon :-)

Re:How recursion got into Algol 60: a comedy of errors by mikeash on Thursday August 27, 2015 @08:01PM (#10132929)
Dear god. I don't know if we should give you a Nobel Prize or put you in prison. Probably both.
Re:How recursion got into Algol 60: a comedy of errors by kabdib on Thursday August 27, 2015 @08:26PM (#10132992)
Pretty much that reaction :-)
Re:How recursion got into Algol 60: a comedy of errors by hellbanner on Thursday August 27, 2015 @11:35PM (#10133614)
Can you explain this a bit? I read http://docs.oracle.com/cd/E19455-01/806-3773/instructionset-... but I'm not sure I follow what X32 is.. times 32?
Re:How recursion got into Algol 60: a comedy of errors by shiro on Friday August 28, 2015 @05:56AM (#10134532)
"X32:" etc. are labels, e.g. just names of functions or destinations of jump. Suppose you want to multiply A-reg by 4. Your code calls subroutine X4. That's immediately calls subroutine X2 (BSR X2), which doubles A (ADD A), and return. The return location is the next instruction of BSR X2--which is actually overlapping the subroutine X2. It doubles A again (ADD A), and returns to your code.
Re:How recursion got into Algol 60: a comedy of errors by UnquietTinkerer on Saturday August 29, 2015 @12:11PM (#10140451)
I think BSR here stands for "branch to subroutine", i.e. CALL.
Re:How recursion got into Algol 60: a comedy of errors by kabdib on Thursday August 27, 2015 @10:00PM (#10133356)
I should add this: Why not just shift left? It's been a while, but I think the ADD A was really some 16-bit ADD. The key to making it small was this "inline recursion" thing, which wouldn't have occurred to most of the crusty firmware folks I've worked with because of fear.
Re:How recursion got into Algol 60: a comedy of errors by quantumtremor on Thursday August 27, 2015 @09:01PM (#10133117)
ELI someone who knows mips?
Re:How recursion got into Algol 60: a comedy of errors by pbsd on Thursday August 27, 2015 @09:34PM (#10133263)
Basically equivalent to this C code (assuming BSR = procedure call):

    int x2(int x) { return x + x; }
    int x4(int x) { return x2(x) + x2(x); }
    int x8(int x) { return x4(x) + x4(x); }
    int x16(int x) { return x8(x) + x8(x); }
    int x32(int x) { return x16(x) + x16(x); }
Re:How recursion got into Algol 60: a comedy of errors by bbcbasic on Thursday August 27, 2015 @10:56PM (#10133516)
Hmm. How is this recursion?

Maybe I don't understand what the word recursion means, but I thought that you'd have to call yourself directly or indirectly.

Re:How recursion got into Algol 60: a comedy of errors by LesZedCB on Thursday August 27, 2015 @11:23PM (#10133587)
It's not recursion in the sense that it calls itself. However, it does divide the problem into smaller (though explicitly defined) chunks, which is still recursion.

You could state it that the multiple by a power of two is the sum of the multiples of one order of magnitude base 2 lower.

Re:How recursion got into Algol 60: a comedy of errors by ScottBurson on Friday August 28, 2015 @12:04AM (#10133683)
You're right. This isn't recursion by any definition I know. Cute, though.
Re:How recursion got into Algol 60: a comedy of errors by bbcbasic on Friday August 28, 2015 @05:10AM (#10134401)
Yes from the answers it seems it is recursion, as long as you stretch the definition of recursion to mean making subroutine calls, or code that can be refactored into a recursive solution.

By these definitions, all but the most trivial code is recursive.

Re:How recursion got into Algol 60: a comedy of errors by sgustard on Friday August 28, 2015 @01:24AM (#10133872)
It's equivalent to this recursive function, just change x2(n) to x(n, 2) and so on.

  // e is a power of two
  int mult(x, e)
    return e==1 ? x : mult(x, e/2) + mult(x, e/2)
  end
Re:How recursion got into Algol 60: a comedy of errors by blt on Thursday August 27, 2015 @09:43PM (#10133299)
What instruction set is this?
Re:How recursion got into Algol 60: a comedy of errors by kabdib on Friday August 28, 2015 @12:53AM (#10133789)
My fuzzy memories of an STM8, made by ST Microelectonics.

The piece of code in question was to use the chip as a smart power controller. Worked pretty well, aside from the limited code space.

Here's a blog entry about the little project: http://www.dadhacker.com/blog/?p=1911

Apparently the original code did multiplies by 10s, so the leaf routine was a few more instructions.

Re:How recursion got into Algol 60: a comedy of errors by bliti on Thursday August 27, 2015 @10:46PM (#10133491)
Brilliant! Let's make sure to include this in the standard tech interview questions set. We only hire the top 1% of the top 1%. Some Assembly required. :D
Re:How recursion got into Algol 60: a comedy of errors by copsarebastards on Friday August 28, 2015 @12:09AM (#10133691)
> Brilliant! Let's make sure to include this in the standard tech interview questions set. We only hire the top 1% of the top 1%.

First of all, that's the top 0.01%. Second of all, with that strategy, no you don't because the top 0.01% are going to walk out of interviews that ask dumb brain teasers. The best programmers are ones who can solve problems in the context of a team and codebase, with the help of the internet and iteration, not solve obscure but not-really-that-hard problems in 15 minutes.

Re:How recursion got into Algol 60: a comedy of errors by bliti on Friday August 28, 2015 @01:46AM (#10133918)
That's the joke. :)