Questions tagged [implementation]
For questions regarding the implementation of a feature in coding languages.
63
questions
5
votes
5
answers
859
views
Correctness of mixed signed/unsigned arithmetic
I'm implementing signed and unsigned integers in my language. They are represented in C as signed long and unsigned long ...
- 145
-1
votes
0
answers
49
views
How to be (more) critical during Code Reviews of team members? [closed]
I'm a Software Engineer who sometimes need to review the code of my fellow team members. I often look at the source code and think; this looks fine. I'm having a hard time to think critical about it. ...
- 1
-2
votes
1
answer
135
views
Low effort, high impact optimizations? [closed]
The Pareto principle tells us that 20% of our efforts will bring us 80% of the results. The same should be true of optimizations.
Are there optimization techniques out there that:
Are simple and easy ...
- 145
4
votes
2
answers
142
views
Supporting reasonably efficient high-level indexing for strings
I'm designing a language that I intend to be implemented on the .NET platform. To my understanding, the native string representation uses UTF-16, by storing an array of ...
- 1,155
9
votes
3
answers
1k
views
Do parsers typically need access to all tokens?
Do parsers typically operate on the entire array/list of tokens available in memory, or are the tokens often streamed one by one as they are recognized? What influences the decision?
- 557
29
votes
11
answers
18k
views
Why do so many programming languages not have a "built-in" way to do simple math functions?
Note 1: My question is not about the factorial function. It's about "simple math functions" that high-school level pocket calculators can do, but most programming languages cannot do without ...
- 805
4
votes
1
answer
213
views
Earliest implementation of pattern matching as a programming language feature
As far as I can tell pattern matching was first proposed as a language feature by Burstall (1969). However, it was a proposal for a feature in the language ISWIM, which itself never had a completed ...
-1
votes
1
answer
216
views
Look behind in parsers [closed]
If Sandwich's AST generator finds that the first token is an identifier, one of two cases can be true:
Function call
Variable assignment
It stores the identifier and checks if the next token is a = ...
- 9
16
votes
2
answers
2k
views
How do lexers/parsers distinguish between nested generics and bitshifts?
The lexical grammar of Java has a special case for the the > character. Normally, tokens are formed based on the longest-match rule, so that an input string of <...
- 16.3k
2
votes
1
answer
315
views
Are enum members literals or constants in an IR?
While implementing enums in Tyr, I just realized that enum constants are the only form of literal-like entity that is not represented like a literal in the intermediate representation.
The enum ...
- 1,533
9
votes
4
answers
922
views
Data structures for scopes and variable shadowing
Let's say I have some code in my target language like:
...
- 1,043
6
votes
1
answer
233
views
How do you implement a structural subtyping checker?
In a structurally-typed language, one type is a subtype of another iff it has all of the fields/methods of the other with compatible types, meaning that field or return types are subtypes, parameter ...
- 10.9k
5
votes
0
answers
143
views
What are some design errors that lead to hard-to-debug code? [closed]
There are some design features in programming languages that make code written in the language difficult to debug (e.g. C's default fallthrough behavior).
So it would be helpful to make a list of ...
- 159
34
votes
6
answers
4k
views
How to ensure that an optimising compiler will terminate?
An optimising compiler typically applies some set of rewrites to some intermediate representation of the program, replacing terms with other terms which are supposed to be equivalent but more ...
- 16.3k
2
votes
1
answer
223
views
3
votes
1
answer
166
views
Call-by-value: Left-to-right vs right-to-left
There are three standard evaluation strategies for the lambda calculus:
Call-by-value (CBV)
Call-by-name
Call-by-need
There are two variants of CBV that differ on how they behave with respect to ...
- 159
6
votes
2
answers
658
views
Empirically, what are the implementation-complexity and performance implications of "unboxed" primitives?
I'm designing a Python-like language: bytecode-compiled, brace-free syntax, reference semantics for variables. Among many differences from Python, I want to support a limited form of static typing. I ...
- 1,155
11
votes
2
answers
341
views
Why did Objective-C remove `NSZone`?
NSZone is a type representing a memory allocation. NSObject implements the allocWithZone: ...
- 8,563
6
votes
2
answers
317
views
How to optimize non-tail recursion?
Tail recursion, where a function calls itself as the last step, is straightforward to optimize as to prevent unbounded stack growth: tail call optimization applies.
However, this doesn't apply to ...
- 8,563
5
votes
1
answer
179
views
Built-In Asynchronous Loops (Not Functions) - Do they / could they exist?
When writing a game's event loop, I always rely on a function from an external library, like draw() in ProcessingJS for ...
- 153
4
votes
2
answers
213
views
Why would Short String Optimization not apply to dynamic arrays?
Short string optimization is the optimization that sufficiently short strings have their data stored inline rather than an external buffer, so the string type ends up being a union. Swift does this, ...
- 8,563
11
votes
5
answers
753
views
What are the pros and cons of a compiler with a single-pass parser?
Assume you are tasked with writing a compiler for a language that can be parsed in a single pass, like C, but does not necessarily have to be. What are the pros and cons for doing this? Would you do ...
- 2,588
12
votes
3
answers
2k
views
What are the pros and cons of single-pass compilers?
Okay, we all know the standard compiler architecture: a batch program with multiple passes for parsing, optimizing, and generating code.
Suppose you wanted to go all Turbo Pascal and implement a ...
- 2,588
6
votes
1
answer
123
views
How can task-local variables be implemented?
In some languages, async/await can be simply transformed into callbacks, as if it were syntactical sugar:
...
- 8,563
3
votes
2
answers
408
views
What are the pros/cons of a tree-based interpreter vs a bytecode-VM-based interpreter?
Based on this closed question.
Basically, why would one choose a pure interpreter for a language implementation as opposed to a virtual machine/bytecode approach like Java or Python (even if at ...
- 1,722
4
votes
5
answers
671
views
What are the pros and cons of interpreted programming languages?
Some programming languages are implemented via a source code interpreter instead of a compiler, for example Python, PHP, Ruby and Perl, and these programming languages are very popular.
So, this ...
- 1,521
2
votes
3
answers
166
views
What are the downsides, if any, of using implicit function purity in an impure language?
An idea I had for one of my languages recently was this: function purity makes it easier to do certain optimizations. However, the language I'm designing is an impure imperative language that has an ...
- 2,594
9
votes
1
answer
176
views
How to test a compiler/interpreter?
What are some testing techniques and strategies (in software engineering sense) that are relevant to compilers/interpreters? For example, having a set of complete programs and verifying their runtime ...
- 683
3
votes
1
answer
116
views
How can an abstract-syntax tree be converted into linear three-address code?
I have an abstract-syntax tree (AST) for a language, and I'd like to use some sort of three-address code (TAC) to represent the program in a linear way, before converting it to assembly.
How do I do ...
- 391
5
votes
2
answers
215
views
How are C++ style references implemented behind the scenes? Could they be implemented without pointers?
I would not be surprised if C++ style int &y = x; was no more than int *y = &x; behind the scenes and every use of ...
- 7,285
7
votes
1
answer
368
views
How are hand-written parsers organised, and how do they work?
Below, we have an example of two extremely simple languages and a relationship between the two languages:
Inputlanguage
(-1, 0)
(0, 1)
(1, 0)
(0, 1)
(0, -1)
(1, 0)
(1, 0)
Outputlanguage
"left&...
- 283
2
votes
4
answers
145
views
Approaches for implementing weak references
How can weak references (weakrefs) be implemented, and how do the different approaches compare?
The most important considerations for implementing weakrefs are:
Safety ─ a weakref shouldn't allow ...
- 16.3k
11
votes
4
answers
640
views
Why does Python ignore type hints?
In Python, everything is treated as an object. This means that CPython interpreter will decide on the fly, what is the type of each variables or the function return type depending on the current state....
- 213
4
votes
2
answers
149
views
How does a compiler know that an identifier in an expression refers to a memory location, or the value stored at that location?
There are situations during compilation when some identifier represents a particular value ("contained" in a variable, etc), but sometimes it references the variable's memory location ...
- 391
11
votes
3
answers
157
views
How are strings, lists and dicts implemented in bytecode?
How do I implement strings, lists and dicts in bytecode?
For example, disassembling the bytecode might look like this:
LOAD str "hello, world"
But how ...
- 1,521
11
votes
1
answer
178
views
How to implement a REPL for a compiled language?
Implementing a REPL is relatively straightforward for an interpreted language; the interpreter maintains the program state as normal, and evaluates each separate statement as normal, just using the ...
- 16.3k
6
votes
1
answer
138
views
What are the pros and cons of ways to implement the LOAD command in a statically typed VM?
What are the pros and cons of ways to implement the LOAD command in a statically typed VM?
There is two ways to implement LOAD ...
- 1,521
12
votes
1
answer
150
views
How do I implement coroutines on WebAssembly?
I am building a compiler targeting WebAssembly for a language that makes heavy use of first-class coroutines. WASM doesn't have native coroutine support (yet), so I have to emulate it. Given the ...
- 10.9k
8
votes
2
answers
149
views
How can I reduce the amount of AST duplication in my code?
I'm working on a language that transpiles to Lua, and writing the transpiler in Kotlin. One problem I'm having is that I simply have too many AST types. I have an untyped AST, a typed AST, and a Lua ...
- 2,594
6
votes
1
answer
128
views
How do I implement branch prediction for JIT?
I have a language with a working interpreter, and I am trying to add just-in-time compilation (JIT) to it. For ease of implementation, only individual branches are compiled, while control flow ...
- 8,563
6
votes
2
answers
91
views
Organizing a large number of built-in instructions
I am currently writing a Funge-98 interpreter in Go following the Funge-98 specification and need to handle all of its built-in instructions. However, this is proving to be unwieldy, because there's ...
- 1,633
4
votes
2
answers
140
views
How can I implement a control flow graph?
A Control-Flow-Graph is:
In computer science, a control-flow graph (CFG) is a representation, using graph notation, of all paths that might be traversed through a program during its execution.
The ...
- 1,553
10
votes
1
answer
172
views
How is fixpoint of type exponentiation implemented?
Fixpoint of type addition or type multiplication is no big deal. You just need to store data in heap. Haskell does this well for lists for example:
...
- 495
8
votes
1
answer
113
views
How can runtime type checks be implemented?
Most if not all OO languages have some way to determine whether an object belongs to a given class at runtime. In some languages -- both interpreted (like JS) and compiled (like Objective-C) -- ...
- 8,563
5
votes
5
answers
331
views
How could fixed-point be implemented?
Fixed point is essentially storing a number of units of a certain size instead of storing a significand and an exponent. However, if the units could be of any size, how big would the fixed-point units ...
- 7,285
7
votes
1
answer
148
views
How are generators implemented?
Several languages, such as JavaScript, C#, and Python, have "generator" methods that lazily yield a series of values rather than returning a single one:
...
- 8,563
11
votes
2
answers
188
views
Is it possible to bootstrap an interpreted language?
Is it possible to bootstrap an interpreted language? Bootstrapping, broadly, refers to writing a programming language in that same programming language.
This is obviously possible for compiled ...
- 1,553
8
votes
1
answer
116
views
When should I use a hand-written parser over a parsing library?
There are plenty of libraries out there that provide tools like LL parsers, combinator parsers, ebnf parsers and more. However, these may not always be suited to the grammar of a programming language.
...
- 1,747
5
votes
3
answers
160
views
How can I reconcile “all functions are variables” with a typeclass type system?
In my WIP language, all functions are really just variables with a callable type. That is, a function call foo(bar) is parsed into the following AST:
...
- 2,594
10
votes
1
answer
244
views
How do I implement AOT compilation of my 2-D esolang?
Background
Trilangle is an interpreted 2-D esolang that I made in February and March of this year. At some point, I had the idea to implement an ahead-of-time compiler for the language, and what ...
- 8,563