A Gray Beard Explores F#(graybeardprogrammer.com)
graybeardprogrammer.com
A Gray Beard Explores F#
http://graybeardprogrammer.com/?p=1
28 comments
Well, the second version here is better for the following reasons:
- 9 less lines of code.
- Easier to see that it's correct. Partly because it's less lines, but partly because those lines are more meaningful and less bland. It would be hard to see a typo in the repetitive inner loop of the first version.
- Two obvious independent pieces of code instead of one big piece of code. That means if you're reading it, you know how to go about understanding it; understand each piece in turn. Somewhat trivial when there are 25 lines, but serious if there are 200 lines.
- Easier to test and debug. At a REPL, it's trivial to see what the stack is going to look like five hops into the functional version; you just apply the processing function five times. To do the same to the imperative version, you need to either write some debug logic into the middle of the function or set a breakpoint and hit 'continue' in your debugger while you count on your fingers.
Those reasons are typical consequences of writing your code as a collection of data and pure functions.
Also, the semantics are not completely inherently serial for most possible stacks. The sequence of operations forms a tree of computation, and the branches of the tree could be computed in parallel. If you actually wanted to do that (say, if the operations took a long time individually) then the way you would go about it is to construct the tree explicitly up front, take this functional version, replace fold with a version of fold that knows how to fold over trees in parallel, and fold it over the tree. Ta-da -- it would just work.
- 9 less lines of code.
- Easier to see that it's correct. Partly because it's less lines, but partly because those lines are more meaningful and less bland. It would be hard to see a typo in the repetitive inner loop of the first version.
- Two obvious independent pieces of code instead of one big piece of code. That means if you're reading it, you know how to go about understanding it; understand each piece in turn. Somewhat trivial when there are 25 lines, but serious if there are 200 lines.
- Easier to test and debug. At a REPL, it's trivial to see what the stack is going to look like five hops into the functional version; you just apply the processing function five times. To do the same to the imperative version, you need to either write some debug logic into the middle of the function or set a breakpoint and hit 'continue' in your debugger while you count on your fingers.
Those reasons are typical consequences of writing your code as a collection of data and pure functions.
Also, the semantics are not completely inherently serial for most possible stacks. The sequence of operations forms a tree of computation, and the branches of the tree could be computed in parallel. If you actually wanted to do that (say, if the operations took a long time individually) then the way you would go about it is to construct the tree explicitly up front, take this functional version, replace fold with a version of fold that knows how to fold over trees in parallel, and fold it over the tree. Ta-da -- it would just work.
Another reason the second may be better:
- Wrap the stack program in a transaction and simply discard the results to roll back the transaction. In an imperative program it is error prone to roll back a complicated operation—the most innocent looking function might mutate external state.
- Wrap the stack program in a transaction and simply discard the results to roll back the transaction. In an imperative program it is error prone to roll back a complicated operation—the most innocent looking function might mutate external state.
Well technically F# has no purity handling, so it's just as possible for the most innocent-looking F# function to have side-effects as well.
Thanks for the warning. That sucks.
My read on this is not that he is claiming those things, but that he is examining those claims to see if they are true.
To be honest, not getting another breathless reiteration of the Functional Programming Dogma is a breath of fresh air. I actually like FP in the general sense, think interesting things are happening there, and am keeping an eye on it (as well as using it in selected places in my job where it makes sense, so I've actually put some cash down on the thing), but I'm really tired of people who have just barely learned enough FP to implement something of, say, this exact level of complexity making wild boasts about how good it is. I suppose it's a specific case of the general problem of seeing someone argue something you agree with, but badly.
This particular "integer stack VM implementation" is so trivial that you can't make arguments based on it. Both the imperative and functional implementations are too tiny to make pronouncements.
To be honest, not getting another breathless reiteration of the Functional Programming Dogma is a breath of fresh air. I actually like FP in the general sense, think interesting things are happening there, and am keeping an eye on it (as well as using it in selected places in my job where it makes sense, so I've actually put some cash down on the thing), but I'm really tired of people who have just barely learned enough FP to implement something of, say, this exact level of complexity making wild boasts about how good it is. I suppose it's a specific case of the general problem of seeing someone argue something you agree with, but badly.
This particular "integer stack VM implementation" is so trivial that you can't make arguments based on it. Both the imperative and functional implementations are too tiny to make pronouncements.
The most, imho, accessible discussion of this stuff is Dybvig's 3 implementations of scheme. The first 75 pages or so are just a great way of using a functional style of thinking to implement a functional VM. http://www.cs.unm.edu/~williams/cs491/three-imp.pdf
It's long and dense, but there's is a valuable point view there, and scheme sidesteps the whole strong typing set of issues. You get a complete, optimized scheme interepreter in , what?, maybe 150 lines of code? seminal paper for an autodidact.
It's long and dense, but there's is a valuable point view there, and scheme sidesteps the whole strong typing set of issues. You get a complete, optimized scheme interepreter in , what?, maybe 150 lines of code? seminal paper for an autodidact.
I don't have much commentary except to say that that was a pleasure to read and I hope we can see more like this in the future.
Was there a particular part you found especially pleasurable? What made it more pleasurable for you to read than other writing?
Good question. The thing I most loved was the progressive refinement of the technique. I love seeing things transformed from rough to fine and seeing the rationale for each step.
It's neat to see how much more expressive F# manages to be compared to C#. One of his examples (passing an operator as an argument to a function) would probably take dozens or hundreds of lines to express in C# because it's just not something that's built into the language.
Er, the C# equivalent of applyBinaryOp state (+) is just applyBinaryOp(state, (a, b) => a + b).
That's not an operator, that's a lambda. The end result is the same, but semantically it's very different. Passing around an operator means you don't need to know the types involved - you can have a function that operates on any two values and applies an operator to them. That's not something you can do with lambdas in C#.
No, there's no difference whatsoever. .NET has no concept of "operators" that are different from functions.
F# is statically typed, just like C#, and the only reason you can pass + in this case is because the type of the stack is Stack<int>, so the compiler can statically infer that "+" means "the + operator on ints." At every usage, + has to refer to a specific function, or it wouldn't compile. For example, if it was a Stack<object> that happened to contain ints, it wouldn't compile.
(You could use .NET's "dynamic" type to make it dynamically resolve which function at runtime, but you could use it equally well in the C# example with a lambda.)
F# is statically typed, just like C#, and the only reason you can pass + in this case is because the type of the stack is Stack<int>, so the compiler can statically infer that "+" means "the + operator on ints." At every usage, + has to refer to a specific function, or it wouldn't compile. For example, if it was a Stack<object> that happened to contain ints, it wouldn't compile.
(You could use .NET's "dynamic" type to make it dynamically resolve which function at runtime, but you could use it equally well in the C# example with a lambda.)
> .NET has no concept of "operators" that are different from functions
That doesn't sound right. I'm pretty sure that arithmetic "+" is not a function. Citation needed.
That doesn't sound right. I'm pretty sure that arithmetic "+" is not a function. Citation needed.
There might be some optimizations on top of that, but overloadable operators in C# do get compiled to a function call (a static method call, if you want to be pedantic): http://stackoverflow.com/questions/6587107/c-sharp-operator-...
See VMAtm's comment's bytecode, showing that "[Decimal] + [Decimal]" compiles to:
To sum up: mquander is completely right, the CLR does not know anything about operators, language compilers will take whatever operator they have at a high level and compile them to method calls (usually). For more details, see http://www.amazon.com/dp/0735627045/
[0] other runtimes make different choices, Python encodes most of its operators into bytecode for instance: http://docs.python.org/library/dis.html#opcode-BINARY_POWER
See VMAtm's comment's bytecode, showing that "[Decimal] + [Decimal]" compiles to:
IL_0011: call valuetype [mscorlib]System.Decimal [mscorlib]System.Decimal::op_Addition(valuetype [mscorlib]System.Decimal,
valuetype [mscorlib]System.Decimal)
To sum up: mquander is completely right, the CLR does not know anything about operators, language compilers will take whatever operator they have at a high level and compile them to method calls (usually). For more details, see http://www.amazon.com/dp/0735627045/
[0] other runtimes make different choices, Python encodes most of its operators into bytecode for instance: http://docs.python.org/library/dis.html#opcode-BINARY_POWER
Interesting. However, operators and functions present very differently when writing c# code.
It's easy to put a lambda or a named function in a variable, pass it to a function, etc. However, if you want to do that to an operator such as "+", the first thing to do is to wrap it in a lambda - e.g.
It's easy to put a lambda or a named function in a variable, pass it to a function, etc. However, if you want to do that to an operator such as "+", the first thing to do is to wrap it in a lambda - e.g.
// invalid
// Func<int, int, int> plus = + ;
// works in a wrapper fn
Func<int, int, int> plusFn = (a, b) => a + b;
public T ApplySomeFunc<T>(Func<T, T> func, T value)
{
// this works
return func(value);
// this does not
//return value + value;
}
> Interesting. However, operators and functions present very differently when writing c# code.
Aye, but that's more of a limitation of C#'s syntax
> However, if you want to do that to an operator such as "+", the first thing to do is to wrap it in a lambda - e.g.
That's pretty much what a section (the parens around the operators) does in F# or Haskell.
> I know that the language has no way to specify that the type T has a "+" operator so that's not going to work
Well it's not so much that "operators and functions present very differently when writing C# code" but that "methods and functions present very differently when writing C# code" and that operators are (static) methods more than functions in C#.
Also that C# has no numeric tower[0] so there's indeed no way to say a type is a generic number (whether that number's an int, a double or a decimal). If there was a root `Number` type you could write something along the lines of:
[1] http://hackage.haskell.org/packages/archive/base/latest/doc/...
Aye, but that's more of a limitation of C#'s syntax
> However, if you want to do that to an operator such as "+", the first thing to do is to wrap it in a lambda - e.g.
That's pretty much what a section (the parens around the operators) does in F# or Haskell.
> I know that the language has no way to specify that the type T has a "+" operator so that's not going to work
Well it's not so much that "operators and functions present very differently when writing C# code" but that "methods and functions present very differently when writing C# code" and that operators are (static) methods more than functions in C#.
Also that C# has no numeric tower[0] so there's indeed no way to say a type is a generic number (whether that number's an int, a double or a decimal). If there was a root `Number` type you could write something along the lines of:
public T AddNumbers<T> where T:Number(T value)
{
// works because all numbers have a `+`
return value + value;
}
addNumbers :: (Num a) => a -> a -> a
addNumbers a b = a + b
[1] http://hackage.haskell.org/packages/archive/base/latest/doc/...
> That's not an operator, that's a lambda. The end result is the same, but semantically it's very different.
It's not, actually. In most functional languages — including F# — operators are just a special case of functions. Haskell will let you both use operators as (prefix) functions (via sections):
Uh? You need to know them in exactly the same way you do for functions.
> you can have a function that operates on any two values and applies an operator to them.
No, you most definitely can't, both operators and functions are typed. They work the exact same way but for the syntactic difference that operators are infix and may have precedence junk on top. But that's parsing, aside from that, a functional language will treat functions and operators the same way (outside of the odd builtin)
It's not, actually. In most functional languages — including F# — operators are just a special case of functions. Haskell will let you both use operators as (prefix) functions (via sections):
Prelude> (/) 42 2
21.0
Prelude> even `filter` [0..20]
[0,2,4,6,8,10,12,14,16,18,20]
Prelude> let (><) a b = a * b in 3 >< 4
12
Prelude> let a >< b = a * b in 3 >< 4
12
Prelude> let a `add` b = a + b in add 3 4
7
Prelude> :t (1 +)
(1 +) :: Num a => a -> a
Prelude> :t map (+ 1)
map (+ 1) :: Num b => [b] -> [b]
Uh? You need to know them in exactly the same way you do for functions.
> you can have a function that operates on any two values and applies an operator to them.
No, you most definitely can't, both operators and functions are typed. They work the exact same way but for the syntactic difference that operators are infix and may have precedence junk on top. But that's parsing, aside from that, a functional language will treat functions and operators the same way (outside of the odd builtin)
Nope. In the F# version, the '+' is passed in as an argument. That is harder to do in c# without wrapping the operator in a function.
it's probably more like
applyBinaryOp(op, a, b) => op(a, b)).
Where op is a wrapper function, in the case of '+' it would be
Func<int, int, int> op = (a, b) => a + b;
it's probably more like
applyBinaryOp(op, a, b) => op(a, b)).
Where op is a wrapper function, in the case of '+' it would be
Func<int, int, int> op = (a, b) => a + b;
his `applyBinaryOp` was the way it would be called: in F# you'd use
applyBinaryOp state (+)
applyBinaryOp(state, (a, b) => a + b)That's pretty similar, except you have the "(a, b) => a + b" inline.
In earlier versions of C#, yes, but with the current language, stuff like that is pretty easy.
Which is kind of the point of F#, right? To get good ideas funneling back to the masses?
Seems like C# is doing the same, and more effectively.
The two processes aren't unrelated. Plenty of good ideas came into the .NET world via F# and then flowed to C#.
C# has been making Java better for years. Now F# gets to make C# better. Everyone wins!
You know I'm sympathetic to this line of thinking, but I wished he would have actually used this VM example to back up these statements.
Why is the version without mutable state better? That's not explained at all. I can think of some reasons why it would be worse -- e.g. more memory allocations. For this VM, its semantics are inherently serial, so the concurrency argument doesn't apply.