FnOio / fno-specification

Repository for https://w3id.org/function/spec
6 stars 1 forks source link

Composing functions and partially applying functions? #3

Closed fkleedorfer closed 2 years ago

fkleedorfer commented 3 years ago

I am using fno for a mapping use case: You have a feature F1 in system S1 that should be mapped to feature F2 in system S2. The idea is that, if you define mappings for all features, you are able to transform a document that uses system S1 into a document that uses system S2.

That requires a definition of a mapping using fno, which doesn't seem to be covered by the ontology (and tools) as it is. The difficulty arises where we define mappings as fno:Executions, but we are not actually recording a specific execution: it is a definition of the function that has to be applied to any concrete instance of the input feature(s). However, some of the function's parameters have already been set (for example regex and replace strings), so it's not taking these parameters any more. You could say, the function has been curried.

Our solution to the problem is to introduce a new kind of parameter/output: a Pipe. Basically it's an RDF resource that can be used as an output in one function and as a parameter in another. Thus, it's possible to concatenate function executions.

The structure of a mapping is:

I am interested in how you would approach the problem. I am halfway there in implementing it - now starting with function implementations in java - and I am not particularly keen on maintaining a fork, so if you think this could be useful, I'd be happy to work this into the framework and contribute here. Alternatively, I may have missed how this is already supported by fno, in which case I'd be grateful for a hint.

Example:

# params/outputs

# IRI of a resource with rdf:type :Feature
:paramStringFeature
    a fno:Parameter ;
    fno:property :stringFeature ;
    :rdfType :Feature ;              # I was missing a way to specify rdf:type of the value if it's an IRI, not a literal
    :featureKind :StringType ;   #this is application-specific, ignore
    fno:required true .

# pipe for an output string (ie. pipe used as sink)
:outputString
    a fno:Output ;
    fno:type xsd:string ;
    fno:name "String Output" ;
    fno:property :resultString ;
    :valueSinkProperty :stringSink ; # equivalent of fno:property for specifying a pipe as a sink
    fno:required true ;
    dc:description "String output of a function"@en .

# pipe for a string parameter (ie. pipe used as source)
:paramString
    a fno:Parameter ;
    fno:type xsd:string ;
    fno:name "String Input" ;
    fno:property :inputString ;
    :valueSourceProperty :stringSource ;  # equivalent of fno:property for specifying a pipe as a source
    fno:required true ;
    dc:description "String input of a function"@en .

# read/write functions

# pass this function the IRI of a string feature and it will assign the feature's string value to the :outputString output
:readStringFeature
    a fno:Function ;
    fno:name "ReadStringFeature" ;
    fno:expects ( :paramStringFeature ) ;
    fno:returns ( :outputString ) ;
    dc:description "Reads the value of the string feature and returns it."@en .

# pass this function the IRI of a string feature and a string value and it will write that feature with the specified value
:writeStringFeature
    a fno:Function ;
    fno:name "WriteStringFeature" ;
    fno:expects ( :paramStringFeature :paramString );
    dc:description "Writes the input string value to the specified string feature."@en .

# regex replace function

:regexReplace
    a           fno:Function ;
    fno:name    "regex replace"@en ;
    fno:expects ( :paramString :paramRegex :paramReplacement );
    fno:returns ( :outputString ) ;
    dc:description
                "Applies the regular expression replacement on the input string and returns the result"@en .

:paramRegex
    a            fno:Parameter ;
    fno:name     "regular expression"@en ;
    fno:type     xsd:string ;
    fno:required true ;
    fno:property   :regex ;
    :valueSourceProperty   :regexSource  .

:paramReplacement
    a            fno:Parameter ;
    fno:name     "replacement expression"@en ;
    fno:type     xsd:string ;
    fno:required true ;
    fno:property   :replacement ;
    :valueSourceProperty   :replacementSource  .

# execution

:regexReplaceExecution1
    a                fno:Execution ;
    fno:executes     :regexReplace ;
    :stringSource :featureA1ValuePipe ;
    :regex        "_ACME-CORP_" ;
    :replacement  "_ECORP_" ;
    :stringSink   :convertedValuePipe1 .

:read1
    a                 fno:Execution ;
    fno:executes      :readStringFeature ;
    :stringFeature :featureP1-A1-1 ;
    :stringSink    :featureA1ValuePipe .

