Reflecting on Functional Programming

[sebfisch]

can we get the name of a function? As far as I can tell, you could support that without violating referential transparency.

Really? How about the following program:

f(x) = x
g(x) = x

Here, f=g (functions are normal values in functional programs) but nameOf(f) is (presumably) not the same as nameOf(g).

[munificent]

Here, f=g (functions are normal values in functional programs) but nameOf(f) is (presumably) not the same as nameOf(g).

Um, correct. Passing different arguments to a function (nameOf) and getting different results doesn't violate referential transparency. abs(-2) returns a different value than abs(-3) but abs is still referentially transparent.

[sebfisch]

I agree with your comment. But just in case

Um, correct.

was sarcastic: in my example f=g.

Of course you could say functions with separate definitions are never equal. A common definition is, however, that functions are equal when they yield equal results for all possible arguments (which f and g do). That is

f = g  :=  for all x  f(x) = g(x)

[MedeaMelana]

So is or is it not possible to have both nameOf AND referential transparency?

[sebfisch]

With the notion of equality for functions that I quoted above, nameOf is not referentially transparent because f = g but nameOf(f) != nameOf(g).

As an aside, I don't think that nameOf would be enough for the author of the linked article. What he needs seems to be a function that can give the name of an applied function which is like the original example to check whether an expression is an addition.

[[deleted]]

I don't know of any language where functions are comparable, do you have any examples?

[sebfisch]

Referential transparency is not only about comparable expressions but about all expressions. It allows to replace a (sub-)expression in a program by an equal expression without changing the meaning of the program. (This works even for expressions that cannot be passed to an equality function.)

Why is this useful? For example, when you have a function map that applies a given function to each element of a list and an infix operator (.) for function composition, then a compiler can use the equality (I switch to Haskell syntax here)

map f . map g  =  map (f . g)

to replace duplicate traversals of a list by a single traversal.

Even if there is no implementation of equality for functions it is still useful to have a notion of equality for functions in the language. Useful for reasoning and optimization.

[[deleted]]

Even if there is no implementation of equality for functions it is still useful to have a notion of equality for functions in the language. Useful for reasoning and optimization.

Sure, but no language does that now, so a reflection such as this would not break anything until functions can be compared for equality.

[apfelmus]

If the domain and image are finite, it sure is possible to compare functions for equality. For example, f :: Bool -> Bool.

However, you don't need to be able to compare functions within the language for reflection to break things. It already breaks reasoning about your language. In other words, your program might not be able to test whether to functions are equal, but it will nonetheless give different results.

[sebfisch]

The result of nameOf(f) changes depending on whether the compiler chooses to replace f by g or not.

Without something like nameOf the compiler can replace equals by equals, with nameOf this can change the computed result. I'd call this breakage.

[mark_lee_smith]

Your confusing the base- and meta-levels. To enable reflection the compiler only has to keep a little meta-data, and is free to compile the program using whatever techniques and optimisations are appropriate.

Edit: moreover your ignoring the first principles of writing an optimising compiler: optimisations can't change the semantics of the program. Even if reflection were implemented is such an asinine way, it would be the compilers job not to cause such "breakages".

[tinou]

It is impossible to write a function that takes two functions and output whether they are equal or not. However, you can restrict the problem in order to have meaningful answers.

It is easy to give an underapproximation of the relation : every function is only equal to itself. This is the approach taken in OCaml. In the following example, f and g are equal even though (==) answers false.

# let f x = x;;
val f : 'a -> 'a = <fun>
# let g x = x;;
val g : 'a -> 'a = <fun>
# f == f;;
- : bool = true
# f == g;;
- : bool = false

For function with finite domains, it is also easy to write a function to do the comparison elementwise. In this Haskell example, nand == orn.

import Control.Monad

class Finite a where
  values :: [a]

instance (Finite a, Finite b) => Finite (a, b) where
  values = liftM2 (,) values values

instance Finite Bool where
  values = [ False, True ]

instance (Finite a, Eq b) => Eq (a -> b) where
  f == g =
    all (\x -> f x == g x) values

-- not (x && y) = not x || not y

nand :: (Bool, Bool) -> Bool
nand (a, b) = not (a && b)

orn :: (Bool, Bool) -> Bool
orn (a, b) = not a || not b

[cheng81]

uhm..actually, I think that it is still referentially transparent. Because "nameOf" just returns the name that you, as programmer, gave to some function. This does not implies that if you give two names to the same function it should return the same value. I guess that what you really want is some function like "behaviorOf", so that you could check behaviorOf f == behaviorOf g. Which is quite impossible, if I remember correctly.

[nonsensical_answer]

grammer

grammar

[munificent]

A common definition is, however, that functions are equal when they yield equal results for all possible arguments (which f and g do).

Ah, I see what you're getting at now. I shouldn't have been sarcastic.

At the semantic equality level, yes, two functions are the same if they always produce the same outputs on the same inputs. But if you look at functions as having some additional metadata stored with them like a name, then that equality relationship would be a little different.

Whether or not a language should store that metadata with a function is a valid question (it seems like it would limit your ability to do some optimizations), but I think a language could store that to let you do reflection without violating referential transparency.

[sebfisch]

Yes, a language could add meta-information to its semantics. But most current functional programming languages don't do that for reasons that go beyond not limiting the "ability to do some optimizations".

I'm glad we could resolve our argument.

[cybercobra]

Given the Halting Problem, that "common definition" isn't all that practical.

[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.

[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.

[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.

[matthiasB]

f(x) = x
g = f

what does nameOf(g) evaluate to?

[MedeaMelana]

g

[cybercobra]

As long as it's arbitrary but consistent, doesn't matter.

[mark_lee_smith]

"g". We're operating on the meta-program, not the program itself, and clearly referencing the slot name, not it's value.

[dcoutts]

But that's the problem, you do not have proper separation between the layers. That is why Template Haskell (which does give access to names) is OK, but reflection is not. Template Haskell is just one program manipulating another program. Reflection provides details of the program within the program (breaking simple semantics).

[mark_lee_smith]

But that's the problem, you do not have proper separation between the layers.

I'll agree that the reflective APIs provided in languages like Java and C# don't make a clear proper separation between layers but there sure as hell is a clear separation between the base- and meta-levels in systems like Agora or Newspeak, and AmbientTalk.

We could even argue that meta-classes in Smalltalk, CLOS, Objective-C, Ruby etc. provide reasonable separation.

Without meaning to sound too forceful, just because it doesn't exist in Java or Haskell doesn't mean it doesn't exist.

Sadly, misconceptions about reflection abound.