text:
# Fixed-point combinator

In mathematics and computer science in general, a fixed point of a function is a value that is mapped to itself by the function.

In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator)[1]: page 26  is a higher-order function ${\displaystyle {\textsf {fix}}}$ that returns some fixed point of its argument function, if one exists.

Formally, if the function f has one or more fixed points, then

${\displaystyle {\textsf {fix}}\ f=f\ ({\textsf {fix}}\ f)\ ,}$

and hence, by repeated application,

${\displaystyle {\textsf {fix}}\ f=f\ (f\ (\ldots f\ ({\textsf {fix}}\ f)\ldots ))\ .}$

## Y combinator

In the classical untyped lambda calculus, every function has a fixed point.

A particular implementation of fix is Curry's paradoxical combinator Y, represented by

${\displaystyle {\textsf {Y}}=\lambda f.\ (\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\ .}$[2]: 131 [note 1][note 2]

In functional programming, the Y combinator can be used to formally define recursive functions in a programming language that does not support recursion.

This combinator may be used in implementing Curry's paradox. The heart of Curry's paradox is that untyped lambda calculus is unsound as a deductive system, and the Y combinator demonstrates that by allowing an anonymous expression to represent zero, or even many values. This is inconsistent in mathematical logic.

Applied to a function with one variable the Y combinator usually does not terminate. More interesting results are obtained by applying the Y combinator to functions of two or more variables. The second variable may be used as a counter, or index. The resulting function behaves like a while or a for loop in an imperative language.

Used in this way the Y combinator implements simple recursion. In the lambda calculus it is not possible to refer to the definition of a function in a function body. Recursion may only be achieved by passing in a function as a parameter. The Y combinator demonstrates this style of programming.

## Fixed-point combinator

The Y combinator is an implementation of a fixed-point combinator in lambda calculus. Fixed-point combinators may also be easily defined in other functional and imperative languages. The implementation in lambda calculus is more difficult due to limitations in lambda calculus. The fixed-point combinator may be used in a number of different areas:

Fixed-point combinators may be applied to a range of different functions, but normally will not terminate unless there is an extra parameter. When the function to be fixed refers to its parameter, another call to the function is invoked, so the calculation never gets started. Instead, the extra parameter is used to trigger the start of the calculation.

The type of the fixed point is the return type of the function being fixed. This may be a real or a function or any other type.

In the untyped lambda calculus, the function to apply the fixed-point combinator to may be expressed using an encoding, like Church encoding. In this case particular lambda terms (which define functions) are considered as values. "Running" (beta reducing) the fixed-point combinator on the encoding gives a lambda term for the result which may then be interpreted as fixed-point value.

Alternately, a function may be considered as a lambda term defined purely in lambda calculus.

These different approaches affect how a mathematician and a programmer may regard a fixed-point combinator. A lambda calculus mathematician may see the Y combinator applied to a function as being an expression satisfying the fixed-point equation, and therefore a solution.

In contrast, a person only wanting to apply a fixed-point combinator to some general programming task may see it only as a means of implementing recursion.

### Values and domains

Every expression has one value. This is true in general mathematics and it must be true in lambda calculus. This means that in lambda calculus, applying a fixed-point combinator to a function gives you an expression whose value is the fixed point of the function.

However, this is a value in the lambda calculus domain, it may not correspond to any value in the domain of the function, so in a practical sense it is not necessarily a fixed point of the function, and only in the lambda calculus domain is it a fixed point of the equation.

For example, consider

${\displaystyle x^{2}=-1\Rightarrow x={\frac {-1}{x}}\Rightarrow f\ x={\frac {-1}{x}}\land {\mathsf {Y}}\ f=x}$

Division of signed numbers may be implemented in the Church encoding, so f may be represented by a lambda term. This equation has no solution in the real numbers. But in the domain of the complex numbers i and -i are solutions. This demonstrates that there may be solutions to an equation in another domain. However, the lambda term for the solution for the above equation is weirder than that. The lambda term ${\displaystyle {\mathsf {Y}}\ f}$ represents the state where x could be either i or -i, as one value. The information distinguishing these two values has been lost, in the change of domain.

For the lambda calculus mathematician, this is a consequence of the definition of lambda calculus. For the programmer, it means that the beta reduction of the lambda term will loop forever, never reaching a normal form.

### Function versus implementation

The fixed-point combinator may be defined in mathematics and then implemented in other languages. General mathematics defines a function based on its extensional properties.[3] That is, two functions are equal if they perform the same mapping. Lambda calculus and programming languages regard function identity as an intensional property. A function's identity is based on its implementation.

A lambda calculus function (or term) is an implementation of a mathematical function. In the lambda calculus there are a number of combinators (implementations) that satisfy the mathematical definition of a fixed-point combinator.

### What is a "combinator"?

Combinatory logic is a higher-order functions theory. A combinator is a closed lambda expression, meaning that it has no free variables. The combinators may be combined to direct values to their correct places in the expression without ever naming them as variables.

## Usage in programming

Fixed-point combinators can be used to implement recursive definition of functions. However, they are rarely used in practical programming.[4] Strongly normalizing type systems such as the simply typed lambda calculus disallow non-termination and hence fixed-point combinators often cannot be assigned a type or require complex type system features. Furthermore fixed-point combinators are often inefficient compared to other strategies for implementing recursion, as they require more function reductions and construct and take apart a tuple for each group of mutually recursive definitions.[1]: page 232

### The factorial function

The factorial function provides a good example of how the fixed-point combinator may be applied. The result demonstrates simple recursion, as would be implemented in a single loop in an imperative language. The definition of numbers used is explained in Church encoding.

The function taking itself as a parameter is

${\displaystyle F\ f\ n=(\operatorname {IsZero} \ n)\ 1\ (\operatorname {multiply} \ n\ (f\ (\operatorname {pred} \ n)))\ .}$

This gives Y F n as

{\displaystyle {\begin{aligned}{\textsf {fix}}\ F\ n&=F\ ({\textsf {fix}}\ F)\ n\\&=(\operatorname {IsZero} \ n)\ 1\ (\operatorname {multiply} \ n\ (({\textsf {fix}}\ F)\ (\operatorname {pred} \ n)))\ .\end{aligned}}}

Setting ${\displaystyle {\textsf {fix}}\ F=\operatorname {fact} }$ gives

${\displaystyle \operatorname {fact} \ n=(\operatorname {IsZero} \ n)\ 1\ (\operatorname {multiply} \ n\ (\operatorname {fact} \ (\operatorname {pred} \ n)))\ .}$

This definition puts F in the role of the body of a loop to be iterated, and is equivalent to the mathematical definition of factorial:

${\displaystyle \operatorname {fact} \ n={\begin{cases}1&{\text{if}}~n=0\\n\times \operatorname {fact} \ (n-1)&{\text{otherwise.}}\end{cases}}}$

## Fixed-point combinators in lambda calculus

The Y combinator, discovered by Haskell B. Curry, is defined as

${\displaystyle Y=\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\ .}$

Beta reduction of this gives:

 ${\displaystyle Y\ g}$ ${\displaystyle =(\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)))\ g}$ (by definition of Y) ${\displaystyle =(\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x))}$ (by β-reduction of λf: applied Y to g) ${\displaystyle =g\ ((\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x)))}$ (by β-reduction of λx: applied left function to right function) ${\displaystyle =g\ (Y\ g)}$ (by second equality)

