Skip to content

Latest commit

 

History

History
105 lines (80 loc) · 5.73 KB

README.md

File metadata and controls

105 lines (80 loc) · 5.73 KB
Raw

🐡 Pufferfish 🐡

Pufferfish is an alternative syntax for Jello / 🪼 Jellyfish 🪼

Jello/Jellyfish is based on the idea that we an build up arbitrary functions by composing builtins (i.e. sort, head) with two variadic functions.

is_unary_invocable auto F₁(is_invocable auto ...fns)
is_binary_invocable auto F₂(is_invocable auto ...fns)

For example, consider the following leetcode solution:

F₁(F₁(F₁(F₁(tail sort) take 2) pair head) F₁(flat sum))

We can make calls to F₁ and F₂ implicit by using parentheses () and curly braces {} to disambiguate whether we are calling F₁ or F₂ respectively

((((tail sort) take 2) pair head) (flat sum))

Closing parentheses, ) and }, at the end of the scope are unnecessary to disambiguate the syntax. We can replace the corresponding opening parenthesis with \ and | respectively and omit the closing parenthesis.

\ (((tail sort) take 2) pair head) \ flat sum

Opening parentheses, ( and {, at the start of the scope are again unnecessary to disambiguate the syntax. We can replace the corresponding closing parenthesis with . and : respectively and omit the opening parenthesis.

\ tail sort . take 2 . pair head . \ flat sum

In fact our F₁ and F₂ only take at most three arguments. Only when we all applying F₁ and F₂ to less than three arguments is it necessary to make . and : explicit. We can omit . and : when we have exactly three arguments:

\ tail sort . take 2 pair head \ flat sum

To help you read the code, pufferfish will print the combinator tree:

tail sort take 2 pair head flat sum
  ╰─┬──╯    │  │   │    │    ╰─┬─╯
    B       │  │   │    │      B
    ╰───┬───┴──╯   │    │      │
       Φₖ          │    │      │
        ╰────┬─────┴────╯      │
             Φ                 │
             ╰───┬─────────────╯
                 B

Definition of F₁ and F₂

F₁ and F₂ are solely determined by the arity of their arguments. They can be described by the following tables for F₁ and F₂ respectively.

Arities Combinator Definition
(1, 2, 1) Φ fn Φ(f,g,h) = x -> g(f(x),h(x))
(1, 2) Σ fn Σ(f,g) = x -> g(x,f(x))
(1, 1) B fn b(f,g) = x -> g(f(x))
(2, 1) S fn s(f,g) = x -> f(g(x),x)
(2,) W fn w(f) = x -> f(x,x)
Arities Combinator Definition
(2, 2, 2) Φ₁ fn Φ₁(f,g,h) = x,y -> g(f(x,y),h(x,y))
(2, 2) ε fn ε(f,g) = x,y -> g(f(x,y), y)
(1, 2, 1) D₂ fn d₂(f,g,h) = x,y -> f(g(x),h(y))
(2, 1) B₁ fn b₁(f,g) = x,y -> g(f(x,y))
(1, 2, 2) Φ.₂ fn Φ.₂(f,g,h) = x,y -> g(f(x),h(x,y))
(1, 2) Δ fn Δ(f,g) = x,y -> f(g(x),y)
(1, 1) B.₃ fn (f,g) = x,y -> g(f(x))

Other higher order functions

Jelly also has explicit higher order functions. Pufferfish requires you to specify the arity of the result by whether you use braces {} or parenthese () at the call site i.e. hof_name(func1 func2) for a monadic result.

Justification

An alternative syntax is needed for two reasons:

  • Arbitrary Nesting: Jelly only allows one level of nesting using separators.
  • Regularity: The combinator boundaries in Pufferfish form a regular grammar. In Jelly the combinator boundaries form a context free grammar. To determine the boundaries of a Jelly chain, you must run a pushdown automata (1 stack) inside your head. To determine the boundaries of a Pufferfish chain, you merely have to run a finite automata (0 stacks) inside your head. This considerably reduces the cognitive burden needed to understand the code, and is the reason why I wont bother to learn APL or J (Uiua like Pufferfish is much easier to read).

Examples

The solutions are @codereport's https://github.com/codereport/jello/blob/main/challenges.md.

Problem Solution
3005. Count Elements With Maximum Frequency \ key{len} . \ idx_max at_idx . sum
3010. Divide an Array Into Subarrays With Minimum Cost I \ tail sort . take 2 pair head \ flat sum
3028. Ant on the Boundary \ sums = 0 sum
3038. Maximum Number of Operations With the Same Score I \ len idiv 2 c{take} chunk_fold(+ 2) \ = head . sum
PWC 250 - Task 1: Smallest Index \ len iota0 . mod 10 = . | keep head
1365. How Many Numbers Are Smaller Than the Current Number \ w(outer{<}) each(sum)
1295. Find Numbers with Even Number of Digits \ i_to_d \ len_each \ odd? \ not sum
2859. Sum of Values at Indices With K Set Bits | (len iota0 . bits) = r * l sum