Questions tagged [programming-languages]

Questions related to design, implementation, and analysis of programming languages. NOT for questions about how to program, which are off-topic on this site.

Filter by
Sorted by
Tagged with
185
votes
10answers
52k views

How can a language whose compiler is written in C ever be faster than C?

Taking a look at Julia's webpage, you can see some benchmarks of several languages across several algorithms (timings shown below). How can a language with a compiler originally written in C, ...
137
votes
12answers
40k views

Why are there so many programming languages?

I'm pretty fluent in C/C++, and can make my way around the various scripting languages (awk/sed/perl). I've started using python a lot more because it combines some of the nifty aspects of C++ with ...
125
votes
7answers
32k views

Is Category Theory useful for learning functional programming?

I'm learning Haskell and I'm fascinated by the language. However I have no serious math or CS background. But I am an experienced software programmer. I want to learn category theory so I can become ...
88
votes
7answers
20k views

Why are some programming languages “faster” or “slower” than others?

I have noticed that some applications or algorithms that are built on a programming language, say C++/Rust run faster or snappier than those built on say, Java/Node.js, running on the same machine. I ...
74
votes
9answers
10k views

What properties of a programming language make compilation impossible?

Question: "Certain properties of a programming language may require that the only way to get the code written in it be executed is by interpretation. In other words, compilation to a native machine ...
68
votes
10answers
12k views

Can a dynamic language like Ruby/Python reach C/C++ like performance?

I wonder if it is possible to build compilers for dynamic languages like Ruby to have similar and comparable performance to C/C++? From what I understand about compilers, take Ruby for instance, ...
68
votes
6answers
22k views

Formal program verification in practice

As a software engineer, I write a lot of code for industrial products. Relatively complicated stuff with classes, threads, some design efforts, but also some compromises for performance. I do a lot of ...
66
votes
4answers
12k views

Dependent types vs refinement types

Could somebody explain the difference between dependent types and refinement types? As I understand it, a refinement type contains all values of a type fulfilling a predicate. Is there a feature of ...
63
votes
14answers
17k views

How can I explain to my parents that I study programming languages?

I am currently finishing my MSc in computer science. I am interested in programming languages, especially in type systems. I got interested in research in this field and next semester I will start a ...
58
votes
6answers
14k views

Are there minimum criteria for a programming language being Turing complete?

Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete? From what I can tell from wikipedia, the language needs to ...
55
votes
9answers
29k views

What is a safe programming language?

Safe programming languages (PL) are gaining popularity. I wonder what is the formal definition of safe PL. For example, C is not safe, but Java is safe. I suspect that the property “safe” should be ...
53
votes
1answer
11k views

What is the earliest use of the “this” keyword in any programming language?

I understand the this (or self or Me) is used to refer to the current object, and that it is ...
50
votes
8answers
20k views

How are variables stored in and retrieved from the program stack?

Apologies in advance for the naivety of this question. I am a 50 year old artist trying to properly understand computers really for the first time. So here goes. I have been trying to understand how ...
43
votes
9answers
15k views

Why are some programming languages Turing complete but lack some abilities of other languages?

I came across an odd problem when writing an interpreter that (should) hooks to external programs/functions: Functions in 'C' and 'C++' can't hook variadic functions, e.g. I can't make a function that ...
40
votes
2answers
7k views

How does Tarjan's pseudocode work (explained to someone familiar with C or Java)?

The Short Story A famous computer scientist, Tarjan, wrote a book years ago. It contains absolutely bizarre pseudocode. Would someone please explain it? The Long Story Tarjan is known for many ...
39
votes
2answers
7k views

What can Idris not do by giving up Turing completeness?

I know that Idris has dependent types but isn't turing complete. What can it not do by giving up Turing completeness, and is this related to having dependent types? I guess this is quite a specific ...
38
votes
8answers
10k views

What determines the “speed” of a programming language?

Suppose a program was written in two distinct languages, let them be language X and language Y, if their compilers generate the same byte code, why I should use language X instead of the language Y? ...
38
votes
2answers
2k views

Are generational garbage collectors inherently cache-friendly?

A typical generational garbage collector keeps recently allocated data in a separate memory region. In typical programs, a lot of data is short-lived, so collecting young garbage (a minor GC cycle) ...
36
votes
14answers
5k views

Criteria for selecting language for first programming course

As a university-level CS educator, the issue of which programming language to teach in the first programming course often comes up for discussion. There are thousands of languages to choose between, ...
35
votes
10answers
11k views

Visual Programming languages

Most of us learned programming using "textual" programming languages like Basic, C/C++, and Java. I believe it is more natural and efficient for humans to think visually. Visual programming allows ...
35
votes
2answers
2k views

on “On the cruelty of really teaching computing science”

Dijkstra, in his essay On the cruelty of really teaching computing science, makes the following proposal for an introductory programming course: On the one hand, we teach what looks like the ...
33
votes
5answers
6k views

Can regular languages be Turing complete?

I was reading about Iota and Jot and found this section confusing: Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly left-...
31
votes
7answers
90k views

Why do we need assembly language?

We mostly write programme in high level language. So while studying I came across assembly language. So an assembler converts assembly language to machine language and a compiler does the same with ...
30
votes
4answers
5k views

Clear, intuitive derivation of the fixed-point combinator (Y combinator)?

The fixed-point combinator FIX (aka the Y combinator) in the (untyped) lambda calculus ($\lambda$) is defined as: FIX $\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. ...
30
votes
2answers
3k views

How are programming languages and foundations of mathematics related?

Basically I am aware of three foundations for math Set theory Type theory Category theory So in what ways are programming languages and foundations of mathematics related? EDIT The original ...
28
votes
6answers
9k views

