Function which returns itself

Question

As a purely academic exercise (read "because I have no life"), I'm trying to write a function f which accepts another function g, executes g for its side effect, and returns itself.

So I have this:

let rec f g x =
    ignore(g x)
    fun y -> f g y

F# complains:

      fun y -> f g y;;
  -------------^^^^^

C:\Users\Juliet\AppData\Local\Temp\stdin(8,14): error FS0001: Type mismatch. Expecting a
    'a    
but given a
    'b -> 'a    
The resulting type would be infinite when unifying ''a' and ''b -> 'a'

If it works the way I intend, then I could write:

let printer = f (printfn "%s")
printer("this")("is")("so")("useless")("its")("awesome!")
// prints:
//    this
//    is
//    so
//    useless
//    its
//    awesome

Is it possible to write a function like this?

Answer 1

No, the static types can't work out. (Maybe if there were infinite types, but there's little practical use for that in a statically-typed language.)

You can do this though:

type Inf<'T> = Inf of ('T -> Inf<'T>)  // '
    with member this.App x =
            match this with Inf(f) -> f x

let rec f g x = 
    g x
    Inf(fun y -> f g y)


let printer = f (printfn "%s") 
printer("this").App("is").App("so").App("useless").App("its").App("awesome!") 

Answer 2

Well, I don't know about F#, but in PostScript you can do:

/quine {
    [ exch {exec [} aload pop
        [ 3 index
            {exec [ aload 7 1 roll ] cvx} aload pop
        ] cvx
        {aload 7 1 roll ] cvx} aload pop
    ] cvx
} def

This is a quinemaker, which when applied to a procedure, returns an executable quine, which is analogous to the conventional quine (a program that prints out its own source code). The executable quine does something and returns itself. Like the conventional quine, in which referencing the filename of the source code is considered cheating, the executable quine would be cheating if it referenced its own name within its body.

Since the above doesn't use any variables at all, not even locally, it makes legit quines. ^_^ (Of course, local variables are acceptable, but you don't always need them in PostScript.) It seems that almost all of the other solutions to this question are cheating by using named recursion or the this construct. :/

You can give this a procedure such as count and then exec the output any number of times:

{count} quine                              % make an executable quine
exec exec exec exec exec exec exec exec    % execute it eight times
pop pstack                                 % remove it from stack and print stack

This program prints out the integers from 7 to 0, counting down. There aren't even any numbers in the program source.

Executable quines for the win!

The equivalent for your example would be

(awesome!) (its) (useless) (so) (is) (this)
{=} quine
exec exec exec exec exec exec

As a bonus, here is a recursive infinite loop in PostScript (the iterative version is just {} loop):

[{[aload 8 1 roll] cvx exec} aload 8 1 roll] cvx exec

To stream an infinite list of pseudorandom integers to stdout, do

[{rand = [aload 8 1 roll] cvx exec} aload 8 1 roll] cvx exec

In fact, this infinite loop is nothing more than an auto-executing executable quine. So we can modify the quinemaker to do this:

/autoexecquine {
    [ exch {exec [} aload pop
        [ 3 index
            {exec [ aload 8 1 roll ] cvx exec} aload pop
        ] cvx
        {aload 8 1 roll ] cvx exec} aload pop
    ] cvx
} def

Then it's possible to run printer("this")("is")("so")("useless")("its")("awesome!") as PostScript code. Yes, in prefix style. You didn't think prefix style was possible in PostScript? Think again.

/printer
{
    {currentfile token {1 1 index length 2 sub getinterval =}{quit} ifelse}
    autoexecquine exec
} def

printer("this")("is")("so")("useless")("its")("awesome!")

Running this in the GhostScript shell, after defining autoexecquine and printer:

GS>printer("this")("is")("so")("useless")("its")("awesome!")
this
is
so
useless
its
awesome!

Note that this is a hack that reads data from the current file (stuff not yet processed) and operates on it, instead of what's already on the stack. It won't work when embedded in a function.

Answer 3

It's pretty simple in python:

def magic(f, arg):
    f(arg)
    return lambda arg: magic(f, arg)

Here's a usage example:

import sys
def prnt(x): 
    sys.stdout.write(x)

printer = magic(prnt, "")

printer("hello ")("world")

Answer 4

hi,

ok I know this is not f#, but in python it is very easy:

def printer(str):
    print str
    return printer

so if you call it:

printer("this")("is")("so")("useless")("its")("awesome!")
this
is
so
useless
its
awesome!
<function printer at 0x8a6ae9c>

Answer 5

ocamlc does not accept

let rec f g x =
ignore(g x) ;
fun y -> f g y

but ocamlc -rectypes does. OCaml's -rectypes option amounts more or less to disabling the occur-check in the unification algorithm while type-checking.

