14 Oct 2008

More about interfaces than you can throw a HissyFitException at

This post is in response to Mike Stone's Please Hold on the Interfaces.

I believe in judicious use of interfaces. Sometimes it's warranted, such as when it represents concepts that lend themselves to multiple unrelated implementations (e.g., Runnable or Callable).

This is doubly useful in, say, (pre-3.0) GNU C++, where you can cast references of any type to a given interface (or signature as G++ calls it) as long as all members of the interface are implemented. It's much, much more flexible than interfaces as seen in Java or C# (where you have to declare upfront in the implementing class that it's in fact implementing some interface).

Where all implementations are likely to have common functionality, having an abstract class is more sensible, in my opinion. Sometimes (such as in the Java collections framework), having both is sensible, too.


Interfaces do use vtables (in fact all interface method invocations are virtual), so whoever says using interfaces is faster because it avoids virtual calls has never profiled their code before, and worse, has no concept of how high-level source code translates to low-level object code. (Yes, I just downvoted their answer.)

I never see a reason to avoid virtual functions when polymorphism is warranted. Seasoned C++ programmers will tell you that what slows your program down with using virtual functions isn't the indirect function call, but the diminished opportunity for inlining.

However, with a managed platform like Java or .NET, the JIT can easily inline for the common case (profile-guided optimisation for the win!), and deoptimise when the common case is no longer the common case. (For lurkers and archives, what I mean is that if a virtual method is being called mostly through instances of one specific concrete class, that concrete implementation can be inlined into the JITted code until other concrete classes start being used more frequently—in which case the code is re-JITted appropriately.)

In contrast, programmers who think they know where their program's bottlenecks are, without profiling for the common cases, are performing ignorance-guided optimisation.


I don't agree with the "call protected virtual initialisation method from constructor" approach though. Remember that in the superclass constructor, the subclass portion of the object isn't constructed yet, and any such virtual methods you call had better make sure that they only access the superclass portion of the object.

In C++, this is enforced—this is a feature, not a bug. Virtual functions do not exhibit virtual behaviour when called (directly or indirectly) from constructors and destructors. I have some code to demonstrate this:


#include <iostream>

class Base {
public:
    Base() {hw();}
    virtual ~Base() {gw();}

    virtual void println(char const* line) = 0;
    void hw() {println("Hello, world!");}
    void gw() {println("Goodbye, world!");}
};

class Derived : public Base {
public:
    Derived() {}
    virtual ~Derived() {}

    virtual void println(char const* line) {
        std::cout << line << '\n';
    }
};

int
main()
{
    Derived d;
    return 0;
}

Here, even though we're instantiating a Derived object, where the println function is defined, while inside the Base constructor (and destructor) Derived::println is not being used at all.

If the constructor/destructor calls println directly, that will generate a compiler error (since a pure virtual function is being called). In this indirect case, the compilation will go fine, but because Base's vtable is used until execution reaches Derived's constructor, the println() call inside hw() will not work as (naively) expected.

Like I said, this is a feature, not a bug. While the price you pay is that you cannot use virtual behaviour inside constructors and destructors, this actually makes your program safer, by not requiring your virtual functions to be specially coded to only use members in the base class.

So, back to the use of a "protected virtual method" to allow mockable initialisation. The proper way to do this, in my view, is to make an initialize() method, that is called by client code after the object is constructed. Since initialize() isn't being called by the constructor, it means that the object is fully constructed, and that it's safe to call into the appropriate virtual method to do the appropriate type of database initialisation (or whatever).

28 May 2008

Lists and Lists: tail recursive fun

So, who's played Andrew Plotkin's Lists and Lists? It's a Scheme tutorial, and it's written in Inform, a language used to author interactive fiction.

What I find cool is that, despite (intentionally) being written for a platform not designed to host a programming language interpreter, Lists and Lists is exactly that—a very flexible interpreter, that allows you to write whatever program you like to solve its challenges. It simply verifies your programs according to the problem criteria, and you are not required to solve the problems ‘any particular way’.

Lists and Lists also has sample solutions, if you type help enough times for a given problem. These sample solutions are designed to be easy for beginners to understand, but are not necessarily optimised for any other criterion. So, variety being the spice of life and all, I've decided to post my answers to some of the questions. (I'm currently learning Scheme, so these are by no means any sort of ‘optimal’.)

