This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Is Scala's type system turing complete?

41 replies
Bill Venners
Joined: 2008-12-18,
User offline. Last seen 31 weeks 5 days ago.

Hi,

Steven Colbourne mentioned in an interview that he heard Scala's type
system is Turing complete. Actually what he said was that he'd heard
"you can make a turing complete language within the generics of
Scala." I've heard that about C++ templates, but never about Scala.
Does anyone know if that's a true statement?

Thanks.

Bill
----
Bill Venners
Artima, Inc.
http://www.artima.com

Richard Wallace
Joined: 2009-07-14,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?

A very interesting series of blog posts about this subject can be
found at http://apocalisp.wordpress.com/2010/06/08/type-level-programming-in-scala/

So it does seem that the type system is turing complete.

Rich

On Thu, Sep 23, 2010 at 12:54 PM, Bill Venners wrote:
> Hi,
>
> Steven Colbourne mentioned in an interview that he heard Scala's type
> system is Turing complete. Actually what he said was that he'd heard
> "you can make a turing complete language within the generics of
> Scala." I've heard that about C++ templates, but never about Scala.
> Does anyone know if that's a true statement?
>
> Thanks.
>
> Bill
> ----
> Bill Venners
> Artima, Inc.
> http://www.artima.com
>

Luc Duponcheel
Joined: 2008-12-19,
User offline. Last seen 34 weeks 3 days ago.
Re: Is Scala's type system turing complete?
Bill,

... for what it is worth ...

would that not imply that it is possible
to write a Scala program for which the type
inferencer execution does not terminate
(an undesirable property)

Luc

On Thu, Sep 23, 2010 at 9:54 PM, Bill Venners <bill [at] artima [dot] com> wrote:
Hi,

Steven Colbourne mentioned in an interview that he heard Scala's type
system is Turing complete. Actually what he said was that he'd heard
"you can make a turing complete language within the generics of
Scala." I've heard that about C++ templates, but never about Scala.
Does anyone know if that's a true statement?

Thanks.

Bill
----
Bill Venners
Artima, Inc.
http://www.artima.com



--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination

dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Is Scala's type system turing complete?
Yes, and the blog post about SKI calculus in Scala that I posted has such an example.

On Thu, Sep 23, 2010 at 17:12, Luc Duponcheel <luc [dot] duponcheel [at] gmail [dot] com> wrote:
Bill,

... for what it is worth ...

would that not imply that it is possible
to write a Scala program for which the type
inferencer execution does not terminate
(an undesirable property)

Luc

On Thu, Sep 23, 2010 at 9:54 PM, Bill Venners <bill [at] artima [dot] com> wrote:
Hi,

Steven Colbourne mentioned in an interview that he heard Scala's type
system is Turing complete. Actually what he said was that he'd heard
"you can make a turing complete language within the generics of
Scala." I've heard that about C++ templates, but never about Scala.
Does anyone know if that's a true statement?

Thanks.

Bill
----
Bill Venners
Artima, Inc.
http://www.artima.com



--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination




--
Daniel C. Sobral

I travel to the future all the time.
Raoul Duke
Joined: 2009-01-05,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?

On Thu, Sep 23, 2010 at 1:12 PM, Luc Duponcheel
wrote:
> would that not imply that it is possible
> to write a Scala program for which the type
> inferencer execution does not terminate
> (an undesirable property)

what is desirable is entirely context-sensitive / subjective; the
power to do cool things leads to the power to inf. loop for example,
whereas saying "we'll make sure to not allow inf. loops" means you end
up with a system that constrains you more than you probably will
really like.

sincerely.

Luc Duponcheel
Joined: 2008-12-19,
User offline. Last seen 34 weeks 3 days ago.
Re: Is Scala's type system turing complete?
Daniel,

do you mean an example where the type inferencer does not terminate?

btw: I fully agree with Raoul's remark, but a non terminating type
inferencing session is, well, maybe not what the average programmer
would be very happy with

ps: I'll have a look at Daniel's blog post asap

Luc

On Thu, Sep 23, 2010 at 10:18 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
Yes, and the blog post about SKI calculus in Scala that I posted has such an example.

On Thu, Sep 23, 2010 at 17:12, Luc Duponcheel <luc [dot] duponcheel [at] gmail [dot] com> wrote:
Bill,

... for what it is worth ...

would that not imply that it is possible
to write a Scala program for which the type
inferencer execution does not terminate
(an undesirable property)

Luc

On Thu, Sep 23, 2010 at 9:54 PM, Bill Venners <bill [at] artima [dot] com> wrote:
Hi,

Steven Colbourne mentioned in an interview that he heard Scala's type
system is Turing complete. Actually what he said was that he'd heard
"you can make a turing complete language within the generics of
Scala." I've heard that about C++ templates, but never about Scala.
Does anyone know if that's a true statement?

Thanks.

Bill
----
Bill Venners
Artima, Inc.
http://www.artima.com



--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination




--
Daniel C. Sobral

I travel to the future all the time.



--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination

Bill Venners
Joined: 2008-12-18,
User offline. Last seen 31 weeks 5 days ago.
Re: Is Scala's type system turing complete?

Hi All,

Thanks everybody for the responses. I published what Stephen said.
Didn't want to if it was in error.

He thinks Scala is too complicated to be the next big language, but a
bit surprisingly to me, he felt Fantom may be too simple to be the
next big language:

http://www.artima.com/lejava/articles/javaone_2010_the_next_big_jvm_lang...

Like Goldilocks, he's looking for a language that's "juuuust right."

Bill

On Thu, Sep 23, 2010 at 1:18 PM, Daniel Sobral wrote:
> Yes, and the blog post about SKI calculus in Scala that I posted has such an
> example.
>
> On Thu, Sep 23, 2010 at 17:12, Luc Duponcheel
> wrote:
>>
>> Bill,
>>
>> ... for what it is worth ...
>>
>> would that not imply that it is possible
>> to write a Scala program for which the type
>> inferencer execution does not terminate
>> (an undesirable property)
>>
>> Luc
>>
>> On Thu, Sep 23, 2010 at 9:54 PM, Bill Venners wrote:
>>>
>>> Hi,
>>>
>>> Steven Colbourne mentioned in an interview that he heard Scala's type
>>> system is Turing complete. Actually what he said was that he'd heard
>>> "you can make a turing complete language within the generics of
>>> Scala." I've heard that about C++ templates, but never about Scala.
>>> Does anyone know if that's a true statement?
>>>
>>> Thanks.
>>>
>>> Bill
>>> ----
>>> Bill Venners
>>> Artima, Inc.
>>> http://www.artima.com
>>
>>
>>
>> --
>>    __~O
>>   -\ <,
>> (*)/ (*)
>>
>> reality goes far beyond imagination
>>
>
>
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.
>

Alex Cruise
Joined: 2008-12-17,
User offline. Last seen 2 years 26 weeks ago.
Re: Is Scala's type system turing complete?
On Thu, Sep 23, 2010 at 1:33 PM, Bill Venners <bill [at] artima [dot] com> wrote:
... but a bit surprisingly to me, he felt Fantom may be too simple to be the next big language:

No user-defined generics?  Too simple.
http://fantom.org/doc/docLang/TypeSystem.html#generics
-0xe1a
dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Is Scala's type system turing complete?
Yes, and it is not _my_ post. I meant the e-mail I posted had a link to a blog post about it. :-)

Anyway, yes, it stops on stack overflow. There's no overwriting types or tail-recursion optimizations :-), so any infinite code is bound to stack overflow. I think. :-)

