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
11
votes
1answer
520 views

Inferring refinement types

At work I’ve been tasked with inferring some type information about a dynamic language. I rewrite sequences of statements into nested let expressions, like so: <...
5
votes
1answer
218 views

Notation for operational semantics that can be used in code comments

I'm defining an intermediate language for a multi-backend code generator that I'm writing. I want to document the operational semantics for this intermediate language in a way that is readable both ...
24
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. ...
3
votes
1answer
289 views

Is the type inference here really complicated?

There's a question on SO asking why in Java the right type doesn't get picked in a concrete case. I know that Java can't do it in such "complicated" cases, but I'm asking myself WHY? The (for ...
4
votes
3answers
956 views

What are the minimum requirements for a language to be considered Turing Complete? [duplicate]

Possible Duplicate: Are there minimum criteria for a programming language being Turing complete? I overheard a conversation on the topic and the conclusion that one gent came to was that in order ...
2
votes
2answers
1k views

How to implement deep copy?

Is there any scientific work about deep copying? So far I have only found source codes (Java, Python, ...). However, there are various approaches and nobody seems to evaluate them. Reflection-based (...
4
votes
1answer
118 views

Expression Problem – looking for a similar standard problem

The Expression Problem, populated by Philip Wadler, is a often used to standard problem to evaluate programming languages. I think it is a very clear and popular example and I wonder if there are ...
15
votes
1answer
625 views

Type inference with product types

I’m working on a compiler for a concatenative language and would like to add type inference support. I understand Hindley–Milner, but I’ve been learning the type theory as I go, so I’m unsure of how ...
8
votes
1answer
619 views

Turing Machine-Like Formalism for The Actor Model

Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done. The Actor Model is sometimes mentioned as a more powerful computational-...
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 ...
6
votes
1answer
167 views

Efficient subtype testing

Languages like Java, C#, Eiffel, and C++ have subtype hierarchies which are directed acyclic graphs, due to interfaces in Java and C# and multiple inheritance in Eiffel and C++. An obvious way to ...
35
votes
13answers
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, ...
2
votes
2answers
340 views

Equality testing of arrays and integers in a procedural language

In terms of references and their implementation on the heap and the stack, how is equality testing for arrays different from that for integers? This is to do with Java programming, if you have a ...
3
votes
2answers
421 views

Grammar in formal languages versus programming language theory

Grammars seem to be used for different purposes. In formal languages, they are used to describe sequences of symbols. In programming language theory, they are used to describe objects in a term ...
5
votes
3answers
958 views

Hoare triple for assignment P{x/E} x:=E {P}

I am trying to understand Hoare logic presented at Wikipedia, Hoare logic at Wikipedia Apparently, if I understand correctly, a Hoare triple $$\{P\}~ C ~\{Q\}$$ means if P just before C, then Q ...
7
votes
4answers
8k views

A faster, leaner JavaScript for scientific computing: what features should I keep?

Here I'm really interested in lowering barriers to mathematical education. Target: I'd like to see created for the JavaScript community, an equivalent of the Python-based/linked scientific and high-...
7
votes
1answer
266 views

Reduction rule for IF?

I'm working through Simon Peyton Jones' "The Implementation of Functional Programming Languages" and on page 20 I see: IF TRUE ((λp.p) 3) ↔ IF TRUE 3 (per β red) (1) ...
15
votes
4answers
754 views

Can a program language be malleable enough to allow programs to extend language semantics

With reference to features in languages like ruby (and javascript), which allow a programmer to extend/override classes any time after defining it (including classes like String), is it theoretically ...
16
votes
2answers
1k views

Scott-continuous functions: an alternative definition

I'm really struggling with this property: Let $X,Y$ be coherence spaces and $f: Cl(X) \rightarrow Cl(Y)$ be a monotone function. $f$ is continuous if and only if $f(\bigcup_{x\in D} x)=\bigcup_{x \...
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, ...
25
votes
2answers
440 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 ...
11
votes
1answer
458 views

Constraint-based Type Inference with Algebraic Data

I am working on an expression based language of ML genealogy, so it naturally needs type inference >:) Now, I am trying to extend a constraint-based solution to the problem of inferring types, based ...
7
votes
1answer
942 views

reduce reduce and shift reduce error in LALR grammar

I have to write a grammar for Pascal, and there is just one thing that is causing problems. Lets say we have operators (sorted by priority from low to high): Postfix ...
56
votes
6answers
13k 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 ...
13
votes
3answers
2k views

Why is using a lexer/parser on binary data so wrong?

I often work with lexer/parsers, as opposed to a parser combinator and see people who never took a class in parsing, ask about parsing binary data. Typically the data is not only binary but also ...
10
votes
3answers
763 views

Polymorphism and Inductive datatypes

I'm curious. I've been working on this datatype in OCaml: ...
64
votes
10answers
11k 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, ...
3
votes
2answers
276 views

Turing Completeness + Dataflow Unification = Arbitrarily invertible (pure, nonrecursive) functions?

Assume we are working in a Turing-complete, referentially-transparent, higher-order language that supports arbitrary dataflow unification. Shouldn't it then be possible to construct the following ...
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 \...
35
votes
10answers
10k 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 ...
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) ...
133
votes
12answers
39k 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 ...
9
votes
2answers
1k views

Does Peterson's 2-process mutual exclusion algorithm account for dying processes?

I think that in Peterson's algorithm for mutual exclusion, if the process first to enter the critical section were to die or be cancelled, the other process would loop forever, waiting to enter the ...
8
votes
3answers
373 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 ...
5
votes
1answer
63 views

Which instruction yields atomicity in this expression that makes the result 2?

I am reading about atomicity and came across the following scenario ...
19
votes
3answers
1k 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 ...
6
votes
1answer
271 views

Reflection on Concurrency

Reflection is a common mechanism for accessing and changing the structure of a program at run-time, found in many dynamic programming languages such as Smalltalk, Ruby and Python, and in impoverished ...
18
votes
3answers
871 views

Problems Implementing Closures in Non-functional Settings

In programming languages, closures are a popular and often desired feature. Wikipedia says (emphasis mine): In computer science, a closure (...) is a function together with a referencing ...
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 ...
11
votes
4answers
402 views

Can you specify a programming language without implementation?

Is it theoretically possible to specify a programming language for which no implementation could exist? A programming language is a way of defining functions. An implementation means a method to ...