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