My particular aim with my answers is that they should be tail recursive, so that when given a very large list to process, the programs don't use up huge amounts of stack.

In standard Scheme, the ‘named let’ syntax makes tail-recursive programs quite readable; sadly, this functionality is not available in Lists and Lists, so I also present my solution in both ‘formats’. Additionally, for extra functional-programming goodness, I present SRFI 1 versions where available.

(Sorry about the funny line wrapping; I wanted to help the two-column format display correctly on a variety of screen widths. I used Emacs to do the indentation, so hopefully the result is readable.)

  1. Define sum to be a function that adds up a list of integers. So (sum '(8 2 3)) should return 13. Make sure it works correctly for the empty list; (sum nil) should return 0.

    My approach here is: Why rewrite the + function when you can reuse it? Or, why take the high road when you can take the cheap road? :-P

    Standard SchemeLists and Lists
    (define (sum l)
      (apply + l))
    
    (define sum 
      (lambda (l)
        (eval (cons + l))))
    

    Okay, if I must actually write an iterative solution (if only so that we have something to compare the next problem against):

    SRFI 1Standard SchemeLists and Lists
    (define (sum l)
      (reduce + 0 l))
    
    (define (sum l)
      (let next ((sum 0) (tail l))
        (if (null? tail) sum
            (next (+ sum (car tail))
                  (cdr tail)))))
    
    (define sum
      (lambda (l)
        (letrec
            ((next 
              (lambda (sum tail)
                (cond
                 ((null? tail) sum)
                 (t (next (+ sum (car tail))
                          (cdr tail)))))))
          (next 0 l))))
    

    Yes, I quite deliberately reused the symbol sum, just to demonstrate that I'm not using sum to recurse. You can't, anyway, if you want a tail-recursive solution.

  2. This problem is like the last one, but more general. Define megasum to add up an arbitrarily nested list of integers. That is, (megasum '((8) 5 (2 () (9 1) 3))) should return 28.

    This solution is similar to the last one, but I'm not assuming that tail is a list, and more specifically, I only do the adding when I'm not dealing with a list. When I encounter a list, I just recurse; this catches cases where (car tail) is a list.

    SRFI 1Standard SchemeLists and Lists
    (define (megasum l)
      (let mega+ ((elem l) (sum 0))
        (cond
         ((null? elem) sum)
         ((list? elem) (fold mega+ sum elem))
         (else (+ elem sum)))))
    
    (define (megasum l)
      (let next ((sum 0) (tail l))
        (cond
         ((null? tail) sum)
         ((list? tail) 
          (next (next sum (car tail))
                (cdr tail)))
         (else (+ sum tail)))))
    
    (define megasum 
      (lambda (l)
        (letrec
            ((next 
              (lambda (sum tail)
                (cond
                 ((null? tail) sum)
                 ((list? tail) 
                  (next (next sum (car tail))
                        (cdr tail)))
                 (t (+ sum tail))))))
          (next 0 l))))
    
  3. Define max to be a function that finds the maximum of a list of integers. So (max '(5 14 -3)) should return 14. You can assume the list will have at least one term.

    My solution uses a pairmax helper function that simply returns the maximum between any two quantities.

    SRFI 1Standard SchemeLists and Lists
    (define (max l)
      (define (pairmax a b)
        (if (> a b) a b))
      (reduce pairmax #f l))
    
    (define (max l)
      (define (pairmax a b)
        (if (> a b) a b))
      (let next 
          ((best (car l)) (tail (cdr l)))
        (if (null? tail) best
            (next (pairmax best (car tail))
                  (cdr tail)))))
    
    (define max 
      (lambda (l)
        (letrec
            ((pairmax 
              (lambda (a b)
                (cond
                 ((> a b) a)
                 (t b))))
             (next 
              (lambda (best tail)
                (cond
                 ((null? tail) best)
                 (t (next (pairmax best (car tail))
                          (cdr tail)))))))
          (next (car l) (cdr l)))))
    

    You'll notice a pattern here, that there is a fairly mechanical way I'm translating from the original program to the Lists and Lists-compatible version. In fact, when tested with Guile, its macro expander actually expanded the named-let blocks on the left into something quite similar to the letrec blocks on the right.

    (Of course, in this problem, since Lists and Lists does not support internal define, the equivalent letrec is used instead.)

  4. Last problem. You're going to define a function called pocket. This function should take one argument. Now pay attention here: pocket does two different things, depending on the argument. If you give it nil as the argument, it should simply return 8. But if you give pocket any integer as an argument, it should return a new pocket function—a function just like pocket, but with that new integer hidden inside, replacing the 8.

    >>(pocket nil)
    8
    >>(pocket 12)
    [function]
    >>(define newpocket (pocket 12))
    [function]
    >>(newpocket nil)
    12
    >>(define thirdpocket (newpocket 3))
    [function]
    >>(thirdpocket nil)
    3
    >>(newpocket nil)
    12
    >>(pocket nil)
    8
    

    Note that when you create a new pocket function, previously-existing functions should keep working.

    My solution is pretty much the same as Lists and Lists' sample solution (just how many ways can you solve this one?!), just using a named let.

    Standard SchemeLists and Lists
    (define pocket
      (let construct ((num 8))
        (lambda (x)
          (if (null? x) num (construct x)))))
    
    (define pocket 
      (letrec
          ((construct 
            (lambda (num)
              (lambda (x)
                (cond
                 ((null? x) num)
                 ((construct x)))))))
        (construct 8)))
    

So, there you go. Feel free to comment with any corrections, improved answers, or whatever ideas you have. :-)

Job programming puzzles

Lately, I've been taking to job programming puzzles, to help my brain atrophy a bit less. :-P There are a couple of ones I've looked at so far: Justin.tv, and Weebly. I found both of these companies through the Hacker News job board. I look forward to doing more puzzles as I come across them. I'll probably store all my answers, and just submit them when my Green Card arrives and I can start applying for some of these jobs.

The Weebly one is easy. I solved that one in 15 minutes (and could have done it somewhat faster if not for a couple of false starts). In so saying, I didn't have to write any JavaScript code at all, I just used standard Unix tools, so perhaps that's cheating (as far as timing goes—I could have done using only client-side JavaScript code, but it would have taken me a little longer). :-P


The Justin.tv one is more challenging. I had some code from my OMGWTF 2007 submission that handled operator precedence (yes, my calculator was written to behave like a scientific calculator, and even provided buttons for parentheses so you could override the precedence), but I wanted to do it ‘the right way’, so I read up Wikipedia on parsing. I ended up using the shunting yard algorithm to do this (if you aren't familiar with this algorithm, I'd advise you to learn it from Dijkstra's paper, rather than from the Wikipedia article).

The extra-credit reduction option I implemented in a fairly conservative way, that does not reorder the values, nor change the evaluation order (even when such reordering would provide a correct final result). It does squash consecutive applications of the same operator into one function call (such that it would work as expected in Scheme), and it does so knowing that addition and multiplication are associative.

My implementation is written in Perl, by the way (and I use operator overloading on the S-expression class so that printing nested S-expressions requires very little code). It's written in a functional style, allowing easy translation to Ruby once I know the language better. And as an extension, it supports the exponentiation operator, **, which has higher precedence than * and /, and the output could even be fed to Scheme (with SRFI-1 support) if you had this function defined:

(define (** . args)
  (reduce-right expt 1 args))

Here is the test set I used (the first five are from the Justin.tv website, and the last four involve negative numbers, which are outside the spec, so change them appropriately if your implementation can't deal with negative numbers):

3
1 + 1
2 * 5 + 1
2 * ( 5 + 1 )
3 * x + ( 9 + y ) / 4
a + b + c + d
a + b + ( c + d )
a + ( b + c ) + d
a + ( b + c + d )
w - x - y - z
w - x - ( y - z )
w - ( x - y ) - z
w - ( x - y - z )
-1 + 0 - 1 * 2 * 3 - 4 - 5
-1 + 0 - 1 * 2 * 3 - 4 - 5 / 6 / 7 - 8 + 9
-1 + ( 0 - 1 * 2 * 3 - 4 - 5 / 6 - 7 / 8 ) + 9
-1 + ( 0 - 1 * 2 * 3 - 4 - 5 / 6 + 7 / 8 ) + 9

Results, without reduction:

3
(+ 1 1)
(+ (* 2 5) 1)
(* 2 (+ 5 1))
(+ (* 3 x) (/ (+ 9 y) 4))
(+ (+ (+ a b) c) d)
(+ (+ a b) (+ c d))
(+ (+ a (+ b c)) d)
(+ a (+ (+ b c) d))
(- (- (- w x) y) z)
(- (- w x) (- y z))
(- (- w (- x y)) z)
(- w (- (- x y) z))
(- (- (- (+ -1 0) (* (* 1 2) 3)) 4) 5)
(+ (- (- (- (- (+ -1 0) (* (* 1 2) 3)) 4) (/ (/ 5 6) 7)) 8) 9)
(+ (+ -1 (- (- (- (- 0 (* (* 1 2) 3)) 4) (/ 5 6)) (/ 7 8))) 9)
(+ (+ -1 (+ (- (- (- 0 (* (* 1 2) 3)) 4) (/ 5 6)) (/ 7 8))) 9)

Results, with reduction:

3
(+ 1 1)
(+ (* 2 5) 1)
(* 2 (+ 5 1))
(+ (* 3 x) (/ (+ 9 y) 4))
(+ a b c d)
(+ a b c d)
(+ a b c d)
(+ a b c d)
(- w x y z)
(- w x (- y z))
(- w (- x y) z)
(- w (- x y z))
(- (+ -1 0) (* 1 2 3) 4 5)
(+ (- (+ -1 0) (* 1 2 3) 4 (/ 5 6 7) 8) 9)
(+ -1 (- 0 (* 1 2 3) 4 (/ 5 6) (/ 7 8)) 9)
(+ -1 (- 0 (* 1 2 3) 4 (/ 5 6)) (/ 7 8) 9)

28 Oct 2007

Is there a safer way to use system()?

Many security guidelines tell people not to use system() and similar functions, because the command is passed wholesale to the shell, and if the shell string isn't escaped properly, then you have all sorts of security problems: attackers can insert redirections to files (and file descriptors) they wouldn't otherwise have access to, and insert arbitrary commands by using ;, &, &&, ||, backticks, etc.

Yet, at the same time, system() is convenient: you don't have to build up your argument array by hand, you don't have to perform token parsing, variable substitution, or tilde expansion, and you don't have to do all the forking work. So, really, you just want all the conveniences of system() without the security risks.

Well, here's something that just might do the job, in certain instances where allowing users to specify command-line arguments is useful. Rather than passing the string to the shell, it uses wordexp() to do the parsing/substitution/expansion, which rejects all the unescaped shell metacharacters and backtick usages. I need to do more testing to be sure, but I am of the opinion that it's somewhat safer to use than system().

My code is based on the implementation of system() provided in the Single Unix Specification, and I release my modifications into the public domain.


#include <sys/wait.h>
#include <errno.h>
#include <signal.h>
#include <unistd.h>
#include <wordexp.h>

int
safer_system(const char *command)
{
    int result;
    struct sigaction sa_new, sa_oldintr, sa_oldquit;
    sigset_t ss_newblock, ss_oldblock;
    pid_t pid;
    wordexp_t we = {};

    if (!command)
        return 1;

    sa_new.sa_handler = SIG_IGN;
    sigemptyset(&sa_new.sa_mask);
    sa_new.sa_flags = 0;
    sigaction(SIGINT, &sa_new, &sa_oldintr);
    sigaction(SIGQUIT, &sa_new, &sa_oldquit);

    sigemptyset(&ss_newblock);
    sigaddset(&ss_newblock, SIGCHLD);
    sigprocmask(SIG_BLOCK, &ss_newblock, &ss_oldblock);

    switch (pid = fork()) {
    case -1:
        result = -1;
        break;

    case 0:
        sigaction(SIGINT, &sa_oldintr, NULL);
        sigaction(SIGQUIT, &sa_oldquit, NULL);
        sigprocmask(SIG_SETMASK, &ss_oldblock, NULL);
        if (wordexp(command, &we, WRDE_NOCMD)) {
            errno = EINVAL;
            return -1;
        }
        execvp(*we.we_wordv, we.we_wordv);
        _exit(127);
        /* NOTREACHED */

    default:
        while (waitpid(pid, &result, 0) == -1) {
            if (errno != EINTR) {
                result = -1;
                break;
            }
        }
    }

    sigaction(SIGINT, &sa_oldintr, NULL);
    sigaction(SIGQUIT, &sa_oldquit, NULL);
    sigprocmask(SIG_SETMASK, &ss_oldblock, NULL);
    return result;
}

My original version did the wordexp() call in the parent process, but this then expands $$ to the wrong process ID. There may be other bugs in this approach that I have yet to discover; as mentioned, I haven't done very much testing with it yet.

On quality relationships, part 1

Many thanks to my friend Nathan whose Final nail article inspired this one.

I totally identify with Nathan's article, because it really upsets me when people try to do too much on a first date. I have had similar experiences (which I won't go into specifics about, both out of respect for those involved, and to protect my privacy and theirs), and I, too, chose to back off.

I chose to back off because I feel that when someone tries to be physical with me before knowing me personally and emotionally, before we establish a meaningful relationship, I worry about the possibility that emotional compatibility is less important to them than physical compatibility. This is doubly so because I'm an introvert (so I actively hide my real self), and thus it takes a lot of effort to know who I am, something that many people I know have difficulty fully understanding. I am a very different person in my own space, much harder to get along with than the social personae (yes, plural) that people usually know me by.

Now, I'm not saying that physical compatibility is not important: sex and physical affection are vital components of a good relationship, but I feel that it cannot be built primarily upon physical aspects. Honest, open communication, which I think too many couples have trouble dealing with, is much more critical (pun intended), for without it, a long-lasting relationship is almost impossible. We each are all too different to begin with; without a solid way to bridge these gaps, what hope have we got?

That's not to say that I'm perfect at communicating. Far, far from it; I still have difficulty dealing with blunt truth, and I dare say I still verbally tiptoe around my spouse too much for my liking. But I do commit to putting in the hard work needed to improve on it, and it is the top priority in my marriage.

Imagine, if you were to share your body, your intimate space, and your heart, with somebody whom, yes, you do share a strong attraction with, but whom you also know you cannot have a long-lasting and meaningful relationship with, because something much more important is in the way, like being unable to talk openly with each other. I can't speak for you, but that'd break my heart more than I want to think about.

18 Aug 2007

On open relationships

A friend asked a very interesting question on My Questions: Is there a premise for open relationships?

Most of you who know me (for some value of know) probably realise that I openly (pun intended) favour open relationships. But, your mileage may vary, and it has a lot to do with what a relationship means to you, and more importantly, what an open relationship means to you.

In the broadest sense, an open relationship is one where its parties can negotiate any terms they can all agree to. However, I would like to narrow the case to the one used in my marriage, because it forms the ‘premise’ which I will use to answer the question.

To me, an open relationship is one where you can establish additional relationships, with the free consent of your existing partner(s). By free consent, I mean that any reservations your partner(s) have about the new relationship, including jealousy and trust issues, have to be resolved before it begins. This way, relationships are only made when everyone wants it, and there is no resentment or bitterness involved.

For this to be effective, we have an agreement in place to allow an existing partner to veto a potential relationship without reprisal (emotional or otherwise). Without this, it'd allow you to pressure your partner to let you start a new relationship against their wishes, and that's not on.

Obviously, everyone involved must have a very established and very honest communication style, so that any issues that arise from the new relationship can be sensibly dealt with, and not be left sitting to develop into destructive resentment. (We have an agreement to openly express our feelings about anything that concerns us, and not to hide anything. Despite this, I am not good at being direct, nor at listening to direct comments, so I have a lot to work on before we're ready to take on new partners.)

Now, I can hear some of you ask, what about the sex? For both of us (being the INFPs that we both are), sex is all about the emotional connection, much more than about the physical satisfaction or whatever else people get out of it. I cannot imagine either of us wanting to have sex with anyone we're not in a relationship with. Your mileage may vary, and if so, then a frank discussion of what kind of sex is acceptable with whom is an absolute necessity.

So then, onto the premise. I think with the right rules and boundaries, and with the right relationship, there are a lot of emotional benefits to running an open relationship. You get to explore relationships with other people in ways that most monogamous people never get to do (without cheating)—and I do believe that some people can add (emotional or other) value to a strong relationship, even if only because we're all unique and by learning more about others, we learn more about ourselves. Also, you never have to worry about a partner being jealous, or wonder just how far you can go before things cease to be okay—these are all discussed beforehand.

But—as I just mentioned, an open relationship can only grow from a place of strength—it cannot be used as a crutch for anything. If an existing relationship has signs of trouble, trying to start an open relationship is likely to be disastrous (much like trying to start a family from a troubled relationship). You have to have the confidence that your relationship will carry the new relationship and all the dramas that come with it. Without it, you'll always worry about whether the relationship will work, and this worry will eat the relationship alive.

And though it's my third time saying it, your mileage may vary.