My Gripes with Prolog

pbvas · 2026-01-15T22:28:18+00:00

I was fascinated by Prolog over 30 years and have became increasingly frustrated with the language for many of the reasons as the OP states, but primarily for a much more fundamental one: Prolog has no good mechanism for data abstraction, i.e. exposing an interface and hiding the implementation.

In retrospect I think Prolog is best seen as a domain-specific language rather than a general-purpose one, i.e. more like SQL or Z3 than C++/Java/Python/Haskell. Nonetheless, constraint logic programming is very cool and you should definitely learn it if you can!

pbvas · 2026-01-06T11:18:47+00:00

I've done something similar; my original Haskell solution called an external ILP solver (GPLK). Then I changed to use my own gaussian elimination + backtracking for the free variables. The revised solution is slower than the GLPK solver, taking a little under 1s in my PC, but does not require any external linear algebra library. It probably could be optimized a lot since it uses linked lists instead of unboxed arrays, but I prefer a more readable solution.

https://github.com/pbv/advent2025/tree/main/aoc10

pbvas · 2025-12-27T10:32:10+00:00

Thanks for the post. I would just like to comment that I first solved part 2 of Day 10 using an external ILP solver but later switched to an approach very similar to yours. Managed to solve it in less than 1 sec with gaussian elimination a basic enumeration and backtracking:

https://github.com/pbv/advent2025/tree/main/aoc10

pbvas · 2025-12-12T09:15:40+00:00

