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
0
votes
0answers
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: ...
0
votes
1answer
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
0
votes
0answers
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, ...
-1
votes
0answers
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 ...
0
votes
1answer
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. ...
3
votes
0answers
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 confined attention to binary fork/join parallelism ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
-1
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
5
votes
1answer
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 ...
0
votes
0answers
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; } ...
0
votes
1answer
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: ...
1
vote
1answer
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: ...
3
votes
1answer
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 ⫿ (...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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: <...
1
vote
0answers
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] ...
1
vote
0answers
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. ...
3
votes
2answers
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. ...
0
votes
0answers
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 ...
0
votes
1answer
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 first described by Milner (1978). A num- ber of type reconstruction algorithms have been proposed, notably the clas- ...
-1
votes
1answer
47 views

What is “Hindley-Milner (i.e., unification-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 ...
2
votes
0answers
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. ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 Definition: In System F1 , the only kind is ...
-1
votes
1answer
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 ...
0
votes
0answers
10 views

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

In Higher-order bounded quantification ($F^ω_{<:}$), introduced in Ch31 in Types and Programming Langauges by Pierce, its subtyping and equivalence rules are: Does subtyping relation only exist ...
0
votes
0answers
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 ...
0
votes
0answers
23 views

Does λ→ have type operators?

In Types and Programming Languages by Pierce, Ch11 Simple Extensions introduces λ→ as the simply typed lambda calculus with simple extensions, and introduces <...
0
votes
0answers
24 views

Is the language “untyped arithmetic expressions” in Types and Programming Languages not Turing complete?

In Types and Programming Languages by Pierce, is it correct that the language introduced in Chapter 3 Untyped Arithmetic Expressions is not Turing complete? Because it doesn't provide recursion. the ...