The Artima Developer Community
Sponsored Link

Java Community News
Using Scala to Explore Trees

12 replies on 1 page. Most recent reply: Nov 15, 2007 3:19 PM by James Iry

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 12 replies on 1 page
Frank Sommers

Posts: 2642
Nickname: fsommers
Registered: Jan, 2002

Using Scala to Explore Trees Posted: Nov 13, 2007 4:38 PM
Reply to this message Reply
Summary
Scala is a JVM programming language that shares many similarities with Java. Scala provides more advanced languages features as well, such as support for functional programming. Luis Diego Fallas and Thomas Lee show two practical examples of how Scala's functional background makes it an excellent tool for exploring tree-like structures.
Advertisement

One of the more popular languages that target the JVM as its execution environment is Scala, an object-oriented, functional language. (For an introduction to Scala, see First Steps to Scala by Bill Venners, Martin Odersky, and Lex Spoon.)

Among Scala's advanced features are pattern matching and parser combinators, two capabilities highlighted in a pair of articles by Luis Diego Fallas and Thomas Lee.

Lee shows how to take advantage of pattern matching for the purpose of parsing and exploring a tree, such as the syntax tree of the JRuby language, in Exploring JRuby Syntax Trees With Scala:

Because of its functional influence Scala provides nice features to manipulate tree structures... I think one of the most interesting features provided by Scala is pattern matching. Among other pattern matching constructs, Scala provides one that I particularly like : Extractors...

Scala extractor objects allow existing Scala or Java Platform classes to participate in pattern matching ... as case classes. Extractor objects can be used to expose only interesting elements for a certain problem and also makes the definition of the class independent of the way it is used in a match construct...

Several techniques [exist] for exploring complex object data structures. One [is] the Visitor design pattern which is one of the most used techniques ... to navigate a syntax tree structure. I think the pattern matching approach can be combined with the visitors to solve different tasks...

In this post I'm interested in showing pattern matching using Scala extractors on the JRuby AST. The JRuby AST seems to provide nice visitor mechanism...

Thomas Lee uses similar techniques, in addition to a standard Scala parser library, to build a compiler for a domain language, in JVM Compiler Construction with Scala and BCEL:

I only started using Scala about two weeks ago. I’m already falling in love with it—you can think of it as a more expressive Java that straddles the fence the computing industry seems to have erected between functional and object-oriented languages. Scala ... is a beautiful blend of the two...

Scala comes with a standard lexical analysis class (StdLexical) which is capable of producing tokens for a simple Scala-like language.

In theory, once you have written an EBNF description of your programming language syntax, writing a parser for it should be reasonably simple: you simply transcribe the EBNF into your language of choice and away you go. Unfortunately it’s not always that simple in practice, so people resort to using tools like yacc or bison to generate their parsers using EBNF-esque pattern-matching. The downside to these tools is that most have a fairly big learning curve.

Along comes parser combinators. Using combinators, it suddenly becomes possible to use EBNF-like rules in the compiler implementation language - a sort of DSL for parsers, if you like. Combinators appear to be especially popular in functional languages like Haskell (via Parsec)... Scala provides a parser combinator library as part of its standard API.

If you've tried Scala, what were your favorite Scala features? If you haven't tried it yet, what Scala features are you most curious about?


James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Using Scala to Explore Trees Posted: Nov 14, 2007 6:26 AM
Reply to this message Reply
> From the article summary:
>
> Scala is a JVM programming language that shares many
> similarities with Java.

I think this is a misleading statement. The similarities between Java and Scala are mostly superficial, in my opinion.

Carsten Saager

Posts: 17
Nickname: csar
Registered: Apr, 2006

Re: Using Scala to Explore Trees Posted: Nov 14, 2007 7:33 AM
Reply to this message Reply
> > From the article summary:
> >
> > Scala is a JVM programming language that shares many
> > similarities with Java.
>
> I think this is a misleading statement. The similarities
> between Java and Scala are mostly superficial, in my
> opinion.

I think the resemblance ends after the package-declaration and import section.

The only deeper connection is the use of type erasure as it is imposed by the underlying JVM

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Using Scala to Explore Trees Posted: Nov 14, 2007 7:40 AM
Reply to this message Reply
> The only deeper connection is the use of type erasure as
> it is imposed by the underlying JVM

I remember seeing some discussion on the Scala mailing list a while back about the possibility of adding reification. I guess that never panned out. If that were supported, it would make Scala very enticing.

Thomas Lee

Posts: 2
Nickname: tomlee
Registered: Nov, 2007

Re: Using Scala to Explore Trees Posted: Nov 14, 2007 9:52 PM
Reply to this message Reply
Aside from the parser combinators, I'm a huge fan of actors (especially remote actors, despite their slightly buggy current implementation).

I've toyed with the idea of another Scala blog post about actors, but it would seem to have been done to death. :)

