Mathematica workshop - worksheet 4

What happens when you press shift+enter?

Please don't send people copies of this worksheet. Instead, direct them to
http://j-star.org/mathematica_course.html
 where the latest version will always be available.
© Jony Hudson, Imperial College London, 2006-2011

We've covered a lot in the last three worksheets. We started with a crash-course in functional programming and the "Mathematica way". Then we looked at structuring our code and data. But we haven't got to the bottom of how Mathematica really works. That's the aim of this worksheet. It's a bit more computer-sciencey than the others - I hope that doesn't put you off - but I think it's pretty interesting stuff.

We're going to look more closely at what happens between you pressing shift + enter to start a computation and Mathematica returning an answer. This will give us further insight into how Mathematica differs from the more widespread programming languages, and how we can figure out what's happening when things go wrong.

First of all, let's recap what happens when you run a program written in C, C++, Fortran, Java, Python etc. When you start the program the computer starts executing the instructions, one by one (well, kind of), until it reaches the end. Your program is a list of instructions to the computer. For this reason these languages are referred to collectively as imperative languages.

Mathematica is completely different (surprise!). In Mathematica a program is typically a set of function definitions (supplemented by the squillions of built-in function definitions). Running a program is accomplished by asking Mathematica for the value of an expression. But how is that value obtained?

Well, this is where it gets a bit complicated! Mathematica is what might be called (Wolfram like this term) a multi-paradigm programming language. Remember my comment in the first worksheet about Mathematica being like "a rewrite system in LISP clothing, in Algol clothing"? This is what I was getting at. Although we haven't concentrated on it in these worksheets, one can write imperative style programs in Mathematica - lists of instructions, for loops, even gotos! We've looked at the functional-programming aspects of Mathematica extensively. So you might also call Mathematica a functional programming language. But what we're going to discover in this worksheet is that neither of these natures, functional nor imperative, are the real Mathematica. In fact, Mathematica is made of different stuff altogether - it's a rewrite system - and the other programming paradigms are "emulated" on top of that. If this all seems tremendously confusing: don't worry! We'll go through it step-by-step, starting at the top.

There aren't really any substantial exercises in this worksheet, but some of them are a little tricky. Don't be disheartened if you can't figure them out. Nothing in this worksheet is really essential for using Mathematica, but if you get through it you should have a better understanding of what's really going on.

Expressions have values

In Mathematica you don't really speak of running a program as you would in an imperative language, just asking for the value of an expression. Every expression has a value [this is a white lie - see if you can figure out why by the end of the worksheet] and typing it into Mathematica and pressing shift + enter will cause Mathematica to calculate that value. That's all Mathematica ever does. Here's a simple example:

1+1

The expression here is 1+1 and the value that Mathematica has calculated is 2. How about something more complicated?

∫(x^2)\[DifferentialD]x

How about this one?

Graphics[Circle[{0,0},(((1+1))^2)],ImageSize->100]

Here the expression is Graphics[Circle[{0,0},(((1+1))^2)]], but what is the value? Easy: the value is the circle that Mathematica plotted! But what does that mean? Is a circle a reasonable value for an expression to have? Well, yes, sort of. The Mathematica front-end can be told to use special rules to display certain values. The circle above is an example of that in action. More generally, this is how all graphics are handled. You can see the underlying raw form of the expression using InputForm:

//InputForm

As you've probably noticed, all values are also expressions. Are all expressions values? We'll get to that eventually. But first, some exercises.

Exercises

Easiest

This first one is pretty easy. Try evaluating the following expressions. Make sure in each case you understand what the value of the expression is.

Solution

Easy

Try evaluating a few expressions of your own. Make sure it makes sense.

Solution

The evaluation process

So Mathematica takes expressions and evaluates them. But how does it arrive at that value? We can use the function Trace to take a look.

(Sqrt[(((1+2))^3)+5])//Trace

We can see the evaluation being done step by step. How about if we involve functions?

f[a_]:=(a^4)
g[a_,b_]:=(((a+b))^2)
g[f[3],f[f[4]]]//Trace

Remove[f,g]

You can see that the evaluator first works out the values of the arguments to g, in the order that they appear, and then feeds in the evaluated arguments. To work out the second f it needs to repeat the process by evaluating the argument, which is another f. This system of descending through an expression by recursively evaluating the arguments in order and then the function is what a computer scientist would call strict, applicative-order evaluation (in the context of functions, at least).