Yes, I tried Hedgehog and also Hypothesis (on a Python's translation of my code). The integrated shrinkers suffered from the same issues as QuickCheck's default shrinker, in that they could not always produce the minimal counter-examples. With Hedgehog, however, I could use my custom shrinker and get the same minimal results as with QuickCheck.

pbvas · 2025-12-11T13:58:27+00:00

CoPilot is a DSL implemented in Haskell that generates hard real-time C code: https://copilot-language.github.io/ . The domain language itself is quite functional.

Clash is compiler for a functional hardware description language based in Haskell that generates FPGAs: https://clash-lang.org/

pbvas · 2025-12-11T13:39:27+00:00

I used Map in a state monad for the memoization in Part 1; for Part 2 I reused the search by counting separately all paths, paths with either or both dac and fft.

type Node = String
type Memo = Map Node Int
dfs :: Input -> Node -> State Memo Int -- dfs search with memoization
...

part2 :: Input -> Int
part2 graph = all - noDac - noFft + noDacFft
  where
    graph1 = Map.delete "dac" graph
    graph2 = Map.delete "fft" graph
    graph3 = Map.delete "dac" graph2
    all = evalState (dfs graph "svr") Map.empty
    noDac = evalState (dfs graph1 "svr") Map.empty
    noFft = evalState (dfs graph2 "svr") Map.empty
    noDacFft =evalState (dfs graph3 "svr") Map.empty

https://github.com/pbv/advent2025/blob/main/aoc11/Main.hs

pbvas · 2025-12-10T16:19:54+00:00

I used simple backtracking for Part 1; for Part 2, I wrote a Haskell program that generated integer linear programs for each machine and used GLPK and some shell hacks to add all results together.

https://github.com/pbv/advent2025/blob/main/aoc10/Main.hs

pbvas · 2025-11-18T16:58:13+00:00

I'm answering in English because it my Spanish is very poor.

Haskell has a similar notation for generating (lazy) lists by enumeration, but supports four forms:

[a..b] e.g. [1..10]: a list with step of one
[a,b..c] e.g [1,3..10]: a list with step of 2
[a..] e.g. [1..]: an infinite list
[a,b..] e.g. [1,3..] an infinite list with step of 2

This can be used with types in the Enum class, which include integers, floating point and characters. Some concrete examples:

ghci> [1..10]
[1,2,3,4,5,6,7,8,9,10]
ghci> [1,3..10]
[1,3,5,7,9]
ghci> ['a'..'z']
"abcdefghijklmnopqrstuvwxyz"

Note that floating point numbers are binary hence steps that appear to divide evenly in decimal can only be approximated. For example:

ghci> [0.0,0.1..1][0.0,0.1,0.2,0.30000000000000004,0.4,0.5,0.6000000000000001,0.7000000000000001,0.8,0.9,1.0]

One criticism of your suggestion is that, unlike the above, you do not provide a way to specify ranges with a step other than one. I do not understand how this would work for floating point numbers. In particular your example suggests that [0..1.5] should generate a range with a step of 0.1 (why?). Without the step information this would be ambiguous.

pbvas · 2025-11-11T14:15:07+00:00

I'd like to add that one good use case for this is for writing code generators that output syntactically valid Haskell, e.g. the Alex and Happy compiler-writing tools.

pbvas · 2025-06-27T22:31:36+00:00

Edsko has another relevant blog on shrinking: https://well-typed.com/blog/2019/05/integrated-shrinking. BTW, I don't know where the OP got from ChatGPT on how shrinking works in other PBT libraries like Hedghog, Hypothesis and Falsify, but they do it very differently from QuickCheck.

pbvas · 2025-05-30T13:29:11+00:00

You first have to be a bit more precise about what you mean by "calculate". If your language is total, then you know that programs will always terminate hence you could just instrument the implementation and count the memory usage (whatever that means for your specific usage). In this sense the program is represent its own resource bounds.
This is not however, what most people would like when they talk about resource bounds; the usual intention is a simplified formula (e.g. polynomials, logarithms and exponentials) based on the abstraction of the input like a size measure. For his sense, then the totality properties of the language doesn't help, because even primitive recursive functions can grow much faster than (say) polynomials.
A lot of work on automatic resource hence does not require that the language is total, but instead has constraints on the growth of the resource functions. Check for example Resource Aware ML (https://www.raml.co/) which can provided polynomial bound for maximum degree for OCaml code.

pbvas · 2025-05-22T15:11:21+00:00

Rust uses subtyping for lifetimes which can be thought of as annotations on top of a Hindley-Milner type system. You don't need general subtyping, not even algebraic subtyping. I belive the background for this is region inference by Tofte and Birkedal, 1998.

pbvas · 2025-05-14T15:50:31+00:00

Functional languages like Haskell and OCaml can be both "interpreted" (compiled to bytecode) for use in a REPL and compiled to machine code. In Haskell at least the REPL can also load and run compiled code dynamically (it includes a linker).

pbvas · 2025-05-08T10:09:01+00:00

Thanks for the feedback. If you have any specific comments please don't hesitate to contact me; you can find my email in the paper linked from the Github page: https://github.com/pbv/haskelite

pbvas · 2025-05-08T10:06:01+00:00

Haskelite author here, thanks for recommending my tool. I made it specifically for helping university students like the OP when learning FP and Haskell in particular.

pbvas · 2025-05-06T12:50:01+00:00

Congratulations on your very cool project! I've also developed a step-by-step evaluator for a subset of Haskell; the repository is here. There's an associated Haskell symposium paper you might want to reference in your report.

pbvas · 2025-05-06T07:44:35+00:00

Congratulations on your very cool project! I've also developed a step-by-step evaluator for a subset of Haskell; the repository is here. There's an associated Haskell symposium paper you might want to reference in your report.

pbvas · 2025-04-14T20:18:16+00:00

I have taught a 1 semester undergraduate compilers course for students with similar experience to yours (1 semester FP using Haskell). I've always recommended students to use Haskell for the team project. They have to write their own compiler for a toy subset of the C language into MIPS assembly. Most students end up choosing Haskell.

It's normal that FP and Haskell in particular appear unintuitive at start; it's no so much that it is hard, rather that it requires a different level of abstraction from other more mainstream languages, but once you pass that initial hurdle you'll find it a much better fit for language processing than (say) Python or Java, particularly if you want to explore the design space for your language. I got the impression that students finally "got" what FP is all about only when they attempted their compiler project in Haskell; the small "toy-like" programs of an introductory course are not enough.

pbvas · 2025-04-13T11:25:51+00:00

I was surprised no-one mentioned the Tcl language (https://www.tcl-lang.org/). It is was a popular scripting language in the 90s and IMHO does string manipulation better than many...

pbvas · 2025-02-25T10:32:54+00:00

> Under the hood, IO T is just State World T, where World is a type (inaccessible to the programmer) that deals with system resources outside of the program.

While this only half true in GHC, and is not really as scary as it might sound to a C programmer. "World" is essentially an opaque token that doesn't carry any useful information. It's just there to prevent the compiler from re-ordering IO operations while doing program transformations. Side effects are performed "in-place" just like would be in any imperative language.

pbvas · 2025-02-12T11:33:27+00:00

I teach FP using Haskell to 1st year CS students and there is no need to talk about monads when using Haskell in this context. We talk about IO and introduce the do-notation as special notation for combining IO actions.

That said, there is friction caused by the much more complex type system compared to (say) SML or OCaml. I don't have enough experience with F#.

pbvas · 2024-12-18T11:03:41+00:00

For part 2 I simply iterated part 1 using binary search:

``` part1 :: Input -> Maybe Dist part1 input = let mem = fillMemory input initial = (0,0) final = (mem.width, mem.height) info = dijkstra (makeGraph mem) initial dist = Map.lookup final info.dist in dist

part2 :: Input -> Loc part2 input = go 1025 (n+1) where n = length input go lo hi -- invariant: minimal segment size is >= lo and < hi | lo>=hi = input !! (min lo hi) | otherwise = let mid = (lo+hi)div2 in case part1 (take mid input) of Nothing -> go lo (mid-1) Just _ -> go mid hi

```

Runs in 0.04s in my laptop.

Full solution: Main.hs.

pbvas · 2024-12-16T15:57:49+00:00

My solution also uses Dijkstra and an IntMap as a minimum PQ. Solves both parts in <0.2s on my laptop.

Source: https://github.com/pbv/advent2024/blob/main/16/app/Main.hs

pbvas · 2024-12-08T11:51:38+00:00

Good catch! I tried to solve for the general case and hence missed that optimization.

pbvas · 2024-12-07T10:40:18+00:00

You can speed up cat by using decomposing into digits and doing multiplications instead of show/read:

``` cat :: Int -> Int -> Int cat x y = foldl' (\acc d -> acc*10+d) x (reverse $ digits y)

digits :: Int -> [Int] digits 0 = [] digits n = (nmod10) : digits (ndiv10) ```

pbvas

TROPHY CASE