Observations on the Feeling of the Ugly and Insignificant

vsm001 said...
I neglected to add my biggest objection to Louis's project, the lack of a strictly (or lazily) functional subset.

Louis told me he is planning on writing a book about interpreter implementation. I have offered to write prolegomena for any future meta-circularity, but Louis doesn't seem too keen on the idea.

Anyway...
vsm001 went directly to the meta-point of many of my posts: This is no way to go about designing a language.

BUT, I wanted to explore a particular issue in the design space of languages, not whether we should be in the space in the first place. In particular, let us assume some plausible rationale for inventing a language and then ask the questions that vsm001 raised.

vsm001 asked,
What are the characteristics of problems that Reason is well-suited to solve?

I'll rephrase this. What are the characteristics of problems that would be better solved by a language that has two complementary ‘modes’ of operation as opposed to a language in which a single mode suffices? In other words, neither of the two modes of Reason taken separately is quite powerful enough to be Turing complete, you really need both of them; under what situations would this provide an advantage over using a single, Turing complete mode?

Critique of Reason

A language will not succeed without a good name. I have recently invented a very good name and now I am looking for a suitable language.
                — Donald Knuth

Louis Reasoner is developing a new computer language. I'm letting him write this post.

---

“I have already done the most important part: the name of my language is Reason.

“The second most important thing is to come up with a trope. This will enable me to defend my language decisions with a pithy reply and call it a design philosophy. My trope is ‘reasonableness’. Reason will adhere to the philosophy of reasonableness. Anything in my language is, by definition, reasonable. Anything omitted is naturally unreasonable. Here is some more design philosophy:

• Small is more reasonable than big.
• Fast is more reasonable than slow.
• Useful is more reasonable than useless.
• Good is more reasonable than bad.
• etc., etc., etc....

I'll generate more later.

“After the name and the self-styled philosophy, the next important thing is the syntax. The syntax of Reason is complicated, but reasonable. Bear with me. Although it might be a bit difficult to explain, it is, after sufficient practice, natural to use.

“Reason borrows heavily from Lisp and Scheme. Most of the programming in Reason is done in ‘Lisp’ mode. Lisp mode is exactly what you think it would be: you write programs just like you would in Lisp, but with a few modifications to make things more reasonable.

• Prefix notation for everything by default, with these exceptions:
  • Infix notation for arithmetic. — Let's just capitulate on this one. Operator precedence will be fleshed out later.
  • Excess parenthesis are ignored where it is unambiguous. You can pretty much always add parenthesis to make something clearer or to override operator precedence.
  • Function calls have the operator on the outside of the parenthesis. Not only is this more natural, it avoids weird interactions with operator precedence. Arguments are separated by commas.
  • Postfix notation for post-increment and post-decrement. — I just like these.
