In case it's not clear, it's just that it eventually ends up with a run time error (the talk about runFunction being a second-order function is just an explanation for why you should expect it to end up with a run time error). The evaluation is
program3()
== runFunction(runFunction)
== runFunction(1)
== 1(1)
== Error: func (with value 1) is not a function1(1) -> 1
Just because the common idea of application is that it only applies to functions does not mean that application applied to other types is nonsensical and should end up with a runtime error.
If your language allows application to be defined for different types, then the type system should be capable of determining the type that returns from application.
A practical example of a language in which application is valid for integers is Unicon/Icon. Both functions and integers have specific semantics with regards to application. And failure is an option.
foo :: a -> (b -> c)
Not saying it's wrong, but "foo is a second-order function" is a distinctly minority opinion.To a useful first approximation, Haskell works as a cartesian-closed category, which basically means we have tuples and that tuples harmonize with functions so that foo behaves just like
uncurry foo :: (a,b) -> c
which is a first-order function.So the majority opinion calls foo a first-order arity-2 function.
Here's a bar function that's truly second-order:
bar :: (a -> b) -> c
In general, the order of a function is the count of parens nesting the leftmost innermost arrow. It is invariant to currying/uncurrying as well as permutation of arguments.The same counting principle applies to other invariants such as ranks and kinds.
"How high can the order of a function go?" is the question explored in this blog post [0]. Note how the author's definition of order -- essentially the same given here -- got left and right mixed up.
[0] http://math.andrej.com/2006/03/21/interesting-higher-order-f...
Here's an example: The W combinator `\f x -> f x x` can be expressed in Haskell but it doesn't work everywhere it should, unlike in an untyped universe:
http://us5.campaign-archive1.com/?u=4937a9a2eb9eee0a26e1e0a2...
In other words, types can sometimes make you lose reuse.
That's amply compensated by types removing massive amounts of junk in the untyped world. If you don't believe me, try hacking in an untyped calculus sometime.
That's an example in one type system, not a feature of all type systems. There's a good argument that typing is more expressive than dynamically typed languages: you can always add a dynamic type to your style system and recover all dynamically typed language features, but you can't go the other way around and recover all the features of a statically typed language. For instance, the performance benefits.
Any type system will reject some correct program. As a trivial example, consider:
if( f() ):
1 + "a"
else
1
This is a perfectly fine expression iff the result of f() is always false.The issue with the first definition is 2-fold. What set of implementations are you qualifying over, and what to do with weird programs that crash occasionally. This is similar to what happens in the given example. The program is equivalent to 'return 1' when f is always false. Otherwise, it might crash.
In the second definition, 'return 1' and the given program are just different programs, until you actually substitute an f and continue reduction.
For a less trivial example, consider the expression "f(x) + g(x)" where both f and g can return either a number or a string. It is conceivable that for any given x, they would always return the same type, but a type system cannot detect every such case.
Or consider a program like:
x = 1
print_int(x)
x="a"
print_string(x)
I have seen code just like this in dynamically typed languages. You can also run into a simmilar situation that is not obviously correct if, for example, x is a global variable while the program is running a state machine. You can then view each state a transitioning the type of x. Determining if such a program is correct would involve knowing each state transition, what type of x is expected when control enters a state, and what type x is when control leaves a state (and a given state might have multiple output (or even input) types. I have seen one program that actually worked like this; and it was not fun to modify.Of course, a type system is no guarentee that you do not have this sort of problem. For example, you could say, in the first example, that x is a union type of Int and String (and print_int and print_string are defined to operate on such a union). In this case, the program is well typed, but has partial functions, so the type system cannot guarantee that there will not be a runtime error when you call them (it won't, however, be a type error, since the type system missed it).
You could also have x be an untagged union. In this case, I don't see a way of doing any better than undefined behavior.
A completely different type of example, is C code such as:
*0x01 = 0
which means "set the memory at address 1 to 0", but is poorly typed. "f(x) + g(x)"
This example is way too trivial to explain why type systems are generally undecidable. Let's imagine: def f/g(x):
if isinstance(x, str):
return 6
elif isinstance(x, int):
return 'a'
It is decidable for any type of x that is previously known. More importantly, type systems were essentially created to be able to prove whether a given expression is decidable or not. x = 1
print_int(x)
x="a"
print_string(x)
This is solved by A-normal form (https://en.wikipedia.org/wiki/A-normal_form). Or by a more general concept that is available outside functional languages, SSA (https://en.wikipedia.org/wiki/Static_single_assignment_form).You can make a point that this code is hard to modify in dynamic languages, but it is an issue with the code style rather than type systems. For example - IntelliJ IDEA would highlight such Pythonic code as incorrectly typed, since you have changed the type and therefore the variable itself.
I find the general argument against complexities in the type systems such as Haskell to be quite amusing, to be fair. Most of the time you are not dealing with code that is undecidable - and that's why type systems are interesting.
You can encode this quite easily in a language with a dependent types.
x = 1
print_int(x)
x="a"
print_string(x)
the type system could simply instantiate a new variable, x: string, that shadowed the old x: int. this is perfectly valid ocaml, for instance: let x = 1 in
Printf.printf "%d\n" (x + 1);
let x = "hello" in
print_endline (x ^ " world")let x = string-of-int(x)
and the rhs will take the value of x (a well-typed integer variable from the previous scope, and the lhs will introduce a new x (a well-typed string variable) in the newly created scope.
this is an orthogonal thing to static/dynamic typing, incidentally; for instance in ruby you can say
a = 10
(3..5).each do |a|
puts a
end
puts a
and you will get 3
4
5
10
the a within the do loop being a new variable that happened to have the same name as the a in the outer scope, but referring to a different actual variable. f(x) + g(x)
For any type of x is enumerable. What that means is that for this specific expression, you can enumerate all of the types that x may take, and then enumerate all of the types that a function would return, given the types (if you can). You can then decide whether this expression is true or not.Now it depends on the implementation of f and g. And type systems, in most of the practical cases - would be able to deal with this.
x = 1
print_int(x)
x="a"
print_string(x)
The second example is always decidable, if we agree that semantics of '=' are generally a question of equivalence.Usually one would have:
zerothOrderFunction :: a
firstOrderFunction :: a -> b
firstOrderFunction' :: a -> (b -> c)
SecondOrderFunction :: (a -> b) -> c
After all, the functions firstOrderFunction and firstOrderFunction' are the same up to currying.The standard definition of order is given here (at the end of the section):
https://en.wikipedia.org/wiki/Simply_typed_lambda_calculus#T...
This happens quite often. Take datastructures. It is often very useful to structure different types of data together in a common structure. Now in most cases, you don't know in advance which type will go where in the datastructure, as the data might only be known or derived at runtime.
In fact I'd say dynamic behavior is the major expressiveness loss. Granted, I'm not sure how runtime vs static type system relate to type theory. Anyone can educate?
"Very useful" often just means: coding a properly typed, easily-understandable solution takes longer than doing it untyped.
I argue that is the case only when using a plain-text editor. When you have a good IDE for a typed-language at hand that can refactor, complete, analyed and follow code on the press of a button, you lose this "advantage" of untyped languages.
Now, what IDE and language are you referring too? The best one I've used was VisualStudio for C#. While I'd say typing wasn't adding too much overhead in it, its type system is also poor, and it's arguable that it may not really prevent much bugs. Now, it does help make C# faster.
It’s just that historically people have found it markedly more useful to have that information available statically, because it lets you prove things about your code that hold “for all” cases (universals), not just “for some” that are executed (existentials). And static information can be used for optimisations because of those guarantees—if you have proof, you don’t need a fallback.
If you give me an unknown function f : ∀T. T → T in a statically typed language, then I know it always returns a value of the same type as its argument. With some assumptions (purity, parametricity, halting) I even know it must be the identity function.
Whereas doing what I’m suggesting in a dynamically typed language, running inference dynamically, I could only recover existential properties: that there are some types for which f returns a value of the same type as its input. So I could recover more and more information (in the form of an intersection type) by calling the function with different inputs:
f : int → int
f : (int → int) ∧ (string → string)
f : (int → int) ∧ (string → string) ∧ (Foo → Foo)
But I could never arrive at ∀T. T → T, because that’s essentially an infinite intersection.
ETA: actually I might not even be able to get this much information; I only know the output type for each input value, not each input type.
Now, you may say “okay, the original program doesn't exist anymore, but my language implementation is a term rewriting engine, so I have a current program that I can submit to the type checker”. Alas, most type checkers, Hindley-Milner included, operate on self-contained program fragments (i.e., not containing unbound variables), so you can't just submit any arbitrary program fragment. And, if you didn't want to type-check your original program, how likely is it that you will want to type-check the entire syntactic representation of the current program state?
Say, because you want to use that reference cell in two different threads.
And degrading the type to a union (int ∨ string) as I mentioned is still nondeterministic even though unions form a lattice—I can recover determinism when writing to the list in both A and B, but supposing A writes first, B writes second, and then A reads expecting only integers, it gets a type error because it hasn’t checked for the string case.
But I’d argue that 1. this is bad form and you want a type error somewhere and 2. you have this problem already with type-changing mutable references in a dynamically typed multithreaded language. (Say just “int” and “string” instead of “list of int” and “list of string”.)
> program3 fails because runFunction can only run first-order functions and runFunction is a second-order function – a function that takes a first-order function as a parameter.
Here I had no idea that JavaScript implicitly typed `runFunction` that way. That's cool.
Also, I never thought of "higher-order functions" as breaking into a countable hierarchy of nth-order functions, which is an interesting thought. In Haskell the hierarchy would start off as
In general, an nth-order function is a function which either1. Takes an (n-1)th order function as an input and returns a simple type.
2. Takes a simple type as an input and returns an (n-1)th order function as an output.
The upshot is that typed programming languages not only catch bugs, but prevent you from legally expressing many non-sensical expressions (analogous to the set theory paradoxes). For example, consider the expression
If you expand this expression, it reduces to itself: In a purely untyped language, this expression would be legal. But what would be its meaning? Arguably, it is non-sense, and should be excluded from the set of legally expressible expressions. The way to do this is through a type system. And indeed, if you typed this statement into a Haskell REPL you would get a type error; this statement can actually be proven to be untypable (IIRC).On the other hand, this means that typed systems are in some sense strictly less expressive than their untyped counterparts. It would therefore be interesting if somebody found an expression which was both (i) meaningful and (ii) only expressible in an untyped language. You would then have an argument for untyped languages :-)