function-combinators/notes.org

Prerequisites

(import (ice-9 exceptions))

(define identity (λ (anything) anything))

<>

(define assert (λ (condition if-false-message) (cond [condition 'no-error] [else (raise-exception (make-exception (make-non-continuable-error) (make-exception-with-message (simple-format #f "~a ~a" "assertion error:" if-false-message)) #;(make-exception-with-irritants (list dividend divisor)) #;(make-exception-with-origin 'divide)))])))

Function combinators

Function combinators are functions, which take functions as input and return functions, which make use of the given functions, combining them in useful ways. Functions have a range of valid input values and an output range of values. Combinators combine functions in such a way, that the resulting functions consider the input range and output range of the combined functions naturally.

Composition

For example there is the combinator of function composition:

(define compose ;; take 2 functions (λ (outer inner) ;; return a function, which takes any number of ;; arguments. (λ (. args) ;; the combination, or function composition in this ;; case, which applies first the inner function and ;; then the outer function. (outer (apply inner args)))))

:results: :end:

Usage

Its usage could look like the following:

<>

(define times-2-plus-3 (compose (λ (n) (+ n 3)) (λ (n) (* n 2))))

(simple-format (current-output-port) "~a\n" (times-2-plus-3 4))

:results: 11 :end:

Iterate

The iterate combinator makes use of the compose combinator internally, giving an example of how combinators can be used to build other combinators.

<>

(define iterate (λ (n) "Return a function, which applies the given function n times by composing it n times." (λ (iteratee) (let compose-iter ([iter-count 0]) (cond [(= iter-count n) identity] [else (compose iteratee (compose-iter (+ iter-count 1)))])))))

:results: :end:

One important thing to note is, that neither compose nor iterate need to know anything about the actual functions, which they are combining. They constitute a separate abstraction layer, that deals with combining functions and not with the actual implementation inside functions. In fact it would be detrimental to the usage of combinators, if they had built in assumptions about the functions, which they combine.

Usage

The usage of iterate is for example the following:

<>

(simple-format (current-output-port) "~a\n" (((iterate 3) (λ (n) (+ 7 n))) 0))

:results: 21 :end:

Parallel combine

The parallel-combine combinator takes a function (func-1), which combines the results of 2 other functions (func-2 and func-3). It is named parallel, because the 2 other functions are evaluated independently and their results are then used as inputs for func-1. It does not relate to parallelism as in using multiple cores. However, the structure of the combinator makes it possible to evaluate func-2 and func-3 on separate cores, taking advantage of a multi core system. Combinators make no assumption to be used on a single or multi core machine.

(define parallel-combine (λ (func-1 func-2 func-3) ;; function combinators return functions (λ (. args) (func-1 (apply func-2 args) (apply func-3 args)))))

:results: :end:

In simple terms: Take 3 functions. Return a function. That function does the following: Take arguments. One of the functions applied to the results of the other 2 functions when applied to the arguments.

Naturally this requires one of the other 2 functions to either be able to work with arbitrary numbers of arguments, or both functions to be of the same arity.

Usage

The usage is as follows:

<>

(define sum-and-product (λ (a b) ((parallel-combine list (λ (arg1 arg2) (+ arg1 arg2)) (λ (arg1 arg2) (* arg1 arg2))) a b)))

(simple-format (current-output-port) "~a\n" (sum-and-product 3 4))

:results: (7 12) :end:

Spread combine

The combinator spread-combine requires, that there is a way of determining the arity of a given function. Its idea is to make and return a function, which takes all the arguments of 2 given functions f and g and then internally split those arguments into the ones used by f and g. To perform this split or spread of the arguments, the resulting function needs to know how many arguments are meant to be used for f. Knowing that number of arguments, the rest of the arguments will be given to g. The results of f and g will be used as 2 arguments for h, which combines the results in some way.

In order to implement spread-combine, first a mechanism for determining the arity needs to be implemented. It is implemented here in a general way, by passing functions inside structs, which carry the additional information. There might be more language specific ways to do this, depending on the programming language, that is used to implement the combinators for. Here we make use of composition in form of structs, which we can extend to have more fields, if we need to do so.

One disadvantage of this approach is, that it will affect how users can use the function combinators. They will have to use special functions to work with the structs instead of using the usual functions like apply on functions. However, the functions each travelling with their own arity specification will prevent usage of global state. It will therefore enable using the combinators concurrently without mutex constructs.

(import ;; structs (srfi srfi-9) ;; for functional structs (not part of srfi-9 directly) (srfi srfi-9 gnu))