On Thu, Sep 23, 2010 at 17:31, Luc Duponcheel <luc [dot] duponcheel [at] gmail [dot] com> wrote:
Daniel,

do you mean an example where the type inferencer does not terminate?

btw: I fully agree with Raoul's remark, but a non terminating type
inferencing session is, well, maybe not what the average programmer
would be very happy with

ps: I'll have a look at Daniel's blog post asap

Luc

On Thu, Sep 23, 2010 at 10:18 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
Yes, and the blog post about SKI calculus in Scala that I posted has such an example.

On Thu, Sep 23, 2010 at 17:12, Luc Duponcheel <luc [dot] duponcheel [at] gmail [dot] com> wrote:
Bill,

... for what it is worth ...

would that not imply that it is possible
to write a Scala program for which the type
inferencer execution does not terminate
(an undesirable property)

Luc

On Thu, Sep 23, 2010 at 9:54 PM, Bill Venners <bill [at] artima [dot] com> wrote:
Hi,

Steven Colbourne mentioned in an interview that he heard Scala's type
system is Turing complete. Actually what he said was that he'd heard
"you can make a turing complete language within the generics of
Scala." I've heard that about C++ templates, but never about Scala.
Does anyone know if that's a true statement?

Thanks.

Bill
----
Bill Venners
Artima, Inc.
http://www.artima.com



--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination




--
Daniel C. Sobral

I travel to the future all the time.



--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination




--
Daniel C. Sobral

I travel to the future all the time.
milessabin
Joined: 2008-08-11,
User offline. Last seen 33 weeks 3 days ago.
Re: Is Scala's type system turing complete?

On Thu, Sep 23, 2010 at 9:12 PM, Luc Duponcheel
wrote:
> ... for what it is worth ...
>
> would that not imply that it is possible
> to write a Scala program for which the type
> inferencer execution does not terminate
> (an undesirable property)

Expressive power, decidability ... pick one ...

Cheers,

Miles

Jesper Nordenberg
Joined: 2008-12-27,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?

C++ compilers typically solve that problem by simply specifying a limit
on the depth of the type "stack". I think it works well in practice.

/Jesper Nordenberg

Luc Duponcheel skrev 2010-09-23 22:31:
> Daniel,
>
> do you mean an example where the type inferencer does not terminate?
>
> btw: I fully agree with Raoul's remark, but a non terminating type
> inferencing session is, well, maybe not what the average programmer
> would be very happy with
>
> ps: I'll have a look at Daniel's blog post asap
>
> Luc
>
> On Thu, Sep 23, 2010 at 10:18 PM, Daniel Sobral
> > wrote:
>
> Yes, and the blog post about SKI calculus in Scala that I posted has
> such an example.
>
>
> On Thu, Sep 23, 2010 at 17:12, Luc Duponcheel
> > wrote:
>
> Bill,
>
> ... for what it is worth ...
>
> would that not imply that it is possible
> to write a Scala program for which the type
> inferencer execution does not terminate
> (an undesirable property)
>
> Luc
>
>
> On Thu, Sep 23, 2010 at 9:54 PM, Bill Venners
> > wrote:
>
> Hi,
>
> Steven Colbourne mentioned in an interview that he heard
> Scala's type
> system is Turing complete. Actually what he said was that
> he'd heard
> "you can make a turing complete language within the generics of
> Scala." I've heard that about C++ templates, but never about
> Scala.
> Does anyone know if that's a true statement?
>
> Thanks.
>
> Bill
> ----
> Bill Venners
> Artima, Inc.
> http://www.artima.com
>
>
>
>
> --
> __~O
> -\ <,
> (*)/ (*)
>
> reality goes far beyond imagination
>
>
>
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.
>
>
>
>
> --
> __~O
> -\ <,
> (*)/ (*)
>
> reality goes far beyond imagination
>

Meredith Gregory
Joined: 2008-12-17,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?
Dear Miles,
You're such a spoil-sport! Can't i have both? ;-) 
More seriously, i think there's actually quite a bit of territory in between; and before i ever heard about pluggable types i dreamed of a combinatorial type system where we knew which subsets of the combinators gave which expressive power. As mental model (but at the object language -- not type language level), Nobuko Yoshida developed a set of combinators for the asynchronous π-calculus and in a beautiful paper, Minimality and Separation Results on Asynchronous Mobile Processes, was able to identify the notion of "basis" (subsets of combinators recovering the expressive power of the full calculus) and minimal bases. 
The reason this example is relevant is that most proofs of Turing completeness of such and such type system of such and such a functional language is that the proofs usually involve an encoding of a combinator-based presentation of a Turing-complete language. Yoshida's combinators are just another set of combinators for yet another Turing-complete language. Yet, Yoshida's combinators are quite intriguing as they deal at a level much lower than SKI -- a level that enables fascinating insight into resource utilization, but i digress.
i used to envision a frontend tool with radio buttons besides combinators that would enable developers to select exactly which combinators were part of the type system. This would enable them to dial up a type system to express and check certain properties and not others. If the type system got too expressive, there would be expressible properties for which the type-check would never return. On the other side, as they weakened the type system (and got decidable type-checks) there would be properties the types could never see (couldn't express).
This vision is certainly feasible, actually. We know for a fact that the following encodings exist
  • SKI -> lambda calculus
  • lambda calculus -> π-calculus
  • π-calculus -> Yoshida's combinators
So, we know that you could -- in principle and in practice -- find a Scala type system encoding of Yoshida's combinators -- which do enjoy these separation theorems about the subsets of combinators. The rub would be to relate the combinator expressiveness to Scala execution. Much more interesting would be to find a set of combinators that closely matched Scala execution.
Finding reasonable combinator sets seems to be a bit of an art. i'm heartened by the Leifer-Milner theorems. They relate rewrites to equivalences in just the right sort of way to enable a better handle on a combinator set that matched the computational model at hand.
Best wishes,
--greg

On Thu, Sep 23, 2010 at 2:50 PM, Miles Sabin <miles [at] milessabin [dot] com> wrote:
On Thu, Sep 23, 2010 at 9:12 PM, Luc Duponcheel
<luc [dot] duponcheel [at] gmail [dot] com> wrote:
> ... for what it is worth ...
>
> would that not imply that it is possible
> to write a Scala program for which the type
> inferencer execution does not terminate
> (an undesirable property)

Expressive power, decidability ... pick one ...

Cheers,


Miles

--
Miles Sabin
tel: +44 7813 944 528
gtalk: miles [at] milessabin [dot] com
skype: milessabin
http://www.chuusai.com/
http://twitter.com/milessabin



--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com
Razvan Cojocaru 3
Joined: 2010-07-28,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?

Well, I can agree that scala is complicated...after several years, I still
manage to shoot myself in the foot and use the lovely REPL to unwind some
type declarations until they compile and more importantly, make sense ...but
then I often feel gung-ho and can type faster than I think :)

I had started work to define a subset of scala for "every-day use": In large
teams of Java developers moving to scala, you don't want them all to start
messing with operators, implicits etc. The other, more complicated parts
would be accessible to "library builders", which need the full expressive
power to make it easier for the rest of us.

This set of restrictions should be easy to configure into a tool like
FindBugs or a compiler plugin or similar.

That work really got nowhere... so far :) but I think it's really what's
needed to put a lot of these fears to rest.

While we're on the subject, Martin's piece on complexity is great!
http://lamp.epfl.ch/~odersky/blogs/isscalacomplex.html

cheers,
Razie