:write1
    a                 fno:Execution ;
    fno:executes      :writeStringFeature ;
    :stringSource  :convertedValuePipe1 ;
    :stringFeature :featureP1-B1-1 .

# domain specific mapping, for context, shows how the three executions are aggregated as one mapping
:mappingP1-A1-1-B1-1
    a                    :FeatureMapping ;
    :inputFeature     :featureP1-A1-1 ;  # ignore, this is domain-specific
    :outputFeature    :featureP1-B1-1 ;   # ignore, this is domain-specific
    s:creator            "originalAuthorId" ;   # ignore, this is domain-specific
    s:editor             "lastEditorId" ;   # ignore, this is domain-specific
    s:dateCreated        "2020-09-21 00:00:00" ;   # ignore, this is domain-specific
    s:dateModified       "2020-09-21 00:00:00" ;   # ignore, this is domain-specific
    :mappingExecution :read1, :regexReplaceExecution1, :write1 .

EDIT: added some # ignore, this is domain-specific lines

bjdmeest commented 3 years ago

Thanks for this! It looks really interesting!

First of all: indeed, piping/composition/nesting functions is not described within FnO (yet). I would need to have a closer look on your proposal, one thing that immediately comes to mind is that maybe the mappingExecutiong range should be an rdf:List, otherwise you semantically don't know the order. You can probably infer it in this case, but I'm not sure that would work for any sequence of piped functions.

One of the ideas I had in mind for a composition of functions, is to make sure that a function that is a composition of functions is in fact described similarily than a 'normal' function, i.e., an implementation could transparently choose between an implementation that implements the entire composited function, or by compositing different implementations dynamically.

Let's say we have a function h(a, c, d) described using FnO, that describes one atomary action: "add c and d, and multiply a with the result ". You could also have a multiplication function f(a, b), and a sum function g(c, d), so you could describe h as

h(a, c, d) === f(a, g(c, d))

When describing compositions of functions, I think you could create more flexible systems if you allow implementations to dynamically choose between h(a, c, d) or f(a, g(c, d)), depending on the implementations available to them (and also maybe based on other parameters such as performance, memory consumption, etc.)

This would then require some kind of meta-description that specifies that h(a, c, d) === f(a, g(c, d)), with a structure like below

- h'(a', c', d') is a complexFunction for h
  - root function: f
    - parameter a' of f' === parameter a of f
    - parameter b' of f' === output of g
      - parameter c' -> parameter c of g
      - parameter d' -> parameter d of g

However, this is verrry draft, I'm not sure yet how it aligns with your proposal, and which one would be best, but you asked for my input, so here it is ;).

Happy to discuss further!

fkleedorfer commented 3 years ago

Commenting as I work through your post:

one thing that immediately comes to mind is that maybe the mappingExecutiong range should be an rdf:List, otherwise you semantically don't know the order.

It does not matter: the execution order of the functions is defined by the DAG defined by the pipes. Begin with the functions for which you have all the inputs, continue until you've executed all the functions once.

fkleedorfer commented 3 years ago

However, this is verrry draft, I'm not sure yet how it aligns with your proposal, and which one would be best, but you asked for my input, so here it is ;).

You could express f(a, g(c, d)) using the proposed approach: g outputs to a pipe, f takes a as a normal param, and the pipe as the other one. Just replace :MappingFunction in the example with fno:ComplexFunction (sidenote: the name may be misleading to thinking about complex numbers).

fkleedorfer commented 3 years ago

What I am still not so sure about is the distinction between fno:Function and fno:Execution in the example I gave.

:regexReplaceExecution1, :read1, and :write1 are all fno:Executions. I modeled it this way because the parameters/outputs are already concrete (and not parameter/output resources describing possible parameters/outputs). But using the pipes I sort of make the fno:Executions second-degree functions, as the executions will be applied to the values provided via the pipes.

I am sure I can make that work in practice. But how to make that work in theory?

fkleedorfer commented 3 years ago

the execution order of the functions is defined by the DAG defined by the pipes

Sorry, that was incorrect. It's not a DAG. Still, ordering the executions would not help, we have to do a recursion through the network.

fkleedorfer commented 3 years ago

Here's a suggestion that, I think, resolves all the problems mentioned so far, at the expense of a bigger amount of triples.

It's taking your example h(a, c, d) = f(a, g(c, d)), and it adds an additional 'partial application' operation, which allows us to set parameters to constant values without having to use fno:Executions.

At the end, there is an fno:Execution of the composed function.