Thanks for posting this by the way, great to see it getting around. :)

James Iry

Posts: 85
Nickname: jiry
Registered: Nov, 2007

Re: Using Scala to Explore Trees Posted: Nov 15, 2007 9:19 AM
Reply to this message Reply
> I think this is a misleading statement. The similarities
> between Java and Scala are mostly superficial, in my
> opinion.

Not so. The similarities are very deep.

Compare it to Prolog, Scheme, APL, Forth, and Erlang. Okay, not fair, they're not even OO (though you can add OO to Scheme and, if you squint a bit, Erlang's message passing can be seen as similar to some aspects of the original conception behind OO).

Compare it to Common Lisp, Dylan, and JavaScript. Common Lisp's and Dylan's OO systems are multi-dispatch. JavaScript's OO system is based on prototypes rather than class inheritance.

Compare it to Ruby, Smalltalk, and Python. They're all single dispatch class based OO but they're all dynamically typed and have rich meta-programming facilities.

C++...hmmm, getting there. Statically typed, class based, single dispatch OO with type polymorphism. But any value can be re-interpereted based on its bit pattern, references aren't opaque and the language is based on explicit memory management rather than garbage collection (although you can glue gc in). Plus, templates give it an incredibly powerful (and incredibly baroque) type system that's distinctive from the kind of type polymorphism you find in Scala.

Compare to Java and C#. Here we go. Imperative, garbage collected, opaquely referenced, statically polymorphically typed, single dispatched, class based OO. All of which apply to Scala.

Don't get me wrong. There are important differences and improvements over Java. It can claim some important similarities with say OCaml and Haskell that Java just can't even think about.

But it's still fair to say that Scala is Java-like given the vast territory that languages inhabit. Certainly , other than C# and maybe C++, no other language I've mentioned here is closer to Java. Somebody coming from a background in only Java can easily get started with Scala after working through some small surface syntax issues and then work their way into the more interesting stuff later. Somebody with only Prolog experience would be lost.

Frank Sommers

Posts: 2642
Nickname: fsommers
Registered: Jan, 2002

Re: Using Scala to Explore Trees Posted: Nov 15, 2007 9:50 AM
Reply to this message Reply
>. Somebody coming from a
> background in only Java can easily get started with Scala
> after working through some small surface syntax issues and
> then work their way into the more interesting stuff later.
> Somebody with only Prolog experience would be lost.

That's exactly one of the values of Scala: For someone with deep Java experience, learning the basics of Scala is not a big stretch. You can program in a Java-like way in Scala, and as you gain more experience, take advantage of Scala's nicer, more advanced features. A lot of people looking for things like closures in Java, for instance, can already have that in Scala. And you can, of course, use any of the Java libraries from Scala, which is another way to make Scala code very familiar to Java developers.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Using Scala to Explore Trees Posted: Nov 15, 2007 10:59 AM
Reply to this message Reply
> Compare to Java and C#. Here we go. Imperative, garbage
> collected, opaquely referenced, statically polymorphically
> typed, single dispatched, class based OO. All of which
> apply to Scala.

To me, Scala is only superficially imperative. You can program like it's imperative but to really 'get' Scala you need to think about your program functionally. The most obvious example is that you can write for loops in Scala that look a lot like a Java for loop but it really a for-comprehension.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Using Scala to Explore Trees Posted: Nov 15, 2007 11:07 AM
Reply to this message Reply
> That's exactly one of the values of Scala: For someone
> with deep Java experience, learning the basics of Scala is
> not a big stretch. You can program in a Java-like way in
> Scala, and as you gain more experience, take advantage of
> Scala's nicer, more advanced features. A lot of people
> looking for things like closures in Java, for instance,
> can already have that in Scala. And you can, of course,
> use any of the Java libraries from Scala, which is another
> way to make Scala code very familiar to Java developers.

I'd say I have pretty deep experience with Java and I find that while I can write code in Scala and make it work, I've often been at a loss as to why it works.

That's what I mean by 'superficial'. You write a program that kind of looks like Java code but it's really means something quite different than what it would it Java.

James Iry

Posts: 85
Nickname: jiry
Registered: Nov, 2007

Re: Using Scala to Explore Trees Posted: Nov 15, 2007 1:37 PM
Reply to this message Reply
> To me, Scala is only superficially imperative.

Here we disagree.

Haskell's apparently imperative nature (do notation) is superficial. Scala's imperative nature is an essential part of the language. vars can be reassigned and things like IO happen exactly when and where you say they should. Those are imperative features and they're used throughout the language and its libraries.

Scala also has reference based equality checking (eq). That means that "new" is an imperative, side-effecting construct as well.

> You can program like it's imperative but to really 'get' Scala you need to think about your program functionally.