• No ‘special’ forms. We get rid of
  • define — Lisp code tends to creep towards the right margin. Removing internal definitions makes the code ‘flatter’ and therefore easier to read. (Besides, it's hard to efficiently compile internal definitions.)
  • begin — No good reason to include it.
  • cond — Too many parenthesis.
  • let — Again, too many parenthesis.
  • lambda — This is just too advanced. Mere mortals can define a named procedure like anyone else would.
  • letrec — As if lambda wasn't confusing enough! Who comes up with this stuff?
  • quote — Too confusing. Actually, I wanted to leave quote in, but with infix and postfix in the mix I couldn't figure out where the quotation ended. I decided to punt.
• Assignment is allowed. This is technically a ‘special form’, but it is so useful that I had to leave it in.

“Lisp mode is distinguished by its use of nesting as the primary means of combination. In fact, sequential combinations are disallowed. Lisp mode constructs are created compositionally from other Lisp mode constructs or primitives. Lisp mode is where most of the primitive procedures of the language are available.

“In order to radically simplify Lisp mode I had to introduce ‘Program’ mode. Program mode is more imperative than Lisp mode, so I tried to reduce the functionality and power of Program mode so that people would favor Lisp mode. Program mode has these features:

• Special forms — Flow control, variable declaration and binding, conditionals, etc. are available in Program mode.
• No artificially rigid syntax — Program mode is not really infix, prefix, or postfix. Each construct defines its own syntax. This improves readability for the built-in special forms. For example, the if construct can have a traditional else clause rather than just having two or three subconstructs like in Lisp.
• No user-defined special forms — The user doesn't have to memorize any additional special forms beyond the built-in ones.
• No arbitrary nesting — In Program mode, you can only nest a construct if the enclosing construct permits it. There is nesting, it is just controlled.
• Concatenation for a means of combination — Lisp mode is obviously recursively evaluated. This isn't needed in Program mode because arbitrary nesting is disallowed. Instead, user constructs in Program mode are built by concatenation of Program mode primitives.
• Easy switching to Lisp mode — You can always concatenate a Lisp mode construct with a Program mode construct. Originally, I didn't want to do this, but I ended up duplicating a lot of the Lisp mode functionality. By allowing the programmer to switch to Lisp mode pretty much whenever he wants, I avoided having to duplicate a lot of code.

“When you write a procedure in Reason, you start in Program mode. As I mentioned, you can switch to Lisp mode whenever you feel like it, but there is no way to switch back (this isn't strictly true, you can mimic the ability to switch back by use of a function call. The function body starts in Program mode.) You can define a procedure in either Program mode or Lisp mode. That is, you can explicitly mark a procedure as available in Program mode only or in Lisp mode only. Of course since you can always switch to Lisp mode, it makes no discernible difference if you define a procedure as Lisp mode only; you can use it in Program mode. But if you define a procedure in Program mode only, you simply cannot use it from Lisp mode. (It will be visible, you just can't call it.)

“I could go on for hours about how variables are looked up, but I don't want to bore everyone. I would like some feedback about my ideas so far, though.

---

How about it? Would any readers care to critique the design of Reason?

I whine too much.

Mea culpa.

   ...
   for (Foo foo : permute(fooList)) {
        operateOnFoo (foo);
    }
   ...

  private static final Random rng = new Random();

  private static <E> List<E> permute (List<E> list) {
    List<E> answer = Lists.newArrayList (list);
    Collections.shuffle (answer, rng);
    return answer;
  }

More about shuffle.

In my last post, I asked why
public static void shuffle(List<?> list) was given a ‘B’ grade. A few readers didn't see the problem, so I thought I'd clarify.

I was writing code to perform some operations on the elements of a collection. Multiple copies of the code will be running. I want to avoid having each copy being synchronized with the others, so it makes sense to iterate over the list elements in a non-deterministic order. This will not prevent multiple instances of the code from occasionally ‘colliding’ on a single object, but it will make this case the exception rather than the rule.

I originally wrote the code using a Set<Foo> rather than a List<Foo> because there is no natural ordering of Foo objects. The code looked like this:

    for (Foo foo : fooSet) {
        operateOnFoo (foo);
    }

where fooSet was an instance variable declared as Set<Foo>.

A Set is an unordered abstraction. Obviously, an iterator on a Set will return the objects is some order, but abstractly, there is no meaningful way to ‘change’ the order of the Set itself. A List, on the other hand, is an ordered abstraction that imposes a external order on the elements. (An array imposes the additional unnecessary constraints of compactedness on the indexes and random access.) Changing the instance variable from Set<Foo> to a List<Foo> was trivial.

The problem is now to ‘iterate pseudorandomly’. Pseudorandom iteration is not an uncommon operation, so I assumed there was a way to do it. Pseudorandom iteration is not common enough that a special iteration construct would be defined for it, so I assumed I would simply use a normal iterator and iterate over a permutation of the list. What immediately came to mind was something like:

    for (Foo foo : fooList.permute()) {
        operateOnFoo (foo);
    }

That doesn't work.

So Java doesn't provide a ‘permute’ method on a list. I vaguely recalled that Java had something called ‘shuffle’ rather than ‘permute’. However, the List class doesn't have a ‘shuffle’ method either. None of the methods on a List will permute it. That is strange because permuting a list is a fairly common operation.

I was sure that I had seen ‘shuffle’ somewhere, so I hauled out grep to search for some code that called it. I found some and chased down the documentation. The shuffle method is a static method in the Collections class. This means that I have to use a different syntax:

    for (Foo foo : Collections.shuffle(fooList)) {
        operateOnFoo (foo);
    }

That doesn't work.

The shuffle method mutates its argument but does not return a value. This means I cannot simply call the method as an expression, but I have to hoist the call to the nearest ‘Command’ level:

    Collections.shuffle(fooList);
    for (Foo foo : fooList) {
        operateOnFoo (foo);
    }

That works, but now I have to revisit my original design: is it OK to directly shuffle the fooList, or should I copy it first? Fortunately, I don't need a copy.

To recap, what I wanted to write was this:

    for (Foo foo : fooList.permute()) {
        operateOnFoo (foo);
    }

what I had to write was this:

    Collections.shuffle(fooList);
    for (Foo foo : fooList) {
        operateOnFoo (foo);
    }

By making shuffle ‘return’ void, the author has relegated the method to command contexts only. I happened to want to use it in an expression context.

I'm sure a lot of readers are wondering “So what?” It is in fact a trivial point, and now that I've discovered how to permute a list I doubt I'll encounter this particular problem in the future. But the point is that Java distinguishes between commands and expressions. You are prohibited from using a command where an expression is called for. However, you are permitted to use an expression where a command is called for. The programmer has to keep track of which things are commands because they require a command context. The programmer doesn't have to remember which things are expressions because they can be used in either context. By making shuffle a command, the author has added yet another item to my mental “remember these aren't expressions” list. If shuffle returned the shuffled list, I wouldn't have to think about it at all.

Arcane Sentiment noted that “ Java uses the return type as a way of declaring that the operation has side effects... ”. I guess I'm weird because I use the return type to declare the type of object that will be returned.

What's wrong with this?

The java.util.Collections library has this method:
public static void shuffle(List<?> list)

Were this homework, I'd give it a solid ‘B’. Readers are encouraged to suggest improvements.

Replies to comments

steck said...
Haskell type classes give a consistent interface to different kinds of numbers (among other things). Would that do here?

It would solve the problems with the built-in number hierarchy. Does Haskell allow you to add user defined subtypes to the built-in number types?

Jevon said...
Are you saying that we shouldn't develop using design patterns? No, there's nothing wrong with the pattern per se. I'm saying that if we have programming concept that is important enough and ubiquitous enough that we can identify it and name it (for example, “The Factory Pattern” or “Singletons”), then there should be a way of abstracting it so that the pattern is replaced by something much more lightweight, or, if possible, nothing at all.

You can't argue against Factory objects using Factorial as an example. That's like arguing against using Windows when you're using Notepad as an example.
Notepad might be an effective example for certain types of arguments. Factorial obviously shouldn't be encapsulated and turned into a first-class object, it's absurd. But the language does require that it be encapsulated in some kind of object, nonetheless.

Michael said...
Java is verbose, way too verbose in areas that should be concise.
True, but I'm not necessarily complaining about the verbosity. I'm complaining that there is no reasonable way to avoid, eliminate, or abbreviate the verbosity.

Hardware Critic said...
His point is that Java has created a culture where developers over-generalize (violating the en vogue You Ain't Gonna Need It principle) and create frameworks rather than customized solutions. You turned it on its side and asked "why should developers ever have to do this junk" and made it a criticism of the Java language.
Just so.

But in doing so, you take code decorated with "don't do this" and then point to it as an example of Java's failings.
You say "but what about the 1% of people who need all that extra nonsense?", but remember Mr. Woody's point is that developers should create bespoke solutions providing only the power necessary to solve the problem at hand rather than large general frameworks.

I don't think we are contradicting each other. Let's take the “Singleton” pattern as an example. Mr. Woody and I both agree that a Singleton would be an unnecessary complication to the factorial class, but we disagree on why. If you look at the Wikipedia article on singletons, you'll see that there are three examples of how to write singletons in Java:

// Examples taken from Wikipedia
public class Singleton {
 
    private static final Singleton INSTANCE = new Singleton();
 
    // Private constructor prevents instantiation from other classes
    private Singleton() {
    }
 
    public static Singleton getInstance() {
        return INSTANCE;
    }
 
}

// Solution suggested by Bill Pugh
public class Singleton {
 
   // Private constructor prevents instantiation from other classes
   private Singleton() {
   }
 
   /**
    * SingletonHolder is loaded on the first execution of Singleton.getInstance() 
    * or the first access to SingletonHolder.INSTANCE, not before.
    */
   private static class SingletonHolder { 
     public static final Singleton INSTANCE = new Singleton();
   }
 
   public static Singleton getInstance() {
     return SingletonHolder.INSTANCE;
   }
 
 }

// Modern way suggested by Joshua Bloch
 public enum Singleton {
   INSTANCE;
 }

All three are missing my point. They say, “The correct way to use singletons is to write your code like this.” What they ought to say is “The correct way for an implementation of singletons to behave is as if your code were written like this.”

A programmer who decides to use singletons (correctly or incorrectly) ought to be able to write something like:

public singleton FactorialUtil
{
    public static int factorial(int n)
    {
        if (n == 0) return 1;
        return n * factorial(n-1);
    }
}

Yes, it is stupid to do this for something like the factorial program, but it clearly states my (poorly considered) intention, was trivial to do, trivial to undo, and best of all, theoretically allows me to change the implementation of singletons from “traditional” to “Pugh style” without having to look at all the places singletons are used.

I'd have to post a much larger program and then spend time arguing the merits of singletons if I had to give a “real world” example.

Your point that Java requires significant boilerplate in order to say what needs to be said is valid, if not particularly novel. Even so, using code which was written in an intentionally convoluted way to criticize Java's convolution is like using the winner of the Obfuscated C Code contest to demonstrate that C is difficult to read.
It is hard to make concise arguments against convolution without needlessly convoluting a concise piece of code. A situation like this in real life usually involves a truly huge pile of awful code which makes the blog post far too large and contains many additional problems that hide the point I'm trying to make.

Jason Wilson said... The Development Chaos Theory article is largely concerned with factories. Factories are used all the time in Scheme and nobody ever complains because both the use and definitions are easy and natural:

USE:
((*factorial-function-factory*) 5)

POSSIBLE DEF:
(fluid-let (*factorial-function-factory*
(lambda (n) ....))

How *factorial-function-factory* got defined should not matter to the code depending on it. It's there. I promise. (Guice gives absolutely no more guarantees that it's defined and it is the best in class dynamic variable err, dependency injection framework for Java).

The Development Chaos Theory article is of course ridiculous for treating fact as a function that needs to be so abstracted, but without dynamic variables, this really is a necessary pattern in Java in many real world cases.
Exactly. There's just one refinement I'd suggest. (let ((factorial (make-instance <factorial-function>))) (factorial 5)) Object frameworks like CLOS provide a ‘universal factory’ generic function. And I'd suggest this definition of <factorial-function>

(defclass <factorial-function> () (:metaclass singleton))

The definition of the singleton metaclass would contain code analagous to Bill Pugh's implementation.

But this doesn't answer Mr. Woody's objection that this is completely unnecessary. In that case, I suggest this alternative definition of <factorial-function>

;; Unnecessary
;; (defclass  <factorial-function> () (:metaclass singleton))

(defmethod make-instance ((class (eql (find-class '<factorial-function>))) &rest initargs)
    #'factorial)

I have overloaded make-instance in this one case to not even instantiate an object but to return the factorial procedure as a natural singleton.

HowWhy (not) to write Factorial in Java.

In “Development Chaos Theory”, William Woody laments the habits of bad Java programmers. I blame the language.

Before I start ranting, let me first say that I agree completely with Mr. Woody. If you haven't read his article, I suggest you do now.

Let's follow the example.

/** 
 * @author wwoody
 */
public static int factorial(int n)
{
    if (n == 0) return 1;
    return n * factorial(n-1);
}

This is presented as a typical way someone might write this in Java. I might have written it slightly differently:

public static int factorial(int n)
{
    return (n == 0) ? 1 : n * factorial (n - 1);
}

There is only a subtle difference between these. return, in its fully general form, is a non-local exit. It returns out of the enclosing method instead of out of the enclosing form. The difference becomes obvious if you attempt to manually inline the factorial method.

public static foo (int x)
{
    int y = (x == 0) ? 1 : x * factorial (x - 1);
    ...etc.
}

public static bar (int x)
{
    int y = if (x == 0) return 1;
            return n * factorial(n-1);
    ...etc.
}

Either way appears to be acceptable Java to me.

There should already be warning bells ringing. I have to admit that I didn't hear them the first time I looked at this code, though. I'm so inured to this crap that I missed a glaring problem.

Simplicio: Why do these methods have type declarations?
Salviati: Java doesn't do type inference.

Simplicio: Ok, that's lame, but why not just declare everything to be Object?
Salviati: Objects are too general. The * method doesn't work on them.

Simplicio: Of course! We want the most general type that supplies ==, *, and - operations. So let's use Number.
Salviati: Hold your horses, cowboy. Arithmetic doesn't work on Numbers.

Simplicio: What? Whyever not?!
Salviati: Arithmetic only works on byte, double, float, int, long, and short.

Simplicio: factorial should work on any of these. Why do I have to pick one?
Salviati: The semantics of these types aren't compatible. They behave quite differently at the very ends of their ranges. There is no way to unify them under a superclass and still preserve the subclass semantics.

Simplicio: umm... whatever. What about that static thingy?
Salviati: That doesn't matter. You aren't using any objects.

Simplicio: If it doesn't matter, why do I have to specify it?
Salviati: It would matter if you were using objects. It tells the compiler that free identifiers should have class scope. By specifying static, you're indicating that you want lexical scope.

Simplicio: But that doesn't matter because I'm not using any objects.
Salviati: Right.

Simplicio: If it doesn't matter, why do I have to specify it?

Then Mr. Woody wraps the method in a utility class:

/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static int factorial(int n)
    {
        if (n == 0) return 1;
        return n * factorial(n-1);
    }
}

and suggests an iterative implementation

/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static int factorial(int n)
    {
        int ret = 1;
        for (int i = 1; i <= n; ++i) ret *= i;
        return ret;
    }
}

Simplicio: Ummm....
Salviati: You don't want to know. In this case, we're not really using the class, but you'll want it later to avoid namespace conflicts.

Simplicio: I guess... Isn't namespace management is more of a configuration control issue than a datatype issue? Wouldn't I want these to be orthogonal issues?
Salviati: They can be handled orthogonally, but that requires some serious hacking. Right now all you want is a simple factorial problem, so just use the default.

Simplicio: What default?
Salviati: Just pick a name. Remember, though, the class name should be the same as the file name.

Simplicio: If it is the default, why do I have to do anything?

Mr. Woody now suggests that BigInteger is the right return type. We'll fix the code:

public class FactorialUtil
{
    public static BigInteger factorial(int n)
    {
        if (n == 0) return BigInteger.ONE;
        return BigInteger.valueOf(n).multiply(factorial(n-1));
    }
}

alternatively...
/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

What we're seeing here is already serious problem. Changing the range of the output is a trivial change, yet it requires large changes to the code. Here we have the original code and the modified code with the changes highlighted.

// before changes...
/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static int factorial(int n)
    {
        int ret = 1;
        for (int i = 1; i <= n; ++i) ret *= i;
        return ret;
    }
}
// after changes...
/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

Sometimes, when you are building a big system, you want to transparently install a far-reaching package. This doesn't happen often, but it happens more often than you might think. Take, for example, the scmutils library. This library augments the standard generic arithmetic in MIT Scheme so that the usual arithmetic operators can handle vectors, matrices, and functions in addition to integers, rationals and reals. No changes need to be made to the code that calls the arithmetic methods. This makes life a lot easier for developers who will not have to remember whether to use the built-in arithmetic or to switch to the extended package.


Mr. Woody now points out that one might want to memoize the answers.

/** 
 * @author wwoody
 */
public class FactorialUtil
{
    static HashMap cache = new HashMap();

    public static BigInteger factorial(int n)
    {
        BigInteger ret;

        if (n == 0) return BigInteger.ONE;
        if (null != (ret = cache.get(n))) return ret;
        ret = BigInteger.valueOf(n).multiply(factorial(n-1));
        cache.put(n, ret);
        return ret;
    }
}

To quote, “easy enough.”

Except it isn't. Memoization is a general technique that has nothing to do with the factorial program. Yet it isn't abstracted out of the problem. Tom White wrote an article on how to use Dynamic Proxy Classes to perform this abstraction. The code is a bit convoluted, but that doesn't matter because when all is said and done, we can just memoize that call to factorial.

That's the theory, anyway. It turns out that you'll need to build an interface to the factorial class and then memoize that:

/** 
 * @author wwoody
 */
public interface FactorialAlgorithm 
{
  public BigInteger factorial(final int n);
}

/** 
 * @author wwoody
 */
public class FactorialUtil implements FactorialAlgorithm
{
    public BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

FactorialAlgorithm originalFactorial = new FactorialUtil();
FactorialAlgorithm memoizedFactorial =
   (FactorialProgram) Memoizer.memoize(new FactorialUtil());

That's better, but there's still a problem. All the places in the code where you used to call FactorialUtil.factorial(n) now need to change to use the interface instead: memoizedFactorial.factorial(n). And every caller has to have access to an instance of the dynamic proxy class at runtime.

Let's continue. Mr. Woody points out that we want to select which version of factorial to use at runtime. After all, we don't even need the BigInteger version if the actual data only contains single digit numbers. To do this, he suggests a factory class that can examine configuration data and instantiate the appropriate implementation. I won't bore you with the details.

Mr. Woody then asserts:

Sure, there are circumstances where a pluggable architecture would be desirable or even necessary—but that comes up so rarely it’s not even funny. About 99% of the time I see code like this, it’s completely and utterly useless. It’s obscuring the purpose of the code—replacing a two or three line utility (max!) with dozens or even hundreds of lines of self-important masturbatory Java bullshit. Sure, it may make you feel good—but it makes an ugly mess of it that future developers will have to clean up, or more likely just avoid like the plague.

Again, I want to stress that I agree with Mr. Woody and I'm not attempting to argue against him. And here I'd like to interject and raise a point. What about the rare situations? About 1% of the time you really do want a pluggable architecture, and code like this is not completely useless. The problem is that you still need “dozens or even hundreds of lines of self-important masturbatory (but necessary) Java bullshit.” Since there is a need for a pluggable architecture, you can be sure that future developers won't be trying to clean it up. Unfortunately, that leaves “avoid like the plague” as our option.

Mr. Woody says:

The biggest complaint I have with many Java developers is that they develop a whole bunch of really bad habits. Specifications are unclear, or they think someday the code may need to be extended into a different direction. So they write a whole bunch of overblown architectural nonsense, sight unseen, thinking that the additional crap someday will help out and make things easier.

But how does this differ from the case where the additional crap really does make things easier? The code doesn't change simply because it becomes more useful. It is still a whole bunch of overblown architectural nonsense. The only difference is that you are forced to use this crap because it is the only way to get things done when the simple solution is insufficient.

My complaint with Java is that it tends to exacerbate a bad situation. Small conceptual changes to code, like changing an int to a BigInteger, end up being large textual changes. Larger conceptual changes, like adding a Factory object or a dynamically pluggable implementation, cannot be abstracted out. This leads to big piles of additional crap that have to be replicated all over the place. The language is unfriendly to change and modern software development is all about managing changes to the body of code.