The memory chips can be abused as big lookup tables, condensing potentially hundreds of discrete logic gates into one chip.
The tradeoffs are very different: with a giant look up table, you can encode any operation with the device. The problem is the rather huge amount of memory you need (with two 8-bit inputs and one 8-bits outputs you need 64KiB of internal memory to account for all possible inputs). With a PAL/GAL like the ATF22V10, you are fairly limited (your operation must be expressible in normal form, and it will have a limited number of terms), but the number of fuses (or memory cells) required to encode this are much, much lower.
Personally, I feel like using actual memory to encode behaviour is a bit "cheating" (that's just my own aesthetics). I would totally do this for actual micro-code, but for an ALU this seems wasteful.
[1]: https://ww1.microchip.com/downloads/en/DeviceDoc/doc0735.pdf
Modern FPGAs (and IIRC even many CPLDs, as the line got somewhat blurred) are usually implemented as array of LUTs implemented as normal memory with fixed address decode and not with this PLA/PAL/GAL trick. Hence, "programmable logic is just bunch of ROMs".
Of interesting historical note is Connection Machine, which while marketed as "computer", is essentially an FPGA stood on it's head. Each of the thousands of CPUs is in essence FPGA LUT block, whose configuration changes for each microinstruction, while routing is fixed.
Most fpgas contain mini async srams used as LUTs. It's very different from using one giant LUT, which is what abusing memory chips is all about.
The LUTs we find if FPGAs are very small, often with as little as 6 input bits. Because the size of the LUT grows exponentially with the number of inputs, there's a natural sweet spot: two few inputs, and the LUT isn't powerful enough. Too many, and the LUT is too bloated.
Using a 64K ROM to encode a 16-bit LUT definitely leans in towards "way too bloated" for me.