Live data from Hacker News

Where Do Type Systems Come From?

blog.felipe.rs

101–110 of 171 posts

Re: Where Do Type Systems Come From?

#101
post #99

Earlier quoted context omitted.

Could you say what type systems those are? Thanks.

To protect against NPEs you need to make nullable and non-nullable types different and forbid the programming from trying to use a nullable value without doing a null check first (doing a null check returns a non-nullable reference in case of success). One example of this is any of the languages with Albegraic Data Types, where it is super easy to create an Option type that encapsulates this concept. For an example o…

Thanks, this should make for some interesting weekend reading.

Re: Where Do Type Systems Come From?

#102

What a great piece! I wish the author would expand on this piece with either more installments or a even short book. I find myself interested in type systems as it relates to programming language design but I haven't found much middle ground between the basic types described in introductory texts about a language and the opposite extreme heavy academic texts such as the ones the author is breaking down in this articl…

> Can anyone recommend any other such middle ground resources on type systems and type system theory?

I really enjoyed Pierce's Types and Programming Languages. As I recall, he starts with the simple untyped lambda calculus, and builds a motivation for a type system, as well as the type system itself. It then switches to ML (or perhaps OCaml) and shows how features can be built-in to a type system as they're described.

I think it's a good fit - I know you said not heavy academic texts, but I don't think it's too heavy, it's at the level of an introductory undergraduate course. (Beware Advanced Topics in ~ by the same author which probably is on the heavier end, I don't know, I haven't braved it yet!)

Re: Where Do Type Systems Come From?

#103
I found Tomas Petricek's essay on "Against a universal definition of 'Type'" very informative. He argues that the word 'type' has shifted shape many times since Frege/Russel, in that the intuition behind them is different. He also argues that multiplicity of definition is a good thing.

http://tomasp.net/academic/papers/against-types/

Re: Where Do Type Systems Come From?

#104
post #96

Earlier quoted context omitted.

I'm assuming parent is thinking of Rust. And more generally type systems relying heavily on linear types (I believe).

Rust's borrow checker isn't a type system, is it? Sure, its benefits are similar to a linear type system, but actually it's a separate compiler pass whose internals are described imperatively and don't look type-based to me: https://github.com/rust-lang/rust/blob/master/src/librustc_b... If anything, I agree with zzzcpan and disagree with swsieber. Types are nice but people oversell them. OO languages appeared at the…

It wouldn't be possible without an affine (at least) type system such as Rust's.

Affine logic rejects contraction, i.e.

     Γ, A, A ⊢ B
    -------------
      Γ, A ⊢ B
My intuition (so take a liberal dose of salt) is that this pretty directly translates to disallowing reuse: we can't see a type twice and continue (inference) as if we saw it once.

Of course, that's very hand-wavy, and doesn't say (as I believe is the case) that there wouldn't be some other way to proceed through a combination of other rules.

Re: Where Do Type Systems Come From?

#105
post #63

Distinctly unimpressed by this post. The author seems to have an axe to grind with mathematicians as a class, which, as we would have been told in school, isn't 'big or clever'. The whole of programming, nevermind types, perhaps the most mathematical part of modern programming, arises from mathematics. There's some good history here, but the early paragraphs in particular are a display of ignorance if not arrogance.…

>"Distinctly unimpressed by this post. The author seems to have an axe to grind with mathematicians as a class, which, as we would have been told in school, isn't 'big or clever'." I thought it was intended to speak to people who might be intimidated or feel obtuse when they encounter really dense academic texts when trying to learn more about type systems as it relates to programming. As such I really appreciated it…

I've no problem with that, it was the opening quotation, accompanying graphic, and following paragraph which read - to me, though I appreciate I may not have read it as it was intended - quite disrespectfully toward mathematicians.

Among whom I cannot count myself, for whatever it's worth.

Re: Where Do Type Systems Come From?

#106

Earlier quoted context omitted.

Interesting. It could still be argued this program isn't meaningful (or perhaps "not useful").

