Don't return null; use a tail call | Hacker News Reader

Don't return null; use a tail call

joelneely.wordpress.com

79 pointsranit842 comments

The important thing here is not that passing onOK and onError callbacks is a good idea. The real issue is that NULL pointers are the most dangerous thing invented in the 20th century and should be avoided like the plague.

From an [expression problem](http://c2.com/cgi/wiki?ExpressionProblem) point of view using a discriminated union (in the same spirit as returning null but safer, since you can you peek at the value after doing a null check) would probably be just fine anyway. You still get to avoid the danger of NULL pointers but you still get a real value to work with (unlike the callback case that allways immediately splits it) so you can store it, pass it around, etc.

By the way, astute readers might have recognized all that callback passing as just the [visitor pattern](https://en.wikipedia.org/wiki/Visitor_pattern) in disguise.

> The real issue is that NULL pointers are the most dangerous thing invented in the 20th century

Not sure if serious

I am somewhat serious about this. Tony Hoare even called them his "Billion Dollar mistake" in a talk he gave a while ago (http://www.infoq.com/presentations/Null-References-The-Billi...)

That talk gets quoted pretty often, but it's a bit silly for Hoare to take all the blame/credit. Null references were discovered, not invented. They are so easy (from the point of view of someone implementing a non-functional language) that they were inevitable.

Funny article. He mentions 'tail call elimination' once, and then never mentions 'tail call' again.

Also a 'tail call' and 'tail call elimination' are 2 completely different things. The former being an implementation detail (to provide proper tail recursion for languages that require it, ie Scheme), the latter an optimization technique (to remove (expensive) tail calls!).

Nonetheless, the term "tail call" should apply to what he is talking about.

If "tail call recursion" means recursing as the last thing you do before returning, then he is saying to send a message as the last thing you do.

AKA send a message as a tail call instead of returning the value of that message.

"a 'tail call' and 'tail call elimination' are 2 completely different things."

Indeed. For those seeking more detailed information about this issue, see:

http://c2.com/cgi/wiki?ProperTailRecursion

http://c2.com/cgi/wiki?TailCallOptimization

http://lambda-the-ultimate.org/classic/message1532.html

Remember to keep track of the call stack in your head as you write code. The trap to avoid is to invert control and then fail to invert (return) back to the main program flow.

In the example referenced, the following call stack could be created:

  0. authenticateUser
  1. login
  2. authSucceeded

If authSucceeded continues to call other functions as if it were the new main flow of control you could end up with a very deep call stack (it's not uncommon to see software with a call stack 40 calls deep). This is why I would have preferred "authSucceeded" to be renamed as "registerUserSession" or something else that screams "this function will do a well defined bit of work and _return quickly_" rather than "this is a loosely defined event callback that may do anything".

In the context of the OA's first sentence ("Why should an object-oriented programmer care about tail-call elimination?"), I think the author is thinking more of Scala and Ruby than Java, and there's no expectation that the tail call will return at all.

Using this approach you would often also need to maintain state about what was requested, using closures or similar to avoid race conditions. Alternatively, Haskell offers the Maybe type, where Nothing means "not found" and Just x means "found x". Using a callback seems more prone to disaster than just encoding the possibility of null into the type system.

C# offers this via Nullable<T>:

  Nullable<int> someNumber = foo.TryAndGetSomeNumber();
  if(someNumber && someNumber.HasValue)
    doSomething( someNumber.Value );

if(someNumber && someNumber.HasValue)

You still have to remember to do this check. Will the compiler complain if you use someNumber.Value without checking that its valid first? If not, then its not really the same thing.

The point of Haskell's Maybe is that the compiler will make sure that you take both cases (that there is a value and that there isn't a value) into account (because to extract the value you must pattern match and pattern matches must be exhaustive, otherwise you get a compile error).

Eh, that's putting it a little too strongly. Haskell is a nice language, but it still doesn't protect you from all your mistakes. The easiest way to extract the value in Haskell is fromJust, which simply errors if no value was returned. I do agree that Haskell makes it more natural, though.

The compiler won't, no - but many/most developers use static analysis tools like ReSharper which WILL tell you that you have a possible NullReferenceException there if you don't check it.

More idiomatic C# might be:

  int result;
  if (foo.TryAndGetSomeNumber(out result))
    doSomething(result);

There might also be a foo.GetSomeNumber() that returns an int or throws on failure.

[fixed formatting]

I disagree that your example is more idiomatic. Maybe pre-3.0...

Why don't you use int? rather than Nullable<int> - aren't they equivalent?

The point is, all values of the int are available. Null is stored somewhere outside the underlying int.

It was just a question about the syntax used - why type Nullable<int> when there is direct syntactical support in C# for nullable types - in this case you could simply type int? rather than Nullable<int>

At the very least Nullable<T> is a lot friendlier to search than T? if you want to learn more on the subject.

not everyone is familiar with C#, and Nullable<int> conveys better meaning in writing to that kind of audience.

int? is syntactic sugar for Nullable<int>, which didn't seem worth getting into :-)

Today is TCO/TCE day at HN! Haskellers learn "Dont' tail call, map/filter/fold"

re: haskell: Unfortunately or otherwise, due to influx of devs,the nomenclature has gotten mangled re Maybe/Either and all the other things that (data) can do:

- ADT used to denote abstract data types,

- Algebraic data types used to signify sum (e.g. Maybe and Either) and product (e.g. record) types, I think many people use it for only sum types now (hard to quantify my impressions of current usage, tho)

Scala has the Option/Some type, IIRC based on Haskell's Maybe, where it's used as: Option(int), and then you check the return for None or Some(int). The compiler should catch when you forget to cover the None case.

Here's a good little tutorial: http://www.codecommit.com/blog/scala/the-option-pattern

Common idiom in Erlang. Using message passing (untested code):

    do_something(N) ->
        Pid = self(),
        spawn(fun() -> find_x(Pid, N) end),
        receive
            {found, Item} -> ...;
            not_found -> ...
        end.
    
    find_x(Pid, N) -> find_x (Pid, N, [1, 3, 5]).
    find_x(Pid, _N, []) -> Pid ! not_found;
    find_x(Pid, N, [N|_T]) -> Pid ! {found, N};
    find_x(Pid, N, [_H|T]) -> find_x(Pid, N, T).

You can also handle timeouts and stuff.

Unless you specifically need a timer, I wouldn't use that and would simply return {ok, N} or {error, not_found}; that would avoid useless copying and message passing. Something like:

    find_x(N) -> find_x (N, [1, 3, 5]).
    find_x(N, []) -> {error, not_found};
    find_x(N, [N|_T]) -> {ok, N};
    find_x(N, [_H|T]) -> find_x(N, T).

If what you want is to get out of deep recursion and the above doesn't work especially well, that's what 'throw/1' is for:

    Res = try find_x(N) of
             Val -> {ok, Val}
          catch
             throw:not_found -> {error, not_found}
          end.

This will allow to avoid the stack, special cases for returning values and give you the code result you need.

The spawning of a process for a simple use case like this is only worth it if you need a timer to give a maximum execution time for a given request. Otherwise, it's not very useful, clear or efficient. I'd mark it as 'concurrency for the sake of it'.

IoC is a very useful concept for any OO language. For instance, ObjC uses it a lot through protocols. More info on that subject can be found here: http://martinfowler.com/bliki/InversionOfControl.html

The above link has some very interesting links about OO design and SmallTalk right at the end.

I don't think that this article focuses on the right problem at all. The real problem in my eyes is that the semantics of 'null' is not agreed upon. It can mean anything, including but not limited to:

  * Wrong username
  * Wrong password
  * Login procedure aborted due to external factor
  * Programming error

This causes a headache, since the client might forget to check for the magic value 'null' and the symptom might therefore accidentally be deferred to any later time.

Instead of using a callback method, why not just return an instance of some more sophisticated class, i.e something like this:

  public AuthenticationResult authenticateUser(User user) {
  ...
  }

with a possible usage:

  AuthenticationResult authResult = authenticateUser(user);
  if (authResult.failed()) {
      notifyUser(authResult.getFailureReason());
  }

If the client then tries to use a failed AuthenticationResult as a successful one, or use a successful AuthenticationResult as a failed one, the programmer is free to throw any informative exception. Example:

  class AuthenticationResult {
    ...
    public FailureReason getFailureReason() {
      if (!failed) {
        throw new IllegalStateException("you cannot fetch a failure reason from a sucessful AuthenticationResult!");
      }
    }

    public AuthToken getAuthToken() {
      if (failed) {
        throw new IllegalStateException("you cannot fetch a auth token from a failed AuthenticationResult!");
      }
    }
  }

If one instead would use 'null' as a magic value for 'auth failed', the dreaded NPE would show up instead!

I'm not bashing your idea, but throwing an authentication exception covers this almost entirely.

See, the calling code probably can't correctly proceed unless authentication was successful, and there's no chance that the caller can simply forget to handle an exception -- at the very least, it'll hit a top-level exception handler and/or crash the program.

That is another viable strategy if you don't want to handle the login failure in any graceful way.

Exceptions are not a crash-or-nothing proposition. The idea is that the caller should handle them at the earliest point in the call-stack that can do something reasonable about the problem.

Also, let me clarify that I don't believe that exceptions should be used as the only way to return values from a method in languages that support them. They are simply a tool with certain properties (among them, the ability to be more difficult to ignore, the topic at hand).

I generally find that one should avoid using exceptions for flow control. They have their usages, but they should in my opinion only be used when they really shine - when you have multiple levels of callers between the detection of the error and the handling. This was not the case in the simple example, and so I chose a return value instead of an exception.

Common idiom in javascript/jquery too, where the callback is called after the asynchronous execution. That's the advantage of this technique of course: synchronous or asynchronous implementations are interchangeable.

AKA double-barrelled continuation passing style

Which is annoying as all hell to write directly. I know it's a cliche to bitch about how 'ugh, language X doesn't have feature Y' but many callback-spaghettisms of Node would go away with call/cc.

if anyone's curious, i wrote a presentation about how call/cc can fix callback-hell per parent.

slides: lets make a blocking API not block. wait, what? (a practical introduction to continuations) [https://docs.google.com/present/view?id=dv9r8sv_82cn7dngcq]

" In his post, the caller passes itself as an argument (using a suitable interface type, of course), and the callee responds by invoking either a “found” or “not found” method on the caller."

Isn't this pretty much what you do in Twisted already?

the difference is that twisted uses trampolining - there's a top level scheduler that manages everything. if twisted worked exactly as described in this article then you'd run out of stack space (python doesn't eliminate tail calls) (also, of course, the trampoline allows other work to happen while processes yield, which is what makes twisted useful).

from another pov: this article describes how the designers of twisted want you to think (ie continuation passing style), but the actual implementation is slightly different.

http://en.wikipedia.org/wiki/Trampoline_(computing)#High_Lev...

http://en.wikipedia.org/wiki/Continuation-passing_style

OP argues that callbacks are less complex than type-checked null because it eliminates checking success at the call site. Branching on success at the call site is similar complexity as implementing onSuccess and onError. I don't think its the check itself that matters, its remembering the check, and both a success/failure interface and type-checked null meet this goal.

As to which is better, type-checked null is referentially transparent, which is a nice objective measurement of complexity, and referentially transparent functions are generally more reusable than those that aren't. It also keeps my mental model of the stack tidy, tail-call optimization or no.

QED, right? have I missed anything?

I agree that it doesn't make things easier but makes it easier to remember.

One thing that the callback style enables is that you can have more than just success and failure and/or you can provide more information about why it failed.

I don't particularly like this callback style though. I do like the multi return value style in languages like Go* where, by convention, an error is returned as the last parameter. You still have to check whether the error itself was nil, but at least you get a reason why; It is also part of the method signature, meaning you can ignore it, but you have to explicitly ignore it.

While that doesn't make it referentially transparent, it does force the programmer to acknowledge the possibility of error, even if they don't deal with it. It also keeps the flow more sequential and often times easier to read than the callback style.

*C#, Ruby and others also have some form of multiple-return values, but it's rare to see them used in this way.

the whole point of type-checked null is that the type system (compiler) forces you to acknowledge potential error states. it doesn't care if you deal with it; you can ignore the error states, or not, but its not possible to forget.

Or return an iterator (e.g. IEnumerable<T> in C#).

Reply on news.ycombinator.com