Lambda the Ultimate

The following are all midpoints between functional and imperative. What do we lose at each point? At what point does what is lost weigh more heavily than what is gained? Are there other useful points in the value type / reference type spectrum?

Point 1:

In functional code we use immutable data structures. Instead of updating an existing value, we create a new value with the desired updates.

Functional languages often have immutable records and syntax for updating them. For example:

let p = {name="Joe", age=27}
let q = p with {age=28}

With nested records this is not so pretty:

let p = {name="Joe", age=27, address={country="France", street="Rue de la Gare", number=43}}
let q = p with {address = p.address with {number=23}}

This pattern is very common when working with functional data structures. Clojure provide certain functions like update-in and assoc-in to handle these patterns. Oftentimes we don't need the old copy of the data structure anymore in the scope it's in. So we can introduce syntactic sugar for record update:

let p.age = 28

-- is sugar for: --

let p = p with {age=28}

This makes use of variable shadowing. This makes nested record update nice:

let p.address.number = 23

Note that other copies of the record are not affected. It has the same semantics as pass-by-copy structs in C/C++.

We can even drop the let in front of variable bindings:

p.address.number = 23

We can also extend this to custom data types (maps, arrays, sets, domain specific objects, etc.) like Common Lisps places (but functional instead of imperative).

Point 2:

Now on another track. If you want to translate this to a functional language:

if <something>:
  x = <calculation of x if something>
  y = <calculation of y if something>
else:
  x = <calculation of x if not something>
  y = <calculation of y if not something>

Then you have to construct a pair:

(x,y) = if <something>
        then (<calculation of x if something>,
              <calculation of y if something>)
        else (<calculation of x if not something>,
              <calculation of y if not something>)

This style can be less clear and perhaps less efficient. We can adopt dominance based scoping: if a block dominates another block, then the variables defined in the first block are visible in the other block. So we can do:

if <something>
  let x = 2
else
  let x = 3

foo x

And the x will be visible outside the if.

Point 3:

We can extend this principle to loops. Loops in functional languages are often written in recursive style:

let xs = <some list of numbers>
let iter ys n =
  if ys==[]
  then iter (tail ys) (n + head ys)
  else n
let sum = iter xs 0

This is reminiscent of programming with gotos.

We can do structured programming by letting variables shadow each other across loop iterations:

let xs = <some list of numbers>
let sum = 0
for x in xs:
  let sum = sum + x

Point 4:

However, some loops are written with higher order functions:

let xs = 
let sum = 0
foreach xs (fun x -> let sum = sum + x)

It's unclear what the semantics are:

let ref x =
  let val = x
  ((fun () -> val), (fun y -> let val = y))

If we allow this, then we are no longer shadowing previous variables: we can implement full stateful references with it.