pl

Entries tagged: pl

June 19, 2021. Hierarchial spreadsheets and you tags: pl, hci
The idea of viewing your possessions like a video game inventory is really amusing:
- 1x laptop
- 1x charging cable
- 1x face mask
- 50x alcohol wipes
- 1x large cup of jasmine green pearl milk tea of power <+7>
Long story short, I had a “wait but actually though” moment in a flash of shower thought brilliance.

It’s not like I lacked motivation for it either. As a minimalist, I’ve always wanted to do this thing where (1) you take inventory of all your things, (2) you cross out the things you don’t need, (3) you get rid of those things. The idea is to intentionally get rid of things, like that hairbrush you never ever ever ever ever use, but keep anyways “just in case”.

Now here was the hard part:

Q: Am I really going to be writing hundreds of items in a bulleted list?
A: sure why not
Q: Some things are in boxes, should I write down the things inside boxes?
A: yes, just indent the things inside boxes
Q: What about boxes in boxes? On a shelf, in a closet?
A: yea, wait fuck

There was no way I was writing a deeply nested bulleted list of hundreds of items – I’ve worked with enough big JSON/YAML behemoths to know that you lose sight of the nesting about 2 levels in. A spreadsheet is only slightly better, but again if you do nesting you either have to have huge cells or multiple spreadsheets. That’s where the second flash of shower thought brilliance kicked in – what if I do this in TreeSheets?

TreeSheets

http://strlen.com/treesheets/

Some spreadsheet software will let you have all kinds of things in a cell – formulae, images, sparklines, stock quotes. TreeSheets (written by the wonderful Wouter van Oortmerssen) lets you have spreadsheets in cells. I don’t know how old or new this concept is but it’s really cool, except for the outdated looking GUI, which is built on wxWidgets.

For me, it just means my nested lists don’t suck, and I can use a second column in each list to add “delete” tags to my things.
```
(an image should go here but I'm too lazy rn)
```
After all was said and done, I had a huge spreadsheet of all my things. TreeSheets has a feature where you can copy your whole spreadsheet and immediately paste it somewhere and it comes out as a nested list. The output was about 500 lines long – turns out I have like 500 things. Which mentally feels like a big number, but according to my friend, “it’s one of those things that seem like a lot only if you count it, like calories.”

I had been using TreeSheets to serve as an organizational tool. By the end of the week-long journey of cataloguing all my things, we witness our third flash of brilliance: spreadsheets have formulas.

The plan was obvious. Set up a programmatic dashboard in TreeSheets using lookup formulas to locate items at will, or at least list all the items I tagged with “delete”. Kind of like a shitty query language! But TreeSheets doesn’t really support that – formulas are super limited, there’s not a lot of functions, and formula cells are more like Jupyter cells in that you can individually run them or hit Run All.

(Also, I could just use ctrl-F in TreeSheets to locate things. I need to stop overengineering.)

Anyways, formulas seem kind of hard in hierarchial spreadsheets. As for who’s solving this particular pickle, the only other hierarchial spreadsheet software I know is:

Inflex

https://inflex.io/

Inflex (currently in beta as of Jun 2021) has the same idea – cells can contain spreadsheets. My impression of Inflex’s ambition is something like “take the most popular declarative language in the world – spreadsheets – and make it really really damn functional”.

To this end, they’ve built support for lists and records as special spreadsheets. I guess the idea is that you can map() and filter() them and it’ll come out the other side as another list or record cell and that’s kind of pretty. There’s also functional debugging support (static typechecking, holes _) which is also kind of pretty.

Pretty but not super polished yet UX-wise – sure, you can paste {a:2,b:[1,2,3]} as text and it’ll be represented as a spreadsheet. But right now, you can’t use cell references (e.g. map(x:x+5, the cell to the left)), so you have to copy the original data into the formula to use it. I honestly would use this if the UX were at the level of TreeSheets, so yeah let’s check back in a year or something.

Future thoughts

Honestly I don’t think any hierarchial spreadsheets support good formulaic lookups which kind of sucks. I mean, I definitely don’t want to work with nested indices like F1A1A1:F1A1A50. Honestly indexing in spreadsheets should be behind-the-scenes details, stuff the user shouldn’t have to deal with at all. I just want to select a range and run lookup or whatever!

I’d love to think about hierarchial spreadsheets of the future, but I’m tired now so I’ll end this post here bye
tagged: pl, hci Hierarchial spreadsheets and you (permalink) (tweet)

June 25, 2020. Thoughts on readable data processing tags: pl
TLDR: dynamic views as a composable zero-cost abstraction. Or: like SQL but easy to read. (gosh, I should get into writing paper titles)