How does Mathematica know, in general, that it's arrived at the value of an expression? (For instance, why did it stop at 4(Sqrt[2])in the example above?) The answer to that question will have to wait until we've looked at term-rewriting. It's the same as the answer to the question of whether all expressions are values.

Exercises

Watching the evaluator

Try using Trace to watch the evaluation of a few expressions. How does the evaluator deal with recursive expressions? Is everything as you'd expect it to be?

Solution

Functional programming, building the imperative

One of the things I want to clarify in this worksheet is the relationship between the different programming styles available within Mathematica. What we'll find at the end is that all of these different styles of programming are based on the same foundation. In this spirit, let's look at how we can build imperative style programming constructs out of one of the other programming aspects of Mathematica. We'll build using the one we've studied most closely: functional programming.

Compound expressions

I've been saying that all Mathematica does is calculate the value of expressions, which is different to the imperative style of giving a list of instructions. But you've most likely come across expressions of the form:

Remove[a,b,c];
a=Integrate[(((b+c))^3),c];
b=5;
c=6;
(Sqrt[a])

This certainly looks like a list of instructions. But is it? Let’s use FullForm to see what's really going on behind the scenes. Just like most other functions FullForm evaluates its arguments before using them. This isn't what we want here, so we’ll use the function Hold, which prevents evaluation of its argument.

Hold[
Remove[a,b,c];
a=Integrate[(((b+c))^3),c];
b=5;
c=6;
(Sqrt[a])
]//FullForm

What we see is that our list of instructions, like everything else in Mathematica is represented by an expression, in particular an expression with head CompoundExpression. Take a look at the help page for CompoundExpression. What it does is to evaluate its arguments in turn, evaluating to the value of the last expression. When we type in lists of instructions with semicolons we’re really just using a shorthand for CompoundExpression (much like /@ is a shorthand for Map). So, even though it might have looked like a list of instructions, it’s actually a function after all. The key thing, though, is that there’s no black magic here: CompoundExpression is just a function like any other. To prove this is the case ...

DIY

Write your own CompoundExpression function, myCompoundExpression, that evaluates its arguments in turn and returns the value of the last. Test it to make sure it does what it should.

Solution

Recursive functions

A recursive function is one that calls itself. The classic example is the following factorial function:

fact[n_]:=n fact[n-1]
fact[0]:=1
fact[5]

What's so interesting about these recursive fuctions? Well, they're an alternative way to think about programs. You've no doubt noticed that loops don't have to feature heavily in Mathematica. In fact, there isn't a single loop in any of my answers to the exercises. Do we need loops at all? The answer is no. You can do everything just with function calls, using them (and in particular, recursion) to generate program structure.