-----
Razvan Cojocaru,
Work: http://www.sigma-systems.com
Playground: http://wiki.homecloud.ca
Latest cool toys: http://scripster.razie.com Scripster and
http://github.com/razie/gremlins Gremlins
Follow me: http://feeds.razie.com/RazvanTech RSS Feed ,
http://twitter.com/razie Twitter , http://github.com/razie GitHub .

Rob Dickens 3
Joined: 2010-06-17,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Is Scala's type system turing complete?

In his blog entry [1], Stephen asks, 'does writing a programming
language [Scala] in the generics of another programming language
[Java] really make sense?!!'

Isn't the assertion (underlying the question) just wrong?

In which case, I don't think he's really qualified to judge whether
Scala is too complicated or not.

1 http://www.dzone.com/links/next_big_jvm_language_backwards_incompatible_...

On Fri, Sep 24, 2010 at 4:58 AM, Razvan Cojocaru-2 wrote:
>
> Well, I can agree that scala is complicated...after several years, I still
> manage to shoot myself in the foot and use the lovely REPL to unwind some
> type declarations until they compile and more importantly, make sense ...but
> then I often feel gung-ho and can type faster than I think :)
>
> I had started work to define a subset of scala for "every-day use": In large
> teams of Java developers moving to scala, you don't want them all to start
> messing with operators, implicits etc. The other, more complicated parts
> would be accessible to "library builders", which need the full expressive
> power to make it easier for the rest of us.
>
> This set of restrictions should be easy to configure into a tool like
> FindBugs or a compiler plugin or similar.
>
> That work really got nowhere... so far :) but I think it's really what's
> needed to put a lot of these fears to rest.
>
> While we're on the subject, Martin's piece on complexity is great!
> http://lamp.epfl.ch/~odersky/blogs/isscalacomplex.html
>
> cheers,
> Razie
>
> -----
> Razvan Cojocaru,
> Work: http://www.sigma-systems.com
> Playground: http://wiki.homecloud.ca
> Latest cool toys:  http://scripster.razie.com Scripster  and
> http://github.com/razie/gremlins Gremlins
> Follow me:  http://feeds.razie.com/RazvanTech RSS Feed ,
> http://twitter.com/razie Twitter ,  http://github.com/razie GitHub .
>
> --
> View this message in context: http://scala-programming-language.1934581.n4.nabble.com/Is-Scala-s-type-...
> Sent from the Scala - User mailing list archive at Nabble.com.
>

adriaanm
Joined: 2010-02-08,
User offline. Last seen 31 weeks 4 days ago.
Re: Re: Is Scala's type system turing complete?
Hi,

On Fri, Sep 24, 2010 at 10:12 AM, Rob Dickens <robcdickens [at] gmail [dot] com> wrote:
In his blog entry [1], Stephen asks, 'does writing a programming
language [Scala] in the generics of another programming language
[Java] really make sense?!!'
There's a lot of FUD in that article and the comments (the one from the Nutter guy is especially amusing)
However, I think the question is valid (spoiler alert: the answer is "yes, of course"). I read it as:
 'does writing a programming language [X] in the generics of another programming language [Scala] really make sense?!!'
where X could be any language you'd want to implement at Scala's type level. Of course, the question could be even more general:
"does programming at the type-level in Scala make sense?"
yes, why yes it does, thank you for asking! -- that's exactly how the 2.8 collections tell the type checker that mapping an int => int function over a bitset gives you another bitset, whereas mapping a function that produces values of type T will get you a Set[T]
these ideas have applications in many libraries (e.g., to give more precise types to the parser combinators), and more generally, we see it as a necessary complement to developing any sufficiently advanced embedded DSL -- you can already describe your domain language's run-time semantics in Scala -- why not its type system?
Of course, you probably shouldn't write non-terminating programs at the type level (in fact, I would consider it a bug if you managed to make the type checker loop -- or, more likely, overflow the stack), but our research hypothesis is that you should be allowed to write quite expressive programs, without the type checker getting in your way if it can't be sure that what you wrote will terminate. 
This may sound scary, but we're here to help! One of our research projects is developing a type debugger, which gives you much more help than what any language currently has to offer when it comes to type error messages. In the state of the art, they are like 1-line stack traces (using a run-time metaphor). In complex cases, it would be nice to be able to step through the type checker's decision-tree to see what exactly caused your type error? You'd see all inferred types, the implicits that were considered,...
I'd love to hear your ideas about this, but this is probably more a scala-debate thing until this type-level future has become the everyday present.
cheersadriaan
Philippe Lhoste
Joined: 2010-09-02,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?

On 24/09/2010 05:58, Razvan Cojocaru-2 wrote:
> Well, I can agree that scala is complicated...

Yes and no...
I don't know if the same distinction exists in English, but in my youth, I learned the
difference (in French) between complicated and complex.
Complicated implies somebody is looking for difficulty, not doing simple things on
purpose, with an idea of confusion and unnecessary hard to understand concepts.
Complex implies something hard to understand, with lot of parts that is difficult to
grasp, but with an idea of organization and logic.

I don't mean to give a lesson on semantics, but as a newbie, I first found Scala to be
complicated (some incantations seems unreadable, near line noise), then, starting to learn
it seriously, I find it simpler than I thought and overall quite readable.
... Except for the type system, which is indeed very complex, even more as some texts
assume familiarity with the theory of types and intimate knowledge of terms like
covariance and contravariance....
Thus, I found the first part of the Scala Overview
very clear and illuminating the
deep consistency behind the cool syntax sugar presented by tutorials... and the second
part totally unreadable for somebody not used to programming language theory and FP
concepts! (but I will come back to it after a while).

So, my feeling is that Scala is quite simple to use, the 'case class' is a joy for a Java
programmer, it allows to express code in a simple and terse yet readable (if carefully
written) way. Yet it can be very complex (ie. hard to understand but with a deep logic
behind) if one must dig into the type system to make generic, re-usable components.

That's actually what you (and Martin) wrote, just expressed in my own (clumsy) words, from
a beginner's point of view.

Your idea is intriguing / interesting, although I am not sure if it is really usable.
Somehow, a beginner will just stay away from making complex (or complicated...) stuff,
just making simple classes and trying to chain some functions.

Note: there is still some difficulty from the doc/API itself, as it exposes this type
system. I found a blog article using flatMap and when I wanted to understand what it does,
I find:

def flatMap [B, That] (f: (A) ⇒ Traversable[B])(implicit bf: CanBuildFrom[List[A], B,
That]) : That
Builds a new collection by applying a function to all elements of this list and
concatenating the results.

What results? How it differs from the simple map()? ("Builds a new collection by applying
a function to all elements of this list.")
I think I (vaguely) understood the difference, but it is far from obvious and the doc
seems to be more aimed at specialists than at newbies...

Luc Duponcheel
Joined: 2008-12-19,
User offline. Last seen 34 weeks 3 days ago.
Re: Is Scala's type system turing complete?
good point Philippe

by the way:

I usually make the distinction between difficult (versus easy) and complex (versus simple).
In general, there is no relationship whatsoever between the concepts*, but,
 o complex thinks seem to be difficult, and
 o implementing difficult things may require a certain amount of complexity

* I can imagine three simple axioms and a difficult theorem to prove based upon them

As for your remark on the API-doc itself, as it exposes this type system

recently I posted this fibs program

I looked at the API, and found two useful methods in Iterable
def zip[B](that: Iterable[B]): Iterable[(A, B)] def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: CanBuildFrom[Iterable[A], (A1, B), That]): That I considered using them for fibs