This feature has a typical history: the behavior was introduced at the same time as objects because it was needed to type them. Later it was noticed that the behavior confused users: often, typing error messages were only printed far after the mistake. So recursive types were disabled for non-object values. Enough users had already found uses for them, though, that by complaining loudly they obtained the option to have recursive types to be introduced again in a third version.

Morality: think twice before you introduce new features, because people will use them

Answer 6

To add some details to Brian's answer, the problem is that the type definition is recursive. A simpler case would be a function that takes unit, does some side-effect and returns itself (this won't compile):

let rec foo () = printf "called"; foo

The compiler infers the following information about the types:

foo : unit -> ´a
´a = unit -> ´a   // This doesn't have (finite) solution in F#

One way to deal with this kind of limiation is to support recursive types. In theory you can define a recursive type using μ (which is a bit like lambda abstraction). When you write μt.<some type expression> it means that you're defining some type and t can be used to recursively refer to that type inside its definition.

For example a list would be defined as μt.unit + (int * t) ("+" denotes discriminated union and "*" denotes a tuple). Here, the value is either unit (empty list) or a cons cell, which is a tuple containign integer and the list itself.

The type of my sample function using this notation is μt.unit -> t. The problem is that the way types are handled in F# (and OCaml/Haskell) doesn't really allow you to write this type without giving it an explicit name (which is essentially what Brian does). In F#, the name cannot be a type alias, but an explicit type declaration. As Pascal mentions, in OCaml, it can be type alias if you provide -rectypes flag. There are some useful information about recursive types on Wikipedia.

That's my purely academic answer to a purely academic question!

Answer 7

Juliet: The type system is getting in your way. Switch to Scheme and you can have some fun, although the fact that functions are not Curried is annoying:

-> (define f (g x) (begin (g x) (lambda (y) (f g y))))
f
-> (val it (f not 3))
<procedure>
-> (it print 99) 
error: expected 1 but found 2 arguments in (it print 99)
-> (f print 99)
99
<procedure>
-> 

P.S. Get a life :-)

Answer 8

Well, I'll cheat and use Scala ... because I don't F# :-) I also cheat and don't use the 'short' notation which doesn't allow recursive types AFAIK.

case class F[T](g: (T) => Unit) extends Function1[T,F[T]] {
 def apply (s: T): F[T] = { g(s); this }
}
>> defined class F
F((s: String) => println(s))("a")("b")("c")
>> a
>> b
>> c
>> res4: F = <function>

It's been awhile, but I believe I've done this in SML before -- see how Lazy Sequences can be implemented. (I may have returned a new function, not the same one, or supplied extra typing. It's been forever and I'm forgetful.)

Answer 9

My haskell isn't excellent, but I assume this is equivalent:

f g x = g x >> f g

It fails, however. "Occurs check: cannot construct the infinite type: b = t -> b" I'm not surprised to see F# fail similarly. With a statically-typed language, it makes fundamental sense why you can't have infinite types.

I do kind of like the haskell code, though. It has a certain zen-like quality to it.

Answer 10

I'm not sure if I'd call this a quine since it doesn't return it own "source code" but rather an instance of itself. It's more of a chain maker (from function chaining). A simple implementation in Javascript would be:

function chain (f) {
  return function () {
    f.apply(this,arguments);
    return arguments.callee;
  }
}

usage:

g = chain(function(x){alert(x)});
g("this")("is")("so")("useless")("its")("awesome!");

Also, I'm almost certain this is some sort of combinator. Not quite the Y combinator but something like it.

Answer 11

Okay, here's a Haskell version that actually works.

f g = F $ \x -> g x >> return (f g)

newtype F a = F { runF :: a -> IO (F a) }
f $$ x = f >>= ($x) . runF

The combinator unwraps IO and F so the end syntax isn't too clumsy. It now returns the actual result of the function application, instead of cheating and returning the original function as it used to ;)

Sample use:

printer = return (f putStrLn)
*Main> printer $$ "this" $$ "is" $$ "so" $$ "useless" $$ "it's" $$ "awesome!"
this
is
so
useless
it's
awesome!

That was with the question's intended meaning, where the returned function is the one that always applies the initial argument one, with whatever arguments are repeatedly applied.

My first interpretation was that a new function was provided at each application. This is still possible, by providing an action of id:

sequencer = return (f id)

*Main> sequencer $$ putStrLn "Press return" $$ (getLine >> return ()) $$ putStrLn "Thanks!"
Press return

Thanks!

Answer 12

As others have pointed out, this works fine in a dynamically typed language. One approach I haven't seen suggested so far is to use F# as a dynamic language (using boxing and unboxing):

let rec f g x =
  g x
  box (f g)

let printer = f (printfn "%s")

let (<?) f x = (unbox f) x

