General recursion in programs (that makes termination undecidable) requires a fix-point operator of type (a -> a) -> a
The logical equivalent of this is an axiom (P -> P) -> P which lets you prove anything. So non-termination in a programming language corresponds to being able to prove anything - including False - in the logic.
I think SSA is related to CPS, but I'm not sure of the correspondence with Linearity. I think the key difference (but I'm not sure), is that SSA only asserts that a variable is assigned once, but might be consumed multiple times. Linearity says that things must be consumed exactly once. For instance, I think:
y <- x + 1
z <- x + 2
is a legal SSA expression, but it is not a legal linear expression because x appears twice.
I think you could say that. Another way to look at it would be to say it's about organising your code in such a way that side-effects don't really matter. For instance, if only I have access to a reference, then I'm free to update it without risk of disrupting anyone else's world view. You could say that there is no side-effect from my update because no-one can observe the change.
This is nice for functional programming because it gives you the performance of mutable state and destructive update, but in a way that is 'pure', or side-effect free, from the outside.
I also get the impression that some people view using dynamically typed languages as a badge of honor, taking more expertise to harness the greater 'expressive' power, all whilst juggling the types in your head. Bad programmers can't use them properly, but if you're one of the good ones then you're not held back by rigid types.
I'm one of the dumb ones and just let the computer do the checking for me.
It's already been flirted with in JS I believe [1], though not specifically for Flow. The problem is that it falls down in the higher order case, which happens quite alot in JS. Also, I don't think JS has a mechanism like sys.setprofile that deals with alot of the pain points.
I'd consider those languages optionally typed, rather than gradually typed, as they don't insert run-time type checks. Regardless, I still think it's all interesting and valuable work.
I think the jump from 'Category' to 'Value: Anything that can be assigned to a variable.' was a somewhat jarring change in abstraction level.
Also, trying to explain Monad, Comonad, or Applicative as 'jargon' is probably a step too far IMO. They are not important for getting started with FP, and describing them without their equational properties is kind of meaningless.
That being said I liked alot of the inclusions; partial application, closure, composition. I think the collection is probably slightly guilty of trying to be too clever by including advanced concepts.
I'm not really sure why you need the requirement of infinite sequences to do functional programming, or the restriction of no intermediate variables. Let bindings seem like a nice thing to have.
I've done some work on dynamic type checking for JavaScript and the tricky part is always when things start going higher order; sadly this is often omitted from examples.
The motivation for dynamic checking was often because many JavaScript programs couldn't be given any useful static types. With the great work on Flow and TypeScript I'm starting to become convinced that we'll just be able to statically check most JavaScript programs in the future and get decent types out.
Really interesting stuff! I tried out some higher-order examples:
INPUT >>>
function add(f, b) {
return f(b);
};
let a = add(function(x) {return x + 1}, 3);
OUTPUT >>>
function add(f: function, b: number): number {
return f(b);
};
let a: number = add(function(x: number): number {return x + 1}, 3);
and I noticed that the flow type annotations are added to the call site, rather than on the argument f in the definition of add. Are all the types that you generate first order?
> Think about being able to specify protocols in the type system and ensuring that your client and server meet the specifications. The example in that link is about user authentication. Imagine having a proof that the program can only get into a "LoggedIn" state by going through the authentication protocol.
This seems like a very simple concept when compared with other systems using software transplants [1]. The most important thing I gleaned from this is the benefit of having 'type information' (clojure specs) available as first class data. The reason why this is so simple, which isn't a bad thing, is because clojure (and lisps) makes it easy to get metadata and work with it.
"So, is JavaScript a truly functional programming language? The short answer is no.
Without support for tail-call optimization, pattern matching, immutable data struc-
tures, and other fundamental elements of functional programming, JavaScript is not
what is traditionally considered a truly functional language."
Time again I'm always surprised by how people over look type systems when talking
about functional languages. Really, much of that list is not fundamental to FP, but
always giving me an Int when you promise one matters.
This is all true, but is it not a problem that most static languages don't let you (easily) specify the kind of invariants people include in unit-tests.
I would distinguish Hearthstone (a.k.a Wizard Poker) from the rest; Hearthstone is fundamentally a gambling game.
However, I would also distinguish the "in-game" gambling in Hearthstone from CSGO because there is no legitimate or practical way to monetize your card collection. Once (or if) you have all the cards, there is little incentive to keep buying packs as you can only play with cards. In CSGO however, there is always the potential to open a new valuable skin that can be sold.
The problem doesn't really have anything to do with immutability; the problem is dependency and composition.
E.g.
f :: A -> B
g :: B -> C
will let me write g(f(x)), but not f(g(x)). It does not matter if f and g are 'pure', the point is that f must come before g. I think the mistake is to think that functional programming is about immutability, and that immutability solves the problems. Immutability is there to keep the types honest, it is fine to have effects aslong as we are upfront about them, and don't conceal them under false names such as "int" and "bool".
The logical equivalent of this is an axiom (P -> P) -> P which lets you prove anything. So non-termination in a programming language corresponds to being able to prove anything - including False - in the logic.