Any additional assertions about how the composed function relates to the constituent functions could be added to :myFun.. however, I don't think there is more to say than how parameters and outputs are connected.

## additional resources for fno ontology

fno:PartiallyAppliedFunction rdf:type owl:Class ;
    rdfs:subClassOf fno:Function .

fno:partiallyApplies rdf:type owl:ObjectProperty ;
    rdfs:domain fno:PartiallyAppliedFunction;
    rdfs:range fno:Function .

fno:Composition rdf:type owl:Class ;
    rdfs:subClassOf fno:Function .

fno:CompositionMapping rdf:type owl:Class .

fno:composedOf rdf:type owl:ObjectProperty ;
    rdfs:domain fno:Composition ;
    rdfs:range fno:CompositionMapping .

fno:mapFrom rdf:type owl:ObjectProperty ;
    rdfs:domain fno:CompositionMapping ;
    rdfs:range fno:CompositionMappingEndpoint .

fno:mapTo rdf:type owl:ObjectProperty ;
    rdfs:domain fno:CompositionMapping ;
    rdfs:range fno:CompositionMappingEndpoint .

fno:CompositionMappingEndpoint a owl:Class .

fno:function a owl:ObjectProperty ;
    rdfs:domain fno:CompositionMappingEndpoint ;
    rdfs:range fno:Function .

fno:functionParameter a owl:ObjectProperty ;
    rdfs:domain fno:CompositionMappingEndpoint ;
    rdfs:range fno:Parameter .

fno:functionOutput a owl:ObjectProperty ;
    rdfs:domain fno:CompositionMappingEndpoint ;
    rdfs:range fno:mapTo .

# params/outputs

:intParam1 a fno:Parameter ;
    fno:type xsd:integer ;
    fno:parameter :intInput1 .

:intParam2 a fno:Parameter ;
    fno:type xsd:integer ;
    fno:parameter :intInput2 .

:intParam3 a fno:Parameter ;
    fno:type xsd:integer ;
    fno:parameter :intInput2 .

:intOutput a fno:Parameter ;
    fno:type xsd:integer ;
    fno:parameter :intResult.    

# functions

:addInt a fno:Function ;
    fno:expects ( :intParam1 ) ;
    fno:returns ( :intOutput ) .

:multiplyInt a fno:Function ;
    fno:expects ( :intParam1 :intParam2 ) ;
    fno:returns ( :intOutput ) .

# a partially applied function: sets the second parameter of addInt to 10, 
# the partially applied function has only one parameter left to set

:add10 a fno:PartiallyAppliedFunction;
    fno:partiallyApplies :addInt ;
    :intInput2 10 .  #the fno:parameter is used to provide the concrete value (as is done for fno:Execution)

# Composition

:myFun a fno:Composition ;
    fno:composedOf :mapping1, :mapping2, :mapping3, :mapping4 ;
    fno:expects ( :intParam1 :intParam2 ) ;
    fno:returns ( :intOutput ) .

:mapping1 a fno:CompositionMapping ;   
    fno:mapFrom [ 
        fno:function :myFun ;  
        fno:functionParameter :intParam1 
    ] ;
    fno:mapTo [ 
        fno:function :multiplyInt ;
        fno:functionParameter :intParam1
    ] .

:mapping2 a fno:CompositionMapping ;   
    fno:mapFrom [
        fno:function :myFun ;
        fno:functionParameter :intParam2 
    ] ;
    fno:mapTo [
        fno:function :add10 ;
        fno:functionParameter :intParam1 # param2 no longer a parameter (constant value 10)
    ] .

:mapping3 a fno:CompositionMapping ;
    fno:mapFrom [
        fno:function :add10 ;
        fno:functionOutput :intOutput 
    ] ;
    fno:mapTo [
        fno:function :multiplyInt ;
        fno:functionParameter :intParam2 
    ] .

:mapping4 a fno:CompositionMapping ;
    fno:mapFrom [
        fno:function :multiplyInt ;
        fno:functionOutput :intOutput 
    ] ;
    fno:mapTo [
        fno:function :myFun ;
        fno:functionOutput :intOutput
    ] .

# execution

:myExecution a fno:Execution ;
    fno:executes :myFun ;
    fno:intInput1 2 ;
    fno:intInput2 3 ;
    fno:intResult 26 .

