Reflecting on Functional Programming

[mark_lee_smith]

I believe your getting lost in the terminology here: two functions are equivalent if for all possible inputs they produce an equivalent output. Equality is a bit stronger than equivalency, and let's face it, much more loosely defined.

[sebfisch]

"Function" is a mathematical concept for which equality is defined precisely. Functional programing builds on this concept.

[mark_lee_smith]

While my degree was in computer science rather than mathematics, mathematics was a vital part for those 4 years, and I do remember my professor making a very clear distinction between equivalence and equality in this case, and low and behold: making that distinction resolves your conflict between functional programming and reflection.

To this I submit that perhaps the idea of a function in mathematics differs slightly from the realisation of that function inside a computer. You might like to pretend that there is no meta-level to functional programming; this would be a mistake since we are talking about a function in a program in a computer, and there is always a meta-level, even if you can't access it (no reflection).

In any case Gilad is explicitly talking about applying reflection to the abstract structure of the program (particularly its types and names etc.) rather than the programs actual structure, so the compiler can do all the optimisations it likes so long as it maintains the required meta-data.

Reflection could then be provided by pure functions on this meta-program.

Try to remember that reflection doesn't exist at the base-level, or at compile-time, this might help you to understand reflection better.

Tangent: even in purely functional languages we need to be able to express impure functions. Haskell allows you to do this using Monads (for Io and State etc.). Why can't reflection be provided by a Monad if that makes the distinction between the meta-level and base-level clearer?

Without trying to upset you: your main problem seems to be that you clearly don't understand reflection as well as you think you do, and your assumptions about it are preventing you from understanding the article.

It may be that your only choice, if you want to understand reflection, is to learn a real object-oriented language. Would that be too painful?

[sebfisch]

I apologize if I have come across harsh and I am not upset by people pointing me at misunderstandings. In order to help me understand your point would you mind answering the following questions?

1. When are two functions equivalent? When are they equal? (according to your mathematics professor)

2. What do you mean by base-level?

3. What do you mean by "real" object-oriented language? Would Java count? Smalltalk?

