2

I'm trying to design a theoretical programming language and I'm facing a problem with high order functions. The language is strong-typed, so the way to define a standard function is like so :

function name ( type1 arg1 , type2, arg2, ... ) : return_type

There's also a way to define data structures like classes (that are types) :

class MyClass
{
    type1 attribute1;
    type2 attribute2;
    ...
}

Now, I would like to extend the function definition to higher-order so that parameters and return values can be classes (types), attributes or functions. For instance having the capability of defining a function that takes as parameter a class or a class member. Let's take an exemple :

function sort ( List<something> data, ??? attribute_name , ??? sorting_function ) : List

This function is supposed to take as first parameter as List of something-typed instances, as second parameter an attribute of the something class, and as third parameter a comparison function. And attribute_name and sorting_function have to be typed. But how ? What should be instead of the ??? ?

I consider an heresy to create a function, class, or attribute type, since they wouldn't be at the same logic-level than data types. This would also imply to have type type, which is even more confusing.

I'm probably missing something in my language-design logic because I'm somehow trying to mix at the same logic-level data and language structure but I totally don't know how to achieve what I want otherwise.

Edit :

To give more details, what matters to me is to have a true seperation between data and models. For instance what we can do in languages such as python or php like :

getattr(obj, attr_name)

or

$obj->$attr_name

doesn't suit my logic since we use data-level (strings) to access attributes, which are structure-level.

In my sort function I gave as example (let's forget the last parameter) we have :

function sort ( List<something> data, ??? attribute_name )

The type of attribute_name cannot be a string, since attributes are not data-level. There should be proper type that designate attributes (class members). But such a type is not a data-type. The real problematic is finding a way to distinguish data-types from strucutre/meta-types that correspond to the different langauge structures.

  • 1
    Attributes are commonly implemented as types/classes that extend a base type. You can see Java and C# doing the same thing. In other words there has to be something you can interact with at runtime to make use of them. Additionally, functions can be handled in different ways. C# has the concept of a delegate, which simply describes a function prototype. Any method or function that matches the signature can be used. Many languages incorporate the concept of lambdas to handle a similar function. Is there something you are not liking from the existing implementations for those features? – Berin Loritsch Jul 30 at 12:59
  • 3
    When a language makes some language concept accessible as a value, that is called reification. For example, Python reifies classes and functions: they are ordinary objects. This is different from reflection, such as Class<?> in Java. C++ is one of the few languages that reifies attribute accesses: you can pass around so-called pointer-to-member. This is similar to using a string in PHP or Python, but a pointer-to-member can be type-checked. Sometimes reified concepts get special syntax, sometimes ordinary type syntax is used (e.g. A (*)(B) vs Function<A, B>) – amon Jul 30 at 19:58
  • 1
    Your question is hard to follow, and I can't quite figure out why. I think it is because you use non-standard terminology for standard concepts and/or standard terms for other concepts than the ones they are typically used for. For example, I keep expecting the term "kind" to show up in your question and your subsequent comments, but it doesn't. For example, you seem to use the term "higher-order" in two different contexts, and I have the feeling that in one of those contexts, it should actually be "higher-kinded". Also, there seems to be some relation to dependent typing, but again, you … – Jörg W Mittag Jul 30 at 21:18
  • 2
    Just as an aside, your function declaration syntax is a bit painful. You have types before the names for parameters, but the type of the function itself comes at the end. That's inconsistent and hard to read. If you really want to do it well, just put types after the declarations in every case. Putting types at the start of declarations was a mistake of the C language, and virtually every statically-typed language outside of the C family puts the types at the end, so that declarations can be read in a simple, straight line, rather than a spiral. – Mason Wheeler Jul 30 at 21:50
  • 1
    I would recommend looking at Swift, Kotlin and Rust for some pretty good examples. They're modern languages with higher ordered functions, and have the benefit of foresight over the woes of C's batshit crazy spelling of function pointer types. – Alexander Sep 22 at 0:53
3

I consider an heresy to create a function, class, or attribute type, since they wouldn't be at the same logic-level than data types. This would also imply to have type type, which is even more confusing.

Yet a Type type is a staple of almost all object-oriented languages, and for good reason - it lets you treat type information objects, functors, and actual instances of objects similarly. Of course, there's nothing wrong with providing some syntactic sugar on the language level, for example:

function Sort<T, P>(List<T> list, .T - > P property, (P, P-> int) comparer) {
   ...

}

Sort(list, MyClass.Price, (p1, p2) -> return...) 

You can then treat property and comparer as special constructs... or simply have your compiler reduce it to a regular function taking objects:

function Sort<T, P>(List<T> list, Property<T, P> property, Function<P, P, int> comparer)...

That should give you a lot of features out of the box that you'd otherwise have to handle specially. Want to assign function to a variable? Just declare one of type Function<... > and do it. Want to make sure the property matches the comparer? Use the same type checking code. Want to map strings to functions to call? No problem, it's just an object map.

Bottom line: while on the language level you can absolutely use different syntax for all those cases, it'll help you greatly to reduce them to a common denominator as early as possible.

  • Also note that your attribute/property can very well be a function as long as you don't assign to it. From there you just have objects and functions, and you can go an OO route like in my answer, or a functional route like in Aaron's one. – Maciej Stachowski Jul 30 at 17:55
5

Many functional languages have simple solutions for describing function types. The most common is a syntax rougly like the following, which is used to describe the type of any expression:

expr: a where a is the type of the expression. If the expression has a type that is a function, it will be:

expr: a -> b where a is the parameter type and b is the return type. The signature for a sort function would be something like this:

sort: (List<a>, a -> b) -> List<a>

So, sort takes a List<a> and a function from a to b, where b is the type of the field upon which the list is being sorted, and returns a List<a>.

Now, in many functional languages, the concept of currying is employed, such that all functions take exactly one parameter. Any functions like sort which you might think of as taking two parameters are rewritten such that they take one parameter at a time and return a function taking the next parameter. That allows the type signature to look more like:

sort: List<a> -> (a -> b) -> List<a>

However, it is also generally common practice to put the most important parameter last, so you would rewrite sort like this:

sort: (a -> b) -> List<a> -> List<a>

The reason being, since each function takes one parameter and returns a function taking the next parameter you can "partially apply" a parameter like the field by which to sort and create a new function that sorts by that field which you can re-use, such as:

let sortByName = sort (item -> item.Name)

You can look at languages like Haskell and F# to see how having an entire language designed around higher-order functions is handled in the type system.

  • F# is derived from Ocaml (itself of the ML family). I recommed looking into ML instead. – Basile Starynkevitch Jul 30 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.