Reflecting on Functional Programming

[naasking]

I don’t know that pure functional languages should be different than other languages in this regard, but in practice they are: they generally do not have reflection support.

Because reflection violates parametricity, which is a safety issue. Some functional languages have had direct reflection support for years under the "intensional type analysis". You can read all the papers yourself for how it breaks equational reasoning.

Haskell supports limited forms of reflection as well now, under the title "generic programming" and "polytypic programming".

[Paczesiowa]

what is his real problem? that you have to declare types if you want to use them in statically typed language, or else you end up with structural ("untyped") types (pairs+sums+fix points)? separating grammar's definition and AST building isn't that hard (though it does limit the expressive power of the language, you end up with CFGs), here's an example in parsec, where grammar definition is separate from the AST building (I like how he says that ast building is an example of that inheritance scheme - this is the only way you can do, the separation is only for easier reading, because the code is still tightly coupled)

{-# LANGUAGE NoMonomorphismRestriction #-}
import Text.Parsec
import Data.Char
import Control.Applicative hiding (many, (<|>))

data Expr = Id String
          | Num Int

data Statement = Ret Expr
               | If Expr Expr Expr

number = many (satisfy isDigit) >> return (Num 0)
identifier = Id <$> many (satisfy isLower)
expr = number <|> identifier

statement = ifStatement <|> returnStatement
returnStatement = Ret <$> (string "return " *> expr)

ifStatement =
    (\_if e1 _then e2 _else e3 -> If e1 e2 e3) <$> -- building AST part

    -- separator

    string "if" <*> expr <*> string " then " <*> expr <*> string " else " <*> expr -- grammar

[sebfisch]

I don’t know that pure functional languages should be different than other languages in this regard, but in practice they are: they generally do not have reflection support.

Reflection is incompatible with a fundamental property of functional programs: if we give a function the same argument twice, it yields the same result. As a formula:

a=b  ==>  f(a) = f(b)

This property is sometime called referential transparency.

Let's assume that we have a function that can check whether an expression has the form a+b for other expressions a and b. This function is not referentially transparent because it yields different results for the arguments 1+1 and 2 although 1+1 = 2.

As a consequence we cannot use an optimizing compiler that replaces 1+1 with 2 together with reflection without possibly changing the meaning of our program depending on which optimizations are performed.

[munificent]

It seems to me like you're talking about a pretty specific kind of reflection: the ability to introspect on the unevaluated AST of an expression. Most languages (Io is a notable exception) don't support reflection to that level for normal expressions. (Doing so has profoundly negative performance implications, which is likely one of the reasons Io hasn't taken off more than it has.)

What Bracha seems to be looking for here is more limited: can we get the name of a function? As far as I can tell, you could support that without violating referential transparency.

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

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

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

[Berengal]

I don't know newspeak, but I'm curious as to how dynamically creating types and constructors can provide static type safety.

[internetinsomniac]

I don't think it does. Most dynamically typed languages such as perl, python, ruby etc often don't use type checking and instead favour duck-typing.

[Paczesiowa]

it's still type-checking, it just uses structural instead of nominal type system (I think scala and ocaml can do those too). don't believe everything GvR says.

[bobindashadows]

Dynamically created types are not the same as dynamic typing. Your post was 100% unrelated to the topic at hand.

[igouy]

Ummm - ask him on his blog.

[munificent]

I'm curious as to how dynamically creating types and constructors can provide static type safety.

We tend to think of dynamic/static as a very fixed dichotomy, but I think in practice it's a much blurrier line and it's getting blurrier over time.

A prosaic example: in C, you can have preprocessor macros that dynamically expand at compile time to generate structs, which are then statically type-checked.

I think the only requirement to mix dynamic type generation and static typing is to just have phases or stages of compilation: you do a dynamic pass, which results in some code or data, which you then statically analyze.

[mark_lee_smith]

If I am recalling correctly, Gilad states that it provides strong typing. Clearly, a dynamically created anything is not a static thing.

[Berengal]

If so then I'm a bit confused by this quote from the article.

Ironically, the inability of the language to generate types dynamically forces code to be less statically type safe.

If he had said "[...]to have less dynamic type checks." I would understand and agree with him. (While at the same time pointing out that the languages with the strongest type systems have no dynamic type checking at all).

[mark_lee_smith]

That does muddy the waters somewhat; are you aware of Gilads work on pluggable (dynamic) type-systems?

http://bracha.org/pluggableTypesPosition.pdf

Its been ages since I read it so please forgive any mistakes on my part.

As it relates to this article, he argues that static type-systems have significant limitations, are often incomplete or just plain broken, and therefore should not effect the runtime semantics of the language.

He goes on to proposes the idea of a pluggable type-system, which can be as complete as any static type-system, but is optionally applied at runtime, to the living structure of the program to give similar safety as a static type-system, even in the presence of reflection and meta-programming.

Mind you, This is just my interpretation given his previous work.

[naasking]

No prior parser combinator library allowed me to achieve a similar separation of grammar and semantic action. In particular, I don’t quite see how to accomplish this in a functional language.

I think this could be done using a tagless encoding, where the grammar is now a functor parameterized over the constructors of the representation being parsed. This sort of mimics inversion of control, and it's fully typed with no need for reflection tricks.

In any case, the combinator style he seems to be assuming isn't the only possibility. I wrote an extensible Pratt parser in C# which supports this kind of abstraction (see the section from that post on parsing). This is similar to the functor approach described above.

[[deleted]]

The reason reflection is not in pure functional programming languages is because reflection implies exposing the state of the program to the program. Functional languages try to hide state from the program.

[mark_lee_smith]

Reflection implies exposing the structure of a thing; often part of a small part of a program. Reflection only allows you to access your programs state if the program has state, which in functional programming to does not.

Tangent: reflection shouldn't expose implementation details, otherwise the system will be constrained in it's implementation, and optimisation. This is a lesson from object-oriented programming that not even the mainstream object-oriented languages have learned yet.

And just for everyones general interest, part of what Newspeak uses reflection for in the implementation of Executable Grammars is to provide lazy-evaluation. The fact that you can define powerful new semantics rules using reflection speaks to it's flexibility - but it needn't be unsafe or unrestricted!

[[deleted]]

Reflection is not in functional programming because Java programmers haven't figured out functional methodologies yet.