Hacker News Reader

Comment by lisper | Hacker News Reader

This is complete and utter hogwash.

> Clearly lisp procedures are not functions

Some are. Others are not.

The only thing a language needs to be legitimately called a functional language is for functions to be first-class data objects. It's helpful but not necessary for them to be lexically scoped. It is also helpful but not necessary to have a conditional expression. Common Lisp has all of these things. In fact, Common Lisp has all of the features commonly associated with modern functional languages except static type inference (and you can add that if you really want it).

Common Lisp is not a purely functional language, but that's true of pretty much every language except Haskell.

View on HN

I like to call Lisp "semi-functional" -- it provides better support for the functional style than ordinary imperative languages, particularly if you use FSet [0] (shameless plug), but is still perfectly good for imperative programming when you want to do that.

[0] https://github.com/slburson/fset

I think you can achieve Turing completeness without higher order functions, using only primitive recursion. That tells us that whatever can be calculated with the help of higher order functions can be somehow calculated without them, without resorting to destructive manipulation.

You don't need higher order functions, but you do need lexical closures. C only has one stack, so it's a PDA. Strictly less powerful than a TM.

This is the reason lexical closures are so important. They are what let you "allocate" an infinite amount of memory so you can be Turing-complete without side-effects.

It isn't clear that C is just A PDA. Without any destructive manipulation, C functions can use pointers to pass down and maintain a chain of contexts, so that each function potentially has random access to something at each stack level above it without having to pop anything.

Yes, that's true. But you can only do a finite number of dereferences from the current frame without being destructive.

Not so; you can recurse back up over that structure.

It's not quite that simple. It turns out that you're right, but it's much more challenging than just saying "recurse back up". The problem is that if you're recursing then you're not in the current frame. You can only do a finite number of dereferences from the current frame. That makes every frame effectively a PDA cell.

Now, that is not a proof (yet) because there's an additional wrinkle: pointer dereferencing lets you reach an arbitrary distance back up the stack in a single step, and that might be the thing that takes you from PDA-land into TM-land. But you only have a finite number of pointers in the current frame, and each of those can only be dereferenced a finite number of times in the current frame and so this is equivalent to just having a local copy of that finite amount of information in the current frame and so you're still a PDA.

Now, it turns out that argument is actually wrong. But figuring out why it's wrong is not so easy. It makes an interesting exercise writing an emulator for a two-stack machine in purely functional C. But you're right, it can be done.

Indeed, I can have a function like this:

   get_data_from_stack(parent_pointer, num_levels);

this function just recurses, decrementing num_levels until it hits zero, and chasing the parent pointers. With that, I have random access all over the stack.

Of course, C is ultimately a finite state machine because pointers have a fixed width. "sizeof pointer" is a constant expression. The absolute number of objects which can be addressed is finite. In an abstract program which doesn't use sizeof on pointers or work with their internal representation in any way, we can relax this model to allow an unlimited space; we just understand that we can have as many stack frames as we want and that somehow, the & operator in any one of them produces unique pointers.

No, that doesn't work. Because...

> Of course, C is ultimately a finite state machine because pointers have a fixed width.

Yes, but I'm willing to let that slide as long as you never do anything with a pointer but dereference one or compare two of them to see if they're equal (because you have to assume that to make any interesting computational model Turing-complete). But I'm not willing to let num_levels slide. If num_levels has a fixed width (and in C it would have to unless you show me how to build a purely functional bignum library) this solution won't work.

It really is not trivial to figure out how to make this work.

> C only has one stack

Sure

> so it's a PDA.

Wrong

Why wrong? Remember, we're talking about functional C here, so no destructive operations are allowed.

Something like Baker's Cheney on the MTA without actually collecting garbage. The "cheat" is that unbounded stack size implies unbounded pointer sizes, which means no finite alphabet, but "C without pointers" isn't C, and "finite stack/tape" isn't PDA/TM, so I think the "cheat" is fair :-)

OK, you're right. I concede the point.

So... Is C a functional language? It allows us to pass functions to functions, return them back, storing them in variables and structures, and so on. Looks like C is a functional language.

Not quite. To be a first-class data object you not only need to be able to pass and return them, but you also need to be able to create new ones at run time (i.e. you need to be able to make closures). C can't quite do that. (You can roll your own closures, but it's awkward.) But yes, C is closer to being functional than most people realize.

Reply on news.ycombinator.com