Writing Ops in PIR

I put together an interesting little code snippet a few days ago that, when finished, would allow writing ops in PIR. I am probably not going to complete work on this idea myself (at least, not any time soon), so I want to put the partially-written code up here for other people to look at and maybe run with.

BEGIN_OPS_PREAMBLE

opcode_t *
Parrot_pir_op_lib_wrapper_func(opcode_t *cur_opcode, PARROT_INTERP)
{
    // TODO: Set dest to the address of the next instruction, after all arguments.
    //       need to parse the number of args from the op signature
    opcode_t * dest = cur_opcode + 3;
    INTVAL opnum = (INTVAL)(*cur_opcode);
    char * const opname = interp->op_info_table[opnum]->name;
    STRING * name = string_make(interp, opname, 8, "ascii",
        PObj_constant_FLAG|PObj_external_FLAG);
    PMC * const root_ns = interp->root_namespace;
    PMC * const ns = Parrot_get_namespace_keyed(interp, root_ns, CONST_STRING(interp, "pir_op_lib"));
    PMC * sub = VTABLE_get_pmc_keyed_str(interp, ns, name);

    // TODO: Need to convert the op signature into a PCC signature here
    PMC * call_sig = Parrot_pcc_build_sig_object_from_op(interp, PMCNULL, signature,
        cur_opcode);
    Parrot_pcc_set_signature(interp, CURRENT_CONTEXT(interp), call_sig);
    interp->current_cont   = NEED_CONTINUATION;

    dest = VTABLE_invoke(interp, sub, dest);
    goto ADDRESS(dest);
}

END_OPS_PREAMBLE

op register_op_sub(IN STR, IN STR, IN PMC) {
    PMC * const root_ns = interp->root_namespace;
    PMC * const sub = $3;
    PMC * const key = Parrot_pmc_new(interp, enum_class_ResizableStringArray);
    STRING * const opname = $1;
    STRING * const sig = $2;
    PMC * const ns = Parrot_get_namespace_keyed(interp, root_ns, CONST_STRING(interp, "pir_op_lib"));
    INTVAL argcount = 3; // TODO: Count number of args in signature
    STRING * const separator = CONST_STRING(interp, "_");
    STRING * longname = Parrot_str_append(interp, opname, separator);
    longname = Parrot_str_append(interp, longname, sig);

    VTABLE_set_string_keyed_int(interp, key, 0, );

    VTABLE_set_pmc_keyed_str(interp, ns, $2, sub);
    op_info_t * new_op = (op_info_t *)malloc(sizeof(op_info_t));
    new_op->name = Parrot_str_to_cstring(interp, opname);
    new_op->full_name = Parrot_str_to_cstring(interp, longname);
    new_op->jump = 0;
    new_op->opcount = argcount + 1;

    // TODO: Initialize ->type based on what's in signature
    new_op->type = (arg_type_t *)malloc(sizeof(arg_type_t) * PARROT_MAX_ARGS);

    // TODO: Initialize based on the signature
    new_op->dirs = (arg_dir_t *)malloc(sizeof(arg_dir_t) * PARROT_MAX_ARGS);

    // TODO: what is this?
    new_op->labels = (char *)malloc(sizeof(char) * PARROT_MAX_ARGS);

    // TODO: Insert the new op into the optable.
}

This code, intended to become a dynop library one day, introduces a single new op: register_op_sub. register_op_sub takes three arguments: the string name of the new op, the string signature of the new op, and the Sub PMC for the new op. An entry is prepared for the interpreter's op_lib table (I haven't found a good way to insert that record yet), and the sub is stored in the "pir_op_lib" namespace. The body of the new op is the function Parrot_pir_op_lib_wrapper. This function body looks up the name of the current op in the op_lib table, then looks up the Sub PMC in the namespace, and will attempt to invoke that sub.

I haven't worked out all the mechanics of everything, obviously. But once a few more questions get answered and a modest amount of code gets written, this could turn into a very useful and very cool extension library for Parrot.

