Hacker News Reader

Comment by Veedrac | Hacker News Reader

> [References'] introduction into high level languages has been a step backward from which we may never recover.

I'm young and never lived through such turbulent times, but this thought struck me as the most disjoint from my reality. Programming without pointer indirection seems like cycling without legs; indeed high level languages often move the other way, abandoning value types altogether.

I'm not sure this has much to teach me about language design in the modern day, but I do appreciate the insight into the early history of these things.

View on HN

> Programming without pointer indirection seems like cycling without legs

A study of functional programming will demonstrate this untrue. The paragraph you quoted from the paper elaborates to specifically why references are complicated and low level: "introducing the concept of reference ... immediately gives rise in a high level language to one of the most notorious confusions of machine code, namely that between an address and its contents ... They cannot be input as data, and they cannot be output as results. If either data or references to data have to be stored on files or backing stores, the problems are immense". Perhaps one reason why people love working in JSON so much is because it only encodes values.

> indeed high level languages often move the other way, abandoning value types altogether

FP languages strongly emphasize programming with values. Rich Hickey, creator of Clojure programming language, gave an amazing talk "Simple made Easy" which is probably the best place to start to dive into this: http://www.infoq.com/presentations/Simple-Made-Easy

FP languages are almost exclusively pointer heavy; without it they could not do structure sharing which it what allows persistent data structures with efficient operations.

FP languages also rely heavily on partial pattern matching, type classes with vtable-style indirection and even GC for cycle collection. Closures in FP languages are boxed, too, almost without exception.

In Haskell, even integers are boxed by default. You don't observe many of the problems of references due to their immutability, but this isn't to say they're not there. The "value-heavy" language closest to FP I know of is Rust, and many functional idioms are plain irritating to use because of it.

Maybe Clojure is different, but I'd be surprised. Perhaps you were in disagreement about the use of the word "value" in "value type", which I meant in the D or Rust sense of a stack-allocated, indirection-free type.

You're talking about implementation now. The text you quoted said "references' introduction into high level languages", not "references' use in the implementation of high level languages". The quote was about languages' conceptual models, not their underlying implementation forced by a particular type of CPU that code written in the language happens to be running on. A language can present value semantics while doing structural sharing using references underneath, as Clojure's persistent data types do.

"even integers are boxed by default"

Um... why? For example, 2 is.. 2. 2 is not 3. If I "box" 2, can I then make it 3?

Some very old FORTRAN implementations actually allowed this:

subroutine x(j)

write(,)j

j = 3

return

do 1 i = 1,2

1 x(4)

(sorry... it's been years). Note that the reference is immutable (j refers to a single location) -- but the value is boxed (4 is put into a memory location). And this is why this can even work.

FredW

Your code is quite hard to read, especially as I don't know Fortran. Can I have it with indentation (indent each line 2+ spaces to make a code block)?

---

Integers are boxed because Haskell's semantics almost exclusively deal with boxed types (eg. you can't pass unboxed types to most functions). The optimizer might specialize some functions for boxed types, but this is a transparent optimization and does not affect semantics.

Or, for this matter, the debate over structured vs. unstructured programming.

In fact, until the late '60s, a lot of people argued that some programs could not be implemented without using GOTO and that loops are insufficient. They weren't proven wrong until 1966 (when the structured program theorem was published).

A lot of programs cannot be implemented efficiently without goto. Instead, you're forced into using existing structured-flow constructs in very weird ways, or extra state variables and the code to handle them. State machines are one such example.

It's similar to the OOP vs procedural programming debate too; making everything into a object is "the OO way" but when overused, creates complexity instead of reducing it. I think OO and structured programming are just ways of organising code which work in many cases, but should not be followed dogmatically since they can lead to superfluous complexity.

Isn't what he's talking about C pointers, which let you mutate the memory location that's visible in the caller? Most modern languages don't let you do that, though object oriented languages let you work in much the same way by mutating the fields of an object.

As for functional programming, the use of pointers seems like an implementation issue. As far as the programmer is concerned, you're just passing around values. Now, part of what he was complaining about was implementation issues, but I don't think that was his only concern in the passage about references.

I think you're right that there's a disconnect between what he's saying and modern languages, but it's not because we've adopted the position he's attacking, instead we've gone a third way.

> As for functional programming, the use of pointers seems like an implementation issue. As far as the programmer is concerned, you're just passing around values.

This is fair if you're OK with time and space complexity being an implementation detail, but I'd wager that this is rarely true. The difference between an O(1) and O(n) destructuring, or an O(n) vs O(∞) size cyclic data structure, is not something I'd want to leave undefined.

Are there (non-contrived) algorithms where adding extra pointer indirection increases the complexity? I would say you could transform O(2n) into O(4n), and in practice this matters, but not O(2n) into O(2n^2).

It's the other way around - removing pointer indirection would ruin their complexities.

If a tree is an unshared value type (eg. there are no references), then a functional tree update is O(n). Using shared references, this is O(n²).

Cyclic data structures without pointers are of unbounded size.

De-structuring a type (X, Y) is O(sizeof(X) + sizeof(Y)) without pointers, but O(1) with.

Tons of examples.

> If a tree is an unshared value type (eg. there are no references), then a functional tree update is O(n). Using shared references, this is O(n²).

I meant O(n) vs O(log n) of course. Not sure what happened there.

Well, maybe implementation detail is not a good way to put it. But as my other comment shows, I think he's even more worried about the semantics of the construct than how the machine executes it.

Sure; but he blames the type for its semantics. New languages have shown that

* even with the downsides, pointers are absolutely worth it, and

* the type's semantics can be improved, removing many of the types's problems.

I've never seen the big O infinity notation before, nice one, thanks.

Here's the closest thing to a definition he gives:

> the concept of reference, pointer, or indirect address into the language as an assignable item of data

I think it's wrong to say that ALGOL's pointers are so different to today's pointers. After all, if he were right about their horrors, C/++ style would have moved away from pointers.

Later languages have shown that his criticisms of pointers are actually problems of the semantics one can apply to them. Java, Python and similar remove the ambiguity between `x = y` and `*x = y` by disallowing the later. Functional programming removes the danger of indirect side-effects by disallowing mutation. Rust removes the danger by disallowing shared mutation.

Rust is actually a very good example; its pointers have almost all of the power that traditional ones, and a very traditional syntax. Yet Rust is a decidedly modern and very safe language.

"Worse still, an indirect assignment through a pointer, just as in machine code, can update any store location whatsoever, and the damage is no longer confined to the variable explicitly named as the target of assignment"

"if x is a reference variable may change any other variable (of appropriate type) in the whole machine"

I don't see much ambiguity.

> "Worse still, an indirect assignment through a pointer, just as in machine code, can update any store location whatsoever"

Aside from functional languages, pretty much every language lets you assign through a pointer. This might be through a field in Java's case, but it's certainly there.

You could argue that people have unanimously agreed that mutable references are wrong, but given the popularity of imperative languages you'll probably not be able to argue that well. Plus, I still contend this is a property of the operation, not the type.

---

To put it another way, it's like calling cars bad because crashes are bad. People still use cars, because they are absolutely useful, and self-driving car proponents (aka. FP proponents) have managed to take away some of their dangers. They're still cars, even if you don't drive them.

Programming without pointers is essentially programming without run-time identities used in aliasing; i.e. programming with values. You can program with values, make it a unique ID or include one, copy that around, and you are essentially back to programming with pointers again (this happens in functional languages a lot, but they don't like to talk about it).

OO languages like to think of everything as an object, FP languages like to think of everything as a value, but in reality you often need both in most applications, and an extreme bias one way or the other isn't useful.

> indeed high level languages often move the other way, abandoning value types altogether

Such as? Every major language currently used has value types. Even Java which in which they are treated like unwanted children (and the language suffers for it).

I'm not 100% certain, but Python, Ruby and Scala are three.

Anyway, I don't mean to imply that they're 100% gone in most languages, just that the trend has been heavily in the opposite direction.

Scala has value types, and you can even define your own by extending AnyVal and following some tricky rules. It's just that Scala doesn't make you treat them differently than any other types, and they can still be magically autoboxed, just like in Java, if they get in a collection that isn't specialized to handle them.

The Scaladocs lead to more detailed explanation:

http://www.scala-lang.org/api/current/index.html#scala.AnyVa...

Auto-boxing isn't really about creating pointers, its just about having some consistency at run-time. Since the boxed item is a value (immutable), it has no state and the fact that it has been given a pointer isn't very interesting.

C# is an example of a language that goes the other way: it provides first class support for custom values in the form of structs. When you are writing performant code, you actually begin to worry about transparent auto boxing and such.

Reply on news.ycombinator.com