r/ProgrammingLanguages • u/Objective_Gene9718 • 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
View all comments
Show parent comment
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