Go Back

Fern Overview + KR and Constraints

Fern is a GUI-toolkit that uses Knowledge-Representation (KR) and multi-way constraints to maintain a tree of cells (aka widgets). This article only describes what already exists and some improvements that have to take place for these. For the picture of further development, see Fern Development Roadmap.

Table of Contents

Fern takes a lot from Garnet, a research GUI toolkit from the 90s. There were some cool applications using it.

Fern is breaking compatibility with Garnet, though, but takes its core ideas and aims to improve on them in a few serious ways. See Fern Development Roadmap for more info. I briefly review Garnet in All Else is Not Enough.

1 Modules

Only the existing modules as of now. There will be more.

1.1 linear-algebra

  • Alias for use in other packages: la.

The major task of this package is to provide a usability layer to April (an APL compiler written entirely in Common Lisp). It's basically a set of wrappers for all the array functions in April. It's not too stable at the moment, some actual field-testing will be required to find any inconsistencies or problems. There are some unit tests.

  • (ql:quickload 'up.mage.fern.linear-algebra)
  • (parachute:test 'fern.linear-algebra)

For an example and a brief explanation, see: Power of Structure/Linear Algebra.

1.1.1 On April and APL

April works on CL arrays.

If you want to write a lot of APL code, you can write it in an .apl files. Then you can define a package-local workspace and just load it. See 2d-vector.lisp of geometry for an example of how it's done. Now, if you stick to apl and apl* of the linear-algebra package, the workspace is automatically used for any expression that you execute.

In general, you can refer to or import functions from other workspaces.

For user-friendliness, APL functions need to have wrappers. All the standard ones do, see main.lisp of linear-algebra. There you will also find a convenient def-op macro to define such wrappers. This macro can be reused in other packages. Check the docstring for its syntax, and, better yet, the actual code using this macro.

April, by-and-large, follows Dyalog. A couple of good resources to understand APL in general are:

Note that Fern doesn't have wrappers for the operators, only for the functions.

Basically, think of April in Fern as something that provides linear algebra capabilities: matrices, vectors, operations on them. It's important to have these for a GUI library. And it won't be necessary to know APL to use Fern as most functions can be understood quite easily by looking at the APL Wiki.

For now, the semantics of the functions is not set in stone. It's yet to be verified that the functions return values that are comfortable to work with. This has to do with APL semantics itself, and we don't always want to impose it on the user. For instance, APL functions take either one or two arguments, either of which can be arrays. So, sometimes it makes sense to make a wrapper that, too, takes an array, and, sometimes, a functions that takes a &rest argument. Sometimes: both, in which case the function that takes an array is postfixed with a *.

Also, the boolean values in APL are just bits: 0/1. The simply-named functions do automatic conversions and return regular t/nil values (that applies even when arrays are being operated on, in which case it's simply checked whether all the values are 1s). The logical 0/1-returning counterparts are designated with l/ in front. There are some examples below.

And, at times, the axis may be specified: that's accounted for as well.

So, there's quite a bit of API-building going on, so refer to the docstrings, to the APL wiki, and if necessary, to the definitions and their macroexpansions.

Here are some examples: 

CL-USER> (ql:quickload 'up.mage.fern.linear-algebra)
CL-USER> (in-package :fern.linear-algebra)
LINEAR-ALGEBRA> (transpose (reshape #(3 2) (i 6)))
#2A((0 2 4) (1 3 5))
LINEAR-ALGEBRA> *2x2* ; internal to linear-algebra
#2A((0 1) (2 3))
LINEAR-ALGEBRA> (catenate *2x2* *2x2* :axis 0)
#2A((0 1) (2 3) (0 1) (2 3))
LINEAR-ALGEBRA> (catenate *2x2* *2x2* :axis 1)
#2A((0 1 0 1) (2 3 2 3))
LINEAR-ALGEBRA> (and 0 1)
NIL
LINEAR-ALGEBRA> (l/and #(1 1 1) #(1 0 1))
#(1 0 1)
LINEAR-ALGEBRA> (l/and* #(1 1 1))
1
LINEAR-ALGEBRA> (and* #(1 1 1))
T

1.2 geometry

  • Alias for use in other packages: ge.

Some geometrical primitives with intersections. Interesting in that there are planes, quadrants, rays, and such. Not all intersections are defined, only the rectangle/* suit is comprehensive. There are some unit tests.

  • (ql:quickload 'up.mage.fern.geometry)
  • (parachute:test 'fern.geometry)

See shapes.lisp to get a better idea of what's what. There you will also find some notes on semantics.

Linear transformation operations acting on shapes are provided.

In general, shapes are immutable. That is, the slots can't be changed (they are declared as :read-only in the struct definition). The whole object has to be transformed instead to produce a new one. This allows to have reliable shapes such as aa-rectangles (where aa means axis-aligned) while retaining inheritance (e.g. from a parallelogram). Some epsilon values are externed by the package to control the precision that determines what's axis-aligned enough.

All shapes have an origin O and a direction v, both 2d-vectors. These two values alone are enough to define many shapes. Some add w as well.

A note on intersect and intersectp: the first one returns a shape that is the result of an intersection. The latter one just tells whether the two given shapes intersect.

There are some access functions like edges and vertices.

Also, there's a morph- function defined for each shape, and it lets you make a copy of a shape with a certain slot changed to another value (the type of the object will change according to the change, e.g. aa-rectangle -> rectangle if you change v and w, but preserve the right angle).

Generic functions are used extensively.

A note about points: there is a point-cloud shape that lets you hold points in some container (like a list or a vector). But, typically, you work on points as a 2xN matrix, and there's a 2d-array type alias to designate those. However, keep in mind that you can't specialize on 2d-arrays in the generic functions as they are now, only on arrays. Using polymorphic-functions should remedy that. There's also a convenient in-2d-array macro for itr for easy iteration.

2d-vectors are used extensively and the package has a function for creating these: vec, e.g. (vec 0 1). This is almost equivalent to just writing down #(0 1), except it implicity attaches type info and sets :adjustable to nil.

Once KR is ready, there will be KR definitions of geometric objects (and the existing operations will extend to these objects too). See Fern Development Roadmap/2D API for Geometry.

Here's an example interaction: 

CL-USER> (ql:quickload 'up.mage.fern.geometry)
CL-USER> (in-package :fern.geometry)
GEOMETRY> (make-parallelogram)
#S(AA-RECTANGLE :O #*00 :V #(1 0) :W #(0 1))
GEOMETRY> (make-parallelogram :O #(0 0) :v #(1 1) :w #(0 1))
#S(PARALLELOGRAM :O #(0 0) :V #(1 1) :W #(0 1))
GEOMETRY> (vertices (make-parallelogram :O #(0 0) :v #(1 1) :w #(-1 1)))
#2A((0 0) (1 1) (0 2) (-1 1))
GEOMETRY> (rotate π/4 (make-parallelogram :O #(0 0) :v #(1 1) :w #(-1 1)))
#S(AA-RECTANGLE
   :O #(0.0d0 0.0d0)
   :V #(1.1102230246251565d-16 1.414213562373095d0)
   :W #(-1.414213562373095d0 1.1102230246251565d-16))
GEOMETRY> (bbox) ; bbox is a convenience alias for making axis-aligned rectangles
#S(AA-RECTANGLE :O #*00 :V #*10 :W #*01)
GEOMETRY> (intersectp (bbox) (make-ray :O #(-2 -2) :v #(1 1)))
T
GEOMETRY> (intersect (bbox) (make-ray :O #(-2 -2) :v #(1 1)))
#S(SEGMENT :O #(0.9999999999999993d0 1.0d0)
           :V #(-0.9999999999999993d0 -1.0d0))

To get an idea of other available operations and entities, package.lisp is a good place to start.

1.3 kr

Has Knowledge-Representation prototype OO and the SkyBlue solver with its multi-garnet integration layer.

There are some tests, both for kr and the constraints. Now, the syntax on the master branch is a bit different, please consult the tests for examples.

For a few basic examples, take a look at sky-blue/examples.lisp. Most examples don't work there (they rely on some old graphics code), but the few simple ones in the beginning do.

So far, only the formula code has been thrown out, both from KR and from SkyBlue (which integrated formulas for compatibility).

1.3.1 Learning about KR and Multiway Constraints

If you wish to take a look at the old Garnet Manual, here it is:

  • Garnet Manual. This can give you a general idea of what programming in Garnet was like. It also contains a pretty good explanation of KR. NOTE: in Fern, formulas are done away with!

But if you are only interested in KR (which will actually be used in Fern), take a look at this instead:

Instead of formulas, the multi-garnet project will be used:

Multi-Garnet employs the SkyBlue constraint solver. See:

(The three papers above may be freely found online, but in PS format: see UW Constraint-Based Languages and Systems. I have just compiled and put them here for convenience.)