This page is part of the web mail archives of SRFI 25 from before July 7th, 2015. The new archives for SRFI 25 contain all messages, not just those from before July 7th, 2015.
Hello!
I'd like to point out a corroborating evidence in favor of
abstract vectors. The evidence is from a different domain: procedural
texture generation. A texture is a function on a matrix (pixelmap). A
paper presented by Jerzy Karczmarczuk at PADL02 shows that even
intricate and exquisite textures can be described declaratively
(combinatorially) -- often by an order of magnitude shorter than in
traditional, imperative, pixel-shoving approach. It has to be stressed
that textures are expressed in a coordinate-free way. Therefore, the
definition of a complex texture does not depend on storage and other
details of the pixelmap.
A summary of Jerzy's talk is enclosed.
I'd like to make one remark though. The abstract vectors
provide 'random' access to vector elements, so to speak. That is, an
abstract vector is a function Int->Value (or, Range->Value or even
Lattice->Value). The function yields the value of a vector element
given an arbitrary, 'random' index within vector's domain. Sometimes,
random access is overkill. Surprisingly many problems can be solved
with only a sequential access to a vector or a matrix: with matrix
streams. Purely functionally, sequential access is defined by
fold-like combinators (accumulating traversals) and by 'subranging'
(and perhaps, general domain transformer functions). For performance
reasons, we may want to define mapping (i.e., a point-wise transform)
and folding of an associative function. A program that uses these
higher-order combinators can be subjected to automated deforestation,
which fuses traversals where possible.
* Functional Approach to Texture Generation
Jerzy Karczmarczuk. PADL02, January 20, 2002.
The talk describes 'Clastic', a system for generation of _procedural_
textures.
http://users.info.unicaen.fr/~karczma/Work/Clastic_distr/clastic.html
The web site refers to a tutorial with many beautiful pictures.
Raster graphics algorithms can be partitioned into "active" and
"passive". Active algorithms take a pixelmap and actively modify it:
they traverse the pixelmap or a subset of it -- often in complex ways
-- and examine and set pixel values. Bresenham line drawing and
contour filling algorithms belong to that class. Passive algorithms on
the other hand do not actively draw anything. The algorithm is
expressed as a function f(x,y). A rendering engine passes the function
coordinates of a point and expects in return the color value at that
point. The values of x and y of two consecutive invocations of f(x,y)
are generally unpredicable. The function f(x,y) does not have access
to a pixelmap and can't examine pixel values. Texture mapping
algorithms belong to the passive category. Such algorithms -- shaders
-- are used in animation and ray tracing pipelines.
Clastic is an exploratory tool for passive raster graphics. The tool
can generate regular (geometric) or random textures _described_ as
relationships between 2D points and their colors. In Clastic, a
texture is a function R^2 -> R^3, a function from points to RGB color
vectors. The relationship is described purely declaratively.
In Clastic, a texture function can be specified in a low-level way,
for example
circle (x,y) = if x*x + y*y <= 1.0 then tx (x,y) else rgb_white (x,y)
which creates a circle filled with a texture tx(x,y) on a white
foreground. However, if we define a texture combinator
fmask h f g = \x -> if (h x == 0.0) then g x else f x
and an overloaded function
step x | x < zero = zero
| x > zero = one
| otherwise = half
then we can write 'circle' as
circle = fmask (\p -> step (1.0 - norm2 p)) tx rgb_white
or even
circle = fmask (step . (sone .- norm2)) tx rgb_white
where
sone p = 1.0
norm2 (x,y) = x*x+y*y
and .- is subtraction lifted to (Float,Float)->Float functions.
What is remarkable about the latter definition of 'circle' is that
point coordinates do not appear at all. The shader 'circle' is
defined as a pure combination of primitive textures. This
coordinate-free style of programming is strongly encouraged by Clastic
[*]. In Clastic, we transform things rather than coordinates. The
coordinates should be hidden inside higher-order operators such as
translate, rotate, scale; inside primitive textures such as rgb_white;
inside 'soft objects' Point->Float such as 'sone'; and inside blending
combinators such as fmask and `over`.
As the paper and the Clastic tutorial show, combining a few primitives
yields surprisingly complex textures such as impressive geometric
patterns, tesselations and wallpaper including Escher reptiles, and
woven patterns.
Clastic uses purely functional, stateless random number generators
(advocated by Ward). The generators are pure functions Integer->Float
with a property that function values do not visibly correlate even for
neighboring arguments. The "random noise" generators let Clastic
produce dithering, fractal patterns (e.g., clouds), turbulence, and
more complex marble-like textures and bump-maps.
Finally, Clastic can apply transformers to other transformers:
deformers. Examples include warping, lenses and random displacement to
generate irregular wooden grain. The problem of inverting a
transformation is generally rather complex. Still Clastic can deal
with it. As the paper stresses, warping and deformation can be used
abstractly, can be used generically and can be composed. This may make
the coding by an order of magnitude shorter and easier than in the
imperative approach.
[*] Clastic uses programming version of Clean for Windows OS. The
examples above are paraphrased in Haskell.