Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Partial application in LLVM

I am trying to create a function "add" that can be applied to a single argument, and subsequently another. I can't figure out how to represent this with LLVM IR, as I don't understand how to call a function with a single value, then save the value somewhere in memory and return another function that is applied to that val. I would need some sort of closure mechanism in LLVM.

I have searched for implementations of this in C so that I could view the emitted LLVM through clang, but the solutions I found were wildly complex, so I thought I might just investigate LLVM directly.

This would be the uncurried version

define i8 @add(i8 %a, i8 %b) {
entry:
  %res = add i8 %a, %b
  ret i8 %res
}

And somehow I'd like for add(1) to return an i8 (i8) type. I figure I'll have to split the function up somehow.

ps. I am looking into this because I'm working on a compiler for a small functional language, so I'm looking for any advice concering the implementation of partial application/currying in compiler design in general.

Update: I now have the following code working, but it's a quite complicated and I don't think it'll be easy to generate automatically

declare i32 @printf(i8* noalias nocapture, ...)

define { i8, i8 (i8, i8) * } @add1(i8 %a) {
  ; allocate the struct containing the supplied argument 
  ; and a function ptr to the actual function
  %nextPtr = alloca { i8, i8 (i8, i8) * }
  store { i8, i8 (i8, i8) * } { i8 undef, i8 (i8, i8) * @add2 }, { i8, i8 (i8, i8) * } * %nextPtr
  %next0 = load { i8, i8 (i8, i8) * } * %nextPtr

  ; insert the supplied arg into the struct
  %next1 = insertvalue { i8, i8 (i8, i8) * } %next0, i8 %a, 0
  ret { i8, i8 (i8, i8) * } %next1
}

define i8 @add2(i8 %a, i8 %b) {
  %res = add i8 %a, %b
  ret i8 %res
}

define i8 @main() {
  ; call add(35) resulting in 'fn' of type {35, &add2}
  %res1 = call { i8, i8 (i8, i8) * } @add1(i8 35)

  ; get the arg of the first call, ie element 0 of the resulting struct
  %arg = extractvalue { i8, i8 (i8, i8) * } %res1, 0
  ; similarily get the function ptr
  %fn = extractvalue { i8, i8 (i8, i8) * } %res1, 1

  ; apply the argument to the function
  %res = call i8 %fn(i8 %arg, i8 30)

  ; print result  
  %ptr = alloca i8
  store i8 %res, i8* %ptr
  call i32 (i8*, ...)* @printf(i8* %ptr)

  ret i8 0
}
like image 724
altschuler Avatar asked Oct 21 '22 10:10

altschuler


1 Answers

I've written this example C code to emulate what my functional language compiler supports for 'partial application' (lambda calculus). I don't emit 'C' code but, instead, directly emit to LLVM-IR. You can see the LLVM-IR perspective by just emitting from the sample source:

clang -S -emit-llvm partial.c

The compiler is triggered to emit the partial machinery in LLVM-IR when it passes over the AST node reflecting a parenthetically wrapped (give or take a few additional details) expression.

Hope this helps.

like image 86
Frank C. Avatar answered Oct 23 '22 11:10

Frank C.