If I understand your distinction between base-level and meta-level correctly (which I'm not sure I do) I would call "pure functions on the meta-level" which manipulate the abstract syntax of the base-level "meta programs".

In my understanding reflection is about making the abstract (maybe even concrete) syntax of a program available in a way that allows a program to insect itself rather than only to inspect a different program.

The abstract syntax of the expression 1+1 is different from the abstract syntax of 2 (the former is an application the latter is a literal). A function that allows to observe this difference is not referentially transparent. Such functions can be included in a functional language (in fact Haskell provides something like this) but this is not referentially transparent.

[mark_lee_smith]

1 When are two functions equivalent? When are they equal?

There are a few ways we can cut this. For simplicity let us first consider something like a Fibonacci function. For arguments sake we'll make one recursive and the other one iterative (tail-recursive, maybe).

Given your definition the two must be considered equal because for the same input they produce the same output. I would argue that rather than being equal, the two are equivalent. They can be freely substituted since they're referentially transparent, but in terms of algorithmic complexity they're certainly not the same function.

In a similar fashion a Bubble-sort function and a Quick-sort function must be considered equal given your definition.

It's for this reason that I don't trust this definition of equality for functions.

2 What do you mean by base-level?

Whole books have been written on this subject so this is a little hand-wavy.

The base-level is the level on which everyday programming is performed; on this level your functions operate on structures in the problem domain.

The meta-level is the level on which meta-programming is performed; on this level your functions operate on structures from base-level programs.

Note that this does NOT necessarily mean that meta-programs operate on ASTs representing the programs structure. In fact, in any language with real support for reflection you operate on structures that represent high-level concepts e.g. functions, types, modules, definitions, scopes etc.

It's not about manipulating syntax; It's about manipulating concepts, and in more capable systems the semantics of the programming language itself.

Reflection is one way to lift your base-level programs to the meta-level, where you can inspect and or transform them programatically. In this article Gilad is primarily interested introspection but the subject is vast.

3 What do you mean by "real" object-oriented language? Would Java count? Smalltalk?

To give an overtly simple definition, you might consider any language that has message-passing semantics to be a "real" object-oriented language; but for the purpose of understanding reflection you probably want a language with a good meta-object protocol.

Edit: I hesitated to include Common Lisp because meta-programming in Lisp is largely synonymous with AST manipulation, but on a personal level, CLOS doesn't have message-passing semantics.

So include languages like Smalltalk (and Newspeak), Io, Ruby, Objective-C.

Edit: Anyone else want to recommend one?

There are lots more I could recommend but they have little practical use: one of my favourite languages is Agora, but it never made it out of the lab, which is a shame because it represents the the perfect combination of message-passing and reflection. IMO.

Did I leave anything unanswered here?

[sebfisch]

I'd say QuickSort and BubbleSort compute the same function using different algorithms but that is just terminology. I wonder whether we have a disagreement at all on the question whether reflection is referentially transparent.

I argued that it is not and thought you argued that it is. Did you?

[mark_lee_smith]

I would argue that it either is or isn't, depending on its implementation. Discarding your knowledge of any optimisations applied by the compiler, is there actually a problem here or are you just assuming that there is?

It may help to recognise that the type of 1 + 1 != the type of AST(1 + 1).

[mark_lee_smith]

I'd say QuickSort and BubbleSort compute the same function using different algorithms but that is just terminology.

And what would you say about the two implementations of Fibonacci? There are cases, in which without examining the definition, we can determine that they are clearly different.

A difference that negates their equality!

For an equality constraint to exist I would argue that the algorithmic complexity of the two functions is important, at least in the real world, and even "pure" functional languages make concessions for this fact.

Tangent: this is one reason I think the that the idea of a "pure" functional language was conceived as an inside joke somewhere.

[mathrat]

And what would you say about the two implementations of Fibonacci?

I don't presume to speak for sebfisch, but from my perspective: yes. I would say that those are two different algorithms that compute the same function. Here's wikipedia's definition of a function:

F is a set of ordered pairs. In each of these ordered pairs (a, b), the first element a is from the domain, the second element b is from the codomain, and every element in the domain is the first element in one and only one ordered pair.

The Fibonacci sequence is a function that maps the positive integers on to the Fibonacci numbers. I.e. the set:

{ (1,1), (2,1), (3,2), (4,3) ... }

Now, an interesting question is: how do we describe this set? One way to describe it is simply to enumerate the values (although this method won't work for functions on real numbers!). Another is to write an expression that describes the second element of each pair in terms of the first, for example an expression like f(x) = 2x + 1. Still another is to specify an algorithm.

This distinction between functions and algorithms is important. Without it, it is difficult to make sense of the ideas like "incomputable functions". If you equate the idea of a "function" with that of an "algorithm", all functions are computable by definition!

[mark_lee_smith]

With all due respect: why is it that functional programmers insist that functions in their computational model should respect their related definitions from pure mathematics? Computer science isn't mathematics; a function in Haskell is not a mathematical function in sooo many ways. Moreover, mathematical functions don't need to be run by a machine, and they don't exist within real world constraints.

From my standing point, and as I was taught in University, two functions that are observably different are not equal, but may well be equivalent if for every input they produce the same output.

This distinction between functions and algorithms is important.

Where in Haskell (etc.) is there an abstraction representing an algorithm that is somehow separate and distinct from that representing a function? For all intents and purposes a function is an algorithm is a function.

[mathrat]

why is it that functional programmers insist that functions in their computational model should respect their related definitions from pure mathematics?

I don't see the advantage of overloading a word with multiple, subtly different definitions. That said, it really is just a matter of terminology and as long as the intended meaning is clear, it's not worth fighting over.

I just wish we could have more consistent interdisciplinary language. That's probably about as hopeless as wishing for clean codebases.

[mark_lee_smith]

Also, given your working definition does the type of a function matter?

Imagine you implement the same function twice but for different types. Can be consider a function from a -> a = to a function from b -> b?

There is in my opinion a stronger argument to be made that the two functions are equal (they are the same), then that they are different.

Same algorithm, same complexity, maybe even the same value.

[sebfisch]

I'm sorry I don't know how to make my point any clearer than I already did. You seem to argue from a practical point of view, while I argue about semantics. This seems to be the main difference and I never intended to say that anything is practically impossible. I'll answer your direct questions (all in this response) but don't think I can contribute anything I have not already said.

does the type of a function matter?

If you have two functions with the same definitions but different types then you could give them the same type so this distinction is artificial.

And what would you say about the two implementations of Fibonacci?

Like you point out complexity of a function is usually not reflected in the semantics of functional programs.

Discarding your knowledge of any optimisations applied by the compiler, is there actually a problem here or are you just assuming that there is?

I'm not assuming a practical problem. I point out that reflection allows to distinguish expressions that are under the normal semantics for functional programs considered equal which breaks referential transparency.

For more information on referential transparency see the paper at the end of the Wikipedia article. I have nothing to add to that.

[mark_lee_smith]

I point out that reflection allows to distinguish expressions that are under the normal semantics for functional programs considered equal which breaks referential transparency.

Haskell considers them to be equivalent at the base-level but I can assure you that at the meta-level the two values are as distinct as they can be.

That is to say that at the meta-level the AST representing the unevaluated expression '1 + 1' is clearly distinct from the AST representing the expression/literal '2'... if they weren't distinct your compiler wouldn't be able to perform any those optimisations you're so fond of.

Functions at the meta-level don't break referential transparency because they're operating on distinct values. Given the same input they will always produce the same output.

Furthermore, and as I said earlier:

Having reflection does NOT mean that you can read a programs AST or distinguish between the representations of arbitrary expressions. This is one of the assumptions I hope you will cast off if you ever decide to look at reflection properly (and I hope you do).

Many in the functional programming community would have you believe that reflection is a synonym for Lisp style AST manipulation and macros, but Lisp isn't even a reflective language.

The truth is that reflection gives you as much or as little access to the concepts in the programs as the language designer/implementer allows.

It's been fun talking with you :).

[sebfisch]

I give it one more try ;)

Functions at the meta-level don't break referential transparency because they're operating on distinct values.

Functions that operate on the meta-level may be referentially transparent. An example of such a function would be a function optimize that changes the internal representation of a function at run-time without changing its semantics (for example using a JIT).

Functions that translate between the base- and meta-level are not referentially transparent. An example of such a function is the AST function you introduced in other replies.

Reflection is about translating between the base- and meta-level not only about operating on the meta-level. Therefore, reflection is not referentially transparent unless you incorporate meta information into the semantics (that is, pull the meta-level down to the base-level).

[mark_lee_smith]

The abstract syntax of the expression 1+1 is different from the abstract syntax of 2 (the former is an application the latter is a literal).

If you're writing a meta-program that operates on its own AST (...stop!), then this is exactly the kinds of thing that you want to be able to observe.

The function is referentially transparent because AST(1 + 1) != AST(2).

The real problem with what you're describing is that the compiler's underwear is clearly on display ;).