EDIT: renamed the currying concept to partial application EDIT: renamed pipes/wiring to compositionMapping, composedOf etc. EDIT: renamed to fno:mapFrom, fno:mapTo, fno:function, fno:function[Parameter|Output]

fkleedorfer commented 3 years ago

Some design decisions in the latest suggestion might deserve discussion, but the overall idea is, I think, better than the initial design (from the first comment). Before going into the design decisions, I have a question on how to best implement this:

My use case is executing functions defined using the FNO vocabulary (in RDF), for an input determined by the application, in java. The code I found (grel-functions-java and function-processor) don't provide that functionality. Is there any code that I can use (and adapt to include partial application and composition), that would help me reach my goal?

Design considerations:


for which only the definition of a property for providing the constant (akin to fnom:constantPropertyValue) would be needed (here `fno:mapFromConstant`). Then, the form proposed earlier would be a shorthand, and maybe should be avoided because it incurs redundancy.

* there is some overlap with the [`fno:Mapping`](https://fno.io/spec/#fno-Mapping) part of the spec and it should probably be reconciled by the authors (either broaden the terms, such as `fno:function` or change the names in this proposal). 
fkleedorfer commented 3 years ago

So... How would you feel about these additions to the fno vocab and the related implementations?

bjdmeest commented 3 years ago

Is there any code that I can use (and adapt to include partial application and composition), that would help me reach my goal?

We created two proof-of-concept implementations, https://github.com/FnOio/function-handler-java and https://github.com/FnOio/function-handler-js , that might be a starting point.

I get the comment about the fno:Mapping overlap, but I'm not sure it's best to reconcile them. a Mapping provides a connection between an abstract function and a concrete implementation, whereas a Composition is a connection between an abstract function and (an)other abstract function(s).

I would not conflate fno:Function and fno:Composition, but both can exist, so small addition from my side:

:add10 a fno:Function ;
    fno:expects ( :intParam1 ) ;
    fno:returns ( :intOutput1 ) .

:add10Composition a fno:Composition;
    fno:composedOf 
    [
        a fno:parameterCompositionMapping ; #I'd add this bc there's a difference in direction between parameters and outputs
        fno:mapFrom [
              fno:compositionFunction :add10;
              fno:functionParameter :intParam1
        ] ;        
        fno:mapTo [
              fno:compositionFunction :addInt ;
              fno:functionParameter :intParam1
        ] ;
    ],
    [ 
        a fno:parameterCompositionMapping ; 
        fno:mapFromConstant 10 ; # maybe instead we should refine this to also have a resource with a value, because now I think only xsd:literals are an option, what if we want to have more complex resources, one that, e.g., adheres to a SHACL shape?
        fno:mapTo [
              fno:compositionFunction :addInt ;
              fno:functionParameter :intParam2
        ] ;
    ] , 
    [
        a fno:outputCompositionMapping ; 
        fno:mapFrom [
              fno:compositionFunction :addInt ;
              fno:functionOutput :intOutput ;
        ] ;
        fno:mapTo [
              fno:compositionFunction :add10 ;
              fno:functionOutput :intOutput ;
        ]
    ] .

All in all, I was kind of surprised this is actually enough, and still looks quite simple, I'm excited, nice work!

I had a quick test, and this also works well if you're combining compositions, pseudo code below:

# let's assume following functions
doStuff (x)
multiply (x, y)
addInt (x, y)
add10(x)

# then you could create doStuff as following
doStuff (x) {
  return multiply(addInt(x, 10), x)
}
# alternative
doStuff (x) {
  return multiply(add10(x), x)
}

# then the composition is as follows (`multiply_y` denotes "y parameter of multiply", `multiply_` denotes multiply's output)
doStuff
  x -> multiply_y , addInt_x
  "10" -> addInt_y
  addInt_ -> multiply_x
  multiply_ -> doStuff_

# alternative composition
doStuff
  x -> multiply_y , add10_x
  add10_ -> multiply_x
  multiply_ -> doStuff_
add10
  x -> addInt_x
  "10" -> addInt_y
  addInt_ -> add10_

So that's cool :)

I would maybe suggest we start an MR to 'solve' this issue, and have some iterations there to make it part of the spec, at least as 'experimental' for now, would that be something you would like to have a look at?

fkleedorfer commented 3 years ago

Sure - if I understand correctly, you are taking the lead on this - if so: count me in. My short-term interest is getting fno function execution in java, as soon as possible, and I need composition.

A couple of remarks:

bjdmeest commented 3 years ago

Sure - if I understand correctly, you are taking the lead on this - if so: count me in

I'm offline between 3-15/7, so if you could prepare something in the meantime, that would be great though :).

Considering your first two comments, see my following proposal:

:add10Composition a fno:Composition;
    fno:parameterCompositionMapping #we can choose a better name ;)
        [
            fno:mapFrom [
                  fno:compositionFunction :add10;
                  fno:functionParameter :intParam1
            ] ;        
            fno:mapTo [
                  fno:compositionFunction :addInt ;
                  fno:functionParameter :intParam1
            ] ;
        ] ,
        [ 
            fno:mapFromTerm 10 ; # this probably covers all cases
            fno:mapTo [
                  fno:compositionFunction :addInt ;
                  fno:functionParameter :intParam2
            ] ;
        ] ;
    fno:outputCompositionMapping 
        [
            fno:mapFrom [
                  fno:compositionFunction :addInt ;
                  fno:functionOutput :intOutput ;
            ] ;
            fno:mapTo [
                  fno:compositionFunction :add10 ;
                  fno:functionOutput :intOutput ;
            ]
        ] .

I personally like the partial application idea, I didn't thoroughly think it through yet, but certainly, something to take into account.

Thinking of this, it might make sense to have the actual composition vocabulary under a different namespace, a bit like how I currently did the mapping and implementation extensions.

fkleedorfer commented 3 years ago

I've given your suggestion to differentiate between fno:Function and a fno:Composition some thought. My reasoning for the initial design was: A composition is itself a function and so it should just be represented as such (a subclass of fno:Function). However, I think your suggestion is better, here is why:

I cannot name any advantages of realizing compositions as functions, other than: you'll use fewer triples to represent it (but not many). That's not enough.

So I'm ok with your suggestion regarding this.

fkleedorfer commented 3 years ago

Just another note : In your proposal, you mean, the range of fno:mapFromTerm is unrestricted (or, the union of Literal and Resource), I guess? That's fine with me. I fear, though, that it may lead to cumbersome implementations that always need to check the actual value when deciding what do do. If there are two different properties, it's easier to differentiate the cases (e.g. in a SPARQL property path). Do you see this as a problem, too?

Anyway, I think this is a question of style, which should be consistent within one ontology. That line of reasoning leads us to the range of fno:expects/fno:returns (via fno:type), which is deliberately vague: no range is specified. This, in turn, would favor the use of only one property here.

fkleedorfer commented 3 years ago

Given

I would maybe suggest we start an MR to 'solve' this issue, and have some iterations there to make it part of the spec, at least as 'experimental' for now, would that be something you would like to have a look at?

and

Thinking of this, it might make sense to have the actual composition vocabulary under a different namespace, a bit like how I currently did the mapping and implementation extensions.

Which repository should that PR (MR) be made to? I can't seem to find the mapping/implementation extensions in this organization.

bjdmeest commented 3 years ago

Actually, the extensions as explained inline in https://github.com/FnOio/fno-specification/blob/master/section/ontology.md , so maybe adding a third section there could be a good first start :)

The actual ontology terms are defined in https://github.com/IDLabResearch/function-ontology

fkleedorfer commented 3 years ago

We have to rethink this fno:parameterCompositionMapping/fno:outputCompositionMapping business. There is another viable combination: output/parameter. So these are the cases:

I am not sure it helps much to differentiate the cases using an rdf:type on the mapping (as suggested earlier), or even a specific property to link to it (as is the current suggestion), as each case has different requirements for the range of :mapFrom and :mapTo, and we can't really restrict them using owl or rdfs accordingly (correct me if I am wrong). So, in both approaches, one could mark a mapping explicitly (e.g. as parameter/parameter) and still use incorrect opbjects :mapFrom or :mapTo, without any generic system detecting the problem.

I'd go back to the initial suggestion: Composition - composedOf - mapFrom/mapTo because it's a more simple model, and all suggestions so far require fno-specific logic to determine if it is correct.

fkleedorfer commented 3 years ago

Heads-up: I've started the work on the ontology and the spec. I'll make one PR to each repo later today.

fkleedorfer commented 3 years ago

Here they are:

I guess our discussion will continue there.

SemanticBeeng commented 2 years ago

This discussion seems to be about kleisli : https://medium.com/@supermanue/understanding-kleisli-in-scala-9c42ec1a5977