News for hackers. Stuff that matters.
Re:Type Systems (2004) [pdf] by lisper on Thursday August 31, 2017 @02:04PM (#15142364)
> Languages where variables can be given (nontrivial) types are called typed languages.

This is a vacuous definition because it doesn't specify what is meant by "variable" or what it means to be "given a type." This is not nit-picking. It actually matters in the case of Common Lisp. Consider:

(let ((x 1)) (declare (fixnum x)) ...)

X is clearly a variable, but has it been "given a type"? In CL, type specifications are promises to the compiler, not specifications of program semantics. (declare (fixnum x)) means "I, the programmer, promise to write my code in such a way that the value of X will always be a fixnum, and you the compiler are free to assume that I will do this correctly in order to make my code run faster."

On the other hand:

(setf x (make-array 10 :element-type 'fixnum))

In this case the implementation is allowed (though not required) to make an array that can only hold fixnums. So are the array elements variables? And have they been "given a type"?

Re:Type Systems (2004) [pdf] by lispm on Thursday August 31, 2017 @02:24PM (#15142554)
Well SBCL/CMUCL/SCL try to be different. From the SBCL manual:

> all type declarations that have not been proven to always hold are asserted at runtime

Re:Type Systems (2004) [pdf] by adrianratnapala on Thursday August 31, 2017 @09:17PM (#15145409)
I think we can forgive such stuff at least in the intro. This document is clearly an introduction to type systems for people who know more about programming than they do about the underlying maths and logic of type theory. Good.

Also good is that it starts from what the reader knows informally rather than trying to build everything rigorously from the ground up.

Re:Type Systems (2004) [pdf] by catnaroek on Thursday August 31, 2017 @09:29PM (#15145470)
> Also good is that it starts from what the reader knows informally rather than trying to build everything rigorously from the ground up.

It's certainly pragmatic, but is it good? Maybe I'm biased as a math student, but I've seen first-hand the horrors that happen when people think they know something just because they have a vague intuition about the topic's main ideas.

Re:Type Systems (2004) [pdf] by adrianratnapala on Thursday August 31, 2017 @10:46PM (#15145737)
But whenever I have learned maths in strict lemma-proof form it was on the second time around. That is, I first had a general sense of the field and intuition about concepts and some of the results, and then rigorous stuff makes sense.

From everything I've read about how mathematicians work, I thought that was normal.

Re:Type Systems (2004) [pdf] by catnaroek on Thursday August 31, 2017 @09:30PM (#15145471)
> In CL, type specifications are promises to the compiler, not specifications of program semantics.

Then they aren't types.

Re:Type Systems (2004) [pdf] by rurban on Friday September 01, 2017 @07:02AM (#15147432)
Most of them are type hints. Perl6 and cperl have a similar distinction. Hard types and compiler hints. In an FFI context it's a hard type, with arrays or structs also, with primitives the compiler may ignore it or allow otherwise permitted temporary casts.
Re:Type Systems (2004) [pdf] by catnaroek on Friday September 01, 2017 @08:36AM (#15147836)
> Most of them are type hints. Perl6 and cperl have a similar distinction.

Why are so-called “type hints” interesting in? The real value in a type system is:

(0) Not having to worry about large classes of mistakes. They just don't happen in a legal program.

(1) Enforcing abstractions, i.e., not allowing library users to make decisions based on library implementation details.

(2) Managing the verification effort. Proving that a program meets its specification becomes much easier when components are guaranteed not to violate the assumptions made in each other's design.

A “type system” that can't do any of these is just a waste of engineering effort.

Re:Type Systems (2004) [pdf] by rurban on Wednesday September 06, 2017 @10:06AM (#15183753)
Yes, and much more. types also allows lowering generic ops to fast ops, which is typically 10x faster then without types.
Re:Type Systems (2004) [pdf] by catnaroek on Saturday September 09, 2017 @05:14PM (#15209187)
I'd love to read about how you can use so-called “type hints” to mechanically rule out programs that inspect the internal representation of abstractions provided by third parties.
Re:Type Systems (2004) [pdf] by hyperpape on Thursday August 31, 2017 @08:45PM (#15145271)
I believe that most type theorists will say that's not a type, since it is trivially unsound. Otherwise a Python program is typed, so far as the programmer sorta halfway thinks about types ("I can iterate over this") at some point.
Re:Type Systems (2004) [pdf] by lisper on Thursday August 31, 2017 @09:01PM (#15145346)
> it is trivially unsound

Why? (And what is the antecedent of "it"?)

Re:Type Systems (2004) [pdf] by hyperpape on Friday September 01, 2017 @01:47PM (#15150747)
The program containing the declaration is unsound because it doesn't preclude using the variable in ways inconsistent with the declaration.
Re:Type Systems (2004) [pdf] by lisper on Friday September 01, 2017 @01:59PM (#15150885)
Ah. In that case:

> that's not a type, since it is trivially unsound

You are misunderstanding what a type is. A type is just a subset of all of the possible data values in a language. Types by themselves don't do anything.

Re:Type Systems (2004) [pdf] by hyperpape on Friday September 01, 2017 @03:27PM (#15151690)
It doesn't count as an assignment of a type to a variable because it's trivially unsound. Are you happy with the rewording?
Re:Type Systems (2004) [pdf] by lisper on Friday September 01, 2017 @03:39PM (#15151768)
OK, but:

1. CL implementations are free to do static type analysis based on declarations (and some do) and they are also free to signal run-time errors if you assign a value not of the declared type (and some do).

2. Not all storage locations are variables, e.g.:

    Welcome to Clozure Common Lisp Version 1.10-r16479M  (DarwinX8664)!
    ? (setf a (make-array 10 :element-type '(unsigned-byte 32)))
    #(0 0 0 0 0 0 0 0 0 0)
    ? (setf (aref a 0) 'foo)
    > Error: FOO doesn't match array element type of #<VECTOR 10 type (UNSIGNED-BYTE 32), simple>.
The point is that focusing on "variables" makes tacit assumptions about programming languages that aren't necessarily true.
Re:Type Systems (2004) [pdf] by junke on Thursday August 31, 2017 @02:36PM (#15142673)
The hyperspec has a definition of what is a variable in the different namespaces. Also, for type declarations:

"Affects only variable bindings and specifies that the vars take on values only of the specified typespec"

Re:Type Systems (2004) [pdf] by lisper on Thursday August 31, 2017 @03:41PM (#15143240)
> The hyperspec has a definition of what is a variable

The hyperspec's definition only applies to the hyperspec, not the paper. On the hyperspec's definition, an array cell is not a variable, but it seems very unlikely that this is what the author of the paper intended. It's much more likely that what the author intended by "variable" the CLHS calls a "place". (But this is exactly the problem: we don't know what the author of the paper intended because he didn't say. We have to guess.)

> vars take on values only of the specified typespec

Right, but the spec doesn't actually say what happens when this constraint is violated.

Re:Type Systems (2004) [pdf] by junke on Thursday August 31, 2017 @05:02PM (#15143892)
> On the hyperspec's definition, an array cell is not a variable, but it seems very unlikely that this is what the author of the paper intended. It's much more likely that what the author intended by "variable" the CLHS calls a "place".

There is no syntax to declare the type of a single cell, you can only put identifiers (symbols), not places, into declarations. Either your variable is declared to hold an array of, say, fixnums, or you bind a variable to the content of a cell and declare the type of that variable.

> Right, but the spec doesn't actually say what happens when this constraint is violated.

The spec says the consequences are undefined. Either you code against the guarantees of your implementation (which are hopefully more precise), or you aim for portability and consistently add check-type before locally declaring types.

Re:Type Systems (2004) [pdf] by lisper on Thursday August 31, 2017 @05:17PM (#15144013)
> the spec doesn't actually say what happens when this constraint is violated.

> The spec says the consequences are undefined.

Don't those mean the same thing?

Re:Type Systems (2004) [pdf] by junke on Thursday August 31, 2017 @05:39PM (#15144181)
Let's try the Zen/taoist analogy.

At the end of the day, a Zen master tells his student: "your next lesson will start at 5am tomorrow, don't be late"; the student says: "what will happen if I am late?". The master doesn't reply.

The student goes to sleep and wakes up late. "You missed your lesson, come back tomorrow at 4am or else I can't guarantee your safety.". The next day, the student arrives on time.

----

Saying things are undefined is an explicit way of demarcating what is part or not of the specification. Otherwise, the meaning could ambiguous.

Re:Type Systems (2004) [pdf] by lisper on Thursday August 31, 2017 @05:51PM (#15144273)
OK. That seems like a pretty fine hair to split in the context of the present discussion.
Re:Type Systems (2004) [pdf] by equalunique on Wednesday September 13, 2017 @06:42AM (#15237046)
Is the notation used here standard in type systems research? I'm pretty much lost before halfway in at the _with_ concept.
Re:Type Systems (2004) [pdf] by kruhft on Thursday August 31, 2017 @12:20PM (#15141376)
Is Mathematics, as a language, considered typed in general?
Re:Type Systems (2004) [pdf] by adamnemecek on Thursday August 31, 2017 @12:29PM (#15141438)
Most mathematics isn't constructive (https://en.m.wikipedia.org/wiki/Constructivism_(mathematics)) so it doesn't really come up I think. E.g. you know how matrices need to have a certain shape to be multiplied? People don't really talk about what happens if they don't.

Physics on the other hand very much has types, the unit to type correspondence is dopetastic.

Re:Type Systems (2004) [pdf] by kruhft on Thursday August 31, 2017 @12:36PM (#15141505)
But what about Russel's type system(s)? Were they just an addition he proposed that never went anywhere, or are they used much like certain programming languages have types and others don't, depending upon the preference of the user? Or are types just 'too hard/restricting' for general mathematics?
Re:Type Systems (2004) [pdf] by danharaj on Thursday August 31, 2017 @12:59PM (#15141749)
Russel and Whitehead's type system never gained significant traction. It's primarily of historical interest. Once mathematicians became convinced that ZF set theory over first order logic was plausibly consistent and expressive enough, such foundational issues became less important to the typical mathematician.

Lately there's been a resurgence in foundations because of what new foundations like Homotopy Type Theory bring to the table. Funny how something as basic as equality can be revisited time and time again for thousands of years!

Re:Type Systems (2004) [pdf] by pmoriarty on Thursday August 31, 2017 @03:13PM (#15142960)
"Once mathematicians became convinced that ZF set theory over first order logic was plausibly consistent and expressive enough, such foundational issues became less important to the typical mathematician."

Was this decision ever explicitly expressed and agreed on by mathematicians at the time, or was it just implicitly adopted?

Re:Type Systems (2004) [pdf] by danharaj on Thursday August 31, 2017 @07:56PM (#15145041)
A bit of both over the years.
Re:Type Systems (2004) [pdf] by AnimalMuppet on Thursday August 31, 2017 @01:31PM (#15142033)
ELI5: Why would constructive math be more typed than non-constructive math?
Re:Type Systems (2004) [pdf] by adamnemecek on Thursday August 31, 2017 @02:05PM (#15142373)
Constructive mathematics is based on intuitionistic logic (i.e. classical logic without law of the excluded middle, meaning you don't have proof by contradiction, to demonstrate the existence of something you have to "construct" it). Intuitionistic logic is very close to type theory.
Re:Type Systems (2004) [pdf] by AnimalMuppet on Thursday August 31, 2017 @03:05PM (#15142874)
OK, ELI10: Why or how is intuitionistic logic very close to type theory? Is it based on type theory? Or is it just similar? In either case, how and why?
Re:Type Systems (2004) [pdf] by rraval on Thursday August 31, 2017 @04:01PM (#15143405)
See https://codewords.recurse.com/issues/one/type-systems-and-lo... for a pretty elaborate response to this question.

tl;dr: types are propositions and values are proofs of those propositions. Constructive logic is not concerned with (true xor false), but rather "I can prove A" or "I can prove not-A". There's also the middle ground of "I don't know how to prove anything about A".

Re:Type Systems (2004) [pdf] by adamnemecek on Thursday August 31, 2017 @03:31PM (#15143153)
Good ol' Curry-Howard isomorphism.

https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...

But the connections don't really end there.

Re:Type Systems (2004) [pdf] by Retra on Thursday August 31, 2017 @08:58PM (#15145335)
They are models of each other. You can translate statements in one to statements in the other by using some relatively simple rules.
Re:Type Systems (2004) [pdf] by catnaroek on Thursday August 31, 2017 @09:41PM (#15145499)
No particular technical reason.
Re:Type Systems (2004) [pdf] by marcosdumay on Thursday August 31, 2017 @02:02PM (#15142350)
Physicists just love to work on natural unities, where they throw their types and conversion functions out of the window and calculate in a unityped framework.
Re:Type Systems (2004) [pdf] by adrianratnapala on Thursday August 31, 2017 @08:48PM (#15145294)
Checking your units is a basic sanity check that we teach students. But as we advance, physicists throw away that wisdom. Theorists especially have an annoying habit of doing this, because all the repetitions of "c", "hbar" etc "k_B" etc clutter up their equations.

But I preffer to keep that stuff in, even when doing pretty abstract stuff. Essentially because I wanted the type annotations. For example my favorite convention for the Minkowski metric is:

     [c^2  0   0   0]
     [ 0  -1   0   0]  
     [ 0   0  -1   0]
     [ 0   0   0  -1]

That way your vectors are just $(t, x, y, z)$, where $t$ has units of time and the rest of space. Your covectors do come out oddly as $(c^2t, -x, -y, -z)$, but that's what makes them covectors.
Re:Type Systems (2004) [pdf] by catnaroek on Thursday August 31, 2017 @09:40PM (#15145496)
Alternatively, you can work with x^0 = ct instead of x^0 = t.
Re:Type Systems (2004) [pdf] by adrianratnapala on Friday September 01, 2017 @12:01AM (#15146023)
Yes, and and that a much more common convention than the one I favour. They do it partly because it keeps the factors of c out of the visible equations -- but I like my those cs.

Another reason is that people instinctively feel that the elements of the coordinate tuple all have to have the same units. But that's not necessary when you have a metric around. Indeed keeping irregular units is helpful because it prevents you from accidentally forgetting to multiply through by the metric.

Re:Type Systems (2004) [pdf] by catnaroek on Friday September 01, 2017 @08:35AM (#15147822)
The c factor doesn't really go away. It just gets shifted into 4-vectors.
Re:Type Systems (2004) [pdf] by gertef on Thursday August 31, 2017 @04:48PM (#15143790)
Mathematics is not a language. Your question is like asking if database-backed web applications are typed.

Mathematics is often expressed in language, That language us usually a mix of a human natural language English/French/German/etc plus symbolic extensions, and that is very poorly typed.

In the recent failed proof of P!=NP, the flaw was a type error:

https://cstheory.stackexchange.com/questions/38803/is-norber...

Type errors are rather common in math proofs that end up retracted.

But it's hard to call them type errors, because it's not like a computer program where the typechecker detected the collision or failed in some way: the proofs make very little mention of types at all, and it's up to the readers to apply a type-system from their own heads.

Re:Type Systems (2004) [pdf] by tom_mellior on Friday September 01, 2017 @03:49AM (#15146860)
> In the recent failed proof of P!=NP, the flaw was a type error:

The link you gave does not support this statement.

Re:Type Systems (2004) [pdf] by kruhft on Thursday August 31, 2017 @06:12PM (#15144403)
The conveyance of mathematics from one mind to another must be done with some form of language.
Re:Type Systems (2004) [pdf] by adrianratnapala on Thursday August 31, 2017 @08:39PM (#15145245)
This is trivially true, but only because you can keep stretching the definition of language.

For example suppose a geometer explains something to another geometer just by drawing diagrams with no verbal or textual annotation. You can plausibly claim that "geometry diagrams" are a language, but now you are defining language so broadly that the term is almost useless.

Re:Type Systems (2004) [pdf] by kruhft on Friday September 01, 2017 @08:19AM (#15147714)
Why would you say that "geometry diagrams" are not a language?

Google, define language:

lan·guage ˈlaNGɡwij/Submit noun 1. the method of human communication, either spoken or written, consisting of the use of words in a structured and conventional way. "a study of the way children learn language" 2. the system of communication used by a particular community or country. "the book was translated into twenty-five languages" synonyms: tongue, mother tongue, native tongue; More

I would say "geometry diagrams" are a language, by the second definition.

Re:Type Systems (2004) [pdf] by guelo on Thursday August 31, 2017 @08:58PM (#15145331)
There are loose conventions. For example, in some contexts θ and α usually designate angles. But even then the only way to know if the angle is in degrees or radians is by tracing the proof from the start. It's easy to make errors.
Re:Type Systems (2004) [pdf] by heinrichhartman on Thursday August 31, 2017 @12:38PM (#15141530)
I don't know my way around Type theory, but I have done a fair bit of Mathematics and Programming.

Mathematics is largely based on set theory, so every element has a set it belongs to, and every function has a source-set (domain) and a target-set (co-domain). Mathematicians are very careful to always qualify the encompassing sets, domains and co-domains. You would always write:

* Let x \in X be a point in Space. * Let f:A->B be a fuction with ceratin properties.

This is even more pronounced in Category theory, which invaded algebra and geometry quite heavily. Where the only thing you know about a function is it's domain, codomain and how it composes.

So, yes. Mathematics on a practical level is _very_ type aware.

And it also prevents you from doing stupid stuff: f:A->B, g:A->C, can't be composed, so f(g(x)) is a "type error".

Re:Type Systems (2004) [pdf] by Drup on Thursday August 31, 2017 @01:41PM (#15142129)
While Mathematics is type aware, Mathematicians often aren't. They mix things that are "not the same object, but almost, I swear", and constantly write ill-typed expressions.

This is generally on purpose, to avoid making explicit things that are obvious, but as someone developing and using statically typed languages, reading Math papers is often quite frustrating.

Re:Type Systems (2004) [pdf] by tel on Thursday August 31, 2017 @06:20PM (#15144462)
Generally, no.

As others have mentioned, Mathematics isn't really a language. It's at the very least absolutely certainly not one language. Certain parts of Mathematics use a typed language. Certain parts rely on other kinds of containment properties which serve nicely as types.

Finally, generally, math is very interested in being completely clear the properties of objects and very interested in speaking abstractly, so even if the language of use is untyped the logic is often very rigorous around typing.

Above it all, perhaps, is the idea that mathematics is concerned with proof and proofs may contain reference to the properties being discussed---metamathematical ideas pervade normal mathematical thought. This means that even absent of types the content of a mathematical utterance is often going to explicitly posit, discuss, and prove properties similar to type propositions.

Re:Type Systems (2004) [pdf] by nerdponx on Thursday August 31, 2017 @01:11PM (#15141866)
I assume that by "mathematics" you mean" mathematical notation".

No, but static type hinting is strongly encouraged. If I say in my paper that "x" is a vector, if I later use "x" to mean a scalar it would cause tremendous cognitive dissonance and confusion for the reader. There is no compiler error, in that the information can still be read and understood. It is just much more difficult.

Mathematical notation is also aggressively polymorphic. The expression "f x" can have wildly different meanings depending on what "f" and "x" are.

Re:Type Systems (2004) [pdf] by dangerousfood on Thursday August 31, 2017 @10:14PM (#15145631)
Why are these academic white papers always in the exact same format? Is there a formatting guide somewhere I don't know about?
Re:Type Systems (2004) [pdf] by erokar on Thursday August 31, 2017 @12:47PM (#15141618)
Admittedly, I skimmed through this, but I miss a balanced discussion of the cost/benefits of static typing. I could see no discussion of the benefits of dynamically typed languges. Insted arguments for static typing are enumerated without a single reference.

For a more balanced discussion, see: https://www.infoq.com/presentations/dynamic-static-typing

Re:Type Systems (2004) [pdf] by ericssmith on Thursday August 31, 2017 @01:30PM (#15142024)
You should try skimming to the end, where there are two pages of references. Not to mention the fact that Cardelli is a prominent figure in the study of programming languages.

And I think you'll find that Gilad Bracha is a more informed critic of reliance on static type checking.

Re:Type Systems (2004) [pdf] by pjmlp on Thursday August 31, 2017 @01:56PM (#15142294)
Yep, he was one of the designers in the Modula-2+ and Modula-3 languages.
Re:Type Systems (2004) [pdf] by simon_o on Thursday August 31, 2017 @10:07PM (#15145597)
"Dynamically" typed languages are untyped, and are therefore likely considered out of scope in this document.