We get used to thinking of programs as lists of instructions for the computer to carry out, but we don't have to think like that - it's a product of learning nothing but imperative programming languages from an early age. We can also think about programs as mathematical structures - in this case chained sequences of function calls (this structure can be formalised and is called the λ-calculus - we'll come back to this later). Often, this lets us state our problem much more clearly than if we try and write a sequence of step-by-step instructions. It also lets us more easily use the tools of mathematics and logic to reason about computer programs. That's one of the reasons that languages like Lisp, ML, Scala, Haskell and Mathematica are interesting from a computer science perspective.

Let's make that change of viewpoint clearer by rewriting some of the familiar imperative programming constructs.

Do loop

Imagine that, perhaps because of some managerial oversight, the Do command had been omitted from Mathematica (read the documentation page on Do if you're not familiar with it). Write your own function myDo without using any other explicit looping constructs.
Hint: you might want to simplify by only implementing the Do[expr,{(Subscript[i, max])}] case.
Hint 2: you will want to read about HoldFirst if you're not already familiar with it.

Solution

Length

Imagine Mathematica had no built in function to count the number of elements in a list (i.e. Length was missing). Write a function that does just that.
Hint: this is a section on recursion!
Hint 2: the function Rest will be useful.

Solution

Functional looping

As I said above, when writing in the functional style you rarely use loops. You might think that this is all a big cheat - we write our programs in this fancy "no loop" style, but we use things like Map all the time. Surely that's just using a loop by a different name? Surely not! Try the following exercise.

What about if there wasn't a built in Map function? Implement one.
Hint: recursion! No loops allowed here.

Solution

The mighty Fold

Fold is one of the most wonderful functions. You should read the documentation for it, which doesn't really make it clear what it's useful for. It's real significance is that it captures a very common recursive programming idiom: doing something over and over, where the result of one step is fed in to the next step. Here are a couple of examples:

Factorial

facFold[n_]:=Fold[#1 #2&,1,Range[n]]
facFold[6]

[Note that there are simpler ways to define factorials, not least the built-in function Factorial!]

Applying lists of transformations to matrices

Fold[#2.#1.((#2)^T)&,ρ,{(Subscript[U, 1]),(Subscript[U, 2]),(Subscript[U, 3]),(Subscript[U, 4])}]

Sum and product

Write functions, using Fold, to sum the elements of a list and to calculate the product of the elements of a list.
Note: these functions are, of course, redundant.

Solution

Exercise

Try and work a Fold into your code one day. It's a rite of passage for anyone who wants to say they are an expert functional programmer.

Term-rewriting systems

Right. We've seen above that, with sufficient motivation, we could implement the imperative programming constructs in Mathematica on top of the functional constructs that we've been learning about in these worksheets. [Well, we've partially seen it - you'll have to use your imagination a bit.]  But we haven't got to the bottom yet. Here are a few nagging questions:

How does Mathematica do algebra?
Are all expressions values?
How does Mathematica know when it's finished evaluating an expression and reached its value?
Why do function defitions have those annoying underscores after the parameters?

To answer them all we'll have to learn about another model of computation: term rewriting systems. A term rewriting system is, roughly speaking, a set of specifications that define a thing called a term and a set of rules for transforming those terms into other terms.

Terms

To define terms one typically starts with a set of function symbols (collectively referred to as a signature). Function symbols can be defined to take zero or more parameters (this number is usually called the symbol's arity). Terms are defined inductively as combinations of these functions and other terms. For example consider the signature:

e[]
i[_]
g[_,_]

Where the underscores are supposed to represent the arity of the symbol. The 0-ary symbol e can be thought of as a constant. Valid terms under the above signature would be things like:

g[i[e[]],e[]]
g[g[e[],e[]],i[g[e[],i[e[]]]]]

You'll notice that this general structure is exactly the same as Mathematica's uniform expression structure. We can introduce the idea of variables, which can stand for any term, allowing us to write terms like.

g[x_,i[x_]]

Where x_ is a variable. I'm following the Mathematica rules for defining variables by appending an underscore. We'll see what this really means in a minute. [Note: often people drop the brackets from 0-ary functions (like e[]) above, but I'll keep them to emphasise the difference between these constant symbols and variables.]

Rewrite rules

To do any computation with these terms we need to have some way of modifying them. For that, we use rewrite rules. The rules match against a term, or part of a term (sub-term), and replace it with something else. For instance, using the terms defined above we could write rules like:

g[e[],e[]]->e[]

The arrow indicates that the rule is directed. We can allow variables in rules too, for instance:

g[x_,i[x_]]->e[]

Power, confluence, termination, normalisation

The, perhaps surprising, thing about such term-rewriting systems that makes them relevant to us is that they are Turing-powerful: they can be used to compute anything that a universal Turing machine can (and by extension, anything you can work out in any programming language on any reasonable computer). One comes up with a set of rules and an initial term, and the act of reducing this term can be made to effect any computation one wishes (with a suitable interpretation of the terms). We'll take a look at this in more detail later.

There are many interesting questions [answers] related to these term-rewriting systems. Will the reduction (the successive application of rules) ever terminate? [sometimes], can we tell if a given set of rules will terminate? [undecidable, in general], does it matter what order we apply the rules? [sometimes, a system is called confluent if the order is unimportant], can we tell if a system is confluent? [undecidable, in general], is the idea of a term general enough to capture all algebraic structures? [yes]. There's a significant literature considering these questions and more. If you want to get started into it the book "Term rewriting and all that" gives a good overview.

But rather than consider these questions formally in this worksheet, let's get on and start implementing some rewrite systems in Mathematica. To do that we'll need to learn about the pattern matcher.

The pattern matcher, rules, transformations

If you're going to build software to implement term-rewriting systems the tricky bit is the left hand side of the rules. The problem is, how do you tell if a given term matches the left hand side of any of the rules. [This problem is called the "word problem" in the computer science literature.] The heart of Mathematica is a powerful and fast pattern matcher for solving this problem.

Patterns

A pattern is a way of specifiying something about a Mathematica expression without specifying everything. The material patterns are built from are called blanks. There are three kinds: _ means any one thing; __ means any non-zero number of things; and ___ means any number of things including zero (i.e. no thing).

The function Cases will select the items from an expression that match a given pattern.

Cases[{1,2,3,a,b,c},_]

Here the blank pattern matches all of the elements of the list. We can give a blank a name by prepending it to the underscore(s). In the next example I use this to match pairs of identical items in a list by using the same blank twice in the pattern. I can only do this because I gave it a name.

Cases[{{1,1},{b,b},{a,b},{π,π}},{q_,q_}]

We can use these patterns to write the rewrite rules that we described above. The function Rule takes two arguments: a pattern, the left hand side; and what to replace any matches with, the right hand side. The functions ReplaceAll applies rules to an expression. It's usual to write rules using the infix operator -> and ReplaceAll with the infix operator /. as in the following. This rule transforms anything into jony, so the expression is transformed into jony:

(x^2)/._->jony

This rule matches anything that is squared and replaces it:

(z^2)+(b^3)+f/.((_)^2)->squareWasHere

By naming the matched element we can transform it. This removes squares:

(x^2)+(y^2)+(z^2)/.((v_)^2)->v

We can start to guess how Mathematica does symbolic maths. In a moment we'll write a simple symbolic differentiator.

An important point to note when transforming expressions is that the pattern matcher attempts to match first against the expression and then against each sub-expression. This can sometimes cause confusion. Consider the following:

{{1,1},{2,2}}/.{n_,n_}->h

This works as expected, replacing each element that is a repeated pair with h. If we try it on this list though:

{{1,1},{1,1}}/.{n_,n_}->h

We see that the outer list itself matches the pattern. This provides a good excuse to introduce another feature of Mathematica's pattern matcher, pattern constraints. These constraints are expressed with /; as follows (AtomQ returns True if its argument is an atom):

{{1,1},{1,1}}/.{n_,n_}/;AtomQ[n]->h

While I'm introducing new features, let's introduce one final feature, ReplaceAllRepeated, usually written //. which applies the rules to the expression over and over until it no longer changes. As we'll see, this is very significant idea.

{{1,1},{2,2}}//.{n_,n_}->h

Patterns are absolutely central to everything you do in Mathematica. Look at the following definitions and Rules.

f[x_]:=(x^2);
f[x_]->(x^2);
aaa=2;
aaa->2;

They look pretty similar, right? Definitions in Mathematica are nothing more than rules which are stored in a global store and tested for a match every time anything is evaluated. We'll look at this further shortly.

But even without wondering about how Mathematica's innards work, you still confront patterns all the time, on the left-hand-side of function definitions. Now that we've learned how sophisticated patterns can be, we can do a significant amount of the computation on the "left-hand-side" of the function definition. You see this style a lot in some of the functional languages (ML in particular). I find it slightly mind-boggling. Here are some exercises to illustrate.

Map again

Rewrite your recursive Map function, but this time imagine that Mathematica had no First, Rest, Last or [[ ]] (Part) functions.

Solution

Length again

Rewrite your recursive Length function with the above restrictions.

Solution

Largest element

Write a function that returns the largest element of a list that you give it. Put the logic "on the left". By this I mean, your solution should not have any comparisons (>, <) on the right of the equals sign. This is quite hard!
Hint: you'll almost certainly want to write a recursive function.
Hint 2: you'll want to use pattern constraints.

Solution

Differentiate!

Let's implement that symbolic differentiator that we talked about. We'll use the function symbol dd[ arg, z] to represent the derivative of arg  with respect to z. Let's implement rules that differentiate powers of a variable. We'll give them a name so that we can apply them later.

polyDiff={
dd[((z_)^(n_)),z_]->n (z^(n-1)),
dd[z_,z_]->1,
dd[a__,z_]/;FreeQ[a,z]->0
};

Here it is in action. The last rule takes care of (x^0) (and, in fact, all constants).

dd[(x^5),x]/.polyDiff

Define some rules to differentiate sine and cosine. Test them.

Solution

Polynomials

It would be nice if we could differentiate polynomials. To do that we need to add a rule expressing the linearity of a derivative.

diffLin={
dd[a_+b__,z_]->dd[a,z]+dd[b,z]
};

To apply both all of the rules at once we join them together in a list. Notice that I'm using the //. operator which applies the rules over and over again until the expression doesn't change any more.

dd[(x^3)+(x^2),x]//.Join[polyDiff,diffLin]

Our polynomials don't yet have coefficients in front of the powers. Try to add some rules to support this. Test it out.
Hint: product rule.

Solution

Values are fixed points!

So, now, after all that we can finally say what's really going on. We've seen above that definitions using = look an awful lot like rules defined using -> . And that's really all they are. Whenever you define a function Mathematica stores it as a rule in a global store (actually there are several stores, but it's not so important right now). When you press shift and enter Mathematica takes your expression and matches it against all of the definitions in the global rule store, transforming over and over again until the expression no longer changes. Just like //. does for explicit lists of rules. This let's us answer our above questions:

Are all expressions values? No. Values are expressions that are also fixed points of the current set of definitions.
How does Mathematica know when it's reached a value? When the expression no longer changes under application of any of the definition rules. 

And that's it. Now you understand the Mathematica evaluation process!

 [For the sake of correctness, I should point out the above description is somewhat simplified. There are several other steps in the evaluation process - you can find them all in the Mathematica book - but the bit described above is the big idea.]

Term rewriting, building the functional

There's just one more detail to tie up before we can say that we really understand how the different programming styles in Mathematica fit together.

We've seen above that functions are stored as rules in a global store. But what we haven't yet done is capture the essence of functions. What do I mean by the essence of functions? Well, I'd say a function is something that can take some arguments and be applied. To fully understand how functional programming constructs can be built on top of term-rewriting we need to capture this essence as a set of rewrite rules.

This is very confusing

For brevity, and sanity, we won't attempt to work out all the details of function application. If you want to know all of the gory details you should read about Church's lambda calculus, which formalises the idea of a function. What we'll do here is implement a part of that calculus, the so-called β-reduction.

What we want to do is be able to define functions (note very well that these "functions" are not the same as the "function symbols" that we talked about when defining terms. Confusingly we will denote our functions by a single function symbol - because we have to). I want to be able to express, for example, that I have a function of a, whose right hand side is a b, I could write it like this:

λ[a, a b]

I'm using the function-symbol λ to denote a function in the functional programming sense. To give this meaning I want to define expressions like the following:

λ[a, a b][c]

to have value

c b

This reduction, replacing all of the occurences of a in the function body with the function argument c is the β-reduction. [Those of you who know the lambda calculus will probably be weeping now, as in Mathematica juxtaposition means multiplication. We have to work much harder if we really want to implement λ-calculus. Still, the idea is there.] This reduction could be said to be the essence of a function.

Write a rewrite rule to carry out the β-reduction, call the rule βreduce. Test it to make sure it works.
Hint: you might need to learn about :>, a.k.a RuleDelayed.

Solution

Building them in

This kind of fouls up our kernel, but we can build the β-reduction rule into Mathematica by issuing it as a definition (figure out how this next line works!):

SetDelayed@@βreduce

And now we can use our λ-functions just like built in pure functions!

λ[q,q+3][λ[a, (a^2)]/@{1,2,3}]

Cool, no?

Remove[λ]

Building mathematics

Once you get into building mathematical structures, it's hard to stop. It's just so much fun! Let's try a few more.

Peano integers

So, imagine you've bought the "Mathematica cheapskate edition" and you're horrified to learn that it doesn't come with support for the integers. It's no problem though, you can just add your own!

The basic thing about integers is that there always a next one. This motivates us to define the integers as expressions like this

s[s[s[s[s[s[e[]]]]]]]

where e[] represents zero, and s[a] represents the successor of the integer a. So we'd like to think of the number above as 6. To give these expressions meaning we need to implement addition on them in a way that respects the rules of arithmetic.

Plus

Write a set of rewrite rules that take expressions like plus[a, b] where a and b are integers and transform it to the sum. Test your rules.
Hint: the rules will generate a recursive structure.
Note: this is not the most efficient way to implement integer operation. Check your CPU manual to see if it includes special-purpose hardware.

Solution

Times

Write a set of rewrite rules that take expressions like times[a, b] where a and b are integers and transform it to the product. Test your rules. Make sure that times and plus work together in combination.
Hint: you can use the plus you defined above.

Solution

Groups

The signature I used above when introducing term-rewriting is that of a group. There's a identity element e[], a unary function that represents the inverse of an element i[_], and a binary group operation g[_,_]. Give meaning to terms over this signature by implementing a set of rewrite rules that capture the group laws. Make sure you can transform a simple group expression correctly.

Solution

Sacrificing termination

Your rules are directed, but the group laws are identities. Meaning that it’s ok to replace the LHS of a group identity with the RHS, but also vice-versa. How do we deal with this? The approach we' ve used thus far is to always use terminating sets of rewrite rules where the RHS was simpler than the left. This naturally tends to simplify terms which, in the context of computer algebra, is usually what we want.

This approach works well for the simple structures we've studied above but falls apart rapidly for complicated expressions. Another approach is to include more rewrite rules, so that any two identical expressions can be reached through successive application of the rules (i.e. the minimal set of rules whose transitive closure is the set of identities). The rewrite system will no longer, in general, terminate so we can't use //. to effect our transformation. Rather we need to use a search strategy. The built in function FullSimplify does exactly this, with the search goal of reducing the size of the expression as much as possible [you can plug in your own, alternative, search goals if you like].

FullSimplify takes the rules in a rather odd form. You need to define a function whose argument is the LHS of your rule, and whose RHS is the RHS of your rule. Here are the first couple of my ruleset - I've given them names gl1, gl2 ...

gl1[g[e[],x_]]:=x;
gl2[g[x_],e[]]:=x;

Complete the ruleset.

Solution

Simplify

Make sure that following expression simplifies to the identity.

g1=g[a,g[b,g[g[c,d],g[g[g[i[d],g[e[],i[g[a,g[i[a],c]]]]],i[b]],i[a]]]]]

You feed the rules to FullSimplify like this :

FullSimplify[expr,TransformationFunctions->{gl1,gl2}]

Solution

Summary, from the ground up

So, there we have it. We've seen that the heart of Mathematica is a term-rewriting engine. On top of this other programming paradgims are impersonated. We've see how we could implement some of the primitives for our own imperative impersonation layer. And we've written the basis of our own functional programming layer, by implementing one of the lambda calculus reduction rules. We've even started to reimplement basic mathematics. I think you can confidently say that you know how Mathematica works now!

I think that this foundation, which unifies all of the aspects of Mathematica, is its nicest feature. It lets you write code that does computer algebra, numerical computation, graphics etc in a comfortably seam-free way!

Playtime

Writing an If

The If command has gone missing (read the documentation page on If if you're not familiar with it). And further imagine that there is no Switch or Which. Try writing your own If function. Does it work? Call it myIf for compatibility with the next exercise.
Hint: one way to do it is to use the ReplaceAll (/.) operator to transform the predicate into an array index.

Solution

Really?

Try out your If on the following expression. Are you really sure it works?

myIf[True,RandomReal[{0,1},3 (10^7)],RandomReal[{0,1},3 (10^7)]];//AbsoluteTiming

Compare this to the built in If. If there's a difference can you figure out what's going on? Any idea how to fix it?

If[True,RandomReal[{0,1},3 (10^7)],RandomReal[{0,1},3 (10^7)]];//AbsoluteTiming

The answer is in the help page for If! You might also like to take a look at the HoldRest attribute.

Ackermann function

A historically significant function in the history of computability theory is the Ackermman function, defined as

A(m.n)=(Piecewise[{{n+1, if m=0}, {A(m-1, 1), if m>0 and n=0}, {A(m-1,A(m,n-1)), if m>0 and n>0}}]) .

Implement this function and try and understand what it's doing. Work out a few values by hand.

See if you can evaluate the value of A(4,1). My implementation does it a second or so, but I'll bet yours doesn't! Why not? Try to figure out what's going on and fix it.
Hint: memoization.

Solution

Recursive pure functions?

Can you write a recursive pure function? Try writing a pure function that calculates the factorial recursively, as above
Note: I know of two ways to solve this problem. One is, to the best of my knowledge, unique to Mathematica.
Hint: As for the second way. If you've solved this on your own then you either knew the answer already, cheated, or are preternaturally intelligent. All others should Google "applicative-order Y-combinator" if interested.

Solution