The advantage of the first one is that it looks easier, but it gives you a tuple of type (Int,Int)
rather than an Int (so I had to sum the tuples) ending up with the sub-optimal
val fibs: Stream[Int] = 1 #:: 1 #:: (for { (x, y) <- fibs.zip(fibs.tail) } yield x+y)

so, I considered a few moments to use the second one, since, with the help of
an implicit buddy, I could have the flexibility to obtain an Int directly

well (and I have to agree, I did not look at it for a long time, because, for a living, I have
other things on my head) I did not manage to find a solution immediately and I gave up

... this complexity could be frustrating for some programmers ...

btw: anyone having more time to use the second one together with an implicit,
I'm sure it's possible (and I could find a solution myself if only I had the time)


Luc

---------- Forwarded message ----------
From: Philippe Lhoste <PhiLho [at] gmx [dot] net>
Date: Fri, Sep 24, 2010 at 10:55 AM
Subject: [scala-user] Re: Is Scala's type system turing complete?
To: scala-user [at] listes [dot] epfl [dot] ch


On 24/09/2010 05:58, Razvan Cojocaru-2 wrote:
Well, I can agree that scala is complicated...

Yes and no...
I don't know if the same distinction exists in English, but in my youth, I learned the difference (in French) between complicated and complex.
Complicated implies somebody is looking for difficulty, not doing simple things on purpose, with an idea of confusion and unnecessary hard to understand concepts.
Complex implies something hard to understand, with lot of parts that is difficult to grasp, but with an idea of organization and logic.

I don't mean to give a lesson on semantics, but as a newbie, I first found Scala to be complicated (some incantations seems unreadable, near line noise), then, starting to learn it seriously, I find it simpler than I thought and overall quite readable.
... Except for the type system, which is indeed very complex, even more as some texts assume familiarity with the theory of types and intimate knowledge of terms like covariance and contravariance....
Thus, I found the first part of the Scala Overview <http://www.scala-lang.org/docu/files/ScalaOverview.pdf> very clear and illuminating the deep consistency behind the cool syntax sugar presented by tutorials... and the second part totally unreadable for somebody not used to programming language theory and FP concepts! (but I will come back to it after a while).

So, my feeling is that Scala is quite simple to use, the 'case class' is a joy for a Java programmer, it allows to express code in a simple and terse yet readable (if carefully written) way. Yet it can be very complex (ie. hard to understand but with a deep logic behind) if one must dig into the type system to make generic, re-usable components.


That's actually what you (and Martin) wrote, just expressed in my own (clumsy) words, from a beginner's point of view.

Your idea is intriguing / interesting, although I am not sure if it is really usable. Somehow, a beginner will just stay away from making complex (or complicated...) stuff, just making simple classes and trying to chain some functions.

Note: there is still some difficulty from the doc/API itself, as it exposes this type system. I found a blog article using flatMap and when I wanted to understand what it does, I find:

def   flatMap  [B, That]  (f: (A) ⇒ Traversable[B])(implicit bf: CanBuildFrom[List[A], B, That])  : That
Builds a new collection by applying a function to all elements of this list and concatenating the results.

What results? How it differs from the simple map()? ("Builds a new collection by applying a function to all elements of this list.")
I think I (vaguely) understood the difference, but it is far from obvious and the doc seems to be more aimed at specialists than at newbies...

Maxime Lévesque
Joined: 2009-08-18,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Is Scala's type system turing complete?

The way I like to see it is that the optimal complexity of a solution (the one with the minimal complexity) is lower
bounded by the inherent complexity of the problem, the delta between the two is the "complexification".

So the "simplicity" of a given language must be avaluated against different (complexity) levels of problems to be fair.
My impression is that the occasional Guru that dismisses Scala as being too complex fails to do this.


Max

On Fri, Sep 24, 2010 at 4:55 AM, Philippe Lhoste <PhiLho [at] gmx [dot] net> wrote:
On 24/09/2010 05:58, Razvan Cojocaru-2 wrote:
Well, I can agree that scala is complicated...

Yes and no...
I don't know if the same distinction exists in English, but in my youth, I learned the difference (in French) between complicated and complex.
Complicated implies somebody is looking for difficulty, not doing simple things on purpose, with an idea of confusion and unnecessary hard to understand concepts.
Complex implies something hard to understand, with lot of parts that is difficult to grasp, but with an idea of organization and logic.

I don't mean to give a lesson on semantics, but as a newbie, I first found Scala to be complicated (some incantations seems unreadable, near line noise), then, starting to learn it seriously, I find it simpler than I thought and overall quite readable.
... Except for the type system, which is indeed very complex, even more as some texts assume familiarity with the theory of types and intimate knowledge of terms like covariance and contravariance....
Thus, I found the first part of the Scala Overview <http://www.scala-lang.org/docu/files/ScalaOverview.pdf> very clear and illuminating the deep consistency behind the cool syntax sugar presented by tutorials... and the second part totally unreadable for somebody not used to programming language theory and FP concepts! (but I will come back to it after a while).

So, my feeling is that Scala is quite simple to use, the 'case class' is a joy for a Java programmer, it allows to express code in a simple and terse yet readable (if carefully written) way. Yet it can be very complex (ie. hard to understand but with a deep logic behind) if one must dig into the type system to make generic, re-usable components.


That's actually what you (and Martin) wrote, just expressed in my own (clumsy) words, from a beginner's point of view.

Your idea is intriguing / interesting, although I am not sure if it is really usable. Somehow, a beginner will just stay away from making complex (or complicated...) stuff, just making simple classes and trying to chain some functions.

Note: there is still some difficulty from the doc/API itself, as it exposes this type system. I found a blog article using flatMap and when I wanted to understand what it does, I find:

def   flatMap  [B, That]  (f: (A) ⇒ Traversable[B])(implicit bf: CanBuildFrom[List[A], B, That])  : That
Builds a new collection by applying a function to all elements of this list and concatenating the results.

What results? How it differs from the simple map()? ("Builds a new collection by applying a function to all elements of this list.")
I think I (vaguely) understood the difference, but it is far from obvious and the doc seems to be more aimed at specialists than at newbies...

Luc Duponcheel
Joined: 2008-12-19,
User offline. Last seen 34 weeks 3 days ago.
Re: Re: Is Scala's type system turing complete?
indeed, Max, imho the art of software engineering is to constrain "complexification"



2010/9/24 Maxime Lévesque <maxime [dot] levesque [at] gmail [dot] com>

The way I like to see it is that the optimal complexity of a solution (the one with the minimal complexity) is lower
bounded by the inherent complexity of the problem, the delta between the two is the "complexification".

So the "simplicity" of a given language must be avaluated against different (complexity) levels of problems to be fair.
My impression is that the occasional Guru that dismisses Scala as being too complex fails to do this.


Max

On Fri, Sep 24, 2010 at 4:55 AM, Philippe Lhoste <PhiLho [at] gmx [dot] net> wrote:
On 24/09/2010 05:58, Razvan Cojocaru-2 wrote:
Well, I can agree that scala is complicated...

Yes and no...
I don't know if the same distinction exists in English, but in my youth, I learned the difference (in French) between complicated and complex.
Complicated implies somebody is looking for difficulty, not doing simple things on purpose, with an idea of confusion and unnecessary hard to understand concepts.
Complex implies something hard to understand, with lot of parts that is difficult to grasp, but with an idea of organization and logic.

I don't mean to give a lesson on semantics, but as a newbie, I first found Scala to be complicated (some incantations seems unreadable, near line noise), then, starting to learn it seriously, I find it simpler than I thought and overall quite readable.
... Except for the type system, which is indeed very complex, even more as some texts assume familiarity with the theory of types and intimate knowledge of terms like covariance and contravariance....
Thus, I found the first part of the Scala Overview <http://www.scala-lang.org/docu/files/ScalaOverview.pdf> very clear and illuminating the deep consistency behind the cool syntax sugar presented by tutorials... and the second part totally unreadable for somebody not used to programming language theory and FP concepts! (but I will come back to it after a while).

