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

763 questions
Filter by
Sorted by
Tagged with
24 views

### Why does the category of language types have morphisms, not functors?

I am probably not phrasing this question well, so please bear with me as I try to explain what I mean. I am working on learning category theory, as applied to programming. So far, I understand that: ...
27 views

### What is the relation between a programming language and the language of its input?

I find some references say that all the features of programming language fall within what can be captured by context-sensitive grammars. In fact, no programming language known to humankind anything ...
159 views

### Why is the assignment rule the way it is in Hoare Logic?

Why is the assignment rule the way it is in Hoare Logic/Axiomatic Semantics? I can't wrap my head around why the assignment rule is backwards from what I expected. I understand Hoare logic is use to ...
34 views

### How to translate automaton (Turing machine) into the program of high level programming language?

Every program in high level ("industrial") programming language can be expresses as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian ...
28 views

### Are these two sensible and related or unrelated ways of regarding a logic system as a programming language?

When I am trying to understand logic programming languages e.g. Prolog, I am immediately confused by the following two ways of relating logic systems and programming languages or type systems. In ...
29 views

### What are the pros and cons of these two coding patterns/structures? And do they have a formal term?

I have traditionally been doing things like this: function test() // A { if (/* conditions */) return true; else return false; } Of late, ...
9 views

### What data model(s) can Datalog apply to?

