zmonx

Whatever it does, I expect Emacs to not crash.

If it cannot allocate more memory, I expect it to throw a Lisp exception that tells me so, not to crash the whole process.

I greatly appreciate Daniel's work to increase the robustness of Emacs, because it means that there will be fewer situations where a process crash leads to lost work for users. In addition, increasing the robustness of Emacs in such cases will also greatly broaden the set of test cases that can be run reliably, and hence help to detect and correct even more issues.

You can crash Emacs for example with the recipe from #2099:

   $ emacs -Q --eval "(let (v) (while t (setq v (cons v v))))"

These are very good points! I would generalize "functional" to declarative though:

Logic programming languages like Prolog and Mercury are also much more amenable to parallelization than C-like languages.

In fact, different Prolog clauses could in principle be executed in parallel without changing the declarative meaning of the program, at least as long as you stay in the so-called pure subset of the language which imposes certain restrictions on the code.

Prolog has definite clause grammars (DCGs), which are very similar to monads.

You can think of a DCG as giving you two implicit arguments, which you can use to express concatenations and in fact arbitrary relations between states.

There are also ways to access these implicit arguments, which are similar to the corresponding constructs in Haskell.

DCGs are a very important feature of Prolog. They are frequently used for parsing and state transformation tasks. Like monads in Haskell, DCGs often make working with immutable data much more convenient, because you can make the more uninteresting parts of your code implicit. Other logic programming languages like Mercury also support DCGs.

Yes, indeed!

Please note that what makes this reasoning method so easily applicable in this case is uniformity of the abstract syntax, not of the surface syntax, which is also called concrete syntax.

Homoiconicity is a relation between the concrete and abstract syntax tree (AST) of programs and the language's built-in data structures.

For one particular example where homoiconicity makes reasoning about programs easier, consider an important reasoning method called abstract interpretation:

https://en.wikipedia.org/wiki/Abstract_interpretation

Using abstract interpretation, you can derive interesting program properties. The uniformity and simplicity of Prolog code, as well as its built-in language constructs like unification and backtracking, make it especially easy to write abstract interpreters for Prolog.

Here is a paper that applies this idea to derive several interesting facts about programs and their meaning:

Michael Codish and Harald Søndergaard, Meta-circular Abstract Interpretation in Prolog (2002) https://link.springer.com/chapter/10.1007%2F3-540-36377-7_6

Abstract interpretation is also applicable to other programming languages. However, it is much easier to apply to homoiconic languages like Prolog.

Please note that the creators of Julia no longer call it homoiconic [1].

The fact that you can access the AST in a language is not sufficient to make it homoiconic. There are several programming languages like Julia that let you access the AST yet are not (conventionally) considered homoiconic.

[1] https://stackoverflow.com/questions/31733766/in-what-sense-a...

In my experience, that is an overgeneralization, though definitely a tempting one that is frequently encountered.

That being said, I find that Prolog code is often more readable than Lisp code. An important reason for this is that Prolog supports prefix, infix and postfix operators that can be defined as part of the concrete syntax. On the level of the abstract syntax tree, all terms conform to the inductive definition, so this is only a notational convenience.

To distinguish homoiconic languages from others (where you may also "operate on the parse tree just the same as you can on regular program data"), a bit more qualification is needed though.

For example, in typical cases, reasoning about such data structures (lists in Lisp, terms in Prolog, bytes in assembly code etc.) is very convenient in homoiconic languages, and in fact I think one could rightfully regard this ability to conveniently reason about a program's abstract syntax tree via built-in language mechanisms as a key advantage of homoiconic languages.

In my opinion, this article puts too much emphasis on reading, and too little emphasis on actually reasoning about programs in homoiconic languages like Prolog and Lisp, and due to this imbalance the conclusion is not sufficiently justified.

It is true: Being able to "read without parsing" is definitely nice.

But that is only a subset of those advantages that a homoiconic language gives you. An at least equally important advantage is due to the fact that programs in homoiconic languages are typically very easy to reason about by built-in mechanisms in that language.

For example, Prolog programs are readily represented as Prolog terms, and can be easily reasoned about by built-in mechanisms such as unification.