Opcode and OpLib PMCs

A few days ago, after some discussion with NotFound and others on #parrot, I started a small branch to experiment with some new PMC types. The results of that work were the two new experimental PMC types Opcode and OpLib. The branch merged into trunk shortly after the 2.1.0 release, so now they are available--experimentally--for people to test and use.

OpLib provides an introspective accessor layer over the interpreter's op table. The OpLib allows us to get a current count of the number of opcodes currently loaded in the system. It can also be used to return the index number of an opcode specified by name, or the name of an opcode given by it's number. On one hand it's important to hide these kinds of details from the average PIR user for reasons of backwards-compatibility and encapsulation. However, for the people writing PIR assemblers and disassemblers in PIR, the information is vital.

These PMC types are read-only types. You can use them to read information about the opcodes in the system, but you can't manipulate that information. However, I'm not against that capability entirely. Imagine the ability to remap an op number to a new custom opcode at runtime. This would allow us to write tools that can attach to live PIR code such as memory usage analyzers, profilers, watchdog monitors, etc. Of course, in most cases this capability would horribly crash the program if used incorrectly, but in the right hands it has much potential. This, if it happens at all, is a long way off.

These two PMC types are still immature but they, along with the ever-improving Packfile PMCs, are already starting to enable some cool new applications. We don't quite expose all the information yet that we need to do complete compilation or decompilation, and some improvements are needed in Parrot itself to fill in some of the remaining gaps, but we are getting closer.

Before the 3.0 release I think we will have a PIR/PASM compiler that runs on top of Parrot natively. This could be written in PIR, of course, or one of the other cool developing languages such as NQP, Winxed, or something else. With this, we could cut IMCC out of the loop almost entirely if we wanted. We could also easily come up with new assembly languages or language dialects for interacting with Parrot. My dislike for PIR is not a secret, so the ability to come up with another, better, assembly language for working with Parrot is an idea that makes me very happy.

The Problem with PIR

I've not liked PIR for a long time now, but I've never quite been able to put my finger on the reason why until now. It's a reasonably nice language to use for low-level interaction with Parrot and it's certainly more friendly than most other assembly-level languages that I've used in the past. So what's my problem with PIR?

Let's spin the question around and first ask this: What is the purpose of PIR?

When you talk about an assembly language, you tend to talk about a human-readable language that has a 1:1 relationship with the underlying machine code. On an x86/Windows computer for example I can write MASM code, compile that into machine code and then disassemble that back into MASM code that would be nearly identical to the original input. I can use a simple table lookup to convert between assembly language mnemonics and binary machine code words. This allows, among other things, live disassembly of code in a debugger and, within reason, in-place code modification. OllyDbg is a great program in this regard and was one of my favorites back when I was doing more work in this area.

PIR is not an assembly language. It's close, but if you read my paragraph above and take that as a strict definition of what an "assembly language" is, PIR is not that. PIR does not have a 1:1 relationship with the underlying bytecode, and it's not as simple as a table lookup to convert between the two forms. It's not significantly more difficult, but it is not strictly so easy either.

Another benefit to assembly language is that they tend to be easy to parse. Ridiculously easy, in fact. Almost all assembly languages use this format for their instructions:

<label>: <mneumonic> <arg>, <arg>, <arg> ...

If all your statements take this form (where the label is typically optional and there can be a different number of args, depending on the particular mneumonic), parsing is painfully simple. And fast. Here's pseudocode for a basic assembler using statements of this form:

Statement * stmt;
while(! file.end_of_file()) {
 char * line = file.readline();
 byte[INSTR_LENGTH] machinecode;
 stmt = parse(line);
 if(stmt.has_label)
   save_label_address(stmt.label);
 machinecode[0] = mneumonic_to_machine_instr(stmt.mneumonic)
 for (int i = 0; i < stmt.args.length; i++)
   machinecode[i+1] = convert_to_machine_addr(stmt.args[i]);
}
update_jump_addresses();

