News for hackers. Stuff that matters.
Re:Alan Kay on Lisp by shalabhc on Friday October 27, 2017 @06:17PM (#15572649)
> more rigorously enforced at compile time

'Compile time', like everything in the artificial science of computing, is a made up thing. We might reconsider if it's a useful idea to keep. Why must there be a specific point in time, when we verify interconnections within a little bundle of code, but later when the bundle of code integrates with a larger system we are completely fine with very different, loosely coupled connections?

The internet is dynamically typed. I just don't see static verification scaling to that level. But verification is still great - so maybe we need a way to verify connections between components as and when they bind. If we build a good model for this late bound 'negotiated safe' binding, the static model might become unnecessary (because you can do the verification whenever you choose, or at multiple times and different scales, as the 'bundle of code' integrates with larger and larger systems.)

Re:Alan Kay on Lisp by Silfen on Friday October 27, 2017 @06:28PM (#15572709)
"Compile time" is artificial, but the difference between static and dynamic is natural (in some sense, I realize these words are quite slippery). It emerges from the underlying mathematics. There's a real difference between correctness properties that I can prove without running my program and correctness properties that will introduce failures at runtime.
Re:Alan Kay on Lisp by sparkie on Friday October 27, 2017 @11:20PM (#15573830)
You're using a dynamic language (bash) to invoke your statically-typed-language-compiler and then to also invoke the binary it produces.

But what's the difference to say, having just a single dynamically typed language with library functions "type-check-my-code", which returns an encapsulated value, and "run-my-typechecked-code" which takes the encapsulated value as input? The whole process happens at "runtime" here.

The artificial static/runtime boundary is introduced by the way Unix implements files and processes. All statically typed languages are effectively supersets of the language of Unix. In Unix we can treat each executable binary as a library function (except that we have a massive overhead for calling it). The designers of Unix were well aware of this which is why from the POV of bash, there's no distinction between invoking a binary and invoking another script written in bash.

How much of the Unix binary and process bloat is really necessary though to say, concatenate N files? Even someone writing a C program will avoid calling cat and instead implement it themselves, or call a library that does it. Perhaps we need to reconsider where the boundary between type checking and running code should be.

Re:Alan Kay on Lisp by xfer on Saturday October 28, 2017 @02:40AM (#15574232)
runtime here means the runtime of target program, it has nothing to do with unix. If your program fails while executing due to a type error, it's not static type-checking.
Re:Alan Kay on Lisp by shalabhc on Sunday October 29, 2017 @05:58PM (#15581668)
I think sparkie has a very valid point. It has to do with Unix because a 'program' in Unix has specific meaning (and Windows is no different in this regard, btw). A Unix program doesn't map exactly to what a program means in the theoretical sense. E.g. two Unix processes talking over a socket are not thought of as single Unix program, even though they can be considered a single theoretical program. So there is a tendency to think in 'processes' not 'systems'. I elaborated a little more about this elsewhere in this thread (https://news.ycombinator.com/item?id=15581591).
Re:Alan Kay on Lisp by xfer on Monday October 30, 2017 @12:59AM (#15583179)
But it has nothing to with typing, as typing means tying to a location in program, you can have processes communicating part of the same program, but the type-error will refer to a part of program and when the type-error is detected i.e. during execution of that part of program or some external part of program is what we are concerned here.

Example: You could think of an interpreter for a statically-typed language running various processes as the same program, but we still say the language is statically typed.

Re:Alan Kay on Lisp by shalabhc on Tuesday October 31, 2017 @03:35PM (#15595889)
> You could think of an interpreter for a statically-typed language running various processes as the same program, but we still say the language is statically typed.

Is it statically typed for cross process messages though?

Re:Alan Kay on Lisp by gnulinux on Saturday October 28, 2017 @03:12AM (#15574300)
There certainly is a fundamental difference between what programmers refer to as compile-time and runtime. Naming is probably problematic; but mathematically you cannot prove all the properties of a program just by looking at its syntax, in general. Because this implies a solution to the halting problem. In other words, there is no program, given your program, that can verify it; whereas, there exists a program, given an input and your program, that can verify that your program outputs the correct thing (as long as the language can be emulated by a Turing machine). When it comes to programming languages, the distinction can be trickier, since you can technically get a python program and statically analyze it. So, "compile" time and "run"time are not necessarily perfect words but they belong to the programming terminology. The more crucial thing is, there is a mathematical difference between those two.
Re:Alan Kay on Lisp by loup-vaillant on Saturday October 28, 2017 @06:35PM (#15577032)
> mathematically you cannot prove all the properties of a program just by looking at its syntax, in general.

A solution that is often overlooked is to simply shrink the set of legal programs. Simply typed lambda calculus for instance has a perfectly decidable halting problem (which is, programs written in it always halt).

There are 2 ways to handle undecidable properties with static analysis: either reject programs for which you can't prove the property holds (you will reject correct programs), or accept programs for which you can't prove it doesn't (you will accept incorrect programs, and may use runtime checks to compensate).

Rejecting correct programs is a problem only to the extent one would like to write such a program in the first place. Take this expression for instance:

  if 2 + 2 = 4
  then "Yay!"
  else 0
It is a perfectly fine expression, of type `string`. Most type systems will reject it however because the two branches of the conditional don't have the same type. Thing is, we don't care about this program in practice, since the constant test expression screams code smell to begin with.
Re:Alan Kay on Lisp by gnulinux on Monday October 30, 2017 @05:40AM (#15583887)
Yeah, but now you're arguing something else. Simply typed lambda calculus is not Turing-complete. With a Turing-complete language, you cannot decide the halting problem of an arbitrary sentence of that language. With a non-Turing-complete one, you potentially can. For example, Charity is one such non-Turing-complete language, for which, hypothetically, one can find an algorithm to decide halting of an arbitrary program. But most languages today are Turing-complete, because TC is a very easy property not to have, and it is very hard to construct non-TC but useful languages (eg, C++ metaprogramming is accidentally Turing complete, so is HTML+CSS). So, while what you explained is correct, it does not have direct implications on languages like Python, C++ etc. We still have different sort of properties while we're statically analyzing a TC language, and executing it with an input. This was what I was trying to explain.
Re:Alan Kay on Lisp by loup-vaillant on Monday October 30, 2017 @09:18AM (#15584769)
Being Turing complete doesn't mean you cannot prove anything without solving the halting problem. Programs have many potentially undecidable properties, and halting is only one of them. It's also one of the strongest.

It doesn't matter which property you are looking at. If it's undecideable, you can sidestep the issue by forbidding programs for which the checker is not sure.

That doesn't mean you have to lose Turing Completeness. You just have to chose properties that don't imply that the program halts. Static typing for instance doesn't mean the language isn't Turing Complete. Simply typed lambda calculus is the exception here.

Re:Alan Kay on Lisp by gnulinux on Monday October 30, 2017 @05:22PM (#15589015)
Where did I claim "you cannot prove anything without solving the halting problem" or "static typing means non Turing complete" exactly? I said nothing of this sort... IN TC languages you can prove some properties, but in general you cannot prove your program is correct. When I say in general, I mean exactly that. You keep bringing some specific cases where you can prove correctness, but that's beyond my point.

I sometimes workaround this by proving for "outputs the correct result, or loops forever". Here, you don't have to prove for halting, since your program is not expected to halt in some cases anyway. But then in some particular cases, you can prove that your algorithm is correct. You do not have to lose Turing-completeness to do this. But it gets trickier when you want to built a type system that can give all the bugs in your program, in general. You can definitely build something that finds all the bugs "for all intents and purposes" but not something that can be mathematically proven that will give you all of them. To be concrete, you can build a program, given arbitrary Python code, gives most of/all the bugs in this program. But you cannot build a program, given arbitrary Python code, that is proven that it will correctly know whether this program will output correct result for all possible inputs. You can do this for some restricted Python programs (as you've been arguing for last two comments) but in general you cannot do this, which brings us to this fundamental division.

Re:Alan Kay on Lisp by shalabhc on Friday October 27, 2017 @06:32PM (#15572744)
> It emerges from the underlying mathematics.

Which mathematics?

(Lisp has its own math, for instance.)

Re:Alan Kay on Lisp by Silfen on Friday October 27, 2017 @07:26PM (#15573063)
Very fundamental ideas around computability, or total vs partial functions. There are some correctness properties that we can prove without running the underlying program, such that we can always accept or reject a given program. None of this is particular to lisp.
Re:Alan Kay on Lisp by shalabhc on Sunday October 29, 2017 @05:44PM (#15581591)
Fundamental ideas about computability include the model of the Turing machine, which has no notion of types, verification, or even functions whatsoever - there are just too many degrees of freedom.

I agree there are correctness properties we can prove without running a 'program', but how do we map the notion of a 'program' into the real world. Is a single function a program? A single module which includes multiple functions? A single executable? A single system that includes multiple processes communicating over a network? I'm arguing each of these is a 'program' and a Turing machine in the theoretical sense. Each of these programs is hooked up to other 'programs' outside of it. 'Compilation' requires the input to be static, but if we think about how things are in flux (you can change a function, switch out a shared library or upgrade and restart a running process, etc.) when do you verify that a 'program' is 'correct'?

This is what I mean by 'compile time is made-up' - it falls out of the current frame of thinking of one OS process = one program = static set of source files. It is possible to design systems that have no notion of 'compile time'. You could still have verification, but it could be incremental and spread out all through the lifetime of the running system. So the system would have no 'compile phase' - it would be running live and as you update parts of it, the updated parts would integrate with the rest of the system and do verification like things.

Re:Alan Kay on Lisp by mjburgess on Friday October 27, 2017 @06:51PM (#15572869)
What on earth are you talking about?

> The internet is dynamically typed.

That's an incoherent claim.

Dynamic typing is where types belong to values. Static typing is where they apply to terms.

Really to call the former "typing" is misnomer. It's an abuse of the word "type" to mean "memory mode". It has not much relationship to typing in the logic/math/philosophy of logic sense in which types are sets and type relationships are those between sets.

It is the Curry-Howard isomorphism (https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...) which defines the correspondance between types in computer science and mathematics.

This is "static" only because the "dynamic" alternative isnt really an alternative at all, and really just a different kind of thing all together.

Re:Alan Kay on Lisp by dang on Friday October 27, 2017 @07:11PM (#15572994)
This crosses into incivility. That breaks the site guidelines. Please re-read them and don't do that when commenting here.

https://news.ycombinator.com/newsguidelines.html

Re:Alan Kay on Lisp by mjburgess on Friday October 27, 2017 @07:30PM (#15573080)
I'm not sure how this is incivil?

The claim is logically incoherent: typing cannot be a property of the internet, in the same way tuesday cannot be pink nor can addition sound terrifying.

The claim is a category error: the internet cannot posses such a property.

In addition, to say, of something, that it is " is a made up thing " is a degree of hubris that is presumably reasonably met by being perplexed at overconfidence of the claim posed with such little correct information.

Is being perplexed more uncivil than hubris? Are we really policing people's language to this minute degree?

Re:Alan Kay on Lisp by dang on Friday October 27, 2017 @09:15PM (#15573469)
"What on earth are you talking about" is uncivil. Your comment didn't need that.

Actually you broke this guideline as well: "Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize." It's possible that shalabhc intended to make a mathematical claim, but a stronger plausible interpretation is easy to come up with (e.g. "it's hard to enforce static guarantees across the software that interoperates on the internet").

The reason we ask people to follow this guideline is not so much that it's nicer, but that nitpicking things each other probably didn't say is tedious and detracts from good conversation, which is what we're really hoping for.

Re:Alan Kay on Lisp by loup-vaillant on Saturday October 28, 2017 @06:58AM (#15574698)
Static typing enables faster feedback loops. The kind of thing Bret Victor raves about.

In practice, I've been able to accomplish things with static typing that I hadn't the brainpower to do with dynamic typing, because even with a REPL, runtime errors came too late, and didn't meaningfully informed me of my mistakes.

As for why we switch to dynamic typing as we scale up, some of it probably has to do with trust. Computers communicating over the internet cannot trust each other, if they can even trust they are talking to one another to begin with. They have no choice but to perform lots of runtime checks to make sure they don't get pwned by the slightest remote mishap. Once you get to this point, static verifications become much less useful, and can often be skipped altogether.

Re:Alan Kay on Lisp by shalabhc on Sunday October 29, 2017 @05:16PM (#15581450)
> As for why we switch to dynamic typing as we scale up, some of it probably has to do with trust.

I'll note that we switch to 'dynamic' much before the question of trust arises. Whenever you do IPC between two OS processes you fully trust, communicate through a database or file, wire up a multi-process system with config files, etc. Most internal code at an organization is trusted, yet the communication between OS processes within an company uses dynamic messaging semantics.

I'll also point out that if you use a compiled shared library, or any system call you are forced to use the type system of C, which isn't particularly advanced.

It could be that we haven't developed dynamic messaging protocols that can bind safely and correctly. I'm arguing that if we have these, they might apply on a smaller scale too (objects within a 'process' or connections between shared libraries, etc.)

> Static typing enables faster feedback loops.

All of that only works on the small scale - where the type knowledge has to be fully shared within the entire program. As soon as you're writing code to call a service, static typing benefits are moot. The current solution is to create 'stubs', which doesn't scale well either. I am not arguing for 'dynamic typing everywhere', but rather about a different POV where we start looking at 'interconnections' at all levels the same way, and think about making the introspection and safe late binding in a standard, scalable way. Minimizing pre-shared knowledge would be one way to improve how this scales, for instance.

Re:Alan Kay on Lisp by loup-vaillant on Monday October 30, 2017 @04:04AM (#15583623)
> Most internal code at an organization is trusted,

It is not.

We trust our colleagues not to be malicious, but we generally don't trust them not to make mistakes. Hence defensive programming.

Re:Alan Kay on Lisp by shalabhc on Monday October 30, 2017 @12:45PM (#15586517)
The point is trust and typing seem orthogonal. E.g. I use static typing within one 'program' but 'dynamic' as soon as I split my program into two, even when the level of trust didn't change. Same thing when including my colleagues' code within my 'program' vs. calling it across program boundaries.

The point I'm trying to make is that 'static-typing style verification' which happens across different parts of a 'single program' doesn't extend to multiple programs or real systems. Maybe we should look at some kind of late bound dynamically bound verification - i.e. a protocol that is executed whenever one 'program' reaches out and connects to another, to determine if the connection is safe and correct. Do you think this has value?