So, my feeling is that Scala is quite simple to use, the 'case class' is a joy for a Java programmer, it allows to express code in a simple and terse yet readable (if carefully written) way. Yet it can be very complex (ie. hard to understand but with a deep logic behind) if one must dig into the type system to make generic, re-usable components.


That's actually what you (and Martin) wrote, just expressed in my own (clumsy) words, from a beginner's point of view.

Your idea is intriguing / interesting, although I am not sure if it is really usable. Somehow, a beginner will just stay away from making complex (or complicated...) stuff, just making simple classes and trying to chain some functions.

Note: there is still some difficulty from the doc/API itself, as it exposes this type system. I found a blog article using flatMap and when I wanted to understand what it does, I find:

def   flatMap  [B, That]  (f: (A) ⇒ Traversable[B])(implicit bf: CanBuildFrom[List[A], B, That])  : That
Builds a new collection by applying a function to all elements of this list and concatenating the results.

What results? How it differs from the simple map()? ("Builds a new collection by applying a function to all elements of this list.")
I think I (vaguely) understood the difference, but it is far from obvious and the doc seems to be more aimed at specialists than at newbies...

Aydjen
Joined: 2009-08-21,
User offline. Last seen 1 year 28 weeks ago.
Re: Is Scala's type system turing complete?

Hi,

Bill Venners wrote:
> He thinks Scala is too complicated to be the next big language,

I don't know if that's even a valid argument. C++ is a very complicated language and still it is on rank 3 in the Tiobe index, with young people still learning it.

For the record, I consider myself an average programmer and I don't find Scala too complex nor too complicated to do everyday work with it.

Andreas

Luc Duponcheel
Joined: 2008-12-19,
User offline. Last seen 34 weeks 3 days ago.
Re: Is Scala's type system turing complete?
Andreas,

I do not want to play the devil's advocate here,
but, have you never been confronted,
even when doing everyday work,
with type inferencer complexity that was not
immediately clear to deal with?

I have to confess that
I sometimes have been confronted with complex
(and slightly confusing) error messages ; agreed
I typically use Scala for more experimental stuff.

On the other hand, when implementing a web application
using Lift, I rarely ran into Scala complexity. It looks as
if a good framework (and rules on how to use it) can avoid
all this.

btw: the (unfinished, because no time to incorporate
brand new stuff to (indeed (!)) reduce complexity
(avoiding templating boilerplate)) project is at
http://github.com/LucDupAtGitHub/GroceryShop
[ it has nothing to do with Grocery, it deals with general products ]

Luc

On Fri, Sep 24, 2010 at 1:22 PM, Andreas Flierl <andreas [at] flierl [dot] eu> wrote:
Hi,

Bill Venners wrote:
> He thinks Scala is too complicated to be the next big language,

I don't know if that's even a valid argument. C++ is a very complicated language and still it is on rank 3 in the Tiobe index, with young people still learning it.

For the record, I consider myself an average programmer and I don't find Scala too complex nor too complicated to do everyday work with it.

Andreas



--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination

Maxime Lévesque
Joined: 2009-08-18,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?

 You hit a crucial point here : can the complexity be hidden in libraries ?

It is often said that Scala is only as complex as one's usage of it,
I think this is "potentially true", i.e. it will become true if the ecosystem can breed
enough libraries and DSLs to allow "programmers with deadlines ...and managers on their backs"
(I prefer this phrasing to "everyday programmer") to not be *required* to dive
into the complexity. I think the potential is very real, that we're not there yet,
but the momentum and the competence in the community is there. Of course
there are many things that could go wrong on the way there.

 Max

On Fri, Sep 24, 2010 at 7:32 AM, Luc Duponcheel <luc [dot] duponcheel [at] gmail [dot] com> wrote:
Andreas,

I do not want to play the devil's advocate here,
but, have you never been confronted,
even when doing everyday work,
with type inferencer complexity that was not
immediately clear to deal with?

I have to confess that
I sometimes have been confronted with complex
(and slightly confusing) error messages ; agreed
I typically use Scala for more experimental stuff.

On the other hand, when implementing a web application
using Lift, I rarely ran into Scala complexity. It looks as
if a good framework (and rules on how to use it) can avoid
all this.

btw: the (unfinished, because no time to incorporate
brand new stuff to (indeed (!)) reduce complexity
(avoiding templating boilerplate)) project is at
http://github.com/LucDupAtGitHub/GroceryShop
[ it has nothing to do with Grocery, it deals with general products ]

Luc

On Fri, Sep 24, 2010 at 1:22 PM, Andreas Flierl <andreas [at] flierl [dot] eu> wrote:
Hi,

Bill Venners wrote:
> He thinks Scala is too complicated to be the next big language,

I don't know if that's even a valid argument. C++ is a very complicated language and still it is on rank 3 in the Tiobe index, with young people still learning it.

For the record, I consider myself an average programmer and I don't find Scala too complex nor too complicated to do everyday work with it.

Andreas



--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination


Aydjen
Joined: 2009-08-21,
User offline. Last seen 1 year 28 weeks ago.
Re: Is Scala's type system turing complete?

Luc,

of course, from time to time, I run into stuff that is not immediately clear how to deal with. This happens (or happened) to me in virtually any language I use or used. I remember when generics came to Java. It was uncharted territory for the programmers I knew and also for me. Lots of issues with the use-site variance and erasure and whatnot. These days, as I am more used to Scala's type-system, I run into corner cases in Java that really surprise me (and slow me down).

To add to this, I don't think the complexity of the language in itself matters too much. For me, it is important how easy or difficult it is to write nice and (more or less) correct programs using that language and its libraries. For me, Scala works better here than Java (and C++ and a bunch of dynamic languages I tried).

I just don't buy this whole complexity (of the language) argument. Many people consider Ruby to be a very simple language. I've done some Ruby programming over a few years. Even after that time, I encountered code (that did simple, everyday stuff) that was completely cryptic (to me). People can (and will) write cryptic, unmaintainable code in any language.

Just my 2c
Andreas

P.S.
Even more unrelated, does Scala even need to be the "next big language"? :)

Luc Duponcheel wrote:

> Andreas,
>
> I do not want to play the devil's advocate here,
> but, have you never been confronted,
> even when doing everyday work,
> with type inferencer complexity that was not
> immediately clear to deal with?
>
> I have to confess that
> I sometimes have been confronted with complex
> (and slightly confusing) error messages ; agreed
> I typically use Scala for more experimental stuff.

Luc Duponcheel
Joined: 2008-12-19,
User offline. Last seen 34 weeks 3 days ago.
Re: Is Scala's type system turing complete?
> Even more unrelated, does Scala even need to be the "next big language"? :)

certainly there is a need for a language having Scala's main characteristics
(it can grow (you can make your own DSLs))

if only to stop the cancer growth of languages that are used now
just because Java does *not* have the characteristic above
(and, even when jdk7 would have closures, I am sure that you cannot
do things using it as *elegant* as in Scala)

also my 2c

--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Is Scala's type system turing complete?
Just as soon as we get the quantum typing and neural interface in 2.9.9.9.9.9, how could it *not* be the next big language?


On 24 September 2010 12:55, Andreas Flierl <andreas [at] flierl [dot] eu> wrote:
Luc,

