[scala] usefulness of OOP

[fft1976]

I was watching a Google Tech talk by Martin Odersky, in which he says
that functional programmers do not understand the usefulness of OOP,
specifically, the ability to extend classes by overriding methods.
However, as far as I can tell, he does not support this claim later in
the talk. As a counter-argument, I know that in OCaml, OOP is
available (the "O" part), but is widely viewed as a failed experiment
(not "failed" in a pejorative sense, but even its creator does not use
the objective extensions). What can overriding methods do that
higher-order functions can not do as well or better?

[Meredith Gregory]

FFT,

i share your sentiments. One real abstraction technique that i believe has some legs and remotely resembles OO techniques is the Haskell typeclass. i think this really gets at some of what OO is groping towards; but, i think there is a genuine overhead for Scala that is about the rational reconstruction of OO semantics. It's an overhead the main function of which is to ease the transition of the OO community to a more scalable set of abstractions.

Best wishes,

--greg

On Mon, Apr 27, 2009 at 6:03 PM, FFT <[hidden email]> wrote:

I was watching a Google Tech talk by Martin Odersky, in which he says
that functional programmers do not understand the usefulness of OOP,
specifically, the ability to extend classes by overriding methods.
However, as far as I can tell, he does not support this claim later in
the talk. As a counter-argument, I know that in OCaml, OOP is
available (the "O" part), but is widely viewed as a failed experiment
(not "failed" in a pejorative sense, but even its creator does not use
the objective extensions). What can overriding methods do that
higher-order functions can not do as well or better?

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com

[Dave Griffith]

I would almost have to imagine you misheard.  Overriding a non-trivial concrete method with another concrete method is very rare in modern mainstream OO practice, to the point where I would almost consider it an anti-pattern.   I would imagine it makes a bit more sense with mix-in inheritance, but haven't needed it enough to say, and in any case that use seems more aspect-oriented than object-oriented.    

FFT-2 wrote

What can overriding methods do that
higher-order functions can not do as well or better?

[Steven Shaw-2]

2009/4/28 Meredith Gregory <[hidden email]>

... to ease the transition of the OO community to a more scalable set of abstractions.

Are you saying that Scala is therapy for Java programmers? :)

[fft1976]

On Mon, Apr 27, 2009 at 9:33 PM, Dave  Griffith
<[hidden email]> wrote:

> I would almost have to imagine you misheard.

Bad wording on my part (I'm not an OO person, so I don't always use
the correct nomenclature) I think what Martin said was that it's
useful to implement some methods in a class, while leaving some
unimplemented (to be implemented by the user of the class).

 He mentioned how functional programmers don't understand the
usefulness of this. I still don't see what useful things this gives
you that higher-order functions don't.

[Ricky Clarkson]

It doesn't give anything that higher order functions don't.  The two techniques are equivalent and can be implemented in terms of one another.  However, in each language, one technique will tend to be more readable than the other.

2009/4/28 FFT <[hidden email]>

On Mon, Apr 27, 2009 at 9:33 PM, Dave  Griffith
<[hidden email]> wrote:

> I would almost have to imagine you misheard.

Bad wording on my part (I'm not an OO person, so I don't always use
the correct nomenclature) I think what Martin said was that it's
useful to implement some methods in a class, while leaving some
unimplemented (to be implemented by the user of the class).

 He mentioned how functional programmers don't understand the
usefulness of this. I still don't see what useful things this gives
you that higher-order functions don't.

[Jesper Nordenberg]

Meredith Gregory wrote:
> FFT,
>
> i share your sentiments. One real abstraction technique that i believe
> has some legs and remotely resembles OO techniques is the Haskell
> typeclass. i think this really gets at some of what OO is groping
> towards; but, i think there is a genuine overhead for Scala that is
> about the rational reconstruction of OO semantics. It's an overhead the
> main function of which is to ease the transition of the OO community to
> a more scalable set of abstractions.

To be really powerful a language needs to support both static and
dynamic polymorphism. In Haskell type classes can be used for both types
(see http://haskell.org/haskellwiki/OOP_vs_type_classes for some
examples). In Scala dynamic polymorphism is achieved through sub typing,
static polymorphism mostly through implicits.

Now with type classes you can extend existing types with new dynamically
resolved functionality to outside of their definition site. This can not
be achieved with inheritance/implementation as the type hierarchy is
static. Something like scoped interface injection could be a solution.
It would be resolved similarly to implicits, but could introduce new
sub/super type relationships locally. I would really be interested if
someone knows a language which supports such a feature, it's somewhat
akin to dynamic multi methods but instead work on interface basis.

