# Tag Info

284

There is no necessary relation between the implementation of the compiler and the output of the compiler. You could write a compiler in a language like Python or Ruby, whose most common implementations are very slow, and that compiler could output highly optimized machine code capable of outperforming C. The compiler itself would take a long time to run, ...

103

In programming language design and implementation, there is a large number of choices that can affect performance. I'll only mention a few. Every language ultimately has to be run by executing machine code. A "compiled" language such as C++ is parsed, decoded, and translated to machine code only once, at compile-time. An "interpreted" language, if ...

100

How can a machine built by a man be stronger than a man? This is exactly the same question. The answer is that the output of the compiler depends on the algorithms implemented by that compiler, not on the langauge used to implement it. You could write a really slow, inefficient compiler that produces very efficient code. There's nothing special about a ...

97

There is no formal definition of "safe programming language"; it's an informal notion. Rather, languages that claim to provide safety usually provide a precise formal statement of what kind of safety is being claimed/guaranteed/provided. For instance, the language might provide type safety, memory safety, or some other similar guarantee.

94

I want to make one point against a common assumption which is, in my opinion, fallacious to the point of being harmful when choosing tools for a job. There is no such thing as a slow or fast language.¹ On our way to the CPU actually doing something, there are many steps². At least one programmer with certain skillsets. The (formal) language they program ...

82

Turing-complete means "can compute every function on natural numbers that a Turing machine can compute". It means exactly that and only that. A list is not a natural number, and list intersection is not a function on natural numbers. Note: it is, of course, possible to encode lists as natural numbers, which would then make list intersection a ...

71

Turing complete languages can compute the same set of functions $\mathbb{N}^k \rightarrow \mathbb{N}$, which is the set of general recursive partial functions. That's it. This says nothing about the language features. A Turing Machine has very limited compositional features. The untyped $\lambda$-calculus is far more compositional, but lacks many features ...

63

The distinction between interpreted and compiled code is probably a fiction, as underlined by Raphael's comment: the claim seems to be trivially wrong without further assumptions: if there is an interpreter, I can always bundle interpreter and code in one executable ... The fact is that code is always interpreted, by software, by hardware or a combination ...

63

Table of Contents I will divide my explanation of Tarjan's pseudocode into the following sections: Tarjan's If-else Blocks (the -> & | operators) Assignment and Equality Tests (:= and =) There is else if, but no else construct Tarjan's Conditional Assignment Operator := if Additional Examples of Tarjan's if and := if 5.5. ...

62

Practically no programming language, modern or ancient, is truly context-free, regardless of what people will tell you. But it hardly matters. Every programming language can be parsed; otherwise, it wouldn't be very useful. So all the deviations from context freeness have been dealt with. What people usually mean when they tell you that programming languages ...

60

If you have a few minutes, most people know how to add and multiply two three-digit numbers on paper. Ask them to do that, (or to admit that they could, if they had to) and ask them to acknowledge that they do this task methodically: if this number is greater than 9, then add a carry, and so forth. This description they just gave of what to do that is an ...

60

Simula 67 is generally considered the first object-oriented language and predates Smalltalk by a number of years. It also used the this keyword for the same concept, which can be seen in this book chapter extract: class Linker; begin ref(Linker) Next, Sex, Employment; text ID; procedure Add_to_List(LHead); name LHead; ref(Linker) LHead; ...

57

Idris is Turing Complete! It does check for totality (termination when programming with data, productivity when programming with codata) but doesn't require that everything is total. Interestingly, having data and codata is enough to model Turing Completeness since you can write a monad for partial functions. I did this, years ago, in Coq - it's probably ...

57

TLDR; this is possible but not practical. (assuming the translator has access to the requisite libraries)? This ends up being the tricky bit, and is part of why things like this don't end up being used in practice. All compilers are translators. Translating from one language to another is definitely possible, and this is literally all a compiler is ...

55

This is simply not true. And part of why it's false is that the premise isn't well formed. There is no such thing as a fast or slow language. The expressive power of a language is purely a function of its semantics. It is independent of any particular implementation. You can talk about the performance of code generated by GCC, or about the performance of the ...

54