printer <? "this" <? "is" <? "so" <? "cool" |> ignore

We need the (<?) combinator here because F# won't allow us to directly apply an obj to a value, but otherwise this is pretty faithful to your original formulation.

Answer 13

OK, it took me a while, but here's the anonymous recursive definition of the quinemaker in (Guile) Scheme:

(define (quine f)
  (primitive-eval
   (quasiquote
    (lambda (z)
      ((unquote f) z)
      (primitive-eval
       ((lambda (x) (let ((y (copy-tree x)))
              (set-cdr! (cadr (cadddr y))
                (list (list (quote quote) x)))
              y))
    (quote
     (lambda (z)
       ((unquote f) z)
       (primitive-eval
        ((lambda (x) (let ((y (copy-tree x)))
               (set-cdr! (cadr (cadddr y))
                     (list (list (quote quote) x)))
               y))))))))))))

Here's the printer function:

(define printer
  (quine (lambda (x) (display x) (newline))))

In action:

guile> ((((((printer "this") "is") "so") "useless") "its") "awesome!")
this
is
so
useless
its
awesome!
#<procedure #f (z)>

Answer 14

I was able to get this to work using F#'s famous cousin, C#.

// a function that takes an argument of type T and returns:
//     a function that takes an argument of type T and returns:
//         a function that takes an argument of type T and returns:
//             a function that ... (etc.)
public delegate FuncFunc<T> FuncFunc<T>(T arg);

// creates a FuncFunc<T>, which is a function that ... (see above)
// having side effects specified by the given Action<T>
static FuncFunc<T> CreateFuncFunc<T>(Action<T> sideEffects)
{
    return x => {
        sideEffects(x);
        return CreateFuncFunc(sideEffects);
    };
}

Little example program:

public class Program
{
    static void Main(string[] args)
    {
        var printer = CreateFuncFunc<string>(s => Console.WriteLine(s));

        printer("This")("Is")("Pretty")("Ridiculous");

        int sum = 0;
        var adder = CreateFuncFunc<int>(i => { sum += i; Console.WriteLine(sum); });

        adder(1)(2)(3)(4)(5);
    }
}

Output:

This
Is
Pretty
Ridiculous
1
3
6
10
15

Answer 15

You can do this in C++. It's called chaining. You have to use a function-object though.

class fun{
 void(action*)(std::string); //your action
 fun(void(a*)(std::string)){action=a;}
 fun operator()(std::string s){
  a(s); return fun(a);}
};

This is a pretty common idiom in boost::spirit.

Answer 16

The magic is possible!

In this answer, I will show that it is actually possible to answer the full question, i.e. provide a function f that takes another, effectful function and repeatedly returns itself while staying completely immutable, statically typed and nevertheless using nothing but plain functions; no objects and usual calling syntax.

Is it turns out, all that's needed is a type system that is powerful enough to statically infer what is done.

Typeclasses as used in Haskell are just a powerful notation for generics. When using generics as the functions return type, f can terminate or return itself when a function is needed for further calls being made.

It's all about the type system!

Using ghci:

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}

class Variandic a r where
    f :: (a -> IO ()) -> a -> r
    auxIO :: (a -> IO ()) -> IO () -> r

instance Variandic a (IO ()) where
    f op x = op x
    auxIO op = id

instance Variandic a r => Variandic a (a -> r) where
    f op x = \next -> auxIO op (op x >> op next)
    auxIO op x = \next -> auxIO op (x >> op next)

And usage looks like this:

-- Somewhat advanced hello world
main :: IO ()
main = do
  let printer = f putStr -- Putting strings ...

  printer "Hello" ", " "World"

Code like

printer "a" 42

will of course fail for being mistyped.

Voilà

Answer 17

Solution in C++:

First, we declare a class that lets us return a self referential function pointer. (Based on this, although I didn't like the Coda...)

#include <boost/function_types/function_type.hpp>
#include <boost/function_types/parameter_types.hpp>
#include <boost/mpl/push_front.hpp>

template<class F>
struct FuncPtr {
  typedef F func_type;
  typedef typename boost::function_types::function_type<typename boost::mpl::push_front<boost::function_types::parameter_types<F>, FuncPtr<F> >::type>::type* type;

  FuncPtr( type pp ) : p( pp ) { }
  operator type() { return p; }
  type p;
};

Then, we declare our functions:

template<class F>
FuncPtr<void(*)(F)> f(F func)
{
  func();
  return f;
}

void g()
{
  cout << "Hello" << endl;
}

and then, if we call it a little bit like this:

typedef FuncPtr<void(*)(void(*)())>::type FunkyFuncPtr;
FunkyFuncPtr x = f(g);
x = x(g);
x = x(g);

then the output looks like this:

Hello
Hello
Hello