Since I regard it as a key advantage of homoiconic languages that their abstract syntax is completely uniform and can typically be easily reasoned about within such languages, I disagree with the main point that the article is trying to make.

One interesting fact about homoiconicity is that extremely low-level languages (like assembly code) and extremely high-level languages (like Prolog) are homoiconic, yet there is a large gap "in the middle", where there are many languages (like Java, C, Python etc.) that lack this property.

Yes, very much so.

In addition, some of the automated translators I have seen also apply automated refactoring: They tend to merge similar sections of code and minimize the delta (similar to diff) that is factored out. This can create a maintenance problem especially in the context of a system like the IRS's, where presumably the code that performs calculations for different years or other periods (legislations etc.) is similar but not identical, but must be retained as fully as possible to reliably perform calculations that are subject to earlier regulations.

Such portions of code should be kept distinct, but an automated conversion may conflate them, and it may require additional and error-prone fiddling to enforce the separation.

Although it may appear a bit surprising at first, assembly language is homoiconic in the sense that you can easily reason about the program code within the language: It is easy to reason about bytes in assembler language, and compiled assembler code is just a sequence of bytes.

This is similar to high-level languages like Lisp and Prolog, whose code is readily represented by built-in data structures in the respective language.

A fun fact about this is that extremely low-level (like assembly) and extremely high-level (like Prolog) languages are homoiconic, but there is a large gap "in the middle" (like Java, C), where there are many languages that lack this property.

I agree, and recommend Biomake:

https://github.com/evoldoers/biomake

It uses the declarative programming language Prolog to write flexible rules.

A logic programming language like Prolog is very well suited for expressing rule-based dependencies.

Very nice, thank you for sharing!

I have one comment on the naming convention. Consider has_type/3 from the post. For example:

    has_type(_, true, bool).

    term_type(_, true, bool).

    context_term_type(_, true, bool).

The reason for this apparent discrepancy is found in the difference between strong and weak NP-completeness.

The fully polynomial-time approximation scheme (FPTAS) for the knapsack problem only runs in so-called pseudo-polynomial time:

https://en.wikipedia.org/wiki/Pseudo-polynomial_time

This means that the runtime is polynomial in the numeric value of the knapsack. Since the encoding of that numeric value only takes logarithmic space (unless you are using unary encoding), the runtime is in fact again exponential in the size of the input.

For this reason, the knapsack problem is called weakly NP-complete:

https://en.wikipedia.org/wiki/Weak_NP-completeness

One can show that, unless P=NP, a so-called strongly NP-hard optimization problem with polynomially bounded objective function cannot have a fully polynomial-time approximation scheme:

https://en.wikipedia.org/wiki/Polynomial-time_approximation_...

SAT, Hamiltonian circuit etc. are strongly NP-complete:

https://en.wikipedia.org/wiki/Strong_NP-completeness

Thus, an FPTAS for these problems would indeed imply P=NP.

The authors have built a start-up based on these ideas:

http://memcpu.com/

They provide their SAT solver as a service that you can try.

A related paper I recommend in this context is NP-complete Problems and Physical Reality by Scott Aaronson:

https://www.scottaaronson.com/papers/npcomplete.pdf

This title is misleading: This was formulated as a question that was put forward (verbatim text: "Is a blockchain essentially a linked list?"), and the current answers are already now diverging between "Not at all!" and "Yes, ... blockchain is similar to a linked list ...".

Very nice, thank you for posting this!

Program slicing is especially useful when debugging and reasoning about programs in declarative languages, such as Prolog.

In Prolog, it is natural to think in terms of generalizations and specializations of programs, and you can often explain important program properties such as nontermination and failure by showing relevant fragments of clauses.

See also failure slicing.

In declarative languages, slicing is much more convenient and useful than tracing the execution.

25 years for acceptance are very well aligned with the timeline that Richard P. Gabriel has outlined in "Models of Software Acceptance":

• Technology in the lab (t=0)

• Technology in the first company (t=2–10 years post-lab)

• Technology in the first successful company (t=5–20 years post-lab)

• Technology acceptance (t=10–25 years post-lab)

Source:

