Lisp's default syntax doesn't lend itself to composition. Chicken Scheme has a compose function, but it's hard to imagine why one would run
((compose (lambda (x) (* x 2)) (lambda (x) (+ x 1))) 1)
instead of
(* 2 (+ 1 1))
If one squints past parentheses, the notion of f ∘ g is already encoded in s-expressions anyway. Couple that with the fact that partial application doesn't exist in Scheme, and point-free programming comes across as pointless. That is, unless there were a way to modify Lisp syntax to make it more approachable.
Scheme's eager evaluation strategy prevents partially-applied functions like (+ 1) from being passed around as parameters. All procedures have to be wrapped in lambdas instead. But what if there were a syntax extension that provided an implicit closure to an incomplete procedure?
(define-syntax λ (syntax-rules () ((_ . α) (lambda . α))))
(define-syntax delay
(syntax-rules ()
((_ (f ...)) (λ (α) (f ... α)))
((_ f ...) (λ (α) (f ... α)))))
It is now possible to write something like the following, and get a curried procedure back.
> (delay (+ 1))
#<procedure (? α405)>
Then apply it.
> ((delay (+ 1)) 1)
2
But what use is an invisible closure if a conspicuous macro is required to declare it? This demands a higher level of abstraction: an environment where calls to delay are themselves implicit.
If compose were augmented to apply delay to each of its parameters, it might actually be useful. Consider this macro, which recursively builds a list of closures from regular syntax.
(define-syntax delay-params
(syntax-rules ()
((_ f) (list (delay f)))
((_ f g ...) (cons (delay f) (delay-params g ...)))))
In action.
> (delay-params iota (* 2) (+ 1))
(#<procedure (? α408)> #<procedure (? α415)> #<procedure (? α421)>)
As you might imagine, these individual lambdas can now be composed by folding a simple function application procedure over the list.
(define (application f α) (f α))
(define-syntax composition
(syntax-rules ()
((_ f ...) (λ (α) (foldr application α (delay-params f ...))))))
(define-syntax ∘ (syntax-rules () ((_ . α) (composition . α))))
It's starting to look useful.
> ((∘ iota (* 2) (+ 1)) 1)
(0 1 2 3)
Still a long way from the complex tacit control flow promised by Haskell and J, however. More abstraction is necessary.
There's a fundamental overhead to declaring a composition chain instead of using a direct s-expression—one that is difficult to justify at the moment. In order to get any practical use out of this concept, we must commit to living inside a point-free environment, complete with a DSL of tacit macros that build on the primitive procedures defined above.
The fanout and splitStrong functions from Haskell's Arrow library are easily-implemented additions to this language within a language.
(define-syntax fanout
(syntax-rules ()
((_ f ...) (λ (α) (map (λ (ω) (ω α)) (delay-params f ...))))))
(define-syntax split-strong
(syntax-rules ()
((_ f ...) (λ (α) (map application (delay-params f ...) α)))))
(define-syntax &&& (syntax-rules () ((_ . α) (fanout . α))))
(define-syntax *** (syntax-rules () ((_ . α) (split-strong . α))))
These powerful operators abstract parallel computation. &&& performs multiple functions against one value.
> ((&&& + (+ 1) (+ 2)) 1)
(1 2 3)
While *** performs multiple functions against multiple values.
> ((*** (iota 1) (iota 2) (iota 3)) '(1 2 3))
((1) (2 3) (3 4 5))
Scheme's weak typing and variadic nature have a serious advantage here; both procedures can operate on an arbitrary number of parallel channels, while Haskell is limited to pairs.
The implementations of &&& and *** are wrapped in closures as well. All the macros defined in this article are. While it is likely that most of these functions will be run inside a composition chain with implicit delay, I wanted to ensure that they retain this behavior when used on their own as well. It is possible to do the following, for instance.
> (map (&&& (+ 1) (+ 2)) '(1 2 3))
((2 3) (3 4) (4 5))
No lambdas necessary. This advantage becomes a liability when used in a composition, however.
> ((∘ (*** (iota 1 1) (iota 2 2) (iota 3 3)) (&&& + (+ 1) (+ 2))) 1)
#<procedure (? α595)>
Because the parameters to ∘ are automatically curried, but &&& and *** are already tacit, the expression wraps its values in unnecessary closures and fails to compose. delay cannot be blindly applied.
A complimentary macro to delay, appropriately named delay? is defined as follows.
(define-syntax delay?
(syntax-rules (∘ λ &&& ***)
((_ (∘ α ...)) (composition α ...))
((_ (λ α ...)) (lambda α ...))
((_ (&&& α ...)) (fanout α ...))
((_ (*** α ...)) (split-strong α ...))
((_ (f α ...)) (delay f α ...))
((_ f) (delay f))))
Before applying delay, it will first pattern match for members of the point-free DSL, which are invoked normally since they themselves are already delayed. Only a non-matching function will be wrapped in a closure. delay-params is redefined in terms of delay?.
(define-syntax delay-params
(syntax-rules ()
((_ f) (list (delay? f)))
((_ f g ...) (cons (delay? f) (delay-params g ...)))))
And then delayed environments stack properly.
> ((∘ (*** (iota 1 1) (iota 2 2) (iota 3 3)) (&&& + (+ 1) (+ 2))) 1)
((1) (2 4) (3 6 9))
All subsequently defined macros must have an entry in delay? if they are to compose properly.
All is still not well. Thanks to delay? something like the following will work.
(&&& (∘ not even?) identity)
But a simple nested call will not be properly coerced into point-free form.
(&&& (not (even?)) identity)
The patterns that delay matches against are too shallow to handle the latter case. It must be redefined to include an additional recursive call to delay?.
(define-syntax delay
(syntax-rules ()
((_ (f (g ...))) (λ (α) (f ((delay? (g ...)) α))))
((_ (f ...)) (λ (α) (f ... α)))
((_ f ...) (λ (α) (f ... α)))))
Now the implicit parameter will be passed along to the deepest level of a nested call, with respect for normal functions and macros alike.
What would a concatenative programming language be without the S combinator?
(define-syntax hook
(syntax-rules ()
((_ (f ...) g ...) (λ (α) ((composition (f ... α) g ...) α)))
((_ f g ...) (λ (α) ((composition (f α) g ...) α)))))
(define-syntax ◁ (syntax-rules () ((_ . α) (hook . α))))
A list could be doubled with it.
> ((◁ append identity) '(1 2 3))
(1 2 3 1 2 3)
How about cloning the head of a list?
> ((◁ (flip cons) car) '(1 2 3))
Error: bad argument count - received 3 but expected 1: #<procedure (chicken.base#flip proc)>
This doesn't work. (flip cons) is not a partial application like (+ 1), but it is matched in the same pattern. It doesn't compose with the DSL and needs special consideration.
(define-syntax flipping
(syntax-rules ()
((_ f α ...) (λ (ω) (f ω α ...)))))
(define-syntax ~ (syntax-rules () ((_ . α) (flipping . α))))
Now it works.
> (define clone (◁ (~ cons) car))
> (clone '(1 2 3))
(1 1 2 3)
It's quickly becoming apparent how brittle our macromatic makeover actually is; expect to deal with many such edge cases.
A liftM2 style fork is also essential.
(define-syntax fork
(syntax-rules ()
((_ (f ...) g ...) (λ (α) ((composition (apply f ...) (&&& g ...)) α)))
((_ f g ...) (λ (α) ((composition (apply f) (&&& g ...)) α)))))
(define-syntax ∴ (syntax-rules () ((_ . α) (fork . α))))
So many recursive Lisp functions call for performing one procedure on a car and another on a cdr. What better way to represent this than as follows?
(define (consf f g) (∴ cons (∘ f car) (∘ g cdr)))
As useful as these special combinators are, the bread and butter of a point-free environment is common functions like map and filter. Using these procedures without lambdas means redefining them as macros, but they luckily all follow a common pattern.
(define-syntax tacit-f
(syntax-rules ()
((_ f g α ...) (lambda (ω) (f (delay? g) α ... ω)))))
(define-syntax tacit-map (syntax-rules () ((_ . α) (tacit-f map . α))))
(define-syntax tacit-filter (syntax-rules () ((_ . α) (tacit-f filter . α))))
(define-syntax tacit-find (syntax-rules () ((_ . α) (tacit-f find . α))))
(define-syntax tacit-for-each(syntax-rules () ((_ . α) (tacit-f for-each . α))))
(define-syntax ⇒ (syntax-rules () ((_ . α) (tacit-map . α))))
(define-syntax ⇐ (syntax-rules () ((_ . α) (tacit-filter . α))))
(define-syntax ∈ (syntax-rules () ((_ . α) (tacit-find . α))))
(define-syntax ∀ (syntax-rules () ((_ . α) (tacit-for-each . α))))
The foldr and foldl functions aren't redefined because they take a binary function as parameter. The advantages of a function like
(⇒ (+ 1))
are clear, but folding with a partially-applied procedure has dubious utility. The list argument to a fold can be omitted by placing it in a standard composition, of course.
(define ← foldl)
(define ι iota)
(define ⌐ flatten)
> ((∘ (◁ - (* 2)) (← + 0) ⌐ (⇒ (⇐ (> 6))) (*** (ι 1 1) (ι 2 2) (ι 3 3)) (&&& (+ 1) (+ 2) (+ 3))) 1)
-11
With some more symbolic synonyms, we're halfway to a weird sort of APL. Imagine what an expression like this would look like with lambdas.
If you'd like to see this experiment taken to its insane conclusion, please check out my pointless library. It has point-free versions of if and cond, as well as a whole lot more glyphs. And I mean it when I say "experiment." I have no idea if this DSL actually makes for better Scheme code.