Repeatedly applying this equality gives:

${\displaystyle Y\ g=g\ (Y\ g)=g\ (g\ (Y\ g))=g\ (\ldots g\ (Y\ g)\ldots )}$

(The equality above should be thought of as a sequence of multi-step β-reductions from left to right. The lambda term ${\displaystyle g\ (Y\ g)}$ may not, in general, β-reduce to the term ${\displaystyle Y\ g}$. One can interpret the equality signs as β-equivalences instead of multi-step β-reductions to allow for going in both directions.)

### Equivalent definition of a fixed-point combinator

This fixed-point combinator may be defined as y, as in

${\displaystyle x=f\ x\land y\ f=x}$

An expression for y may be derived using rules from the definition of a let expression. Firstly, using the rule

${\displaystyle (\exists xE\land F)\iff \operatorname {let} x:E\operatorname {in} F}$

gives

${\displaystyle \operatorname {let} x=f\ x\operatorname {in} y\ f=x\ .}$

Also, using

${\displaystyle x\not \in \operatorname {FV} (E)\land x\in \operatorname {FV} (F)\to \operatorname {let} x:G\operatorname {in} E\ F=E\ (\operatorname {let} x:G\operatorname {in} F)}$

gives

${\displaystyle y\ f=\operatorname {let} x=f\ x\operatorname {in} x\ .}$

And then using the eta reduction rule,

${\displaystyle f\ x=y\iff f=\lambda x.y\ ,}$

gives

${\displaystyle y=\lambda f.\operatorname {let} x=f\ x\operatorname {in} x\ .}$

### Derivation of the Y combinator

Curry's Y combinator may be readily obtained from the definition of y.[5]

Starting with,

${\displaystyle \lambda f.\operatorname {let} x=f\ x\operatorname {in} x\ ,}$

A lambda abstraction does not support reference to the variable name, in the applied expression, so x must be passed in as a parameter to x. We can think of this as replacing x by x x, but formally this is not correct. Instead defining y by ${\displaystyle \forall z,y\ z=x}$ gives

${\displaystyle \lambda f.\operatorname {let} y\ z=f\ (y\ z)\operatorname {in} y\ z\ .}$

The let expression may be regarded as the definition of the function y, where z is the parameter. Instantiation z as y in the call gives

${\displaystyle \lambda f.\operatorname {let} y\ z=f\ (y\ z)\operatorname {in} y\ y\ .}$

And, because the parameter z always passes the function y,

${\displaystyle \lambda f.\operatorname {let} y\ z=f\ (z\ z)\operatorname {in} y\ y\ .}$

Using the eta reduction rule,

${\displaystyle f\ x=y\equiv f=\lambda x.y\ ,}$

gives

${\displaystyle \lambda f.\operatorname {let} y=\lambda z.f\ (z\ z)\operatorname {in} y\ y\ .}$
${\displaystyle n\not \in FV(E)\to (\operatorname {let} n=E\operatorname {in} L\equiv (\lambda n.L)\ E)}$

gives

${\displaystyle \lambda f.(\lambda y.y\ y)\ (\lambda z.f\ (z\ z))\ .}$

This is possibly the simplest implementation of a fixed-point combinator in lambda calculus. However, one beta reduction gives the more symmetrical form of Curry's Y combinator:

${\displaystyle \lambda f.(\lambda z.f\ (z\ z))\ (\lambda z.f\ (z\ z))\ .}$

### Other fixed-point combinators

In untyped lambda calculus fixed-point combinators are not especially rare. In fact there are infinitely many of them.[6] In 2005 Mayer Goldberg showed that the set of fixed-point combinators of untyped lambda calculus is recursively enumerable.[7]

The Y combinator can be expressed in the SKI-calculus as

${\displaystyle Y=S(K(SII))(S(S(KS)K)(K(SII)))\ .}$

The simplest fixed-point combinator in the SK-calculus, found by John Tromp, is