(define-immutable-record-type ;; define constructor (make-arity-func func min-arity max-arity) ;; define predicate arity-func? ;; define accessors and functional setters (func arity-func-func) (min-arity arity-func-min-arity set-arity-func-min-arity) (max-arity arity-func-max-arity set-arity-func-max-arity))

(define get-arity (λ (f) "return an arity, if it is clear from the min arity and max arity" (cond [(eqv? (arity-func-min-arity f) (arity-func-max-arity f)) (arity-func-min-arity f)] [else #f])))

(define restrict-arity (λ (f min-arity max-arity) "set the arity of a function" (cond [(arity-func? f) (set-fields f ((arity-func-min-arity) min-arity) ((arity-func-max-arity) max-arity))] [else (make-arity-func f min-arity max-arity)])))

(define arity-func-apply (λ (f args) (let ([num-args (length args)]) (cond [(and (>= num-args (arity-func-min-arity f)) (<= num-args (arity-func-max-arity f))) (apply (arity-func-func f) args)] [else (raise-exception (make-exception (make-non-continuable-error) (make-exception-with-message (simple-format #f "wrong arity of ~a: min-arity: ~a, max-arity: ~a, number of supplied arguments: ~a" f (arity-func-min-arity f) (arity-func-max-arity f) num-args)) (make-exception-with-origin 'arity-func-apply) (make-exception-with-irritants args)))]))))

(import (prefix (srfi srfi-1) srfi-1:))

<> <>

(define spread-combine (λ (h f g) (let* ([arity-of-f (get-arity f)] [arity-of-g (get-arity g)] [sum-arity (+ arity-of-f arity-of-g)]) (define the-combinator (λ (. args) ;; always perform arity checks (assert (= (length args) sum-arity) "in spread-combine: arity of supplied functions does not agree with number of supplied arguments") (let ([args-f (srfi-1:take args arity-of-f)] [args-g (srfi-1:drop args arity-of-f)]) (h (arity-func-apply f args-f) (arity-func-apply g args-g))))) ;; restrict the resulting function's arity to be the sum of the arities of ;; the 2 given functions f and g (restrict-arity the-combinator sum-arity sum-arity))))

:results: :end:

<>

(simple-format (current-output-port) "~a\n" (arity-func-apply (spread-combine list (make-arity-func (λ (a b) (list 'foo a b)) 2 2) (make-arity-func (λ (x y z ignored1 ignored2) (list 'bar x y z)) 5 5)) '(1 2 3 4 5 6 7)))

:results: ((foo 1 2) (bar 3 4 5)) :end:

Exercises

Compose with arity checks

<> <>

(define compose (λ (outer inner) (let ([min-arity-inner (arity-func-min-arity inner)] [max-arity-inner (arity-func-max-arity inner)]) (define the-combinator (λ (. args) (let ([num-args (length args)]) ;; check for arity (assert (and (>= num-args min-arity-inner) (<= num-args max-arity-inner)) (simple-format #f "arity mismatch: Expected at least ~a arguments and at most ~a arguments. Received ~a arguments." min-arity-inner max-arity-inner num-args)) (assert (= (arity-func-min-arity outer) 1) (simple-format #f "arity mismatch: outer function takes at least ~a arguments. Received 1 argument." (arity-func-min-arity outer))) ;; then apply (arity-func-apply outer (list (arity-func-apply inner args)))))) ;; restrict arity of the combinator (restrict-arity the-combinator min-arity-inner max-arity-inner))))

:results: :end:

<>

(simple-format (current-output-port) "~a\n" (arity-func-apply (compose (make-arity-func (λ (c) (* c 10)) 1 1) (make-arity-func (λ (a b) (+ a b)) 2 2)) '(3 4)))

:results: 70 :end:

Parallel combine with arity checks

<> <>

(define parallel-combine (λ (h f g) (let ([min-arity-f (arity-func-min-arity f)] [max-arity-f (arity-func-max-arity f)] [min-arity-g (arity-func-min-arity g)] [max-arity-g (arity-func-max-arity g)])

(assert (and (>= max-arity-f min-arity-g) (>= max-arity-g min-arity-f)) (simple-format #f "arity mismatch: Minimum and maximum arities of ~a and ~a incompatible." f g)) (define the-combinator (λ (. args) (let ([num-args (length args)]) ;; check arity of given arguments (assert (and (>= num-args (max min-arity-f min-arity-g)) (<= num-args (min max-arity-f max-arity-g))) (simple-format #f "arity mismatch: Combinator expects at least ~a arguments and at most ~a arguments. Received ~a arguments." (max min-arity-f min-arity-g) (min max-arity-f max-arity-g) num-args)) (h (arity-func-apply f args) (arity-func-apply g args))))) ;; declare arity for later inspection (restrict-arity the-combinator (max min-arity-f min-arity-g) (min max-arity-f max-arity-g)))))

:results: :end:

<>

(simple-format (current-output-port) "~a\n" (arity-func-apply (parallel-combine list (make-arity-func (λ (arg1) (+ arg1)) 1 1) (make-arity-func (λ (arg1 arg2) (* arg1 arg2)) 2 2)) (list 3 4)))

:results: ice-9/boot-9.scm:1669:16: In procedure raise-exception: ERROR:
1. &non-continuable
2. &message: "assertion error: arity mismatch: Minimum and maximum arities of #< func: #:120:37 (arg1)> min-arity: 1 max-arity: 1> and #< func: #:121:37 (arg1 arg2)> min-arity: 2 max-arity: 2> incompatible."

   Entering a new prompt. Type `,bt' for a backtrace or `,q' to continue. scheme@(guile-user) [1]> :end:

   Plan for handling minimum and maximum arity

   The plan for handling minimum and maximum arity is to somewhere store the minimum and maximum arity. In some programming languages the arity might not be easily accessible. In order to still provide access to the arity, the functions are wrapped in a struct arity-func, which contains the arity information. However, this requires special procedures to work with the struct. Instead of apply arity-func-apply is used and arity functions cannot be applied as usual functions would.

   If one assumes to work with a programming language, where the minimum and maximum arities are readily accessible for normal procedures, one would not need to wrap the functions into an additional struct.

   An alternative would be to use global state to store arity information, instead of letting it travel inside a struct along with the function.

   Instead of storing only one arity for a function both minimum and maximum arity need to be stored.

   Spread combine with arity checks

   (import (prefix (srfi srfi-1) srfi-1:))

   <> <>

   (define spread-combine (λ (h f g) (let* ([min-arity-f (arity-func-min-arity f)] [max-arity-f (arity-func-max-arity f)] [min-arity-g (arity-func-min-arity g)] [max-arity-g (arity-func-max-arity g)])

   (define the-combinator (λ (. args) (let ([num-args (length args)]) ;; perform arity checks (assert (and (>= num-args min-arity-f)) (simple-format #f "arity mismatch: insufficient arguments for ~a. Given ~a arguments." f num-args)) (assert (and (>= num-args min-arity-g)) (simple-format #f "arity mismatch: insufficient arguments for ~a. Given ~a arguments." g num-args))

   ;; When there are minimum and maximum arity, it might be the case, ;; that we cannot find only a single answer to the question, how many ;; arguments f should consume and how many it should leave for ;; g. Instead there could be multiple possibilities. We choose the ;; convention, that f takes as many as possible, while still leaving ;; as many as needed for g to work.

   ;; Substract the minimum required arguments of g from the number of ;; arguments given to the combinator. This is the amount of ;; arguments f can at most take. (let ([num-remaining-args-for-f (- num-args min-arity-g)]) ;; If the remaining number of arguments is too low for f, throw an ;; exception. (simple-format (current-output-port) "remaining args for f: ~a\n" num-remaining-args-for-f) (assert (>= num-remaining-args-for-f min-arity-f) (simple-format #f "arity mismatch: insufficient arguments for ~a and ~a. Given ~a arguments." f g num-args)) (let ([args-f (srfi-1:take args num-remaining-args-for-f)] [args-g (srfi-1:drop args num-remaining-args-for-f)]) (simple-format (current-output-port) "args-f: ~a\n" args-f) (simple-format (current-output-port) "args-g: ~a\n" args-g) (h (arity-func-apply f args-f) (arity-func-apply g args-g)))))))

   ;; restrict the resulting function's arity (restrict-arity the-combinator (+ min-arity-f min-arity-g) (+ max-arity-f max-arity-g)))))

   <>

   (simple-format (current-output-port) "~a\n" (arity-func-apply (spread-combine list (make-arity-func (λ (a b) (list 'foo a b)) 2 2) (make-arity-func (λ (x y z ignored1 ignored2) (list 'bar x y z)) 5 5)) '(1 2 3 4 5 6 7)))

   :results: remaining args for f: 2 args-f: (1 2) args-g: (3 4 5 6 7) ((foo 1 2) (bar 3 4 5)) :end:

   local variable definitions noexport