Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
71 votes
7 answers
21k 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 ...
Khanzor's user avatar
  • 1,451
145 votes
12 answers
43k 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 ...
Suresh's user avatar
  • 5,387
194 votes
10 answers
55k 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, ...
StrugglingProgrammer's user avatar
137 votes
7 answers
41k 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 ...
user avatar
6 votes
4 answers
1k views

Do we need recursion in programming language to solve any problem?

My question is simple: If we want to be able to solve every problem, that we can solve using recursions, do we need programming language to allow us use recursions? Assuming we are allowed to use: ...
kravemir's user avatar
  • 202
6 votes
5 answers
2k views

Are if statements unnecessary if a program is represented as an explicit state machine?

This question occurred to me some time ago when I was thinking about whether or not if statements are fundamental in computation. Consider a program that manages a ...
Devian Dover's user avatar
41 votes
8 answers
11k 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? ...
Rodrigo Valente's user avatar
76 votes
9 answers
11k 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 ...
Anderson Nascimento Nunes's user avatar
69 votes
10 answers
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, ...
Ichiro's user avatar
  • 815
29 votes
5 answers
10k 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 ...
Honinbo Shusaku's user avatar
19 votes
3 answers
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 ...
Gilles 'SO- stop being evil''s user avatar
94 votes
7 answers
24k 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 ...
evil_potato's user avatar
  • 1,372
87 votes
6 answers
31k 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 ...
Frank's user avatar
  • 1,642
43 votes
9 answers
17k 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 ...
Mr. Minty Fresh's user avatar
39 votes
10 answers
12k 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 ...
Mohammad Al-Turkistany's user avatar
38 votes
5 answers
7k 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-...
sdleihssirhc's user avatar
35 votes
14 answers
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, ...
Dave Clarke's user avatar
  • 20.2k
31 votes
2 answers
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 ...
Guy Coder's user avatar
  • 5,101
26 votes
6 answers
8k 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 ...
Zwander's user avatar
  • 365
6 votes
3 answers
2k views

Where should I start to understand how computers work? [duplicate]

I am interested in how computers work but I have no idea how the concept of 0's and 1's converts to making possible for people to control a computer by programming. I would like to understand from ...
Mardia's user avatar
  • 171
6 votes
3 answers
14k views

Call by value-result vs. call by reference?

From my Googling, it appears that call by value-result is similar to call by reference in that it changes values in the caller, but it's different in that the changes don't take place until the callee ...
Tootsie Rolls's user avatar
11 votes
3 answers
1k views

Polymorphism and Inductive datatypes

I'm curious. I've been working on this datatype in OCaml: ...
Stéphane Gimenez's user avatar
8 votes
3 answers
476 views

ML functions from polymorphic lists to polymorphic lists

I'm learning programming in ML (OCaml), and earlier I asked about ML functions of type 'a -> 'b. Now I've been experimenting a bit with functions of type ...
Gilles 'SO- stop being evil''s user avatar
5 votes
1 answer
2k views

What is the difference between the semantic and syntactic views of function types?

Edit: My original question referred to nonconstructive and constructive definitions of function types. I changed the terminology in the question and the title to semantic and syntactic, which the ...
Heatsink's user avatar
  • 223
5 votes
1 answer
128 views

What does $ \forall \alpha_1, \dots , \alpha_n . \tau $ mean formally as a type?

I was learning about polymorphic types but I couldn't understand the notation, can someone explain it means (context cs421 UIUC): $$ \forall \alpha_1, \dots , \alpha_n . \tau $$ its supposed to be a ...
Charlie Parker's user avatar
4 votes
2 answers
443 views

Compare regex in programming languages with regular expression from automata/formal language?

I'm trying to reconcile the differences/similarities between regular expression from formal language theory and automata, and the "regex" offered by programming languages. These two differ not just ...
Yibo Yang's user avatar
  • 153
3 votes
2 answers
1k views

Do "compiler" and "assembler" correspond to frontend and backend phases of a compiler?

In Compilers: Principles, Techniques, and Tools (2nd Edition) 2nd Edition by Alfred V. Aho (Author), Monica S. Lam (Author), Ravi Sethi (Author), Jeffrey D. Ullman (Author) , Figure 1.5 gives a ...
Tim's user avatar
  • 4,925