Well, it is a trivial example. In reality, such things would be hidden in the complexity of the code. One could argue that if the correctness of the code cannot be accepted by the type system then it would also be confusing for a human to look at, and should therefor be refactored; which is why (in practice) this is a non issue. For a less trivial example, consider the expression "f(x) + g(x)" where both f and g can…

> 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.

You can encode this quite easily in a language with a dependent types.

Re: Where Do Type Systems Come From?

#107

Earlier quoted context omitted.

The category-theory window onto the world of types only appeals to a small subset of human minds. For the average programmer you may as well be spouting gibberish because the average programmer will have no way to evaluate the claims (if any) you are making. Note, I am saying that you may as well be and not that you are . Please do not misunderstand me. Types systems certainly are formal theoretical systems but I per…

Type theorists are people who understand arrows very well -- as long as those arrows aren't pointers. :)

ba-dum tss! are you here all week?

Re: Where Do Type Systems Come From?

#108
post #74
post #38

Earlier quoted context omitted.

There’s the technical aspects of the fact that every language has to have some notion of “type”. And seemingly interpreted languages might be JIT-compiled etc. This is of interest if you care about the implementation of languages. Then there’s the opinions that users of languages with more elaborate, expressive type systems have, like how some people really enjoy Haskell or Elm because they feel that the type system…

> There’s the technical aspects of the fact that every language has to have some notion of “type” This isn't true. There are no types in lisp or untyped lambda calculus.

Common Lisp has a primitive type system. Some implementations use that for compile-time type checks:

An integer type I1 from 0 to 65535.

    (deftype i1 (&optional (min 0) (max 65535))
      `(integer ,min ,max))
The function foo gets an integer and returns an I1:

    (declaim (ftype (function (integer) i1)
                    foo))

    (defun foo (i)
      (mod i 65536))

    (defun test ()
      (foo 6712312)       ; okay
      (foo 311212.2))     ; wrong call
Let's compile it in SBCL, a Common Lisp compiler:

    ; compiling file "/private/tmp/test.lisp" (written 08 JUL 2017 11:10:09 AM):
    ; compiling (DEFTYPE I1 ...)
    ; compiling (DECLAIM (FTYPE # ...))
    ; compiling (DEFUN FOO ...)
    ; compiling (DEFUN TEST ...)
    ; file: /private/tmp/test.lisp
    ; in: DEFUN TEST
    ;     (FOO 311212.2)
    ; 
    ; note: deleting unreachable code
    ; 
    ; caught WARNING:
    ;   Constant 311212.2 conflicts with its asserted type INTEGER.
    ;   See also:
    ;     The SBCL Manual, Node "Handling of Types"
    ; 
    ; compilation unit finished
    ;   caught 1 WARNING condition
    ;   printed 1 note

As you can see that it detects the type error.

The type system has been defined for Common Lisp with its first version in 1984. It had been used to allow the compiler to generate optimized code or to do more precise runtime checks. Early on in the mod 80s the CMUCL compiler then added the idea to use these type declarations as type assertions and to check those at compile time.

Re: Where Do Type Systems Come From?

#109
post #97
post #82

Earlier quoted context omitted.

> On the other hand, this means that typed systems are in some sense strictly less expressive than their untyped counterparts. 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 fac…

> It is often very useful to structure different types of data together in a common structure. "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 lo…

How do you define expressiveness? To me, it means saying more with less. Applied to code it means doing more with less work. Which directly translates to productivity gains.

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.

Re: Where Do Type Systems Come From?

#110

Earlier quoted context omitted.

>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 :-) Any type system will reject some correct program. As a trivial example, consider: if( f()…

Interesting. It could still be argued this program isn't meaningful (or perhaps "not useful").

At this point, you start hitting a problem from fundamental computation. When are 2 programs equivalent? Is it when they behave equivalently in any implementation or is it when there is a chain of rewriting rules that change one to the other.

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.

Post reply on HN