of course, from time to time, I run into stuff that is not immediately clear how to deal with. This happens (or happened) to me in virtually any language I use or used. I remember when generics came to Java. It was uncharted territory for the programmers I knew and also for me. Lots of issues with the use-site variance and erasure and whatnot. These days, as I am more used to Scala's type-system, I run into corner cases in Java that really surprise me (and slow me down).

To add to this, I don't think the complexity of the language in itself matters too much. For me, it is important how easy or difficult it is to write nice and (more or less) correct programs using that language and its libraries. For me, Scala works better here than Java (and C++ and a bunch of dynamic languages I tried).

I just don't buy this whole complexity (of the language) argument. Many people consider Ruby to be a very simple language. I've done some Ruby programming over a few years. Even after that time, I encountered code (that did simple, everyday stuff) that was completely cryptic (to me). People can (and will) write cryptic, unmaintainable code in any language.

Just my 2c
Andreas

P.S.
Even more unrelated, does Scala even need to be the "next big language"? :)

Luc Duponcheel wrote:

> Andreas,
>
> I do not want to play the devil's advocate here,
> but, have you never been confronted,
> even when doing everyday work,
> with type inferencer complexity that was not
> immediately clear to deal with?
>
> I have to confess that
> I sometimes have been confronted with complex
> (and slightly confusing) error messages ; agreed
> I typically use Scala for more experimental stuff.



--
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda

Philippe Lhoste
Joined: 2010-09-02,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?

On 24/09/2010 13:55, Andreas Flierl wrote:
> People can (and will) write cryptic, unmaintainable code in
> any language.

Obfuscated code contests are still popular... :-)
On the other hand, I even saw readable Perl (for somebody not knowledgeable like me)... ;-)

> P.S. Even more unrelated, does Scala even need to be the "next big language"? :)

Yes, if we want to code in Scala in our day job... :-P

Philippe Lhoste
Joined: 2010-09-02,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?

On 24/09/2010 13:32, Luc Duponcheel wrote:
> I have to confess that
> I sometimes have been confronted with complex
> (and slightly confusing) error messages ; agreed
> I typically use Scala for more experimental stuff.
>
> On the other hand, when implementing a web application
> using Lift, I rarely ran into Scala complexity. It looks as
> if a good framework (and rules on how to use it) can avoid
> all this.

That show the dual nature of Scala, and why we get contradictory signals from people
looking at it or using it!

Scala is a powerful tool to make efficient and easy to use frameworks/libraries/tools. I
haven't investigated them already, but I have seen lot of good opinions on Lift,
Scala-Swing, SBT and similar.
Now, apparently, the work of those making these tools/libraries/frameworks might be not so
easy, as they have to think ahead a good type system & API to make them flexible and
future-proof.
Yet, nothing prevent from making something more limited, Java-style for example, or even
imperative, if we are limited ourself (as I am currently) and if it fits the short term
goal (and Scala might be flexible enough to allow extending this without breaking too much
legacy work).

That's how we find children programming in Scala with Kojo, and computer scientists making
high-level experimental stuff with this language.

Wibowit
Joined: 2010-09-13,
User offline. Last seen 2 years 4 weeks ago.
Re: Is Scala's type system turing complete?
There are two mutually exclusive goals:- simplicity of language,- conciseness of solutions,
Java generally is quite simple (not counting some weird stuff concerning generics) but there's LOT of boilerplate code that makes code hard to understand. It takes a few months to learn almost entire Scala language and from that point reading concise Scala code is much more pleasing that reading boilerplate code in "simple" languages.
The tradeoff is to spend few months learning Scala to be many times more productive in tens of years of developing.
Due to expressive power of Scala, talented programmers can develop solutions many times faster than users of simple languages. Any wise enhancements to Scala will widen that gap.
I don't want lazy programmers, not really interested in their job, to program in Scala, as this would mean a lot of poor code in Scala. There should be some diversity.
What we really need is a modern and sophisticated Scala platform, that isn't tied to JVM or CLR.

2010/9/24 Andreas Flierl <andreas [at] flierl [dot] eu>
Luc,

of course, from time to time, I run into stuff that is not immediately clear how to deal with. This happens (or happened) to me in virtually any language I use or used. I remember when generics came to Java. It was uncharted territory for the programmers I knew and also for me. Lots of issues with the use-site variance and erasure and whatnot. These days, as I am more used to Scala's type-system, I run into corner cases in Java that really surprise me (and slow me down).

To add to this, I don't think the complexity of the language in itself matters too much. For me, it is important how easy or difficult it is to write nice and (more or less) correct programs using that language and its libraries. For me, Scala works better here than Java (and C++ and a bunch of dynamic languages I tried).

I just don't buy this whole complexity (of the language) argument. Many people consider Ruby to be a very simple language. I've done some Ruby programming over a few years. Even after that time, I encountered code (that did simple, everyday stuff) that was completely cryptic (to me). People can (and will) write cryptic, unmaintainable code in any language.

Just my 2c
Andreas

P.S.
Even more unrelated, does Scala even need to be the "next big language"? :)

Luc Duponcheel wrote:

> Andreas,
>
> I do not want to play the devil's advocate here,
> but, have you never been confronted,
> even when doing everyday work,
> with type inferencer complexity that was not
> immediately clear to deal with?
>
> I have to confess that
> I sometimes have been confronted with complex
> (and slightly confusing) error messages ; agreed
> I typically use Scala for more experimental stuff.

dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Is Scala's type system turing complete?
I expect Scala will get better soon in that respect. This problem often happens because all the type checker knows is that the types do not check. The intent of the library at which the code failed is not known to the compiler. Or that was the case, anyway. One post 2.8.0 commit introduced an annotation that enables libraries to produce targetted error messages if an implicit parameter is not found, which should go a long way.

On Fri, Sep 24, 2010 at 08:55, Andreas Flierl <andreas [at] flierl [dot] eu> wrote:
Luc,

of course, from time to time, I run into stuff that is not immediately clear how to deal with. This happens (or happened) to me in virtually any language I use or used. I remember when generics came to Java. It was uncharted territory for the programmers I knew and also for me. Lots of issues with the use-site variance and erasure and whatnot. These days, as I am more used to Scala's type-system, I run into corner cases in Java that really surprise me (and slow me down).

To add to this, I don't think the complexity of the language in itself matters too much. For me, it is important how easy or difficult it is to write nice and (more or less) correct programs using that language and its libraries. For me, Scala works better here than Java (and C++ and a bunch of dynamic languages I tried).

I just don't buy this whole complexity (of the language) argument. Many people consider Ruby to be a very simple language. I've done some Ruby programming over a few years. Even after that time, I encountered code (that did simple, everyday stuff) that was completely cryptic (to me). People can (and will) write cryptic, unmaintainable code in any language.

Just my 2c
Andreas

P.S.
Even more unrelated, does Scala even need to be the "next big language"? :)

Luc Duponcheel wrote:

> Andreas,
>
> I do not want to play the devil's advocate here,
> but, have you never been confronted,
> even when doing everyday work,
> with type inferencer complexity that was not
> immediately clear to deal with?
>
> I have to confess that
> I sometimes have been confronted with complex
> (and slightly confusing) error messages ; agreed
> I typically use Scala for more experimental stuff.



--
Daniel C. Sobral

I travel to the future all the time.
Razvan Cojocaru 3
Joined: 2010-07-28,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?

He he. Touche. flatMap denotes the mythical fuzzy creature, the Monad
which is not easily comprehended. I stick with foreach and map for the
most part.

I'm now going through Haskell, just to get a better understanding of
the fuzzy creature.