Are there programs that can 'translate' source code between any two languages?

Are there programs that can 'translate' source code between any two languages (assuming the translator has access to the requisite libraries)? If there are, how do they work (techniques used, ...
28
votes
9answers
4k views

Are programming languages becoming more like natural languages?

Can we study programming languages in the context of linguistics? Do programming languages evolve naturally in similar ways to natural languages? Although full rationality, and mathematical ...
28
votes
7answers
4k views

Why is the object destructor paradigm in garbage collected languages pervasively absent?

Looking for insight into decisions around garbage collected language design. Perhaps a language expert could enlighten me? I come from a C++ background, so this area is baffling to me. It seems ...
26
votes
7answers
7k views

Are all turing complete languages interchangeable

Note, while I know how to program, I'm quite a beginner at CS theory. According to this answer Turing completeness is an abstract concept of computability. If a language is Turing complete, then ...
26
votes
6answers
6k views

What is the Relationship Between Programming Languages, Regular Expressions and Formal Languages

I've looked around the net for an answer to this question and it seems as if everybody implicitly knows the answer except me. Presumably this is because the only people who care are those who have had ...
26
votes
3answers
3k views

What is the relation between functors in SML and Category theory?

Along the same thinking as this statement by Andrej Bauer in this answer The Haskell community has developed a number of techniques inspired by category theory, of which monads are best known but ...
25
votes
11answers
14k views

Is a universal assembly language for all computers possible?

I would like to ask a few questions about Assembly language. My understanding is that it's very close to machine language, making it faster and more efficient. Since we have different computer ...
25
votes
3answers
3k views

Visual programming tools, why don’t they work with the AST directly?

I've found several open source visual programing tools like Blockly and friends, and other projects hosted at Github, but could't find any that work directly with the abstract syntax tree. Why is ...
25
votes
3answers
3k views

What are staged functions (conceptually)?

In a recent CACM article [1], the authors present an implementation for staged functions. They use the term as if it was well-known, and none of the references looks like an obvious introduction. ...
25
votes
2answers
452 views

Is there evidence that using dynamic languages has an impact on productivity?

I am wondering if there are any experiments that show the existence or the non-existence of a correlation between usage of a dynamic language (such as Python, Ruby, or even languages that run on the ...
24
votes
5answers
7k views

Why are functional languages Turing complete?

Perhaps my limited understanding of the subject is incorrect, but this is what I understand so far: Functional programming is based off of Lambda Calculus, formulated by Alonzo Church. Imperative ...
23
votes
8answers
7k views

Programming language where every expression makes sense

Per recommendation I am reposting this from Stack Overflow. Recently I have been thinking about following issue. Consider the code for a standard "Hello world!" program: ...
23
votes
2answers
7k views

Do any programming languages use general recursive functions as their basis?

This is a naïve and, therefore, possibly malformed question, so apologies in advance! My view is that a Turing Machine can be seen as the computational basis for procedural/imperative programming ...
23
votes
4answers
4k views

How do garbage collectors avoid stack overflow?

So I was thinking about how garbage collectors work and I thought of an interesting issue. Presumably garbage collectors have to traverse all structures in the same way. They can't know weather they ...
23
votes
3answers
1k views

Categorisation of type systems (strong/weak, dynamic/static)

In short: how are type systems categorised in academic contexts; particularly, where can I find reputable sources that make the distinctions between different sorts of type system clear? In a sense ...
23
votes
1answer
1k views

Does a do-while loop suffice for Turing-completeness?

I know that, in imperative programming languages, a while-do loop is sufficient as a control flow construct to make the language Turing-complete (as far as control flow goes - of course we also need ...
21
votes
6answers
3k views

Halting problem theory vs. practice

It is often asserted that the halting problem is undecidable. And proving it is indeed trivial. But that only applies to an arbitrary program. Has there been any study regarding classes of programs ...
20
votes
7answers
2k views

What are examples of inconsistency and incompleteness in Unix/C?

In Richard Gabriel's famous essay The Rise of Worse is Better, he contrasts caricatured versions of the MIT/Stanford (Lisp) and New Jersey (C/Unix) design philosophies along the axes of simplicity, ...
20
votes
6answers
5k views

What is the difference between a scripting language and a normal programming language?

What is the difference between programming language and a scripting language? For example, consider C versus Perl. Is the only difference that scripting languages require only the interpreter and don'...
20
votes
3answers
3k views

When are two simulations not a bisimulation?

Given a labelled transition system $(S,\Lambda,\to)$, where $S$ is a set of states, $\Lambda$ is a set of labels, and $\to\subseteq S\times\Lambda\times S$ is a ternary relation. As usual, write $p \...
19
votes
5answers
4k views

What is the formal, rigorous definition of a programming language?

In programming language theory, people study the theory behind programming languages. But I have never heard any formal definition of programming languages themselves. What is the formal definition, ...
19
votes
3answers
2k views

ML function of type 'a -> 'b

Our professor asked us to think of a function in OCaml that has the type 'a -> 'b i.e. a function of one argument that could be anything, and that can return ...
19
votes
2answers
3k views

Type-checking algorithms

I am starting a personal bibliographic research on type-checking algorithms and want some tips. What are the most commonly used type-checking algorithms, strategies and general techniques? I am ...
18
votes
4answers
2k views

Why must a function with polymorphic type `forall t: Type, t->t` be the identity function?

I am new to programming language theory. I was watching some online lectures in which the instructor claimed that a function with polymorphic type ...
18
votes
2answers
4k views

What makes PROLOG Turing-complete?

I know that it can be proven PROLOG is Turing-complete by constructing a program that simulates a Turing machine like this: ...

1
2 3 4 5
17