Hints on Programming Language Design (1973) [pdf]
i.stanford.edu
i.stanford.edu
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.
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).
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.
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 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.
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)
4
3
(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
---
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.
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.
> 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.
"if x is a reference variable may change any other variable (of appropriate type) in the whole machine"
I don't see much ambiguity.
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.
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.
* even with the downsides, pointers are absolutely worth it, and
* the type's semantics can be improved, removing many of the types's problems.
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.
I meant O(n) vs O(log n) of course. Not sure what happened there.
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).
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.
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.
The Scaladocs lead to more detailed explanation:
http://www.scala-lang.org/api/current/index.html#scala.AnyVa...
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.
1. Go - compilation should not be too slow and and runtime not to slow.
2. Ocaml - special notations for certain operations e.g. A.+B