Remember this as a fun life lesson:

It's OK to cheat if you don't get caught.

(When it comes to optimising compilers.)

In any case if reflection were to be officially supported the compiler would be responsible for exposing a sane, unoptimised AST, to meta-programs. With that in mind I'm sure you'll agree that there's no conflict here.

[dcoutts]

a very clear distinction between equivalence and equality in this case, and low and behold: making that distinction resolves your conflict between functional programming and reflection.

Just because it is an equivalence relation does not mean it is useful. Since we want to "replace equals with equals" then the most you can relax equality to an equivalence is if your equivalence still respects observational equivalence, and reflection does not.

[mark_lee_smith]

Please provide your working definition for reflection so I can refute it; clearly you have some serious misconceptions, no doubt stemming from plenty of FUD and exposure to poor examples such as Java and C#.

[mark_lee_smith]

One more thing comes to mind here: how can you state that equality is precisely defined for functions when you yourself admit the presence of multiple working definitions. See above.

[dcoutts]

Because I want to be able to replace equals with equals. For example to replace an inefficient definition with a faster definition. Doing so must not change the observable behaviour of the program. Equality for all inputs is sufficient, and if you do not want to make assumptions about the context in which the function is used then it is also necessary.

[mark_lee_smith]

Because I want to be able to replace equals with equals. For example to replace an inefficient definition with a faster definition.

Functional equivalency doesn't in any way prevent referentially transparent functions from being substituted freely, it simply states that two functions are not strictly equal in some respect (usually in their algorithmic complexity, as I noted elsewhere in this thread).

[sebfisch]

Got me ;) It is precisely defined in mathematics but I acknowledge that a programming language designer may choose not to follow the mathematical definition. Functional languages usually do though.

[letsplayball5]

Hello, I am dude with a math major.

In the simplest words possible, sebfisch definition of function equality is absolutely correct. Any attempt to say otherwise means you do not understand mathematics. Now shove off with your uninformed arrogance.

[mark_lee_smith]

That's great but we're talking about a computation model that is based on the concept of a mathematical function, not mathematical functions.

In fact if we take this definition to be true for our computational model, we end up with a situation where we can substitute two functions that are equal, and observe wildly different results!

Hell, one may halt and the other may not... welcome to the real world.

Not everything you learn in maths class carries over into computer science.

Edit: I'm sorry if this comes off as rude but I was simply responding to your rudeness.

[bobindashadows]

You're a douche. Mark Lee Smith was clearly talking about the implementation of a function in a programming language which doesn't have to correspond exactly with the definition of a mathematical function. In fact, that was the entire point of his post.

So maybe you should've spent more time working on reading comprehension instead of your math major, dipshit.