pragma solidity ^0.4.18;

contract Gastoken {
    function free(uint256 value) public returns (bool success);
    function freeUpTo(uint256 value) public returns (uint256 freed);
    function freeFrom(address from, uint256 value) public returns (bool success);
    function freeFromUpTo(address from, uint256 value) public returns (uint256 freed);
}

contract Example {

    // This function consumes a lot of gas
    function expensiveStuff() private pure {
        /* lots of expensive stuff */
    }

    /*
     * Frees `free' tokens from the Gastoken at address `gas_token'.
     * The freed tokens belong to this Example contract. The gas refund can pay
     * for up to half of the gas cost of the total transaction in which this 
     * call occurs.
     */
    function burnGasAndFree(address gas_token, uint256 free) public {
        require(Gastoken(gas_token).free(free));
        expensiveStuff();
    }

    /*
     * Frees `free' tokens from the Gastoken at address `gas_token'.
     * The freed tokens belong to the sender. The sender must have previously 
     * allowed this Example contract to free up to `free' tokens on its behalf
     * (i.e., `allowance(msg.sender, this)' should be at least `free').
     * The gas refund can pay for up to half of the gas cost of the total 
     * transaction in which this call occurs.
     */
    function burnGasAndFreeFrom(address gas_token, uint256 free) public {
        require(Gastoken(gas_token).freeFrom(msg.sender, free));
        expensiveStuff();
    }
}

Compile and Run ▶