the big idea

Late last night I thought of an idea for a data processing language. Consider the following problem:
```
"just a second" -> "JUST a second"
"bone apple tea" -> "BONE apple tea"
"capitalize the first word" -> "CAPITALIZE the first word"
```
In most languages (like Python or regex), this would require one or more of the following:
- find where to stop capitalizing at (via a loop or via string matching)
- working with indices up to that index
- use a loop to capitalize each letter
and the resulting performance is dependent on how you wrote that.

What if instead of doing any of that, we can naively operate on a specific view of the string, namely the first word:
```
# run toUpper() on each char of the first word
toUpper(input.words.first.chars);
```
and have it behave exactly as if we wrote a tight loop in C? like
```
for (int i = 0; i < input.length; i++) {
  if (!isSpace(input[i])) {
    input[i] = toUpper(input[i]);
  } else break;
}
```
I doubt this is a new idea, since my thoughts here are very inspired by the idea of dynamic views and by the J language’s composability. It’s like SQL, except queries are performant AND readable.

fleshing out the concept

To simplify things, let’s work with flat, nonempty integer arrays. So the interesting problems include things like taking k-maximum, or finding the cumulative sum.
```
1 6 2 3 4.maximum(2) == 4 6
1 6 2 3 4.cumulativeSum == 1 7 9 12 16
```
How would we express these using the idea of ‘operating on an specified view’? I would imagine something like
```
input.maximum(k) := input.sorted.last(k)
input.cumulativeSum := input.prefixes.sum
```
Takeaways:
- maximum: applying something like .sorted.last(k) should not actually perform a sort, but instead find k-maximum (like via min heap when k > 3).
- cumulativeSum: clearly I’m cheating a bit, since I said we’re working with flat arrays, but taking prefixes of a flat array sounds like a jagged 2D array. I’m thinking that prefixes is actually some special intermediate object that expects a folding operation (sum) to be performed on the prefixes, and then uses that folding operation to produce the cumulative sum. It’s directly inspired by J’s \ operator. This reminds me of Clojure’s transducers…
zero-cost property

How do we best-effort ensure that this dynamic view abstraction is zero-cost? Meaning that everything we write using dynamic views should be equivalent (performance-wise) to writing a tight loop. Make indirection invisible after compilation.

For starters, every dynamic view should be managed at compile-time. Under the hood, the compiler should translate input.first.add(2) to input[0] += 2 in C. How?

I’m thinking that each hardcoded view, like .first, should (at compile-time) change the modified data to be the first element. This sounds obvious, but becomes non-trivial when we get things like .sorted where the modified data is now the sorted version of the array. .sorted requires some indirection under the hood. Taking another page from J, we could use keep around permutation vector as indices, so 10 30 40 20 would have the permutation vector 0 3 1 2, meaning “smallest element is at index 0, second smallest is at index 3, …” The compiler handles the rest.

This ad-hoc method needs to be implemented for every dynamic view, and maybe there should be optimizations for common compositions like .sorted.last.

composition property

This approach to dynamic views is cool, but it has one flaw: composition is non-trivial. There are actually two parts to this:
- Language-level composition: how do we make it easy to work with a view of a view of a view?
- Compiler-level composition: how to make that work perfectly under the hood?
Language-level composition

My favorite example here would be taking the integer mean of an integer array. This requires summing an array, finding its length, and integer dividing these two numbers.