https://www.dreamsongs.com/Files/AcceptanceModels.pdf

In these slides, Richard gives several examples that match this model and includes several additional explanations.

For example:

• First window system: Stanford/SRI/Xerox PARC ~1975, MIT ~1976

• First commercial use: Symbolics (1979), LMI (1979), Xerox Star (~1980), Apple Lisa (~1982), Apple Macintosh (1984)

• First use by a successful company: Microsoft (~1989)

• Technology acceptance: Microsoft (~1995)

Spreadsheets are another example that is given in the slides. In fact, 25 years for acceptance are quite common in software. Sometimes, it also takes much longer.

Thank you for sharing this! It's nice to see Prolog used for such tasks, which are a good fit for a logic programming language.

I have one small suggestion that I hope you find useful: Currently, the code is rather imperative: It contains lots of side-effects that have immediate consequences which cannot be easily reasoned about. You can use Prolog this way. However, you forfeit its most interesting advantages if you use it as an imperative language instead of a declarative one.

A major attraction of Prolog is that it allows you to declaratively describe what holds. Therefore, I recommend to aim for declarative descriptions of situations, and limit side-effects to a few isolated areas of your program.

Here is an example: In brexit.pl, you currently have the following:

    notice_persons_at(Place) :-
            person_at(X, Place),
            write('Apparently '),
            write(X),
            writeln(' is here, that is your'),
            writeln('chance for a quick chat. Type "\e[1mtalk.\e[0m" to start'),
            writeln('start the conversation').

    notice_persons_at(Place) -->
            { person_at(X, Place) },
            ['Apparently ',X,' is here, that is your ',
             'chance for a quick chat. Type ', bold(talk), 'to start',
             ' the conversation'].

In addition, it allows you to later switch to a different way of outputting this text altogether. For example, at one point, you may want to convert this into a web-based application: In that case, the output should no longer be emitted on the system terminal, but sent as HTML snippets to the client.

Thus, I recommend to first focus on a clear declarative description of everything that should occur in your program, formulated as a DCG or via a domain-specific language you may want to design for this specific task of implementing a text-based game. Later, you can flexibly interpret this language in any way you want!

The same goes for the uses of assert/1 and rectract/1 that are currently sprinkled through your code: This imperative style prevents you from using the predicates in all directions. If you use a more declarative formulation, you will be able to use the code in much more flexible ways. A declarative way to express state changes is to think in terms of relations between states. Think about it this way: There is an initial state, and a user's actions relate any given state to a new state. Thus, state changes can be modeled as relations between states, and you will be able to use such predicates in reverse and also in the most general way!

The beauty of this is that a constraint solver (over finite domains, Boolean values, sets etc.) blends in completely seamlessly into the way Prolog works.

From the perspective of Prolog and its users, a constraint solver is simply available just like any other predicate! All the internal reasoning a constraint solver performs is completely abstracted away. The only interface is typically a few Prolog predicates that let you access the features of the solver by stating what must hold about the involved variables.

