6

So I like test-driven development and frequently I have wanted a programming language to assist with the creation of test routines. I have wanted to define the domain of a function and then have some test 'buddy' generate some random test input based on the domain, some test data deliberately inside the domain and some deliberately outside to test the error case, also some deliberately on the boundary which is where more errors can occur.

It seems possible with a custom C# attribute adorned on a method parameters. However, I would like an extra level of cleverness I would like inferred domains, inferred from the domains of feeder functions. I should introduce some example code at this point, the following is VBA and illustrates a case where (given enough language support) the domain of i(x) could be inferred by looking at the domains of g(x) and h(x).

Option Explicit

'* I'd like to define the domain of g(x) to be 2 <= x <= 5 , whilst g(x) maps x->x+1
Function g(x)
    If Not (2 <= x And x <= 5) Then g = CVErr(2011): Exit Function '* VBA domain screened with If

    g = x + 1
End Function

'* I'd like to define the domain of h(x) to be -4 <= x <= 4, whilst h(x) maps x->x^2
Function h(x)    
    If Not (-4 <= x And x <= 4) Then h = CVErr(2011): Exit Function '* VBA domain screened with If

    h = x ^ 2
End Function

Function i(x)
    '* it would be nice if a computer language could understand that the domain of i(x) can 
    '* be inferred from the domains
    '* of g(x) and h(x) and is thus 2 <= x <= 3 
    '* obviating the need for me to write the line explicitly

    i = h(g(x))
End Function

Sorry if this is a contrived example but real world instances do arise in my experience.

I guess in formal terms the language would need 'declarative definition of function domains'.

So could, in theory, a programming language support this?

Could this be related to Constraint programming - Wikipedia?

Other Links:

  • You could try to enforce such domains with types of parameters, e.g. void f(int_range<2, 3>) or something like this. However, I don't know if mainstream (C#, C++, etc.) languages (or rather, their compilers) would be amendable to this. Try ML-derived languages if you want enhanced inference powers. – Mael Mar 14 '18 at 12:33
  • 1
    I did not downvote, but the question got also a close vote for being a request for 3rd party resources like programming languages. So I took the freedom and changed the wording of the last sentence slightly to make it clear that's not the focus of the question. – Doc Brown Mar 14 '18 at 13:05
  • @Mael C# has something similar if I am not mistaken, the Code Contracts. – wondra Mar 14 '18 at 13:55
8

Let D(f) be the domain of a function f, C(f) its codomain and & the intersection operator. Let further g^-1(M) the domain values of g which map into a certain set M. Then one can write the domain of i as

 D(i) =  g^-1 ( C(g) & D(h) )

So as you see, there is more involved than just the domains of g and h, one needs to know the codomain of g and the reverse mapping g^-1 for an arbitrary subset of that codomain.

This boils down to knowing the exact behaviour of the function g, not just those domains. So except for very simple or restricted functions g, the only general way to achieve this is probably to fill some map for every value of D(g), and calculate the reverse mapping for each value of C(g) & D(h) one by one. This might be possible for small, finite sets D(g) and D(h), but it becomes unfeasible when D(g) and D(h) are too huge to fit fully into the available memory space (for example, when x in g(x) is a double value or a 64 bit integer with no further restrictions).

Note further this becomes impossible (in general) if g behaves "nasty" and goes into an endless loop. Then the analyser would need to solve the halting problem.

  • 1
    Can I ask why do you speak of finite sets? Boundary conditions are typically expressed as inequalities x>=2. – S Meaden Mar 14 '18 at 13:55
  • 5
    Because even if the domain for a function is a simple inequality, that doesn't help much for. Consider g(x) = sin(x), h(x) = 1/x and i = (g ∘ h): the domain of i is R \ {2pi*k | k in N}, but the domains of g and h are R and R \ {0} respectively. To figure out what the input of h is going to be, you need to know not only the image of g but also how it is derived from it's input. ... and I'm pretty sure that's equivalent to the halting problem. – Jasmijn Mar 14 '18 at 14:28
  • @Robin: ok, I can imagine stepping beyond linear constraints to be a problem. How about restricting it linear constraints? – S Meaden Mar 14 '18 at 14:34
  • 4
    @SMeaden: Robin's example is already one with linear constraints (on the input domains of g and h). I guess the problem can be solved efficiently if one restricts it to linear constraints and monotone functions in one real valued parameter, but that would be very restrictive, don't you think so? – Doc Brown Mar 14 '18 at 14:52
  • Happy to restrict to (i) linear, (ii) monotonic, (ii) real-values, sure no problem that covers the vast majority of the code I write. Could you stretch to multiple variables? Also, constraints expressed in relation to the other variables, so x+y<50. Did you see I edited question to include link to Constraint programming? – S Meaden Mar 14 '18 at 15:22

Your Answer

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

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