Cons List Algebraic Evaluator

What is CLAE?

Clay is a type of fine-grained natural soil containing clay minerals (hydrous aluminum phyllosilicates, e.g. kaolinite Al2Si2O5(OH)4).

Cons List Algebraic Evaluator or CLAE is the next generation of FFBBAE (Fix Function Bind Boolean Algebraic Evaluator) with numbers, booleans, functions, recursion, and now lists. CLAE adds the essential utilities to define, query, and manipulate lists and the capabilities to build even more.

It accomplishes with minimal modifications to the base language, performing nearly all functionality using only primitive list manipulation features. This helps demonstrate how powerful the base language is on its own for building on top of.

What can it do?

  • Environment driven recursion
    • FixV: A ClosureV-like value that allows binding a n identifier to a Fix in a captured environment
  • Lists
    • Lists: ListV type [values] defines a homogenous list of CLAE values. The typing guarantees we cna check whether two different lists are compatible, even [] and []!.
  • List Utilities
    • Cons: Prepends an element to a list
    • Head: Gets the first element of a list
    • Tail: Gets everything but the first element of a list
    • Null: Checks whether a list is empty
  • The Fold
    • It's the best fold (foldr) that we all know, implemented directly from our core list utilities.
    • Used to iterate over a list and build an accumulator
  • Map and Filter
    • If you have fold, you can do anything these can!
    • Map: Applies a function over all values in a list
    • Filter: Returns the elements from a list that satisfy a condition function
  • More List Utilities
    • Length: Finds the length of a list
    • Concat: Combines two lists together into one
    • Index: Maybe, just possibly, quite important. Returns a list with the element at a given index (starting from 0) or an empty list.
    • Take: Gets the first n elements from a list
    • Drop: Returns the list without the first n elements
    • Reverse: !tsil a serseveR

Why these features?

FixV gives the same binding guarantees as a Closure but for all uses of Fix. Nested uses of Fix with the same identifier will properly propagate. This core feature allows us to derive functionality from Fold without risk of substituting the wrong identifiers.

Lists are an essential data structure. They allow us easily store and process related data together. I personally also think the paradigm of treating everything as transforming data form one form to another is quite powerful, and lists allow us to do that on a great scale.

We need a standard set of list utilities for users to use. Without a way to perform cons, head, tail, and null, we can't really work with our lists in a meaninful way. These core expressions let us gather some information about lists and slightly modify them. When combined with functions, they enable building more powerful features.

Fold, map, and filter are what I think are the standard 3 functions to do useful things to lists. They allow you to apply a function over the elements of a list in order to construct new data form it. It's everywhere from computing a sum, scaling a list up or down, or gathering only elements over some threshold.

Finally, the extended set of utilities are just applications of the previous 3 to represent some of the more higher level features expected with lists of all types. They some quality of life functions that would otherwise have to be implemented by the user.

Related Work

Lists are a completely novel concept and I can't believe nobody has ever thought of them before!

Lists are pretty much in every other programming language. They're a very standard feature to have with very standard behavior across the board.

Because of this, I haven't made any modifications to how they work since I wanted it to be easy to adapt expressions in other languages to CLAE. The major difference in usage is that you have to be very explicit with types (see Limitations), where many other languages will do the inferrence for you.

Limitations

Before adding FixV, one of the big limitations was that you could not nest a Fold-derived function within a Fold-derived function. It would conflict the two identifiers and end up substituting them in unexpected ways. With it however, the issue is resolved and combining functions is much easier.

A limitation that couldn't be resolved is the arguably excessive use of types. Because Fold and its derivatives are extensions of the base language, they need type information in order to properly construct the functions that will implement them. This results in the user needing to always specify the output type of the list, even when it's inferrable from a higher level: a reversed list keeps the same type.

Other than this verbosity, I haven't observed any problems with the language.

Analysis

I don't feel successful after the stress of debugging previous implementions and all their insanity, especially after taking on the challenge of implementing everything via fold, but all features mentioned in the language do work! I've verified this against a set of test cases that both incorporate previous assumptions about the language and handle all standard and "tricky" behavior concerning lists. There may still be bugs or unexpected behaviors with more complex functions though, especially with heavy nesting and identifier calls.

Try it out!

CLAE GitHub Repository

Examples:

-- List CLAEType [CLAE]
List TNum [Num 1, Num 2] -- [1, 2] == [1, 2]

-- Cons CLAE List
Cons (Num 1) (List TNum [Num 2]) -- cons 1 [2] == [1, 2]

-- Head List
Head (List TNum [Num 1, Num 2, Num 3]) -- head [1, 2, 3] == 1