/Jesper Nordenberg

[Martin Odersky]

On Tue, Apr 28, 2009 at 3:03 AM, FFT <[hidden email]> wrote:

> I was watching a Google Tech talk by Martin Odersky, in which he says
> that functional programmers do not understand the usefulness of OOP,
> specifically, the ability to extend classes by overriding methods.
> However, as far as I can tell, he does not support this claim later in
> the talk. As a counter-argument, I know that in OCaml, OOP is
> available (the "O" part), but is widely viewed as a failed experiment
> (not "failed" in a pejorative sense, but even its creator does not use
> the objective extensions). What can overriding methods do that
> higher-order functions can not do as well or better?
>

The crucial thing is to be able to implement methods (and, in the case
of Scala, types)
in subclasses. That way, the unknown part of an abstraction can be
left open in a class to be filled in later in subclasses. Functional
programmers indeed usually don't get this, and think higher-order
methods or ML functors are a sufficient replacement. But the crucial
difference is this:

An implementation of an abstract {def, val, type} can refer to other
members of its superclass. But an argument to a higher order method or
functor cannot refer to
the result of the application. So open recursion with abstraction is
supported in OOP but it requires elaborate and rather tedious
boilerplate in FP (such as the encodings of classes in TAPL (*).

To get a demonstration what difference this can make, I invite you to
try to do this little task, which was originally proposed by Corky
Cartwright at a WG 2.8 meeting (**):

The task is to write an interpreter for a little functional language -
 lambda calculus with n-argument functions and integer arithmetic.
There are several means to represent
variables and environments in such an interpreter. For instance,
variables could be strings and environments association lists, or
variables could be DeBruijn numbers, and environments simple stacks.
The question is this -- how much of your interpreter can you re-use if
you change your decision how to represent variables and environments?

Corky put this up as a challenge in the meeting because he noted that
this was rather easy in Scheme, but almost impossible in GJ (or Java
today). So are static types hindering re-use? People at the meeting
came up with three different solutions, one in SML, one in Haskell,
and one in Scala. The Scala solution used a simple abstract class for
the interpreter where environment type, variable type and environment
access were kept abstract. Abstract members were then implemented in
different ways for DeBruijn and association list interpreters. The
Haskell solution used a big type class (with six functional
dependencies, if I remember correctly). The ML solution used functors
with sharing constraints. It was about 1 1/2 times the length of the
other two solutions. Also, everyone but the most experienced ML
programmers found it significantly harder to understand than the other
two solutions. But it's really better if you try this out for
yourself...

Cheers

 -- Martin

(*) Benjamin Pierce: Types And Programming Languages
(**) IFIP Working Group for Functional Programming

[Johannes Rudolph-2]

On Tue, Apr 28, 2009 at 3:03 AM, FFT <[hidden email]> wrote:
> I was watching a Google Tech talk by Martin Odersky, in which he says
> that functional programmers do not understand the usefulness of OOP,
> specifically, the ability to extend classes by overriding methods.
> However, as far as I can tell, he does not support this claim later in
> the talk. As a counter-argument, I know that in OCaml, OOP is
> available (the "O" part), but is widely viewed as a failed experiment
> (not "failed" in a pejorative sense, but even its creator does not use
> the objective extensions). What can overriding methods do that
> higher-order functions can not do as well or better?

Part of the usefulness of OOP shows even when comparing Java to C#:
Java supports closures with anonymous inner classes, whereas in C#
only delegates (=functions) may close over the surrounding scope.
Being used to programming with closures, I felt that very limiting in
C# and ended up passing several delegates to the constructor of a
generic helper class (instead of creating named subclasses for each
case which probably would have been more natural).

--
Johannes

-----------------------------------------------
Johannes Rudolph
http://virtual-void.net

[Paul Chiusano]

To get a demonstration what difference this can make, I invite you to
try to do this little task, which was originally proposed by Corky
Cartwright at a WG 2.8 meeting (**):

The task is to write an interpreter for a little functional language -
 lambda calculus with n-argument functions and integer arithmetic.

 

This sounds very interesting, Martin! Are the solutions people came up with documented anywhere that we could look at?

On Tue, Apr 28, 2009 at 5:23 AM, martin odersky <[hidden email]> wrote:

On Tue, Apr 28, 2009 at 3:03 AM, FFT <[hidden email]> wrote:
> I was watching a Google Tech talk by Martin Odersky, in which he says
> that functional programmers do not understand the usefulness of OOP,
> specifically, the ability to extend classes by overriding methods.
> However, as far as I can tell, he does not support this claim later in
> the talk. As a counter-argument, I know that in OCaml, OOP is
> available (the "O" part), but is widely viewed as a failed experiment
> (not "failed" in a pejorative sense, but even its creator does not use
> the objective extensions). What can overriding methods do that
> higher-order functions can not do as well or better?
>

The crucial thing is to be able to implement methods (and, in the case
of Scala, types)
in subclasses. That way, the unknown part of an abstraction can be
left open in a class to be filled in later in subclasses. Functional
programmers indeed usually don't get this, and think higher-order
methods or ML functors are a sufficient replacement. But the crucial
difference is this:

An implementation of an abstract {def, val, type} can refer to other
members of its superclass. But an argument to a higher order method or
functor cannot refer to
the result of the application. So open recursion with abstraction is
supported in OOP but it requires elaborate and rather tedious
boilerplate in FP (such as the encodings of classes in TAPL (*).

To get a demonstration what difference this can make, I invite you to
try to do this little task, which was originally proposed by Corky
Cartwright at a WG 2.8 meeting (**):

The task is to write an interpreter for a little functional language -
 lambda calculus with n-argument functions and integer arithmetic.
There are several means to represent
variables and environments in such an interpreter. For instance,
variables could be strings and environments association lists, or
variables could be DeBruijn numbers, and environments simple stacks.
The question is this -- how much of your interpreter can you re-use if
you change your decision how to represent variables and environments?

Corky put this up as a challenge in the meeting because he noted that
this was rather easy in Scheme, but almost impossible in GJ (or Java
today). So are static types hindering re-use? People at the meeting
came up with three different solutions, one in SML, one in Haskell,
and one in Scala. The Scala solution used a simple abstract class for
the interpreter where environment type, variable type and environment
access were kept abstract. Abstract members were then implemented in
different ways for DeBruijn and association list interpreters. The
Haskell solution used a big type class (with six functional
dependencies, if I remember correctly). The ML solution used functors
with sharing constraints. It was about 1 1/2 times the length of the
other two solutions. Also, everyone but the most experienced ML
programmers found it significantly harder to understand than the other
two solutions. But it's really better if you try this out for
yourself...

Cheers

 -- Martin

(*) Benjamin Pierce: Types And Programming Languages
(**) IFIP Working Group for Functional Programming

[Martin Odersky]

Hi Paul.

I don't have the source anymore. It's been 2003 when we did this. But
it's not hard to do this yourself, really.

Cheers

 -- Martin

On Tue, Apr 28, 2009 at 8:08 PM, Paul Chiusano <[hidden email]> wrote:

>> To get a demonstration what difference this can make, I invite you to
>> try to do this little task, which was originally proposed by Corky
>> Cartwright at a WG 2.8 meeting (**):
>>
>> The task is to write an interpreter for a little functional language -
>>  lambda calculus with n-argument functions and integer arithmetic.
>
>
> This sounds very interesting, Martin! Are the solutions people came up with
> documented anywhere that we could look at?
> On Tue, Apr 28, 2009 at 5:23 AM, martin odersky <[hidden email]>
> wrote:
>>
>> On Tue, Apr 28, 2009 at 3:03 AM, FFT <[hidden email]> wrote:
>> > I was watching a Google Tech talk by Martin Odersky, in which he says
>> > that functional programmers do not understand the usefulness of OOP,
>> > specifically, the ability to extend classes by overriding methods.
>> > However, as far as I can tell, he does not support this claim later in
>> > the talk. As a counter-argument, I know that in OCaml, OOP is
>> > available (the "O" part), but is widely viewed as a failed experiment
>> > (not "failed" in a pejorative sense, but even its creator does not use
>> > the objective extensions). What can overriding methods do that
>> > higher-order functions can not do as well or better?
>> >
>> The crucial thing is to be able to implement methods (and, in the case
>> of Scala, types)
>> in subclasses. That way, the unknown part of an abstraction can be
>> left open in a class to be filled in later in subclasses. Functional
>> programmers indeed usually don't get this, and think higher-order
>> methods or ML functors are a sufficient replacement. But the crucial
>> difference is this:
>>
>> An implementation of an abstract {def, val, type} can refer to other
>> members of its superclass. But an argument to a higher order method or
>> functor cannot refer to
>> the result of the application. So open recursion with abstraction is
>> supported in OOP but it requires elaborate and rather tedious
>> boilerplate in FP (such as the encodings of classes in TAPL (*).
>>
>> To get a demonstration what difference this can make, I invite you to
>> try to do this little task, which was originally proposed by Corky
>> Cartwright at a WG 2.8 meeting (**):
>>
>> The task is to write an interpreter for a little functional language -
>>  lambda calculus with n-argument functions and integer arithmetic.
>> There are several means to represent
>> variables and environments in such an interpreter. For instance,
>> variables could be strings and environments association lists, or
>> variables could be DeBruijn numbers, and environments simple stacks.
>> The question is this -- how much of your interpreter can you re-use if
>> you change your decision how to represent variables and environments?
>>
>> Corky put this up as a challenge in the meeting because he noted that
>> this was rather easy in Scheme, but almost impossible in GJ (or Java
>> today). So are static types hindering re-use? People at the meeting
>> came up with three different solutions, one in SML, one in Haskell,
>> and one in Scala. The Scala solution used a simple abstract class for
>> the interpreter where environment type, variable type and environment
>> access were kept abstract. Abstract members were then implemented in
>> different ways for DeBruijn and association list interpreters. The
>> Haskell solution used a big type class (with six functional
>> dependencies, if I remember correctly). The ML solution used functors
>> with sharing constraints. It was about 1 1/2 times the length of the
>> other two solutions. Also, everyone but the most experienced ML
>> programmers found it significantly harder to understand than the other
>> two solutions. But it's really better if you try this out for
>> yourself...
>>
>> Cheers
>>
>>  -- Martin
>>
>> (*) Benjamin Pierce: Types And Programming Languages
>> (**) IFIP Working Group for Functional Programming
>
>

[fft1976]

On Tue, Apr 28, 2009 at 2:23 AM, martin odersky <[hidden email]> wrote:
> The ML solution used functors
> with sharing constraints. It was about 1 1/2 times the length of the
> other two solutions.

If we are going to compare the lengths of code with such accuracy, a
more precise problem definition could be helpful or, better yet, the
original implementation to convert from (Scheme or Scala?)

What's the syntax and semantics of the language being interpreted? Is
the idea to have two implementations sharing code, while minimizing
the total code size?

[Martin Odersky]

On Tue, Apr 28, 2009 at 8:31 PM, FFT <[hidden email]> wrote:

> On Tue, Apr 28, 2009 at 2:23 AM, martin odersky <[hidden email]> wrote:
>> The ML solution used functors
>> with sharing constraints. It was about 1 1/2 times the length of the
>> other two solutions.
>
> If we are going to compare the lengths of code with such accuracy, a
> more precise problem definition could be helpful or, better yet, the
> original implementation to convert from (Scheme or Scala?)
>
> What's the syntax and semantics of the language being interpreted? Is
> the idea to have two implementations sharing code, while minimizing
> the total code size?
>

Here's the language to to interpret (where postfix * means tupling):

Variables: x
Integer literals: i
Terms:

t = Lambda x*. t
  |  Apply t t*
  |  Var(x)
  |  Num(i)

We assume usual operational semantics of lambda calculus (i.e. static scoping).

The task is to write two interpreters, one with variables x being
DeBruijn indices and one with them being names.
You should go for maximal sharing, i.e. factor out commonalities into
a common class/typeclass/functor/whatever, so that there remains no
duplication of code in the two solutions.

Cheers

 -- Martin

[Ricky Clarkson]

Martin,

Do you have a simpler such problem?  I'd like to see what you mean for myself, but there's too much in there that I would need to learn beforehand.

Ricky.

2009/4/28 martin odersky <[hidden email]>

On Tue, Apr 28, 2009 at 8:31 PM, FFT <[hidden email]> wrote:
> On Tue, Apr 28, 2009 at 2:23 AM, martin odersky <[hidden email]> wrote:
>> The ML solution used functors
>> with sharing constraints. It was about 1 1/2 times the length of the
>> other two solutions.
>
> If we are going to compare the lengths of code with such accuracy, a
> more precise problem definition could be helpful or, better yet, the
> original implementation to convert from (Scheme or Scala?)
>
> What's the syntax and semantics of the language being interpreted? Is
> the idea to have two implementations sharing code, while minimizing
> the total code size?
>

Here's the language to to interpret (where postfix * means tupling):

Variables: x
Integer literals: i
Terms:

t = Lambda x*. t
 |  Apply t t*
 |  Var(x)
 |  Num(i)

We assume usual operational semantics of lambda calculus (i.e. static scoping).

The task is to write two interpreters, one with variables x being
DeBruijn indices and one with them being names.
You should go for maximal sharing, i.e. factor out commonalities into
a common class/typeclass/functor/whatever, so that there remains no
duplication of code in the two solutions.

Cheers

 -- Martin

[Martin Odersky]

On Tue, Apr 28, 2009 at 8:50 PM, Ricky Clarkson
<[hidden email]> wrote:
> Martin,
> Do you have a simpler such problem?  I'd like to see what you mean for
> myself, but there's too much in there that I would need to learn beforehand.
> Ricky.
>
Not really. The problem is that any such discussion requires problems
of a certain size. You can't justify the usefulness of OOP on a
whiteboard (in any case, I can't).  You need problems approaching real
size scenarios.

But in any case the solutions to the problem Corky gave are quite
manageable -- they were all under 60 lines AFAIRC.

Cheers

  -- Martin

[Daryoush Mehrtash-2]

I am not sure I follow.  So what is wrong with this:
 

Abstract members were then implemented in
different ways for DeBruijn and association list interpreters. The
Haskell solution used a big type class (with six functional
dependencies, if I remember correctly).

Daryoush

On Tue, Apr 28, 2009 at 2:23 AM, martin odersky <[hidden email]> wrote:

On Tue, Apr 28, 2009 at 3:03 AM, FFT <[hidden email]> wrote:
> I was watching a Google Tech talk by Martin Odersky, in which he says
> that functional programmers do not understand the usefulness of OOP,
> specifically, the ability to extend classes by overriding methods.
> However, as far as I can tell, he does not support this claim later in
> the talk. As a counter-argument, I know that in OCaml, OOP is
> available (the "O" part), but is widely viewed as a failed experiment
> (not "failed" in a pejorative sense, but even its creator does not use
> the objective extensions). What can overriding methods do that
> higher-order functions can not do as well or better?
>

The crucial thing is to be able to implement methods (and, in the case
of Scala, types)
in subclasses. That way, the unknown part of an abstraction can be
left open in a class to be filled in later in subclasses. Functional
programmers indeed usually don't get this, and think higher-order
methods or ML functors are a sufficient replacement. But the crucial
difference is this:

An implementation of an abstract {def, val, type} can refer to other
members of its superclass. But an argument to a higher order method or
functor cannot refer to
the result of the application. So open recursion with abstraction is
supported in OOP but it requires elaborate and rather tedious
boilerplate in FP (such as the encodings of classes in TAPL (*).

To get a demonstration what difference this can make, I invite you to
try to do this little task, which was originally proposed by Corky
Cartwright at a WG 2.8 meeting (**):

The task is to write an interpreter for a little functional language -
 lambda calculus with n-argument functions and integer arithmetic.
There are several means to represent
variables and environments in such an interpreter. For instance,
variables could be strings and environments association lists, or
variables could be DeBruijn numbers, and environments simple stacks.
The question is this -- how much of your interpreter can you re-use if
you change your decision how to represent variables and environments?

Corky put this up as a challenge in the meeting because he noted that
this was rather easy in Scheme, but almost impossible in GJ (or Java
today). So are static types hindering re-use? People at the meeting
came up with three different solutions, one in SML, one in Haskell,
and one in Scala. The Scala solution used a simple abstract class for
the interpreter where environment type, variable type and environment
access were kept abstract. Abstract members were then implemented in
different ways for DeBruijn and association list interpreters. The
Haskell solution used a big type class (with six functional
dependencies, if I remember correctly). The ML solution used functors
with sharing constraints. It was about 1 1/2 times the length of the
other two solutions. Also, everyone but the most experienced ML
programmers found it significantly harder to understand than the other
two solutions. But it's really better if you try this out for
yourself...

Cheers

 -- Martin

(*) Benjamin Pierce: Types And Programming Languages
(**) IFIP Working Group for Functional Programming

[Ricky Clarkson]

I'm not objecting to the size of solutions; I'll happily rattle out a couple of thousand lines of code to demonstrate a point to myself, but I wonder if the same result could be obtained with a more approachable problem.  Something of Programming in Scala's academic level.

2009/4/28 martin odersky <[hidden email]>

On Tue, Apr 28, 2009 at 8:50 PM, Ricky Clarkson
<[hidden email]> wrote:
> Martin,
> Do you have a simpler such problem?  I'd like to see what you mean for
> myself, but there's too much in there that I would need to learn beforehand.
> Ricky.
>

Not really. The problem is that any such discussion requires problems
of a certain size. You can't justify the usefulness of OOP on a
whiteboard (in any case, I can't).  You need problems approaching real
size scenarios.

But in any case the solutions to the problem Corky gave are quite
manageable -- they were all under 60 lines AFAIRC.

Cheers

 -- Martin

[Martin Odersky]

On Tue, Apr 28, 2009 at 10:51 PM, Daryoush Mehrtash <[hidden email]> wrote:
> I am not sure I follow.  So what is wrong with this:
>
>>
>> Abstract members were then implemented in
>> different ways for DeBruijn and association list interpreters. The
>> Haskell solution used a big type class (with six functional
>> dependencies, if I remember correctly).
>
>
Nothing. Did I imply that something was wrong with it?

 -- Martin

[Jon Harrop]

On Tuesday 28 April 2009 21:51:03 Daryoush Mehrtash wrote:
> On Tue, Apr 28, 2009 at 2:23 AM, martin odersky
<[hidden email]>wrote:

> > To get a demonstration what difference this can make, I invite you to
> > try to do this little task, which was originally proposed by Corky
> > Cartwright at a WG 2.8 meeting (**):
> >
> > The task is to write an interpreter for a little functional language -
> >  lambda calculus with n-argument functions and integer arithmetic.
> > There are several means to represent
> > variables and environments in such an interpreter. For instance,
> > variables could be strings and environments association lists, or
> > variables could be DeBruijn numbers, and environments simple stacks.
> > The question is this -- how much of your interpreter can you re-use if
> > you change your decision how to represent variables and environments?
> >
> > Corky put this up as a challenge in the meeting because he noted that
> > this was rather easy in Scheme, but almost impossible in GJ (or Java
> > today). So are static types hindering re-use? People at the meeting
> > came up with three different solutions, one in SML, one in Haskell,
> > and one in Scala. The Scala solution used a simple abstract class for
> > the interpreter where environment type, variable type and environment
> > access were kept abstract. Abstract members were then implemented in
> > different ways for DeBruijn and association list interpreters. The
> > Haskell solution used a big type class (with six functional
> > dependencies, if I remember correctly). The ML solution used functors
> > with sharing constraints. It was about 1 1/2 times the length of the
> > other two solutions. Also, everyone but the most experienced ML
> > programmers found it significantly harder to understand than the other
> > two solutions. But it's really better if you try this out for
> > yourself...

Apologies for joining this late (in case I missed what I'm looking for
already) but are the solutions available anywhere and has anyone added an
OCaml solution?

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

[Meredith Gregory]

Martin,

Cool! i'll give this a whirl.

Best wishes,

--greg

On Tue, Apr 28, 2009 at 11:41 AM, martin odersky <[hidden email]> wrote:

On Tue, Apr 28, 2009 at 8:31 PM, FFT <[hidden email]> wrote:
> On Tue, Apr 28, 2009 at 2:23 AM, martin odersky <[hidden email]> wrote:
>> The ML solution used functors
>> with sharing constraints. It was about 1 1/2 times the length of the
>> other two solutions.
>
> If we are going to compare the lengths of code with such accuracy, a
> more precise problem definition could be helpful or, better yet, the
> original implementation to convert from (Scheme or Scala?)
>
> What's the syntax and semantics of the language being interpreted? Is
> the idea to have two implementations sharing code, while minimizing
> the total code size?
>

Here's the language to to interpret (where postfix * means tupling):

Variables: x
Integer literals: i
Terms:

t = Lambda x*. t
 |  Apply t t*
 |  Var(x)
 |  Num(i)

We assume usual operational semantics of lambda calculus (i.e. static scoping).

The task is to write two interpreters, one with variables x being
DeBruijn indices and one with them being names.
You should go for maximal sharing, i.e. factor out commonalities into
a common class/typeclass/functor/whatever, so that there remains no
duplication of code in the two solutions.

Cheers

 -- Martin

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com