Here we both agree and disagree. We agree in that if you don't use Scala's functional features you'll feel like the language is strangely crippled and you'll be missing out. Indeed Scala's functional features are sophisticated enough that you can cleanly program without side effects as long as you don't use any side effecting libraries.

However, where we disagree is that if you use most any library, especially IO, you have to program Scala like it's imperative or you'll screw probably yourself up because the order of execution can be important beyond the obvious data dependencies. That's the hallmark of imperative languages.

> The most obvious example is that you can write for loops in Scala that look a lot like a Java for loop but it really a for-comprehension.

Here we agree, mostly. Scala's "for" comprehensions are interesting mix of both worlds. On the one hand when you use "yield" they're purely functional monad comprehensions (like Haskell's "do") in disguise. To really grok Scala you need to understand how that works.

On the other hand "for" without "yield" maps to foreach which MUST be used imperatively to get anything useful out of it. If the function you pass to foreach doesn't have imperative effects then you're just wasting CPU cycles.

But either way, Scala still has "while" and it's exactly what you expect from an imperative language in the C family. It's trivial to map any imperative "for" from Java to a "while" in Scala. To contrast, mapping from some Java "for" examples to anything in Haskell can often require a non-trivial amount of rethinking.

I suspect we're having a terminology issue. Functional and imperative aren't opposites. A functional language is one that supports functions as values. An imperative language is one that supports side effects. Scala does both. That makes Scala along with Scheme, Common Lisp, OCaml, Erlang, and many others what are called "impure functional languages." That's as opposed to Haskell and Clean which are "pure functional languages."

To use an impure functional language effectively you must come to grips with its imperative nature. If you come from a non-functional imperative background then naturally the imperative aspects won't seem like a big deal but the functional aspects will seem to stand out. That doesn't make the imperative aspects any more superficial. If you try to use Scala the way you would Haskell you will screw yourself up unless you're very, very careful.

By the way, I have a series of articles up about monads, for comprehensions, and even how to do IO in a purely functional way. That last bit isn't terribly pragmatic given the shear volume of libraries that do IO (and other side effects) imperatively, but it is an interesting mind stretching exercise that helps illuminate monads in general.
The IO article is http://james-iry.blogspot.com/2007/11/monads-are-elephants-part-4.html. But you'll probably want to look at the other "monads are elephants" articles to get a grounding.

Thomas Lee

Posts: 2
Nickname: tomlee
Registered: Nov, 2007

Re: Using Scala to Explore Trees Posted: Nov 15, 2007 2:21 PM
Reply to this message Reply
To add my two cents to the "Functional vs Imperative" debate (and to paraphrase my original article) - Scala intentionally blurs the lines between imperative and functional languages.

No, it's not purely functional. It tries to take as many good ideas as it can from other languages to produce something useful rather than something only academia care about.

So I guess you could say it's an imperative language that encourages a functional approach to solving problems ... with objects. :)

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Using Scala to Explore Trees Posted: Nov 15, 2007 3:06 PM
Reply to this message Reply
> I suspect we're having a terminology issue.

It's apparently my issue but yes. I see what you are saying but as someone who has used Java as a primary programming language for a fair number of years, I don't see Scala as being similar. It's got some tricks that make Java-esque code work but a lot of things that Scala supports are bizarre from a Java-centric universe (not that it's the 'correct' perspective.)

I would say that Scala is a much more powerful language than Java that Java programmers can start using immediately.

Maybe it's also just that because Java straddles the divide it appears to be functional to the imperative programmer and imperative to the functional programmer. This even though it may actually be [more?] imperative.

James Iry

Posts: 85
Nickname: jiry
Registered: Nov, 2007

Re: Using Scala to Explore Trees Posted: Nov 15, 2007 3:19 PM
Reply to this message Reply
> To add my two cents to the "Functional vs Imperative"
> debate (and to paraphrase my original article) - Scala

There can't be a "functional vs imperative" debate. At least not in the way the word "functional" is commonly used by programmers: a language where functions are values. That's like having a debate on whether I should buy something black or buy some shoes. There's no reason I can't do both. Scala's foreach is a perfect example of that. It's a higher order function that has to be used imperatively to be useful.

There is a debate between the pure, mathematical sense of the word "function" and impure sense in which it is used in most languages (including Scala).

That debate, while it sounds very theoretical, actually has deep value to a practicing programmer in even a completely pragmatic language like Java. For instance, we have that debate internally every time we decide on whether to make the objects of some class immutable or not.

As for Scala, its goal isn't to blur the imperative/functional "boundary." That was done long ago by by Lisp.

Scala's goal is to obliterate the OO/functional boundary for statically typed languages. Many languages have nibbled at it, but I think Scala is the first to really nail it properly. That, its type system, and Java compatibility are why I'm drawn to it.

Flat View: This topic has 12 replies on 1 page
Topic: Enterprise Software Freakishness Previous Topic   Next Topic Topic: Advanced Installer for Java 6.0


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2018 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use