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.
688
questions
-2
votes
0answers
52 views
Is the infinite program Turing-recognizable/decidable?
Imagine we have a program which does an infinite loop: while(true){loop}
We run the program on a linux machine(assume the compilation is ok), then this linux ...
-3
votes
0answers
15 views
what is soln and code for this problem [on hold]
given string s1 and s2, we have to transform s1 to palindrome such that s1 contain s2 as substring
in minimum opeartion, where operation is we can convert any character to an other character . print -...
0
votes
1answer
18 views
How does this example violate Liskov substitution principle, which then causes violation of the open-closed principle?
From Agile Principles, Patterns, and Practices in C# by Robert Martin,
Listing 10-1. A violation of LSP causing a violation of OCP
...
0
votes
1answer
22 views
Does the concept of subtype require dynamic method binding?
https://en.wikipedia.org/wiki/Subtyping says
In programming language theory, subtyping (also subtype polymorphism or inclusion polymorphism) is a form of type polymorphism in which a subtype is a ...
1
vote
2answers
70 views
Type theory for imperative programming languages?
The type theory that I have seen is all developed over lambda calculus, which is an inherently functional language.
Nevertheless, in practice imperative languages have type systems. Are there ...
0
votes
0answers
16 views
Does formal specification of UX needs special language apart from the general specification languages?
I am fan of Alloy and CASL specification languages and my question is - what is the common practice regarding the formal methods in UX? Does UX require distinct specification languages? Generally one ...
1
vote
0answers
45 views
Is it possible to write a fully-decidable type system for the J language?
I'm experimenting with the J array language, a dynamically-typed array language with mutable assignment, subtyping, and function overloading (just like traditional APL).
It is unclear to me whether ...
0
votes
1answer
109 views
Why there aren't any famous programming languages that implement what Alan Kay considers to be “real OOP”? [closed]
Why there aren't any famous programming languages that implement what Alan Kay considers to be "real OOP"?
Is it because the "modern OOP" that exists in programming languages like C++ and C# and Java ...
2
votes
1answer
36 views
Properties of reciprocal Quines
I was reading about the concept of quine and in particolar of "reciprocal Quines" for example a Program $A$ that output the code of a program $B$ and vice versa, with the two being written in the same ...
1
vote
3answers
82 views
in function declarations, what advantages are there to having the type of the parameter specified after the parameter name?
For typed languages, what advantages/disadvantages are there to specifying the parameter type after the parameter name?
For languages like C and Java, the type comes first:
...
6
votes
1answer
87 views
Can all regular tree types be expressed as $\mu$ types?
In "Types and Programming Languages", Pierce gives a translation from recursive types ($\mu$ types) to types expressed as regular trees: possibly infinite trees, but with finitely many distinct ...
1
vote
0answers
27 views
What is the difference between self-rewriting program and program-with-updates-and-restart
I am reading about Goedel machine http://people.idsia.ch/~juergen/goedelmachine.html and especially the article about possible implementation (in the Scheme language) of this machine http://people....
0
votes
1answer
41 views
Construct a grammar for the language
How can I achieve this. Write a grammar for the language consisting of strings built only of the letters a and b. The strings may have any number of these letters, but the letter combinations bab must ...
12
votes
1answer
156 views
Is the IO monad technically incorrect?
On the haskell wiki there is the following example of conditional usage of the IO monad (see here).
...
12
votes
3answers
3k views
Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks? [closed]
Python quite famously uses indentation to syntactically define blocks of code. (See Compound statements in the Python Language Reference). After years of using Python I'm still intrigued by and very ...
2
votes
1answer
52 views
Why are both caller-save registers and callee save registers needed?
I am having a difficult time understanding callee and caller-save registers. I get that caller-save registers are those which are needed after function call and hence caller saves them in caller ...
2
votes
1answer
26 views
Why “Choice Points” introduce non-determinism in a program?
I'm studying the didactic programming language Oz, following the book "Concepts, Techniques, and Models of Computer Programming".
In the book, the nondeterminism is introduced through the concept of ...
1
vote
1answer
27 views
What is the relation between an algorithm and its implementation at the level of code?
Is there any isomorphism or equivalence relation? What strictly bind these two together?
0
votes
0answers
27 views
Law and contracts as “programs” executed by human brains
Note: This question is NOT about using computers/AI in legal practice.
I found a paper (pdf here) that makes the analogy between law and computer programming:
Laws and contracts are programs/...
4
votes
1answer
441 views
What are the characteristics of a typeless programming language?
Assume that we have an imaginary programming language that allows you to assign a Literal to a variable, but does not allow you to set the the data type of the variable, for example
...
0
votes
0answers
20 views
Declarative vs Relational Programming
I've searched a lot on the web, and I found no material that expresses clearly and in simple terms what is the difference between declarative and relational programming. Can you help me ?
1
vote
1answer
75 views
Why is the syntax of some programming languages very much not according to earlier conventions? [closed]
Looking at the syntax of the programming language C and others inspired by it, I cannot help but ask the question in the title. Mathematics, logic and other subjects have been existing for many ages ...
6
votes
1answer
88 views
How do we know $\neg \neg LEM$ isn't provable in MLTT?
I've been trying (fruitlessly) to prove something which I now know is not provable. Take the following definitions:
$$LEM \equiv \prod_{A : Type} \neg A \vee A$$
$$DNE \equiv \prod_{A : Type} \neg \...
1
vote
1answer
46 views
Fixed Points of Factorial Function
(This is taken from the book Semantics with Applications)
I'm trying to determine the fixed points for the following block:
...
1
vote
2answers
59 views
Proving Turing Completeness by creating a compiler to a Turing Complete language
Given a programming language A unknown to be Turing Complete, if one can create a compiler for a TC programming language B using A does this imply that A is itself Turing Complete? If so, what is the ...
0
votes
0answers
32 views
Trying to determine Fixed Points
I'm basically trying to solve 4.2
(Taken from Semantics with Applications)
As I see it, the functional F will be defined like so:
...
0
votes
2answers
52 views
Can a language with some set of higher-order functions like map, fold and filter but without recursion or iteration be Turing complete?
I was reading this article and was wondering if there is any finite set of higher-order functions like map, fold or filter such that they could empower a language to be Turing complete even without ...
1
vote
1answer
46 views
How much does C# gain from its value types
C# makes an distinction between value types and reference types contrast to Java where all (except primitives types) are of reference semantics. The design decision, as I understand it, is mainly to ...
3
votes
1answer
33 views
“Immediate” method of translating arbitrary mutable program to equivalent unmutable program?
Consider the following program in "mutable style":
x=1
x=f(x);
x=f(x);
We can rewrite this in "immutable style" without changing the higher-level structure of ...
1
vote
1answer
48 views
Sizeof function definition in a system
Why sizeof(int) and sizeof(int *) takes different value in a system? I mean generally size of integer is 4 B, but size of integer pointer is 8 B. But why they cannot take same value, although their ...
-1
votes
1answer
38 views
Term for the use of the same programming language in every tier?
What is the technical term that describes the use of the same programming language in every tier in the architecture of a system? For example, having JavaScript in model, view and controller.
edit #1:...
1
vote
2answers
155 views
Pass by Value or by Reference and Impure or pure functions
Beginner question: I am teaching myself the two passing techniques: Pass by Value and Pass by Reference.
Can Pass by Value change the states of an object? If yes, how? Which of the two techniques ...
0
votes
0answers
45 views
How does computer work? [duplicate]
I am not a computer scientist or even a student of CS. I just want to find more information and would like if someone could put if in right direction about how actually computer works. I understand ...
0
votes
1answer
98 views
Is ambiguity in Programming Language always bad?
Suppose we have a token and our language allows the compiler to build two different derivation trees. However, it can happen that there exists two semantic ways to interpret our token. So ambiguity is ...
1
vote
2answers
94 views
Is lazy evaluation required for do-notation?
Do-notation is most famous by Haskell, which is also famous for having lazy evaluation.
But is lazy evaluation a requirement for implementing do-notation?
In principle, could do-notation be added ...
5
votes
3answers
81 views
How exactly do we define parametric polymorphism?
My naive distinction between parametric polymorphism and ad-hoc polymorphism, is that:
In parametric polymorphism, the type is given as a variable: (pseudocode)
Function f: <.Type T> T $\to$...
0
votes
3answers
102 views
Preconditions and postconditions
What are preconditions and postconditions in this C++ function?
I have this example in my slides but still didn't get the idea!
...
1
vote
1answer
44 views
Generalization of Functors to other datatypes?
Functors in category theory, and also in its application to functional programming, can be seen as a kind of "structured" functions: Given two sets $A,B$, rather than just having a function $f:A\to B$,...
0
votes
1answer
66 views
Why in Declarative Programming variables are not reassigned?
I've read that a Declarative language is called "stateless". This means that we can imagine that internally every variable is a constant variable, and it never get reassigned ( in contrast with what ...
2
votes
1answer
79 views
Is the Shakespeare Programming Language Turing complete?
I was reading about tge Turing machine. I also came across with the Shakespeare programming language. After trying to understand the basics of the PL, I thought ...
4
votes
0answers
27 views
Static type analysis with dynamic scoping?
Both in school and out, I have only ever encountered dynamic scoping paired with dynamic typing. Is there any published work (even if just academic, not yet implemented in a "real" programming ...
3
votes
2answers
255 views
The idea behind the state of Imperative languages
I was reading about programming paradigms and I have a question about the state when speaking about Imperative languages. What does it mean to change the program's state? Is it just an abstract idea? ...
1
vote
0answers
44 views
Reasons for why x - 1 and x -1 gives different result in some languages [closed]
I assume the reason space makes a difference in F# is due to reserving a certain function, when minus is in front of a number without space, however what are the reasons for this? I can't seem to find ...
3
votes
3answers
123 views
How does a computer “wait” time?
Me and a friend were discussing how programming languages can perform asynchronous tasks, like waiting 15 seconds before performing another task, and we started a debate.
I know that computers have ...
6
votes
1answer
68 views
Type system with subtyping on abstract data types?
Consider this example on binary trees in some ML-like language:
...
1
vote
0answers
34 views
Converting (reverse-engineering) Turing machine into program or most concise algorithm?
It is known that every program or every algorithm can be converted to Turing machine. But what about the reverse process? Is there algorithm (or research trend that considers such algorithm) to ...
39
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 ...
5
votes
1answer
595 views
Where are C++ templates inside of the lambda cube?
C++ templates have type variables and can express lambdas, so they must have System F embedded. But is that exactly where they are located in the lambda cube? Can C++ templates produce new types or ...
3
votes
0answers
45 views
Computability of Kolmogorov complexity in total languages
It is well known that the Kolmogorov complexity is uncomputable in Turing-complete programming languages. However, what about total programming languages?
For example, is the Kolmogorov complexity of ...
1
vote
1answer
71 views
Reason programming language B was named “B”?
I’ve searched around for this already but ironically the results have been overshadowed by “Why C was named C” instead.
If C was named “C” because it came after B, why was B named "B", since the only ...