Look at the for mapping to flatmap, you may get one idea as to when
it's useful.

Cheers,
Razie

On 9/24/10, Philippe Lhoste wrote:
> On 24/09/2010 05:58, Razvan Cojocaru-2 wrote:
>> Well, I can agree that scala is complicated...
>
> Yes and no...
> I don't know if the same distinction exists in English, but in my youth, I
> learned the
> difference (in French) between complicated and complex.
> Complicated implies somebody is looking for difficulty, not doing simple
> things on
> purpose, with an idea of confusion and unnecessary hard to understand
> concepts.
> Complex implies something hard to understand, with lot of parts that is
> difficult to
> grasp, but with an idea of organization and logic.
>
> I don't mean to give a lesson on semantics, but as a newbie, I first found
> Scala to be
> complicated (some incantations seems unreadable, near line noise), then,
> starting to learn
> it seriously, I find it simpler than I thought and overall quite readable.
> ... Except for the type system, which is indeed very complex, even more as
> some texts
> assume familiarity with the theory of types and intimate knowledge of terms
> like
> covariance and contravariance....
> Thus, I found the first part of the Scala Overview
> very clear and
> illuminating the
> deep consistency behind the cool syntax sugar presented by tutorials... and
> the second
> part totally unreadable for somebody not used to programming language theory
> and FP
> concepts! (but I will come back to it after a while).
>
> So, my feeling is that Scala is quite simple to use, the 'case class' is a
> joy for a Java
> programmer, it allows to express code in a simple and terse yet readable (if
> carefully
> written) way. Yet it can be very complex (ie. hard to understand but with a
> deep logic
> behind) if one must dig into the type system to make generic, re-usable
> components.
>
>
> That's actually what you (and Martin) wrote, just expressed in my own
> (clumsy) words, from
> a beginner's point of view.
>
> Your idea is intriguing / interesting, although I am not sure if it is
> really usable.
> Somehow, a beginner will just stay away from making complex (or
> complicated...) stuff,
> just making simple classes and trying to chain some functions.
>
> Note: there is still some difficulty from the doc/API itself, as it exposes
> this type
> system. I found a blog article using flatMap and when I wanted to understand
> what it does,
> I find:
>
> def flatMap [B, That] (f: (A) => Traversable[B])(implicit bf:
> CanBuildFrom[List[A], B,
> That]) : That
> Builds a new collection by applying a function to all elements of this list
> and
> concatenating the results.
>
> What results? How it differs from the simple map()? ("Builds a new
> collection by applying
> a function to all elements of this list.")
> I think I (vaguely) understood the difference, but it is far from obvious
> and the doc
> seems to be more aimed at specialists than at newbies...
>
> --
> Philippe Lhoste

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Is Scala's type system turing complete?
I'm not so sure, this slide tells me that the JVM is pretty modern and sophisticated: http://cr.openjdk.java.net/~jrose/pres/201009-OneVMManyLanguages/pres_files/pres.008.jpg


On 24 September 2010 13:19, Piotr Tarsa <piotr [dot] tarsa [at] gmail [dot] com> wrote:
There are two mutually exclusive goals:- simplicity of language,- conciseness of solutions,
Java generally is quite simple (not counting some weird stuff concerning generics) but there's LOT of boilerplate code that makes code hard to understand. It takes a few months to learn almost entire Scala language and from that point reading concise Scala code is much more pleasing that reading boilerplate code in "simple" languages.
The tradeoff is to spend few months learning Scala to be many times more productive in tens of years of developing.
Due to expressive power of Scala, talented programmers can develop solutions many times faster than users of simple languages. Any wise enhancements to Scala will widen that gap.
I don't want lazy programmers, not really interested in their job, to program in Scala, as this would mean a lot of poor code in Scala. There should be some diversity.
What we really need is a modern and sophisticated Scala platform, that isn't tied to JVM or CLR.

2010/9/24 Andreas Flierl <andreas [at] flierl [dot] eu>
Luc,

of course, from time to time, I run into stuff that is not immediately clear how to deal with. This happens (or happened) to me in virtually any language I use or used. I remember when generics came to Java. It was uncharted territory for the programmers I knew and also for me. Lots of issues with the use-site variance and erasure and whatnot. These days, as I am more used to Scala's type-system, I run into corner cases in Java that really surprise me (and slow me down).

To add to this, I don't think the complexity of the language in itself matters too much. For me, it is important how easy or difficult it is to write nice and (more or less) correct programs using that language and its libraries. For me, Scala works better here than Java (and C++ and a bunch of dynamic languages I tried).

I just don't buy this whole complexity (of the language) argument. Many people consider Ruby to be a very simple language. I've done some Ruby programming over a few years. Even after that time, I encountered code (that did simple, everyday stuff) that was completely cryptic (to me). People can (and will) write cryptic, unmaintainable code in any language.

Just my 2c
Andreas

P.S.
Even more unrelated, does Scala even need to be the "next big language"? :)

Luc Duponcheel wrote:

> Andreas,
>
> I do not want to play the devil's advocate here,
> but, have you never been confronted,
> even when doing everyday work,
> with type inferencer complexity that was not
> immediately clear to deal with?
>
> I have to confess that
> I sometimes have been confronted with complex
> (and slightly confusing) error messages ; agreed
> I typically use Scala for more experimental stuff.




--
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda

Wibowit
Joined: 2010-09-13,
User offline. Last seen 2 years 4 weeks ago.
Re: Is Scala's type system turing complete?
There's many optimizations listed, many are pretty standard.
I've checked for example "autobox elimination" - I think it's optimization of wrapped primitives. I've created a simple loop and computed factorial inside, and wrapped primitives had about 8x lower performance. For with Ranges aren't optimized by JVM (there's a fresh thread about it).
I didn't programmed in Scala very much but for example I've read that Singleton pattern, heavily supported by Scala, is in fact antipattern as it introduces global mutable state. What I would like to have instead of that is dynamic Dependency Injection built directly into VM. For example:  interface C - in some package; class A provides C when (condition) - in another package;val b = inject C
Couple that with implicits etc whatever is appropriate (and some module system) and we do not need any global state. But that's a little Off-Topic.
We can remove explicit thread synchronization (ie. use processes like those from Erlang) and include actors and mailboxes support directly into VM - this way message distribuiton could be optimized on-the-fly.

2010/9/24 Kevin Wright <kev [dot] lee [dot] wright [at] gmail [dot] com>
I'm not so sure, this slide tells me that the JVM is pretty modern and sophisticated: http://cr.openjdk.java.net/~jrose/pres/201009-OneVMManyLanguages/pres_files/pres.008.jpg


On 24 September 2010 13:19, Piotr Tarsa <piotr [dot] tarsa [at] gmail [dot] com> wrote:
There are two mutually exclusive goals:- simplicity of language,- conciseness of solutions,
Java generally is quite simple (not counting some weird stuff concerning generics) but there's LOT of boilerplate code that makes code hard to understand. It takes a few months to learn almost entire Scala language and from that point reading concise Scala code is much more pleasing that reading boilerplate code in "simple" languages.
The tradeoff is to spend few months learning Scala to be many times more productive in tens of years of developing.
Due to expressive power of Scala, talented programmers can develop solutions many times faster than users of simple languages. Any wise enhancements to Scala will widen that gap.
I don't want lazy programmers, not really interested in their job, to program in Scala, as this would mean a lot of poor code in Scala. There should be some diversity.
What we really need is a modern and sophisticated Scala platform, that isn't tied to JVM or CLR.

2010/9/24 Andreas Flierl <andreas [at] flierl [dot] eu>
Luc,

of course, from time to time, I run into stuff that is not immediately clear how to deal with. This happens (or happened) to me in virtually any language I use or used. I remember when generics came to Java. It was uncharted territory for the programmers I knew and also for me. Lots of issues with the use-site variance and erasure and whatnot. These days, as I am more used to Scala's type-system, I run into corner cases in Java that really surprise me (and slow me down).

To add to this, I don't think the complexity of the language in itself matters too much. For me, it is important how easy or difficult it is to write nice and (more or less) correct programs using that language and its libraries. For me, Scala works better here than Java (and C++ and a bunch of dynamic languages I tried).

I just don't buy this whole complexity (of the language) argument. Many people consider Ruby to be a very simple language. I've done some Ruby programming over a few years. Even after that time, I encountered code (that did simple, everyday stuff) that was completely cryptic (to me). People can (and will) write cryptic, unmaintainable code in any language.

Just my 2c
Andreas

P.S.
Even more unrelated, does Scala even need to be the "next big language"? :)