Turing-completeness says one thing and one thing only: a model of computation is Turing-complete, if any computation that can be modeled by a Turing Machine can also be modeled by that model. So, what are the computations a Turing Machine can model? Well, first and foremost, Alan Turing and all of his colleagues were only ever interested in functions on ...

52

in school you (probably) memorized the common operations (addition, subtraction, multiplication and division) for decimal 1 digit numbers. Then you learned how to do operations on larger numbers using those memorized operations by doing the computation part by part for example long multiplication and long division. A computer can do the same algorithms using ...

49

Turing completeness is an abstract concept of computability. If a language is Turing complete, then it is capable of doing any computation that any other Turing complete language can do. This does not, however, say how convenient it is to do so. Some features that are easy in some languages may be very difficult in others, due to design choices. Turing ...

47

Assembly language is a way to write instructions for the computer's instruction set, in a way that's slightly more understandable to human programmers. Different architectures have different instruction sets: the set of allowed instructions is different on each architecture. Therefore, you can't hope to have a write-once-run-everywhere assembly program. ...

46

The earliest known use of % for modulo was in B, which was the progenitor of C, which was the ancestor (or at least godparent) of most languages that do the same, hence the operator's ubiquity. Why did Thompson and Richie pick %? It had to be a printable ASCII character that wouldn't conflict with B's other features. % was available, and it resembles the / ...

45

Direct answer to the question: yes, there are esoteric and highly impractical PLs based on $\mu$-recursive functions (think Whitespace), but no practical programming language is based on $\mu$-recursive functions due to valid reasons. General recursive (i.e., $\mu$-recursive) functions are significantly less expressive than lambda calculi. Thus, they make a ...

44

In short, the answer is yes. But you're mixing two completely unrelated meanings of the term "language" (yes, this is confusing): A set of strings. "Context-free language" means "a set of strings which can be recognized using a context-free grammar". A way of specifying a computation. "Turing-complete language" means "a way of specifying programs in which ...

43

If you can get your hands on a copy of Benjamin Pierce's Types and Programming Languages, in the introduction, he has a good overview on various perspectives on the term "safe language". One proposed interpretation of the term that you might find interesting is: “A safe language is completely defined by its programmer’s manual.” Let the definition of ...

40

The main differences are along two dimensions -- in the underlying theory, and in how they can be used. Lets just focus on the latter. As a user, the "logic" of specifications in LiquidHaskell and refinement type systems generally, is restricted to decidable fragments so that verification (and inference) is completely automatic, meaning one does not require ...

40

To taper expectations a little bit, I will first note that the term "programming language" is deliberately broad: it is intended to be open to some interpretation. It means, no more and no less, any convention that is used for describing instructions for computers to execute. This includes, for example, not just C++ and Python, but also things like ...

34

Why do we need assembly language? Well, there's actually only one language we will ever need, which is called "machine language" or "machine code". It looks like this: 0010000100100011 This is the only language your computer can speak directly. It is the language a CPU speaks (and technically, different types of CPUs speak different versions). It also ...

32

The first thing to note is that this isn't necessarily true. For example, depending on the language a function with that type, besides being the identity function, could: 1) loop forever, 2) mutate some state, 3) return null, 4) throw an exception, 5) perform some I/O, 6) fork a thread to do something else, 7) do call/cc shenanigans, 8) use something like ...

31

Redcode, the assembly language behind codewars, was explicitly written to have very few halting instructions, because the code often gets mangled before it finally gives out, and the more opportunities it has to halt, the less interesting the game is. You see very few such languages in practice because we don't just want a program to run, we want it to run ...

28

Many of these tools do work directly with the abstract syntax tree (or rather, a direct one-to-one visualisation of it). That includes Blockly, which you've seen, and the other block-based languages and editors like it (Scratch, Pencil Code/Droplet, Snap!, GP, Tiled Grace, and so on). Those systems don't show a traditional vertex-and-edge graph ...

28

Storing local variables on a stack is an implementation detail – basically an optimization. You can think of it this way. When entering a function, space for all local variables is allocated somewhere. You can then access all variables, since you know their location somehow (this is part of the process of allocation). When leaving a function, the space is ...

Only top voted, non community-wiki answers of a minimum length are eligible