4 ms·

>for example .NET’s LINQ cannot be expressed in LISP, not unless you add a static type system Doesn't that imply that Lisp, sans-static typing, is not Turing-C

by na85 8y ago

>for example .NET’s LINQ cannot be expressed in LISP, not unless you add a static type system Doesn't that imply that Lisp, sans-static typing, is not Turing-Complete? Surely that is not the case.

nine_k 8y ago
A Turing machine is Turing-complete. Good luck expressing LINQ syntax, or Lisp syntax, or even Basic-80 syntax on it. Syntax is important, it's a tool of thought.
- na85 8y ago
  I understood the post to which I replied to be arguing that LINQ could not be expressed in Lisp, not that Lisp doesn't have the correct syntax. Surely you can write LINQ in any Turing-complete language.
  - crabmusket 8y ago
    I guess the question you are begging is: how far can Lisp-LINQ go from the syntax, semantics, and ergonomics of C#'s LINQ before you stop calling it LINQ? Turing completeness doesn't describe expressivity of source code, as far as I understand it - it describes the ability to produce a desired outcome. So yes, you can perform the same operations LINQ allows, in Lisp or any other Turing-complete language. But can you do it while giving the programmer the same (or a similar enough) experience? From the .NET docs: > Language-integrated query allows query expressions to benefit from the rich metadata, compile-time syntax checking, static typing and IntelliSense that was previously available only to imperative code. Language-integrated query also allows a single general purpose declarative query facility to be applied to all in-memory information, not just information from external sources. Now, to be fair, I'm not sure you can express all that in Haskell either. And it could be reasonable to argue that a few of those benefits (e.g. intellisense) just _haven't_ been done for Lisp, not necessarily that they _can't_ be done.
- rs86 8y ago
  Syntax is different from abstraction. The problem in doing those things in turing machines and assembly is the low level of programming. Otherwise their syntax is pretty simple: commands and operands.
crimsonalucard 8y ago
https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis It's lambda complete. Which has been famously proven to be the same as turing complete. Also type checking is basically more or less putting restrictions on your code. If there is a language that doesn't have the syntax to compute certain things, how would restricting that language via type checking suddenly cause it to be able to compute everything and be turing complete? Makes no sense. To make a language change from not turing complete to turing complete you have to expand.. not restrict ... but expand it's computational ability. Again Type checking serves to restrict. Type checking is essentially just pre runtime special syntax for: define add (x,y) if type(x) != 'int' or type(y) != 'int': throw TypeError return x+2 or in a lisp like functional language: (define (int) (x) (if (equal? type(x) 'int') (x) (error 'Type Error')) (define add (x y)) (+ int(x) int(y))) It's not a big deal. I'm not sure what LINQ is, but you don't have to add a type checking system to a language to do type checking if you know what I mean. He doesn't know what he's talking about.
- rs86 8y ago
  Type checking is much more than that. It is not the same as throwing exceptions when types don't match; it is about proving that a type checked program will never produce type errors.
  - crimsonalucard 8y ago
    You're right. I wanted to illustrate that type checking shouldn't be a factor in the the parents context as you can use code to explicitly type check or prove it.
lomnakkus 8y ago
Of course not. You could always implement C# (static types and all) and LINQ atop Lisp, or indeed any other turing complete language.[1] The point of static type systems isn't that they add power -- it's that they take power away. Thus empowering the programmer to reason in a restricted subset of "all the possible things". [1] I'm ignoring the detail of there actually being a way to interface with the actual physical hardware, but I think we can assume that in any remotely practical TC language.

by na85 8y ago

>for example .NET’s LINQ cannot be expressed in LISP, not unless you add a static type system Doesn't that imply that Lisp, sans-static typing, is not Turing-Complete? Surely that is not the case.

nine_k 8y ago

A Turing machine is Turing-complete. Good luck expressing LINQ syntax, or Lisp syntax, or even Basic-80 syntax on it. Syntax is important, it's a tool of thought.

na85 8y ago
I understood the post to which I replied to be arguing that LINQ could not be expressed in Lisp, not that Lisp doesn't have the correct syntax. Surely you can write LINQ in any Turing-complete language.
- crabmusket 8y ago
  I guess the question you are begging is: how far can Lisp-LINQ go from the syntax, semantics, and ergonomics of C#'s LINQ before you stop calling it LINQ? Turing completeness doesn't describe expressivity of source code, as far as I understand it - it describes the ability to produce a desired outcome. So yes, you can perform the same operations LINQ allows, in Lisp or any other Turing-complete language. But can you do it while giving the programmer the same (or a similar enough) experience? From the .NET docs: > Language-integrated query allows query expressions to benefit from the rich metadata, compile-time syntax checking, static typing and IntelliSense that was previously available only to imperative code. Language-integrated query also allows a single general purpose declarative query facility to be applied to all in-memory information, not just information from external sources. Now, to be fair, I'm not sure you can express all that in Haskell either. And it could be reasonable to argue that a few of those benefits (e.g. intellisense) just _haven't_ been done for Lisp, not necessarily that they _can't_ be done.
rs86 8y ago
Syntax is different from abstraction. The problem in doing those things in turing machines and assembly is the low level of programming. Otherwise their syntax is pretty simple: commands and operands.

crimsonalucard 8y ago

https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis It's lambda complete. Which has been famously proven to be the same as turing complete. Also type checking is basically more or less putting restrictions on your code. If there is a language that doesn't have the syntax to compute certain things, how would restricting that language via type checking suddenly cause it to be able to compute everything and be turing complete? Makes no sense. To make a language change from not turing complete to turing complete you have to expand.. not restrict ... but expand it's computational ability. Again Type checking serves to restrict. Type checking is essentially just pre runtime special syntax for: define add (x,y) if type(x) != 'int' or type(y) != 'int': throw TypeError return x+2 or in a lisp like functional language: (define (int) (x) (if (equal? type(x) 'int') (x) (error 'Type Error')) (define add (x y)) (+ int(x) int(y))) It's not a big deal. I'm not sure what LINQ is, but you don't have to add a type checking system to a language to do type checking if you know what I mean. He doesn't know what he's talking about.

rs86 8y ago
Type checking is much more than that. It is not the same as throwing exceptions when types don't match; it is about proving that a type checked program will never produce type errors.
- crimsonalucard 8y ago
  You're right. I wanted to illustrate that type checking shouldn't be a factor in the the parents context as you can use code to explicitly type check or prove it.

lomnakkus 8y ago

Of course not. You could always implement C# (static types and all) and LINQ atop Lisp, or indeed any other turing complete language.[1] The point of static type systems isn't that they add power -- it's that they take power away. Thus empowering the programmer to reason in a restricted subset of "all the possible things". [1] I'm ignoring the detail of there actually being a way to interface with the actual physical hardware, but I think we can assume that in any remotely practical TC language.