Questions related to design, implementation, and analysis of programming languages

learn more… | top users | synonyms (1)

1
vote
1answer
74 views

Calculi for a computability class

Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the ...
-4
votes
0answers
12 views

You have an error in your SQL syntax;check the manual that corresponds to your MySQL server version for the right syntax to use near 'False' at line 1 [on hold]

You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'False' at line 1 Hi guys! I'm new in programming. I'm having ...
2
votes
0answers
16 views

Where does the term “Amechanicity” for type-error generation come from

I've been looking at these slides about improving type error messages for programming languages. One of the things they describe, starting at Slide 8, is the concept of amechanicity. Anytime the ...
2
votes
1answer
59 views

Is the memory usage of total languages deterministic?

I'm interested in the memory usage of various programming languages when implemented on actual hardware. I believe that a Turing-complete programming language has, in general, unknowable memory usage ...
-1
votes
0answers
5 views

Comparing Two Lists in SML using Fold/Map? [migrated]

Say I have two lists, [1,2,3] and [9,2,3]. Say I'm given a third element, 2. If I want to find out if two is in both lists, but I can only use foldl/foldr/map to do so (no let environments or custom ...
4
votes
1answer
56 views

What does Harper mean by “class”?

I've been teaching myself type theory on and off over the past couple years. I've reach large sections of Pierce's Types and Programming Languages and Harper's Foundations of Programming Languages, ...
4
votes
0answers
57 views

What was the first programming language with loop break?

While tracing the history of the BREAK and CONTINUE statements found in popular languages, I ran into a dead end right around ALGOL. Algol _? -> CPL -> BCPL -> C -> C++ -> Java -> JavaScript What ...
1
vote
3answers
144 views

String Comparison vs. Hashing

I recently learned about the rolling hash data structure, and basically one of its prime uses to searching for a substring within a string. Here are some advantages that I noticed: Comparing two ...
1
vote
0answers
16 views

converting each element in a group/list of number into other base [closed]

I am new to python programming. I am now trying to build a program which convert every element in a list of numbers of base 10 into its base 4. For example here, say i have numbers from 0 to 20 or ...
4
votes
3answers
91 views

What is the difference between Abstract Data Types and objects?

An answer on Programmers.SE characterizes an essay by Cook (Objects are not ADTs) as saying Objects behave like a characteristic function over the values of a type, rather than as an ...
2
votes
1answer
37 views

Prove an arithmetic property of a partial recursive function

I have this program written in haskell : I have to prove that: $(\forall a \in \mathbb{N})[!D_V [h](a) \Rightarrow log_2 (D_V[h](a) )\equiv 2 (mod$ $ 10) ]$. The predicate $P_2$ for the $g$ ...
2
votes
0answers
28 views

What language features would I need to remove from a real programming language to make it decidable? [closed]

Let's say that I want to restrict certain features of a common programming language--for instance, C--such that the result is decidable, and thus no longer Turing-complete. What language features, at ...
1
vote
1answer
53 views

What is the Haskell-style type signature called (i.e., who is it named after)?

A type signature in Haskell is written in the following format: functionName :: (arg1Type, arg2Type) -> returnType There's a (hyphenated, after a person or ...
3
votes
1answer
75 views

What is the point of delimiters and whitespace handling

I see that language specifies reserved words, delimiters and whitespaces in the lexer section. Are delimiters just like reserved identifiers in the punctuation space or they have additioinal function ...
0
votes
0answers
30 views

How cin and cout work in C++ [duplicate]

I am interested in knowing the blow by blow account of what happens from the time the compiler reads a text document containing a cout/cin command to the time the executable it generates is finished ...
1
vote
0answers
28 views

Where does the Dynamic Link point to on the activation record

I'm a bit confused as to wear exactly the dynamic link points to on the activation record. I understand that it points to the 'top' of the instance of the callers activation record but I am unsure of ...
6
votes
2answers
99 views

Why are strings immutable in some languages?

String is an immutable class in Java. An immutable class is simply a class whose instances cannot be modified. Why does the Java programming language choose to make objects of class String immutable? ...
3
votes
0answers
25 views

How did MacLisp's garbage collector “run in the register set”?

Olin Shivers, ‘History of T’: Maclisp on the [PDP]-10 had used a mark&sweep GC (one version of which famously "ran in the register set," though that is another story) This implies, in my ...
7
votes
1answer
79 views

Can we do everything in imperative languages with a functional language if it does not allow for a 'state'?

I was reading Structure and Interpretation of Computer Programs (SICP), MIT. What I have understood is that in pure functional programming language, there is no such thing as a local state. SICP, pg ...
2
votes
1answer
25 views

Call-by-reference semantics for RPC

Does call-by-reference semantics for remote procedure call (RPC) have a real use case? Why does call-by-reference RPC exist? Is it useful for anything? Is there a scenario where call-by-value can't ...
4
votes
2answers
74 views

Interpretation in scripting languages

Why is pure interpretation more common for scripting languages compared to programming languages? I mean, why are programs written in a scripting language not converted to machine language and then ...
2
votes
0answers
40 views

Differences between programming model and programming paradigm?