Datalog is similar to Prolog. Both are logical programming languages. In Database System Concepts 6ed, Datalog is used as a query language for tuple relational calculus (a kind of relational data ...
16 views

### Is relational algebra a procedural, imperative, and/or declarative language?

In Database System Concepts 6ed, 6.2 The Tuple Relational Calculus When we write a relational-algebra expression, we provide a sequence of procedures that generates the answer to our query. ...
148 views

### Proper algorithm for resolving ambiguity in grammars via enforcing associativity and precedence rules

I was told there is a algorithm that always resolves ambiguity for grammars that have issues with precedence and associativity. I know ambiguity in general is undecidable, so I only want to resolve ...
32 views

### Can a programming language be designed to use a fixed amount of memory?

I have been toying around with the idea of creating a programming language as a side-project, specifically trying to get extreme performance out of a machine. I have been thinking about the ...
31 views

### When concatenating two sequences, can evaluations of two input sequences be in parallel with each other?

In Practical Foundation of Programming Languages by Harper (www.cs.cmu.edu/~rwh/pfpl/2nded.pdf), 37.3 Multiple Fork-Join So far we have conﬁned attention to binary fork/join parallelism ...
14 views

### How is cooperative multi-threading implemented in terms of coroutines?

In Practical Foundations of Programming Languages by Harper, Although it is relatively easy to visualize and implement coroutines involving only two partners, it is more complex and less useful to ...
25 views

### What is the denotation for identifiers?

I am trying to understand what is the domain for denotational semantics. Right now the way I understand denotational semantics is that given some syntax of a program that maps to some mathematical ...
37 views

### How shall I understand the undesirable consequences of dynamic scoping?

In Practical Foundation of Programming Languages by Harper 8.4 Dynamic Scope Another approach, called dynamic scoping, or dynamic binding, is sometimes advocated as an alternative to static ...
52 views

### Why was R designed as a 1-starting indexes language?

Spawning from here: We usually don't care whether indices start at $0$ or $1$ (except in the sense we'd rather start with our favourite if it doesn't matter, and the old joke is that set theorists ...
42 views

### Does assembly language get translated to binary code? If so, is assembly language portable across machines?

I've tried to find the answer through Google but I've come across conflicting uses of terminology, so I just wanted to be absolutely clear. Here is my understanding: High level code written in a ...
71 views

### What is the language feature which allows a variable to be associated with values of different types?

In Python, I can change the types of values associated with a variable: >>> x=1 >>> x="abc" In C, I can't do the same. What is the name of ...
46 views

### Is the choice of static and dynamic typing not visible to the programmers of the languages? [closed]

From Design Concepts in Programming Languages by Turbak Although some dynamically typed languages have simple type markers (e.g., Perl variable names begin with a character that indicates the type ...
31 views

### Why is this grammar ambiguous?

S ::= x S ::= if E then S S ::= if E then S else S This is example if E then if E then x else x proves that it is ambiguous ...
37 views

### Are type variables really only used in mathematical conversation about types?

Are type variables really only used in mathematical conversation about types? i.e. are type variables (meta-variables that only contain the type classification label) only exist in proofs for types ...
58 views

### What is the difference between $\alpha \to \alpha$ vs $\forall \alpha. \alpha \to \alpha$?

I was studying polymorphic types and I was finding the distinction with monomorphic types difficult to pin down (context CS 421). From the course I linked the have the following (vague attempt) at a ...
73 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 ...
32 views

### Why is empty in this Abstract Syntax Tree?

I given the following code to write as AST: { a = 4; while (a<10) if (a<5) a = a+5; else a = a+3; } ...
22 views

### Confused about substitution in grammar in certain cases

To illustrate my confusion let's say I'm given this unambiguous grammar in BNF: ...
29 views

### How to intuitively come up with an example for an ambiguous grammar and how to make that grammar unambiguous?

I don't get how to intuitively come up with an example for an ambiguous grammar. Let's take as an example this grammar: ...
61 views

### Difference between ⫾ (U+2AFE) and ⫿ (U+2AFF) in the context of Dijkstra's Guarded Command Language?

Continuing https://tex.stackexchange.com/questions/435986/how-to-draw-the-box-of-dijkstras-guarded-command-language, what is the difference in the intended usage of ⫾ (Dijkstra choice, U+2AFE) and ⫿ (...
298 views

### Why does higher-order abstract syntax need an inverse to define catamorphisms?

In the introduction to the colorfully-named Boxes Go Bananas: Encoding Higher-Order Abstract Syntax with Parametric Polymorphism, Washburn and Weirich describe a problem in traditional formulations of ...
10 views

### Do forward chaining (Rete) business rules (Drools, ILOG) / production rules support higher order rules and compositionality?

There is this talk http://andrewcropper.com/pubs/jelia19-typed.pdf about higher order Prolog, about use of higher-order predicates (that takes other predicates as arguments) and compositionality of ...
50 views

### I don't see why the array[1..3, 1…2] is faster to index than array[1…2, 1…3]?

In my programming concept class we learned that for the array type it's faster to index in memory if the length of an element is = $2^n$. This case make us only need to offset instead of actually ...
13 views

### Manage nested recursions in the design of a concatenative language interpreter

I'm in the designing of an interpreter for a stack based concatenative language, and I'm currently stuck with a problem about recursion of some of my concatenative program to calculate factorial: <...
20 views

### Do Rank-1 (prenex) polymorphism and Predicative polymorphism mean the same?

https://en.wikipedia.org/wiki/Parametric_polymorphism says: Rank-1 (prenex) polymorphism In a prenex polymorphic system, type variables may not be instantiated with polymorphic types.[4] ...
22 views

### What are the relation and differences between reification and type passing semantics?

https://en.wikipedia.org/wiki/Type_erasure says type erasure refers to the load-time process by which explicit type annotations are removed from a program, before it is executed at run-time. ...
127 views

### What can't you do without Turing-completeness?

I suppose that, since a Turing-complete language can simulate a Turing-machine, a non-Turing-complete language can't, but most programs do not have the simulation of a Turing machine as their purpose. ...
20 views

### What are the relations between these two descriptions of let polymorphism?

In Types and Programming Languages by Pierce, there are two descriptions of let-polymorphism. Sec23.8 Fragments of SystemF on p359 says This has led to various proposals for restricted fragments ...
29 views

### What are the difference and relation between type checking and type reconstruction?

In Types and Programming Languages by Pierce, ML-style let-polymorphism was ﬁrst described by Milner (1978). A num- ber of type reconstruction algorithms have been proposed, notably the clas- ...
47 views

### What is “Hindley-Milner (i.e., uniﬁcation-based) polymorphism”?

In Types and Programming Languages by Pierce, Ch11 Simple Extensions extends the typed lambda calculus. Section 11.5 Let Bindings says: In Chapter 22 we will see another reason not to treat let as ...
21 views

### Does Hindley-Milner refer to the unification algorithm for type reconstruction, a type system, or a form of polymorphism?

What does Hindely-Milner refer to? In Types and Programming Languages by Pierce, I only find that Section 22.4 Unification mentions "Hindley" and "Milner", when introducing the unification algorithm. ...
43 views

### Can most programs (except the IO part) be re-written as a sequence of matrix operations?

I got this idea recently. If we do not consider the data IO part of software, imagine the data is in the memory and we need to come out with some decision (which product to recommend to a user, how to ...
37 views

### Advantage of Stack-Based Allocation for Local Variables

While learning stack allocation, I came across this paragraph in the textbook (Programming Language Pragmatics - 3rd Edition): Even in a language without recursion, it can be advantageous to use a ...
26 views

### What does valid method overriding mean?

In Types and Programming Languages by Pierce, from p257 to p258, about featherweight Java, The predicate override(m, D, C→C0) judges whether a method ...
52 views

### Which is a type of objects in mainstream OO languages: a class, an interface, an abstract class, a metaclass?

In Types and Programming Languages by Pierce, Section 18.6 Simple Classes in Chapter 18 Imperative Objects says: We should emphasize that these classes are values, not types. Also we can, if we ...
60 views

### Is JavaScript a homoiconic language?

I can't help but notice the uncanny resemblence JavaScript has to LISP. JSON (JavaScript Object Notation), for instance, is a data structure that can be reconstituted into an object by subjecting it ...
20 views

### When did our current concepts of program modularity develop?

I take it that the concept of a modular subroutine call/return existed prior to the concept of a call stack (and hence to the possibility of recursive subroutines or of recursion limits). I would ...
27 views

### Does an ADT have multiple or only one representations/implementations?

Section 24.2 in Types and Programming Languages by Pierce defines ADTs in existential types: A conventional abstract data type (or ADT) consists of (1) a type name A, (2) a concrete representation ...
20 views

### Why can System F1 a.k.a. λ → have kind *, but no quantification ∀?

In Types and Programming Languages by Pierce, on p461 in Section 30.4 Fragments of 30.4.1 Deﬁnition: In System F1 , the only kind is ...
43 views

### What order logic does a system correspond to under Curry–Howard correspondence?

In Types and Programming Languages by Pierce, Section 9.4 Curry–Howard correspondence on p109 has a table Does the table mean that the simply typed lambda calculus ...
10 views

### Can two type expressions in different kinds have subtyping relation and equivalence relation?

In Higher-order bounded quantiﬁcation ($F^ω_{<:}$), introduced in Ch31 in Types and Programming Langauges by Pierce, its subtyping and equivalence rules are: Does subtyping relation only exist ...
33 views

### Is → a type operator?

In Types and Programming Languages by Pierce, The level of types contains two sorts of expressions. First, there are proper types like Nat, Nat→Nat, Pair Nat Bool, and ∀X.X→X, which are ...