Tiered approaches to higher order programming?

I am looking for examples of what I call a "tiered" approach to higher order programming. At the base, you'd have objects (numbers, strings, etc). Above that, you'd have functions which map objects to objects. At the top, you'd have functionals which map functions to functions. Neither functions nor functionals would be first class objects, nor could you pass a function to a function or a functional to a functional.

My thinking is that this approach would offer most of the benefits of the typical higher order approach while making reasoning easier. For example, certain forms of type inference become practical that would be undecidable in a language with first class functions.

Does any language like this currently exist? Backus's FP is similar but it does not allow the definition of new functionals. FL lifts this restriction but adds first class functions. I'm looking for something in the middle.

To put it another way, I'm looking for a higher order language like Lisp or ML but with the restriction that functions can only be constructed and passed statically.

Edit: I should note that because all functions provided to functionals are statically known, programs in such a language would be trivially reducible to first order programs. The 'functionals' would be acting very much like glorified macros.

Perhaps look at Walid Taha's

Perhaps look at Walid Taha's RT-FRP paper, which exploits the separation of combinators (signal functions) from primitive objects (signals updating on some schedule) for proving properties relevant to real-time systems.

I'm not sure what you mean by the last sentence of the first paragraph -- if functions / functionals aren't first-class, you can't pass them to *anything*, right? My interpretation is you mean the function, functional, and object domains are distinct, and objects are not first-class. If so, the RT-FRP is close to this, exploiting the original FRP approach of building up a function graph (point-free programming, essentially), potentially letting you do compiler tricks with it, and then plugging in signals (objects) to it later.

By lmeyerov at Fri, 2009-03-20 19:44 | login or register to post comments

I'm not sure what you mean

I'm not sure what you mean by the last sentence of the first paragraph -- if functions / functionals aren't first-class, you can't pass them to *anything*, right?

You can pass functions to functionals. You cannot pass functionals to anything.

I mean that functions and functionals are not first class in the sense that you can't stick them in a list, return them from a function, bind them in a let expression, construct them at runtime, et cetera. You can do all of these things with objects.

By John Nowak at Fri, 2009-03-20 21:09 | login or register to post comments

If I wanted to do this...

I'd start with a basic first-order functional language, and then equip it with an ML-style module system with modules and functors (maps from modules to modules).

Xavier Leroy has a nice paper on implementing ML style module systems, titled "A Modular Module System".

By neelk at Fri, 2009-03-20 22:03 | login or register to post comments

Aye

That's very much my plan.

By John Nowak at Fri, 2009-03-20 22:21 | login or register to post comments

Then I can strongly

Then I can strongly recommend the Leroy paper, since it's designed to work for most any reasonable base language.

By neelk at Fri, 2009-03-20 23:36 | login or register to post comments

Many languages have tiers,

Many languages have tiers, though how they compose and restrict behavior varies quite a bit. Effect types, for example, impose a certain form of tiering.

Anyhow, if your goal is to "make reasoning easier", then you must tier the 'properties' of the language: reversibility, determinism, termination, communication effects, mutability, confinement, naming and uniqueness, potential for race-conditions and need for synchronization, potential for certain partial failures (exceptions, lost nodes) and means of recovery, and so on. Tiering the features of the language should be a means to an end, not a goal by itself. It seems you're getting your heart set right away on a particular design without clear justification for it other than an assertion that it "might" help reasoning about the system. That isn't sufficient or, at least, it shouldn't be.

To put it another way, I'm looking for a higher order language like Lisp or ML but with the restriction that functions can only be constructed and passed statically.

Try Charity programming language. It requires functions passed to other functions be performed via a special facility rather than via the functions themselves.

By dmbarbour at Fri, 2009-03-20 23:06 | login or register to post comments

Right

It seems you're getting your heart set right away on a particular design without clear justification for it

I assure you that's not the case...

Try Charity programming language.

I'm aware of Charity. It's the only thing I can think of that fits my description. The problem is that Charity is not exactly a language that's seen wide use. I was hoping for a language with a larger body of code written in it that might reveal how the limitations of this approach have been dealt with. For example, has it been necessary to build particular constructs into the language that would typically be implemented via first class functions? Which ones?

By John Nowak at Fri, 2009-03-20 23:43 | login or register to post comments

Hmm

This is an interesting idea... although I like higher order programming a lot, and I'm not convinced it's quite as bad as some make it out to be.

If you keep working on this enough to develop some good answers, the natural question I would ask is whether or not the code in a unrestricted higher-order language can be automatically analyzed for your properties, and then implemented using your techniques.

There could be some really useful stuff here! I for one am biased in favor of higher-order functions over macros, if applicable. Of course, macros are more general, and even when both are suitable, a macro-based implementation can be more appropriate.

By Leon P Smith at Sat, 2009-03-21 00:50 | login or register to post comments

I for one am biased in favor

I for one am biased in favor of higher-order functions over macros

Agreed. By "glorified" macros, I meant type-safe HOFs that *could* be implemented as macros under the hood. It's actually not quite that easy because recursive functionals would require the generation of new functions to convert the program to a first order form, but it's still fairly straightforward.

By John Nowak at Sat, 2009-03-21 01:15 | login or register to post comments

Hmm.

Indeed. Macros are similar... somewhat... to HOFs, but neither is a more general concept. So I guess I was wrong a little bit.

By Leon P Smith at Sat, 2009-03-21 18:44 | login or register to post comments

Decade, Synchrone et al

This reminds me of the treatment of higher-order functions in some synchronous dataflow languages. There's some (brief) discussion in this paper on Decade. Decade itself (I think) has true higher-order functions, but as I recall the paper mentions earlier languages with a more restricted form of higher-orderness, where functional values are always statically fixed, and so can be simply inlined to give a first-order program.

By Roly Perera at Sat, 2009-03-21 08:46 | login or register to post comments

Higher Order Functions Considered Unnecessary

Maybe this paper from Joseph Goguen is relevant, using parameterized modules in the context of OBJ

"Higher Order Functions Considered Unnecessary for Higher Order Programming"

http://www-cse.ucsd.edu/~goguen/pps/utyop.ps

By Bernie Pope at Sun, 2009-03-22 05:36 | login or register to post comments

Yes!

It is very relevant indeed. Thank you.

By John Nowak at Sun, 2009-03-22 06:44 | login or register to post comments

Thanks

I've had OBJ in my queue since Derek Elkins referenced it for its initial algebra semantics. This post prompted me to look at it and I wish I'd seen it earlier. I think the "parameterized style" this paper talks about is a very good idea and deserves further support from languages.

The main example I don't see addressed in the paper is how to do data associated dispatch. For example, if you don't have first class functions, how are you going to associate behavior to the entities in a simulation? It looks like you'll need some mechanism that lets you incrementally add to open types. Adding existential types seems cleaner to me, but allows you to essentially recover first class functions through a Fun theory.

By Matt M at Sun, 2009-03-22 19:38 | login or register to post comments

Lambda the Ultimate

User login

Navigation