!!! -*- mode: asm; asm-comment-char: ?! -*- !!! SPARC assembly language !!! Church numerals !!! Copyright 2009, Matthias Andreas Benkard !!! Compile with: !!! gcc -o church-numerals church-numerals.S !! 16 extended words (64 bit) for the register window. !!#define FRAME_SIZE (16*8) !! 16 words (32 bit) for the register window. #define FRAME_SIZE 64 .section ".text" .global main .id: save %sp, -FRAME_SIZE, %sp .id_set_function: !! function to call (set 0, %l0) sethi %hi(0), %l0 or %l0, %lo(0), %l0 mov %i0, %o0 .id_footer: ret restore %o0, 0, %o0 ! move %i0 to %o0 .id_end: nop .church_function_call: call %l0 nop .church_copy_function: mov %l2, %o0 set .church_function_call, %o1 set (.church_copy_function - .church_function_call), %o2 !! We can't simply `call memmove' here because that would make !! this a relative branch. Relative branches are bad. Bad, !! bad, bad. See, we want to relocate this code by copying stuff !! around. Relative branches hurt. Really, they do. set memmove, %g1 call %g1 nop add %l2, (.church_copy_function - .church_function_call), %l2 .church_end: nop !!! The Church numeral for zero. As is, it returns a copy of id, but it's !!! also a template for all other Church numerals. Comments in square !!! brackets signify places that church_succ alters. !!! !!! A Church numeral generally expects a subroutine pointer in %i0 and !!! returns a pointer to a newly allocated function closure in %i0 and its !!! size in %i1. The closure, when called, calls the subroutine passed to !!! the numeral n times where n is the number represented by the Church !!! numeral. church_zero: save %sp, -FRAME_SIZE, %sp !! Allocate enough room for id set (.id_end - .id), %o0 church_zero_call_malloc: add %o0, 0, %o0 ! [modify this] mov %o0, %l1 set malloc, %g1 call %g1 nop mov %o0, %l0 church_zero_copy_id_header: !! Copy id header to allocated region mov %l0, %o0 set .id, %o1 set (.id_footer - .id), %o2 set memmove, %g1 call %g1 nop add %l0, (.id_footer - .id), %l2 church_zero_copy_id_footer: !! [Insert function call copying here] !! Copy id footer to allocated region mov %l2, %o0 set .id_footer, %o1 set (.id_end - .id_footer), %o2 set memmove, %g1 call %g1 nop !! Modify function pointer within the closure. add %l0, (.id_set_function - .id), %l2 srl %i0, 10, %l4 and %i0, 0x3ff, %l5 ld [%l2], %l3 or %l3, %l4, %l3 st %l3, [%l2] ld [%l2+4], %l3 or %l3, %l5, %l3 st %l3, [%l2+4] !! Return address to region along with size mov %l0, %i0 mov %l1, %i1 ret restore church_zero_end: nop !!! Church numeral successor function. This is the interesting part of the !!! programme. It expects a Church numeral in %i0 and its size in %i1 and !!! returns the successor numeral in %i0 along with its size in %i1. church_succ: !! %i0: block !! %i1: length of block save %sp, -FRAME_SIZE, %sp add %i1, (.church_end - .church_copy_function), %l1 mov %l1, %o0 set 1, %o1 call calloc nop mov %o0, %l0 !! Copy first part of the Church number. mov %i0, %o1 set (church_zero_copy_id_footer - church_zero), %o2 call memmove nop !! Modify closure allocation size. add %l0, (church_zero_call_malloc - church_zero), %l2 ld [%l2], %l4 and %l4, 0xfff, %l4 ! load lower 12 bits add %l4, (.church_copy_function - .church_function_call), %l4 ld [%l2], %l3 srl %l3, 12, %l3 sll %l3, 12, %l3 or %l3, %l4, %l3 st %l3, [%l2] !! Note that we have now got the number of synthesised !! instruction blocks, multiplied by the block length, in %l4. udiv %l4, (.church_copy_function - .church_function_call), %l4 dec %l4 !! Add an instance of .church_copy_function. add %l0, (church_zero_copy_id_footer - church_zero), %o0 set .church_copy_function, %o1 set (.church_end - .church_copy_function), %o2 call memmove nop !! Copy the second part of the Church number. add %l0, (church_zero_copy_id_footer - church_zero + .church_end - .church_copy_function), %o0 add %i0, (church_zero_copy_id_footer - church_zero), %o1 umul %l4, (.church_end - .church_copy_function), %o2 add %o2, (church_zero_end - church_zero_copy_id_footer), %o2 call memmove nop mov %l0, %i0 mov %l1, %i1 ret restore %g0, %g0, %g0 !!! An example function to test the numerals with. You should be able !!! to substitute any function that obeys the SPARC calling conventions !!! for it. increment: retl inc %o0 main: save %sp, -FRAME_SIZE, %sp set church_zero, %o0 set (church_zero_end - church_zero), %o1 call church_succ nop call church_succ nop call church_succ nop call church_succ nop mov %o0, %l0 mov %o1, %l1 set increment, %o0 call %l0 nop mov %o0, %l0 clr %o0 call %l0 nop mov %o0, %o1 set .msg, %o0 call printf nop ret restore %g0, 0, %o0 .section ".data1" .align 4 .msg: .ascii "Result: %d\n\0" .msg_end: .skip 4