User:Renamed user awfwvowjvwrvnwio/How to implement closures in assembly

This is a tutorial in how to implement closures in x86 assembly. We will assume a Win32 or WOW64 architecture and the NASM assembler.

This can be easily adapted to other operating systems by changing allocation methods and can easily be translated to other x86 assemblers.

See the header /metafuncs.h for an implementation in C++ of the combinators.

Method

This works by having a function that fills in a function skeleton with the argument(s) it received.

For instance, the skeleton for the K combinator is:

mov eax, 0xCCCCCCCC ;# this magic number will be replaced by the K function's argument.
ret 0x0004 ;# stdcall

Note it assembles into: B8 CC CC CC CC C2 04 00 and the 4 bytes to replace are at 1 byte from the start.

Then we make the K function, that works as follows:

We allocate a block in a executable heap (created by calling the function HeapCreate in KERNEL32.DLL or RtlCreateHeap in ntdll.dll) that is 8 bytes long.

The code is below:

#include <Windows.h>

void* heap = NULL;

void init() {
  heap = HeapCreate(0x40000, 0x1000, 0x100000); // allow execution of blocks in heap
}

char* K_skeleton = "\xB8\xCC\xCC\xCC\xCC\xC2\x04\x00";
int (__stdcall *Func)(int arg);
Func K(int s) {
  Func result = (Func)(HeapAlloc(heap, 0, 8));
  char* res = (char*)(result);
  memcpy(res, K_skeleton, 8);
  *((int*)(res + 1)) = s;
  return result;
}

Partial functions

We then perform partial function evaluation using the same skeleton technique.

;# Code generated:
;# 0x00: push ebp
;# 0x01: mov ebp, esp
;# 0x03: push dword [ebp+0x08]
;# 0x06: push dword "arg"
;# 0x0b: mov eax, "fun"
;# 0x10: call eax
;# 0x12: mov esp, ebp
;# 0x14: pop ebp
;# 0x15: ret 0x0004

;# Curries a two-argument function with one argument already given.
;# When called with f and x, produces a function g of y which
;# calls f with x and y. The produced function is STDCALL.
;# Function types supported: f can be CDECL or STDCALL (note line
;# 0x12 in code generated, cleans up arguments left on stack if
;# function is CDECL or does nothing if STDCALL.
CurryFunction2_1:
push ebp
mov ebp, esp
push dword 0x00001000
push byte +0
call AllocateCodeBlock
mov dword [eax], 0xFFEC8B55
mov dword [eax+0x04], 0x00680875
mov ecx, [ebp+0x08]
mov [eax+0x0C], ecx
mov ecx, [ebp+0x0C]
mov [eax+0x07], ecx
mov byte [eax+0x0B], 0xB8
mov dword [eax+0x10], 0xE58BD0FF
mov dword [eax+0x14], 0x0004C25D
pop ebp
ret 0x0008

align 16

"AllocateCodeBlock" is a function allocating a readable, writable, executable memory block that takes two arguments and is STDCALL as are many of the functions in the library. It takes two arguments: a starting address (0 if allow system to decide, in here it is the case) and a memory size (in this case 4096 bytes, the minimum size). Simply, it allocates a readable, writable and executable memory block and fills it with a 24-byte skeleton with two 4-byte blank spots, one 7 bytes after the start and the other 12 bytes after.

Those are for the first argument of the function given and the function itself, respectively. This is a partial function evaluator because it takes a two-argument function f as its first argument and the first argument of that function x and produces a partially evaluated function g which takes an argument y and returns f(x, y). This calling operation is STDCALL, again.

I'll soon perform a full currying operation using another skeleton operation.