${\displaystyle Y'=SSK(S(K(SS(S(SSK))))K)\ .}$

although note that it is not in normal form, which is longer. This combinator corresponds to the lambda expression

${\displaystyle Y'=(\lambda xy.xyx)(\lambda yx.y(xyx))\ .}$

The following fixed-point combinator is simpler than the Y combinator, and β-reduces into the Y combinator; it is sometimes cited as the Y combinator itself:

${\displaystyle X=\lambda f.(\lambda x.xx)(\lambda x.f(xx))\ .}$

Another common fixed-point combinator is the Turing fixed-point combinator (named after its discoverer, Alan Turing):[8][2]: 132

${\displaystyle \Theta =(\lambda xy.y(xxy))\ (\lambda xy.y(xxy))\ .}$

Its advantage over ${\displaystyle {\textsf {Y}}}$ is that ${\displaystyle \Theta \ f}$ beta-reduces to ${\displaystyle f\ (\Theta f)}$,[note 3] whereas ${\displaystyle {\textsf {Y}}\ f}$ and ${\displaystyle f\ ({\textsf {Y}}f)}$ only beta-reduce to a common term.[note 2]

${\displaystyle \Theta }$ also has a simple call-by-value form:

${\displaystyle \Theta _{v}=(\lambda xy.y(\lambda z.xxyz))\ (\lambda xy.y(\lambda z.xxyz))\ .}$

The analog for mutual recursion is a polyvariadic fix-point combinator,[9][10][11] which may be denoted Y*.

### Strict fixed-point combinator

In a strict programming language the Y combinator will expand until stack overflow, or never halt in case of tail call optimization.[12] The Z combinator will work in strict languages (also called eager languages, where applicative evaluation order is applied). The Z combinator has the next argument defined explicitly, preventing the expansion of Z g in the right-hand side of the definition:[13]

${\displaystyle Zgv=g(Zg)v\ .}$

and in lambda calculus it is an eta-expansion of the Y combinator:

${\displaystyle Z=\lambda f.(\lambda x.f(\lambda v.xxv))\ (\lambda x.f(\lambda v.xxv))\ .}$

### Non-standard fixed-point combinators

In untyped lambda calculus there are terms that have the same Böhm tree as a fixed-point combinator, that is they have the same infinite extension λx.x (x (x ... )). These are called non-standard fixed-point combinators. Any fixed-point combinator is also a non-standard one, but not all non-standard fixed-point combinators are fixed-point combinators because some of them fail to satisfy the equation that defines the "standard" ones. These strange combinators are called strictly non-standard fixed-point combinators; an example is the following combinator:

${\displaystyle N=BM(B(BM)B)}$

where

${\displaystyle B=\lambda xyz.x(yz)}$
${\displaystyle M=\lambda x.xx\ .}$

The set of non-standard fixed-point combinators is not recursively enumerable.[7]

## Implementation in other languages

(The Y combinator is a particular implementation of a fixed-point combinator in lambda calculus. Its structure is determined by the limitations of lambda calculus. It is not necessary or helpful to use this structure in implementing the fixed-point combinator in other languages.)

Simple examples of fixed-point combinators implemented in some programming paradigms are given below.

### Lazy functional implementation

In a language that supports lazy evaluation, like in Haskell, it is possible to define a fixed-point combinator using the defining equation of the fixed-point combinator which is conventionally named fix. Since Haskell has lazy datatypes, this combinator can also be used to define fixed points of data constructors (and not only to implement recursive functions). The definition is given here, followed by some usage examples. In Hackage, the original sample is: [14]

fix, fix' :: (a -> a) -> a
fix f = let x = f x in x         -- Lambda dropped. Sharing.
-- Original definition in Data.Function.
-- alternative:
fix' f = f (fix' f)              -- Lambda lifted. Non-sharing.

fix (\x -> 9)                    -- this evaluates to 9

fix (\x -> 3:x)                  -- evaluates to the lazy infinite list [3,3,3,...]

fact = fix fac                   -- evaluates to the factorial function
where fac f 0 = 1
fac f x = x * f (x-1)

fact 5                           -- evaluates to 120

### Strict functional implementation

In a strict functional language, the argument to f is expanded beforehand, yielding an infinite call sequence,

${\displaystyle f\ (f...(f\ ({\mathsf {fix}}\ f))...)\ x}$.

This may be resolved by defining fix with an extra parameter.

let rec fix f x = f (fix f) x (* note the extra x; here fix f = \x-> f (fix f) x *)

let factabs fact = function   (* factabs has extra level of lambda abstraction *)
0 -> 1
| x -> x * fact (x-1)

let _ = (fix factabs) 5       (* evaluates to "120" *)

### Imperative language implementation

This example is a slightly interpretive implementation of a fixed-point combinator. A class is used to contain the fix function, called fixer. The function to be fixed is contained in a class that inherits from fixer. The fix function accesses the function to be fixed as a virtual function. As for the strict functional definition, fix is explicitly given an extra parameter x, which means that lazy evaluation is not needed.

template <typename R, typename D>
class fixer
{
public:
R fix(D x)
{
return f(x);
}
private:
virtual R f(D) = 0;
};

class fact : public fixer<long, long>
{
virtual long f(long x)
{
if (x == 0)
{
return 1;
}
return x * fix(x-1);
}
};

long result = fact().fix(5);

In an imperative-functional language, such as Lisp, Scheme, or Racket, Landin (1963)[full citation needed] suggests the use of a variable assignment to create a fixed-point combinator:

(define Y!
(lambda (f-maker)
((lambda (f)
(set! f (f-maker (lambda (x) (f x)))) ;; assignment statement
f)
'NONE)))

Using a lambda calculus with axioms for assignment statements, it can be shown that Y! satisfies the same fixed-point law as the call-by-value Y combinator:[15][16]

${\displaystyle ({\textsf {Y}}_{!}\ \lambda x.e)e'=(\lambda x.e)\ ({\textsf {Y}}_{!}\ \lambda x.e)e'}$

## Typing

In System F (polymorphic lambda calculus) a polymorphic fixed-point combinator has type[citation needed];

∀a.(a → a) → a

where a is a type variable. That is, fix takes a function, which maps a → a and uses it to return a value of type a.

In the simply typed lambda calculus extended with recursive data types, fixed-point operators can be written, but the type of a "useful" fixed-point operator (one whose application always returns) may be restricted.

In the simply typed lambda calculus, the fixed-point combinator Y cannot be assigned a type[17] because at some point it would deal with the self-application sub-term ${\displaystyle x~x}$ by the application rule:

${\displaystyle {\Gamma \vdash x\!:\!t_{1}\to t_{2}\quad \Gamma \vdash x\!:\!t_{1}} \over {\Gamma \vdash x~x\!:\!t_{2}}}$

where ${\displaystyle x}$ has the infinite type ${\displaystyle t_{1}=t_{1}\to t_{2}}$. No fixed-point combinator can in fact be typed; in those systems, any support for recursion must be explicitly added to the language.

### Type for the Y combinator

In programming languages that support recursive data types, it is possible to type the Y combinator by appropriately accounting for the recursion at the type level. The need to self-apply the variable x can be managed using a type (Rec a), which is defined so as to be isomorphic to (Rec a -> a).

For example, in the following Haskell code, we have In and out being the names of the two directions of the isomorphism, with types:[18][19]

In :: (Rec a -> a) -> Rec a
out :: Rec a -> (Rec a -> a)

which lets us write:

newtype Rec a = In { out :: Rec a -> a }

y :: (a -> a) -> a
y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x)))

Or equivalently in OCaml:

type 'a recc = In of ('a recc -> 'a)
let out (In x) = x

let y f = (fun x a -> f (out x x) a) (In (fun x a -> f (out x x) a))

Alternatively:

let y f = (fun x -> f (fun z -> out x x z)) (In (fun x -> f (fun z -> out x x z)))

## General information

Because fixed-point combinators can be used to implement recursion, it is possible to use them to describe specific types of recursive computations, such as those in fixed-point iteration, iterative methods, recursive join in relational databases, data-flow analysis, FIRST and FOLLOW sets of non-terminals in a context-free grammar, transitive closure, and other types of closure operations.

A function for which every input is a fixed point is called an identity function. Formally:

${\displaystyle \forall x(f\ x=x)}$

In contrast to universal quantification over all ${\displaystyle x}$, a fixed-point combinator constructs one value that is a fixed point of ${\displaystyle f}$. The remarkable property of a fixed-point combinator is that it constructs a fixed point for an arbitrary given function ${\displaystyle f}$.

Other functions have the special property that, after being applied once, further applications don't have any effect. More formally:

${\displaystyle \forall x(f\ (f\ x)=f\ x)}$

Such functions are called idempotent (see also Projection (mathematics)). An example of such a function is the function that returns 0 for all even integers, and 1 for all odd integers.

In lambda calculus, from a computational point of view, applying a fixed-point combinator to an identity function or an idempotent function typically results in non-terminating computation. For example, we obtain

${\displaystyle (Y\ \lambda x.x)=(\lambda x.(xx)\ \lambda x.(xx))}$

where the resulting term can only reduce to itself and represents an infinite loop.

Fixed-point combinators do not necessarily exist in more restrictive models of computation. For instance, they do not exist in simply typed lambda calculus.

The Y combinator allows recursion to be defined as a set of rewrite rules,[20] without requiring native recursion support in the language.[21]

In programming languages that support anonymous functions, fixed-point combinators allow the definition and use of anonymous recursive functions, i.e. without having to bind such functions to identifiers. In this setting, the use of fixed-point combinators is sometimes called anonymous recursion.[note 4][22]

## Notes

1. ^ Throughout this article, the syntax rules given in Lambda calculus#Notation are used, to save parentheses.
2. ^ a b For an arbitrary lambda term f, the fixed-point property can be validated by beta reducing the left- and the right-hand side: ${\displaystyle {\textsf {Y}}\ f}$ ${\displaystyle \equiv }$ ${\displaystyle (\lambda f.(\lambda x.f(xx))\ (\lambda x.f(xx)))\ f}$ ${\displaystyle \to }$ ${\displaystyle (\lambda x.f(xx))\ (\lambda x.f(xx))}$ ${\displaystyle \to }$ ${\displaystyle f\ ((\lambda x.f(xx))\ (\lambda x.f(xx)))}$, where ${\displaystyle \equiv }$ and ${\displaystyle \to }$ denote syntactic equality by definition and beta reduction, respectively. Similarly to the first two steps, one obtains ${\displaystyle f\ ({\textsf {Y}}\ f)}$ ${\displaystyle \to }$ ${\displaystyle f\ ((\lambda x.f(xx))\ (\lambda x.f(xx)))}$. Since both terms ${\displaystyle {\textsf {Y}}\ f}$ and ${\displaystyle f\ ({\textsf {Y}}\ f)}$ could be reduced to the same term, they are equal.
3. ^ ${\displaystyle \Theta \ f}$ ${\displaystyle \equiv }$ ${\displaystyle (\lambda xy.y(xxy))\ (\lambda xy.y(xxy))\ f}$ ${\displaystyle \to }$ ${\displaystyle (\lambda y.y\ ((\lambda xy.y(xxy))\ (\lambda xy.y(xxy))\ y))\ f}$ ${\displaystyle \to }$ ${\displaystyle f\ ((\lambda xy.y(xxy))\ (\lambda xy.y(xxy))\ f)}$ ${\displaystyle \equiv }$ ${\displaystyle f\ (\Theta \ f)}$
4. ^ This terminology appears to be largely folklore, but it does appear in the following:
• Trey Nash, Accelerated C# 2008, Apress, 2007, ISBN 1-59059-873-3, p. 462—463. Derived substantially from Wes Dyer's blog (see next item).
• Wes Dyer Anonymous Recursion in C#, February 02, 2007, contains a substantially similar example found in the book above, but accompanied by more discussion.

## References

1. ^ a b Peyton Jones, Simon L. (1987). The Implementation of Functional Programming. Prentice Hall International.
2. ^ a b Henk Barendregt (1985). The Lambda Calculus – Its Syntax and Semantics. Studies in Logic and the Foundations of Mathematics. Vol. 103. Amsterdam: North-Holland. ISBN 0444867481.
3. ^ Selinger, Peter. "Lecture Notes on Lambda Calculus (PDF)". p. 6.
4. ^ "For those of us who don't know what a Y-Combinator is or why it's useful, ..." Hacker News. Retrieved 2 August 2020.
5. ^ "abstract algebra - Can someone explain the Y Combinator?". Mathematics Stack Exchange.
6. ^ Bimbó, Katalin (27 July 2011). Combinatory Logic: Pure, Applied and Typed. p. 48. ISBN 9781439800010.
7. ^ a b Goldberg, 2005
8. ^ Alan Mathison Turing (December 1937). "The ${\displaystyle p}$-function in ${\displaystyle \lambda }$-${\displaystyle K}$-conversion". Journal of Symbolic Logic. 2 (4): 164. JSTOR 2268281.
9. ^ "Many faces of the fixed-point combinator". okmij.org.
10. ^ Polyvariadic Y in pure Haskell98 Archived 2016-03-04 at the Wayback Machine, lang.haskell.cafe, October 28, 2003
11. ^
12. ^ Bene, Adam (17 August 2017). "Fixed-Point Combinators in JavaScript". Bene Studio. Medium. Retrieved 2 August 2020.
13. ^ "CS 6110 S17 Lecture 5. Recursion and Fixed-Point Combinators" (PDF). Cornell University. 4.1 A CBV Fixed-Point Combinator.
14. ^
15. ^ Felleisen, Matthias (1987). The Lambda-v-CS Calculus. Indiana University.
16. ^ Talcott, Carolyn (1985). The Essence of Rum: A theory of the intensional and extensional aspects of Lisp-type computation (Ph.D. thesis). Stanford University.
17. ^ An Introduction to the Lambda Calculus Archived 2014-04-08 at the Wayback Machine
18. ^ Haskell mailing list thread on How to define Y combinator in Haskell, 15 Sep 2006
19. ^ Geuvers, Herman; Verkoelen, Joep. On Fixed point and Looping Combinators in Type Theory. CiteSeerX 10.1.1.158.1478.
20. ^ Daniel P. Friedman, Matthias Felleisen (1986). "Chapter 9 - Lambda The Ultimate". The Little Lisper. Science Research Associates. p. 179. "In the chapter we have derived a Y-combinator which allows us to write recursive functions of one argument without using define."
21. ^ Mike Vanier. "The Y Combinator (Slight Return) or: How to Succeed at Recursion Without Really Recursing". Archived from the original on 2011-08-22. "More generally, Y gives us a way to get recursion in a programming language that supports first-class functions but that doesn't have recursion built in to it."
22. ^ The If Works Deriving the Y combinator, January 10th, 2008


text:
# Posts by Category

## Debugging Odoo compute fields with ir.logging

I was trying determine why a computed field wasn’t working as expected and was really annoyed at the fact that log isn’t available on that context. We can c...

## Electrostatics simulation with WASM

In-browser simulation of electric potential and field generated by 2D electrodes using Emscripten.

## Electrostatics simulation with WASM

In-browser simulation of electric potential and field generated by 2D electrodes using Emscripten.

format: plain


text:
Determining stability of the differential equation

Determine wether the differential equation is stable or not for the following conditions:

$x”'(0) = x”(0) = x'(0) = x(0) =0$

$\frac{d^3x(t)}{dt^3}+\frac{d^2x(t)}{dt^2}+4\frac{dx(t)}{dt}+4x(t) = e^t(H(t)-H(t-3))$

Now, I got that the solution to this differential equation reduces x(t) by use of Laplace Transforms, however, how do I determine whether or not it is stable?

$x(t) = 0.1e^{-t} + 0.1e^t – 0.1\sin(2t) + 0.1e^3 (\sin(2(t-3)) + e^{-t+3}-e^{t-3})*H(t-3)$

Now I first thought I would look at it graphically and I used Matlab software to get a plot as shown below:

And from the plot above it clearly appears to diverge (though this is not a proof).

Anyone have an idea as to an elegant proof to show the solution is unstable?

Anyone help would be greatly appreciated!

Solutions Collecting From Web of "Determining stability of the differential equation"

You have eigenvalues $-1,2i,-2i$ and no forcing after $t=3$. This is stable, but not asymptotically stable, i.e., solutions do not shrink to zero, but they also do not grow.

As you found, the homogeneous solution, which is valid for $t>3$, is
$$x(t)=c_1\cos(2t)+c_2\sin(2t)+c_3e^{-t}$$
where the first two components stay bounded while the third converges towards zero.

On the graph

That a formula represents a stable solution does not automatically mean that the evaluation of that formula is numerically stable. Indeed, for large $t$ the floating point evaluation of that formula reduces to the evaluation of $0.1·(e^t-e^3·e^{t-3})$ which can incur cancellation error of the size $0.1·e^t·10^{-16}$ which for $t=100$ gives the magnitude $10^{-1+43-16}=10^{26}$ which is indeed also the scale factor in the graph.

One needs to explicitly switch off this exponential factor via
$$0.1·e^t·(H(t)-H(t-3))$$
or a similar form of conditional evaluation.


text:
A wiki system written for the Django framework.

## Django support

The below table explains which Django versions are supported.

Release

Django

0.9.x

2.2, 3.0, 3.1, 3.2, 4.0

0.7

0.8.x

2.2, 3.0, 3.1, 3.2, 4.0

0.7

0.7.x

2.2, 3.0, 3.1, 3.2

0.5 or 0.6

0.6.x

2.1, 2.2, 3.0

0.5

0.5.x

2.1, 2.2

0.4

0.4.x

1.11, 2.0, 2.1

0.3

0.3.x

1.8, 1.9, 1.10, 1.11

0.2

0.2.x

1.8, 1.9, 1.10

0.1

0.1.x

1.5, 1.6, 1.7

0.0.24

0.0.24

1.4, 1.5, 1.6 1.7 (unstable)

0.0.?

## Translations (Transifex)

Django-wiki has almost fully translated into 12 languages, apart from the default (English). But please help out in adding more languages! It’s very easy, you don’t even need to be a programmer.

Some languages…

• Just need a little push, as they are almost fully complete

• Got initiatied and need a new instigator to carry on the ambitions

• Do not exist yet - but you can request them and become the coordinator.

Visit the django-wiki project on Transifex

## Demo

https://demo.django-wiki.org

## Community

Please use our IRC or mailing list (google group) for getting in touch on development and support. Please do not email developers asking for personal support.

## THIS IS A WORK IN PROGRE…

Currently, the model API is subject to smaller changes, and the plugin API seems pretty stable.

In order to customize the wiki, best idea is to override templates and create your own template tags. Do not make your own hard copy of this repository in order to fiddle with internal parts of the wiki – this strategy will lead you to lose out on future updates with highly improved features and plugins. Possibly security updates as well!

The release cycle has already begun, so you can administer django-wiki through Pypi and pip.

All views are class-based, however don’t take it as an encouragement to extend them, unless you are prepared to modify both templates and view classes every time there is an update.

## Manifesto

Django needs a mature wiki system appealing to all kinds of needs, both big and small:

• Be pluggable and light-weight. Don’t integrate optional features in the core.

• Be open. Make an extension API that allows the ecology of the wiki to grow in a structured way. Wikipedia consists of over 1100 extension projects written for MediaWiki. We should learn from this.

• Be smart. This is the map of tables in MediaWiki - we’ll understand the choices of other wiki projects and make our own. After-all, this is a Django project.

• Be simple. The source code should almost explain itself.

• Be structured. Markdown is a simple syntax for readability. Features should be implemented either through easy coding patterns in the content field, but rather stored in a structured way (in the database) and managed through a friendly interface. This gives control back to the website developer, and makes knowledge more usable. Just ask: Why has Wikipedia never changed? Answer: Because it’s knowledge is stored in a complicated way, thus it becomes very static.

## Docs

See the docs/ folder, or read them at:

## Background

Django-wiki is a rewrite of django-simplewiki, a project from 2009 that aimed to be a base system for a wiki. It proposed that the user should customize the wiki by overwriting templates, but soon learned that the only customization that really took place was that people forked the entire project. We don’t want that for django-wiki, we want it to be modular and extendable.

As of now, Django has existed for too long without a proper wiki application. The dream of django-wiki is to become a contestant alongside Mediawiki, so that Django developers can stick to the Django platform even when facing tough challenges such as implementing a wiki.

## Q&A

• Why is the module named just wiki ? Because when we tried pip install wiki, it returned “No distributions at all found for wiki”, so we had to make up for that!

• What markup language will you use? Markdown. The markup renderer is not a pluggable part but has been internalized into core parts. Discussion should go here: https://github.com/django-wiki/django-wiki/issues/76

• Why not use django-reversion? It’s a great project, but if the wiki has to grow ambitious, someone will have to optimize its behavior, and using a third-party application for something as crucial as the revision system is a no-go in this regard.

• Any support for multiple wikis? Yes, in an sense you can just imagine that you always have multiple wikis, because you always have hierarchies and full control of their permissions. See this discussion: https://github.com/django-wiki/django-wiki/issues/63

## Requirements

Please refer to current release to see exact version dependencies. And make note that Pillow needs to have certain build dependencies satisfied on your host system.

## Docker tl;dr

There is a docker container available here: https://github.com/riotkit-org/docker-django-wiki

## Acknowledgements

• The people at edX & MIT for finding and supporting the project both financially and with ideas.

• django-cms for venturing where no django app has gone before in terms of well-planned features and high standards. It’s a very big inspiration.

• django-mptt, a wonderful utility for inexpensively using tree structures in Django with a relational database backend.

## Project details

Uploaded source
Uploaded py3


text:
# Area of Semi-Circle region from Chord

• Aug 8th 2007, 02:19 PM
Chris Rickets
Area of Semi-Circle region from Chord
http://img261.imageshack.us/img261/7381/problemgq0.png

Hello,
I would like to know how I am supposed to approach this problem.
A small semi-circle is inserted into a bigger one.
The only measurement that I have been given is that chord WX = 36mm, and is parallel to diameter YZ.
I need to find the area of the grey area, and I am completely stuck for any idea on how to tackle this with only the one measurement.

p.s. The diameter of the smaller semi-circle is not necessarily half the diameter of the larger one.

Thanks if anyone can help.
• Aug 8th 2007, 02:35 PM
ThePerfectHacker
This shape is called the Arbelos (or Shoemaker's Knife) it has been discussed in the Book of Lemmas by Archimedes Proposition 14.

NOTE: You need to find a link called "Book of Lemmas", it is not possible to post this as a redirect.
• Aug 8th 2007, 02:53 PM
Chris Rickets
Thanks, but I am still none the wiser as to how to solve the question at hand.

I found proposition 14 in the Book of Lemmas, but I couldn't figure out how to utilise any of the information.

Also, it seems that all of the Arbelos' have two semi-circles inscribed and not just one as in my problem.

Thanks in advance for any further help!
• Aug 8th 2007, 03:57 PM
Soroban
Hello, Chris Rickets!

Quote:

http://img261.imageshack.us/img261/7381/problemgq0.png

A small semi-circle is inserted into a bigger one.
The only measurement is that chord WX = 36mm, and is parallel to diameter YZ.
Find the area of the grey area.

Let $r$ = radius of small circle.
Let $R$ = radius of large circle.

Let $O$ be the center of the large circle.
Then: . $OW \,=\, R$

From $O$ erect a perpendicular, cutting $WX$ at $P$.
\. . Note that: $OP \,= \,r$

In right triangle $WPO$, we have: . $OP^2 + WP^2 \:=\:OW^2$
. . So: . $r^2 + WP^2 \:=\:R^2\quad\Rightarrow\quad WP \:=\:\sqrt{R^2-r^2}$

Since $WZ = 36,\:WP = 18\!:\;\sqrt{R^2-r^2} \:=\:18\quad\Rightarrow\quad R^2-r^2\:=\:324$ .[1]

The area of the large semicircle is: . $\frac{1}{2}\pi R^2$
The area of the small semicircle is: . $\frac{1}{2}\pi r^2$

Then the grey area is: . $A\:=\:\frac{1}{2}\pi R^2 - \frac{1}{2}\pi r^2 \:=\:\frac{1}{2}\pi\left(R^2-r^2\right)$ .[2]

Substitute [1] into [2]: . $A \:=\:\frac{1}{2}\pi(324) \:=\:\boxed{162\pi\text{ mm}^2}$

• Aug 8th 2007, 04:13 PM
Chris Rickets
Thank you so much!
I just couldn't get my head around it!


text:
# Doppler shift and change in intensity of a sound wave

• I
How are the intensity of a sound wave and the Doppler shift of frequency related togheter?
That is, if the source or the observer are in relative motion, how does the intensity change?

For a sound wave $$I=\frac{1}{2} \rho \omega^2 A^2 c=2 \pi^2 \rho f^2 A^2c$$

(##c## is sound speed, ##\rho## is density of air, ##A## is amplitude)

So, since Doppler effect is only about ##f##, I would say that

$$I'=I \bigg(\frac{f'}{f}\bigg)^2=I \bigg(\frac{c+v_{oss}}{c+v_{sorg}}\bigg)^2$$


text:
# matplotlib.axes.Axes.phase_spectrum¶

Axes.phase_spectrum(x, Fs=None, Fc=None, window=None, pad_to=None, sides=None, *, data=None, **kwargs)[source]

Plot the phase spectrum.

Call signature:

phase_spectrum(x, Fs=2, Fc=0,  window=mlab.window_hanning,

Compute the phase spectrum (unwrapped angle spectrum) of x. Data is padded to a length of pad_to and the windowing function window is applied to the signal.

Parameters:
x : 1-D array or sequence

Array or sequence containing the data

Fs : scalar

The sampling frequency (samples per time unit). It is used to calculate the Fourier frequencies, freqs, in cycles per time unit. The default value is 2.

window : callable or ndarray

A function or a vector of length NFFT. To create window vectors see window_hanning(), window_none(), numpy.blackman(), numpy.hamming(), numpy.bartlett(), scipy.signal(), scipy.signal.get_window(), etc. The default is window_hanning(). If a function is passed as the argument, it must take a data segment as an argument and return the windowed version of the segment.

sides : [ 'default' | 'onesided' | 'twosided' ]

Specifies which sides of the spectrum to return. Default gives the default behavior, which returns one-sided for real data and both for complex data. 'onesided' forces the return of a one-sided spectrum, while 'twosided' forces two-sided.

The number of points to which the data segment is padded when performing the FFT. While not increasing the actual resolution of the spectrum (the minimum distance between resolvable peaks), this can give more points in the plot, allowing for more detail. This corresponds to the n parameter in the call to fft(). The default is None, which sets pad_to equal to the length of the input signal (i.e. no padding).

Fc : integer

The center frequency of x (defaults to 0), which offsets the x extents of the plot to reflect the frequency range used when a signal is acquired and then filtered and downsampled to baseband.

Returns:
spectrum : 1-D array

The values for the phase spectrum in radians (real valued)

freqs : 1-D array

The frequencies corresponding to the elements in spectrum

line : a Line2D instance

The line created by this function

Other Parameters:
**kwargs :

Keyword arguments control the Line2D properties:

Property Description
agg_filter a filter function, which takes a (m, n, 3) float array and a dpi value, and returns a (m, n, 3) array
alpha float (0.0 transparent through 1.0 opaque)
animated bool
antialiased or aa bool
clip_box a Bbox instance
clip_on bool
clip_path [(Path, Transform) | Patch | None]
color or c any matplotlib color
contains a callable function
dash_capstyle ['butt' | 'round' | 'projecting']
dash_joinstyle ['miter' | 'round' | 'bevel']
dashes sequence of on/off ink in points
drawstyle ['default' | 'steps' | 'steps-pre' | 'steps-mid' | 'steps-post']
figure a Figure instance
fillstyle ['full' | 'left' | 'right' | 'bottom' | 'top' | 'none']
gid an id string
label object
linestyle or ls ['solid' | 'dashed', 'dashdot', 'dotted' | (offset, on-off-dash-seq) | '-' | '--' | '-.' | ':' | 'None' | ' ' | '']
linewidth or lw float value in points
marker A valid marker style
markeredgecolor or mec any matplotlib color
markeredgewidth or mew float value in points
markerfacecolor or mfc any matplotlib color
markerfacecoloralt or mfcalt any matplotlib color
markersize or ms float
markevery [None | int | length-2 tuple of int | slice | list/array of int | float | length-2 tuple of float]
path_effects AbstractPathEffect
picker float distance in points or callable pick function fn(artist, event)
pickradius float distance in points
rasterized bool or None
sketch_params (scale: float, length: float, randomness: float)
snap bool or None
solid_capstyle ['butt' | 'round' | 'projecting']
solid_joinstyle ['miter' | 'round' | 'bevel']
transform a matplotlib.transforms.Transform instance
url a url string
visible bool
xdata 1D array
ydata 1D array
zorder float

magnitude_spectrum()
magnitude_spectrum() plots the magnitudes of the corresponding frequencies.
angle_spectrum()
angle_spectrum() plots the wrapped version of this function.
specgram()
specgram() can plot the phase spectrum of segments within the signal in a colormap.

Notes

Note

In addition to the above described arguments, this function can take a data keyword argument. If such a data argument is given, the following arguments are replaced by data[<arg>]:

• All arguments with the following names: 'x'.


text:
# Verschiebungsvektor im Netzplot - 1D

Hi Miha,

good point. Maybe, I can split up the components, i.e., the horizontal and the vertical component, like for the principle components.

/Micha

--
applied-geodesy.org - OpenSource Least-Squares Adjustment Software for Geodetic Sciences


text:
Opened 5 years ago

Closed 3 years ago

# Can't import "Import Error : cannot import name add_script_data"

Reported by: Owned by: anonymous falkb normal SimpleMultiProjectPlugin blocker 0.11

The reason I'm reporting this issue is because I did not find any information regarding the version needed on the hacks page.

I have 0.11.7 installed.

After installation of SimpleMultiProjects plugin I see it only on the admin page.

This plugin is not visible on the roadmap page.

On trac logs I found this error:

Trac[loader] ERROR: Skipping "simplemultiproject = simplemultiproject":
(can't import "ImportError: cannot import name add_script_data")

### comment:1 Changed 5 years ago by Volodymyr.Koval

Version of SimpleMultiProjects? plugin - 0.0.3

### comment:2 follow-ups:  4  7 Changed 5 years ago by falkb

Hmm... it seems add_script_data is a new function of 0.12 :-( Do you see a chance to backport it to 0.11? Unfortunately, I don't have 0.11 anymore.

### comment:3 Changed 5 years ago by falkb

This ticket is related to #10078

### comment:4 in reply to:  2 Changed 5 years ago by Ryan J Ollos

Description: modified (diff)

### comment:5 follow-up:  6 Changed 5 years ago by falkb

rjollos wrote on trac-dev@…:

I'm not sure about backporting, but I can show you some examples of what developers did before the function was available. These are the changesets/patches in which I replaced the virtual script with add_script data:

Thanks a lot, stored here now. Need some time...

### comment:6 in reply to:  5 Changed 5 years ago by Jun Omae

rjollos wrote on trac-dev@…:

I'm not sure about backporting, but I can show you some examples of what developers did before the function was available. These are the changesets/patches in which I replaced the virtual script with add_script data:

Another solution is to add script element to head element on ITemplateStreamFilter.filter_stream.

### comment:7 in reply to:  2 Changed 5 years ago by Chris Nelson

Hmm... it seems add_script_data is a new function of 0.12 :-( Do you see a chance to backport it to 0.11? Unfortunately, I don't have 0.11 anymore.

This appears a trivial backport. Diffing to 0.11.6:

• ## trac/web/chrome.py

index 20e89d5..2cdc2e3 100644
 a def add_script(req, filename, mimetype='text/javascript'): req.chrome.setdefault('scripts', []).append(script) scriptset.add(filename) # Backported from 0.12 def add_script_data(req, data={}, **kwargs): """Add data to be made available in javascript scripts as global variables. The keys in data and the keyword argument names provide the names of the global variables. The values are converted to JSON and assigned to the corresponding variables. """ script_data = req.chrome.setdefault('script_data', {}) script_data.update(data) script_data.update(kwargs) def add_javascript(req, filename): """Deprecated: use add_script() instead.""" add_script(req, filename, mimetype='text/javascript')

With that in place, I can load GroupTicketFieldsPlugin and it creates sections in my ticket for other fields but the configured fields don't show up in the new section. Still looking into that.

### comment:8 follow-up:  9 Changed 5 years ago by Ryan J Ollos

It looks like you are on the right track, but you need the corresponding functionality to parse script_data in your template (see layout.html) and a to_json function.

### comment:9 in reply to:  8 ; follow-up:  11 Changed 5 years ago by Chris Nelson

It looks like you are on the right track, but you need the corresponding functionality to parse script_data in your template (see layout.html) and a to_json function.

The former is easy. The latter seems a slippery slope.

• to_json is in presentation.py
• It relies on dumps from json or to_js_string from util.text.
• In 0.11.6, there is no to_js_string in util.text
• I'm in Python 2.6.5 and that has dumps so that may work but I don't know how far back

### comment:10 Changed 5 years ago by falkb

IIRC json.dumps is available since Python 2.6 (also read here). But look here for how to code a compat switch.

### comment:11 in reply to:  9 ; follow-up:  12 Changed 5 years ago by Chris Nelson

The former is easy. The latter seems a slippery slope.

• to_json is in presentation.py
• It relies on dumps from json or to_js_string from util.text.
• In 0.11.6, there is no to_js_string in util.text
• I'm in Python 2.6.5 and that has dumps so that may work but I don't know how far back

Now I'm stuck. I have to_json in presentation.py but how do I *import* it into layout.html?

### comment:12 in reply to:  11 Changed 5 years ago by Ryan J Ollos

Now I'm stuck. I have to_json in presentation.py but how do I *import* it into layout.html?

I think that you need to add it to the data dictionary: data['to_json'] = to_json. Take a look at populate_data to see how this works.

### comment:13 Changed 5 years ago by Chris Nelson

So that gets me further. The page source includes:

which is consistent with my configuration:

[group-ticket-fields]
relationships = Relationships
relationships.fields = parents,blockedby,blocking
group_order = relationships,main

but in the ticket, the Relationships section is still empty.

I don't find anything in trac.log about any failure and I don't get a JavaScript error.

FireBug doesn't list group_ticket_fields.js among the loaded script resources.

### comment:14 follow-up:  18 Changed 5 years ago by Chris Nelson

However, the page source includes:

### comment:15 follow-up:  16 Changed 5 years ago by Ryan J Ollos

One potential problem is that the plugin is calling the function enableFolding, which is provided in Trac 0.12 by folding.js. This function doesn't exist in Trac 0.11 (see #8942). However, that doesn't seem to be your primary problem here.

### comment:16 in reply to:  15 ; follow-up:  17 Changed 5 years ago by Chris Nelson

One potential problem is that the plugin is calling the function enableFolding, which is provided in Trac 0.12 by folding.js. This function doesn't exist in Trac 0.11 (see #8942). However, that doesn't seem to be your primary problem here.

Yeah, I can live without folding. Hmmm, I wonder if that needs to be protected by a try?

### comment:17 in reply to:  16 Changed 5 years ago by Chris Nelson

One potential problem is that the plugin is calling the function enableFolding, which is provided in Trac 0.12 by folding.js. This function doesn't exist in Trac 0.11 (see #8942). However, that doesn't seem to be your primary problem here.

Yeah, I can live without folding. Hmmm, I wonder if that needs to be protected by a try?

No, that call seems safe:

if ($.inArray('foldable', group['properties']) != -1) {$('legend', fieldset).enableFolding($.inArray('collapsed', group['properties']) != -1, true); } ### comment:18 in reply to: 14 ; follow-up: 19 Changed 5 years ago by Chris Nelson Replying to ChrisNelson: However, the page source includes:  I had not (re)deployed static resources. When I do that the script loads and executes but doesn't quite do what I expect. It moves one label but not the corresponding field and ignores the rest of the fields. Maybe it encountered an error. ### comment:19 in reply to: 18 Changed 5 years ago by Ryan J Ollos Replying to ChrisNelson: I had not (re)deployed static resources. When I do that the script loads and executes but doesn't quite do what I expect. It moves one label but not the corresponding field and ignores the rest of the fields. Maybe it encountered an error. I'm reaching here, but I seem to remember several of the ticket form IDs being renamed between 0.11 and 0.12, and having to fix some problems in another plugin with the stream filter not operating as expected in 0.12 as a result. ### comment:20 follow-up: 22 Changed 5 years ago by Chris Nelson The Group Ticket Fields JavaScript seems to go off into the weeds at line 58: var value_td =$('td').has('#' + field_id); // get the

When I set a breakpoint there and at 59 and continue from 58, I never get to 59.

I'm left with a partially modified ticket:

<legend>Relationships</legend>

Parent Ticket:

Given that piece of the page, I don't see what "td" it is supposed to get, there isn't one. Is it searching for the  where the field was originally populated? That I can find in the page source just fine.

This is getting into jQuery territory I'm not familiar with. Maybe I need to give up.

### comment:22 in reply to:  20 ; follow-up:  23 Changed 5 years ago by Ryan J Ollos

This is getting into jQuery territory I'm not familiar with. Maybe I need to give up.

We've come too far to give up ;) I'm setting up to test in 0.11 and 0.12.

### comment:23 in reply to:  22 Changed 5 years ago by Ryan J Ollos

We've come too far to give up ;) I'm setting up to test in 0.11 and 0.12.

Well, nevermind. I had meant to comment on #10468, and was going to take a crack at getting that working, but since the issue is solved now, I won't worry about it.

### comment:24 Changed 4 years ago by falkb

Owner: changed from Christopher Paredes to falkb

### comment:25 Changed 4 years ago by falkb

(In [12999]) blindly tried backport to Trac 0.11, I don't have it installed, please report back (refs #10515, refs #10240, refs #10078)

### comment:26 Changed 3 years ago by falkb

Resolution: → wontfix new → closed

giving up support of Trac older than 0.12

### Modify Ticket

Change Properties


text:
# why Calc gives different results for an Excel sheet?

Hi,

there is an XLSX file which gives different results in Excel and Calc, but only in some rows. If you take a look on it the Excel results seem to be consistent, while Calc result are suspicious. This is why I ask it here and not on MSDN... ;-) Unfortunately I cannot upload a file yet, I need 3 points to it. I cannot even upload an image about the phenomenon. I can manage an FTP or HTTP download (200 kB), of course, if someone might want to waste her/his time on my problem.

The formula in Hungarian Excel: =HA($B11>=0;B11*C11;-(MAX(HA($E$2:$E11<-SZUMHA($B$2:$B11;"<0");$F$2:$F11)) -(SZUMHA($B$2:$B11;"<0")+MAX(HA($E$2:$E11<-SZUMHA($B$2:$B11;"<0");$E$2:$E11))) *INDEX($C$2:$C11;HOL.VAN(MIN(HA($E$2:$E11>=-SZUMHA($B$2:$B11;"<0");$E$2:$E11));$E$2:$E11;0)) +SZUMHA(ELTOLÁS(D11;-1;0;-SOR(D11)+1;1);"<0"))) English equivalent =IF($B11>=0;B11*C11;-(MAX(IF($E$2:$E11<-SUMIF($B$2:$B11;"<0");$F$2:$F11)) -(SUMIF($B$2:$B11;"<0")+MAX(IF($E$2:$E11<-SUMIF($B$2:$B11;"<0");$E$2:$E11))) *INDEX($C$2:$C11;MATCH(MIN(IF($E$2:$E11>=-SUMIF($B$2:$B11;"<0");$E$2:$E11));$E$2:$E11;0)) +SUMIF(OFFSET(D11;-1;0;-ROW(D11)+1;1);"<0")))

Is there any known incompatibility in the formula? What is interesting: it appears in 14 cells, and the results are the same in all the 8 cells which give positive result, and in the first cell which gives negative result. All the other 5 cells with negative results are different.

Thanks for any help in advance: M. Gy.

edit retag close merge delete

( 2016-09-05 12:18:15 +0100 )edit
( 2016-09-05 14:42:26 +0100 )edit

I have had a look at the Excel sheet. Could you explain the problem better?

( 2016-09-05 15:26:41 +0100 )edit

If you open this sheet in Excel, then you will see in cell D7 ($7 796,75), If you open it in Calc, you see ($8 201,27) in D7. There is also a difference in D9, D11, D12, D15. All the other cells in column D are the same both in Excel and Calc.

( 2016-09-05 17:00:07 +0100 )edit

Sort by » oldest newest most voted

The difference between Excel and Calc (using formula in D7) seems to be in the evaluation of :-

SUMIF(OFFSET(D7,-1,0,-ROW(D7)+1,1),"<0")

In Excel this evaluates to 404.521 but in Calc this evaluates to 0.

A simpler formula that works correctly in both Excel and Calc is:-

SUMIF($D$1:$D6,"<0")  Again this is for the formula in D7. Note the location of$ and in particular that this is not prior to the 6.

If you change the formula in D7 to the following, and then copy this cell to the other rows of column D then I think you should have the same results for both Excel and Calc.

=IF($B7>=0,B7*C7,-(MAX(IF($E$2:$E7<-SUMIF($B$2:$B7,"<0"),$F$2:$F7)) -(SUMIF($B$2:$B7,"<0")+MAX(IF($E$2:$E7<-SUMIF($B$2:$B7,"<0"),$E$2:$E7))) *INDEX($C$2:$C7,MATCH(MIN(IF($E$2:$E7>=-SUMIF($B$2:$B7,"<0"),$E$2:$E7)),$E$2:$E7,0)) +SUMIF($D$1:$D6,"<0")))

I also noticed you have entered the formula in column D as array formula, but that does not seem to be necessary. I think this is due to the functions MAX, MIN and SUMIF, which evaluate the result of a range of cells and do not return an array result.

You might also consider simplifying the formula by using helper columns to hold intermediate results of the calculation instead of using such a complicated formula in column D.

Note. I used LO 5.2.0.4 and Excel 2010, on Windows 8.1.

Edit to suggested functions to avoid a self reference in the formula when pasted to cell D2. Changed from "SUMIF($D$2:$D6,"<0")" to "SUMIF($D$1:$D6,"<0")"

more

As -ROW(D7)+1 results in -6 The above quoted sub-formula +SUMIF(OFFSET(D7,-1,0,-ROW(D7)+1,1),"<0") is violating a restriction (newHeight > 0) contained in the mandatory specification of the OFFSET function by OpenFormula. The zero value returned for the erroneous expression should thus be replaced by Err:502.
If needed in similar cases for parametrisation the mentioned sub-expression can be replaced by +SUMIF(OFFSET(D7;-ROW(D7)+1;0;ROW(D7)-1;1);">0").

( 2016-09-06 12:46:36 +0100 )edit

Might someone point to a specifiaction for OFFSET as used by Excel 2010, please? Is there any?

(Sorry: The replacing subformula in my comment above is containing ">0" instead of the correct"<0". I can no longer edit the older comment.)

( 2016-09-06 13:01:22 +0100 )edit

Excel OFFSET function. It looks like Excel OFFSET function is also defined as requiring a positive height but it seems this is not being enforced by Excel.

( 2016-09-06 14:59:15 +0100 )edit

@mark_t: Can you quote or loink to the definition/specification you are talking of?

( 2016-09-06 21:07:33 +0100 )edit

@Lupp, beginning of my last comment is the link, sorry if the words were hiding the link. https://support.office.com/en-us/arti...

( 2016-09-06 22:24:30 +0100 )edit

Sorry! I must have missed the highlighting.
Thank you for the link. It goes, however, to a "support" page. Thus I cannot be sure again if the text there was produced by someone who thought he knew how OFFSET works, or by someone who knew how it was specified to work. If this is the same, and the guy mentioned first is always right with his assumption, there cannot be any bugs in the world. I found a few, however.

( 2016-09-06 22:43:53 +0100 )edit

By the way: Excel 2016 introduced two non-commutative accumulating functions (CONCAT and TEXTJOIN). Applying one of these woud require an additional specification about the order of the elements to process, in specific if the argument is a reference returned by OFFSET with a negative height. Why do I feel so sure that nobody considered this? MS has made a big mess of computing which I once appreciated for reasons no longer valid. .

( 2016-09-06 22:53:09 +0100 )edit

Thank you all for the help, I try to understand the solution and the comments and return back with the result... :-)

( 2016-09-07 09:58:18 +0100 )edit