none
Function Application

    Question

  • The F# language reference states that F# function application associates to the left.  However, this does not seem to be true in VS2010.  For example, take the following definitions:

    let f () = printf "1"; fun () -> printf "2"

    let g () = printf "g"

    then, rather bizarrely, the following "two" programs behave differently:

    f () (g ()) evaluates to () printing out "g12"

    (f ()) (g ()) evaluates to () printing out "1g2"

     

    Surely this is a bug?  Otherwise it seems quite counter-intuitive (to me at least) that given terms M, N and P: (M N) P is not identified with M N P.

     

     

     

    Wednesday, July 27, 2011 2:26 PM

Answers

  • I don't know what to say, other than that the current behavior is intentional and any changes to the spec would clarify that the current behavior is by design.  I think that section 6.9.5's description makes it clear how the evaluation of the application of a function to an argument list should proceed, although you're right that the spec's coverage of elaborated forms could be expanded/improved.  I understand that you may be disappointed with this conclusion and if you'd like to formally express your dissapointment, feel free to file an issue on the Connect site.  However, I would not expect this behavior to change in any future version of the language.

    • Marked as answer by SJR124 Thursday, August 04, 2011 9:06 AM
    Wednesday, August 03, 2011 6:53 PM

All replies

  • I believe that the behavior that you are seeing is expected.  It's important to distinguish precedence/associativity from order of evaluation (Eric Lippert has written extensively about this distinction in his blog and on StackOverflow in the context of C#, since it's a common point of confusion - you may find these posts helpful despite the differences between C# and F#).

    In this case, clearly function application is associating to the left since the compiler is not attempting to apply () to (g ()).  The question is in what order side effects will occur.  On this point, the section of the F# spec covering evaluating function application expressions makes this clear: all expressions are evaluated before the function is applied.  In your first case, this means that f, (), and (g ()) are evaluated, and then f is applied to () and () (the result of evaluating (g ())).  In your second case, (f ()) and (g ()) are evaluated, and then the result of the first evaluation (effectively (fun () -> printf "2")) is applied to the result of the second.  Does that make sense?

    Wednesday, July 27, 2011 5:47 PM
  • That is very interesting, and it does look from your link to the F# spec that this might indeed be intended behaviour. However, if this is the case I would agree with Steven that this is somewhat counter-intuitive. My understanding is that saying a binary operator such as application is `left associative' is a statement about syntax. To borrow one of Eric's C# arithmetic examples (concerned with associativity deriving from operator precedence):

    a + b * c is syntactically equivalent to a + (b * c)

    It is fair to point out that the evaluation strategy employed (evaluating a, then b, then c) is independent of the fact that * binds more strongly than + insofar as the evaluation order would be the same in the expression (a + b) * c. However, if hypothetically the evaluation order in a + b * c and a + (b * c) were different, it would  seem to me impossible to maintain both that the evaluation strategy is deterministic and that the syntactic equivalence holds.

    Similarly saying that binary application is `left associative' (as is the case here and indeed as I have personally assumed convention  dictates) suggests to me that fab should be parsed as (fa)b---in other words are representations of exactly the same term. It would therefore seem strange for a deterministic evaluation strategy to treat these two representations differently. If, as seems to be the case, fab and (fa)b are actually two different terms, it then seems inaccurate to describe application as left associative. Rather one would have a family of k-ary application operators for each integer k where (fa)b involves two instances of binary application and fab a single instance of ternary application.

     

     

    Wednesday, July 27, 2011 7:12 PM
  • Christopher,

    I agree that it's an interesting corner case.  Regarding associativity/precedence, as I see it, associativity implies that to evaluate the expression a() + b() + c(), the following quantities need to be calculated:

    1. x = a()
    2. y = b()
    3. z = c()
    4. tmp = x + y
    5. tmp + z

    However, from my perspective, associativity doesn't imply any particular ordering of these calculations (other than the obvious ordering implied by dependencies, such as that 1 has to occur before 4).  Instead, additional language-specific rules are needed to specify the order.  In F#, the spec indicates that operators are desugared to function applications and all arguments to functions are evaluated left-to-right.  Therefore, in F# the order is forced to be 1,2,4,3,5.  The C# spec imposes similar constraints.  However, as I see it a language could allow the evaluation order 1,2,3,4,5 (and a brief skim of the C++ spec makes me think that may be a valid order in C++, though I'm not an expert).  It's also worth noting that the only way to observe a difference between 1,2,3,4,5 and 1,2,4,3,5 in the first place is if the application of the operator can cause side effects.

    To put an even finer point on it, parentheses are used for grouping and do not necessarily have anything to do with evaluation order.  That is, even if a() + b() + c() is syntactically translated to (a() + b()) + c(), there's still no guarantee that the evaluation of a() and b() and the first addition are performed before the evaluation of c() (and again, I believe that C++ is an example of a language which does not make such a guarantee).  Thankfully, in C# and F#, the language rules do ensure that the parenthesized expression is evaluated before the right hand operand's expression, which means that in these languages thinking of associativity and precedence as adding parentheses is a useful mental model.  Philosophically, I would argue that this is a happy coincidence that simplifies reasoning, rather than the "right way" to think about associativity.

    Having said all that, I agree that the F# rule for function application may lead to confusion because it uses an evaluation order which is not equivalent to parenthesizing the first application, making it an odd exception to the general rule.  It's probably worth avoiding side-effecting sub-expressions when possible (in both arithmetic and function application contexts), which will minimize confusion regardless of the evaluation order that's used.  Hope that helps.

    Regards,

    Keith

    Thursday, July 28, 2011 4:34 AM
  • Dear Keith,

     

    Thanks for the link to the F# spec, I had previously looked for the relevant part of it without success and it is interesting to see how the evaluation strategy is worded.  

     

    I agree completely with what you have said, however, what I think Chris is pointing out, and what my question stems from, is that to say that function application associates to the left is to say that f a b and (f a) b are really one and the same program.  So if I write f a b it is really the same thing as writing (f a) b.  Hence, no matter the order in which the f, a, b, f a, and f a b are evaluated (assuming it is deterministic) it should at the very least be consistent between (f a) b and f a b.  They are one and the same program.  As you say, one might expect that when I type f a b into the interpreter it is automatically syntactically translated to (f a) b, but if that were the case they could not possibly evaluate differently.  The fact that they do evaluate differently is a contradiction to the claim that application is left associative.

     

    I think you are surely right about it only happening when the sub-terms have side effects, and I would go as far as to say that I think it is likely to only occur also when some definition is not given in eta-long form.  

     

    Best,

    Steven

     

    PS:

    The following interaction is also rather suspicious:

     

    > let f () = printf "1"; fun () -> printf "2";;

    val f : unit -> (unit -> unit)

    > let f () = fun () -> printf "2";;

    val f : unit -> unit -> unit

     

    Perhaps also the arrow is not right associative? :--)

     

    Thursday, July 28, 2011 10:33 AM

  • Hi Steven,

    This is the part of your response that I (slightly) disagree with:

    To say that function application associates to the left is to say that f a b and (f a) b are really one and the same program. So if I write f a b it is really the same thing as writing (f a) b.

    I would say that the claim that an operator is left associative only means that (a ()) op (b ()) op (c ()) evaluates to the same value as ((a ()) op (b ())) op (c ()), but does not necessarily imply that the evaluation order (and thus visible side effects) are the same between them, although many languages do happen to obey your more stringent definition.

    Regarding this:

    PS:

    The following interaction is also rather suspicious:

     

    > let f () = printf "1"; fun () -> printf "2";;

    val f : unit -> (unit -> unit)

    > let f () = fun () -> printf "2";;

    val f : unit -> unit -> unit

     

    Perhaps also the arrow is not right associative? :--)

    These types are equivalent.  However, there actually is a difference between the types (unit -> unit) and unit -> unit when they are not nested within another type (the distinction is due to the way values of these types are exposed to other .NET languages, and is not normally important).  See the Arity Conformance for Values subsection of the spec for more info.

    Regards,
    Keith

    Thursday, July 28, 2011 2:43 PM
  • Well, I think we will have to agree to disagree on what it means to be left associative, but let me point out what I understand to be the generally accepted definitions of the term:

     

    left-association of op: is a convention for how to parse a term of the form a op b op c when there are no disambiguating brackets present.  It is entirely syntactic and divorced from any notion of evaluation, hence it is specified at the level of the language grammar (for example in yacc) before any notion of semantics is attached and indeed may be applied to terms for which there is no notion of evaluation.

     

    By the way, we should be careful not to confuse it with the property of associativity of op, which is the conventional name given to a theorem of the form:

    forall a, b, c: (a op b) op c = a op (b op c)

    in some equational theory.  In contrast to left-association of op, the property of associativity is often a statement about semantics, e.g. in the first-order theory of arithmetic, the = symbol refers to the equality of the values on the left and right hand side.

     

    In any case, even in your preferred weaker definition the contradiction still exists since it is very difficult to divorce evaluation and side-effects!  Take, for example:

    let a = ref true

    let f () = a := true; fun () -> !a

    let g () = a := false

    > (f ()) (g ());;
    val it : bool = false
    > f () (g ());;
    val it : bool = true

     

    I think it would be very strange in a higher-order language to require every application to be completely bracketed in order to disambiguate how it is parsed (and consequentially evaluated) so let us hope that this is a bug in the compiler and not a bug in the documentation.

     

    By the way, the difference between the type (unit -> unit) and unit -> unit is very interesting and came as quite a surprise so thanks for the link.

     

    Thursday, July 28, 2011 4:44 PM
  • Hi Steven,

    Nice counterexample :).  I actually quite like the definition you cited, and in any case I agree that calling function application left-associative is potentially confusing given that it works differently than all of the left-associative arithmetic operators.

    However, I'm not surprised by the behavior, since it makes function application and method calls similar: all arguments are evaluated before the function or method is called.

    -Keith

    Thursday, July 28, 2011 5:35 PM
  • EDIT: Apologies for the multiple edits, but I realised a lot of what I wrote about choice of evaluation strategy is beside the point and detracts.

    EDIT: I realised I was incorrect about the evaluation order of (MN)P... I have removed this incorrect assertion, sorry about that. I can also now see where you are coming from with respect to consistency with method calls, although I still disagree with the conclusion. (I have tried to clarify my response to that a bit).

    Hi Keith,

    I wonder whether you could possibly please clarify what you mean by application being different to left-associative arithmetic operators. If addition is left associative (I am not sure whether or not addition associates to the left or to the right but let's assume it associates to the left), then:

    f + g + h

    would parse as

    (f + g) + h

    and so the compiler would treat both of these terms as being exactly the same thing. In particular, f, g, and h would evaluate in the same order in both cases (whatever order that may be). However, if I were to add brackets:

    f + (g + h)

    then this is a different term and I would then agree that it is possible that f, g and h will be evaluated in a different order. This is exactly the same as what Steven means with respect to application.

    I think in the light of the discussion thus far, it is fair to say that it is incorrect to describe function application in F# as left-associative. If this is the case, then I think it is very important to make this clear in the documentation, particularly as it would be very non-standard.  I very much agree with you that it is undesirable to write code that depends on these kinds of subtleties concerning evaluation order. Nevertheless such dependencies can creep in subtly. If I have code of the form:

     f + g * h

    then I might want to improve readability by changing it to:

    f + ( g * h)

    If I am told that * binds more strongly than + (so both expressions should parse in the same way), it seems reasonable to expect that adding such brackets won't break code that previously worked. I would be very surprised if there is any implementation of any mainstream language where such a change would alter behaviour (even for a language like C++ provided one sticks with one particular implementation). Likewise, if I am told that application is left-associative, I should be able to rewrite MNP as (MN)P without fear of changing behaviour in any way whatsoever.

    However, I personally share Steven's hope that this is a bug in the implementation rather than a bug in the documentation. For one thing, it is very standard for application to associate to the left and I would argue that having a language where this is not the case is similar to having a language where + binds more strongly than * (rather than the other way round, as is standard!). Moreover, there are principled reasons for this convention, not least the desire for the curried version of a function to be equivalent to its uncurried form and the elegance of having a single binary application `operator' rather than a family of k-ary operators. 

    If there were some technical reason peculiar to .NET that makes it appropriate to drop left-associativity, then this quirk would be understandable. I am not too sure what such a technical reason would look like, however. :-) You mention method calls. It is important to emphasise that our concern is about consistent evaluation order and not what that actual consistent ordering should be. If one really wants to use the evaluation strategy as it stands for fab, one can correct the left-association inconsistency by doing exactly the same evaluation for (fa)b --- if need be just have an internal `translation' of (fa)b to fab before evaluating!

    It is really great that Microsoft is pushing functional programming into the mainstream, and I generally speaking admire their principled approach to language design. It seems a pity if it is let down by a little quirk like this!  I think I would like F# even more if this were` corrected'. :-)

    Chris



    Friday, July 29, 2011 12:11 AM
  • I think the F# quotation system provides some instructive insight into this problem.

    Given the unpleasant snippet a couple of posts up, where the function may return either true or false depending *solely* on the bracketing, I have constructed two quotations. The first has no bracketing i.e. M N P, whereas the second has brackets i.e. (M N) P:

    #r "FSharp.PowerPack.Metadata.dll"
    #r "FSharp.PowerPack.Linq.dll"
    #r "FSharp.PowerPack.dll"
    open Microsoft.FSharp.Quotations
    open Microsoft.FSharp.Linq.QuotationEvaluation
    
    let q1 =
     <@ let a = ref false
       let g () = a := false
       let f () = a := true; fun () -> !a
       f () (g ()) @>
    
    let q2 =
     <@ let a = ref false
       let g () = a := false
       let f () = a := true; fun () -> !a
       (f ()) (g ()) @>

    Analysing the structure of the quotations gives:

    val q1 : Quotations.Expr<bool> =
     Let (a,
       Call (None,
          Microsoft.FSharp.Core.FSharpRef`1[System.Boolean] Ref[Boolean](Boolean),
          [Value (false)]),
       Let (g,
         Lambda (unitVar0,
             Call (None,
                Void op_ColonEquals[Boolean](Microsoft.FSharp.Core.FSharpRef`1[System.Boolean], Boolean),
                [a, Value (false)])),
         Let (f,
            Lambda (unitVar0,
                Sequential (Call (None,
                         Void op_ColonEquals[Boolean](Microsoft.FSharp.Core.FSharpRef`1[System.Boolean], Boolean),
                         [a, Value (true)]),
                      Lambda (unitVar0,
                          Call (None,
                             Boolean op_Dereference[Boolean](Microsoft.FSharp.Core.FSharpRef`1[System.Boolean]),
                             [a])))),
            Application (Application (f, Value (<null>)),
                  Application (g, Value (<null>))))))


    Here q2 gives exactly the same (which I hoped for, but did not expect having observed that M N P does not equal (M N) P in general in F#), and the crux of the matter lies with the Application at the end giving the binary tree we expect where the implicit bracketing makes it clear that f () is applied to g () in *both* cases.

    Just to ensure that we aren't seeing things, or that the %A of Expr<'T> isn't simplifying things, let's use the evaluation features in the PowerPack:

    > q1.Eval();;
    val it : bool = true
    > q2.Eval();;
    val it : bool = true

    As expected using the left associative behaviour of function application given in the specification and seen in the quotations. But this yields the astonishing result that e = <@ e @>.Eval() does not hold!

    This is a worrying inconsistency, that I hope can be clarified. The structure of the quotations is really what I would expect from a functional language/lambda calculus with standard binary application, and my first thought on seeing this thread was that the behaviour pointed out by Steven is a bug that would be resolved in favour of that we have just seen using the quotations.

    Tuesday, August 02, 2011 4:02 PM
  • I wanted to update this thread based on a conversation I had with Don last week:

    1. The implemented behavior of function application matches the spec and is indeed expected.
    2. The use of the term "left-associative" without qualification to describe function application is not particularly helpful, so we'll look at making it clearer in a future update to the spec.

    In typical usage the evaluation order won't matter anyway because it is only only observable when side effects are interleaved.  From a coding style perspective, if you are evaluating an expression for its side effects this should generally not be done as part of a subexpression within a larger expression, precisely because the evaluation order is not always obvious.  You can always get exactly the evaluation order you want by using explicit let bindings.  For example you can make the current behavior explicit:

    let a = x()
    let b = y()
    f a b
    

    Or you can get the more typical "left-associative" semantics:

    let a = x()
    let g = f a
    let b = y()
    g b

    Tuesday, August 02, 2011 5:59 PM
  • I think the F# quotation system provides some instructive insight into this problem.

    Given the unpleasant snippet a couple of posts up, where the function may return either true or false depending *solely* on the bracketing, I have constructed two quotations. The first has no bracketing i.e. M N P, whereas the second has brackets i.e. (M N) P:

    #r "FSharp.PowerPack.Metadata.dll"
    #r "FSharp.PowerPack.Linq.dll"
    #r "FSharp.PowerPack.dll"
    open Microsoft.FSharp.Quotations
    open Microsoft.FSharp.Linq.QuotationEvaluation
    
    let q1 =
     <@ let a = ref false
      let g () = a := false
      let f () = a := true; fun () -> !a
      f () (g ()) @>
    
    let q2 =
     <@ let a = ref false
      let g () = a := false
      let f () = a := true; fun () -> !a
      (f ()) (g ()) @>

    Analysing the structure of the quotations gives:

     

    val q1 : Quotations.Expr<bool> =
     Let (a,
      Call (None,
       Microsoft.FSharp.Core.FSharpRef`1[System.Boolean] Ref[Boolean](Boolean),
       [Value (false)]),
      Let (g,
       Lambda (unitVar0,
         Call (None,
          Void op_ColonEquals[Boolean](Microsoft.FSharp.Core.FSharpRef`1[System.Boolean], Boolean),
          [a, Value (false)])),
       Let (f,
        Lambda (unitVar0,
          Sequential (Call (None,
               Void op_ColonEquals[Boolean](Microsoft.FSharp.Core.FSharpRef`1[System.Boolean], Boolean),
               [a, Value (true)]),
             Lambda (unitVar0,
               Call (None,
                 Boolean op_Dereference[Boolean](Microsoft.FSharp.Core.FSharpRef`1[System.Boolean]),
                 [a])))),
        Application (Application (f, Value (<null>)),
           Application (g, Value (<null>))))))

     


    Here q2 gives exactly the same (which I hoped for, but did not expect having observed that M N P does not equal (M N) P in general in F#), and the crux of the matter lies with the Application at the end giving the binary tree we expect where the implicit bracketing makes it clear that f () is applied to g () in *both* cases.

    Just to ensure that we aren't seeing things, or that the %A of Expr<'T> isn't simplifying things, let's use the evaluation features in the PowerPack:

     

    > q1.Eval();;
    val it : bool = true
    > q2.Eval();;
    val it : bool = true

     

    As expected using the left associative behaviour of function application given in the specification and seen in the quotations. But this yields the astonishing result that e = <@ e @>.Eval() does not hold!

    This is a worrying inconsistency, that I hope can be clarified. The structure of the quotations is really what I would expect from a functional language/lambda calculus with standard binary application, and my first thought on seeing this thread was that the behaviour pointed out by Steven is a bug that would be resolved in favour of that we have just seen using the quotations.


    Hi Robin,

    I believe that this is a known issue with quotations which the team is looking at fixing for a future release.  If you believe that this is an important issue to fix, could you please open a bug on the Connect site so that we can track the community's interest?

     

    Thanks,
    Keith

    Tuesday, August 02, 2011 6:03 PM
  • Hi Keith,

    I wonder whether you could possibly please clarify what you mean by application being different to left-associative arithmetic operators. If addition is left associative (I am not sure whether or not addition associates to the left or to the right but let's assume it associates to the left), then:

    f + g + h

    would parse as

    (f + g) + h

    and so the compiler would treat both of these terms as being exactly the same thing. In particular, f, g, and h would evaluate in the same order in both cases (whatever order that may be).


    Hi Chrisopher,

    I wanted to briefly address the issue that you raise here.  I think that a better way to look at it is that when the compiler sees f + g + h, because (+) is left associative this is parsed into a tree something like:

        +
       / \
      +   h
     / \
    f   g

    This is not necessarily the same as how (f + g) + h is parsed.  For instance, it is possible that the fact that (f + g) is parenthesized is explicitly captured in the parse tree.  The order of evaluation is defined by the additional rules of the language, as I have described in previous posts, and these rules might take things like explicit parentheses into account.  In the case of (+) in F#, parenthesizing (f + g) does not affect the evaluation order.  However, in the case of applications the additional parentheses do affect it, as mandated by the spec.

    Regards,

    Keith

    Tuesday, August 02, 2011 6:17 PM
  • Hi Keith,

    Many thanks for your reply. I think I understand what you are saying now. I guess a language designer is free to parse his language however he sees fit (provided it is documented) including explicit treatment of brackets in the parse tree, as you describe. I personally feel, however, that this is very counter-intuitive, particularly in the case of function application given the almost universal convention in lambda calculus/FP that (MN)P and MNP are exactly the same term. Indeed I would wonder whether the `bug' that Robin highlighted with the quotation system is symptomatic of this counter-intuition! If such mistakes are made `in-house', I fear for third-party developers creating tools to manipulate F# code in manners that they naively believe to be sound due to their being conditioned to this convention.

    I thus feel that the `burden of proof' is very much on justifying the F# status quo, and I would be very interested to hear the rationale behind this design choice. Assuming that we want to adhere to the doctrine of deterministic evaluation (as F#, quite rightly, seems to do), I can't off the top of my head think of any reason why one would want to treat (MN)P and MNP as different terms unless one wanted to enable programmers to alter the evaluation order by inserting brackets! I think we would both agree that this would not be a good design decision (as you say, judiciously ordered let bindings would be a neater way of doing this). If this is not the case, then why sacrifice elegance by rejecting an equivalence that intuitively should hold? We can surely just pick the current evaluation strategy for either MNP or (MN)P (whichever is our favourite) and apply it to `both' terms!

    Regards,

    Chris

     


    Tuesday, August 02, 2011 7:22 PM
  •  

    Hi Robin,

    I believe that this is a known issue with quotations which the team is looking at fixing for a future release.  If you believe that this is an important issue to fix, could you please open a bug on the Connect site so that we can track the community's interest?

     

    Thanks,
    Keith

    Thanks for your attention to detail on this thread Keith. Like Chris, I am surprised that the bug is considered to be with the quotation system. I would be very interested in any more insight you can offer into the rationale behind this design decision. 

    Tuesday, August 02, 2011 7:37 PM
  • Hi Chris,

    I can't speak to the design rationale, and I agree that the current behavior is not completely intuitive.  Having said that, I don't find analogies to the lambda calculus particularly persuasive since the classic lambda calculus doesn't have side effects, and in the case of pure terms the evaluation order in F# is unobservable.  Indeed, while the purist in me agrees that the alternative evaluation order is arguably more elegant, I think that any benefit to changing the behavior would be very small. In order to observe the evaluation order, partially applying the function needs to have an effect, evaluating the second argument needs to have an effect, and ordering these effects differently must be observable. This is simply not a situation that frequently arises in real world code, and other than this thread I am not aware of any cases where the current behavior has caused confusion. 

    Regardless, F# has been released as a product and a significant amount of code has been written against the current implementation.  Making a breaking change to the semantics of evaluation has the potential to affect this code if it is recompiled, and the subtle nature of the change makes it especially likely that bugs that are introduced by the change in semantics might go unnoticed.  Furthermore, while it may not be intuitive, the current behavior does match the specification, so people may be intentionally relying on it.

    Therefore, to me the costs of switching clearly outweigh the benefits.  I do hope that the documentation is improved to clarify the expected behavior, though.

    Regards,

    Keith


    Tuesday, August 02, 2011 8:05 PM
  • Hi Keith,

    Many thanks for your quick reply, this is an interesting discussion.

    Having said that, I don't find analogies to the lambda calculus particularly persuasive since the classic lambda calculus doesn't have side effects, and in the case of pure terms the evaluation order in F# is unobservable.
    I only intended the analogy to be with respect to bracketing of application. In the classic lambda calculus, MNP is not strictly speaking well-formed (we only have binary application), which is why we have a convention that this really means (MN)P. There are good reasons for this convention that make it non-arbitrary (such as currying --- whilst it is admittedly true that currying does not work in an eager language in any case, intuitions derived from it still hold only if (MN)P and MNP are the same thing). In any case, I am unaware of any other functional language (even with side effects) for which this does not hold and I would think many functional programmers would be versed in this convention.
    Regardless, F# has been released as a product and a significant amount of code has been written against the current implementation.  Making a breaking change to the semantics of evaluation has the potential to affect this code if it is recompiled, and the subtle nature of the change makes it especially likely that bugs that are introduced by the change in semantics might go unnoticed.

    I can certainly see that this may be a big issue. At the same time, as you say, there are probably very few cases where real-world code would be sensitive to this matter. If, as you suggest, the benefit to changing it would be small, it seems to me very plausible that any detriment to changing it would also be small. I would very much doubt that many (if any) programmers would intentionally exploit such subtleties in the evaluation order. My concern is about maintaining consistency on those occasions when such subtleties occur inadvertently. I personally feel that having the ability to insert brackets to improve code readability without fear of there being even a small risk of altering behaviour outweighs the small risk of one off problems being caused by a change of semantics. I suspect the majority of F# programmers believe they can already do the former (which is perhaps why the issue has not been raised before) and that the majority do not realise that they could explicitly depend on the latter, even if they wanted to, particularly given the current lack of clarity in the documentation. It would also simplify the semantics for those wanting to develop third party tools to process F# code!

    Nevertheless, I do appreciate that making such a change may well be difficult in practise. It therefore seems a pity that this somewhat unconventional design decision was made in the first place!

    Regards,

    Chris

    Tuesday, August 02, 2011 8:59 PM
  •  In any case, I am unaware of any other functional language (even with side effects) for which this does not hold and I would think many functional programmers would be versed in this convention.

     

    I think this point is crucial.  People who have learned any functional programming at all will have certainly been taught that function application associates to the left (not least by members of the F# development team http://lorgonblog.wordpress.com/2008/04/03/f-function-types-fun-with-tuples-and-currying/ ).  Functional programming is built upon function application, so to deviate from this basic principle is almost certainly going to cause confusion.  It exposes programmers to a whole new way in which they can introduce bugs into their programs which simply does not exist in other functional languages. 

     

    By the way, Keith is correct that it is quite possible for compilers to represent the parentheses internally in the AST and, as I understand it, it is quite common to do so for the purposes of relaying type errors and so on back to the programmer in a way which is completely faithful to the code that was written, for example GHC does this.  However, whilst I think most people would agree that it can be useful to maintain a slightly more concrete syntax tree during some stages of compilation, it is a mistake to do so in a way which is incompatible with the programmer's understanding of the properties of the language.

     

    Microsoft has been impressively principled with its design of programming languages in recent years, so to intensionally give programmers rope to hang themselves with in their implementation of a functional language (of all programming paradigms) is perplexing to say the least.  Of course, these bugs seem likely to only appear very rarely in practice and, as with all engineering, there are pros and cons to everything but it would be absolutely fascinating to know what the advantages really are. 


    • Edited by SJR124 Tuesday, August 02, 2011 11:55 PM Added extra comments regarding syntax trees.
    Tuesday, August 02, 2011 9:56 PM
  • I have been trying to understand how the current behaviour satisfies the specification and how changing the behaviour in the manner suggested would violate the constraints imposed by the specification.

    The grammar makes it clear that the language has only binary application (conceptually at least---I believe the implementation of the parser may differ on this point).

    expr ::=

    expr expr                   -- application expression

    expr(expr)                  -- high precedence application

    ...

    I must admit I have been unable to find a clear explanation (in the spec) of how function applications are supposed to elaborate, but naively I would have thought the process would have been something along the following lines. Upon meeting a binary @-node of the pre-elaborated syntax tree, we first recursively elaborate the left-hand branch L to obtain a function f and a list of arguments [e_1...e_n]. We then recursively elaborate the right-hand branch R to obtain an elaborated form e and concatenate this to the list of arguments of f to get a final elaborated form [e_1...e_n, e]. Something along those lines would be consistent with observed behaviour when we do not pollute applications with the controversial brackets and in such cases would be consistent with `left associativity' in the parse-tree sense.

    However, this guess of mine must be incorrect because 6.5.1 tells us:

    An expression of the form (expr) is a parenthesized expression and begin expr end is a block expression.

    The expression expr is checked with the same initial type as the overall expression.

    The elaborated form of the expression [presumably (expr)]  is simply the elaborated form of expr.

    which would also give us left associativity in the sense that Steven means it ((MN)P and MNP would have the same elaborated forms). I noticed that at the end of section 6.2 in the language spec we have:

    By convention, when describing the process of elaborating compound expressions, we omit the process of recursively elaborating sub-expressions.

    As I say, I have been unable to find/ have not understood how the specification defines elaborated forms of applications. Nevertheless I assume wherever this is defined it must make an exception to the convention above. If not then would it be the case that either the current behaviour violates the specification or else the specification would be sufficiently laxed to allow a change of the relevant behaviour without violating it?

     




    Wednesday, August 03, 2011 4:34 PM
  • Hi Chris,

    I believe that section 6.9.5 describes the expected (and implemented) behavior.

     

    Regards,

    Keith

    Wednesday, August 03, 2011 4:54 PM
  • Unfortunately I don't think it does. Unless I have misread it, it only talks about function applications in elaborated form, which begs the question.

    If there is nothing more to it, then 6.9.5 is not well-defined, after all one can have a term of the form fe_1e_2..e_m which is a subterm of fe_1e_2...e_n where n > m. But in any case, my understanding was that evaluation is carried out on elaborated forms, and so one cannot ignore:

    An expression of the form (expr) is a parenthesized expression and begin expr end is a block expression.

    The expression expr is checked with the same initial type as the overall expression.

    The elaborated form of the expression [presumably (expr)]  is simply the elaborated form of expr.

    which suggests to me that (expr) and expr will have the same elaborated form and so for evaluation purposes should be equivalent.

    It may well be that the specification explicitly states somewhere that, when computing the elaborated form of an application, the recursion down the left-branch of an @-node halts as soon as a bracketed @-node is reached. If this is the case, then I would agree the implemented behaviour is as specified (although I would personally share Steven's strong opinion about this being undesirable). If this is not the case, then I would argue that on its most natural reading the current implementation violates the specification for (MN)P (which should evaluate the way MNP currently evaluates).

    Wednesday, August 03, 2011 5:08 PM
  • I don't know what to say, other than that the current behavior is intentional and any changes to the spec would clarify that the current behavior is by design.  I think that section 6.9.5's description makes it clear how the evaluation of the application of a function to an argument list should proceed, although you're right that the spec's coverage of elaborated forms could be expanded/improved.  I understand that you may be disappointed with this conclusion and if you'd like to formally express your dissapointment, feel free to file an issue on the Connect site.  However, I would not expect this behavior to change in any future version of the language.

    • Marked as answer by SJR124 Thursday, August 04, 2011 9:06 AM
    Wednesday, August 03, 2011 6:53 PM
  • Many thanks Keith for your attention to this thread, which is appreciated. We'll have to agree to disagree on the clarity of 6.9.5's description (for the reasons I outlined in my last two posts); certainly before reading this thread I personally would have misinterpreted it and even now I think one can make a strong case for interpreting it as saying something that it evidently was not intended to say! The reason this is a relatively big deal is perhaps best summarised by Steven's most recent post. If both the behaviour and the consequences of the behaviour were intentional (I am still a little sceptical about the latter), then I think it would be very helpful if someone had the opportunity  to post here to explain the rationale, as it would be good to understand the principles behind the decision.
    Wednesday, August 03, 2011 10:02 PM
  • Yes indeed, thanks for your many patient replies Keith!  It is a pity that the outcome is not better, but I think it is only particularly disappointing because F# is such a brilliant language otherwise and, having committed to using the language on a big project, the discovery of this feature has shaken my confidence in it a little.  If you do get a chance to find out any more information about the reasons behind the choice then it would be very interesting to hear them so please do pass them on. 

    Thursday, August 04, 2011 9:05 AM
  • I'd like to see someone file an issue on Connect. Although the benefit of fixing this might be minor, I still hope F# would improve itself in every little aspect toward the perfection.
    Friday, August 26, 2011 2:21 AM