What is the relation and difference between a programming model and a programming paradigm? (especially when talking about the programming model and the programming paradigm for a programming ...
5
votes
1answer
62 views

Error in solution in Types and Programming Languages?

I'm reading Types and Programming Languages and trying to understand the solution to exercise 5.2.4 on untyped lambda calculus / Church numerals: Define a term for raising one number to the power ...
5
votes
1answer
115 views

Implementing primitive recursive functions in a programming language

I started studying Design Concepts in Programming Languages by Turbak, Gifford and Sheldon. In the first chapter, they define a language called POSTFIX, similar to a postfix calculator's input ...
5
votes
2answers
83 views

What real-world computer languages cannot be described by deterministic grammars?

Are there any examples of real-world computer languages that are non-deterministic? By computer languages I include programming languages, markup languages, query languages, modeling language, ...
3
votes
4answers
91 views

Why translating a program from one high-level programming language directly into another is difficult?

I am looking for a better explanation (research level, papers) to answer: Why translating a program from one high-level programming language directly into another is difficult? Note: When I say ...
5
votes
2answers
262 views

In the Curry-Howard isomorphism as applied to Hindley-Milner types, what proposition corresponds to a -> [a]?

(Using Haskell syntax, since the question is inspired by Haskell, but it applies to general Hindley-Milner polymorphic types systems, such as SML or Elm). If I have a type signature ...
18
votes
9answers
6k views

Programming language where every expression makes sense

Per recommendation I am reposting this from Stack Overflow. Recently I have been thinking about following issue. Consider the code for a standard "Hello world!" program: ...
5
votes
3answers
149 views

How did it happen that Algol 60 was an improvement on its successors?

The original statement referred to by this question is: The more I ponder the principles of language design, and the techniques which put them into practice, the more is my amazement and ...
5
votes
1answer
143 views

Can a functional language be homoiconic?

According to the wikipedia page on homoiconicity: In a homoiconic language the primary representation of programs is also a data structure in a primitive type of the language itself. I was ...
-2
votes
1answer
29 views

Trying to code for calculating cosine series [closed]

I was trying to calculate cosine series : cos x = 1 - x^2/2! + x^4/4! - x^8/8! .... , where x is in radians: include iostream include math.h using namespace std; long factorial (long num) { if ...
2
votes
1answer
16 views

Can big-step semantics express evaluation order?

Can you express evaluation order using big-step semantics? For example, in a simple language consisting of only if t then t else t and ...
0
votes
1answer
37 views

Is program analysis part of programming language theory?

If I am correct, programming language theory studies syntax and semantics of programming languages, and design and implementation of programming languages (e.g. compiler, ...) Does programming ...
0
votes
2answers
102 views

Why would you introduce the goto statement into a modern language?

I just found out something really quite extraordinary. While looking through Stackoverflow, I came across a question about removing goto from a php function. PHP ...
3
votes
1answer
51 views

Inference rule with two conclusions or rather inverse function application

I want to express a simple correctness theorem for a term-desugaring function $\Delta$. The goal is to express that if the evaluation of a desugared term yields a value, this value is the desugared ...
2
votes
0answers
38 views

What algorithm solves high-order unification for untyped terms in most cases?

High-order pattern matching is an undecidable problem. That means there is no algorithm that, given an equation a => b, where ...
3
votes
1answer
36 views

Subgraph of an interprocedural control flow graph

Say I have the interprocedural control flow graph (ICFG) of a program. Now I am only interested in the control flow between two functions f1 and f2. What is the most straight-forward way to remove ...
14
votes
1answer
314 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 ...
4
votes
2answers
102 views

Are Strings Scalar?

I have always considered strings scalar and the main reason for that is that in programming we treat string values a lot like primitive values. But this and this Wikipedia definitions, as far as I ...
6
votes
1answer
138 views

Is there a way of objectively measuring the efficiency or quality of software or code design?

I've been thinking about ways of measuring code, and, quite frankly, I can't think of truly objective, semi-universal ways of evaluating the quality or "strength" of code to say, "Yes, this is better ...
3
votes
1answer
79 views

Creating arrays of object of abstract class in statically-typed object-oriented languages

In statically-typed object-oriented languages (like Java, C++, C#, ...), suppose I declare an abstract class: ...
1
vote
2answers
62 views

How can I infer inputs to a function, given an output?

Is there a way to generate a set of inputs, for a given output of a function? This may be a common thing in lisp/haskell world, but I'm not aware of it. Is this what mini-kanren does? I understand ...
9
votes
9answers
4k 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 ...
2
votes
2answers
104 views

Why is least fixed point (lfp) important in program analysis

I am trying to get a big picture on the importance of least fixed point (lfp) in program analysis. For instance abstract interpretation seems to use the existence of lfp. Many research papers on ...
108
votes
10answers
38k 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, ...
6
votes
3answers
1k views

Which research languages have a stronger typesystem than Haskell and why?

Here I read that: Haskell definitely does not have the most advanced type system (not even close if you count research languages) but out of all languages that are actually used in production ...
3
votes
2answers
133 views

Are syntax and semantic just 2 structures such that one is a model of the other?

The syntax of a language is a structure. The semantic of a language is a structure. The semantic of a language is a model of its syntax. And that's all ? The duality syntax/semantic is just model ...
3
votes
1answer
181 views

Difference between “data dependence graph”, “data dependency graph”, and “data flow graph”

Is there a difference between a "data dependence graph" and a "data dependency graph"? I have seen both terms - sometimes used interchangeably sometimes not. To make things even more complicated, a ...
3
votes
2answers
22 views

Is there a formal term for functions that have static state across executions?

Two examples, one in PHP: function adder($i){ static $a = 0; $a += $i; return $a; } A similar effect can be achieved with closures in javascript: ...
-2
votes
3answers
72 views

Book reference: Programming Languages are for humans

Currently I'm writing my thesis and I made the assumption that all programming languages are made for humans and humans alone. There's no reason to make compromises to fit the machine needs. ...