-- Tail List
Tail (List TNum [Num 1, Num 2, Num 3]) -- tail [1, 2, 3] == [2, 3]

-- Null List
Null (List TNum []) -- null [] == false
Null (List TNum [Num 1, Num 2, Num 3]) -- null [1, 2, 3] == true

-- Fold <Input List element CLAEType> <End result & accumulator CLAEType> Lambda BaseCase List
-- Sum function: foldr (\x acc -> x + acc) 0 [1,2,3,4,5] == 15
FoldX TNum TNum (LambdaX "x" TNum (LambdaX "y" TNum (PlusX (IdX "x") (IdX "y")))) (NumX 0) (ListX TNum [NumX 1, NumX 2, NumX 3, NumX 4, NumX 5])

-- Map <Input element CLAEType> <Output element CLAEType> Lambda List
-- Squares all elements: map (\x -> x*x) [1,2,3,4,5] == [1,4,9,16,25]
MapX TNum TNum (LambdaX "x" TNum (MultX (IdX "x") (IdX "x"))) (ListX TNum [NumX 1, NumX 2, NumX 3, NumX 4, NumX 5]),

-- Filter <Input element CLAEType> Lambda List
-- All elements <=3: filter (\x -> x <= 3) [1,2,3,4,5] == [1,2,3]
FilterX TNum (LambdaX "x" TNum (LeqX (IdX "x") (NumX 3))) (ListX TNum [NumX 1, NumX 2, NumX 3, NumX 4, NumX 5]),

-- Length <Input element CLAEType> List
LengthX TNum (ListX TNum [NumX 1, NumX 2, NumX 3, NumX 4, NumX 5])

-- Concat <Input element CLAEType> List List
ConcatX TNum (ListX TNum [NumX 1, NumX 2, NumX 3, NumX 4, NumX 5]) (ListX TNum [NumX 6, NumX 7, NumX 8, NumX 9, NumX 10])

-- Take <Input element CLAEType> CLAE List
TakeX TNum (NumX 2) (ListX TNum [NumX 1, NumX 2, NumX 3, NumX 4, NumX 5]) -- take 2 [1,2,3,4,5] == [1,2]

-- Drop <Input element CLAEType> CLAE List
DropX TNum (NumX 2) (ListX TNum [NumX 1, NumX 2, NumX 3, NumX 4, NumX 5]) -- drop 2 [1,2,3,4,5] == [3,4,5]

-- Index <Input element CLAEType> CLAE List
IndexX TNum (NumX 1) (ListX TNum []) -- index 1 [] == []
IndexX TNum (NumX 2) (ListX TNum [NumX 1, NumX 2, NumX 3, NumX 4, NumX 5]) -- index 2 [1,2,3,4,5] == [3]

-- Reverse <Input element CLAEType> List
ReverseX TNum (ListX TNum [NumX 1, NumX 2, NumX 3, NumX 4, NumX 5]) -- reverse [1,2,3,4,5] == [5,4,3,2,1]

-- A bit more complex:
MapX
  (TList TNum)
  (TList TNum)
  -- for the input element x, do map (\y -> y*y) x
  (LambdaX "x" TNum (MapX TNum TNum (LambdaX "y" TNum (MultX (IdX "y") (IdX "y"))) (IdX "x")))
  -- nested list mess
  (ListX TNum [ListX TNum [NumX 6, NumX 1], ListX TNum [NumX 6, NumX 2], ListX TNum [NumX 6, NumX 3], ListX TNum [NumX 6, NumX 4], ListX TNum [NumX 6, NumX 5]])
-- map (\x -> map (\y -> y*y) x) [[6,1],[6,2],[6,3],[6,4],[6,5]] == [[36,1],[36,4],[36,9],[3616],[36,25]]

-- What on earth is that...
BindX
  -- define recursive factorial function
  "fac"
  (TNum :->: TNum)
  ( FixX ( LambdaX "g" (TNum :->: TNum)
    ( LambdaX "x" TNum
      ( IfX
        (IsZeroX (IdX "x"))
          (NumX 1)
            ( MultX
              (IdX "x")
              (AppX (IdX "g") (MinusX (IdX "x") (NumX 1)))
            )
        )
      )
    )
  )
  -- apply the function to each element
  (MapX TNum TNum (LambdaX "v" TNum (AppX (IdX "fac") (IdX "v"))) (ListX TNum [NumX 1, NumX 2, NumX 3, NumX 4, NumX 5])),
-- map (\x -> fac x) [1,2,3,4,5] == [1,2,6,24,120]

Published

Category

clae