search

adamjstewart / prolog

An implementation of Prolog written in OCaml
MIT License
2 stars 3 forks source link

Add list support and remove redundant substitutions #7

Closed Em-Wright closed 1 year ago

Em-Wright commented 1 year ago

With larger programs, the environment tends to collect a lot of substitutions for temporary variables which are no longer relevant. Since unification requires iterating through the entire list of substitutions, this slows down execution pretty significantly. I added a section in eval_query to remove these redundant substitutions.

I also added support for list notation in the lexer and parser, since this allows you to write large programs more easily.

One program where the impact of removing redundant substitutions is noticeable is the following:

take([H|T], H, T). take([H|T], R, [H|S]) :- take(T, R, S). perm([], []). perm(L, [H|R]) :- take(L, H, T), perm(T,R). ?- perm([1,2,3,4,5,6,7],L).

The effect is more pronounced on longer lists.

adamjstewart commented 1 year ago

I'm gonna be honest, this repo was just a class project I worked on 5 years ago. I wouldn't recommend using it for anything serious.

Em-Wright commented 1 year ago

I've been using this project as the basis for my diss - I submitted the pull request so I could mention that I'd done it in the write up for extra brownie points, so feel free to ignore