zmonx

8 jaar geledendiscuss

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.

zmonx

8 jaar geledendiscuss

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

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

In response to how such deep structures can arise: They may for example arise when testing Emacs with randomly generated code snippets. For testing edge cases, it is highly desirable that Emacs run robustly also in such situations.

zmonx

8 jaar geledendiscuss

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.

zmonx

8 jaar geledendiscuss

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.

zmonx

8 jaar geledendiscuss

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.

zmonx

8 jaar geledendiscuss

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.

zmonx

8 jaar geledendiscuss

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...

zmonx

8 jaar geledendiscuss

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.

zmonx

8 jaar geledendiscuss

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.

zmonx

8 jaar geledendiscuss

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.

zmonx

8 jaar geledendiscuss

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.

zmonx

8 jaar geledendiscuss

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.

zmonx

9 jaar geledendiscuss

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.

zmonx

9 jaar geledendiscuss

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).

A better name for this would be:

    term_type(_, true, bool).

or even:

    context_term_type(_, true, bool).

This makes clear what each of the arguments means, and does not limit the reading to only one direction of use. Note that we can query this also in other directions, and the predicate still makes sense!

zmonx

9 jaar geledendiscuss

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.

zmonx

9 jaar geledendiscuss

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

zmonx

9 jaar geledendiscuss

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 ...".

zmonx

9 jaar geledendiscuss

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.

zmonx

9 jaar geledendiscuss

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.

zmonx

9 jaar geledendiscuss

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').

Consider formulating this declaratively, for example as follows:

    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'].

I am using a Prolog definite clause grammar (DCG) to describe the output that is expected to occur at this place. Since I am decoupling this description from the actual side-effect of emitting the output, I have won a lot of convenience, flexibility and versatility. You see that this description is shorter and can be used not only for actually emitting the output, but also to easily test whether the program (still) behaves as intended.

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!

Submissions

Schedulebot: Simple Scheduling in Braid

The Warren Abstract Machine in Rust

Second-Guessing R

Algorithmic Program Debugging [pdf]

Building and Probing Prolog with Intel Architecture

comments