Luc Duponcheel wrote:

> Andreas,
>
> I do not want to play the devil's advocate here,
> but, have you never been confronted,
> even when doing everyday work,
> with type inferencer complexity that was not
> immediately clear to deal with?
>
> I have to confess that
> I sometimes have been confronted with complex
> (and slightly confusing) error messages ; agreed
> I typically use Scala for more experimental stuff.




--
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda


Miles Egan
Joined: 2010-07-05,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?

I think not, which is good because my instinct is that the rank & file
are still not ready for a full-blown functional language.

The brilliant thing about FP on the JVM is that we don't have to be
the next big thing, just big enough.

On Fri, Sep 24, 2010 at 4:55 AM, Andreas Flierl wrote:
> Even more unrelated, does Scala even need to be the "next big language"? :)

Randall R Schulz
Joined: 2008-12-16,
User offline. Last seen 1 year 29 weeks ago.
Re: Is Scala's type system turing complete?

On Friday September 24 2010, Maxime Lévesque wrote:
> You hit a crucial point here : can the complexity be hidden in
> libraries ?

Incidental complexity? Yes. Essential complexity?
Less so; perhaps not much at all.

> ...
>
> Max

Randall Schulz

Randall R Schulz
Joined: 2008-12-16,
User offline. Last seen 1 year 29 weeks ago.
Re: Is Scala's type system turing complete?

On Friday September 24 2010, Kevin Wright wrote:
> Just as soon as we get the quantum typing and neural interface in
> 2.9.9.9.9.9, how could it *not* be the next big language?

Sounds like a language ripe to tunnel to 3.0.0.0.0.1.

RRS

Randall R Schulz
Joined: 2008-12-16,
User offline. Last seen 1 year 29 weeks ago.
Re: Is Scala's type system turing complete?

On Friday September 24 2010, Piotr Tarsa wrote:
> ...
>
> I don't want lazy programmers, not really interested in their job, to
> program in Scala, as this would mean a lot of poor code in Scala.
> There should be some diversity.

Since the conversation is about definitions, you have to distinguish two
kinds of laziness (apart from kind in the programming language itself,
naturally):

- Plain sloth. People who are not ambitious, not diligent, not motivated
and want to just do the minimum (or even less) to get a job done (or
get through the day), regardless of consequences that will be felt down
the road or that may fall on others.

- Inventive laziness: This is the kind of laziness that starts with "I
shouldn't have to do this" or "I shouldn't have to do this again." and
proceeds to invent something to free the "lazy" person of that burden
once and for all, freeing them up to do more things. Inventive laziness
is usually quite a bit of work, but it's worth it 'cause it saves even
more work in the future, usually the immediate future.

This could be elaborated, of course, but the essence is there.
There's "good lazy" and "bad lazy."

> ...

Randall Schulz

Wibowit
Joined: 2010-09-13,
User offline. Last seen 2 years 4 weeks ago.
Re: Is Scala's type system turing complete?
I thought it was obvious from the context: "good lazy" programmers do not write poor code!
Apart from that: what are other types besides "good lazy" and "bad lazy"? "Semi lazy" - people too irritated to be "bad lazy" but unable to be "good lazy"?

2010/9/24 Randall R Schulz <rschulz [at] sonic [dot] net>
On Friday September 24 2010, Piotr Tarsa wrote:
> ...
>
> I don't want lazy programmers, not really interested in their job, to
> program in Scala, as this would mean a lot of poor code in Scala.
> There should be some diversity.

Since the conversation is about definitions, you have to distinguish two
kinds of laziness (apart from kind in the programming language itself,
naturally):

- Plain sloth. People who are not ambitious, not diligent, not motivated
and want to just do the minimum (or even less) to get a job done (or
get through the day), regardless of consequences that will be felt down
the road or that may fall on others.

- Inventive laziness: This is the kind of laziness that starts with "I
shouldn't have to do this" or "I shouldn't have to do this again." and
proceeds to invent something to free the "lazy" person of that burden
once and for all, freeing them up to do more things. Inventive laziness
is usually quite a bit of work, but it's worth it 'cause it saves even
more work in the future, usually the immediate future.


This could be elaborated, of course, but the essence is there.
There's "good lazy" and "bad lazy."


> ...


Randall Schulz

Raoul Duke
Joined: 2009-01-05,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Is Scala's type system turing complete?

On Fri, Sep 24, 2010 at 1:51 AM, Adriaan Moors wrote:
> This may sound scary, but we're here to help! One of our research projects
> is developing a type debugger, which gives you much more help than what any
> language currently has to offer when it comes to type error messages.

holy cow. that. would. be. awesome.

(i mean, i love how the sml compiler helps me get things right in the
end, but it can be a big hunt-the-wumpus / whack-a-mole adventure of
slow painful bad usability along the way.)

sincerely.

Raoul Duke
Joined: 2009-01-05,
User offline. Last seen 42 years 45 weeks ago.
Re: Is Scala's type system turing complete?

2010/9/24 Maxime Lévesque :
>  You hit a crucial point here : can the complexity be hidden in libraries ?

people claim it can be, but personally i have never seen a solid,
valid existence proof of it. i believe it to be an inherently leaky
abstraction.

sincerely.

Michael
Joined: 2009-02-23,
User offline. Last seen 20 weeks 1 day ago.
Re:

Here is my take at encoding the SKI calculus in Scala's type system:
http://michid.wordpress.com/2010/01/29/scala-type-level-encoding-of-the-...

If correct, this would show that Scala's type system is indeed Turing complete.

Michael

Christian Szegedy
Joined: 2009-02-08,
User offline. Last seen 42 years 45 weeks ago.
Re: Re:

Scary.

This is not good.

IMO, the compiler of a reasonable language should run in linear or at
least polynomial time
in the length of the code checked.

On 9/24/10, Michael wrote:
> Here is my take at encoding the SKI calculus in Scala's type system:
> http://michid.wordpress.com/2010/01/29/scala-type-level-encoding-of-the-...
>
> If correct, this would show that Scala's type system is indeed Turing complete.
>
>
> Michael
>
>

nilskp
Joined: 2009-01-30,
User offline. Last seen 1 year 27 weeks ago.
Re: Is Scala's type system turing complete?
On Fri, Sep 24, 2010 at 8:59 AM, Piotr Tarsa <piotr [dot] tarsa [at] gmail [dot] com> wrote:
I didn't programmed in Scala very much but for example I've read that Singleton pattern, heavily supported by Scala, is in fact antipattern as it introduces global mutable state.

Nonsense. A singleton need not be public nor mutable.

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland