Is Scala's type system turing complete?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
49 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Is Scala's type system turing complete?

Bill Venners-3
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
Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Luc Duponcheel
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 <[hidden email]> 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

Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Richard Wallace
In reply to this post by Bill Venners-3
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 <[hidden email]> 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
>
Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Raoul Duke
In reply to this post by Luc Duponcheel
On Thu, Sep 23, 2010 at 1:12 PM, Luc Duponcheel
<[hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Daniel Sobral
In reply to this post by Luc Duponcheel
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 <[hidden email]> 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 <[hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Luc Duponcheel
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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

Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Bill Venners-3
In reply to this post by Daniel Sobral
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_stephen_colebourne.html

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

Bill

On Thu, Sep 23, 2010 at 1:18 PM, Daniel Sobral <[hidden email]> 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 <[hidden email]>
> 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 <[hidden email]> 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.
>



--
Bill Venners
Artima, Inc.
http://www.artima.com
Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Alex Cruise-2
On Thu, Sep 23, 2010 at 1:33 PM, Bill Venners <[hidden email]> 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.


-0xe1a
Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Bill Venners-3
Hi Alex,

Oh I meant that I was a bit surprised *Stephen* felt Fantom was an
unlikely candidate, because he has long been a Fantom fan.

Bill

On Thu, Sep 23, 2010 at 1:35 PM, Alex Cruise <[hidden email]> wrote:
> On Thu, Sep 23, 2010 at 1:33 PM, Bill Venners <[hidden email]> 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



--
Bill Venners
Artima, Inc.
http://www.artima.com
Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Daniel Sobral
In reply to this post by Luc Duponcheel
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Miles Sabin
In reply to this post by Luc Duponcheel
On Thu, Sep 23, 2010 at 9:12 PM, Luc Duponcheel
<[hidden email]> 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: [hidden email]
skype: milessabin
http://www.chuusai.com/
http://twitter.com/milessabin
Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Jesper Nordenberg
In reply to this post by Luc Duponcheel
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
> <[hidden email]
> <mailto:[hidden email]>> 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
>     <[hidden email]
>     <mailto:[hidden email]>> 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
>         <[hidden email]
>         <mailto:[hidden email]>> 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
>


Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Meredith Gregory
In reply to this post by Miles Sabin
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 <[hidden email]> wrote:
On Thu, Sep 23, 2010 at 9:12 PM, Luc Duponcheel
<[hidden email]> 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: [hidden email]
skype: milessabin
http://www.chuusai.com/
http://twitter.com/milessabin



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

+1 206.650.3740

http://biosimilarity.blogspot.com

Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Razvan Cojocaru-2
In reply to this post by Bill Venners-3
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: Scripster and Gremlins
Follow me: RSS Feed, Twitter, GitHub.
Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Rob Dickens-2
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_java.html

On Fri, Sep 24, 2010 at 4:58 AM, Razvan Cojocaru-2 <[hidden email]> 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-system-turing-complete-tp2552612p2553014.html
> Sent from the Scala - User mailing list archive at Nabble.com.
>
Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Adriaan Moors-4
Hi,

On Fri, Sep 24, 2010 at 10:12 AM, Rob Dickens <[hidden email]> 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.

cheers
adriaan

Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Philippe Lhoste
In reply to this post by Razvan Cojocaru-2
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...

--
Philippe Lhoste
--  (near) Paris -- France
--  http://Phi.Lho.free.fr
--  --  --  --  --  --  --  --  --  --  --  --  --  --

Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Luc Duponcheel
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 <[hidden email]>
Date: Fri, Sep 24, 2010 at 10:55 AM
Subject: [scala-user] Re: Is Scala's type system turing complete?
To: [hidden email]


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

--
Philippe Lhoste
--  (near) Paris -- France
--  http://Phi.Lho.free.fr
--  --  --  --  --  --  --  --  --  --  --  --  --  --




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

reality goes far beyond imagination

Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Maxime Lévesque
In reply to this post by Philippe Lhoste

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 <[hidden email]> 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...

--
Philippe Lhoste
--  (near) Paris -- France
--  http://Phi.Lho.free.fr
--  --  --  --  --  --  --  --  --  --  --  --  --  --


Reply | Threaded
Open this post in threaded view
|

Re: Is Scala's type system turing complete?

Luc Duponcheel
indeed, Max, imho the art of software engineering is to constrain "complexification"



2010/9/24 Maxime Lévesque <[hidden email]>

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 <[hidden email]> 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...

--
Philippe Lhoste
--  (near) Paris -- France
--  http://Phi.Lho.free.fr
--  --  --  --  --  --  --  --  --  --  --  --  --  --





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

reality goes far beyond imagination

123