0 votes
1 answer
153 views

How can mainstream OO languages support strong binary operations by classes?

Section 24.2 in Types and Programming Languages by Pierce compares ADT and existential objects,in terms of how well they support strong binary operations: Other binary operations cannot be ...
Tim's user avatar
  • 4,925
0 votes
1 answer
2k views

Register Machine code for Fibonacci Numbers

I am not sure whether this is the right place to ask this question. I would like to write a register machine code which when given an input of n in register 1, returns (also in register 1) the nth ...
user71346's user avatar
  • 101
77 votes
4 answers
17k 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 ...
Joey Eremondi's user avatar
42 votes
2 answers
8k 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 ...
Squidly's user avatar
  • 531
38 votes
2 answers
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) ...
Gilles 'SO- stop being evil''s user avatar
36 votes
7 answers
7k 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. ...
BlueBomber's user avatar
  • 1,297
35 votes
2 answers
3k 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 ...
Matthew Towers's user avatar
27 votes
3 answers
4k 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 ...
Guy Coder's user avatar
  • 5,101
27 votes
7 answers
8k 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 ...
touring's user avatar
  • 289
27 votes
12 answers
19k 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 ...
nTuply's user avatar
  • 469
25 votes
1 answer
2k 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 ...
Martin Ender's user avatar
23 votes
2 answers
6k 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: ...
Lenar Hoyt's user avatar
23 votes
5 answers
6k 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, ...
user107952's user avatar
20 votes
5 answers
12k views

How do computers perform operations on numbers that are larger than 64 bits?

There are many reasons why numbers larger than 64 bits must be computed. For example, cryptographic algorithms usually have to perform operations on numbers that are 256 bits or even larger in some ...
CCS's user avatar
  • 343
20 votes
3 answers
4k 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 \...
Dave Clarke's user avatar
  • 20.2k
17 votes
9 answers
28k views

What problems of procedural programming does OOP solve in practice?

I have studied the book "C++ Demystified". Now I have started to read "Object-Oriented Programming in Turbo C++ first edition (1st edition)" by Robert Lafore. I do not have any knowledge of ...
user31782's user avatar
  • 271
15 votes
4 answers
5k views

Can someone give a simple but non-toy example of a context-sensitive grammar?

I'm trying to understand context-sensitive grammars. I understand why languages like $\{ww \mid w \in A^*\}$ $\{a^n b^n c^n \mid n\in\mathbb{N}\}$ are not context free, but what I'd like ...
BlueBomber's user avatar
  • 1,297
13 votes
1 answer
1k views

Why aren't we researching more towards compile time guarantees?

I love all that is compile time and I love the idea that once you compile a program a lot of guarantees are made about it's execution. Generally speaking a static type system (Haskell, C++, ...) seems ...
Shoe's user avatar
  • 279
13 votes
3 answers
2k views

Relation between Russellian type theory and type systems

I recently realized that there is some sort of relation between Russellian type theory and type systems, as found e.g. in Haskell. Actually, some of the notation for types in Haskell seems to have ...
Frank's user avatar
  • 1,642
12 votes
1 answer
1k views

Why product type is a dependent SUM?

It might just be a stupid question but I simply see no obvious reason why dependent sum type is a generalized form of product type. Concretely, the sigma type $\Sigma(x:S)T$ degenerates to a product ...
Jason Hu's user avatar
  • 632
10 votes
1 answer
4k views

What is the difference between assignment, valuation and name binding?

I read that Name binding assigns some value (data/code/expression) to an identifier. Assignment and valuation seem to do the same thing. It is confusing. Can I just tell that free variable is one, ...
Val's user avatar
  • 837
9 votes
10 answers
87k views

Computer Program vs. Algorithm

It's said that a program include algorithms, however if we refer to their definition, an algorithm is a sequence of instructions written to perform a specified task and a computer program is also a ...
Ahmad's user avatar
  • 449
9 votes
1 answer
2k views

How close are common programming languages to not being Turing complete?

The term "Turing completeness" has been discussed in several of the Computer Science classes that I've taken. However, I've never gotten an intuitive feel for what Turing completeness actually ...
haroba's user avatar
  • 193