How would you express that? In J, it would look like (+/ % #) input meaning (sum divide length) input. So J has composition down – it has a neat way to compose operators (the fork combinator).

How do we get dynamic views to be just as powerful? For reference, a tight loop in another language would look like:
```
int total = 0;
for (int i = 0; i < input.length; i++) {
  total += input[i];
}
mean = total / input.length;
```
Would it just be input.mean := input.sum.divide(input.length)? It sounds messy. This needs some thinking.

compiler-level composition

I mentioned earlier that common compositions of primitives, like .sorted.last, should be identified and replaced with a more performant version. Idempotent functions like .sorted.sorted should translate to .sorted. Involutions like .reverse.reverse should translate to no-op. These are hardcoded solutions corresponding to Special Combinations in J.

But how do we make things like this work in general? Take toUpper(input.words.first.chars) from the first example, using strings. How the hell do we go from that to…?
```
for (int i = 0; i < input.length; i++) {
  if (!isSpace(input[i])) {
    input[i] = toUpper(input[i]);
  } else break;
}
```
My current thought for this is to make every view apply a layer of indirection, which will get resolved at compile time. So .sorted generates an array of permutation indices, which the compiler can traverse later to get the actual sorted list representation. (This approach is very amenable to extension, since all that’s needed to support new view operations is to define the indices.)

In our toUpper example, .words could be a list of indices that point to the start of each word. .first gets the first index of this list. .chars gets the list of indices for each letter. The compiler will have all this information available. The challenge is, how do we skip computing the unused information, like indices for things that are not the first word? I need to do more research.

(side note: In J we would turn notIsSpace "abc 123" into a predicate array 1 1 1 0 1 1 1, which can be used by other operations to split into words, for example. In our example, I’d imagine we’d throw out everything after seeing the first 0. How do we avoid computing the remaining 1s? Where does the early break come in? This needs research.)

practical data representations

I really want this dynamic view idea for more than just integer arrays. I’m thinking strings obviously, but also associative arrays, custom ADTs, json, bit fields, dataframes, file handles.

Well, one can’t possibly write them all, but what if there was an API that allowed writing this stuff at a low level? Like having a low level way to specify views as lists of indices. The easiest solution would be specifying operations that the compiler can use in the compile step, though this makes compilation dangerous (might allow arbitrary execution?).

closing thoughts

This was just a thought experiment for a small data-processing language that compiles down to a fast language like C. If it turns out to be a solvable problem, then I wouldn’t feel comfortable about the implications. For one, if these operations are easy to specify while being zero cost, then there’s no point in learning algorithms for e.g. finding k-maximum, since you would just use an equivalent formulation like .sorted.last(k) at zero cost!

If we know all the fast algorithms, and this syntax saves you from handwriting speed-saving constructions (like constructing min heaps by hand) and doesn’t require importing a library, then why ever learn algorithms outside of academia?

If most data-processing is expressible via manipulation of dynamic views, then why ever learn other forms of declarative programming with high level concepts like filters and folds?

Thoughts like this keep a practical computer science educator up at night.

addendum: approximate algorithms

One thing this abstraction does not allow is approximate algorithms, which may be much much faster than the best algorithm both time- and space-wise, at the cost of not guaranteeing correctness.

Maybe approximate algorithms could be a library? Adding things like approxSort? Maybe we do need libraries after all.

addendum: time-efficiency vs space-efficiency

All this time I kind of ignored space as a problem. In the interest of optimizing for time, I silently assumed constructing auxiliary data structures would not be a big issue. Which is not true. Allocations are not free, and ignoring allocation might make the time-efficient algorithms slower.

This will definitely have to be a user setting. Maybe optionally annotate files or LOC or individual functions to run with certain efficiency constraints, so the compiler picks the more space-efficient translation over the time-efficient translation. Maybe have different levels of efficiency annotations. Will need to think about this too.
tagged: pl Thoughts on readable data processing (permalink) (tweet)

April 30, 2020. J is my calculator tags: pl
I used to use node (javascript) as my CLI calculator. (I know, I know.) After realizing how silly I was for using such an inexpressive language, I tried to learn calc and bc. The next few I went through were:
- python
- ghci (Haskell)
- R
- octave (matlab equivalent)
- and finally, J
I don’t have a good reason to settle with J. Maybe I’ll change it soon. But here’s my review of J, collected slowly over a few months of usage:

Pros:
- Hassle-free rationals: write 1%2r127+3r160 instead of 1/((2/127)+(3/160)), and get 20320r701 ( $\frac{20320}{701}$ ) as a result.
- No need to repeat an operator. Write */12 52 65 13 42 rather than 12*52*65*13*42
- Built-in polynomial evaluation at multiple points. Write _4 2 1 1 p. 1 2 3 to evaluate x³+x²+2x-4 at x={1,2,3}.
- The idiom for convolution (polynomial multiplication) is +//. @: (*/) (take outer product */ and sum +/ the antidiagonals /.)
- Any user defined function is an operator just like +
- Hooks and forks make some expressions incredibly easy to write. Examples:
  
  (+/%#) 2.252 2.284 evaluates to the mean of the list: 2.268
  
  2.268 (-,+) 0.016 evaluates to the interval 2.252 2.284
  
  (f,g,h) x evaluates multiple functions on the same data x (say, mean median range)
  
  recent example for me: (13.342-7.666)%%:+/18.140 14.378(*:@[*%)578 379 evaluates $\frac{13.342-7.666}{\sqrt{\frac{18.140^2}{578}+\frac{14.378^2}{379}}}$
Cons:
- You can only share with other J users (not like you’re going to share one-off calculations though)
- Need to get used to how every operator associates right without exception
- Have to understand how J evaluates things in order to refactor expressions
- Configuration is not obvious: e.g. (9!:11)4 sets displayed floating point precision to 4.
- Jagged or non-homogenous arrays requires you to learn the messy art of value boxing/unboxing
- Working in hex (or any base) is a hassle if you want hex output. You can input hex with 16bdeadbeef for example, but all output is in decimal (unless you pass it through the hex-printing (4+#@$) }. 2&(3!:3) or use the printf addon).
- It’s hard to find the right operator for the job if you don’t know it by heart. It’s just like in mathematics. Languages like J suffer from lack of discoverability.
tagged: pl J is my calculator (permalink) (tweet)

modified May 21, 2020. FP takes on OOP design patterns tags: pl

Visitor Pattern

Objective: Separate an algorithm from the structure on which it works

In Haskell terms, this means defining an ADT implementing Functor. For example: data T a = A | B | C (T a) (T a) deriving Functor.

To call a function f on the data mydata, a client writes:

fmap f mydata

(We’ll assume f is some unsafe function, since the equivalent visit method in Java returns void.)

In Java, the idea is to define an abstract class Data, and have some concrete classes that extend Data, e.g. A, B, C. (This is just Java’s way of making an ADT.)

Then define an interface called DataVisitor defining a visit method overloaded for argument types A, B, and C. (This interface is equivalent to defining and implementing a Functor typeclass specifically for Data.)

Then give each of A, B, C an accept method taking in a DataVisitor, which does nothing but call the DataVisitor’s visit method on itself. (Why define an identical accept method for each of A, B, C? This is Java’s workaround for pattern matching on Data – having each of its subsclasses A, B, C overload some method.)

To call a function f on some mydata, a client needs to do two things. First: define a class FDataVisitor implementing the DataVisitor interface, i.e. defining visit for A, B, C to do whatever f does. (Like for accept, this is akin to pattern matching on the argument of f, and so you need to define a whole class to give f that power). Then, the client creates a FDataVisitor object (call it visitor) and writes:

mydata.accept(visitor)

In summary, the equivalent bits in the Visitor pattern are:

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
abstract `Data` class	${\leftrightarrow}$	ADT type
`A`, `B`, `C`	${\leftrightarrow}$	ADT constructors
`DataVisitor` interface	${\leftrightarrow}$	specialized `Functor` typeclass
`visit`	${\leftrightarrow}$	generic `f` argument to `fmap`
`accept`	${\leftrightarrow}$	`fmap`
`data.accept(f)`	${\leftrightarrow}$	`fmap f data`
`FDataVisitor` class and object	${\leftrightarrow}$	a pattern matching branch in `f`

Interpreter Pattern

Objective: To evaluate an expression in the form of a syntactic tree

In Haskell, this translates to a function (call it eval) which performs pattern matching on an ADT. If a local context is needed, it can be encoded by adding an extra context argument to the function (which is equivalent to using the Reader monad). A global context can be encoded with the State monad.

In Java, this requires defining an Expression interface with an interpret method taking in a global context (local context is not possible). Each terminal and nonterminal in the expression grammar is a class implementing Expression (Java’s way of defining ADTs).

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
`Expression` interface	${\leftrightarrow}$	ADT type
terminal and nonterminal classes	${\leftrightarrow}$	ADT constructors
`interpret`	${\leftrightarrow}$	a pattern matching branch in `eval`
context	${\leftrightarrow}$	extra argument to `eval`

Command Pattern

Objective: To encapsulate the details of an action to execute it later

In Haskell, each action and its parameters can be encoded as one constructor of an ADT. We can execute it later by writing some eval function that pattern matches and does the corresponding command acting on some global state. Since state is often safely encapsulated by stateful monads like State or IO, you might write your eval in a stateful monad.

Alteratively, you can write each action as its own function, and literally store partially-applied functions for later use. This is easier to write and extend, but harder to debug because you can’t print out functions, and because there is no exhaustiveness checking for invalid commands.

In Java, this is the same as Interpreter pattern, except everything is a nonterminal storing some parameters. These nonterminals can be stored, reordered, etc, any way you want (until they are consumed like in the Interpreter Pattern).

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
`Command` interface	${\leftrightarrow}$	ADT type
`FooCommand` classes	${\leftrightarrow}$	ADT constructors
`execute`	${\leftrightarrow}$	a pattern matching branch in `eval`
global state, which commands affect	${\leftrightarrow}$	stateful monads

Strategy Pattern

To define a family of algorithms which are interchangeable within the family.

In Haskell this means defining various functions (the algorithms) which are all parameterized by the same variables and functions. This can be accomplished by passing along these parameters as an argument, providing them each time you call each function. But the whole point of the Strategy pattern is to avoid having to do that. Avoiding passing arguments all the time is also the whole point of the State monad.

So, the State monad can be used for the Strategy pattern – every function using this strategy will live in State s where s is some ADT holding the aforementioned parameters. To change the strategy, use put to change the strategy’s variables and functions. Functions using the strategy will use get to get the strategy’s variables and functions.

In Java, this requires our client Context object to store some strategy member variable implementing the Strategy interface, which has data and functions used elsewhere in the methods of Context. Changing the strategy is as easy as setting the strategy member variable.

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
`Strategy` interface	${\leftrightarrow}$	`s` (ADT for your state)
`Strategy` object	${\leftrightarrow}$	value of type `s`
family of algorithms	${\leftrightarrow}$	the functions living in your `State s` monad
changing the `Strategy`	${\leftrightarrow}$	`put`
accessing the `Strategy`	${\leftrightarrow}$	`get`
methods in `Context`	${\leftrightarrow}$	your API

Adapter Pattern

Objective: To bridge between two incompatible interfaces.

In Haskell, interfaces are typeclasses, so the goal is to let instances of typeclass Foo be used as if they are instances of typeclass Bar. We do this by literally implementing Bar for all instances of typeclass Foo using type variables, like

instance Foo a => Bar a where
  ...

which you might read “Foo anything implies Bar anything”. Then instances of typeclass Foo can directly be used as if they are instances of typeclass Bar.

In Java, this requires writing a FooAdapter class which wraps a Foo but implements the Bar interface. Then Foo objects can be used as a Bar objects by wrapping them in FooAdapter, which is-a Bar.

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
interface	${\leftrightarrow}$	typeclass
`FooAdapter`	${\leftrightarrow}$	(unnecessary)
wrapper variable in `FooAdapter`	${\leftrightarrow}$	type variable

Iterator Pattern

Objective: To traverse elements of a collection without exposing its underlying representation.

In Haskell, we always write collection-traversing operations as some kind of fold, without exception. So the closest equivalent is the Foldable typeclass and its sequential foldr function.

In Java, we write this ‘next’ element function by defining a Iterator interface with a next and hasNext method for traversal. Each collection can define some kind of createIterator method which returns the corresponding CollectionIterator class that implements Iterator.

To use this, the client gets an iterator with createIterator. Then it enters a loop calling hasNext to check if the loop continues, and next to get the next element in sequence.

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
`Iterator` interface	${\leftrightarrow}$	(unnecessary)
`createIterator`	${\leftrightarrow}$	(unnecessary)
code using `Iterator`	${\leftrightarrow}$	some kind of fold
collection with iterators	${\leftrightarrow}$	instance of `Foldable`
`hasNext`	${\leftrightarrow}$	whether the pattern match in `foldr` is base case
`next`	${\leftrightarrow}$	use variable from pattern match in `foldr`

Observer Pattern

Objective: Define a one-to-many relationship between objects such as if one object is modified, it automatically notifies all the depenedent objects.

In Haskell, this is the heart of functional reactive programming (FRP). The gist of it is that updates are Events (a value associated with a time), and states are Behaviors (values that change depending on time, like a signal in signal theory). Everything is done by modifying and combining Behaviors – for example, if it’s true that the engine dies whenever the tank runs out, you’d modify the ‘fuel-in-tank’ Behavior into an engine-is-alive Behavior by applying a function (> 0), exactly like how it is in signal theory.

Whenever updates (Events) happen from the outside, you can turn them into Behaviors and use them to change other Behaviors. And you can always sample a Behavior at interesting times to get Events to act on.

There isn’t a need to keep track of which objects are subscribed or having to call update on each subscribed object, since any potentially interested objects are able to access the state as it exists at every point in time, and are able to define new states from that state based on incoming updates.

In Java, the Observer pattern requires a supervising Subject class which stores a state (with getter and setter) and a collection of Observer objects. It provides an attach method which adds an Observer to the collection. The setter for the state must call the update method of each Observer with the new state.

Observer is an abstract class with a single update method. Classes extending Observer will define update to do whatever interesting thing needs to be done on a state change. Whenever an Observer object is created, it requires a reference to Subject, so the Observer constructor can call subject.attach(this) in order to add the new Observer to the watch list.

TODO: more patterns

References

tagged: pl FP takes on OOP design patterns (permalink) (tweet)

pl

TreeSheets

Inflex

Future thoughts

the big idea

fleshing out the concept

zero-cost property

composition property

Language-level composition

compiler-level composition

practical data representations

closing thoughts

addendum: approximate algorithms

addendum: time-efficiency vs space-efficiency