This code example calls several simple, single-purpose helper functions which I won't discuss in detail here but I could explain if any of the readers were interested. The point I am trying to make is that we could make a reasonably fast, stable assembler for a PASM-like assembly language if we optimized for parse-ability. The total parser could be within 300 lines of code and be completely readable and straight-forward.

This assembler, of course, wouldn't provide hooks for things like optimizations but that's the point exactly. What comes out of this assembler would have an exact 1:1 relationship with what went into it. We could make a disassembler that had almost exactly the same program structure too, and do complete back-and-forth translations of the code losing nothing but variable and label names, comments and whitespace.

And herein lies an interesting dichotomy: assembly language is the lowest-level interface to the machine, but is almost completely disregarded in favor of coding in C or C++. Most programmers don't want to program assembly. Most programmers shouldn't. I can entertain arguments about that point in the comments or even address them in a different post. Assembly language can be a huge waste of time, a huge headache, and your bug rate will tend to be higher than if you used a higher-level language. If the computer that you are using right now has software which represents over a billion lines of source code total, I would estimate that less than one ten-thousandth of one percent of that code was written directly in assembly language. Your bootloader is probably entirely written in assembly language, and small snippets in your kernel and device drivers may have been as well, but that's it. Almost nobody else uses assembly for anything because it doesn't make sense to do it. For almost the same capabilities and almost none of the same headache (or, different but less severe headache) people use C or C++ instead for low-level applications.

I've digressed, but I think some readers are going to understand my point. PIR isn't really an assembly language; it's had too many additions and syntax "improvements" to aid in readability and usability for the developer and has lost the intimate relationship with the underlying bytecode representaton because of it. At the same time, it's not really not an assembly language either: It's not as high-level, comparatively, as C is on the hardware machine and doesn't really provide the same kinds of structures or paradigms as a normal structured programming language would do. It's nice for the programmer, but not nice enough. Plus, programmers don't want to be using an assembly language anyway. Why pretty up an assembly-level language for developers in the first place if developers don't want to use assembly-level languages anyway? Why not just give them a low-level structured programming language that presents structures and idioms that they will be more familiar with? Sure, PIR offers a large series of complex and limited macros to simulate high-level control stuctures (which, by the way, are error-prone on many levels and difficult to parse), but why not give developers a real language with those structures properly integrated into the language from the beginning?

So what's the alternative?

NQP seems like a decent language to jump in and serve as the "system language" of choice for most developers on Parrot. Because of it's use in PCT, NQP does enjoy a certain amount of "market share" among developers and that kind of installed base is hard to ignore. Also, it's well-documented. I'm a little bit mistrustful of NQP because it is tied very closely to the Perl 6 language and doesn't necessarily represent the needs of Parrot developers in an agnostic way. I don't have any particular complaints, just a general mistrust of relying on software that has a different motivation than what I need. Also, NQP isn't even hosted in the Parrot repo, though the newest versions of it are copied to the repo for releases. A good systems language, in my opinion, has no motivation besides effectively bridging the gap between the raw power of the machine and the friendly abstraction needed by the programmers. I have high hopes for Austin Hasting's Close language, though that project appears to be on hold for now while he works on other foundational things. We want something simple but structured, with access to the intimate details of the Parrot VM but with a layer of abstraction to help keep programmers from getting lost in the arcana and minutia.

What I would like to see on the road to 3.0 are these things:

1. PIR should really be deprecated as the primary interface to Parrot. To program on Parrot you should either use PASM (typically as the raw text-based output of automated code generators), NQP (or another similar system language), or one of the HLLs. PIR does not satisfy a useful niche, it has been thrust upon people as the way to program on Parrot when it doesn't have any particular merits in this regard.
   
2. PIR can continue to exist, but as a separate compiler and not a part of Parrot directly. PIRC should be setup as a stand-alone compiler tool that converts PIR->PBC. The Parrot executable should have the ability to load this as an HLL compiler, but Parrot should natively act on PASM and PBC only.
   
3. PASM should be fixed to accurately represent the Parrot bytecode format in a 1:1 way. It's not far off from this, but a few fixes are needed. PASM should also not have things like macros or any kind of "syntax sugar", and should have limited assembler directives.
   
4. PCT should be updated to directly output PBC or, barring that, to output PASM instead of PIR. Of course, once we have PASM output, it's a matter of a simple table lookup to convert that into PBC. If PASM is the primary human-readable interface to Parrot, and if we have simple, fast routines for converting PASM to PBC on the fly, more programs and utilities will output PBC directly. This, in turn, improves performance for everybody.
   
5. Extend NQP or whatever systems language we want to push as the default to have access to all or almost all capabilities present in PASM. Possibly give the option to inline small PASM sequences easily.

There are lots of benefits to doing this, I think: Decreasing developer confusion, increasing performance, and gaining momentum to build languages that people actually want to use and have fitness for particular purposes, etc. I think it's a really good idea and I would like to hear feedback about it. I say we let the assembly languages (PASM) be assembly languages which are intended to be close to the machine, and that we give developers structured programming languages by default that people will actually be comfortable programming in. It seems win-win to me.

Y Combinator in Pure PIR

Tonight I took the time to do something I've wanted to do for a while: Write a Y-combinator routine in pure PIR code. I was inspired by Aristotle's excellent blog post about the topic, and the ensuing comments from his readers. I'll direct people to him for more information about the function and it's derivation.

So, without further adieu, here is the Y combinator, defined in terms of the U combinator:

# U-Combinator
.sub 'U'
    .param pmc f
    .lex '$f', f
    .const 'Sub' U_inner = '_U_inner'
    $P0 = newclosure U_inner
    .return($P0)
.end

.sub '_U_inner' :outer('U')
    .param pmc args :slurpy
    $P0 = find_lex '$f'
    $P1 = $P0($P0, args :flat)
    .return($P1)
.end

# Y-Combinator, defined in terms of the U-Combinator
.sub 'Y'
    .param pmc f
    .lex '$f', f
    .const 'Sub' Y_inner_1 = '_Y_inner_1'
    $P0 = 'U'(Y_inner_1)
    $P1 = $P0()
    .return($P1)
.end

.sub '_Y_inner_1' :outer('Y')
    .param pmc h
    .lex '$h', h
    .const 'Sub' Y_inner_2 = '_Y_inner_2'
    $P0 = newclosure Y_inner_2
    .return($P0)
.end

.sub '_Y_inner_2' :outer('_Y_inner_1')
    .param pmc args :slurpy
    .local pmc f
    .local pmc h
    f = find_lex '$f'
    h = find_lex '$h'
    $P0 = 'U'(h)
    $P1 = $P0()
    $P2 = f($P1)
    $P3 = $P2(args)
    .return($P3)
.end

And here is a little driver program that uses it to calculate the factorial of 10:

.sub 'main' :main
    .const 'Sub' wrapper = 'fact_wrapper'
    .local pmc x
    x = box 10
    $P0 = 'Y'(wrapper)
    $P1 = $P0(x)
    print "Answer: "
    say $P1
.end

.sub 'fact_wrapper'
    .param pmc f
    .lex '$f', f
    .const 'Sub' fact = 'factorial'
    $P0 = newclosure fact
    .return($P0)
.end

.sub 'factorial' :outer('fact_wrapper')
    .param pmc whatev
    .local pmc n
    n = shift whatev
    print "Calculating factorial of "
    say n
    if n >= 2 goto n_is_large
    .return(1)

  n_is_large:
    .local pmc f
    f = find_lex '$f'
    .local pmc n_minus_one
    n_minus_one = n - 1
    $P0 = f(n_minus_one)
    $P1 = $P0 * n
    .return($P1)
.end

It was quite a fun little exercise, and a great workout for the newclosure opcode, which I'm not sure is well-tested elsewhere. I may add this, or something like it, to the test suite for Parrot to run.