So, to use a constraint solver in Prolog, you simply use the predicates it provides, just as you would use any other Prolog predicate. In the example above, I am using the constraint (#=)/2, which is a predicate that is true iff its arguments evaluate to the same integer.

From the perspective of implementors, Prolog is a great implementation language for constraint solvers due to its built-in search and backtracking mechanisms. It also allows you to use the standardized Prolog syntax that many users are already familiar with, instead of having to devise yet another modeling language on top of your solver.

Thus, I would describe the relation as a natural symbiosis: It is natural to use constraint solvers in Prolog, and natural to implement them in Prolog.

Please see my profile page: It contains links that I find relevant for learning modern Prolog features.

Every predicate you impose on the set of solutions can be regarded as a constraint, because it can at most restrict the set of solutions, never increase it.

So, in fact, every Prolog goal you invoke is a constraint. When reasoning over Herbrand terms, the only constraints are equality and disequality of terms, which are implemented by the predicates (=)/2 and dif/2, respectively.

In addition to these basic constraints over terms, modern Prolog systems also provide constraints over more specialized domains, such as constraints on integers, rational numbers and Boolean values. For combinatorial tasks such as map coloring, constraints over integers are especially useful.

For example, here is a constraint on integers, using GNU Prolog:

    | ?- 3 #= 1+Y.
    
    Y = 2

Constraints implement relations between their arguments and can be used in all directions. This is the reason why Prolog predicates are typically more general than functions in other languages. However, to truly benefit from this, you must consistently use these comparatively new language features instead of lower-level ones. I say comparatively because these language features have been available for several decades by now in professional Prolog systems such as SICStus.

In fact, the "old semantics" actually included language constructs that are only now becoming available (again) in Prolog systems.

An example of such a construct is dif/2, which is a constraint that was provided in even the very first Prolog system, sometimes called Prolog 0, several decades ago. However, it was not widely available in Prolog systems until much more recently, even though professional Prolog systems such as SICStus have provided it for longer. Also arithmetic constraints were available in early implementations such as Prolog IV. So, in a sense, we are now going "back to the roots" of Prolog by making very old features widely available.

In my personal view, calling modern Prolog an "incompatible paradigm" with the way that Prolog is still being taught is not completely fitting, yet still more right than wrong: The new features are not meant to be used "on top" of old features, but instead! When using modern Prolog features to their fullest extent, you can completely eschew those language constructs that traditionally cause the worst problems for beginners.

Moded arithmetic is a prime example for this, which can be replaced completely by arithmetic constraints in modern Prolog systems. dif/2 is also a good example, which lets you avoid (\+)/1 in many cases by using a more general predicate instead.

Due to their operational semantics that is very hard to explain and understand, rather limited constructs often take significant room in many Prolog courses, and replacing them by more modern alternatives will entail a paradigm shift towards better methods and also make room for even more new material that can be covered instead. This is because on top of being more general, the new language constructs are often also easier to understand for beginners.

In a sense, yes, these modules are written in Prolog. However, that is not the full story: CLP requires special interface predicates that the underlying Prolog system must provide. You cannot implement CLP "on top" of just any Prolog system with reasonable performance and correctness.

Devising and implementing such suitable interface predicates is quite hard, and only a very small number of Prolog systems have succeeded with this so far.

For example, the SWI interface for CLP is too limited in practice, and its constraint solvers have elementary mistakes also because of the limitations of the interface predicates it provides.

In contrast, SICStus Prolog provides a much more general interface to attributed variables that supports all widely used constraint solvers (finite domains, Boolean variables, rational numbers etc.) with good performance and no known mistakes.

The tutorial you link to has several rather severe shortcomings, and I cannot recommend it for learning CLP(FD). Please see my profile page if you are interested in Prolog resources.

I agree with what Sylvain Soliman said about this on Reddit: It's a nice tutorial for the 80's parts of the language:

https://www.reddit.com/r/programming/comments/7hp2xw/introdu...

In modern Prolog systems, you would use more declarative features such as constraints to model combinatorial tasks like map coloring.

Make sure to check out modern Prolog features if you are interested in learning the language seriously!

Sorting and then summing is a commonly used technique. Still, there are also better methods such as Kahan summation:

https://en.wikipedia.org/wiki/Kahan_summation_algorithm

Using pairwise addition is a very good alternative with the added benefit that it can be easily parallelized.

Personally, I would gladly use a number format that does not require such special considerations for summing a set of numbers, and still yields good results. I am really looking forward to alternative representations.

Yes, that is true.

It is true that cancellation errors are often the source of wrong results.

However, computations involving IEEE floating point arithmetic can go horribly wrong even if there is no addition and no subtraction whatsoever, no divisions, and only a very small number of rounding errors. Here is one such example:

http://people.eecs.berkeley.edu/~wkahan/WrongR.pdf

Even professional users working in this domain will have a hard time to locate the cause of such problems involving IEEE floating point arithmetic. The format is extremely error-prone to use for casual users and experts alike.

Yes, I think these are fair statements.

John Gustafson's presentation also includes a few important points about interval arithmetic:

http://www.johngustafson.net/presentations/Right-SizingPreci...

In such cases, you get a ubound that contains the exact value. When the inputs are exact, the result is exact too.

Here is a sample implementation in Julia:

https://github.com/JuliaComputing/Unums.jl