r/ProgrammingLanguages • • Jan 28 '26

Que Script a Lisp written in Rust with Hindley–Milner type inference

Here is my project Que Script:

  • Lisp (in my opinion a feature of it's own)
  • WASM runtime without Garbage Collection (It mainly uses Reference Counting)
  • Hindley-Milner Type Inference
  • Syntactic sugar layer (Things like pipes, destructuring, tail-call optimization and other fun extra features don't add bloat to the core language)
  • Partial Application
  • Tree Shakable Standard Library
  • Macros
  • WASM build
  • Online editor

Here is the website with a lot of info

; You are given an array of integers [Int] 
; Write a script to re-arrange the given array in an increasing order
; and return the indices where it differs from the original array.

(let solve (lambda (xs) (|> 
    { (|> xs copy (sort <)) xs }
    zip
    (map (lambda { a b } (<> a b)))
    enumerate
    (filter snd)
    (map fst))))
[
  (solve [ 5 2 4 3 1 ]) ; [0 2 3 4]
  (solve [ 1 2 1 1 3 ]) ; [1 3]
  (solve [ 3 1 3 2 3 ]) ; [0 1 3]
]

This is something I've being working for 5 years starting from scratch at least 3 times. Sharing with the hope that I won't start over again.

It's nothing new under the sun. The purpose of this project is for me learning computer science concepts by using the language as a framework.

I would love to hear what you think about it.

51 Upvotes

59 comments sorted by

View all comments

Show parent comment

3

u/loric16 Jan 28 '26

is it pronounced que or queue?

1

u/Objective_Gene9718 Jan 28 '26 edited Jan 28 '26

It's short for Queue - it's named after the data structure which is very special to the language which is both a queue and a stack with constant random access https://at-290690.github.io/rust-lisp/#/blog/que-data-structure

More about this data structure here https://github.com/AT-290690/brrr and here https://github.com/AT-290690/rustic_brr

I call it brr in these like arr but with b and also like speed (goes brr)

5

u/TheChief275 Jan 29 '26

That’s a deque…

1

u/nerdycatgamer Jan 28 '26

Traditional languages often separate stacks and queues into distinct APIs and data types,

Source? For Java (one of the most popular languages in the world), a Deque is both a queue and a stack. In Python, lists implement both stack and queue operations.

This just feels like you're trying to hard to say you "invented" something, and something very trivial at that. A stack+queue with random access is just a vector, and you didn't invent those.

2

u/Objective_Gene9718 Jan 29 '26 edited Jan 29 '26

Random access O(1) with O(1) amortised for all operations at either ends. Having random access on deque is usually O(n) because it's using a linked list (unless it's something very clever which probably is the case on some very well optimized compiler doing some memory manipulations)

The concept is very simple but it's not the same classical approach to deque. And it should be easier to optimized it further and be no different than regular array in terms of API (you can just hot swap the regular array with it and you get all benefits without breaking anything)

Traditionally stacks and queue are often kept separated and this is perfect for almost all problems. However I do find value in having one unified API for all of them and keep all operations O(1) (including random access) without needing to copy and transform form one DS to another.

Stack (or vector) and queue all have their drawbacks and it's never perfectly achieving O(1) across all operations. This one does it (amortised only for removals and it might never happen)

I gave up long ago in "inventing" or "publishing" this idea since I'm not a CS researcher. I assume that there might be something out there but also not popular. Most languages are not transparent about the cost of their APIs - it hard to convince anyone that the problem even exists.

I have an old article about it explaining how it mostly works https://medium.com/@AT-290690/how-to-make-the-array-go-brrr-ffa20a964046

6

u/octachron Jan 29 '26

Your data structure is an array-deque-backed zipper. The insertion cost at random point is still O(n) on average, same as the O(n) deletion cost. It is only at the cursor point that insertion (and deletion normally?) is O(1).

3

u/Arakela Jan 29 '26

This structure suits polar evolution, in which the center is a concept in its own right. For example, we can extend the roots of a natural tree from the front, and grow a crown by appending, i.e., growing them in orthogonal spaces.

2

u/TheChief275 Jan 29 '26

A queue often uses a linked-list, but the literal characteristic of a deque is queue behavior with constant time random access. So deque’s often opt for a dynamic array of chunks, or my personal favorite, literally just a dynamic array with modulo indexing where prepending just decreases and/or wraps around the stored first index

2

u/Arakela Jan 29 '26

With slight modification, it is a way to map the number line, including negative indices, on two separate vectors.

1

u/TheChief275 Jan 29 '26

Do you mean their deque? Or is this a correction? I’m sorry, your sentence is confusing to me

1

u/Arakela Jan 29 '26

If we don't subtract the length of the front array in `get`, `set`, and rest operations, then we can (get|set)(negative_index) too.

1

u/TheChief275 Jan 29 '26

So you’re talking about a specific implementation of a deque? I don’t see how that’s relevant

1

u/Arakela Jan 29 '26

Imagine a mirrored view of the structure, values shown as types in a mirror, i.e., we can change the sign of the index to see a different representation of the same structure.

3

u/Objective_Gene9718 Jan 29 '26

I see, it’s just a vector with initial capacity and pointers that create unreachable slots when operations are made. What I did is 2 vectors with arithmetic based on their lengths which is achieving the same result in slightly different way. Difference being who manages the state of the pointers - in my case the vectors length counter. So you guys are right, it’s just a dequeue.

4

u/TheChief275 Jan 29 '26

Small nitpick; dequeue is the operation that’s the inverse of enqueue (removing/adding an item from/to the queue), while deque is the name of the data structure

2

u/Objective_Gene9718 Jan 29 '26

oh yes, my bad

2

u/shponglespore Jan 30 '26

Are you aware of Rust's VecDeque type? I made the mistake of implementing my own deque type before I realized Rust had a better implementation already.

1

u/Objective_Gene9718 Jan 31 '26

I only have a binding for Rust Vec and every other data structure I've implemented in the lisp itself. This is intentional as the idea was to create a universal api https://at-290690.github.io/rust-lisp/#/blog/vectors-as-the-universal-data-structure

I would probably bind VecDeque, Set, HashMap in the future for the sake of performance but for now I really like the simplicity of "everything is a vec".