What everybody ought to know about RESEARCH

Why do so few scientists make significant contributions and so many are forgotten in the long run?

Richard Hamming asked himself and some of the greatest scientists of the 20th century this very question. In his classic "You and Your Research" talk, he relates what led him to the discovery of the Hamming Code and the Hamming Distance among other things. The following is my humble attempt to summarize it to make it more accessible.

1) Research is not just a matter of luck. Consider Einstein for example. Can luck explain that he discovered Special Relativity and - 10 years later - the General Theory of Relativity? One after another, you see people setting a pattern of Great Science.

2) Successful scientists are courageous. Once you get your courage up and believe that you can do important problems, then you can. If you think you can't, almost surely you are not going to. Research is not easy. If you always give up early on, you won't get anywhere. Think and continue to think any under circumstance.

3) Don't work on big problems right away. Research is hard. Expect to be paralyzed if you skip stepping stones to work a big problem. Build some background knowledge by working on smaller problems first.

4) Work hard. Given two people of approximately the same ability with one working 10% more than the other, the latter will outproduce the former more than twice over the course of a lifetime. The more you know, the more you learn; the more you learn, the more you can do; the more you can do, the more the opportunity.

5) It's important to cultivate ambiguity. Believe in you theory enough to push forward. Doubt it enough to notice the flaws and the errors. If you don't believe, you will never get started. If you don't doubt, you may lose a lot of time working on something wrong. Noticing and fixing flaws will make your theory stronger.

6) You have to want to do something significant. To quote Pasteur, "Luck favors the prepared mind". You can't win Lotto without participating. If you never try to work on anything significant, the odds are against you. Newton used to say "If others would think as hard as I did, then they would get similar results". You have to try.

If you enjoyed this, I recommend the original talk.

The secret of the LLVM C bindings

Ever wanted to use LLVM from C? Can't find any documentation? Welcome.

Since I'm considering retargeting CLISP'S JIT Compiler I've been experimenting with LLVM. LLVM is an optimizing compiler for a virtual instruction set. Technically, it is very interesting. And this year, with Apple and CLANG in the game, it seems to be here to stay.

A Factorial in C with LLVM
Let's make a factorial function using the C bindings of LLVM 2.3+.
The function we will describe in LLVM instructions is illustrated below.

I inserted the phi instruction manually to make things more interesting.
Paste this in your favorite editor and save it as "fac.c":

// Headers required by LLVM
#include <llvm-c/Core.h>
#include <llvm-c/Analysis.h>
#include <llvm-c/ExecutionEngine.h>
#include <llvm-c/Target.h>
#include <llvm-c/Transforms/Scalar.h>


// General stuff
#include <stdlib.h>
#include <stdio.h>


int main (int argc, char const *argv[])
{
  char *error = NULL; // Used to retrieve messages from functions
  LLVMModuleRef mod = LLVMModuleCreateWithName("fac_module");
  LLVMTypeRef fac_args[] = { LLVMInt32Type() };
  LLVMValueRef fac = LLVMAddFunction(mod, "fac", LLVMFunctionType(LLVMInt32Type(), fac_args, 1, 0));
  LLVMSetFunctionCallConv(fac, LLVMCCallConv);
  LLVMValueRef n = LLVMGetParam(fac, 0);

  LLVMBasicBlockRef entry = LLVMAppendBasicBlock(fac, "entry");
  LLVMBasicBlockRef iftrue = LLVMAppendBasicBlock(fac, "iftrue");
  LLVMBasicBlockRef iffalse = LLVMAppendBasicBlock(fac, "iffalse");
  LLVMBasicBlockRef end = LLVMAppendBasicBlock(fac, "end");
  LLVMBuilderRef builder = LLVMCreateBuilder();

  LLVMPositionBuilderAtEnd(builder, entry);
  LLVMValueRef If = LLVMBuildICmp(builder, LLVMIntEQ, n, LLVMConstInt(LLVMInt32Type(), 0, 0), "n == 0");
  LLVMBuildCondBr(builder, If, iftrue, iffalse);

  LLVMPositionBuilderAtEnd(builder, iftrue);
  LLVMValueRef res_iftrue = LLVMConstInt(LLVMInt32Type(), 1, 0);
  LLVMBuildBr(builder, end);

  LLVMPositionBuilderAtEnd(builder, iffalse);
  LLVMValueRef n_minus = LLVMBuildSub(builder, n, LLVMConstInt(LLVMInt32Type(), 1, 0), "n - 1");
  LLVMValueRef call_fac_args[] = {n_minus};
  LLVMValueRef call_fac = LLVMBuildCall(builder, fac, call_fac_args, 1, "fac(n - 1)");
  LLVMValueRef res_iffalse = LLVMBuildMul(builder, n, call_fac, "n * fac(n - 1)");
  LLVMBuildBr(builder, end);

  LLVMPositionBuilderAtEnd(builder, end);
  LLVMValueRef res = LLVMBuildPhi(builder, LLVMInt32Type(), "result");
  LLVMValueRef phi_vals[] = {res_iftrue, res_iffalse};
  LLVMBasicBlockRef phi_blocks[] = {iftrue, iffalse};
  LLVMAddIncoming(res, phi_vals, phi_blocks, 2);
  LLVMBuildRet(builder, res);

  LLVMVerifyModule(mod, LLVMAbortProcessAction, &error);
  LLVMDisposeMessage(error); // Handler == LLVMAbortProcessAction -> No need to check errors


  LLVMExecutionEngineRef engine;
  LLVMModuleProviderRef provider = LLVMCreateModuleProviderForExistingModule(mod);
  error = NULL;
  LLVMCreateJITCompiler(&engine, provider, &error);
  if(error) {
    fprintf(stderr, "%s\n", error);
    LLVMDisposeMessage(error);
    abort();
  }

  LLVMPassManagerRef pass = LLVMCreatePassManager();
  LLVMAddTargetData(LLVMGetExecutionEngineTargetData(engine), pass);
  LLVMAddConstantPropagationPass(pass);
  LLVMAddInstructionCombiningPass(pass);
  LLVMAddPromoteMemoryToRegisterPass(pass);
  // LLVMAddDemoteMemoryToRegisterPass(pass); // Demotes every possible value to memory
  LLVMAddGVNPass(pass);
  LLVMAddCFGSimplificationPass(pass);
  LLVMRunPassManager(pass, mod);
  LLVMDumpModule(mod);

  LLVMGenericValueRef exec_args[] = {LLVMCreateGenericValueOfInt(LLVMInt32Type(), 10, 0)};
  LLVMGenericValueRef exec_res = LLVMRunFunction(engine, fac, 1, exec_args);
  fprintf(stderr, "\n");
  fprintf(stderr, "; Running fac(10) with JIT...\n");
  fprintf(stderr, "; Result: %d\n", LLVMGenericValueToInt(exec_res, 0));

  LLVMDisposePassManager(pass);
  LLVMDisposeBuilder(builder);
  LLVMDisposeExecutionEngine(engine);
  return 0;
}

Compiling the code
Generating the object file is a no-brainer:

gcc `llvm-config --cflags` -c fac.c

Linking is a little trickier. Even though you are writing C code, you have to use a C++ linker.

g++ `llvm-config --libs --cflags --ldflags core analysis executionengine jit interpreter native` fac.o -o fac

All set!